Skip to content

CONCEPT Cited by 1 source

Replicated log

A replicated log is a sequence of ordered slots, each containing a decided event, maintained identically across all functioning replicas in a distributed system. It is the core abstraction underlying most consensus-based systems.

Definition

  • The log is a sequence of slots — each slot can contain an event or be empty (not yet decided)
  • A decided slot contains an event that a majority of replicas have agreed upon
  • The invariant: if any two replicas decide on the value for a slot, those values are the same
  • A replica may lag behind (not yet know about a decision) but will never record a different entry

How it enables strong consistency

Applications are layered on top of the log. A key-value store, for example, applies operations from the log in sequence to construct state. Because all replicas have the same log, applying operations in order produces identical state on every replica.

Both reads and writes become log events. A read must go through consensus to ensure it is ordered after all prior writes — this is what makes the system linearizable.

Relationship to consensus

A consensus algorithm is run for each slot to decide its value. Only one proposal for a given slot can win — the consensus algorithm ensures a majority agrees on which one.

Meerkat instance

In Meerkat, each replica translates application requests (KV get/put) into log events. The replica distributes each event to all other replicas via QuePaxa. Applications hosted on the replica read the decided events and construct state.

Seen in

Last updated · 573 distilled / 1,747 read