Part 3 of 8 · 4 min read
Write conflicts
What happens when two leaders accept different values for the same record, and four ways to settle it.
Think of two editors who each change the title of the same article on their own copy. One writes "B" and the other "C". Both copies are valid on their own. When they swap changes, they must decide on one title, and the choice should be the same in both copies.
The book gives the example of a wiki page title. User 1 changes the title from A to B on leader 1. User 2 changes it from A to C on leader 2, at the same time. Each write succeeds locally. When they are copied, a conflict is detected. A single-leader database never has this problem.
Write conflict
A write conflict happens when two writes to the same data are accepted by different leaders at the same time, so that neither writer saw the other's change.
Example: two users set the same field to different values on two leaders in the same second.
In a single-leader database, the second writer waits or is aborted and retries. In multi-leader, both writes succeed, and the conflict is found later, when it may be too late to ask the user. One could make detection synchronous by waiting for all replicas, but then the main benefit is lost, and one might as well use a single leader.
Four ways to deal with conflicts, from the book:
- Avoid them. If all writes for a record go through the same leader, no conflict can occur. A user's requests can be routed to their "home" data centre, so from that user's point of view the system is single-leader. This is the most recommended approach. It breaks when a data centre fails or a user moves, and then concurrent writes become possible.
- Converge to the same value. Every replica must end with the same value. Methods: - Give each write a unique id (a timestamp, a random number) and keep the highest. With a timestamp this is last write wins (LWW). It is popular and dangerously prone to data loss. - Give each replica an id, and let writes from the higher-numbered replica win. This also loses data. - Merge the values, for example join them alphabetically ("B/C"). - Record the conflict in a data structure that keeps all the information, and settle it later in application code, perhaps by asking the user.
- Custom resolution code. The application supplies a handler. On write: the database calls it when a conflict is found in the replication log. It cannot ask the user, runs in the background and must be quick. On read: all conflicting versions are stored, and the next read returns them to the application, which may ask the user and write back the result. CouchDB works this way.
- Automatic resolution. Research into data types that merge by themselves: conflict-free replicated data types (CRDTs), mergeable data structures that track history like Git, and operational transformation, which is behind Google Docs and Etherpad.
CRDT (conflict-free replicated data type)
A CRDT is a data structure, such as a counter, set or list, that several replicas can change independently and that merges the changes automatically in a sensible way.
Example: a "like" counter held as a separate count per replica. The total is the sum. Two replicas can add likes at once without a conflict.
Resolution usually applies to one row or document, not a whole transaction.
A cautionary example from the book: for a time, the conflict handler for Amazon's shopping cart kept items that were added but not items that were removed. Customers saw items they had deleted come back.
A worked example of last write wins. Replica A has a clock 2 seconds fast.
- At true time 10:00:00 user 1 sets the price to 20 on replica B (clock correct, timestamp 10:00:00).
- At true time 10:00:01 user 2 sets the price to 25 on replica A (clock 2 seconds fast, timestamp 10:00:03).
- Both are copied. LWW keeps the highest timestamp: 25. Right, in this case.
- Reverse the order: user 2 on A writes at true time 10:00:00 (timestamp 10:00:02) and user 1 on B writes later at 10:00:01 (timestamp 10:00:01). LWW keeps 10:00:02, the older write. The later write is lost, with no error.
Not all conflicts are obvious. In a meeting-room booking system, two bookings for the same room and time on two leaders do not touch the same record but still conflict. The book notes that there is no quick answer to this.
Check yourself:
- Why is conflict avoidance the most recommended approach?
- In the LWW example, why can a clock that is 2 seconds fast lose a write?