Shared Log as Consensus — State Machine Replication

Shared Log as Consensus — State Machine Replication A data-flow diagram generated by Archify. 01 / Propose 02 / Append 03 / Total order 04 / Replicate 05 / Apply Client 1 writes · concurrent · 01 / Propose · propose value Client 1 writes concurrent propose value Client 2 writes · concurrent · 01 / Propose · propose value Client 2 writes concurrent propose value Client 3 writes · concurrent · 01 / Propose · propose value Client 3 writes concurrent propose value Leader · single writer · 02 / Append · append entry Leader single writer append entry Shared log · entries #1 #2 #3 · 03 / Total order · total order Shared log entries #1 #2 #3 total order Quorum copy · replica copies · 04 / Replicate · majority ack Quorum copy replica copies majority ack Apply in order · in log order · 05 / Apply · deterministic Apply in order in log order deterministic Fencing token · monotonic counter · 03 / Total order · log index = token Fencing token monotonic counter log index = token Serial txns · stored procedure · 03 / Total order · one per entry Serial txns stored procedure one per entry State machine · deterministic logic · 05 / Apply · same final state State machine deterministic logic same final state propose write concurrent propose write concurrent propose write concurrent append log entry replicate synchronous deliver in order majority ack apply deterministic index = token monotonic stored procedure per log entry Legend primary data policy / PII async batch data store data flow