Lesson 22 · Logical time & version history

Two Vectors, Three Answers

A Lamport timestamp orders everything, which sounds generous until you notice it also orders things that never influenced each other. A vector clock refuses to do that — and the refusal is the whole point, because it is what lets a store say "these two writes are both real" instead of quietly throwing one away.

The win in this lesson: given two version vectors you will be able to say which of three relations holds — descends-from, precedes, or concurrent — and explain why detecting concurrency is the prerequisite for merging conflicting data rather than losing it.

1. The question Lamport clocks cannot answer

Lesson 21 left you with a total order: every event gets a number, and no two events share one. The trouble is what that number does not tell you.

"Given the Lamport timestamps of two events, it is in general not possible to tell whether those events are concurrent or whether one happened before the other."
Distributed Systems, Martin Kleppmann, University of Cambridge · §4.1, Logical time

The implication runs one way only. If a happened before b, then L(a) < L(b). But seeing L(a) < L(b) tells you nothing: a may have caused b, or the two may have happened on opposite sides of a partition with no knowledge of each other at all. The converse is missing, and the converse is exactly what a replicated store needs.

Why the missing converse costs data

A store that cannot distinguish "b supersedes a" from "a and b are both real" has one option left: pick the bigger number and discard the other. That is last-write-wins, and Lesson 05 already named it a data-loss policy wearing a neutral name. Detecting concurrency is not a nicety. It is the difference between merging and deleting.

2. One counter per node

The fix is almost embarrassingly direct: stop compressing the system's state into one integer.

"While Lamport timestamps are just a single integer (possibly with a node name attached), vector timestamps are a list of integers, one for each node in the system. […] Concretely, ti is the number of events known to have occurred at node Ni."
§4.1, Kleppmann

Three rules drive it, and they are worth memorising because every version-vector scheme you meet is a variation on them:

on initialisation at node Ni:
    T := ⟨0, 0, …, 0⟩          one slot per node

on any local event at node Ni:
    T[i] := T[i] + 1           only ever your own slot

on sending message m at node Ni:
    T[i] := T[i] + 1 ; send (T, m)

on receiving (T′, m) at node Ni:
    T[j] := max(T[j], T′[j])   for every j     merge what the sender knew
    T[i] := T[i] + 1           then count this receive

The merge on receive is the load-bearing line. Kleppmann states it plainly: the recipient "merges the vector timestamp in the message with its local timestamp by taking the element-wise maximum of the two vectors, and then the recipient increments its own entry" (§4.1). Element-wise maximum means knowledge only ever accumulates — a node never forgets that it once heard about an event.

Three slots, one per node, always written in the order ⟨A, B, C⟩. Read the shaded band twice. B's ⟨2,2,0⟩ knows about A's first two events; C's ⟨0,0,1⟩ knows about nothing but itself. Each vector wins in a slot the other loses, and that crossing pattern is the detection — no clock, no heuristic, no threshold. A Lamport timestamp would have ordered these two and told you nothing about whether the order meant anything.

3. Comparing two vectors

The comparison is defined element by element, and it yields a partial order — partial precisely because some pairs are left unordered, which is the feature.

Relation	Test on every slot `i`	What it means for your data
`T = T′`	`T[i] = T′[i]` for all `i`	The same event. Nothing to do.
`T < T′`	`T[i] ≤ T′[i]` for all `i`, and they differ somewhere	`T` happened before `T′`. The older version is an ancestor and can be discarded safely.
`T > T′`	the same test, the other way round	`T′` is the ancestor. Same conclusion, mirrored.
`T ∥ T′`	neither `T ≤ T′` nor `T′ ≤ T`	Concurrent. Both are real. Keep both and reconcile.

"two vectors are incomparable if one vector has a greater value in one element, and the other has a greater value in a different element. For example, T = 〈2, 2, 0〉 and T ′ = 〈0, 0, 1〉 are incomparable because T [1] > T ′[1] but T [3] < T ′[3]."
§4.1, Kleppmann

And the property that makes the whole construction worth the bytes:

"The partial order over vector timestamps corresponds exactly to the partial order defined by the happens-before relation. Thus, the vector clock algorithm provides us with a mechanism for computing the happens-before relation in practice."
§4.1, Kleppmann

Exactly is a strong word and it is meant literally: V(a) < V(b) if and only if a → b, and V(a) ∥ V(b) if and only if a ∥ b. No false positives, no false negatives. This is the converse Lesson 21 could not give you.

4. What Dynamo does with a detected conflict

Dynamo attaches one of these vectors to every version of every object, and uses it to decide whether it is allowed to throw a version away.

"Dynamo uses vector clocks […] in order to capture causality between different versions of the same object. A vector clock is effectively a list of (node, counter) pairs. One vector clock is associated with every version of every object."
Dynamo: Amazon's Highly Available Key-value Store, DeCandia et al., SOSP '07 · §4.4

Note the list-of-pairs form: a sparse map, not a fixed-width array, so a node only appears once it has actually coordinated a write. The decision rule is then the table above, in one sentence:

"If the counters on the first object's clock are less-than-or-equal to all of the nodes in the second clock, then the first is an ancestor of the second and can be forgotten. Otherwise, the two changes are considered to be in conflict and require reconciliation."
§4.4, Dynamo

Syntactic and semantic reconciliation

Dynamo splits the work by who is capable of doing it:

"Most of the time, new versions subsume the previous version(s), and the system itself can determine the authoritative version (syntactic reconciliation). However, version branching may happen, in the presence of failures combined with concurrent updates, resulting in conflicting versions of an object. In these cases, the system cannot reconcile the multiple versions of the same object and the client must perform the reconciliation in order to collapse multiple branches of data evolution back into one (semantic reconciliation)."
§4.4, Dynamo

Syntactic reconciliation is free and needs no knowledge of what the data means — one vector dominates, the other goes in the bin. Semantic reconciliation requires knowing that a cart is a set of items and that two carts can be unioned. Only the application knows that. So Dynamo hands the branches back:

"if Dynamo has access to multiple branches that cannot be syntactically reconciled, it will return all the objects at the leaves, with the corresponding version information in the context."
§4.4, Dynamo

The arithmetic of the merge follows Figure 3 of the paper: the read context is the merge of the siblings' clocks, and the coordinating node bumps its own counter when the reconciled version is written back. Because D5's clock dominates both D3 and D4, every replica that later sees it can drop the siblings without asking anybody.

Compare this against the Lesson 05 default. Last-write-wins would have compared two timestamps, kept the lamp or the mug, and returned a cart that was silently wrong. The vector clock does not make the merge happen — it makes the merge possible, by proving that a merge is required.

"Using this reconciliation mechanism, an 'add to cart' operation is never lost. However, deleted items can resurface."
§4.4, Dynamo

5. Residual risk: the vector grows

Every mechanism in this course bills you for something. Here the bill is size.

"A downside of vector clocks is that they can become expensive: every client needs an entry in the vector, and in systems with large number of clients (or where clients assume a new identity every time they are restarted), these vectors can become large, potentially taking up more space than the data itself."
§5.1, Kleppmann

Dynamo hits the same wall whenever writes stray outside the usual coordinators — which is exactly what a partition or a node failure causes — and its answer is blunt:

"Along with each (node, counter) pair, Dynamo stores a timestamp that indicates the last time the node updated the data item. When the number of (node, counter) pairs in the vector clock reaches a threshold (say 10), the oldest pair is removed from the clock."
§4.4, Dynamo

Truncation trades correctness for bytes, and the paper says so

Dropping the oldest pair breaks the one guarantee the vector existed to provide: "this truncation scheme can lead to inefficiencies in reconciliation as the descendant relationships cannot be derived accurately" (§4.4). A truncated clock can make a genuine descendant look concurrent — producing a sibling that did not need to exist — or, worse, hide a real branch.

The paper's defence is empirical, not formal: "this problem has not surfaced in production and therefore this issue has not been thoroughly investigated" (§4.4). Read that as what it is — a known unsound corner, accepted because the measured cost was zero.

The measurement that justifies the bet is in §6.3. Over 24 hours of shopping-cart traffic, "99.94% of requests saw exactly one version; 0.00057% of requests saw 2 versions; 0.00047% of requests saw 3 versions and 0.00009% of requests saw 4 versions." Branching is rare, and the paper adds that the increase "is contributed not by failures but due to the increase in number of concurrent writers."

So the honest summary of a version vector: it is a per-object set of writer identities, and it costs whatever that set costs. Keep the writer set small — one coordinator per key in the common case — and the vector stays tiny. Let every client mint a fresh identity and the metadata outgrows the data.

6. Check yourself

7. Back to your world

You will rarely implement a vector clock. You will constantly meet its absence. The tell is a field named updated_at doing load-bearing work.

Does your "latest wins" comparison have a converse? If two rows can be written on different machines and you resolve by timestamp, you have last-write-wins and you are losing writes at a rate nobody is measuring.
Can your schema even represent two answers? A column holds one value. If concurrency is possible, the type has to be a set, a list of siblings, or a CRDT — otherwise detection is pointless because there is nowhere to put the second version.
Who merges, and do they have enough information? A union is only correct if removal is not a real operation. If it is, you need tombstones, not just a vector.
How many distinct writers touch one object? That number is your vector width. If it is unbounded — per-device, per-session, per-retry identities — plan the truncation before it plans itself.

Ask me things. Good directions: "work an example — give me two vectors and make me classify them" · "what is a dotted version vector and what does it fix?" · "how do CRDTs avoid needing the application to merge?" · "why can't I just use a hybrid logical clock?" · "I still think last-write-wins is fine for my case. Grill me."