Lesson 03 · Cache misses & leases

The Dangerous Moment

A cache hit is the least interesting event in computing. Everything that can go wrong with a cache goes wrong in the microseconds after a miss — and there are two separate failures hiding in there, which most people conflate into one.

The win in this lesson: you will be able to tell a thundering herd from a stale set — they look identical on a dashboard and need completely different fixes — and you will know the one mechanism Facebook used to kill both.

1. Why the miss is the whole story

On a hit, a look-aside cache does nothing interesting: it returns bytes. On a miss, the application has to do three things that are not atomic — notice the miss, fetch from the database, write the result back — and between those steps the world keeps moving. Other readers arrive. Writers commit. Invalidations land.

Two things can go wrong in that gap, and they are genuinely different problems:

• Too many clients do the fetch at once — a thundering herd. A load problem. The cache ends up correct; the database falls over.
• One client writes back a value that is already out of date — a stale set. A correctness problem. The database is fine; the cache is now lying, and it will keep lying until something invalidates it again.

On a graph they can look the same — latency up, database busy. Fixing the wrong one wastes a week.

2. The thundering herd

"A thundering herd happens when a specific key undergoes heavy read and write activity. As the write activity repeatedly invalidates the recently set values, many reads default to the more costly path."

§3.2.1, Scaling Memcache at Facebook

Read that carefully, because the usual telling of this story is wrong. The herd is not caused by a cache expiring, or by a cold start. It is caused by writes — each one deletes the key (Lesson 01: invalidate by delete, because deletes are idempotent), and every reader that arrives before someone refills it goes to the database. A popular, frequently-edited key is a pump: write, miss, miss, miss, refill, write, miss, miss, miss.

3. The stale set

"A stale set occurs when a web server sets a value in memcache that does not reflect the latest value that should be cached. This can occur when concurrent updates to memcache get reordered."

§3.2.1

This one is worth walking through step by step, because it is the failure people do not see coming. Nothing crashes, no request is slow, and no log line is printed. The cache simply becomes wrong and stays wrong.

4. One mechanism, both problems

"a memcached instance gives a lease to a client to set data back into the cache when that client experiences a cache miss. The lease is a 64-bit token bound to the specific key the client originally requested. The client provides the lease token when setting the value in the cache. With the lease token, memcached can verify and determine whether the data should be stored and thus arbitrate concurrent writes."

§3.2.1

So a miss no longer returns "nothing". It returns permission — a token saying "you are the one refilling this key". And crucially:

"Verification can fail if memcached has invalidated the lease token due to receiving a delete request for that item."

§3.2.1

That single sentence kills the stale set. Replay the diagram above with leases: the reader's token is issued at the miss, the writer's delete invalidates that token, and when the reader finally tries to set, memcached rejects it. The stale value never lands. The cache stays empty — which is correct, because empty means "ask the database", and the database has v2.

A lease is not a lock

The word invites the wrong picture. A lock is pessimistic: you take it, everyone else blocks, and you must give it back. A lease is optimistic: you take a token, nobody blocks, and there is nothing to give back. The token is only examined at the very end, when you try to write.

That difference is not stylistic — it removes an entire class of operational pain:

The paper points at the right family directly: leases "prevent stale sets in a manner similar to how load-link/store-conditional operates". That pair of CPU instructions is: load a value and begin watching the address, then store only if nothing has touched it since. The store does not wait for anyone — it either succeeds or reports that it was beaten.

What the token actually encodes

One fact, and only one: "no delete has arrived for this key since your miss". That is why a delete invalidates outstanding tokens — the delete is the event the witness was watching for.

And note what happens when verification fails: the set is rejected and the cache entry stays absent. Not wrong — absent. This is safe precisely because of the property from Lesson 01: in a look-aside cache, a missing entry only ever costs a database read. Rejecting a write can never damage correctness, so the mechanism is allowed to be blunt. (Compare the remote marker, where eviction was unsafe — and which the paper flags as a departure from cache semantics for exactly this reason.)

So a get has four possible answers, not two

Where it still leaks

Three residual risks, none of which the paper hides:

• The holder can vanish. If the client with the token crashes before setting, nothing refills the key — but nothing is stuck either. The server will issue a fresh token to someone else, at worst on the next rate-limit window. The failure is bounded and self-healing, which is exactly what a lock cannot say.
• Waiters pay latency. "Wait a short amount of time" is still waiting. The rate limit converts database load into client-side delay — a trade that is clearly worth it at their ratios, and worth checking at yours.
• It is local, not coordinated. A token is state on one memcached instance about one key. There is no agreement between servers, no consensus, nothing to elect. That is why it is cheap enough to do on every miss at a billion requests per second — and also why it guarantees nothing beyond the single server that issued it.

5. The twist that kills the herd

Leases as described solve correctness. One extra rule solves load:

"Each memcached server regulates the rate at which it returns tokens. By default, we configure these servers to return a token only once every 10 seconds per key. Requests for a key's value within 10 seconds of a token being issued results in a special notification telling the client to wait a short amount of time. Typically, the client with the lease will have successfully set the data within a few milliseconds. Thus, when waiting clients retry the request, the data is often present in cache."

§3.2.1

One token per key per ten seconds means at most one database query per key per ten seconds, no matter how many clients want it. Everyone else is told to wait and try again — and by the time they do, the first client has refilled the cache, so they get a hit.

Notice the shape of the fix: it is not caching, and it is not queueing. It is admission control — deciding how many callers are allowed past the cache and into the expensive path at all. The cache stops being only a store and becomes a gatekeeper.

What it was worth, measured on keys chosen for being herd-prone, over a week:

A 13× reduction — but the sentence that follows the numbers is the one to actually steal:

"Since we provision our databases based on peak load, our lease mechanism translates to a significant efficiency gain."

§3.2.1

6. The escape hatch: serve it stale

Waiting is still waiting. So Facebook added a third option for callers who do not need the freshest value:

"When a key is deleted, its value is transferred to a data structure that holds recently deleted items, where it lives for a short time before being flushed. A get request can return a lease token or data that is marked as stale. Applications that can continue to make forward progress with stale data do not need to wait for the latest value to be fetched from the databases."

§3.2.1

A deleted value is not thrown away immediately — it is kept briefly, flagged as stale. A caller that misses can be handed either a lease token ("you go fetch it") or the old value stamped "this is out of date, do what you like with it". Which turns a two-way choice into three, and only one of them touches the database.

And the justification for why this is usually safe is a lovely piece of domain reasoning:

"since the cached value tends to be a monotonically increasing snapshot of the database, most applications can use a stale value without any changes."

§3.2.1

Stale here means "an earlier version of the truth", not "a wrong version". A like count that is a few seconds behind is a number that was true and is only low. That is survivable in a way that an arbitrary wrong value never would be — and it is the property you have to check before using this trick anywhere.

7. The three answers, side by side

The interesting column is the second one. Discord could not put this in the store, because they run a database they did not write; Facebook could, because they had already forked memcached and were shipping their own build. Where a fix can live is decided by what you own — the same force that decided memcached over Redis in Lesson 01.

8. Check yourself

Three of these reach back to earlier lessons. Mixing them in is deliberate and it is supposed to feel harder than reviewing them in a block.

9. Back to your world

You do not need Facebook's traffic for either of these. The herd arrives the first time a popular cached value is also frequently written — a dashboard counter, a feed, a config blob read on every request. The stale set arrives the first time you write "invalidate the cache after the update" and deploy it, because the hole is in the pattern, not in your implementation of it.

The question to carry: on a miss, who is allowed to fetch, and what stops a slow fetcher from writing back a value that is already wrong? If the answer to either is "nothing", you have both bugs; you are just waiting for the traffic that reveals them.