Lesson 32 · Replication topologies · Module 3
Chain Replication
A quorum buys consistency by counting votes on every single operation. There is another shape that buys the same guarantee by arranging the replicas in a line — writes enter at one end, reads are answered at the other, and nobody votes on anything.
The win in this lesson: you will be able to explain why serving reads from the tail alone gives you linearizable reads with no coordination at read time, and say honestly what that costs against a quorum.
1. The problem: agreement is expensive per operation
Lesson 05 left you with a dial. Set R + W > N and every read contacts enough replicas to
be sure it intersects the last write. That works, and the bill arrives on every operation: a read is a
fan-out, and its latency is the slowest replica in the read set.
Chain replication asks a different question. Instead of proving at read time that this reader has seen enough replicas, arrange the replicas so that there exists one server whose state is, by construction, never ahead of anybody. Then a read of that one server needs no proof at all.
"Chain replication is a new approach to coordinating clusters of fail-stop storage servers. The approach is intended for supporting large-scale storage services that exhibit high throughput and availability without sacrificing strong consistency guarantees."
Chain Replication for Supporting High Throughput and Availability, van Renesse and Schneider, OSDI '04 · Abstract. De-hyphenated across a PDF line break: "with-out".
2. The arrangement
"In chain replication, the servers replicating a given object objID are linearly ordered to form a chain."
§3, Chain Replication
Three rules, and they are the whole protocol:
| Rule | The paper's words | Consequence |
|---|---|---|
| Updates enter at the head | "Each update request is directed to the head of the chain." | One server orders all writes |
| Queries are answered at the tail | "Each query request is directed to the tail of the chain and processed there atomically using the replica of objID stored at the tail." | One server orders all reads, against the oldest state in the chain |
| Every reply comes from the tail | "The reply for every request is generated and sent by the tail." | A write is acknowledged only once the whole chain holds it |
Between head and tail, state changes move down a link that does not reorder or lose them:
"state changes are forwarded along a reliable FIFO link to the next element of the chain (where it is handled and forwarded), and so on until the request is handled by the tail."
§3, Chain Replication. De-hyphenated: "for-warded", "han-dled".
3. Why this is strongly consistent
The paper's justification is one sentence, and it is worth memorising:
"Strong consistency thus follows because query requests and update requests are all processed serially at a single server (the tail)."
§3, Chain Replication. De-hyphenated: "re-quests".
Reads and writes are not merely each serialised — they are serialised against each other, at one place, in one queue. That is exactly the shape Lesson 23 asked for: a single global order that every client agrees on, with every operation appearing to take effect at one instant between its call and its return.
The structural fact underneath is the invariant that makes the tail special:
"Because updates are sent between elements of a chain over reliable FIFO links, the sequence of updates received by each server is a prefix of those received by its successor."
§3.1, Chain Replication · Update Propagation Invariant
A read needs no coordination when the server it reads holds only state that every other replica already has. The paper says it in a single line: "In chain replication, the tail is the one replica known to store all completed updates." (§6) A quorum discovers the committed value by intersecting sets at read time. A chain positions a server so that its local state already is the committed value.
And so the read costs what a read costs:
"Processing a query request involves only a single server, and that means query is a relatively cheap operation."
§3, Chain Replication
4. Failure: the master repairs the chain
Nothing above survives a crash on its own. A separate service — the master — detects failures, rewires each survivor's predecessor and successor, and "informs clients which server is the head and which is the tail of the chain." (§3.1)
4.1 Head failure — the cheap one
"This case is handled by the master removing H from the chain and making the successor to H the new head of the chain."
§3.1, Chain Replication · Failure of the Head
Requests the dead head had received but not yet forwarded are simply lost — and that is legal, because they were never acknowledged to anyone. Reads are untouched: "Head Failure. Query processing continues uninterrupted. Update processing is unavailable for 2 message delivery delays" (§4, de-hyphenated: "un-interrupted").
4.2 Tail failure — the expensive one
"This case is handled by removing tail T from the chain and making predecessor T− of T the new tail of the chain."
§3.1, Chain Replication · Failure of the Tail. De-hyphenated: "re-moving", "predeces-sor"; the paper's superscript minus is written here as T−.
Look at the prefix ladder again and this is obviously safe: the predecessor's history is a superset of the dead tail's, so promoting it can only reveal updates, never lose one. Some requests that were in flight become committed the instant the new tail takes over. Nothing that had already been acknowledged can disappear.
This is the only case where reads stop: "Tail Failure. Query and update processing are both unavailable for 2 message delivery delays while the master sends a message to the new tail and then notifies all clients of the new tail using a broadcast." (§4)
4.3 Middle failure — the one with bookkeeping
A middle server can fail holding an update its successor never received. Drop it from the chain naively and the prefix invariant breaks. So each server keeps a list of what it has forwarded but not yet seen acknowledged:
"Whenever server i forwards an update request r to its successor, server i also appends r to Sent i. The tail sends an acknowledgement ack (r) to its predecessor when it completes the processing of update request r. And upon receipt ack (r), a server i deletes r from Sent i and forwards ack (r) to its predecessor."
§3.1, Chain Replication · Failure of Other Servers. De-hyphenated: "succes-sor"; the paper subscripts the i in "Sent i".
The repair order matters, and the paper is specific: "The master first informs S's successor S+ of the new
chain configuration and then informs S's predecessor S−." (§3.1) The new predecessor then replays its
Sent list before it sends anything new.
The paper's own summary of the middle case: "Middle Server Failure. Query processing continues uninterrupted. Update processing can be delayed but update requests are not lost, hence no transient outage is experienced, provided some server in a prefix of the chain that has received the request remains operating." (§4)
# the invariant every repair must preserve
history(head) ⊇ history(middle) ⊇ history(tail)
# what each failure does to it
head dies → drop head; unforwarded, unacked requests vanish (reads unaffected)
middle S dies → wire S− to S+; S− replays Sent(S−) first (reads unaffected)
tail dies → promote T−; history can only grow, never shrink (reads pause)5. The trade against a quorum
Two honest costs, and the paper names both.
Read throughput is capped at one machine. Adding replicas to a chain lengthens it; it
does not add read capacity, because every query still lands on the tail. A quorum system with
R = 1 spreads reads over all N — at the price of a weaker guarantee — and even a
quorum read at R = 2 of N = 5 uses far more of the cluster than a chain ever does.
Write latency is the length of the chain. A quorum writes in parallel and waits for the
slowest of W. A chain writes serially and waits for the sum:
"With parallel dissemination, the time needed to generate a reply is proportional to the maximum latency of any non-faulty backup; with serial dissemination, it is proportional to the sum of those latencies."
§4, Chain Replication
The paper's own worked figure makes the asymmetry concrete: "if a chain comprises three servers, the total latency to perform an update is 94 ms […] Query latency is only 7 ms, however." (§5.1, de-hyphenated: "pro-cess"; the elision removes the per-hop breakdown.)
| Dimension | Chain replication | Quorum (Lesson 05) |
|---|---|---|
| Read path | Tail only, one server | R replicas, chosen per query |
| Read coordination | None — position does the work | Intersection computed on every read |
| Read throughput | Capped at one node, whatever N is | Scales with N / R |
| Read latency | One hop to the tail | Slowest of the R replicas |
| Write path | Serial, head to tail | Parallel fan-out to W |
| Write latency | Sum of the hops | Max of the W replicas |
| Durability of an ack | Every replica in the chain holds it | W replicas hold it |
| Guarantee | Strong consistency, stated outright | "Quorum-like"; ordering still your problem |
| Concurrent writes | Ordered by the head, no conflicts | Can both succeed and diverge |
| Membership changes | An external master, itself run on consensus | Preference lists, sloppy quorums, hinted handoff |
| Slow replica | Delays writes; reads only if it is the tail | Can be voted around if N exceeds R |
Read the last two rows together with Lesson 05. Dynamo bent its quorum to stay writeable during failures and paid in conflicts the application had to merge. A chain refuses that bargain: it would rather pause writes for two message delays and never hand you two versions of the same object.
6. Residual risk
- The tail is a hot spot by design. Every read and every reply leaves from it. Sizing the system means sizing that one node for the whole read load of the chain.
- The master is the real single point of failure, and making it not one costs you a consensus protocol. The elegance of the data path is paid for on the control path.
- Repair rebalances badly. After a server recovers and is re-added, the paper observes that it "will now participate in fewer chains than other servers but will be the tail of every chain in which it does participate. So the load is no longer well balanced over the servers, and aggregate query throughput is lower." (§5.3, de-hyphenated: "through-put".) A recovered node becomes a tail-shaped hot spot for every chain it joins.
- Longer chain, slower writes, better durability. There is no setting of chain length
that is good at both, and unlike
RandWyou cannot vary it per operation. - Everything assumes fail-stop. A server that is alive but wrong — a corrupt replica silently forwarding garbage — is outside the model, and the tail will serve that garbage with full confidence.
7. Check yourself
8. Back to your world
You are unlikely to deploy a chain. You are very likely to meet its shape: a write path that must land everywhere before it is acknowledged, and a read path deliberately pinned to one place so it needs no agreement. Object stores, replicated logs and several modern storage engines borrow exactly this.
- Where is your read path allowed to be pinned? If one node can serve every read, you can have linearizability for free. If it cannot, you are buying a quorum whether you wanted one or not.
- What does an acknowledgement mean in your system? "All replicas have it" and "a majority have it" are different promises, and they fail differently.
- Who is your master, and what happens when it is wrong? Every chain has one. If yours is a health check and a DNS record, you have a master with no consensus behind it.