vault

Chain Replication

16 min read

Chain Replication

Chain replication is a mechanism for coordinating a cluster of fail-stop storage servers that delivers strong consistency at high throughput by arranging the replicas of an object into a linear chain: every update enters at the HEAD and propagates node-by-node down the chain, while every query is served by the TAIL — and because the tail holds only updates that have already reached the end of the chain, a read at the tail can only ever return committed state, which is what makes reads strongly consistent for free. It was introduced by Robbert van Renesse and Fred B. Schneider in “Chain Replication for Supporting High Throughput and Availability” (OSDI 2004), who frame it explicitly as “a form of the primary/backup approach” that is itself an instance of the state-machine approach. Its signature insight is to split the primary’s two jobs — ordering writes and answering reads — across two different nodes (head and tail), so that the load a lone primary would carry alone is shared, yielding equal-or-better throughput than primary-backup while keeping strong consistency. The read-scaling descendant CRAQ (Chain Replication with Apportioned Queries, Terrace & Freedman, USENIX ATC 2009) removes the tail read-bottleneck by letting every node answer reads while still guaranteeing the tail’s committed value.

Boundary with the topology and RSM notes

This is a mechanism note in §6 of the Distributed Systems MOC. The general idea of running identical state machines by replaying an agreed input order lives in Replicated State Machine Architecture; the single-authority protocol chain replication specializes lives in Primary-Backup Replication; the quorum-intersection alternative lives in Read and Write Quorums. This note traces chain replication’s specific protocol — its invariants, its failure handling, and CRAQ — and cross-links rather than re-explaining those neighbors.

Mental Model — Split the Primary Into a Head and a Tail

Start from Primary-Backup Replication: a single primary orders writes, ships them to backups, waits for acks, and answers reads. Its weakness is that the one primary does all the work — ordering, dissemination bookkeeping, and read serving — so it is the throughput ceiling. Chain replication’s move is to take those duties apart and lay the replicas in a line. The head owns write ordering (it is where updates enter and get their serial position). The tail owns read serving and, implicitly, commit: an update is “committed” precisely when it reaches the tail. The nodes in between just relay. Because reads come from the tail and writes leave from the head, the two heaviest duties run on different machines.

flowchart LR
    U["update"] -->|"enter here"| H["HEAD"]
    H -->|"FIFO"| M1["node"]
    M1 -->|"FIFO"| M2["node"]
    M2 -->|"FIFO"| T["TAIL"]
    T -->|"reply to update client"| U
    Q["query"] -->|"served here"| T
    T -->|"reply to query client"| Q

What it shows and the insight to take: updates travel strictly left-to-right along reliable FIFO links; queries touch only the rightmost node. The insight is that the tail is a natural commit point — anything the tail has seen has, by construction, already passed through every replica to its left, so it is durable and strongly consistent, and anything the tail has not seen is still “in flight” and invisible to readers. Serving reads at the tail therefore gives strong consistency without any extra coordination: there is no quorum to gather, no versions to reconcile, just “ask the last node.” The cost, which CRAQ later attacks, is that a single node (the tail) carries the entire read load.

The Storage-Service Interface

The paper first specifies what a storage service does, independent of chain replication, so the protocol can be proved to implement it. An object’s state is two variables (OSDI ‘04, Figure 1):

  • Hist_objID — the sequence of updates already performed on the object (its history).
  • Pending_objID — the set of requests received but not yet processed.

Three transitions govern them: T1 a client request r arrives → add r to Pending; T2 a pending request is ignored → remove it from Pending (a lost/dropped request is indistinguishable to the client from one that was never sent — the end-to-end argument says clients must retry anyway); T3 a pending request is processed → remove it from Pending, and if it is a query reply from Hist, else if it is an update append it to Hist (Hist := Hist · r) and reply. Queries are idempotent (they do not change Hist); updates need not be, so a client re-issuing a non-idempotent update must guard against double-application — the ambient at-least-once reality.

The Protocol and Its Consistency Argument

Servers are assumed fail-stop: a server halts rather than making an erroneous transition, and its halt is detectable by the environment. With an object replicated on t servers, up to t − 1 may fail without compromising availability. The chain linearly orders those t servers; concretely (OSDI ‘04, §3):

  • Update processing. Each update is directed to the head, processed there atomically against the head’s replica, and the resulting state change is forwarded down a reliable FIFO link to the next node, and so on until the tail handles it. The non-deterministic choice in an update (if any) is made once, by the head, and the computed difference is what flows down the chain — so each downstream replica only performs a cheap write, never a re-computation.
  • Query processing. Each query is directed to the tail and answered atomically from the tail’s replica.
  • Reply generation. Every reply — for both updates and queries — is generated and sent by the tail.

Strong consistency follows immediately because all queries and all update-completions are serialized at a single server (the tail). The subtle part is proving the chain actually implements the abstract Hist/Pending. The paper defines Hist_objID ≜ Hist^T_objID (the object’s history is whatever the tail has), and Pending_objID as the set of requests received by any server in the chain but not yet processed by the tail. It then establishes the two invariants that carry the whole correctness argument:

  • Update Propagation Invariant. For servers labelled i and j with i ≤ j (i.e. i is a predecessor of j, closer to the head), Hist^j_objID ⪯ Hist^i_objID — read ⪯ as “is a prefix of.” In words: a server closer to the tail has a history that is a prefix of the history of any server closer to the head. The head is always furthest ahead; the tail always furthest behind. This holds because updates flow head-to-tail over FIFO links, so each server has seen a prefix of what its predecessor has seen.
  • Inprocess Requests Invariant. For i ≤ j, Hist^i_objID = Hist^j_objID ⊕ Sent_i, where Sent_i is the list of updates server i has forwarded to its successor but that have not yet been acknowledged by the tail. This says the “gap” between a predecessor and a successor is exactly the set of still-in-flight updates.

Why do these give strong consistency (operations appear to execute in one sequential order and every read sees the latest committed write)? Because the tail defines both the commit order (an update is committed when the tail appends it) and the read order (queries read the tail’s history), and the Update Propagation Invariant guarantees the tail’s history is a genuine prefix of every replica’s — so the tail can never return a value that some replica would contradict. A read at the tail sees exactly the committed prefix, nothing partial. This is linearizable single-object behaviour.

Coping With Server Failures

Failures are handled by a master service that detects halted servers (fail-stop guarantees detectability), informs each surviving server of its new predecessor/successor, and tells clients which server is now head and tail. The paper assumes a single, never-failing master for exposition but notes the real prototype replicates the master over multiple hosts coordinated by Paxos so it behaves like one non-failing process — a crucial detail, because a lone master would be a single point of failure. There are three cases, and the elegance is how little has to be done in each (OSDI ‘04, §3):

  • Head failure. The master removes the head and makes its successor the new head. Query processing is uninterrupted (queries hit the tail, untouched). Update processing pauses for the two message-delays it takes the master to notify the new head and its successor. Deleting the head only drops requests it received but had not forwarded — those were still in Pending, so removing them is consistent with transition T2, and no acknowledged update is lost.
  • Middle (internal) server failure. The master splices server S out by telling S’s successor S⁺ its new predecessor and S’s predecessor S⁻ its new successor. Query processing continues uninterrupted. The one hazard is the Update Propagation Invariant: updates S had received but not yet forwarded past itself must still reach S⁺. Each server keeps its Sent_i list for exactly this — S⁻, on being told S⁺ is its new successor, first re-sends the suffix of Sent_{S⁻} that S⁺ has not yet seen (the master tells S⁺’s last-received sequence number sn so S⁻ can compute the missing suffix), and only then resumes normal forwarding. This four-message reconfiguration restores the invariant with no lost updates.
  • Tail failure. The master removes the tail T and makes its predecessor T⁻ the new tail. Because T⁻ was behind T in the history (Hist^{T⁻} ⪰ Hist^T by the invariant), promoting T⁻ can only increase the committed history — updates T⁻ had received but T had not yet processed now become committed. Query and update processing both pause for two message-delays while the master notifies the new tail and clients.

Extending a chain to replace failed servers keeps chain length near the desired t: a new server is easiest to add at the very end (a new tail T⁺), whose Sent list starts empty; the current tail T forwards its object replica to T⁺ (concurrently with serving requests), and once T⁺ is caught up the master promotes it and redirects clients.

Throughput and Latency vs Primary-Backup

Chain replication is deliberately compared against Primary-Backup Replication because it is a specialization of it. In primary-backup the single primary both sequences update requests and interleaves query requests; chain replication splits that — the head sequences updates, the tail extends the sequence with queries. This sharing does two things (OSDI ‘04, §4):

  • Query throughput. Queries touch only the tail and are never delayed by activity elsewhere in the chain, whereas in primary-backup a query at the primary competes with (and awaits acknowledgements for) prior updates. The paper’s simulations show chain replication has equal or superior throughput to primary-backup across all mixes of updates and all replication factors tested.
  • Update latency. Here chain replication is worse in isolation: it disseminates updates serially down the chain, so update latency is proportional to the sum of the per-hop latencies, whereas primary-backup fans updates to all backups in parallel, giving latency proportional to the maximum single-backup latency. Chain replication trades higher per-update latency for the throughput win and simpler recovery.

The recovery comparison is where chain replication shines. The dominant recovery cost in both schemes is the time to detect a failure — identical for both. After detection, chain replication’s worst case is tail failure (2 message-delays of unavailability), and its best case is middle-server failure (often no transient outage, since a surviving prefix still holds the request). The paper’s punchline: chain replication’s worst-case outage (tail failure) is never as long as primary-backup’s worst case (primary failure), because promoting a backup to primary requires the master to poll all backups for how many updates they hold, pick the most-advanced, and reconcile — several message-delays — whereas promoting the tail’s predecessor is immediate.

CRAQ — Apportioned Queries for Read Scaling

Chain replication’s one blemish is that all reads go to the tail, so read throughput does not scale with chain length — a longer chain buys durability, not read capacity. CRAQ (Terrace & Freedman, ATC ‘09) fixes this while preserving strong consistency, by letting any node answer reads. The mechanism:

  1. Versioned, clean/dirty objects. Each node may store multiple versions of an object, each with a monotonically increasing version number and a flag: clean (known committed) or dirty (possibly uncommitted).
  2. Write propagation marks dirty. When a node receives a new version propagating down the chain, it appends it to the object’s version list. If the node is not the tail, it marks the version dirty and forwards it. If it is the tail, it marks the version clean — this is the commit — and sends an acknowledgement back up the chain. As each node receives that ack, it marks its copy clean and may delete older versions.
  3. Apportioned reads. On a read: if the node’s latest known version is clean, it returns that value locally — no coordination. If the latest is dirty (a write is mid-flight), the node sends a lightweight version query to the tail asking for the tail’s last-committed version number, then returns that version (which it is guaranteed to still hold). Because the tail dictates the committed version even for dirty-node reads, every read across the chain returns the strongly-consistent tail value.

The payoff: for read-mostly workloads, the C − 1 non-tail nodes serve reads as cheap local clean-reads, so read throughput scales linearly with chain length — the paper reports roughly a 200% improvement for three-node chains and 600% for seven-node chains over basic chain replication. Even under write-heavy load, dirty reads only cost a small version query to the tail (far lighter than a full read), so aggregate read throughput still beats basic CR. CRAQ also exposes weaker consistency knobs — eventual consistency (return the newest known version without a version query) and eventual-consistency-with-bounded-inconsistency — that let read-only nodes keep serving during partitions, and it layers on wide-area chain placement (ordering the chain across datacenters so writes cross each boundary once) and ZooKeeper-based group membership in place of CR’s hand-rolled master.

Failure Modes and Common Misunderstandings

  • Write latency grows with chain length. Serial dissemination means a t-node chain pays t hops per update. Longer chains buy durability and (with CRAQ) read scaling but lengthen every write. This is the fundamental tension CRAQ’s wide-area placement tries to manage.
  • The head is a single-object write bottleneck. All writes to one object funnel through its head; chain replication scales reads (via CRAQ) and aggregate writes (via many chains over many objects, mapped by Consistent Hashing), but not concurrent writes to a single hot object.
  • The master is the real dependency. The pretty three-case failure handling assumes a reliable master. A naïve single master is a single point of failure; correct deployments replicate it with Paxos (CR) or ZooKeeper (CRAQ). Getting the master’s membership decisions right — and avoiding two nodes both believing they are the tail — is the genuinely hard engineering, mirroring the split-brain risk in Primary-Backup Replication.
  • Fail-stop is an assumption, not a fact. Chain replication’s correctness rests on servers halting cleanly and detectably. Under omission or Byzantine faults the invariants do not hold; van Renesse later explored Byzantine chain replication as a separate line of work.
  • Dirty-read version-query load. Under sustained write-heavy load in CRAQ, non-tail nodes constantly issue version queries to the tail, re-concentrating load there — CRAQ mitigates this (version queries are cheap) but does not eliminate it; for persistently write-heavy objects the tail can still saturate.

Alternatives and When to Choose Them

Choose chain replication / CRAQ when you want strong consistency and high (read) throughput on a storage service with many objects and read-mostly access — its sweet spot is exactly key-value and object stores. Choose plain Primary-Backup Replication when update latency matters more than throughput (parallel dissemination wins) or the chain would be short. Choose quorum replication when you need to stay write-available under partition and can tolerate reconciling concurrent writes — chain replication, being strongly consistent, blocks writes when the chain cannot be maintained. Choose full consensus (Raft, Multi-Paxos) when you need a replicated log with seamless leader failover rather than a replicated object store; indeed the chain’s master is itself typically backed by consensus. A useful framing: chain replication is state-machine replication specialized to independent single-object updates, trading the generality of a total order across all operations for the throughput of per-object chains.

Production Notes

Chain replication left the lab. Hibari is a production distributed ordered key-value store (originally built at Gemini Mobile for multi-million-user webmail) that uses chain replication for strong consistency and durability, reporting on the order of 2,200 transactions/second on commodity HDDs with single-digit-to-tens-of-milliseconds read latency (Hibari). FAWN-KV and HyperDex both use chain replication as their strong-consistency mechanism (HyperDex with a “value-dependent chaining” twist that threads an object through multiple chains keyed on its attributes). CorfuDB builds on chain-replication ideas for its replicated log, including explicit chain-repair/lengthening protocols (CorfuDB). The recurring practitioner lesson (echoed in Fritchie’s “Chain Replication in Theory and in Practice” on Hibari) is that the protocol is the easy part; the hard part is the membership/master layer — reconfiguring chains correctly on failure, healing shortened chains before a second failure exhausts redundancy, and never letting two nodes disagree about who the tail is.

Uncertain

The specific production adopters (FAWN-KV, HyperDex value-dependent chaining, CorfuDB chain-repair, Microsoft Azure Storage’s stream-layer replication being “a form of chain replication”) were confirmed via search-result summaries and the CorfuDB/Hibari repository pages, not by reading each system’s primary paper end to end during this task. The Fritchie Erlang-Workshop paper (ACM DL) returned HTTP 403 and was not fetched. To resolve: read the FAWN (SOSP ‘09), HyperDex (SIGCOMM ‘12), and Windows Azure Storage (SOSP ‘11) papers directly before citing their internals with precision. #uncertain

See Also

Graph View