Vector clocks: an interactive conflict detection simulator

A vector clock is a list of counters, one per node, attached to each version of a piece of data. Comparing two vector clocks tells you whether one version descends from the other, so it can safely replace it, or whether the two were written concurrently, neither seeing the other, so both must be kept. Wall-clock timestamps cannot tell those apart, which is why systems that use them, last write wins, quietly lose writes.

The playground keeps a shopping cart on three replicas that each accept writes. Add items at different replicas, sync them in any order, and compare what vector clocks keep with what last write wins keeps.

How vector clocks work

1. Start at zero: every node’s entry is 0, written [A:0 B:0 C:0].
2. Write: take the clocks of the versions you read, combine them by taking the larger value of each entry, then add one to your own node’s entry.
3. Compare: if every entry of one clock is less than or equal to the other’s, the second descends from the first and replaces it. If each is ahead in some entry, they are concurrent.
4. Keep siblings: concurrent versions are stored side by side until someone reads them all, merges them and writes the result, whose clock descends from all of them.

In the second preset, A writes [A:1 B:0] and B writes [A:0 B:1]. A is ahead in its entry and B in its own, so neither descends from the other: two siblings. In the last preset, B reads both, merges them and writes [A:1 B:2], which is at least as large as both in every entry, so it replaces them.

Why not just use timestamps?

Last write wins keeps whichever version has the later timestamp and discards the rest. Two problems follow. Concurrent writes are not merged, one simply disappears: in the second preset the cart ends up with eggs but no milk. And the timestamps come from each node’s own clock, which drifts: in the slow clock preset, B’s write happens after A’s but is stamped earlier, so the newer write is the one thrown away.

Last write wins is still a reasonable choice when losing a concurrent write does not matter: a user’s latest location, a cache entry, a value that is always overwritten whole. Cassandra uses it for every column. For a shopping cart, a document or a counter, it loses data.

Siblings and merging

Detecting concurrency is half the job; something has to merge the siblings. Usually that is the application, on the next read: the Dynamo paper’s shopping cart took the union of the carts, so an added item was never lost, though an item removed in one sibling could reappear from another. Merges that are always safe are what CRDTs provide: data types such as sets, counters and maps designed so that concurrent versions combine automatically and every replica ends up the same.

Vector clocks, version vectors and Lamport clocks

• Lamport clock: a single counter. It orders events consistently with cause and effect, but two concurrent events still get different numbers, so it cannot tell you they were concurrent.
• Vector clock: one counter per process, so it can detect concurrency. Its size grows with the number of processes that write.
• Version vector: one counter per replica rather than per client, which keeps it small. This is what Dynamo-style stores track, and what the playground shows. Riak later moved to dotted version vectors, which avoid false siblings when many clients write through the same replica.

Clocks can still grow as nodes come and go; the Dynamo paper describes truncating the oldest entries once a clock passes a size limit, at the small risk of treating a descendant as concurrent.

Vector clocks in code

def compare(a: dict, b: dict) -> str:
    keys = a.keys() | b.keys()
    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"        # b descends from a: b may replace it
    if b_le_a: return "after"
    return "concurrent"               # keep both as siblings

def write(node: str, versions_read: list[dict]) -> dict:
    clock = {}
    for v in versions_read:           # the new version has seen everything it read
        for k, n in v.items():
            clock[k] = max(clock.get(k, 0), n)
    clock[node] = clock.get(node, 0) + 1
    return clock

write("A", [])                        # {'A': 1}
write("B", [])                        # {'B': 1}: concurrent with A's
write("B", [{"A": 1}, {"B": 1}])      # {'A': 1, 'B': 2}: replaces both

In a system design interview

Vector clocks come up when a design accepts writes in more than one place: a leaderless key-value store, an active-active multi-region database, offline-first sync. Say what you detect and how you resolve it: “Each value carries a version vector. When a write does not descend from the stored version, we keep both as siblings and return them on the next read; for the cart, the client merges by union.” Then expect the follow-ups: why not last write wins, how deletes are merged, and how big the vectors get.

Read the guide to CRDTs and operational transformation, try quorum reads and writes to see where concurrent versions come from, or watch a strong candidate design a distributed key-value store.

Questions people ask