Leaderless Replication
Leaderless replication with quorums, hinted handoff, and read repair.
Type-3 Leaderless Replication (Dynamo-style)
No leader at all. Client sends write to ALL (or most) nodes directly. No one node is special. Any node can accept any write. Invented by Amazon for Dynamo (2007). Used by: Cassandra, Riak, Voldemort. Idea: sacrifice strong consistency for extreme availability and fault tolerance.
Leader dies → writes stop until election completes → downtime
leader-based replication
Node 1 dies → client writes to Node 2 and Node 3 → no downtime Node 1 comes back → catches up → business as usual
Client wants to write: username = "kartikeya" Client sends to Node 1 → Node 1 writes it → OK Client sends to Node 2 → Node 2 writes it → OK Client sends to Node 3 → Node 3 is down → no response
n = total number of replica nodes w = number of nodes that must confirm a WRITE r = number of nodes you must read from
The rule that makes it consistent: w + r > n
n = 3 nodes total w = 2 must write to 2 nodes r = 2 must read from 2 nodes w + r = 4 > 3 = n
No single point of failure for writes
n w r w+r Characteristic ------|-----|-----|------|---------------------------------------- 3 2 2 4 Standard. Tolerates 1 failure. 5 3 3 6 Tolerates 2 failures. 3 3 1 4 Fast reads, slow writes. Read anywhere. 3 1 3 4 Fast writes, slow reads. Write anywhere. 3 1 1 2 w+r ≤ n. Eventually consistent only.
How Write works
How Read works
Client reads username from Node 1, Node 2, Node 3 Node 1 returns: { username:"kartikeya", version: 5 } Node 2 returns: { username:"kartikeya", version: 5 } Node 3 returns: { username:"kart", version: 3 } ← stale, was down during write
Then client does Read Repair. it notices Node 3 is stale and writes the latest value back to it.
Client → Node 3: here is the latest value, update yourself Node 3 updates: { username:"kartikeya", version: 5 }
1. Read Repair
Read Repair Mechanism
2. Anti-Entropy (background process + Merkle Tree)
Anti-entropy is a background process that constantly compares nodes and syncs differences.
Every few minutes: Node 1 and Node 2 compare their data Node 1 has version 5 for some key Node 2 has version 3 for same key Node 2 pulls version 5 from Node 1 and updates itself
It uses a data structure called a Merkle Tree to efficiently find which parts of the data differ without comparing every single key.
Merkle Tree: Hash of all data → one root hash If root hashes match → data is identical, nothing to do If root hashes differ → drill down the tree to find exactly which keys differ
we used merkle tree in blockchain also - proof of work, consensus protocol