Data Versioning with Vector Clocks

Why this matters: the previous lesson accepted writes on both sides of a partition. This lesson is the bill for that decision — and vector clocks are the single most transferable idea in the chapter.

How divergence happens

Both nodes were correct. Both accepted writes because the system requires it. Now they disagree, and something must decide what the object's real state is.

Why not timestamps

The intuitive fix is to timestamp every write and let the latest win. It does not work.

Physical timestamps are unreliable in distributed systems because clocks drift or become unsynchronized, so they cannot safely determine which request happened last.

Vector clocks

A vector clock is a list of (node, counter) pairs associated with every version of an object. Comparing two vector clocks tells you whether the versions are causally related — one descends from the other — or whether they conflict and need reconciliation.

The rule for reading them:

If every counter in clock X is <= the matching counter in clock Y,
then X is an ANCESTOR of Y  ->  Y supersedes X, discard X.

Otherwise the versions are CONCURRENT  ->  a conflict; keep both.

A worked example

Follow one object through a partition and back.

Step by step:

1. Node A handles the first write, E1, giving vector clock [A,1].
2. Node A handles another write to the same object, E2, giving [A,2]. E1 is no longer required — E2 happened on the same node, having read E1's changes and then made new ones. E2 supersedes E1.
3. A network partition occurs. The request is now handled by two different nodes, B and C.
4. This produces E3 with ([A,2], [B,1]) and E4 with ([A,2], [C,1]).
5. The partition is repaired and the client writes again — but now there is a conflict. The context ([A,2], [B,1], [C,1]) is returned to the client.
6. After the client reconciles and A coordinates the write, we get E5 with ([A,3], [B,1], [C,1]).

The API has to change

To enforce causality, each request must include the vector clock from the previous operation along with the originating node ID. So the API from Lesson 2 grows a parameter.

get becomes:

get(key)

This now returns an object — or a collection of conflicting objects — along with a context. The context holds encoded metadata such as the object's version.

put becomes:

put(key, context, value)

This locates the correct node from the key and stores the value. The client must provide the context received from a previous get in order to update an object — that context is what lets the system determine version history via vector clocks.

If a read reveals divergent branches, the system returns all objects at the leaf nodes with their version information, and the client reconciles them into a single new version.

Bounding vector clock growth

The size of a vector clock may increase if multiple servers write to the same object simultaneously. In practice this is unlikely, because writes are typically handled by one of the top n nodes in the preference list — a small, stable set.

But with network partitions or multiple server failures, writes may be processed by nodes outside the top n. Then you can end up with a version like:

[A,10], [B,4], [C,1], [D,2], [E,1], [F,3],
[G,5],  [H,7], [I,2], [J,2], [K,1], [L,1]

Storing and maintaining that much version history is a real burden, and it grows with every unusual event.

Clock truncation

To prevent unbounded growth, cap the size of the vector clock:

1. Attach a physical timestamp to each (node, counter) entry, recording that node's last update time for the item.
2. Remove the oldest entries once the number of pairs exceeds a configured threshold — for example, 10.

Interview signal by level

Next: making the consistency behavior tunable.