Lesson 01 · Replication & staleness

The Replica Time Machine

You add a read replica to take load off the database. In three lines of config you have also added a machine that shows some of your users the past. Here is the bug that creates, what it is called, and what Facebook actually did about it.

The win in this lesson: you will be able to look at any architecture diagram with an arrow pointing at a replica and immediately ask the question that separates a reviewer from a spectator — "what happens when a user reads their own write?"

1. The move everyone makes first

Your single database is hot. CPU sits at 80%, reads are 95% of the traffic, and someone suggests the obvious: add a read replica. Writes go to the primary, reads go to the replica, load halves. This is correct, cheap, and the right first move. Nearly every system on this list did it before they did anything cleverer.

The cost is buried in one word in the docs: replication is asynchronous. The primary commits your write and tells you "done" before the replica has it. The gap between those two moments is replication lag. Usually milliseconds. Under a bulk update, a long-running query, or a network hiccup, seconds — and in the bad cases, minutes.

For most reads, nobody notices or cares. The feed is three seconds stale; so what. But there is one read where staleness is not a cosmetic issue — it is a bug report.

2. What replication actually is

Before going further: a replica is not a copy job. Nothing periodically dumps the database and ships it across. Replication is log following, and once you see that, every property in this lesson falls out of it.

Your database already writes every change to an ordered, durable log before it acknowledges a commit. PostgreSQL calls it the WAL — the write-ahead log — and that is the name this workspace will use. (Facebook's stack is MySQL, where the equivalent is the binary log; the mechanics below are the same shape.) The WAL exists for crash recovery: if the machine dies mid-transaction, the database replays the log on restart to get back to a correct state. Replication is the realisation that somebody else could replay that same log too.

Lag is a position, not a mood. The replica is always at some point in the log, and the distance to the primary's head is the whole problem. Every fix in this lesson is about not reading from the shaded region.

The replica opens a connection to the primary, streams that log, and replays each entry into its own copy, in order, forever. Four consequences, and each one matters later:

It is a stream, not a snapshot. The replica is always somewhere in the log. That position is a number you can query, which is what makes lag measurable — and what makes rung 3 of the ladder possible at all.
Order is preserved. The replica never applies entry 8 before entry 7. This is exactly why Facebook could embed cache invalidations inside the SQL statement: the delete becomes just another entry in the log, and an entry cannot overtake the one before it.
Nobody waits, by default. The primary commits and answers the client immediately. It does not check whether any replica has caught up. Lag exists precisely because nothing is blocking on it — that is the trade being made, silently, by the default configuration.
Replaying is real work. A burst of writes on the primary can be produced faster than a replica can apply it. So lag is worst exactly when traffic is heaviest — when you can least afford it.

Who waits for whom is the only real dial, and in Postgres it has a name: synchronous_commit. off — don't even wait for the local disk. local — wait for local flush, ignore replicas. remote_write — wait until a standby has written the commit record. on (the default) — wait until a standby has flushed it durably. remote_apply — wait until a standby has applied it, "so that it has become visible to queries on the standby". That last one is rung 4 of the ladder, and the quote is exactly why it costs what it costs. PostgreSQL 18, WAL configuration

How the stream actually works

"Stream" is doing real work in that sentence, so here it is concretely, in PostgreSQL 18 — the reference implementation for this workspace. The standby is configured with the primary's address (primary_conninfo) and opens a long-lived connection to it. Not a poll, not a file copy, not a cron job. The primary starts a walsender process for that connection, the standby runs a walreceiver, and WAL records flow down the socket as they are produced:

"The standby connects to the primary, which streams WAL records to the standby as they're generated, without waiting for the WAL file to be filled."
PostgreSQL 18 docs, Log-Shipping Standby Servers

The phrase "without waiting for the WAL file to be filled" is the whole upgrade. The older approach, file-based log shipping, ships a completed 16 MB WAL segment at a time — so your lag is however long it takes to fill 16 MB, which on a quiet system could be minutes. Streaming sends records as they are written, which the docs put at "typically under one second" assuming the standby can keep up.

Who starts it, and who pushes

Worth being exact, because the answer is "both, in that order". The standby dials out. The primary never initiates — it has no list of standbys to call. The connection is an ordinary libpq connection to primary_conninfo, carrying one special startup parameter:

"the frontend sends the replication parameter in the startup message. A Boolean value of true… tells the backend to go into physical replication walsender mode, wherein a small set of replication commands… can be issued instead of SQL statements."
PostgreSQL 18, Streaming Replication Protocol

The standby is drawn on the left because it is the one that dials — the primary has no list of standbys to call. Everything above the dashed line happens once, at startup. Everything below it repeats for the life of the connection, and note the direction: the primary pushes without being asked, and the only thing travelling back is the standby's acknowledgement of how far it has got. That acknowledgement is what synchronous_commit waits on.

standby → primary:  connect(primary_conninfo, replication=true)

  > IDENTIFY_SYSTEM
  < systemid | timeline | xlogpos | dbname

  > START_REPLICATION SLOT standby1 PHYSICAL 3/AF000000 TIMELINE 1
  < CopyBothResponse        -- from here the primary pushes, unasked

  < 'w'  XLogData        WAL bytes, whenever there are any
  < 'k'  keepalive       "still here" — may demand an immediate reply
  > 'r'  status update   written LSN | flushed LSN | applied LSN

The standby names its own starting position in START_REPLICATION — that is the entire "request for updates", and it is made exactly once. It knows the position from its own recovery state: it replays whatever is already sitting in pg_wal or the archive, then connects and asks for everything after that. After CopyBothResponse the primary pushes 'w' messages whenever WAL exists. Nothing polls. Nothing is requested per record.

This is also why SLOT matters. A replication slot "will be updated as replication progresses so that the server knows which WAL segments… are still needed by the standby." Without one, the primary is free to recycle WAL the standby has not consumed — and the standby reconnects to find its starting LSN no longer exists. A slot is the primary agreeing to hold the door open; the cost is that a standby that stays offline can fill the primary's disk.

The reverse stream is the one that matters here

The standby replies with 'r' status updates carrying three positions: the last WAL byte written, flushed, and applied on the standby. Those are the three positions in the diagram above — not an analogy, three Int64 fields in one message.

Which means synchronous_commit is not a different protocol. It is the primary declining to answer the client until that acknowledgement catches up: remote_write waits for field 1, on for field 2, remote_apply for field 3. Same stream, different patience.

And there is not one position on the standby but three, because arriving, being made durable, and being applied are separate steps:

Received — the bytes arrived and were flushed to the standby's disk. Safe from a crash, but not yet visible to anything.
Replayed — the records have been applied to the standby's data files. Now queries on the standby can see them.
And on the primary, the head of the log: everything committed so far.

The shaded band is the entire subject of this lesson. Read the right-hand rail downwards: it is the same timeline, marked with how far down it each synchronous_commit setting makes the primary wait before answering the client. Every step lower is a shorter lag window bought with a slower write — and remote_apply, the bottom rung, is the only one that closes the band entirely. One catch worth knowing before you reach for it: these levels only mean anything if you have actually named standbys in synchronous_standby_names. Leave it empty — as a default install does — and "remote_apply, remote_write and local all provide the same local synchronization level as on", which is to say: your replication is asynchronous and the band is wide open. PostgreSQL 18, WAL configuration.

Each is a LSN (log sequence number) — a byte position in the WAL, and the reason lag is a number you can query rather than a feeling:

-- on the primary: where the log head is right now
SELECT pg_current_wal_lsn();          -- e.g. 3/AF0001C8

-- on the standby: arrived vs. actually visible to queries
SELECT pg_last_wal_receive_lsn(),     -- received and flushed
       pg_last_wal_replay_lsn();      -- replayed — queries here can see it

-- lag, measured two ways
SELECT pg_wal_lsn_diff('3/AF0001C8', pg_last_wal_replay_lsn());  -- in bytes
SELECT now() - pg_last_xact_replay_timestamp();                  -- in time

This is rung 3, made concrete

Take pg_current_wal_lsn() right after a user's write, keep it in their session, and serve their reads from a standby only once its pg_last_wal_replay_lsn() has passed that value — otherwise send them to the primary. That is Facebook's remote marker with the position written down explicitly instead of compressed into a yes/no flag. Same idea, different currency.

Two things replication is not

Not a backup. It replicates your accidental DELETE FROM users faithfully and within milliseconds. A replica protects you from a dead machine, never from a bad statement.

Not sharding. Every replica holds the entire dataset — replication makes copies. Sharding splits the data so each machine holds a slice. Replication buys read capacity and survivability; only sharding buys write capacity and shrinks the working set. Different problem, later lesson.

3. The bug

The write is durable. The database is fine. Nothing is broken, crashed, or lost — and the user is still staring at the old name, wondering why your save button doesn't work.

What happens next is worse than the stale read itself. The user edits the field again. They hit save again. They file a ticket that says "profile changes don't stick", and you cannot reproduce it, because by the time you look, the replica has caught up.

Name the thing

Read-your-writes (also called read-after-write) is the guarantee that once a user has made a write, every subsequent read by that same user reflects it. Other users may keep seeing the old value — that is allowed and usually fine.

This is the whole trick, and it is why the problem is tractable: you do not need the system to be consistent. You need one user's next few reads to be consistent with their own writes. That is a far cheaper promise.

4. Your turn, before the reveal

The cheapest correct answer, and the one most teams ship: route that user's reads to the primary for a short window after they write. Stick a timestamp in their session; while it is younger than, say, ten seconds, their reads skip the replica. Everyone else keeps hitting the replica, so you keep almost all of the load reduction.

If you said "make replication synchronous" — that works too, and it is the expensive answer: every write now waits for the replica, so you have traded a latency increase on 100% of writes to fix a bug that affects a few reads. Keep that trade in your pocket; the interesting part of this lesson is watching Facebook refuse to make it.

5. What Facebook actually did

In 2013 Facebook published Scaling Memcache at Facebook at USENIX NSDI — one of the most useful systems papers ever written, precisely because it is not elegant. It is a record of what survived contact with a billion users.

Their shape is the one above, scaled up twice:

In front of MySQL sits memcache, used as a look-aside cache: on a read, the web server asks the cache first, and on a miss it reads "the database or other backend service" and populates the cache. It holds page data at enormous volume — trillions of items, and a p95 page load fetches 1,740 of them — plus anything else expensive to compute, down to "pre-computed results from sophisticated machine learning algorithms". The remote markers below are a tiny reuse of a cache that was already deployed everywhere, not the reason it exists.
Across the planet, one region holds the master databases; the others hold read-only replicas. Your write may have to cross an ocean; your read does not.

One person in Europe pressing Save, followed by the reload that would otherwise show them the old name. Steps 1–3 are the remote marker protocol exactly as §5 of the paper states it: flag the key, write to the master with the invalidations embedded in the SQL, drop the local copy. Step 5 is the part that is easy to get wrong — mcsqueal invalidates its own region only, because sending the delete straight to EU would beat the data across the ocean and the refill would re-cache the stale value. Step 6 is why that is safe: data and invalidations travel together down the replication stream, so the marker in step 7 disappears precisely when the local replica becomes trustworthy. Everything below the line exists to answer one question on a cache miss — is this region's copy still behind? — and the last arrow is the only one the user ever notices.

Wait — didn't step 3 already delete k?

It did, and step 7 deletes it again. That is not a contradiction; the two differ on scope and timing, and the paper is explicit that the first one is a shortcut:

"As an optimization, a web server that modifies data also sends invalidations to its own cluster to provide read-after-write semantics for a single user request and reduce the amount of time stale data is present in its local cache."
§4.1, Regional Invalidations

Scope: step 3 reaches only the cluster the web server happens to be sitting in. A region runs several frontend clusters, each caching its own copy of k. Step 7's mcsqueal "broadcasts these deletes to the memcache deployment in every frontend cluster in that region."

Timing: step 3 is inline with the request — milliseconds. Step 7 cannot arrive before replication does, which may be seconds. The user's next click will not wait, so you take the cheap narrow fix now and the authoritative wide one when it lands.

Deleting twice costs nothing, because deletes are idempotent — the same property from §2 that justified invalidating rather than updating. Redundancy here is free by construction, and it is routine: the paper measures that "only 4% of all deletes issued result in the actual invalidation of cached data."

And the question exposes a real gap. The marker is only consulted on a miss — a read asks memcache for k first, and a hit is served without ever looking at r_k. So a different cluster in the same region that still holds a stale k will serve it happily: step 3 never reached that cluster, and step 7 has not arrived yet. That window is not covered by the marker at all. It is part of what the authors mean when they say the system provides "best-effort eventual consistency".

Region, cluster, pool

Three words that sound like synonyms and are not. The geography matters, because "delete k in the local cluster" and "put r_k in the regional pool" are choices about how many copies exist and who can see them.

A region is a datacentre location. The paper: "Each region consists of a storage cluster and several frontend clusters." The storage cluster holds the databases — the master in one region, read-only replicas in the others. A frontend cluster is a self-contained unit of web servers plus its own memcached servers, and a region runs several of them.

Note the asymmetry the diagram is built to show: k exists three times, once per cluster, while r_k exists once for the whole region. That is not an accident — it is the reason step 3 of the marker protocol cannot finish the job, and the reason the marker works at all.

Why is k replicated per cluster? Because requests are spread randomly across clusters, so each one independently ends up caching roughly the same hot items — and that redundancy is useful:

"If users' requests are randomly routed to all available frontend clusters then the cached data will be roughly the same across all the frontend clusters. This allows us to take a cluster offline for maintenance without suffering from reduced hit rates."
§4.2, Regional Pools

Within a cluster, memcached servers are further split into pools by workload, because "different applications' workloads can produce negative interference resulting in decreased hit rates." The default pool is named wildcard; keys that would misbehave there get their own. §3.2.2, Memcache Pools

The cost of that redundancy is memory: every cluster paying to cache the same large, rarely-read item is waste. So for some data they give up replication and keep one copy per region — a regional pool, a set of memcached servers shared by all the frontend clusters. The trade is spelled out plainly: crossing a cluster boundary costs latency, and "our networks have 40% less average available bandwidth over cluster boundaries than within a single cluster."

Why this decides where the marker lives

A remote marker has to be visible to every web server in the region, because the user's next request may well land in a different cluster than the one that handled their write. Put r_k in a cluster's own memcache and it is invisible to the other clusters — the protection becomes a coin flip. The regional pool is the only placement where one write produces one marker that everybody sees. Meanwhile k stays replicated per cluster, because it is read constantly and the whole point is to serve it locally.

"For write requests, the web server issues SQL statements to the database and then sends a delete request to memcache that invalidates any stale data. We choose to delete cached data instead of updating it because deletes are idempotent."
§2, Scaling Memcache at Facebook, NSDI '13

mcsqueal is the invalidation daemon: one process on every database, which "inspects the SQL statements that its database commits, extracts any deletes, and broadcasts these deletes to the memcache deployment in every frontend cluster in that region" (§4.1). It does not contact memcached directly — that many databases talking to that many cache servers would be a packet storm — so it batches deletes and hands them to mcrouter instances in each cluster to unpack and route. Because the invalidations live inside committed SQL, a delete that was lost or misrouted can simply be replayed from the log. You know this pattern by another name: change data capture — read the commit log, emit events. Here it has exactly one consumer, the cache.

Now the problem doubles. A user in Europe writes to the master in the US, then reads locally. Their read can be stale for two independent reasons: the local replica has not received the change, and a miss against that stale replica would cheerfully cache the old value — freezing the staleness in place for everyone in the region.

The paper's fix is a remote marker. The steps, verbatim:

Reading the notation

k is a memcache key — the string the application makes up to name one cached value. Not a row id and not a table: something like user:1234:profile. The paper's own description of a read is "the web server… requests the value from memcache by providing a string key", and k stands for whichever key this particular write affects.

r_k is the remote marker belonging to k — a second, separate key derived from the first. The subscript is doing real work: there is one marker per key, not one flag per region. Only the handful of keys a user has just written get their reads diverted to the master; every other key in the region keeps reading locally, which is the entire reason this is affordable.

And r_k carries no useful value — its presence is the message: "this region's copy of k may still be behind, don't trust it yet." The two also live in different places: k in the per-cluster pools, r_k in the regional pool, so every cluster in the region can see the same marker.

"When a web server wishes to update data that affects a key k, that server (1) sets a remote marker r_k in the region, (2) performs the write to the master embedding k and r_k to be invalidated in the SQL statement, and (3) deletes k in the local cluster. On a subsequent request for k, a web server will be unable to find the cached data, check whether r_k exists, and direct its query to the master or local region depending on the presence of r_k."
§5, Across Regions: Consistency

The marker is a note that says "this region's copy of k may be behind — don't trust it yet." It is deleted by the replication stream itself, so it disappears exactly when the local data becomes trustworthy again.

Strip away the scale and this is the same idea you probably predicted: after you write, read from the source of truth for a while. Facebook's version is sharper in one respect — the "for a while" is not a guessed timeout. The marker rides the replication stream and is invalidated when the write itself lands locally, so the expensive path is used for precisely as long as it is needed and not one millisecond longer.

And if the user then reads from a third region?

Write from Europe, read from Asia. The marker was set in Europe's regional pool; Asia has its own, and it is empty. So Asia misses on k, finds no r_k, reads its own lagging replica, and serves the old value. If Asia happens to still hold a cached k it is worse — a hit, with no marker consulted at all.

The guarantee was always scoped to the region the write went through. The paper does not discuss users moving between regions, so this is a reading of the mechanism rather than a documented case — but it follows directly from where the marker lives. In practice users are routed to a region by geography, which is the stated reason for multiple regions at all, so the failure needs someone to cross continents within the replication-lag window. Rare enough to price in. And covering it properly would mean writing a marker into every region on every write, forever, which runs straight into the paper's stated posture: "Most ideas that provide stricter semantics rarely leave the design phase because they become prohibitively expensive."

The structural lesson is worth more than the case. A remote marker is state stored in the infrastructure, keyed by data — it sits where it was written and cannot follow anybody. A token is state carried by the client, keyed by the user: put the write's LSN in their session or cookie and it travels with them, so any region can compare it against its own replay position and route accordingly. Same rung of the ladder, opposite placement of the state — and that placement is exactly what decides whether the guarantee survives the user moving. The design-review question to keep: where does this state live, and what happens when the user isn't where it is?

6. The sentence to steal

This is the part that matters for design review. Immediately after describing the mechanism, the authors write down its price:

"In this situation, we explicitly trade additional latency when there is a cache miss, for a decreased probability of reading stale data."
§5, Across Regions: Consistency

Read that again with an editor's eye. "Explicitly trade." "Decreased probability." Not "solves", not "guarantees", not "ensures consistency". And the paper goes further, volunteering its own failure case: concurrent modifications to the same key can delete a marker that should have stayed, and a stale read slips through. They measured it, decided it was rare, and shipped it.

The tech-lead move

Every mechanism buys something and costs something. The engineer describes the mechanism. The tech lead says the price and the residual risk in the same breath. Steal the template literally: "We explicitly trade ⟨cost⟩ for ⟨reduction in badness⟩, and it still fails when ⟨case⟩ — which we think is rare because ⟨evidence⟩." Use it in your next design doc and watch how differently the conversation goes.

7. The ladder of fixes

Four rungs, cheapest first. Pick the lowest one that clears your actual requirement — the full cheat sheet lives in the staleness playbook.

Fix	What you pay	Reach for it when
1. Don't read render what the client just wrote	Client complexity; lies if the write silently failed	The UI already has the value. Cheapest possible fix.
2. Sticky-to-primary after a write, route that user to the primary for N seconds	A slice of read traffic back on the primary; N is a guess	Default answer for a single-region app. Ship this.
3. Marker or token Facebook's r_k; or carry a write position and only read a replica that has caught up to it	Real plumbing; a per-key or per-session side-channel	Many replicas or many regions, and N-seconds is too blunt.
4. Synchronous replication the write isn't done until a replica has it	Latency on every write, forever; availability drops when a replica is sick	Correctness genuinely outranks write latency. Rarely.

8. Check yourself

Close the page above this line if you can. Retrieval that costs you something is what turns this from "read an interesting thing" into "know an interesting thing".

9. Back to your world

Most systems run a single database, which means most systems do not have this bug — and being able to say that out loud in a planning meeting, rather than cargo-culting a fix for a problem you do not have, is itself the skill. But the shape arrives long before a replica does. Anywhere a write is followed by a re-fetch to display the result, you are one caching layer, one CDN rule, or one read replica away from exactly this. The question to keep in your pocket: after this write, what is the very next read, and where does it land?

Ask me things. I am your teacher for this, not just the author of the page. Good things to push on: "what is an LSN and how does rung 3 actually work?" · "why is caching a stale read worse than serving one?" · "which write paths in a system like mine would break first?" · "I don't buy that read-your-writes is enough — grill me on it."