The idea: a line of servers, write at one end, read at the other
Chain replication puts the replicas of a key in a line: S1 → S2 → S3. The first server is the head, the last one the tail. A write goes to the head, which applies it and passes it to the next server, and so on down the chain. When the write reaches the tail, every server has it: it is committed, and the tail tells the client OK. A read goes to the tail and returns the tail's value.
The head gives each write a sequence number (seq), so every server applies the updates in the same order. Each server keeps the updates it has passed on but not yet seen acknowledged in a pending list (the paper calls it Sent). After the tail commits seq 2, an ack 2 travels back up the chain and each server drops seq 2 from its pending list (Demo 1). On the canvas a green server holds only committed updates, an orange one still has pending updates.
Why reads at the tail are strongly consistent
The tail only holds updates that every server in the chain already has. So a value the tail returns can never be lost by a crash, and a later read can never return something older. That makes chain replication linearizable without voting or quorums: one server decides the order (the head) and one server answers (the tail).
A read that arrives while a write is still in flight returns the old value (Demo 2). That is correct: the client has not been told OK yet, so the write has not happened as far as anyone can tell. Once the write reaches the tail, the next read returns the new value.
Reading anywhere else
The head is ahead of the tail: it holds updates that are not committed yet. With read from: head a read can return such a value. In Demo 3 the head returns x = 20, then crashes before forwarding it. x = 20 is gone, and the next read at the tail returns x = 10: the reads went back in time. The client never got OK for x = 20, so its next Write resends it to the new head. CRAQ (chain replication with apportioned queries) lets every server answer reads safely: a server with a pending version asks the tail which version is committed.
Failures and the master
The servers do not repair the chain themselves. A separate master (in practice a small Paxos or ZooKeeper group) watches heartbeats, removes a crashed server and tells the neighbours and the client the new chain.
| crash | the master | what happens to writes in flight |
|---|---|---|
| head | makes the next server the head | writes only the old head had are lost; they were never acked, so the client retries (Demo 3) |
| middle | links the predecessor to the successor | the successor reports its last seq; the predecessor resends the rest from its pending list (Demo 5) |
| tail | makes the predecessor the tail | the new tail already holds them: they are committed now, and it answers the client (Demo 4) |
Adding a server
A new server joins at the tail. It first copies the current tail's state, then the master makes it the new tail and tells the old tail to forward to it (Demo 6). A chain of n servers survives n − 1 crashes, but every write takes n hops.
Compared with other replication schemes
| chain replication | primary–replica | quorums (R + W > N) | |
|---|---|---|---|
| write goes to | head, then each server in turn | primary, then all replicas in parallel | all N replicas, wait for W |
| write latency | n hops in a row | one round trip to the slowest synced replica | the W-th fastest replica |
| reads go to | the tail | the primary (or a replica, maybe stale) | R replicas |
| consistency | linearizable | linearizable at the primary only | not linearizable on its own |
| a crash | master reconfigures; a slow server slows every write | failover, possible lost writes with async | no reconfiguration needed |
In real systems
Chain replication appears in the FAWN-KV key-value store, in HDFS's write pipeline (a block's replicas form a pipeline and acks come back along it), in Hibari and in CRAQ-based object stores. Kafka is different: its leader collects followers' fetches in parallel (Kafka replication).
See also Primary–Replica Replication (sync vs async), Quorum Reads and Writes (R + W > N), Leader-based vs Leaderless Replication, Raft (consensus, the kind of protocol the master itself runs) and Consistency Patterns.
What the page leaves out
Timing (failure detection takes a timeout, and the chain is paused while the master reconfigures), more than one key and many clients, batching and pipelining many writes on each link, a crash during reconfiguration, the master's own replication, CRAQ's version queries, the old tail forwarding new updates while a new server copies its state, and servers in different data centers.