Section 8: Two Truths About One Cart - Deep Dive: Versioning, Vector Clocks & Reconciliation

Executive Summary: Every stored version carries a vector clock, a short list of (node, counter) pairs. Comparing two clocks tells the store whether one version descends from the other, so the store discards the ancestor itself (syntactic reconciliation), or whether they are concurrent, so both go back to the reader and the cart service merges them (semantic reconciliation). We follow Dana's cart from D1 [B:1] through the DC1 partition to siblings D3 and D3′, then to the merged D4 [B:4, F:1]. Two refinements from the 2007 paper keep this cheap: the write coordinator is the node that answered the preceding read fastest, and clocks are truncated at 10 pairs. Truncation usually costs a false sibling and can, in principle, hide a real one: it is safe in practice, not by construction. Last-write-wins, the rejected alternative, would lose either the removal or the gift card.

Interviewer: "Dana's phone and laptop both wrote cart:7731 while DC1 was cut off. Which write wins?"

You: "Neither. That's the point of the design. The store's job isn't to pick a winner. It has to notice that there are two truths, keep both, and give them to the only party that knows how to combine them, which is the cart service. Let me show you how the store notices."

A Version Is a Clock, Not a Timestamp

A vector clock is a list of (node, counter) pairs, one entry per node that has coordinated a write to this key. When a coordinator handles a put, it takes the clock from the caller's context and increments its own entry. In this design each entry also carries a wall-clock timestamp. That timestamp is never used to order versions. It exists only so truncation can find the oldest entry.

One rule the paper leaves implicit, and our design states: the coordinator must also compare the incoming context with what it already stores. If B holds a version the context doesn't cover (say a robot's write that also came through B), the new write is concurrent with it. B advances its counter past both (max of local and context, plus one) and keeps the uncovered version as a sibling, replicating the two together. Without this rule, two writes through B from the same context would both be stamped [B:3], and one would silently replace the other.

Comparison is mechanical. Version X descends from Y if every counter in X is greater than or equal to the matching counter in Y. If each clock has some entry larger than the other's, the versions are concurrent: neither writer saw the other's write. A wall clock can't make that distinction; it says which write came later by one machine's reckoning, not whether the second writer knew about the first.

Here is Dana's arc, version by version:

Check step 4 by hand. D3 has F:1 and D3′ has no F entry, so D3 is ahead on F. D3′ has B:3 against D3's B:2, so D3′ is ahead on B. Each is ahead somewhere, so they are concurrent. Each still dominates D2, which means any replica holding D2 next to either of them can drop D2 without asking anyone.

Key Insight: Vector clocks don't resolve conflicts. They classify them. Syntactic reconciliation handles the overwhelming majority, where one version simply descends from the other, inside the store with no application code. Only true concurrency reaches the application, and it arrives with enough information to merge correctly.

Quick check before moving on: