Leaderless Replication: Quorums, Sloppy Quorums, and Hinted Handoff

In both single-leader and multi-leader replication, a designated leader node acts as the authority determining write order. But what if we eliminate the concept of a leader entirely?

In Leaderless Replication (pioneered by Amazon Dynamo and popularized by Apache Cassandra and Riak), any replica node can directly accept write and read requests from clients.

---

1. The Strict Quorum Invariant ($R+W>N$)

In a leaderless system with $N$ total replicas, how can we guarantee that a read query will always observe the latest written value without centralized coordination?

We define two configurable quorum parameters:

• $W$ (Write Quorum): The minimum number of replica acknowledgments required for a write to be considered successful.
• $R$ (Read Quorum): The minimum number of replica responses required before returning a value to the client.

The Pigeonhole Principle Invariant:

If the sum of the read quorum and write quorum is strictly greater than the total number of replicas:

$R+W>N$

Then by the Pigeonhole Principle, the set of nodes written to and the set of nodes read from MUST overlap by at least one node:

Because Node 2 belongs to both the Write Quorum and the Read Quorum, the client reading from Node 2 and Node 3 will receive two versions: $(v_2,t_{100})$ and $(v_1,t_{50})$. The client selects the version with the newer timestamp ($v_2$).

Common Quorum Configurations ($N=3$ or $N=5$):

• Balanced Strong Consistency: $N=3,W=2,R=2⟹2+2=4>3$. (Tolerates 1 failed node for both reads and writes).
• Fast Writes, Slow Reads: $N=3,W=1,R=3⟹1+3=4>3$. (Write completes in $1\text{ms}$ on 1 node; reads require querying all 3 nodes).
• High Read Throughput: $N=3,W=3,R=1⟹3+1=4>3$. (Read completes in $1\text{ms}$ on 1 node; writes require 100% node availability).

---

2. Dealing with Stale Data: Read Repair vs Anti-Entropy

Because leaderless writes are sent to all replicas concurrently and some nodes may temporarily fail or lag, replicas inevitably drift out of sync. Leaderless systems restore consistency using two mechanisms:

A. Read Repair (Opportunistic Synchronization)

When a client executes a read with $R=2$, it compares versions from all responding nodes. If Node 2 returns $v_2$ and Node 3 returns stale $v_1$, the client or coordinator immediately fires an asynchronous background write to repair Node 3:

B. Background Anti-Entropy with Merkle Trees (Hash Trees)

If a cold key is never read by any client, Read Repair will never trigger. To prevent cold data from permanently drifting, leaderless databases run background Anti-Entropy processes using Merkle Trees.

A Merkle Tree is a binary tree of cryptographic hashes where:

• Leaf nodes are hashes of individual key-value pairs.
• Parent nodes are hashes of their combined children.

Why Merkle Trees are Ultra-Efficient ($O(\log N)$):

1. Replicas exchange only their Root Hash (32 bytes).
2. If root hashes match, millions of keys are identical—zero data transfer needed!
3. If root hashes differ, they traverse down only the divergent tree branches, pinpointing the single differing key (Key 4) without scanning the entire dataset.

---

3. High Availability Under Partitions: Sloppy Quorums and Hinted Handoff

In a strict quorum ($N=3,W=2$), if a network partition isolates 2 of the 3 designated home replicas for key k, writes to k will fail because $W=2$ cannot be satisfied among home nodes.

To prioritize 100% Write Availability (AP in CAP theorem), Dynamo introduced Sloppy Quorums:

How Hinted Handoff Operates:

1. When home nodes $H_2$ and $H_3$ are down, the coordinator accepts the write on an unrelated healthy node $F_1$ outside the key's hash ring.
2. $F_1$ stores the record in a special Hinted Handoff buffer tagged with metadata: "This write belongs to Home Node 2".
3. When network connectivity heals and $H_2$ returns to health, $F_1$ delivers the buffered writes back to $H_2$ and deletes its local hint.

---

4. Code Deep-Dive: Dynamo-Style Quorum Coordinator with Read Repair

---

5. Production Failure Postmortem: Cassandra Hinted Handoff Disk Exhaustion Cascade

Incident Overview:

During a multi-hour network partition between AWS Availability Zones, a Cassandra cluster running with Sloppy Quorums suffered a total cluster outage after the partition healed.

What Happened:

1. AZ-East went unreachable for 4 hours.
2. Healthy nodes in AZ-West continued accepting writes, storing hundreds of gigabytes of Hinted Handoff mutation files on local SSDs.
3. When the network partition healed, all AZ-West nodes simultaneously began streaming gigabytes of hinted handoffs back to AZ-East.
4. The sudden torrent of replay traffic saturated inter-node network links and overwhelmed disk I/O.
5. Nodes missed their Gossip heartbeats, causing Sentinel monitors to mark healthy nodes as dead, triggering a catastrophic cluster-wide cascading crash loop.

Remediation:

• Set max_hint_window_in_ms = 3h (stop storing hints if a node is dead for $>3\text{ hours}$; rely on Merkle Tree anti-entropy instead).
• Applied hinted_handoff_throttle_in_kb = 1024 to rate-limit replay throughput and protect live traffic.

---

6. Chapter Summary & Replication Architecture Comparison