# DDIA Ch. 6: version numbers catch the conflict LWW hides ## 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. 1. **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. 2. **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. 3. **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. 4. **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 them - **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 Deterministic — no clocks, no randomness, no network — so the transcript reproduces exactly: - 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. ## Steps ### 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? **Observe.** ``` 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? **Observe.** ``` 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? **Observe.** ``` 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 1. **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. 2. **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? 3. **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.