I shipped cache stampede protection. Then I read how Facebook solved the same problem at a billion requests a second.
At SurgeGrowth I built a caching layer to stop us paying for the same scrape twice.
The idea was simple. We pulled Facebook Ad Library data through a paid third-party scraper, and the same advertiser page kept getting fetched over and over different users, syncs, retries each one a fresh charge. So I used leader election: the first request for a page wins, pays for the scrape, fills the cache. Everyone else concurrent waits and piggybacks on that single result instead of triggering their own.
Cut the bill ~70%. I shipped it. I moved on.
Then I wanted to see how the people who operate this at a scale I'll probably never touch had solved the same problem. That's how I ended up in Scaling Memcache at Facebook (Nishtala et al., NSDI '13).
I expected to nod along and confirm I'd done it "right."
Instead the paper showed me something more useful than validation: my solution and theirs start from the same idea, but their scale pushed that idea somewhere mine never had to go. And then it kept going because stampedes turn out to be the easy problem. The paper isn't really about caching. It's about everything caching breaks once you put it in front of a billion users.
This is me reconstructing how that understanding built up, decision by decision. I'm going to keep asking the same question the authors clearly kept asking themselves: what breaks if we don't do this? Because once you see what breaks, every decision in the paper stops looking clever and starts looking inevitable.
What made this paper inevitable
Start with the number that forces everything else.
One Facebook page load fetches, on average, 521 distinct items from the cache. The 95th percentile is 1,740.
Sit with that. Not 521 rows from one query. 521 separate lookups, often spread across hundreds of machines, to render a single page.
Now imagine those lookups going to MySQL instead. The paper says it plainly: a feature that issues hundreds of database queries per page "would likely never leave the prototype stage because it would be too slow and expensive."
That's the whole tension. The product Facebook wants to build rich, aggregated, real-time pages is computationally impossible on databases alone. Not slow. Impossible. The database is the wrong tool for a read pattern this wide.
So a cache isn't an optimization here. It's the thing that makes the product exist at all.
one page render
|
v
~521 lookups ──► MySQL? ──► too slow, too expensive ──► product dies
|
└─────────► in-memory cache (~333µs each) ──► product is possible
And the workload has one more property that quietly decides every design choice downstream: users consume far more than they create. Reads vastly outnumber writes. Hold onto that. It's the assumption the entire paper is secretly resting on and the moment it's true, a cache-heavy design isn't just viable, it's obvious.
So the paper exists because read fan-out at social-network scale drowns databases, and reads outnumber writes badly enough that caching the reads is the natural escape. Everything from here is the consequence.
The first decision that isn't obvious: delete, don't update
Memcache is a look-aside cache. The pattern is the one you've seen:
The read path is unsurprising. The write path has a choice in it that I would have gotten wrong.
On a write, you change the database and then you delete the key from the cache. You don't update it with the new value. That feels wasteful. You have the new value right there; why throw it away and force the next reader to miss and refetch?
Because delete is idempotent, and update is not.
If two writes race and you're updating the cache, the order matters the slower write can land last and leave a stale value sitting in the cache forever. If you're deleting, order doesn't matter. Two deletes, ten deletes, deletes that arrive out of order the result is identical: the key is gone, and the next read refills it from the source of truth. A delete can't be "stale." An update can.
This is the first appearance of a theme that runs through the entire paper: the cache is never the authority. It's allowed to be empty, allowed to be wrong, allowed to be evicted. The database owns the truth. The cache is a disposable accelerator. Every later decision leans on that being true.
Once you accept "the cache is disposable," delete-don't-update isn't clever. It's the only choice that stays correct under races.
Leases : the decision I'd already half-made
Here's where I met my own code in someone else's paper.
The problem Facebook calls a thundering herd: a hot key gets invalidated, and before any single request can refill it, a flood of other requests all miss simultaneously and all fall through to the expensive thing behind the cache. For Facebook that's the database. For me it was a paid scraper .
That's exactly the problem I'd solved at SurgeGrowth. And their mechanism rhymes with mine. Two requests for the same advertiser page landed 40ms apart, and the second one still piggybacked onto the first's scrape instead of firing its own. N near-simultaneous misses on one hot key, collapsed into a single fetch.
A memcached instance hands out a lease on a miss a 64-bit token tied to that specific key. The client takes its token, fetches from the DB, and presents the token when it sets the value back. The server only accepts the set if the token is still valid. Late clients that miss within the window get told "wait a moment and retry," and by the time they retry, the winner has usually already filled the cache.
N misses collapse into 1 fetch. That's my leader election, give or take a primitive. I felt good reading it. hehe 😎
Then I hit the sentence that took the air out of it.
Leases solve two problems. The herd is the one I knew about. The other is the stale set and the token kills it for free, because any delete on that key invalidates the outstanding lease. So if a write lands while a slow reader is still holding a token from before that write, the reader's set gets rejected. The stale value can't overwrite the fresh one.
So I went back to my own design with fresh eyes. My leader election targets the stampede one fetcher wins, the rest wait. That was the problem in front of me, and it's the half the lease and I both solve. The stale set the second thing the lease quietly handles I'd addressed separately: TTLs and careful ordering of when I read versus when I cache. Two facets, two mechanisms.
That's the real divergence. My version keeps the two concerns separate because, at my scale, a separate freshness story is cheap to reason about. Facebook folds both into a single primitive because at their scale every extra moving part is one more thing to get wrong one token that arbitrates writes and collapses the herd is fewer seams than two systems doing one job each.
Same idea. Theirs is more general, because it had to be.
And the throttle detail is worth keeping: tokens are rate-limited to one per key every 10 seconds. That's not free correctness it's a deliberate choice to sometimes hand back slightly stale data rather than let a hot key generate a fetch storm. First sighting of the paper's real worldview, which we'll come back to: staleness is a dial, not a bug. The payoff is concrete on herd-prone keys, this took the database query rate from 17,000/s down to 1,300/s.
Scaling out, and the confusion that taught me the most
So one cache server isn't enough. You run hundreds per cluster and spread the keys across them with consistent hashing. Fine.
Here's where I had it backwards, and it's worth showing the wrong model because the right one is the whole point.
I read "a web server talks to many memcached servers per request" and my brain filled in: the data must be replicated across all of them, so any server can answer.
Wrong. Backwards, actually.
There is no replication by default. Consistent hashing puts each key on exactly one server. The data is sharded spread out not copied. So why does one request touch hundreds of servers?
Because of the 521. One page needs 521 different keys, and those keys hash to ~hundreds of different machines. The web server has to ask server A for key 1, server B for key 2, server C for key 3, and so on. The fan-out isn't redundancy. It's the cost of having spread the data out in the first place.
web server building one page
|
┌────┼────┬────┬─────────────┬────┐
v v v v v v
mc1 mc2 mc3 mc4 ... mc299 mc300 ← each holds a DIFFERENT slice
k1 k2 k3 k4 k520 k521
"many servers per request" = data is SCATTERED, not copied
Once that flips in your head, a new problem falls out of it immediately, and it's a nasty one.
Every web server talks to (nearly) every cache server in a short window. That's an all-to-all communication pattern. And when one web server fires off ~300 parallel gets, ~300 responses come back at almost the same instant and converge on the one switch port leading to it. The buffer overflows. Packets drop. This is incast congestion many senders, one receiver, one synchronized burst.
300 servers all reply at once
\ | | | /
\ | | | /
v v v v v
┌───────────────┐
│ switch port │ ← buffer overflows → drops → retransmits → latency spike
└───────────────┘
|
v
web server
(Quick aside, because I confused these myself: incast is not backpressure. Incast is the problem the many-to-one burst. Backpressure is a fix a signal telling senders to slow down. Memcache's sliding-window flow control, which caps how many requests are outstanding at once, is a form of backpressure applied to the incast problem.)
So sharding gives you capacity but hands you incast. Hold that thought, because the fix for incast is going to collide with something else 🤓.
"Replication" three times, meaning the opposite thing each time
This is the part that looked like a contradiction until I forced myself to be precise about which replication I was talking about.
The paper says replication wastes memory. The paper also builds multiple replicated clusters and replicated databases. Both are true, because "replication" happens at three levels and they make the opposite call at each one.
So the same word, three times, opposite decision. At the fine grain (per key) replication is wasteful, so they refuse it. At the coarse grain (per cluster, per region) replication buys failure isolation, lower latency, and crucially it's how they fix incast: split the giant pool into clusters so each web server only fans out across its cluster, bounding the burst.
The way I now hold it: it's not "replicate or don't." It's at what granularity does replication's benefit start to outweigh its cost? Fine grain, no. Coarse grain, yes. (**That framing is mine, not the paper's the paper states each trade separately; I'm the one collapsing them into one axis.)
And notice what just happened. The incast fix (split into clusters) is level-2 replication. The thing they refused at level 1 to save memory, they pay for at level 2 to fix the problem level-1 sharding created. Every fix has a bill, and the bill shows up one level out.
Failure: the clever move is the wrong move
A few cache servers die. What happens?
Normally, their share of requests now misses and falls through to the database. A few dead cache boxes can turn into a database overload. So you need a plan.
The obvious plan: rehash the dead server's keys onto the survivors. Spread the orphaned load around.
The paper explicitly rejects this, and the reason is sharp enough that it reframed how I think about failover.
One key can be 20% of a server's traffic. If that hot key's server dies and you rehash it onto a surviving server, that server already busy now eats a 20% spike and may fall over too. Which rehashes again onto the next server. You've built a cascading failure out of your recovery mechanism.
So instead they use gutter: a small pool of idle standby cache servers, about 1% of the cluster. On no-reply, the client retries against gutter, not against the survivors.
The distinction that matters: gutter is a cache, not a database. It's disposable, short-TTL, holds copies.
The backing store(aka:the DB) is the authority. People conflate "the thing requests fall back to" but gutter is a catch-net in front of the backing store, built specifically so failures don't become database load. It converts would-be DB hits back into cache hits and cuts client-visible failures by 99%.
Rehashing optimizes for using your existing capacity. Gutter optimizes for not cascading. At scale the second one matters more so shunting load to idle boxes, which looks wasteful, is actually the only choice that doesn't risk taking the whole cluster down. Inevitable, once you see the cascade.
(And gutter accepts slightly stale data with its short TTLs there's the staleness dial again, turned knowingly.)
Who keeps all these caches in sync? Nobody.
By now there are multiple clusters, each independently caching. My instinct said: there must be a leader. Some coordinator keeping the caches consistent.
There isn't. And the absence of a leader is the design.
Two facts from the paper. Memcached servers "provide no server-to-server coordination." And "each cluster independently caches data depending on the mix of the user requests that are sent to it." The caches don't talk to each other and don't answer to a coordinator.
So what stops cluster 1 from serving a stale value after cluster 2 processes a write? Not a leader the invalidation pipeline, hung off the one thing that's already authoritative: the database's commit log.
write commits to MySQL
|
v
mcsqueal (daemon tailing the commit log)
|
v
mcrouter (batches + routes)
|
v
memcached in EVERY frontend cluster ──► DELETE the key
A daemon called mcsqueal reads the database's commit log, extracts the deletes, and broadcasts them to every frontend cluster in the region. The commit log which already exists, already reliable, already the source of truth becomes the coordination mechanism. No cluster is in charge. Each one just gets told "drop this key."
Why off the log instead of having web servers broadcast invalidations directly? Because the log is durable and replayable. If a delete is lost or misrouted, mcsqueal can replay it. A web-server broadcast is fire-and-forget lose it and you have a permanently stale key with no recourse.
A leader would have been a coordinator to elect, a consensus to run, a bottleneck to scale. By refusing one and leaning on the commit log instead, every cluster stays independent which is exactly why the system scales horizontally. The absence is the architecture.
(Two numbers that show how much engineering hides in "broadcast a delete": batching deletes gives an 18× improvement in deletes-per-packet, and only 4% of all deletes actually invalidate cached data the other 96% are keys nobody had cached. They built a whole reliable pipeline knowing most of its traffic does nothing, because the 4% that matters, matters.)
Across regions, the bill comes due as consistency
One region holds the master databases. Other regions hold read-only replicas, kept current by MySQL replication. Web servers read from their local replica for speed.
And replicas lag.
That's the core cross-region problem, and it produces the one mechanism I found genuinely subtle: cold cluster warmup which, read carefully, is the paper proving its own architecture to you.
When a cluster comes up cold (empty cache, ~0% hit rate), it can't shield the backend. The obvious fix is to refill it from the database. They don't. They refill it from a warm sibling cluster "rather than the persistent storage."
Read that again with the earlier questions in mind. A cold cluster warms itself from another cache. That's only possible because the cache is a shared, decoupled, peer layer not something welded to a particular database. If you'd coupled each cache to its own DB replica, there'd be no peer cache to pull from, and warming would mean slamming a replica with the entire working set at once the exact load spike caches exist to prevent. Warming cache-to-cache is RAM-to-RAM. Days become hours.
But and this is the paper being honest about its own seams warming from a peer cache opens a consistency race:
cold-cluster client writes the DB
|
v
another client reads the still-stale value from the WARM cluster
| (before the warm cluster received the invalidation)
v
cold cluster caches the stale value → indefinitely inconsistent
Their patch is a two-second hold-off: after a delete, the cold cluster rejects add operations for two seconds, so a fresh write can't be clobbered by an in-flight stale fill. And they say the quiet part out loud: "the operational benefits of cold cluster warmup far outweigh the cost of rare cache consistency issues."
This is the motif at full volume. The decoupling that makes cheap cache-to-cache warmup possible is the same decoupling that creates the staleness race. Every scaling win arrives married to a consistency bill, and they pay it with a small, bounded, good-enough mechanism rather than a heavy correctness guarantee.
Which is the thing I actually came away chewing on.
The line I'm still chewing on: simplicity over perfection
The paper's stated lessons are short. One of them is "simplicity is vital." Another way they keep phrasing it: they'll take cheap-and-mostly-right over expensive-and-perfect, every time.
When I first read that, it scratched against instinct. We're trained to chase correctness. "Mostly right" sounds like a euphemism for a bug you didn't fix.
Here's where I've landed, and I'm genuinely still turning it over.
At a billion requests per second, perfect isn't free. Every consistency guarantee costs coordination, and coordination costs latency, and at that scale the price explodes. Strong consistency isn't a switch you flip it's a tax you pay on every operation, forever.
So "simplicity over perfection" isn't laziness. It's this:
Know exactly where your system can be wrong. Then decide whether fixing that rare wrong case is worth the cost. Usually it isn't.
That's what every mechanism in this paper actually is. The 10-second lease throttle. Gutter's short TTLs. The 2-second warmup hold-off. Best-effort invalidation. Each one names a precise, bounded way the system can serve stale data and then consciously decides that being occasionally, briefly wrong is cheaper than the machinery required to never be wrong.
Staleness as a dial, not a bug. They turned correctness into a parameter and tuned it against load. That's the worldview the whole system is built on, and it's the part of the paper I expect to keep re-learning for years.
What I actually took away
Walk back through it and notice that nothing in the architecture is clever. Each piece is forced.
Every arrow is a constraint forcing the next box. By the end the design doesn't feel like a bag of tricks Facebook invented. It feels like the only thing they could have built, given the numbers they started with. That's the whole point when you can see the constraints, the architecture stops being impressive and starts being inevitable.
And the personal part, the reason I read it at all: I'd shipped stampede protection and thought I understood the problem. I'd solved the herd. I hadn't even named the stale set. My version was narrower than theirs not wrong, just scoped for a smaller world that didn't force the harder half.
That's not a knock on my code. It's the actual lesson. Their scale forced generality I didn't need. Reading the paper didn't tell me I'd done it wrong it showed me the full shape of a problem I'd only seen one face of.
Which is the best reason I know to read the paper after you've built the thing. You arrive knowing one corner of the problem by feel. The paper hands you the rest of it and shows you why, at their scale, there was never any other way.
Next in this series: I'm sitting with leases a while longer specifically where my ON CONFLICT leader election and a real lease diverge, and what it would take to close the stale-set gap in a system that, unlike Facebook's, mostly doesn't need it.