Part 5 of 8 · 2 min read
Conflicts
When two copies disagree.
Eventual consistency means two clients can change the same key through different nodes at the same time. Say a name was "john". One server writes "johnSanFrancisco" and another writes "johnNewYork". Now there are two versions, and neither is the parent of the other. A clock time cannot decide, since clocks are not reliable (Level 5, page 4). The system needs a way to tell "one version came after the other" from "they were made apart".
A vector clock does this. It is a list of pairs [server, counter] attached to a value. When a server writes a value, it adds 1 to its own counter in the list, or adds a new pair [server, 1] if it has none.
The book's example:
- A client writes D1 through server Sx. Clock: [(Sx,1)].
- A client reads D1, changes it, and writes D2 through Sx. Clock: [(Sx,2)]. D2 follows D1, so it replaces it.
- A client reads D2 and writes D3 through Sy. Clock: [(Sx,2),(Sy,1)].
- Another client reads D2 and writes D4 through Sz. Clock: [(Sx,2),(Sz,1)].
- A client reading both D3 and D4 sees a conflict. It merges them and writes D5 through Sx. Clock: [(Sx,3),(Sy,1),(Sz,1)].
Rule to compare two clocks.
- If every counter in clock Y is at least as big as the same counter in clock X, then X is an ancestor of Y. There is no conflict, and Y wins.
- If each clock has some counter bigger than the other's, the versions are in conflict.
Check with the example: [(Sx,2),(Sy,1)] against [(Sx,2),(Sz,1)]. The first has Sy = 1 that the second lacks (counts as 0), and the second has Sz = 1 that the first lacks. Each is ahead in one place, so they conflict. Compare [(s0,1),(s1,1)] with [(s0,1),(s1,2)]: every counter in the second is at least as big, so the first is an ancestor, and no conflict.
Two downsides, from the book. The client must contain code to resolve conflicts. And the clock can grow long as more servers write. A common fix is to cap its length and drop the oldest pairs, at the cost of sometimes being unable to tell ancestors from siblings. The Dynamo paper reported this was not a problem in production.
Vector clock
A vector clock is a list of [server, counter] pairs kept with a value, used to tell whether one version came after another or whether two versions conflict.
Example: [(A,2),(B,1)] came after [(A,1),(B,1)], but conflicts with [(A,1),(B,2)].
Check yourself: 1. Why can wall-clock time not settle a conflict? 2. Do [(A,1),(B,2)] and [(A,2),(B,1)] conflict? 3. What is a downside of vector clocks?