# DDIA Ch. 10: a Lamport clock inverts a cross-shard "then", and the gap leaks a private photo

## Concept

A user does two things, in this order: (1) sets their account **private** on the
accounts shard, then (2) uploads a photo to the photos shard. Each shard stamps
its own writes with its own Lamport clock, and the two shards exchange **no
message** for these two operations. Because a Lamport timestamp only advances
across a message, the user's real "(1) then (2)" is invisible to the clocks — and
the photos shard, having seen fewer local events, stamps the **later** upload with
a **lower** number (`2`) than the **earlier** set-private (`8`). The order
inverts. Now a viewer takes an MVCC snapshot read at a timestamp **between** the
two: they see a still-**public** account that already holds the photo — a photo
that only exists *because* the account was already private. It **leaks**. The fix
is one line of architecture: route both writes through a single **linearizable id
generator**, so the upload provably gets a higher id (`10`) than set-private
(`9`), and no snapshot can ever show the photo before the privacy.

## Provenance

*Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025),
Chapter 10 — *Consistency and Consensus*, §"Linearizable ID Generators"
(Figure 10-10):

> Lamport timestamps [...] provide a total ordering [...] but this order is not
> sufficient [...] a node cannot immediately tell whether another node's operation
> causally precedes or follows its own.

The book contrasts Lamport timestamps (a total order that is only *consistent
with* causality along message chains) against a linearizable, monotonically
increasing ID generator that reflects the order operations *actually* happened.
Here you build two shards that never message each other, watch Lamport invert a
real "then," leak a photo through the inversion, then close it with the
linearizable sequencer.

## Prerequisites

The surprise turns on one fact: **no message ⇒ no causal edge**. Lamport can only
order what a happens-before chain connects, and nothing connects these two ops.
Each line notes where the idea shows up.

1. **Lamport clocks & happens-before** — each node keeps a counter, bumped +1 on
   every local event and raised to `max(local, incoming)+1` only when a *message*
   arrives. The guarantee "if `a` happened-before `b` then `ts(a) < ts(b)`" is
   built from exactly two edges: process order on one node, and the +1 across a
   message. It shows up as `LamportClock.local_event()` vs. `receive()` — and the
   `receive()` that is never called between the shards is the bug.
2. **Concurrent events on non-communicating nodes are unordered** — if no chain of
   messages links `a` and `b`, they are *concurrent*, and Lamport's total order
   (counter, then node-id tiebreak) is an arbitrary choice, not a causal fact. It
   shows up as the busier accounts shard stamping the *earlier* real event with
   the *larger* number.
3. **Linearizable / total-order ID generators** — a single sequencer that hands
   out ids in the real order operations reach it. Because there is one monotonic
   source, `id(later) > id(earlier)` always. It shows up in Step 3 as the fix.
4. **Snapshot (MVCC) reads** — a read at timestamp `T` sees exactly the writes with
   `ts <= T`. It is the reader that turns the timestamp inversion into a *visible*
   anomaly: it shows up as `Shard.snapshot(T, ...)`.

### Where to learn the prerequisites

- **Lamport clocks & happens-before (#1, #2):** Lamport, *Time, Clocks, and the
  Ordering of Events in a Distributed System* (1978) — the original; DDIA
  §"Sequence Number Ordering" and §"The 'happens-before' relationship and
  concurrency" (Ch. 6).
- **Linearizable ID generators (#3):** DDIA §"Linearizable ID Generators" and
  §"Total Order Broadcast" — why a correct one needs consensus.
- **Snapshot isolation / MVCC (#4):** DDIA Ch. 8, §"Snapshot Isolation and
  Repeatable Read".

If only one is new, make it **#2** — "concurrent" meaning *causally unordered*,
not *simultaneous*, is the hinge: no message between the two ops means Lamport
never had an edge to preserve.

## Environment

Deterministic — the shards' background histories come from a seeded RNG and the
two operations run in a fixed order, so the transcript reproduces exactly:

- macOS 26.5.2 (Darwin 25.5.0), arm64
- Python 3.15.0a8, standard library only — no Docker
- Two shards simulated in one process; no real network, no wall clock
- Seed `7` → accounts shard 7 prior writes, photos shard 1 prior write

## Mental model

Lamport orders events **only along message chains**. Picture the two edges it is
built from:

- **Process order** — on a single node, if `a` happens before `b`, the counter
  bumped between them, so `ts(a) < ts(b)`. Solid.
- **Message order** — when a node sends `a` and another receives it as `b`, the
  receiver does `counter = max(local, ts(a)) + 1`, so `ts(b) > ts(a)`. Solid.

Happens-before is the *transitive closure of just those two edges*. A user's
real-world "I set private, then I uploaded" is neither: it crosses from the
accounts shard to the photos shard **without a message**. So to Lamport the two
ops are **concurrent** — genuinely unordered — even though the human did them in
sequence. And when two independent counters are compared, the one that has ticked
more wins, regardless of real time: the busier accounts shard (counter already at
7) stamps set-private `8`, while the quiet photos shard (counter at 1) stamps the
*later* upload `2`. The whole exercise is one script,
`code/lamport_clock_leak.py`.

## Setup

```
cd study/ddia/ch10
python3 code/lamport_clock_leak.py
```

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

## Steps

### Step 1 — the timestamp inversion

**Predict.** The accounts shard has had 7 prior local writes (counter = 7); the
photos shard has had 1 (counter = 1). The user does set-private on accounts
*first*, then upload on photos. No message passes between the shards. What Lamport
timestamp does each op get — and which number is larger?

**Observe.**

```
SETUP -- two shards, each with its own independent Lamport clock
    accounts shard: 7 prior local writes  -> Lamport counter now 7
    photos   shard: 1 prior local writes  -> Lamport counter now 1
    the shards exchange NO message -- neither clock has ever seen the other's

STEP 1 -- the user acts: set PRIVATE, then upload a photo
    real-world order the user performed:
      (1) accounts.set_private   THEN   (2) photos.upload

    (1) set_private  on accounts shard -> Lamport ts = 8
    (2) upload_photo on photos   shard -> Lamport ts = 2

    INVERSION: the user did (1) THEN (2), but ts(upload)=2 < ts(set_private)=8.
```

**Upload gets `2`, set-private gets `8` — the later op has the smaller
timestamp.** Each shard just incremented its own counter (7→8, 1→2). Nothing
carried the accounts shard's time to the photos shard, so the photos clock had no
reason to be anywhere near 8. Lamport didn't get it "wrong" — it never had an edge
between these two ops to get right.

### Step 2 — the leaking snapshot read

**Predict.** A viewer takes an MVCC snapshot read at `T = 5` (between the two
timestamps: `2 <= 5 < 8`). A write is visible iff its `ts <= T`. As of `T = 5`, is
the account private? Does the photo exist? What does the viewer see?

**Observe.**

```
STEP 2 -- a viewer's MVCC snapshot read BETWEEN the two timestamps
    snapshot timestamp T = 5   (chosen: ts_upload=2 <= T < ts_private=8)
    a write is visible in the snapshot iff its timestamp <= T

    accounts.visibility as of T : PUBLIC   (set_private ts=8 > T, so NOT yet visible)
    photos.photo:sunset as of T : EXISTS   (upload ts=2 <= T, so visible)

    >>> LEAK: the snapshot shows a PUBLIC account that already holds the photo.
    >>> The viewer sees a photo that only exists because the account was
    >>> ALREADY private -- data they were never supposed to see.
```

**Public account, existing photo — the leak.** The upload (`ts=2`) is under the
snapshot, so the photo is visible; set-private (`ts=8`) is above it, so the
account still looks public. The snapshot is a consistent-looking cut across both
shards that never actually existed in real time: the user was *already private*
when they uploaded.

### Step 3 — the fix: one linearizable id generator

**Predict.** Now route both writes through a single monotonic sequencer that hands
out ids in the order operations reach it. The user repeats the same real sequence:
set-private, then upload. What id does each get — and is the later op's id larger?

**Observe.**

```
STEP 3 -- the fix: one LINEARIZABLE id generator for both writes
    both shards now take their write id from a single monotonic sequencer,
    so ids are handed out in real order regardless of which shard writes.

    (1) set_private  -> linearizable id = 9
    (2) upload_photo -> linearizable id = 10
    ORDER RESTORED: id(upload)=10 > id(set_private)=9, matching real order.
```

**Set-private `9`, upload `10` — the later op now has the larger id.** One source,
one counter, incremented in real order: there is no way for a later request to get
a smaller id. The cross-shard "then" is finally represented by an edge — the
shared sequencer — that Lamport's two per-shard clocks never had.

### Step 4 — no snapshot can leak now

**Predict.** Scan every possible snapshot timestamp `T` from 0 upward under the
fixed ids (private = 9, upload = 10). Is there any `T` where the photo exists but
the account is still public?

**Observe.**

```
STEP 4 -- no snapshot can leak now: scan every boundary
    T=0: account=public  photo=absent -> safe
    T=1: account=public  photo=absent -> safe
    T=2: account=public  photo=absent -> safe
    T=3: account=public  photo=absent -> safe
    T=4: account=public  photo=absent -> safe
    T=5: account=public  photo=absent -> safe
    T=6: account=public  photo=absent -> safe
    T=7: account=public  photo=absent -> safe
    T=8: account=public  photo=absent -> safe
    T=9: account=private photo=absent -> safe
    T=10: account=private photo=exists -> safe
    T=11: account=private photo=exists -> safe

    >>> No snapshot shows photo-without-private. The photo can only become
    >>> visible at T >= id(upload), and by then set_private (a lower id) is
    >>> ALREADY visible. The leak is closed.
```

**Every `T` is safe.** The photo first appears at `T = 10`, and at `T = 10` the
account is already private (visible since `T = 9`). Because `id(private) <
id(upload)` *always*, there is no window where photo leads privacy. The anomaly
isn't patched — it's made unrepresentable.

## What you should see

- Under two independent Lamport clocks the later upload gets ts **2**, the earlier
  set-private gets ts **8** — the order **inverts**.
- A snapshot read at **T = 5** shows a **public** account that already **holds the
  photo** — the leak, over the window `T ∈ [2, 7]`.
- Under one linearizable id generator, set-private gets **9** and upload **10** —
  order **restored**.
- Scanning every boundary, **no** snapshot shows photo-without-private — the leak
  is closed.

## Why

Lamport's happens-before relation is, precisely, the transitive closure of two
edges: *process order* (events on one node are ordered by its local counter) and
*message order* (a receive lands above the matching send, via
`max(local, incoming)+1`). The total order Lamport timestamps induce is
*consistent with* that relation — if `a → b` then `ts(a) < ts(b)` — but it says
**nothing** about pairs the relation doesn't connect. Our two operations are
exactly such a pair: the user crossed from the accounts shard to the photos shard
in their own head, with no message between the shards, so no edge exists. To
Lamport the ops are concurrent, and its tiebreak (bigger counter, then node id)
picks an order with no relation to real time. The busier shard's counter simply
happened to be higher, so the *earlier* real event won the bigger number. The
snapshot read then does what MVCC always does — include every write with
`ts <= T` — and faithfully renders a cut, `T = 5`, that inverts causality: photo
present, privacy absent.

The linearizable id generator fixes this by *manufacturing the missing edge*.
Every write, on either shard, must first ask one monotonic sequencer for an id.
That single source imposes a real-time total order on all writes — the essence of
linearizability — so an operation that reaches it later provably gets a larger id.
The user's cross-shard "then" is now backed by an actual ordering edge (both
requests passed through the one sequencer, in order), which is the edge the two
independent Lamport clocks never had. Privacy gets `9`, the upload `10`, and the
"photo before privacy" state is no longer a point on any timeline.

### The boundary — the leak needs the cross-shard, no-message gap

Put the two writes on the **same shard** and the inversion vanishes: one Lamport
counter orders them by process order, so `ts(upload) > ts(set_private)`
automatically. Or leave them on separate shards but pass **any message** carrying
the accounts clock to the photos shard before the upload (`receive(8)` → photos
counter jumps to 9, upload gets 10): the message edge restores the order too. The
anomaly exists *only* in the gap — two nodes, a real "then" that crosses between
them, and no message to carry it. That gap is common: independent microservices,
sharded stores, and separate databases routinely don't message each other on the
write path.

### Go deeper

1. **Add the message.** Have the accounts shard send its clock to the photos shard
   (`photos.clock.receive(ts_private)`) before the upload, and confirm the upload's
   timestamp jumps above 8 and the leak closes — the message edge does the same job
   as the sequencer, for this one pair.
2. **Why the sequencer is hard.** A single id generator is a single point of
   failure; making it fault-tolerant *and* still totally ordered is
   **total-order broadcast**, which is **equivalent to consensus** (DDIA
   §"Total Order Broadcast"). The one clean line in Step 3 hides a Raft/Paxos-sized
   problem.
3. **Detect vs. order.** Contrast the Ch. 6 `version-vectors` exercise: version
   vectors *detect* that two writes are concurrent and keep both as siblings — they
   never impose a total order. Here you *want* a total order (privacy really did
   come first), so detection isn't enough; you need the linearizable sequencer.
   Two different answers to "these two clocks disagree," for two different goals.
```