Chain replication

Deep dive

How it works

Parts:

• head — assigns sequence numbers, accepts writes
• middle nodes — apply and forward each write once
• tail — commits, answers reads and clients
• master — small consensus group holding the chain configuration and epoch
• sent list per node — forwarded but not yet acked writes, resent after a splice

1. Head assigns a sequence number to the write, applies it as pending, forwards to its successor, and remembers it in sent.
2. Each middle node applies and forwards, also keeping it in sent.
3. The tail applies, marks committed, replies to the client, and sends an ack up the chain; each node drops acked entries from sent.
4. Head fails: master makes the successor the head (pending writes the old head never forwarded are lost; client retries).
5. Tail fails: predecessor becomes tail; its pending entries become committed.
6. Middle node fails: master links predecessor P to successor S; S reports its last seq; P resends sent entries after it.
7. Add a node: copy state to a new tail, then switch.

client write ─► [head] ─► [mid] ─► [tail] ─► reply to client
                   ▲        ▲         │
                   └── ack ─┴── ack ──┘
reads (CR): tail only        reads (CRAQ): any node; dirty key → ask tail for committed seq

Code

Node logic for CRAQ (CR is the special case where only the tail answers reads).

use std::collections::{BTreeMap, HashMap};

#[derive(Clone, Debug)]
pub struct Update { pub seq: u64, pub key: String, pub value: Vec<u8> }

pub enum Out { Forward(Update), CommitAndAck(u64), AckUp(u64), None }

#[derive(Default)]
pub struct Node {
    pub is_head: bool,
    pub is_tail: bool,
    next_seq: u64,                                  // head only
    pub last_seq: u64,                              // highest update received
    pub committed_seq: u64,                         // highest update known acked by tail
    versions: HashMap<String, BTreeMap<u64, Vec<u8>>>, // key -> seq -> value
    sent: BTreeMap<u64, Update>,                    // forwarded, not yet acked
}

impl Node {
    pub fn client_write(&mut self, key: String, value: Vec<u8>) -> Out {
        assert!(self.is_head);
        self.next_seq += 1;
        self.on_update(Update { seq: self.next_seq, key, value })
    }

    pub fn on_update(&mut self, u: Update) -> Out {
        if u.seq <= self.last_seq { return Out::None; } // duplicate after a resend
        self.last_seq = u.seq;
        self.versions.entry(u.key.clone()).or_default().insert(u.seq, u.value.clone());
        if self.is_tail {
            self.committed_seq = u.seq;
            self.gc(&u.key, u.seq);
            Out::CommitAndAck(u.seq)                    // reply to client, ack predecessor
        } else {
            self.sent.insert(u.seq, u.clone());
            Out::Forward(u)
        }
    }

    pub fn on_ack(&mut self, seq: u64) -> Out {
        self.committed_seq = self.committed_seq.max(seq);
        let still = self.sent.split_off(&(seq + 1));     // entries > seq stay pending
        let acked = std::mem::replace(&mut self.sent, still);
        for u in acked.values() { self.gc(&u.key, seq); }
        if self.is_head { Out::None } else { Out::AckUp(seq) }
    }

    /// Keep the newest committed version of `key` plus any newer dirty ones.
    fn gc(&mut self, key: &str, seq: u64) {
        if let Some(vs) = self.versions.get_mut(key) {
            if let Some((&c, _)) = vs.range(..=seq).next_back() {
                let keep = vs.split_off(&c);
                *vs = keep;
            }
        }
    }

    /// CRAQ read. Ok(value) if clean; Err(()) means "ask the tail for its committed seq of key".
    pub fn read(&self, key: &str) -> Result<Option<Vec<u8>>, ()> {
        let Some(vs) = self.versions.get(key) else { return Ok(None) };
        let (&newest, v) = vs.iter().next_back().unwrap();
        if self.is_tail || newest <= self.committed_seq { Ok(Some(v.clone())) } else { Err(()) }
    }

    /// Second half of a dirty read: the tail told us which seq is committed for this key.
    pub fn read_at(&self, key: &str, tail_seq: u64) -> Option<Vec<u8>> {
        self.versions.get(key)?.range(..=tail_seq).next_back().map(|(_, v)| v.clone())
    }

    /// Tail-side answer to a version query.
    pub fn committed_version(&self, key: &str) -> u64 {
        self.versions.get(key).and_then(|vs| vs.keys().next_back().copied()).unwrap_or(0)
    }

    /// Reconfiguration: our new successor has seen up to `succ_last`; resend the rest in order.
    pub fn on_new_successor(&self, succ_last: u64) -> Vec<Update> {
        self.sent.range(succ_last + 1..).map(|(_, u)| u.clone()).collect()
    }
}

Complexity and constants

• Write: n sequential hops + reply; in one datacenter order of 50-200 µs per hop including apply, so a 3-node chain ≈ 0.2-0.6 ms without fsync.
• Bandwidth: each node receives and sends each object once. A leader sends n−1 copies, so for large objects the leader's egress NIC caps write bandwidth at about 1/(n−1) of line rate; a chain reaches about line rate (2× at n = 3).
• Reads (CR): all on the tail, the bottleneck for read-heavy loads. CRAQ: clean reads local, dirty reads cost one small round trip to the tail.
• Fault tolerance: n = f+1 for f crash failures, given the master survives.

Efficiency

• Cost: per write, each node receives and sends the object once, so bandwidth is about line rate; latency is n sequential hops, order of 50-200 µs per hop in one datacenter (see above), so a 3-node chain is about 0.2-0.6 ms without fsync. Bound: network latency for small writes, NIC bandwidth for large ones; CR reads all hit the tail.
• Levers:
  • many chains per server set with rotated orders — spreads head and tail load evenly (Chain Replication paper, OSDI 2004) — sharded stores
  • CRAQ clean reads from any node — read throughput scales with chain length (Terrace and Freedman, ATC 2009) — read-mostly loads
  • tail replies to the client directly — removes the ack hops from the client's path — latency-sensitive writes
  • fsync in parallel with forwarding — only the tail's commit waits — durable chains
• Naive → standard → state of the art:
  • primary fans out n−1 copies · leader egress caps writes at about 1/(n−1) of line rate
  • chain replication (CR) · about line rate, reads at the tail only
  • CRAQ with sharded chains · reads from every replica, writes still n hops

Implementation notes

• The master is a small Raft/Paxos group (or ZooKeeper/etcd) holding the chain configuration with an epoch; every message carries the epoch and nodes reject stale epochs.
• Failure detection timeouts trade write stall time for false positives; a stalled chain blocks all writes for the shard.
• Shard data into many chains with different orderings of the same servers so head/tail load spreads evenly.
• Tail can reply directly to the client to save the ack hops on the client's critical path; acks still flow up for GC.
• Fsync placement: if every node fsyncs before forwarding, latency adds n fsyncs; many systems fsync at each node in parallel with forwarding and only the tail's commit waits.

Pitfalls

• Serving reads from a non-tail node in plain CR: returns uncommitted writes that may be lost.
• Resending sent out of order after splicing: successors must apply in seq order (drop duplicates, buffer gaps).
• Two nodes both believing they are the tail during reconfiguration: use epochs or leases from the master.
• Long chains for "more durability": every node added costs latency on every write.

Variants and alternatives

In production

Distributed file and object storage: DeepSeek 3FS (CRAQ for storage targets, used for AI training data), HDFS write pipelines (datanodes forward each block along a chain). Key-value stores: FAWN-KV, HyperDex (value-dependent chaining), Hibari. Shared logs: CORFU/CorfuDB replicates log pages along a chain.

Implementations

Sources

• Robbert van Renesse, Fred B. Schneider, Chain Replication for Supporting High Throughput and Availability, OSDI 2004. paper
• Jeff Terrace, Michael J. Freedman, Object Storage on CRAQ: High-Throughput Chain Replication for Read-Mostly Workloads, USENIX ATC 2009. paper
• David Andersen et al., FAWN: A Fast Array of Wimpy Nodes, SOSP 2009. paper
• DeepSeek, 3FS design notes. code