KBY Technologies Logo
cd ../lexicon
sys/docs/lexicon/chain-replication.md
Lexicon Entry

Chain Replication

A replication protocol that arranges replicas into a linear order, propagating writes sequentially from the head to the tail while allowing reads to be served exclusively from the tail. It provides strong consistency with strictly stronger throughput characteristics than quorum-based protocols because acknowledgment overhead is decoupled from the write path.

In Chain Replication, replicas R1...Rn are ordered such that R1 is the head and Rn is the tail. A write is sent to the head, applied, and forwarded to the next node in sequence; only when it reaches the tail is it considered committed and acknowledged back to the client (or up the chain, depending on the variant). Because every node processes writes in the exact same total order dictated by chain position, there is no need for a quorum vote or leader election on the write path itself — ordering is structural, not negotiated. This is fundamentally different from Raft or Paxos, where a leader must collect acknowledgments from a majority before committing; chain replication instead pushes the cost of durability confirmation to a single tail node, freeing intermediate replicas from participating in consensus overhead per-request.

The read path is where the design trade-off becomes explicit: standard Chain Replication only serves reads from the tail, guaranteeing linearizability trivially since the tail has processed every committed write in order and nothing else. This makes reads simple but concentrates read load on one node. The CRAQ (Chain Replication with Apportioned Queries) variant relaxes this by allowing any replica to serve reads, provided it first checks whether it has any in-flight (uncommitted) writes for that object; if clean, it answers locally, otherwise it queries the tail to resolve the pending state. This trades a small amount of read latency in the uncommon case for horizontal read scalability across the whole chain.

Failure handling is the operational crux. Losing the head requires promoting R2 to head and requires the control/coordination service (historically implemented via something like Chubby or ZooKeeper) to fence off the old head and notify clients of the new topology — a configuration change, not a per-request negotiation. Losing the tail requires promoting the penultimate node and, critically, replaying any writes that had been acknowledged by the old tail but not yet applied downstream (irrelevant since the tail is the end) or, more subtly, ensuring writes in flight between the new tail and its predecessor are reconciled before the new tail starts serving reads. Losing a middle node requires splicing the chain: the predecessor must re-send any writes the failed node had acknowledged but the successor never received, which demands per-node write buffering until the successor’s ack.

  • Throughput profile: write throughput is bound by the slowest link in the chain (pipeline latency), but each node only does O(1) work per write rather than O(n) message fan-out, making it attractive for high-throughput storage backends (e.g., early versions of systems like FAWN and some object store designs).
  • Latency profile: write latency is O(chain length) sequential hops, which is worse than quorum-based systems for short chains but scales more predictably than the fan-out/fan-in pattern of majority-vote systems as replica count grows.
  • Reconfiguration dependency: the protocol assumes an external, highly available configuration manager for chain topology changes; it does not solve leader election internally, unlike Raft, which bundles consensus and leadership into one mechanism.

The architectural implication is that Chain Replication is best suited for workloads with a clear separation between a low-churn control plane (topology management) and a high-throughput data plane (linear write propagation), and where read scalability can either be sacrificed (vanilla chain) or engineered around via staleness checks (CRAQ). It is a poor fit for systems requiring dynamic, frequent membership changes or geo-distributed chains, since the sequential hop latency compounds badly across wide-area links.