Vector clocks

A Lamport clock gives every event a number, but two numbers can't tell you whether events were concurrent. A vector clock solves that. Each process keeps a vector with one counter per process. Comparing two vectors reveals exactly what happened before what, and what was concurrent.

The big idea

Each process remembers what it has seen from every process. Think of a group of friends. Each keeps a note with the latest message they've heard from each other friend. Comparing two notes shows whether one friend's view contains the other's, or whether they know different things.

The vector grows with the number of processes, which is the cost. Systems keep it small by using replica IDs and by pruning old entries.

Walking through it

The rules are three lines.

1. Before each local event or send, V[i] = V[i] + 1, where i is your own position.
2. Attach V to every message.
3. On receive with vector W, take the entry-wise maximum, then add one to your own entry.

Using the same trace as the Lamport clocks page, the vectors on the three processes look like this:

P1 a        V = [1, 0, 0]
P1 send m1  V = [2, 0, 0]
P2 c        V = [0, 1, 0]
P2 recv m1  V = [2, 2, 0]
P2 send m2  V = [2, 3, 0]
P3 e        V = [0, 0, 1]
P3 recv m2  V = [2, 3, 2]
P3 send m3  V = [2, 3, 3]
P1 recv m3  V = [3, 3, 3]

Now compare two of them. b is the send of m1, with V = [2, 0, 0]. e is P3's first event, with V = [0, 0, 1].

def before(v, w):  # v happened before w: every entry ≤, and not equal
    return all(a <= b for a, b in zip(v, w)) and v != w

b = [2, 0, 0]  # P1 sends m1
e = [0, 0, 1]  # P3's first event
print("b before e:", before(b, e))
print("e before b:", before(e, b))
print("concurrent:", not before(b, e) and not before(e, b))

Output:

b before e: False
e before b: False
concurrent: True

Lamport's numbers put e before b, which was misleading. The vectors show the two are concurrent, because neither contains the other.

Version vectors in a shopping cart

Leaderless databases such as Dynamo use a close cousin, the version vector, to detect conflicting writes to one key. Each replica that coordinates a write bumps its own entry. Here is the cart example from Dynamo's paper:

1. The cart is written through replica Sx: version {Sx:1}.
2. It's updated through Sx again: {Sx:2}, which replaces {Sx:1}.
3. Two clients both read {Sx:2}. One updates through Sy, giving {Sx:2, Sy:1}. The other updates through Sz, giving {Sx:2, Sz:1}.
4. Neither new version is less than or equal to the other, so they're concurrent. Dynamo keeps both as siblings and returns both on the next read.
5. The client merges them, such as by taking the union of cart items, and writes back {Sx:3, Sy:1, Sz:1}, which dominates both.

Last-write-wins would have silently kept one cart and dropped the other's items.

Common mistakes

• Comparing by eye. Every entry must be at most the other vector's entry. One larger entry in the wrong place makes the two concurrent.
• Reading concurrent as simultaneous. Concurrent means neither event knew of the other. They may be far apart in real time.
• Letting vectors grow forever. Each replica that writes adds an entry. Prune old entries, and use replica IDs rather than client IDs.

Check yourself

1. Are [2, 0, 0] and [0, 0, 1] before, after or concurrent? Concurrent, because neither vector is less than or equal to the other.
2. Why does Dynamo keep both shopping cart versions? They're concurrent, so neither can be discarded. The client merges them, such as by taking the union of items.

Key takeaways

• A vector clock keeps one counter per process and detects concurrent events exactly.
• Compare vectors entry by entry. Equal in every entry means the same event.
• Dynamo-style stores keep concurrent versions as siblings for the client to merge.
• Vectors grow with replicas, so prune them and use stable replica IDs.

Further learning

Kleppmann's lecture on logical time builds Lamport and vector clocks step by step on space-time diagrams.

Next, read about hybrid logical clocks and TrueTime, which bring real time back into the picture.