Version Vectors and Conflict Detection in Multi-Writer Replication

Multi-writer replication accepts two writes to the same key that were composed without knowledge of each other. Before anything can be merged, the system must determine whether the two writes are actually concurrent or whether one happened after the other. A wall-clock timestamp answers that question with a comparison that is cheap and wrong; a version vector answers it with a comparison that is more expensive and correct with respect to the causal history the system actually observed.

Why a timestamp is the wrong comparison

Give each write the reading of the writer’s local clock. When two versions meet, keep the one with the larger timestamp. This is last-write-wins, and it is a valid policy for some data. It is not a mechanism for detecting conflict, because it answers a different question.

Two writes with timestamps 10 and 12 may be ordered by causality, in which case the later one should win. They may also be concurrent, in which case neither should silently win. And they may be ordered the other way around in causality while the clocks disagree, in which case the comparison picks the wrong one. Clock skew between machines, and non-monotonic behaviour when a clock is adjusted, both produce orderings that contradict the causal history. The result is a write disappearing with no record that a decision was made.

Last-write-wins is defensible when the data is a register whose last writer is the only meaningful one, and when the application can tolerate losing the other write. It is not defensible as a general conflict detector, because it cannot represent “these two are concurrent”.

What a version vector represents

A version vector is a map from replica identifier to counter, a structure introduced for detecting inconsistency among replicated copies in the early 1980s. Each replica increments its own entry on every write it originates, and merges other replicas’ entries when it receives their writes by taking the element-wise maximum. A version is then a pair of (value, vector), and the vector summarises everything the writer had observed when it produced the value.

Comparison between two vectors A and B is defined by three cases:

• A ≤ B if A[i] ≤ B[i] for every i. Then the write carrying A happened before the write carrying B, because B’s writer had seen everything in A.
• A ≥ B symmetrically.
• Otherwise neither dominates, and the two writes are concurrent.

This is a partial order, not a total one. That is the point. The comparison can say “these are incomparable”, which a scalar timestamp cannot.

def compare(a, b):
    """Return 'before', 'after', 'equal', or 'concurrent'."""
    keys = set(a) | set(b)
    a_le_b = all(a.get(k, 0) <= b.get(k, 0) for k in keys)
    b_le_a = all(b.get(k, 0) <= a.get(k, 0) for k in keys)
    if a_le_b and b_le_a:
        return 'equal'
    if a_le_b:
        return 'before'
    if b_le_a:
        return 'after'
    return 'concurrent'

The complexity is O(number of replicas) per comparison, which for a fixed replica set is a constant. For a system that creates replicas dynamically, the vector grows with the number of writers that have ever touched the key, and comparison becomes proportional to that count.

The vector grows and must be pruned

The cost of correctness is metadata. A key touched by twenty replicas carries a vector with twenty entries. That is fine for a cluster of five and untenable for a key that has been written in every one of hundreds of edge locations over its lifetime.

Pruning is where implementations diverge. One approach is to restrict the vector to the replicas that currently own the key, discarding entries from replicas that no longer hold it. That is safe only if the discarded replicas will never write to the key again, which requires knowing the ownership history. Another approach is to keep a fixed-size vector and accept that old causal information is lost; the vector then no longer detects some conflicts and the system silently degrades toward last-write-wins for very old versions. A third is to summarise the vector into a hash for comparison and keep the full vector only where a conflict actually occurs, trading exactness in the common case for storage.

The tension is the same one that appears in Merkle tree anti-entropy: the metadata that makes divergence detectable is itself proportional to history, so the mechanisms that bound it are all forms of forgetting.

Dotted versions and the sibling problem

A plain version vector describes a set of writes, not a single write. When a replica receives a value whose vector dominates its own, it can overwrite. When the vectors are concurrent, both values must be kept as siblings, and the client is asked to merge them or the system merges them with a type-specific function.

Siblings accumulate. Two concurrent writes produce two versions; a third write based on only one of them produces another concurrency with the other. Without care the number of siblings per key grows with the number of concurrent writers. Dynamo’s answer was to return all siblings on a read and let the application collapse them, with the application supplying the merge. That places the merge function in the data model, which is honest but demanding: the application must be able to merge any pair of values it might receive.

A refinement called the dotted version vector tracks, alongside the vector, the specific write that produced the value. The dot is a single (replica, counter) pair identifying the origin of that version. With dots, a replica can tell whether an incoming value is one it has already seen, which prevents re-adding a sibling that was already merged. The vector plus dot gives both the summary of the causal past and the identity of the current write, and the identity is what makes deduplication possible.

Merging is a data-type decision

Conflict detection and conflict resolution are separate concerns, and the second cannot be solved generically. A version vector says “these are concurrent”; it does not say what the merged value should be.

For a counter, the merge is addition of per-replica increments, which is why conflict-free replicated data types represent counters as vectors of per-replica counts rather than a single integer. For a set, the merge depends on whether removals must be respected: a grow-only set merges by union, while a set that supports removal needs tombstones or observed-remove metadata, because a plain union resurrects deleted elements. For a register holding an opaque blob, there is no correct merge and the only options are to keep both or to pick one by policy.

The important consequence is that the storage layer cannot be responsible for merging arbitrary values. Systems that try to do so end up with a default policy — usually last-write-wins — which reintroduces the problem the version vector was meant to solve. The design that works is to let the storage layer detect concurrency exactly and to let the application declare a merge function per data type.

Reading with vectors

On the read path, a coordinator contacts R replicas and receives values with vectors. It compares them pairwise, discards any value whose vector is dominated by another’s, and returns the surviving set. If one value survives, the read is unambiguous. If several survive, they are concurrent and the client must merge.

The comparison also drives repair. Any replica whose version is dominated by the winner is behind and should be brought forward. This is the read-repair path, and its correctness depends on the vector comparison being exact — a repair that overwrites a concurrent sibling destroys data that the merge function was supposed to see.

There is a limit to what vectors can express. They capture causality among the writes the system has observed, and nothing else. Two writes that were causally ordered in the real world but never exchanged messages will appear concurrent, which is the correct answer given the information available. A version vector is a record of knowledge, not of time.

The other limit is that the vector is per key. A transaction spanning several keys needs a vector per key, or a mechanism that relates them, and the atomicity requirement is a separate problem from concurrency detection. What the vector does provide is the input to repair: a replica that holds a dominated version is behind, and the mechanism that brings it forward is described in read repair and hinted handoff.