CRAQ (Chain Replication with Apportioned Queries)

Standard Chain Replication (CR) enforces strong consistency by routing all writes head-to-tail and all reads exclusively to the tail. This is simple and correct, but it means the tail node becomes a hard bottleneck: read throughput cannot scale by adding more chain nodes, and tail latency is coupled to the full propagation delay of the write. CRAQ addresses this by allowing every replica to answer read queries directly, apportioning read load across the entire chain rather than funneling it to a single node.

The mechanism hinges on a per-object versioned dirty/clean marker. When a write arrives at a node, that node doesn’t just overwrite the value—it appends a new version to a local list, marking the entry as dirty and forwarding the write down-chain. The entry only transitions to clean once an acknowledgment (ACK) propagates back up from the tail, confirming the write has been committed durably to the end of the chain. A read request handled by a non-tail node checks this marker: if the latest local version is clean, it answers immediately from local state—no coordination needed. If it’s dirty, the node cannot know if that’s the definitively committed value, so it issues a synchronous version-query to the tail to fetch the latest committed version number, then serves the corresponding value from its own version history.

This design creates an important trade-off surface: read latency is O(1) in the common case (clean reads) but degrades to a round-trip-to-tail under write contention (dirty reads), meaning CRAQ’s read performance is inversely sensitive to write throughput on hot keys. Operationally, this makes CRAQ excellent for read-heavy, write-light workloads—object stores, configuration services, session caches—where write bursts are rare. It’s a poor fit for write-heavy hot-key workloads, since every replica must retain a version history until cleared, and dirty-read fallback traffic converges back on the tail anyway, partially reintroducing the original bottleneck under sustained write pressure.

Failure handling inherits CR’s reconfiguration protocol (a chain master or external coordinator like Zookeeper detects failures and splices the chain), but CRAQ adds complexity: a failed node mid-chain can leave downstream replicas holding stale dirty markers with no clear path to resolve them until the chain is repaired and ACKs re-propagate. Systems built on CRAQ must also bound the version history length per object—unbounded dirty version lists under write storms become a memory-exhaustion vector, so implementations typically garbage-collect versions once they fall behind the tail’s committed point. In practice, CRAQ sits as a middle ground between full linearizable read-from-tail systems and eventually-consistent gossip-based replicas, offering tunable consistency-vs-throughput behavior purely through workload shape rather than explicit quorum configuration.