Chain Replication with Apportioned Queries (CRAQ) is a replication protocol that extends the original chain replication design to support strongly consistent reads from any replica in the chain, not just the tail. This makes it a compelling alternative to Raft-based consensus for workloads where read throughput far exceeds write throughput, which is the common case in key-value stores and object storage systems.
In standard chain replication, writes flow from head to tail and reads are served only by the tail, creating a bottleneck. CRAQ eliminates this by allowing any node in the chain to answer reads — either immediately when the node’s copy is clean (committed), or after a lightweight version check with the tail when the node holds a dirty (uncommitted) version. This apportioning of queries across all replicas can multiply read throughput by the replication factor.
For systems like an experimental distributed database where range partitions need high read availability without giving up linearizability, CRAQ offers an elegant middle ground between the simplicity of primary-backup and the generality of multi-paxos. Understanding CRAQ’s version propagation, clean/dirty states, and failure recovery is essential for building high-performance replicated storage.
CRAQ achieves linearizable reads from any replica by maintaining version metadata at each node. A clean version is guaranteed committed; a dirty version triggers a lightweight tail check that costs one extra round trip but avoids full consensus.
Read throughput scales linearly with chain length because queries are distributed across all replicas, unlike Raft where the leader handles all reads (or requires expensive read leases).
A client sends a write to the head of the chain. The head appends a new version object (key, value, version number) to its local store, marks it dirty, and forwards the write to the next node. Each subsequent node does the same until the write reaches the tail. The tail marks the version clean and sends an acknowledgment backward through the chain. Each node that receives the ack marks its copy clean and discards any older versions for that key.
A client can send a read to any node in the chain. If the node’s latest version for the requested key is clean, the node responds immediately with the value. This is the fast path and requires zero network hops beyond the client’s request.
If the node holds a dirty version, it cannot be sure the version is committed. It sends a lightweight version-query to the tail asking for the latest committed version number for that key. The tail responds with the committed version, and the node returns the corresponding value. This adds one round trip but guarantees linearizability.
Under low write contention, nearly all reads hit the clean fast path. The dirty fallback is only triggered during the brief propagation window of an in-flight write, so the average read latency stays close to a single local lookup.
If a middle node fails, its neighbors link together and replay any dirty versions. If the head fails, the next node becomes the new head. If the tail fails, the preceding node becomes the new tail and commits all pending dirty versions. A configuration manager (e.g., ZooKeeper or etcd) tracks chain membership and triggers reconfiguration.
func (n *CRAQNode) Read(key string) ([]byte, error) {
n.mu.RLock()
versions := n.store[key]
latest := versions[len(versions)-1]
n.mu.RUnlock()
if latest.Clean {
return latest.Value, nil
}
// Dirty: ask the tail for the committed version
committed, err := n.tail.QueryVersion(key)
if err != nil {
return nil, fmt.Errorf("tail version query: %w", err)
}
n.mu.RLock()
defer n.mu.RUnlock()
for _, v := range n.store[key] {
if v.Version == committed {
return v.Value, nil
}
}
return nil, ErrVersionNotFound
}func (n *CRAQNode) PropagateWrite(key string, value []byte, version uint64) error {
// Store as dirty locally
n.mu.Lock()
n.store[key] = append(n.store[key], VersionEntry{
Version: version,
Value: value,
Clean: false,
})
n.mu.Unlock()
if n.isTail {
// Tail: commit and send ack backward
n.markClean(key, version)
return n.predecessor.Ack(key, version)
}
// Forward to next node in chain
return n.successor.PropagateWrite(key, value, version)
}
func (n *CRAQNode) Ack(key string, version uint64) error {
n.markClean(key, version)
n.gcOldVersions(key, version)
if n.predecessor != nil {
return n.predecessor.Ack(key, version)
}
return nil // head reached, write fully committed
}