# DDIA Ch. 13: losing causal order across two logs notifies the ex you unfriended ## Concept Alice does two things, in order: first she **unfriends** her ex Bob, then she **posts** a rude message. Because she unfriended him *before* posting, Bob must not be notified. But the two facts live in **two independent logs** — a friendship log and a message log — with no shared order between them. A notification service is a *join* that consumes both. Merge them by **arrival order** and, because the logs travel over independent transports, the post can arrive *before* the unfriend: the consumer still sees Alice and Bob as friends and **fires a notification to Bob** — a real side effect that cannot be un-sent. Two fixes the chapter names close the leak: **(a)** route both events for the (alice, bob) pair through the **same ordered partition** so the unfriend is delivered first; or **(b)** stamp the post with a **causal reference** to the friend-list version it was written against, and have the consumer **wait** for that version before processing. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 13 — *A Philosophy of Streaming Systems* (referred to in the book's Ch. 5 material as well), §"Ordering events to capture causality": > ...the unfriend event and the message-send event may be processed in a > different order by a downstream consumer, so the notification service may send > the notification even though the sender unfriended the recipient first. The book uses the break-up scenario to make one point precise: a real-world "A happened before B" survives downstream **only if the system records the dependency**. Two independent logs discard it, so a consumer joining them is free to process B before A. Here you trigger exactly that notification, then watch each fix suppress it. ## Prerequisites The leak turns entirely on order that was never captured. Each line notes where it shows up. 1. **Causal ordering / happens-before** — Alice's unfriend *happened before* her post; a correct system must preserve that "before" all the way to the notification consumer. It shows up as the required verdict: Bob is *not* notified. 2. **Multiple independent logs lose cross-log order** — two logs each have their own internal order, but there is no order *between* them, so a join can interleave them any way transport delivers. It shows up as the post arriving before the unfriend in the buggy run. 3. **Single-partition ordering** — everything routed through one partition is delivered in one total order; co-locating the two events there restores "unfriend before post." It shows up in fix (a). 4. **Causal dependencies / version references** — an event can name the version of state it was written against; a consumer that *waits* for that version won't process the event too early. It shows up in fix (b) as `depends_on_friend_version=2`. ### Where to learn the prerequisites - **Happens-before and causality (#1):** DDIA §"The 'happens-before' relationship and concurrency" (Ch. 6); Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System" (1978). - **Ordering events to capture causality (#2–#4):** DDIA Ch. 13 §"Ordering events to capture causality" — the same break-up example, and the two remedies (co-locate in one partition, or attach a causal reference / logical timestamp the consumer respects). > **Carries the result:** #2. *Cross-log causality is lost unless captured.* Two > separately-ordered logs have no "before" between them; every fix here is just a > different way of putting that lost order back — physically (one partition) or > logically (a version the consumer waits for). ## Environment Deterministic, so the verdict reproduces exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — no Docker, no deps - The log arrival order is modeled explicitly (the message log is delivered before the friendship log), so the run is fixed every time ## Mental model Two independent logs have **no shared order**, so a consumer that joins them can see an *effect* before its *cause*. There are two ways to put the order back. - **Buggy join (merge by arrival order)** — the friendship log and the message log arrive over independent transports. The consumer processes whatever lands first. The post lands first, so at the moment it processes the post, its view still says "alice and bob are friends" → it notifies Bob. - **Fix (a): one ordered partition** — route both the unfriend and the post for the (alice, bob) pair through a *single* partition. A single log has exactly one order; place the events in causal order (unfriend, then post) and the consumer is forced to apply the unfriend first → Alice has no friends → no notification. - **Fix (b): a causal reference the consumer waits on** — keep two logs and the *same* adversarial arrival order (post first), but stamp the post with the friend-list version it was written against (`2`, after the unfriend). The consumer *buffers* the post until it has applied friend-list version 2. The unfriend arrives, advances the version, and only then does the post get processed → no notification. All three run in one script, `code/causal_notification_leak.py`, against the identical facts; only how order is (or isn't) preserved differs. ## Setup ``` cd study/ddia/ch13/code python3 causal_notification_leak.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — the buggy join **Predict.** Alice unfriended Bob *before* posting. But the friendship log and the message log are independent, and the consumer merges them by arrival order — and the post arrives first. When the consumer processes the post, is Bob notified? **Observe.** ``` [buggy] one consumer joins both logs, merged by ARRIVAL order independent transport delivers the post before the unfriend: notification sent to ex (bob)? YES -- LEAK users notified about the post: bob ``` **Bob is notified — the leak fires.** At the instant the consumer handles the post, it has not yet seen the unfriend, so its view still lists Bob as Alice's friend. The notification goes out. The unfriend arrives one moment later, but the side effect is already irreversible. ### Step 2 — fix (a): one ordered partition **Predict.** Now both events for the (alice, bob) pair go through a *single* partition, in causal order: unfriend, then post. The consumer reads that one log top to bottom. Is Bob notified? **Observe.** ``` [fix a] route both events for the (alice, bob) pair through ONE ordered partition -> unfriend is delivered before the post: notification sent to ex (bob)? NO -- suppressed users notified about the post: (no one) ``` **No notification.** One partition means one order. The consumer applies the unfriend first — Bob leaves Alice's friend set — so when it reaches the post, there is no one to notify. The cause is physically forced ahead of the effect. ### Step 3 — fix (b): a causal reference the consumer waits on **Predict.** Two logs again, and the *same* bad arrival order — the post still lands first. But the post now carries `depends_on_friend_version=2`, and the consumer waits for that version before processing. Is Bob notified? **Observe.** ``` [fix b] two logs, SAME arrival order (post first), but the post carries depends_on_friend_version=2; the consumer waits for that version: notification sent to ex (bob)? NO -- suppressed users notified about the post: (no one) ``` **No notification — even though the post arrived first.** The consumer sees the post's required friend-list version (2), notices it has only applied version 1, and buffers the post. The unfriend arrives, advances Alice's friend-list version to 2 and removes Bob, and the consumer retries the buffered post: dependency satisfied, no friends to notify. The order was put back *logically*. ## What you should see - The buggy join **notifies Bob** — the post is processed before the unfriend. - Fix (a), one ordered partition, **suppresses** it — unfriend before post. - Fix (b), a causal reference the consumer waits on, **suppresses** it too — even though the post still arrives first. ## Why A real-world "A then B" is only preserved downstream if the system *records the dependency*. Alice's unfriend truly happened before her post, but that "before" lives only in Alice's head and in wall-clock time — neither of which the pipeline carries. The friendship log and the message log are ordered *internally* and not with respect to each other, so the pair of events forms an **antichain**: to the join there is no fact of the matter about which came first, and it is free to apply them in whatever order transport happens to deliver. The buggy consumer delivers the post first, evaluates "who are Alice's friends?" against a view that still contains Bob, and fires. Nothing is broken in the notification logic; the information needed to make the right call — *the post was written after Bob was removed* — was thrown away upstream, at the moment the two facts were split into two independently-ordered streams. Both fixes reintroduce the lost order; they differ in *how*. Fix (a) does it **physically**: send both events through one partition, and a single log's total order becomes the shared order the two facts lacked — the consumer *cannot* see the post before the unfriend because the log doesn't offer them in that order. Fix (b) does it **logically**: the post carries a version number naming the state it depends on, turning an invisible real-world "before" into an explicit datum the consumer can honor by *waiting*. The consumer buffers any event whose causal prerequisite it hasn't applied, so arrival order stops mattering — the post is processed against the correct, post-unfriend view no matter when it lands. One buys ordering by constraining routing; the other buys it by carrying metadata and paying a little latency (the buffer). > **The boundary — no two independent sources, no leak.** If both facts always > flow through *one* ordered stream, or the consumer is single-threaded over one > merged causal order, the reorder can't happen and there is nothing to fix — the > whole failure *needs* two independently-ordered sources joined without a > captured dependency between them. That is also why fix (a) works by collapsing > the two sources into one: remove the second order and the antichain disappears. ## Go deeper - **Version vectors instead of a single version.** A lone integer version works here because only Alice's friend list matters; with concurrent updates from many users you need per-writer bookkeeping to say what really happened-before what. See the Ch. 6 exercise [`version-vectors`](../ch06/version-vectors.html) — the same "capture causality with per-actor counters" idea that underlies fix (b). - **Watch a logical clock leak the same way.** The Ch. 10 exercise [`lamport-clock-leak`](../ch10/lamport-clock-leak.html) shows a Lamport timestamp *totally ordering* events that were actually concurrent — the dual failure to this one (imposing an order that wasn't there, versus dropping one that was). - **Total-order broadcast would also fix it — at a cost.** Push every event through one consensus-ordered log and *all* consumers see one agreed order, so no join can ever reorder anything. It closes this leak and every sibling of it, but it forces a global sequencer onto traffic that was happily partitioned — throughput and availability paid to buy an order most event pairs never needed.