Data Versioning with Vector Clocks

In one line: 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.

What clock skew actually costs you

If node B's clock runs 200 ms ahead of node C's, a write made earlier in real time can carry a later timestamp — and last-write-wins will discard the newer write, permanently, with no error and no record.

This is the same trap the databases material flagged for LWW conflict resolution. The difference here is that we refuse to accept it: instead of guessing which write is newer, we track which writes knew about which other writes. That is causality, and unlike time it can be established without synchronized clocks.

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]).

Read step 4 carefully — it's the whole mechanism

E3 is ([A,2], [B,1]) and E4 is ([A,2], [C,1]).

Neither dominates the other: E3 has a B counter that E4 lacks, and E4 has a C counter that E3 lacks. So neither descends from the other — they are concurrent, which is exactly what a conflict is.

Compare that to step 2, where [A,1] is clearly an ancestor of [A,2] and can be safely discarded. The same comparison rule detects both cases — that is why vector clocks work without any clock at all.

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.

Truncation trades correctness for bounded size

Since truncation can remove causal history, the system may no longer accurately determine version ancestry, which can reduce reconciliation accuracy.

Two versions that were genuinely related may now look concurrent — producing a false conflict the client is asked to resolve unnecessarily. That is the acceptable direction of error: a spurious conflict is annoying, whereas missing a real conflict would silently lose data.

Note the irony worth pointing out in an interview: physical timestamps were rejected for deciding order, and they reappear here purely as a heuristic for deciding what to forget. That is a legitimate use — being wrong about which entry is oldest costs you accuracy, not correctness.

Interview signal by level

Next: making the consistency behavior tunable.