Multi-leader replication and conflicts
Several machines that all accept writes: why anyone wants that, and what happens when two of them change the same thing.
5 minute lesson
A leader in every region
With one leader in Frankfurt, a user in Sydney waits for the planet on every write, and a failure in Frankfurt stops all writes. Multi-leader replication puts a leader in each region. Every leader accepts writes at once and passes them to the others afterwards.
- Frankfurtaccepts writes
- Sydneyaccepts writes
- Writes are fast everywhere, because the leader is nearby.
- A region can fail, and the others keep writing.
Two writes that both succeeded
- Same moment
A page title is "Draft". Ana, in Frankfurt, changes it to "Plan A". Ben, in Sydney, changes it to "Plan B". Each leader accepts and confirms its write.
- FrankfurtPlan A
- SydneyPlan B
- Exchange
The leaders send each other their change. Each now receives a write that contradicts one it has already confirmed. Neither user got an error.
- Frankfurtgets Plan B
- Sydneygets Plan A
- Decide
Both leaders must end with the same title. Some rule has to pick one, or combine the two. Whatever it does, it does it after both users were told their change was saved.
- Both leadersone title
Two users change the same record at the same moment, each through the leader of their own region. Both are told that the change was saved.
Why did neither of them get an error?
- Each leader confirmed before it heard of the other write
- The two leaders agreed on an order before confirming
- The second leader waited for a lock held by the first
- The two changes were merged before they were confirmed
Show the answer
- Each leader confirmed before it heard of the other write
A leader in a multi-leader set-up does not ask the others before it accepts a write. That is what makes it fast and independent. When each confirmed, it knew of one change only. The conflict exists only from the moment the two leaders exchange their changes, and by then both users have moved on.
Leaders confirm on their own and replicate afterwards, so conflicts are found too late for an error.
Three ways to settle a conflict
- Last write winsThe later timestamp stayssimple, and the other change is lost silently
- MergeA rule combines bothworks for some data, such as adding to a set
- Keep bothShow the versions to a personnothing is lost, and someone has to decide
Two leaders hold conflicting changes to one record. The system resolves conflicts by last write wins.
What happens to the change with the earlier timestamp?
- It is discarded, and its author is not told
- It is kept as a second version of the record
- It is merged into the change that came later
- It is sent back to its author for another try
Show the answer
- It is discarded, and its author is not told
Last write wins compares timestamps and keeps one change. The other is overwritten on every replica, as if it had never been made. Its author was told "saved" and never learns otherwise. The rule is popular because it is simple and always produces one answer. It is also a quiet way to lose data.
Last write wins always converges, by silently dropping one of the writes.
Why can a write conflict arise with several leaders, and what can be done about it?
Show the answer
Each leader confirms writes on its own and tells the others afterwards. Two leaders can therefore accept different changes to the same record, and only notice when they exchange them. A rule must then decide: keep the later write and drop the other, merge the two, or keep both for a person to resolve. Better still, route all writes for a record to one leader, so that they cannot conflict.
Recap
- Several leaders give fast local writes and survive the loss of a region.
- Two leaders can accept conflicting writes and discover it only afterwards.
- Settle conflicts by a rule, or avoid them by sending each record's writes to one leader.