30-Second Glance
- No leader: clients write to multiple nodes at once and read from multiple nodes, reconciling versions on read.
- A write (or read) counts only when a quorum of nodes acks — the note's quorum-based consensus for success.
- Used in Cassandra and Riak; explicitly not DynamoDB per this note.
- Anti-entropy gossip propagates missed writes in the background; Merkle trees find the diff in O(log N) instead of scanning full logs in O(N).
- Trade-off: no single point of failure and high availability, at the cost of version reconciliation and weaker consistency.
Introduction
In leaderless replication, there is no single leader node that coordinates write operations. Instead, write operations can be sent to any node, and these nodes coordinate to ensure data consistency.
Used in: Cassandra, Raik and NOT used in Dynamo DB(remember!)
How Leaderless Replication Works:
- Write Operations:
- A client sends a write request to multiple nodes simultaneously.
- Each node independently writes the data and acknowledges the write.
- Read Operations:
- A client sends a read request to multiple nodes and may receive different versions of the data.
- The client or a coordinating service reconciles these versions to provide a consistent view.
- Quorum-Based Consensus:
- To ensure consistency, a write is considered successful only if a quorum of nodes (typically a majority) acknowledges the write.
- Similarly, a read is considered successful if a quorum of nodes returns the same version of the data.
Anti-Entropy
Propagates changes to the background !
How can we quickly tell which writes to send?? Solution: Merkle Trees!
Merkle Trees
How to build a merkle tree?? On the left we've the key-value pairs in a DB.
Comparing Merkle Trees: Logarithmic Time Complexity instead of linear time complexity if we would've scanned the replication logs of both the DBs.
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| Write to any node + quorum ack | No leader bottleneck or failover; survives node loss | Needs quorum coordination; concurrent versions to reconcile | High-availability stores like Cassandra/Riak |
| Read from multiple nodes + reconcile | Client sees disagreements and repairs them | Slower reads; app or coordinator must merge versions | Leaderless reads where freshness matters |
| Anti-entropy background sync | Heals missed writes without blocking the hot path | Extra background traffic; convergence isn't instant | Any leaderless deployment |
| Merkle-tree diffing | Finds divergent keys in O(log N) vs O(N) log scan | Tree build/maintain cost | Large datasets with small divergence |
Interview One-Liners
Q: How do writes and reads work with no leader? A: The client sends writes to multiple nodes in parallel and reads from multiple nodes, reconciling differing versions.
Q: When is a leaderless write considered successful? A: When a quorum (typically a majority) of nodes acknowledges it — same rule for reads.
Q: Which systems does the note cite, and with what caveat? A: Used in Cassandra and Riak — and, per this note, not in DynamoDB.
Q: What is anti-entropy? A: Background propagation that heals replicas that missed writes without blocking foreground traffic.
Q: Why Merkle trees for anti-entropy? A: Comparing trees pinpoints differing keys in O(log N) instead of scanning whole replication logs in O(N).
Q: What is the core trade-off of leaderless replication? A: No single point of failure and great availability, but reads/writes need quorum coordination and conflict reconciliation.