A user sets their account private on one shard, then uploads a photo to another. The shards never message each other, so their independent Lamport clocks stamp the later upload 2 and the earlier set-private 8 — the order inverts. A snapshot read at T = 5 shows a still-public account that already holds the photo: it leaks. One linearizable id generator (private 9, upload 10) closes it.
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.
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.
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.
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.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.id(later) > id(earlier) always. It shows up in Step 3 as the fix.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, ...).7 → accounts shard 7 prior writes, photos shard 1 prior write.
Lamport orders events only along message chains. Picture the two edges it is built from:
a happens before b, the counter bumped between them, so ts(a) < ts(b). Solid.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.
cd study/ddia/ch10
python3 code/lamport_clock_leak.pyDo not read the output yet — make each prediction first.
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?
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.
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?
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.
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?
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.
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?
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.
T ∈ [2, 7].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.
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.
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.Sources: DDIA 2e, Ch. 10, §"Linearizable ID Generators" (Figure 10-10), §"Total Order Broadcast", §"Sequence Number Ordering" · Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System" (1978).