Chain Replication: Why the Head Writes and the Tail Reads

A quorum scheme distributes a write across a set and lets any sufficiently large subset acknowledge it. Chain replication does the opposite: it puts the replicas in a line and passes the write down the line, one hop at a time. The cost is that a write’s latency includes the chain’s length; the benefit is that the ordering of writes is decided in exactly one place, so every replica applies the same sequence without a consensus round.

The write path

The chain has a head, a set of middle nodes, and a tail. A client sends its write to the head only. The head applies it to its own copy, then forwards it to the next node, which applies it and forwards, and so on to the tail. The tail’s acknowledgement goes back up the chain, and the head returns success to the client when the tail has acknowledged.

Because the forward path is a single ordered sequence of hops, every node applies writes in the order the head received them, and no node can be ahead of its predecessor. The invariant that results is strong and simple: a node’s copy is a prefix of its successor’s history. The head’s history is the shortest, the tail’s is the longest, and the difference between adjacent nodes is exactly the writes in flight on that link.

Reads go to the tail. The tail has applied every write the head has acknowledged, plus possibly some that are still propagating, so a read at the tail is linearizable with respect to writes that have returned to the client. It is also the only node whose state can be treated as authoritative without asking anyone else. The head could serve reads, but it would return a state that may be missing writes that are already on the wire, and the client would see its own acknowledged write vanish and reappear.

# Sketch of the forwarding invariant: each hop applies, then forwards.
def handle_write(self, seq, op):
    if seq != self.last_applied + 1:
        raise ValueError(f"gap at {seq}")     # the chain guarantees contiguity
    self.apply(op)
    self.last_applied = seq
    if self.successor:
        self.successor.forward(seq, op)        # synchronous: wait for downstream ack
    else:
        self.client_ack(seq)                  # tail acknowledges; ack propagates back

The synchronous hop is what makes the guarantee, and it is also what makes the latency $L$ hops instead of one. Pipelining helps throughput, since the head can accept the next write while the previous one is still travelling, but it does not shorten the latency of a single write, because the client’s acknowledgement still waits for the tail. This is the fundamental trade against a quorum scheme: chain replication pays in latency for a simpler correctness argument, and a quorum scheme pays in protocol complexity for a latency that can be as short as the fastest W acknowledgements.

Why the tail is the read point

The read-at-tail rule is the source of the design’s read throughput advantage in the original proposal, because reads and writes go to different nodes and do not contend for the same lock or the same disk queue. The head is write-only, the tail is read-only, and the middle nodes do neither from the client’s perspective. With a chain of three, the system has effectively one dedicated write node and one dedicated read node, which is a better use of three machines than three nodes each doing both.

The rule also makes read scaling trivial in the trivial case: multiple clients read the tail, and the tail’s capacity is the read capacity. It does not scale beyond that without a mechanism, because there is only one tail. CRAQ addresses this by letting any node serve a read, provided the node can prove its copy is clean, meaning that no write has been applied locally but not yet acknowledged by the tail. The mechanism is a dirty/clean flag per object: a node marks an object dirty when it applies a write and clears the flag when the tail’s acknowledgement propagates back. A read at a non-tail node that finds the object clean returns it directly; a read that finds it dirty must ask the tail, or wait.

The dirty-flag scheme converts the read bottleneck into a read fan-out, at the cost of per-object state and a reverse acknowledgement path. The reverse path is the part that costs: the tail’s acknowledgement has to travel back through every node, so each node learns when its copy became clean. That is the same number of hops as the write, in the opposite direction, and it doubles the message count per write.

Failures at the two ends

The chain’s simplicity is concentrated in the middle and complicated at the ends. A middle node failure is easy: the predecessor and successor reconnect, and the chain continues with one fewer link. The writes in flight on the failed node’s inbound link may be lost, so the predecessor must resend everything the failed node had not yet acknowledged downstream, which requires the predecessor to keep a buffer of unacknowledged writes. That buffer is the only state the failure path needs, and its size bounds how much work a middle failure can cost.

A tail failure is also manageable, because the tail has no successor: the new tail is the previous node, and it already holds a prefix of the old tail’s state. Writes acknowledged by the old tail may be missing from the new tail if they were applied at the old tail but not yet propagated back, but propagation is exactly the acknowledgement path, so a write the client saw acknowledged had reached the tail and its acknowledgement had reached the head, which means every node in the chain had already applied it. The new tail therefore has every acknowledged write. This is a property worth stating plainly because it is the reason chain replication is described as tolerating tail failure without data loss.

A head failure is the hard case. The head is where ordering is decided, so its loss removes the authority that assigns sequence numbers. The writes in flight may be partially propagated: some nodes have them, some do not. The remaining chain must elect a new head and must decide what to do with the in-flight writes, and that decision is a consensus problem, which is why chain replication is usually paired with a separate membership service, a Paxos or ZooKeeper-style protocol that decides who the head is and publishes the chain configuration.

The membership service is not an implementation detail; it is the part of the design that provides the guarantee the chain cannot provide for itself. Chain replication gives ordering and read consistency conditional on a stable chain; the membership service provides the stability. A system that implements the chain without a membership service has an ordering guarantee that evaporates whenever the head changes.

Reconfiguration

Changing the chain is the operation that exposes the most edge cases. Adding a node to the middle is straightforward: the predecessor starts forwarding to the new node, which forwards to the old successor, and the new node catches up by copying the predecessor’s state before it starts accepting forwards. The catch-up must be done while writes continue, so the new node is fed the current state and then the writes that occurred during the copy, in order.

Changing the head is the same problem as head failure but voluntary. The old head must stop accepting new writes, drain the in-flight ones to the tail, and then hand authority to the new head. During the drain the chain is write-unavailable, which is why head changes are rare and why the chain length is kept short enough that the drain is fast.

Removing a node requires the predecessor to buffer the writes that were in flight to the removed node and resend them to the successor. The successor must be able to accept them in order, which it can, because the sequence numbers come from the head and the successor’s applied prefix is behind the removed node’s.

The configuration itself has to be versioned, and every node must know which version it is operating under. A node that receives a forward tagged with a configuration version it does not recognise must reject it rather than apply it, because the chain’s shape determines the meaning of “next”. This is the same versioning problem that ring membership has, in a form where a stale version produces a broken chain rather than a misplaced key.

Where the design fits

Chain replication suits workloads where writes are the throughput bottleneck and reads can be concentrated or fanned out with a dirty-flag mechanism. It does not suit workloads where a single write must have minimal latency, because the chain’s length is directly in the latency. It does not suit geographically distributed replicas, because a chain spanning three continents makes every write pay three wide-area round trips, whereas a quorum write can be acknowledged by the two closest replicas.

The comparison to quorum intersection is exact. A quorum write of W replicas can complete in one round trip if the client contacts all W in parallel; a chain write takes L hops in series. A quorum read of R replicas must reconcile versions, which requires version metadata and a merge rule; a chain read at the tail needs no reconciliation because there is only one version. The chain trades a latency constant for the elimination of a reconciliation path, and that trade is favourable exactly when reads outnumber writes and the reconciliation path is the expensive part.

The residual limitation is the one shared by every scheme that concentrates authority: the head is a single point of write serialisation, and its throughput is the write throughput of the chain. Sharding by key range multiplies that throughput by the number of chains, which is why chain replication appears in practice as a per-shard mechanism inside a partitioned store rather than as a whole-cluster design.