Part 5 of 8 · 2 min read
Leaderless replication
Letting any replica take a write, and repairing the replicas that missed it.
Think of a vote taken by a committee of three members. A motion is carried if two agree. One member being away does not stop the committee. When the absent member returns, the others tell them what was decided.
Leaderless (Dynamo-style) replication
In leaderless replication, there is no leader. A client (or a coordinator node acting for it) sends each write to several replicas, and reads from several replicas. Any replica accepts writes. The coordinator does not enforce an order of writes.
Example: Cassandra, Riak and Voldemort. They were inspired by Amazon's Dynamo system.
The book notes this idea is old, was forgotten while relational databases dominated, and came back after Amazon built Dynamo. It also points out that DynamoDB, a hosted AWS product, has a different design based on a single leader.
A write while a node is down. There are three replicas, and one is being rebooted. In leader-based replication, a failover might be needed. In leaderless replication, there is no failover. The client sends the write to all three in parallel. Two accept it, one misses it. If it is enough for two to acknowledge, the write succeeds, and the client ignores the missed replica.
When the node returns, it lacks the writes it missed. A read from it returns old data. So reads also go to several nodes in parallel. The client may get different answers, and version numbers say which is newer.
Two mechanisms bring the lagging node up to date:
- Read repair. When a client reads from several nodes and sees one with an old value, it writes the newer value back to that node. In the book's figure, user 2345 gets version 7 from replicas 1 and 2 and version 6 from replica 3, and writes version 7 to replica 3. This works well for values that are read often.
- Anti-entropy process. A background process looks for differences between replicas and copies missing data. Unlike a replication log, it does not copy writes in any order, and there may be a long delay. Not all systems have both. Without anti-entropy, a value that is rarely read may be missing from some replicas, so its durability is reduced.
A worked example. Three replicas hold key X at version 6. Replica 3 is down. A write sets X to version 7 on replicas 1 and 2. Replica 3 returns still holding version 6. A read asks all three: replies are 7, 7, 6. The client takes version 7 and writes it to replica 3. Replica 3 is now at version 7. If nobody reads X, replica 3 stays at version 6 until the anti-entropy process runs.
Check yourself:
- Why does leaderless replication have no failover?
- What does read repair do, and for which values does it work best?