# DDIA Ch. 13: uniqueness needs a total order; async multi-leader grants 'alice' twice ## Concept Two users race to claim the username `alice`; a `UNIQUE(username)` constraint says exactly **one** may own it. A tempting design: two datacenters, each a leader that enforces the constraint locally, replicating asynchronously. Model it — two independent leaders, each with its own `taken` set, each check-then-set against its **local** table — and both requests find `alice` free and both **GRANTED**. The constraint is silently violated; the conflict is only discovered at replication merge, by which point two users have been told they own `alice`. Now route every claim through **one totally-ordered log partition** (partition by hash of the username), consumed single-threaded: the consumer sees a definite **first** writer, grants one and **REJECTS** the rest — exactly one owner. Same two claims; the only difference is whether the contenders share an order. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 13 — *The Future of Data Systems* (stream processing / a philosophy of streaming systems), §"Uniqueness constraints require consensus" and §"Uniqueness in log-based messaging": > Enforcing a uniqueness constraint requires consensus [...] The most common way > of achieving this consensus is to make a single node the leader, and put it in > charge of making all the decisions. The book rules out asynchronous multi-leader replication for uniqueness because different leaders can concurrently accept conflicting writes, and offers the log-based route: funnel all requests for a key through one partition of a totally-ordered log and let a single consumer decide. Here you watch both. ## Prerequisites The surprise is that a *local* uniqueness check is not a uniqueness constraint. Each line notes where the idea shows up. 1. **Uniqueness constraints** — `UNIQUE(username)` must admit exactly one owner across the *whole* system, not per node. It shows up as the two-owner outcome in Model 1: each leader's local constraint held, yet the global one broke. 2. **Consensus / total order** — agreeing on a single value (here: who was first) is consensus; a total order over the contenders is what supplies that agreement. It shows up as the log partition's fixed order in Model 2. 3. **Asynchronous multi-leader replication & write conflicts** — independent leaders accept writes without coordinating, so two conflicting writes can both commit and only clash at merge time. It shows up as the CONFLICT line after "asynchronous replication merges the two leaders." 4. **Log-based single-consumer serialization** — appending to one ordered partition and consuming it single-threaded turns concurrent requests into a sequence with a definite first element. It shows up as the offset-0 grant, offset-1 reject. ### Where to learn the prerequisites - **Uniqueness = consensus (#1, #2):** DDIA §"Uniqueness constraints require consensus" and Ch. 10 §"Consensus"; the constraint is equivalent to all contenders agreeing on a single first writer. - **Multi-leader write conflicts (#3):** DDIA Ch. 6 §"Handling write conflicts" — concurrent writes to the same key on different leaders conflict, and detection happens asynchronously, after both have committed. - **Log-based uniqueness (#4):** DDIA §"Uniqueness in log-based messaging" — route all requests for a key to the same log partition and decide with a single-threaded consumer. If only one carries the result, it is **uniqueness ≡ agreeing on a first writer**: the whole exercise is that a uniqueness constraint is a consensus problem in disguise, and consensus needs a shared order the async leaders lack. ## Environment Deterministic — the concurrency is modeled explicitly, so the outcome is fixed: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — no Docker, no deps - No real threads: the two concurrent claims and the log order are laid out in code, so both models produce the same result every run - Fixed workload: two users (`user-1` via `req-1`, `user-2` via `req-2`) both claim `alice` ## Mental model A uniqueness constraint requires all contenders for a name to **agree who was first**. Two ways to try to supply that agreement: - **Asynchronous multi-leader** — each leader owns a *local* copy of the uniqueness index and decides on its own. There is no shared order: a grant at L1 is invisible to L2 until a later async merge. So both leaders can look at their table, see `alice` free, and both grant. The disagreement surfaces only when the two logs merge — after both users were promised the name. A compare-and-set inside each leader would not help: the leaders don't share the register it would test. - **One totally-ordered log partition** — every claim for `alice` is appended to the *same* partition (chosen by hash of the username) and a single consumer reads it in order. The log *is* the shared order: it has a definite first entry, so the consumer grants that one and rejects every later one. One order, one first writer, one owner. Both models run against the identical two claims. The whole thing is one script, `code/uniqueness_needs_total_order.py`. ## Setup ``` cd study/ddia/ch13/code python3 uniqueness_needs_total_order.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — the async multi-leader constraint **Predict.** Two datacenters, each a leader enforcing `UNIQUE(username)` on its own local table, replicating asynchronously. Two users concurrently claim `alice`, one request routed to each leader. How many of the two claims are GRANTED? **Observe.** ``` MODEL 1 -- asynchronous multi-leader replication two independent leaders, each enforces UNIQUE(username) on its LOCAL table two users concurrently claim 'alice', one request routed to each leader: L1 receives req-1 (user-1): checks local table, 'alice' is free -> GRANTED L2 receives req-2 (user-2): checks local table, 'alice' is free -> GRANTED ``` **Both GRANTED.** Each leader's local check passed — from L1's view `alice` was free, and from L2's view `alice` was free too. Neither local constraint was violated; the *global* one was. ### Step 2 — the async merge **Predict.** Replication now merges the two leaders' indexes. Does the merge catch the conflict in time to keep the constraint — and how many owners does `alice` end up with? **Observe.** ``` ... asynchronous replication merges the two leaders ... L1.taken['alice'] = req-1 L2.taken['alice'] = req-2 CONFLICT at merge: two owners for 'alice' -- detected, but both users were already told they won RESULT: 2 grants for 'alice' -- UNIQUE constraint VIOLATED (two owners) owner: user-1 via req-1 (granted by L1) owner: user-2 via req-2 (granted by L2) ``` **Two owners — the constraint is violated.** The merge *detects* the conflict, but detection is too late: both grants already committed and both users were told they own `alice`. Async replication moves conflict discovery to *after* the decision, which is exactly when a uniqueness constraint can no longer be enforced. ### Step 3 — one totally-ordered log partition **Predict.** Now route both claims through a single log partition (chosen by hash of the username) and consume it single-threaded. How many of the two claims are GRANTED? **Observe.** ``` MODEL 2 -- one totally-ordered log partition, single-threaded consumer all claims for 'alice' route to log partition #0 (hash of username) the log fixes ONE order; a single consumer grants the first, rejects the rest: log partition #0 order: req-1(user-1) , req-2(user-2) offset 0: consume req-1 (user-1): 'alice' is free -> GRANTED offset 1: consume req-2 (user-2): 'alice' already owned by req-1 -> REJECTED RESULT: 1 grant for 'alice' -- UNIQUE constraint HELD (exactly one owner) owner: user-1 via req-1 ``` **Exactly one owner.** The log gives the two claims a definite order; the single consumer grants offset 0 and, seeing `alice` already taken, rejects offset 1. The constraint holds *before* anyone is told they won — no merge, no conflict, no double grant. ### Step 4 — the two models side by side **Predict.** Summarize: how many owners does each model produce, and what is the one structural difference that decides it? **Observe.** ``` ==================================================================== async multi-leader : 2 owners -> constraint violated totally-ordered log: 1 owner -> constraint held uniqueness needs all contenders to agree who was FIRST; independent leaders have no shared order, so both think they won; one ordered partition gives every contender the same first writer. ``` **2 vs 1 — the difference is a shared order.** Nothing about the claims changed; what changed is whether the contenders were forced through one order. That order is the consensus the constraint needs. ## What you should see - Async multi-leader: **both** claims GRANTED, `alice` ends with **2 owners** — `UNIQUE(username)` **violated**, and the conflict only surfaces at merge. - Totally-ordered log: **1** claim GRANTED, **1** REJECTED, `alice` has **1 owner** — `UNIQUE(username)` **held**. - The only structural change between the two is whether all contenders for the key share a single total order. ## Why A uniqueness constraint is a consensus problem wearing a schema keyword. To grant `alice` to exactly one claimant, the system must **linearize** the claims: put them in a single order and let the first one win. Everything turns on whether that order exists at decision time. Asynchronous multi-leader replication has no such order. Each leader is an independent decider with its own copy of the index, and by construction it commits a write *before* replicating it. So when two claims land at the same instant on different leaders, each check-then-set runs against a table that has not yet heard about the other — both read `alice` free, both write, both grant. The conflict is real, but it becomes *visible* only when the two logs merge, and a merge that runs after both commits can at best *detect* a double grant, never prevent it. (A compare-and-set inside a leader doesn't rescue this: CAS serializes contenders on *one* register, and the two leaders are testing two different registers. Local atomicity buys nothing when the deciders are independent.) That is precisely why the book rules async multi-leader out for uniqueness. Routing every claim for a key through **one totally-ordered log partition** is the consensus that was missing. Appending to a single partition assigns the concurrent claims a definite sequence — offset 0, then offset 1 — and a single-threaded consumer reading that sequence sees an unambiguous first writer. It grants offset 0 and rejects everything after, so at most one claim is ever granted. The log doesn't detect the conflict after the fact; it *dissolves* it, because there is never a moment when two deciders both believe `alice` is free. Uniqueness = agreeing on a first writer = a total order over the contenders. **The boundary — the violation needs concurrent INDEPENDENT deciders.** A single leader (or a single partition per key) already provides the order for free: one decider processing claims in sequence has a first writer by construction, so it needs no extra consensus machinery — a plain `UNIQUE` index on one primary does the job. The anomaly appears *only* when two or more nodes decide the same key without a shared order. And the fix does not require a global bottleneck: partitioning the log **by the unique key** keeps every key's decisions serial on its own partition while different keys proceed in parallel — you serialize `claim('alice')` against other `alice` claims, not against `claim('bob')`. The constraint scales precisely because uniqueness is per-key, so the order it needs is per-key too. ### Go deeper 1. **Why uniqueness = consensus = linearizable ID assignment.** Granting a name to one claimant is the same shape as handing out a unique, monotonic ID: both demand that all contenders agree on a single winner/next-value. Trace how the log's offsets *are* a linearizable ID assignment for the key. 2. **Cross-reference the Ch. 10 linearizable-ID / Lamport-leak exercise** (`ddia/ch10/lamport-clock-leak.md`) — it shows a Lamport clock giving a total order that is *not* linearizable without a max-so-far exchange. The same gap is why "eventually consistent" multi-leader can't enforce uniqueness: an order that only exists after merge is too late. 3. **Shard the constraint by key.** Change `partition_for` to spread keys across partitions and confirm that `alice` and `bob` claims land on different partitions and decide in parallel — uniqueness held per key, no global lock.