Chain Replication

Keeping multiple copies of data alive so that no single server failure loses anything is one of the oldest jobs in distributed systems. The hard part is making those copies agree — a client should never see a stale value just because a replica is a step behind.

Most replication protocols solve agreement through voting among replicas, with all the coordination complexity that entails. Chain replication, introduced by Renesse and Schneider in 2004, takes a radically different approach: arrange the replicas in a line, route every write through the line from head to tail, and let reads be answered only by the tail.

The result is strong consistency — as strong as reading from a single server — with a protocol so simple you can sketch it on a napkin. The trade-off is that write latency grows linearly with chain length, but for many workloads that is a price worth paying for the clarity and correctness guarantees you get in return.

Below is a live chain of three replicas — Head, Middle, and Tail. Type a value and press Send Write to dispatch it. The write travels node by node; the acknowledgment only travels back once the Tail has committed.

<!-- {{c_html_intro}} -->
<div class="controls">
  <input id="val-input" type="text" maxlength="12" placeholder="{{placeholder_val}}" autocomplete="off" />
  <button id="btn-write" type="button">{{btn_write}}</button>
</div>
<div id="chain" class="chain"></div>
<div class="action-row">
  <button id="btn-fail" type="button" class="ghost">{{btn_fail}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="status" class="status"></div>
<div id="log" class="log"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; gap: .5rem; margin-bottom: .8rem; flex-wrap: wrap; }
input { padding: .4rem .7rem; border: 1px solid #ccc; border-radius: 8px;
        font: 600 14px system-ui, sans-serif; width: 140px; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
/* {{c_css_chain}} */
.chain { display: flex; align-items: center; gap: 0; margin: .6rem 0 1rem; flex-wrap: wrap; }
.node { width: 80px; text-align: center; }
.node-box { border: 2px solid #1d3557; border-radius: 10px; padding: .4rem .2rem;
            background: #e8eef3; position: relative; transition: background .25s, border-color .25s; }
.node-box.active { background: #ffd166; border-color: #e6a200; }
.node-box.failed { background: #f1f1f1; border-color: #bbb; color: #999; }
.node-label { font-size: .7rem; font-weight: 700; color: #1d3557; text-transform: uppercase;
              letter-spacing: .05em; }
.node-box.failed .node-label { color: #aaa; }
.node-val { font: 700 18px ui-monospace, monospace; min-height: 1.5em; color: #1d3557; }
.node-box.failed .node-val { color: #ccc; }
.node-role { font-size: .65rem; color: #5a7088; margin-top: .15rem; }
.node-box.failed .node-role { color: #bbb; }
/* {{c_css_arrow}} */
.arrow { width: 32px; text-align: center; font-size: 1.3rem; color: #1d3557; flex-shrink: 0; }
.arrow.faded { color: #ccc; }
.action-row { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-bottom: .3rem; }
.status.ok { color: #0a7d33; }
.status.err { color: #c92f3c; }
.status.info { color: #1d3557; }
/* {{c_css_log}} */
.log { font-size: .78rem; font-family: ui-monospace, monospace; color: #555;
       max-height: 120px; overflow-y: auto; border-top: 1px solid #ddd; padding-top: .4rem; }
.log-entry { margin-bottom: .15rem; }
.log-entry.ack { color: #0a7d33; }
.log-entry.fail { color: #c92f3c; }

// Code not found

Notice the direction: writes always flow left to right, and only the tail answers clients. Add a simulated failure with Fail a node to see how the chain simply skips that link — the remaining nodes still form a valid (shorter) chain with full consistency guarantees intact.

What makes chain replication tick, and what are its real costs?

• Write path: a client sends a write to the head. Each node stores it and forwards it to the next. The tail commits and sends an acknowledgment back up the chain to the client. Latency for one write is proportional to the chain length $k$: roughly $k$ network round-trips.
• Read path: reads go directly to the tail, which always holds the committed state. No voting, no quorums. Read throughput is limited only by the tail's capacity.
• Linearizability: because every committed value has passed through every node in order, and the tail is the single point of truth, chain replication provides linearizability — the gold standard of consistency. Every read sees the most recently committed write.
• CRAQ (2009): Terrace and Freedman's Chain Replication with Apportioned Queries lets any node serve reads, not just the tail. A node answers a read immediately if its copy is clean (not awaiting a write in flight); otherwise it asks the tail for the latest committed version. This spreads read load evenly while preserving linearizability.
• Failure handling: the master (or a consensus service like ZooKeeper) watches the chain. If the head fails, the second node becomes the new head. If the tail fails, its predecessor becomes the tail. Middle-node failures are stitched over by relinking neighbors. No ongoing write is lost as long as at least one node survives.
• Throughput: writes and reads can be pipelined — the head can accept a second write before the first has reached the tail. Under high write load, throughput approaches the bandwidth of a single link because all $k$ nodes process different writes simultaneously.

Compare this to a Paxos-style quorum: both achieve linearizability, but chain replication achieves it with a completely deterministic message flow. There is no leader election per operation, no voting round — just a conveyor belt.

Chain replication's combination of simplicity and strong consistency has made it a foundational building block in real systems:

• Object storage: Amazon S3 and similar systems use chain-like replication internally to keep multiple copies of objects consistent across availability zones without expensive all-to-all coordination.
• Key-value stores: systems like Riak and TiKV have adopted chain or chain-inspired replication to combine high read throughput with strong consistency guarantees.
• Distributed databases: CockroachDB and YugabyteDB use Raft (a cousin of chain replication) for strongly consistent replication of partition leaders.
• HDFS pipelines: the Hadoop Distributed File System uses a write pipeline identical in spirit to chain replication — data blocks flow through a chain of DataNodes before the write is acknowledged.
• Research baseline: chain replication is the canonical example used in distributed systems courses to introduce linearizability, fault tolerance, and the tension between consistency and latency. See also max-flow for another case where a linear structure unlocks surprisingly clean guarantees.

Whenever you need "reads always return the last committed write" without the complexity of a full consensus protocol, chain replication is the answer.

Chain replication is a beautiful proof that structure can replace coordination. By forcing writes to flow in one direction and letting only the tail answer reads, you get linearizability — the strongest guarantee a distributed system can offer — with a message pattern so regular it can be reasoned about by hand.

The protocol is not magic: write latency scales with chain length, and you need an external service to manage membership. But within those constraints it delivers something rare in distributed systems: a guarantee so crisp that it requires almost no explanation. Next time someone tells you that strong consistency requires complex voting protocols, point them at a chain.