study › DDIA › Chapter 6 · Replication

Version Numbers Catch the Conflict LWW Hides

Two clients edit the same cart concurrently — each based on v0. Last-Write-Wins keeps the greater timestamp and silently drops one write. A version number recognizes the two as concurrent and keeps both as siblings: v0 → v1{[milk]} → v2{[milk],[eggs]} → v3{[milk, eggs]}. Nothing is lost.

Concept

Two clients edit the same shopping cart at the same time. Each read the cart before the other's write existed, so neither saw the other — the two writes are concurrent. Last-Write-Wins resolves the clash by keeping the greater timestamp and throwing the other write away, silently: one customer's item just vanishes, no error. A version number per key does better. Because the server makes every client read-before-write and echo back the version it last saw, it can tell that both writes were "based on v0" and so neither supersedes the other — it keeps both as siblings and hands them to the app to merge. You will replay the book's cart example and watch the server go v0 → v1{[milk]} → v2{[milk],[eggs]} → v3{[milk, eggs]}, then run the identical two writes under LWW and watch milk disappear.

Provenance

Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 6 — Replication, §"Detecting Concurrent Writes" / §"Capturing the happens-before relationship":

the server can return all siblings—all values that have not been overwritten.

The book develops the single-replica algorithm on the shopping-cart example. Here you implement that server and watch it detect the concurrency LWW erases.

Prerequisites

The surprise is that a plain integer, not a clock, is what separates concurrent writes from sequential ones. These help; each line notes where it shows up.

Concurrent vs. sequential writes — two operations are concurrent when neither happened-before the other (neither client saw the other's write). The whole point is that concurrency is a fact about causality, not about time — both writes here are "based on v0", which is exactly what makes them concurrent.
Read-before-write — the protocol requires a client to read (getting the current version) before it writes, and to send that version back. That echoed version is what lets the server reconstruct happens-before; it is used in every write call in the transcript.
Siblings — when the server cannot order two writes, it keeps both values for the key. Those un-overwritten values are the siblings a read returns; you see the sibling set printed after each step.
Last-Write-Wins (LWW) — the baseline: attach a timestamp, keep the max, discard the rest. It is what the contrast run uses, and what silently loses the milk.

Where to learn the prerequisites Concurrency & happens-before (#1): DDIA §"The 'happens-before' relationship and concurrency"; Lamport's Time, Clocks, and the Ordering of Events for the original definition. The server algorithm & siblings (#2, #3): DDIA §"Capturing the happens-before relationship" — the worked cart example this exercise runs. LWW and why it drops data (#4): the companion exercise lww_clock_skew.py in this chapter, and DDIA §"Last write wins". If only one is new, make it #1 — "concurrent" meaning causally unordered, not simultaneous, is the hinge of the whole exercise.

Environment these numbers came from Deterministic — no clocks, no randomness, no network — so the transcript reproduces exactly. Captured on macOS 26.5.2 (Darwin 25.5.0), arm64, Python 3.15.0a8, standard library only — no pip, no Docker. One key, cart, whose value is a list of items; two concurrent clients plus a later merging client, exactly as in the book's figure.

Mental model

The server stores, per key, two things: a version number and a set of siblings — the values written since they were last overwritten, each tagged with the version at which it landed. The rules:

Read returns the current version number and every sibling value.
Write carries the version the client last read. The server overwrites (removes) every value at or below that version — the client had seen those, so its new value subsumes them — but keeps every sibling written since, because the client never saw those and cannot claim to replace them. It stores the new value under a freshly incremented version.

So a write "based on v0" arriving after another "based on v0" write does not overwrite it (that value sits at v1 > 0): both survive as siblings. Contrast this with LWW, which just keeps max(timestamp) and discards the rest. The whole exercise is one script, code/version_vectors.py.

Setup

cd study/ddia/ch06
python3 code/version_vectors.py

Do not read the output yet — make each prediction first.

Step 1 · predict the version-vector run

Predict. The server starts empty at version 0. Client 1 reads v0, adds milk, writes based on v0. Client 2 also read v0 (before client 1's write existed), adds eggs, writes based on v0. Write down the version number and the sibling set after each write. Is [eggs] written on top of [milk] (replacing it), or alongside it?

Does the second "based on v0" write replace milk, or join it?

VERSION NUMBERS -- the server keeps a version + the un-overwritten siblings -------------------------------------------------------------------------- server: version 0, siblings { } (empty cart, nothing written yet) server: version 1, siblings { [milk] } client 1 read v0, added milk, wrote based on v0 server: version 2, siblings { [milk] [eggs] } client 2 also read v0, added eggs, wrote based on v0 <-- CONCURRENT ^ two writes both 'based on v0' -> server recognizes them as concurrent and returns BOTH as siblings. Neither milk nor eggs is lost.

Because client 2's write was based on v0, the server overwrites only values at version ≤ 0 — and [milk] sits at v1, so it stays. The result is a sibling set {[milk], [eggs]}, the server's way of saying "these two are concurrent; I cannot pick a winner, so here are both."

Step 2 · watch the merge collapse the siblings

Predict. A later client reads at v2 and gets both siblings. It merges them to [milk, eggs] and writes based on v2. What happens to the two siblings now?

Does the merge, based on v2, clear both siblings?

server: version 3, siblings { [milk, eggs] } later client read v2, merged siblings -> [milk, eggs], wrote based on v2 ^ writing based on v2 (having seen both) overwrites both siblings: the conflict is now resolved by the app, with everything preserved.

This write was based on v2 — the client had seen everything up to and including both siblings — so the server overwrites all values at version ≤ 2, which is both of them, and stores the merged cart at v3. The conflict is resolved by the app, and nothing was lost along the way.

Step 3 · run the same two writes under LWW

Predict. Take the identical concurrent writes — client 1 adds milk, client 2 adds eggs — and resolve them with Last-Write-Wins (keep the greater timestamp). What does the cart contain afterward?

What survives LWW — and what silently disappears?

LAST-WRITE-WINS -- same two concurrent writes, keep the greater timestamp -------------------------------------------------------------------------- client 1 writes [milk] (ts=100) client 2 writes [eggs] (ts=101) => LWW keeps the greater timestamp: [eggs] (client 2, ts=101) - [milk] (client 1, ts=100): LOST (silently discarded) bottom line -- what each cart contained after the two concurrent writes: version numbers -> [milk, eggs] (both writes detected as concurrent, kept as siblings, then merged) last-write-wins -> [eggs] (one concurrent write silently dropped) LWW lost: ['milk'] -- the customer's cart is missing an item, with no error. Concurrent writes are not ordered by a clock; a version number that captures happens-before is what tells the two apart.

Same two writes, two outcomes: version numbers preserve [milk, eggs]; LWW keeps only [eggs] and drops milk with no error, no conflict, no trace.

What you should see

The version-number run climbs v0 → v1{[milk]} → v2{[milk], [eggs]} → v3{[milk, eggs]}; the two "based on v0" writes become siblings, not one overwriting the other.
The merge, made based on v2, collapses both siblings into one value — conflict resolved with nothing lost.
LWW on the identical writes keeps only [eggs]; milk is silently discarded.

Why

The difference is what each scheme uses to decide whether one write may replace another. LWW uses a timestamp and the rule "bigger wins." But a timestamp is just a number on a clock; it imposes a total order on writes that were never actually ordered. The two cart writes happened concurrently — neither client saw the other — yet LWW must still declare one "later," and the "earlier" one is deleted. The information that they were concurrent is simply gone by the time LWW compares timestamps.

The version number keeps that information. Because every client reads before it writes and echoes back the version it saw, the server can ask a sharper question than "which is newer?": it asks "which values had this writer already seen?" Those, and only those, its write is entitled to overwrite. Client 2 had seen only v0, so it may overwrite values at v0 — but [milk] was written at v1, after what client 2 saw, so client 2 has no authority over it. The server keeps both. This is precisely the happens-before relation: a write supersedes another only if it causally follows it (saw its version). When neither saw the other, the writes are concurrent and the server preserves both siblings — pushing the choice up to the application, which knows that two carts should be merged, not that one should win.

The boundary — version numbers detect conflicts, they do not resolve them, and one number only covers one replica The server here still had to be handed a merge — the app decided [milk] ∪ [eggs] = [milk, eggs]; a different app might need a different rule (and deletions need tombstones, or a merged-away item can resurface). A single integer works because there is one replica assigning versions. With multiple replicas each accepting writes, one counter is not enough: you need a version vector — one version number per replica — so that "which writes had this client seen?" can be answered per replica. That is the leaderless / multi-leader case, and the vector is the generalization of the single number you just watched work.

Go deeper

Break the read-before-write rule. Make client 2 write based on v1 (as if it had seen milk) instead of v0. Predict the sibling set — and notice that a client which lies about what it saw can still overwrite a concurrent write. The protocol's safety rests on honest version echoes.
Three concurrent writers. Add a client 3 that also read v0 and adds bread. Predict the version and sibling set after all three "based on v0" writes, then after a client reads and merges. How many siblings does the server hold at the peak?
Generalize to a version vector. Extend the store to two replicas, each with its own counter, and make read return the pair. Work out the merge rule for two vectors (component-wise max) and confirm it still calls the milk/eggs writes concurrent — this is the leaderless case DDIA covers next.

Sources: DDIA 2e, Ch. 6, §"Detecting Concurrent Writes", §"Capturing the happens-before relationship", §"Version vectors" · Lamport, Time, Clocks, and the Ordering of Events in a Distributed System (1978).