Vector clocks and repair

When replicas accept writes independently, they drift apart. Two things must be solved: how to tell whether two versions are related or conflicting, and how to make replicas converge again. Vector clocks answer the first. Hinted handoff, read repair and Merkle tree anti-entropy answer the second.

A wall-clock timestamp seems the natural way to order updates, but clocks on different machines disagree by milliseconds or more, so "later" by timestamp may not be later in reality. Worse, a timestamp cannot tell you that two updates were concurrent, meaning neither knew about the other. Picking the later one silently discards a real update. What we need is causality: did one update happen knowing about the other?

A vector clock is a list of counters, one per node that has updated the item. Each version of a value carries one.

• When node X updates an item, it increases its own counter: [X:1], then [X:2].
• A new version made from an existing one copies its clock and increments the updating node's counter.

To compare two clocks A and B:

• If every counter in A is less than or equal to the matching counter in B, then A is an ancestor of B, and B simply supersedes it.
• If neither is an ancestor of the other, the versions are concurrent: a conflict.

Example. Version D2 has [X:2]. During a partition, node Y updates it to D3 with [X:2, Y:1], and node Z updates it to D4 with [X:2, Z:1]. D3 has a Y counter that D4 lacks, and D4 has a Z counter that D3 lacks, so neither dominates, and both are kept. A later reader merges them, and the result carries [X:2, Y:1, Z:1] with the merging node's counter increased, which descends from both.

Limits: clocks grow with the number of writers, so systems prune old entries, and the application must decide how to merge conflicts. Lamport timestamps are a simpler single number that respects causality but cannot detect concurrency, so they suit ordering when conflict detection is not required.

When a replica is down during a write, a neighbor accepts the write for it and keeps it with a hint naming the intended owner. When the owner returns, the neighbor delivers the data and deletes its copy. It keeps writes available through short outages, and repairs the most common gap right away. It does not help if the hint holder fails or the outage outlasts the hint's retention.

When a read contacts several replicas and finds that some have older versions, the coordinator returns the newest to the client and also writes it back to the stale replicas. Frequently read data heals itself with no extra process. Data that is rarely read stays stale, which is why another mechanism is needed.

To find and fix every difference, including in data nobody reads, replicas periodically run anti-entropy repair. Comparing every key between two replicas would move enormous amounts of data. A Merkle tree avoids that.

A Merkle tree is a tree of hashes. Each leaf holds the hash of one key's data, or a small range of keys. Each parent holds the hash of its children's hashes. The root summarizes the entire dataset: if two replicas have the same root hash, they hold identical data.

Comparing two replicas:

1. Exchange only the root hash. If equal, stop. Nothing is different.
2. If different, exchange the two children's hashes and compare them.
3. Descend only into the branches that differ, until reaching the exact leaves that disagree.
4. Exchange and reconcile only those keys.

For 1 million keys the tree has about 20 levels, since 2 to the 20 is just over a million. Finding a single difference takes about 20 small comparisons instead of a million. The cost is proportional to the number of differences, not to the size of the data.

• Hinted handoff repairs short outages at write time.
• Read repair repairs frequently read data at read time.
• Anti-entropy with Merkle trees repairs everything else, in the background, on a schedule, including long outages.
• Vector clocks decide which version wins or whether a conflict needs merging.

Used together, they let a system accept writes during failure and still converge, which is the foundation of Dynamo and Cassandra.

Repair uses disk and network, so run it off peak and in small ranges. Merkle trees must be rebuilt as data changes. Conflicts need application logic. All of these are the price of staying available during failures, instead of refusing writes.