Caches & Databases: Read-Your-Writes Coherence

A user on your marketplace renames their restaurant to "Ana's Kitchen", hits Save, reloads — and there's the old name, staring back at them. You know this bug. You spent all of Read Replicas & Replication Lag on it: the write landed on the leader, the read was routed to a copy that hadn't heard yet.

Except this time you check the architecture diagram, and there's no replica on it. One app, one database, and the little Redis box you added back in the caching section, in an afternoon, to take load off the hot reads.

That box is the replica. A cache in front of a database holds a second copy of the data and serves reads from it — which is the definition of a read replica, minus one thing: Postgres replicas have a replication protocol, a WAL stream, lag you can measure in pg_stat_replication. Your cache's replication protocol is whatever your code remembers to do after each write. Denormalization called this rung of the ladder precisely: a copy in a different system that nobody syncs. You became a replication engineer the day you added the cache. You just never wrote down the contract.

In this lesson: the guarantee this bug violates (it has a name and a 1994 paper), why "just keep them in sync" is not on the menu, the three contracts a read can actually have, the machinery that delivers each — up to what Facebook runs at a billion reads a second — and the trap where two correct answers compose into one wrong system, which served stale data to 40% of GitHub for an afternoon last year.

Scope: HOW to invalidate — TTLs, delete-on-write, the stale-set race and its cures — is C1's Cache Invalidation: The Second-Hardest Problem, and the four cache wirings are Caching Patterns: Cache-Aside, Read-Through, Write-Through, Write-Behind. We build on both. This lesson owns the question they left open: what did you promise each read, and what does keeping that promise cost?

What the renaming user expects is modest. Not "everyone sees my edit instantly" — they can't check that, and mostly don't care. Just: I saved it, so I should see it.

That guarantee has a name and a birth certificate: read-your-writes, defined in Terry et al.'s 1994 Bayou paper on session guarantees. Their definition is worth reading exactly, because every word is load-bearing: "If Read R follows Write W in a session and R is performed at server S at time t, then W is included in DB(S,t)." A session is one application's sequence of reads and writes — one user, one browser, one flow. (You met the formal family in The Consistency Spectrum; this lesson puts one member of it to work.)

Notice what the definition does not say: nothing about other users, nothing about all servers, nothing about "instantly". And that restraint is the whole economics of this lesson. The paper is explicit about why: enforcing a guarantee restricts which servers a session may use, so scoping it per-session means "requests for one or more of the guarantees within a session have no affect on the availability seen by applications that are using other sessions."

Read that again with your cache on your mind. You do not have to make the cache consistent — a global, expensive, races-all-the-way-down project. You have to make it consistent for the one person who just wrote, for the few seconds it matters. Everyone else keeps their fast, possibly-slightly-stale read, and that's not a compromise — it's the design. This is the same move Read Replicas & Replication Lag made with its per-read routing question (can this read tolerate stale data?), now pointed at a copy you own.

The tempting alternative is to make the problem disappear: every write updates the database and the cache, atomically, always. Then there's no staleness and no contract to think about.

You can't, and it's worth being precise about why: the database and the cache are two systems with no shared transaction. There is no BEGIN that spans Postgres and Redis. Whatever order you pick, there is a moment where one has the write and the other doesn't — and a crash, a timeout, or a concurrent reader can freeze that moment into the cache. This is the dual-write problem, and it is the reason C1's invalidation lesson is a catalog of workarounds rather than one answer: TTL bounds how long the moment can last; delete-on-write shrinks it to a window; change-data-capture replays the database's own log to close it. All three make the cache converge on the truth.

But look at what the renaming user needed: not convergence — convergence is about eventually. They needed a guarantee about one specific read, right now. That's the gap this lesson lives in: convergence is a property of the system; a contract is a promise to a read. C1§8 gave you convergence. Nothing so far has given any particular read a promise.

So write the contract. Every read your product serves fits one of three promises, and the whole craft of caching-with-a-database is putting each read in the right row — because each row down costs more.

Two things make this table sharper than it looks.

First: the rows are about reads, not tables. The same users row can appear in all three — your name on a leaderboard is row one, your name on your own settings page is row two, your is_admin flag during an authorization check is row three. The contract attaches to the read path, which is why no cache-wide setting can express it.

Second: row three is not cowardice. Serving a stale balance isn't slow, it's wrong — a correctness bug wearing a performance optimization's clothes. GitHub's March 2026 incident, coming up below, was exactly a row-three read (permissions) being treated like row one. When someone says "cache everything, invalidate carefully," the answer is this table.

Row two is where the engineering lives. The writer is watching; everyone else isn't. Cheapest first:

Bypass the cache after your own write. After a session writes, route that session's reads for the affected keys straight to the database for a grace window (or keep a small per-session set of "dirty" keys). Crude, effective, ships in an afternoon. Bill: the writer's next few reads lose the cache; a session store carries a little state.

Refill from the truth. Delete-on-write already drops the stale entry (database first, then delete — C1§8's rule). The refill decides everything: if the next read repopulates from the primary, we measured RYW holding on a real redis+postgres pair — write Ana!, DEL, miss, refill → Ana!, fresh. Hold that thought: where the refill reads from is about to become the whole trap.

Carry a marker. The precise fix, and you already know it — it's Read Replicas & Replication Lag's wait-for-LSN wearing a cache costume. On write: store a tiny marker next to the cache — marker:user:42 = <commit LSN> — and delete the key. On a miss: if a marker exists, compare it to the replica's pg_last_wal_replay_lsn(). Replica behind the marker? Refill from the primary. Caught up? Marker's job is done; back to the cheap path. Four commands, measured working through a live lag spike in the capture below. The marker is the contract made mechanical: this key had a recent write; prove you're past it before serving a copy.

Same idea, three systems now: wait-for-LSN for replicas, this marker for your cache — and, next section, the same trick running at a billion reads per second since 2013.

Facebook's memcache deployment — the NSDI '13 paper is the production text on this problem — serves over a billion reads per second; loading one popular page fetches ~521 distinct cached items. At that scale they hit our exact problem with geography attached: a user in a non-master region writes (the write goes to the master region's database), and their local database replica won't hear about it for a while. Their own next read would land on the local copy. Vanishing write, continental edition.

Their fix is called a remote marker, and you will recognize it instantly. On a write to key k in a replica region: set a marker rk in the regional cache, send the write to the master, delete k locally. On the next read: miss → check rk → "the presence of a marker indicates that data in the replica is stale and the query is redirected to the master region" — pay the cross-country round trip, read the truth. The replication stream deletes rk when the write finally arrives locally. The paper's own accounting: this "trades additional latency for reduced probability of reading stale data" — and only for the keys that were just written, only until replication catches up. Terry et al.'s per-session economics, industrialized.

Two decades in, the sequel is telling. In 2022 Meta published how they pushed TAO's cache consistency from six nines to ten nines — fewer than one stale read per ten billion — and the headline wasn't a new protocol. It was observability: a service called Polaris that pretends to be a cache server, receives every invalidation event, and then checks the actual replicas against the one invariant that matters — cache should eventually match the database. Their bug stories explain why that's the design: one hunt ended at an error handler whose drop_cache(key, version) refused to drop a stale item because the item already carried the newest version number. Every component correct; the composition wrong. You cannot review your way to ten nines — you measure the invariant in production and let the violations page you.

And the stakes, from their own writeup: a run of inconsistent cache reads made two clients disagree about where a user's messages lived, and "neither region/store had a complete copy of Alice's messages." Stale caches don't just show old numbers. They make systems act on different worlds.

Now the section's two big tools meet, and they interfere.

You run delete-on-write, database-first — correct, straight from C1§8. You also scaled reads with a replica pool, so read traffic — including cache refills — goes to replicas. Also correct, straight from The Read-Scaling Playbook. Watch what they do together, verbatim from a live redis + postgres primary + streaming replica (replay paused to simulate the lag spike Read Replicas & Replication Lag measured under real load):

UPDATE 'Anna' on primary (commit lsn 0/30001E8) + DEL cache   <- both textbook-correct
next read: miss -> refill from the REPLICA:
    replica returned: Ana!            <- the OLD value
    redis GET -> Ana!   TTL 60s
replay resumed. replica now: Anna
the DATABASE has healed everywhere. the cache:
    redis GET -> Ana!   TTL 59s       <- STALE FOR THE WHOLE TTL

Your delete worked. That's the cruel part — the delete caused the miss, the miss refilled from a copy that hadn't heard yet, and the stale value went back in with a brand-new TTL. A replica lag of one second was just promoted into a cache staleness of sixty — or of forever, if that key has no TTL. (You've seen this shape before: it's C1§8's stale-set race, except the "slow reader" holding an old value is the database's own replica.)

This is not a lab curiosity. On March 3, 2026, a GitHub deployment made exactly this mistake — the cache-rebuild path read from replicas that were lagging under production load — and for ~83 minutes (18:46–20:09 UTC), 40% of github.com requests and 43% of API calls served stale data, permissions included, with Copilot erroring at ~21%. The fix that day was a rollback; the remediation was a killswitch and monitoring on the cache path. Their availability report reads like this section.

The escapes, in order of bluntness: refill from the primary (simple; misses now load the primary); re-invalidate after a delay longer than your worst expected lag (cheap, probabilistic); or the marker — the refill compares the write's LSN to the replica's replay position and routes accordingly, which is exactly the four-command capture from two sections ago. Pick by how much correctness the read's row in the contract table demands.

Below is this lesson as a control panel. Three scenarios — a profile name (the writer is watching), a feed count (nobody owns it), a balance (no one may see it stale) — and five contract mechanisms. Type a name, save it, reload as yourself, read as a stranger. Then do the real experiment: pick delete-on-write, refill from replica, flip the 🔥 lag spike, save, and reload — you'll watch the database heal while the cache keeps lying, exactly like the capture. Switch to the marker and run it again. And check the verdicts as you go: the widget doesn't just fail wrong answers — it flags over-buying (a marker on a like-count is machinery nobody asked for). The cheapest contract that survives the scenario is the correct one.

The strongest argument against everything above is that most of the industry ships "TTL and move on" — and mostly gets away with it. Take that seriously: for row-one reads it isn't negligence, it is the contract. Bounded staleness on a like-count is priced correctly at zero machinery. If your product is all feeds and catalogs, this lesson's kit stays in the drawer, and that's a win.

The honest costs of going further:

• Session machinery has moving parts. Bypass windows, dirty-key sets, markers — each is state that can itself be wrong, and each moves some misses to the primary. Meta ran markers for a decade and still needed Polaris to see the truth; coherence machinery is expensive to run, not just to write.
• Some reads shouldn't be in a cache at all — and saying so is an architecture decision, not a failure. Balance, permissions, auth: read the truth and make the query fast. A sub-millisecond indexed read (Indexes Deep-Dive measured 0.053 ms) needs no cache to be fast.
• When you do cache and it matters, monitor the invariant, not the code. A tiny Polaris — a sampler that compares cache entries to the database and counts violations per million — turns "probably fine" into a number. GitHub's remediation was precisely this plus a killswitch.

What you'd say under follow-up: "Per read, I'd ask who observes it. Nobody → TTL. The writer → read-your-writes machinery: bypass-after-write, or a version marker checked on refill — and refills must never read a laggier copy than the marker allows, or replica lag gets promoted into a full TTL of staleness. Everyone → don't cache it; make the query fast. And I'd sample cache-vs-database disagreement in prod, because this failure mode is silent by construction."

Everything below ran for real (docker + psql + redis-cli); your values will match. The spine:

1. The rig — redis, a postgres primary, and a streaming replica:

docker network create cohnet
docker run -d --name pgp --network cohnet -e POSTGRES_PASSWORD=pw postgres:16
docker run -d --name rds --network cohnet redis:7-alpine
# seed: CREATE TABLE users(id int PRIMARY KEY, display_name text); INSERT (42,'Anastasia')
# replica: pg_basebackup -h pgp -R into a second container, chmod 700 the datadir, pg_ctl start

2. Break read-your-writes (cache-aside + TTL, no invalidation). Warm the cache, rename in the database, reload:

redis GET user:42:name -> Anastasia
UPDATE users SET display_name='Ana' ...   -- primary now: Ana
redis GET user:42:name -> Anastasia        <- THEIR OWN WRITE, GONE
TTL remaining: 60s of staleness ahead

3. Reproduce GitHub's incident. Pause the replica (SELECT pg_wal_replay_pause()), then do everything right — UPDATE then DEL — and let the refill read the replica:

replica returned: Ana!                    <- old
redis GET -> Ana!   TTL 60s
-- resume replay; replica catches up to 'Anna'
redis GET -> Ana!   TTL 59s               <- DB healed, cache stale for the whole TTL

4. Fix it with a marker. Predict first: which way does the LSN comparison come back while the replica is paused?

SET marker:user:42 = 0/3000260  (the commit LSN) ; DEL user:42:name
-- next miss:  replica replay_lsn >= marker lsn?  f
--   -> refill from PRIMARY: redis GET -> Annushka   <- fresh, THROUGH the lag
-- after catch-up: replay_lsn >= marker?  t -> DEL marker

That f is the entire mechanism: the marker carries the write's position, pg_last_wal_replay_lsn() says whether the replica is past it, and the refill routes accordingly. You've now run Facebook's remote marker on your laptop.

5. Clean up: docker rm -f pgp pgr rds && docker network rm cohnet

Step back and look at the shape of everything in this lesson: writes go to one model (the database, guarded, normalized), reads come from another (the cache, fast, denormalized, allowed its own schedule), and machinery in between decides how quickly the read model must reflect the write model. That architecture has a name: CQRS — Fowler: "you can use a different model to update information than the model you use to read information." A cache-in-front-of-a-database is CQRS in casual clothes; systems that take the split seriously make the read model explicit and feed it from the write model's changes. Fowler's caution travels with the name — for most systems it "can add significant complexity" — and the full treatment (where it shines, where it hurts) belongs to the event-driven architectures of Production Systems (C4). For now, keep the lens: every cache is a small, informal read model, and this lesson's contract table is its service-level agreement.

• "Read-your-writes means everyone sees fresh data." It's a session guarantee — Terry et al.'s definition binds a read to the writes of its own session. Other users seeing a slightly older value is allowed, normal, and exactly why the guarantee is affordable.
• "A short TTL is basically consistent." For the writer it's binary: within that window they watch their own edit vanish (measured: 60 s of Anastasia after the database said Ana). TTL bounds staleness; it cannot deliver read-your-writes.
• "Delete-on-write keeps reads fresh." It empties the seat; it doesn't choose who sits down next. If the refill reads a lagging replica, your correct delete installs stale data with a full TTL — the GitHub failure mode, reproduced above.
• "Redis is consistent, so my cache is fine." Each Redis operation is atomic — and irrelevant. The system your user reads is cache + database, two systems with no shared transaction; coherence is a property of the pair.
• "Write the new value into the cache on update, then it's never stale." Two writers race and the loser's value sticks — C1§8's rule stands: delete, don't update. This lesson doesn't repeal it; it adds the refill-source rule on top.
• "Cache everything; invalidate carefully." Meta runs remote markers and still needed a dedicated service to verify the invariant at ten nines. Permissions, balances, and auth don't belong in the cache at any level of care — stale there is a correctness bug, not a slowdown.
• "The cache broke it." The cache did nothing wrong. A read was served by a copy whose contract nobody chose. Same bug class as the replica's vanishing write; same fix shape: route, mark, or wait.

• A cache in front of a database is an async replica you sync yourself — its replication protocol is your invalidation code. The vanishing write returns with no replica in the diagram (measured: cache Anastasia, truth Ana, 60 s to go).
• Coherence is a contract per read, not a setting per system. Three rows: bounded staleness (TTL — feeds, counts), read-your-writes (the writer is watching — profile, cart), no-staleness-ever (don't cache — balance, permissions, auth). The cheapest surviving row is the correct one, in both directions: under-buying breaks users, over-buying breaks budgets.
• RYW is bought per session (Terry et al., 1994): bypass-after-write, dirty keys, or a marker — the write's LSN stored beside the cache, compared to the replica's replay position on refill. One idea, three systems: wait-for-LSN (replicas) ≙ your marker (Redis) ≙ Facebook's remote marker (a billion reads/s since 2013).
• The refill is the weak point. Correct delete + lagging-replica refill = bounded lag promoted to a full TTL of staleness (GitHub, 2026-03-03: 40% of requests, ~83 minutes). Refill from the primary, delay-and-reinvalidate, or gate on the marker.
• Verify the invariant, not the code — Meta reached ten nines with observability (Polaris), not a cleverer protocol. Sample cache-vs-truth disagreement; add a killswitch.
• Every cache is an informal CQRS read model (full story in Production Systems). Next — the Scaling Reads checkpoint: three slow-read cases, and every wrong answer is a trap this section taught you to name.