jonnify·redis /redis-patterns/caching/cache-stampede-prevention/coalescing

R1.05.3 · Cache stampede prevention — dive 3

Collapse many misses into one.

The first miss starts the rebuild. Every later miss on the same owner attaches to it and waits for the one result — one source read serves the whole burst.

Grounding: echo/apps/echo_store/table.ex (the single-flight flights map, the :coalesced counter) · bcs.4.md (the herd drill) — coalescing, as EchoStore runs it.

The funnel. Slide the burst size; the misses funnel into one in-flight regeneration that makes one source read. Hover a stage to read its role.
6
misses one flight in-flight, shared source 1 read
readout · Slide the burst size; hover a stage to read its role.
§1

One in-flight regeneration

source · Handling Waiting Clients

Coalescing turns a key into a one-rebuild-at-a-time resource. The first request to miss the key starts the regeneration and records it in a small in-flight table: key → the in-flight rebuild. The next request that misses the same key, milliseconds later, looks in that table, finds the entry, and attaches to the running rebuild rather than starting a second one. Every attached request waits on the same result; when the rebuild completes, the value is delivered to all of them and the table entry is cleared.

The effect is that concurrency on one key collapses to one. A thousand near-simultaneous misses produce one source read and one cache fill; the other nine hundred and ninety-nine requests pay only the wait for that single rebuild. It needs no extra key on the engine: the merge is in-process state — a map of in-flight rebuilds keyed by the cache key.

The boundary is the process. The in-flight table lives in one application instance, so coalescing dedupes the misses within that instance. Across a fleet of instances, each one independently coalesces its own burst — so a hundred instances make up to a hundred source reads, not one. Closing that gap is the next section.

in-flight table
An in-process map, key → rebuild, of regenerations currently running.
first miss
Starts the rebuild and records it. Reads the source once.
later miss
Finds the in-flight entry and attaches; waits for the shared result; does not read the source.
completion
Delivers the one value to every waiter and clears the entry.
§2

Coalescing across processes

source · Solution 2: Mutex Locking

In-process coalescing is one source read per instance. To make it one source read for the whole fleet, the merge has to live somewhere shared — and that is the regeneration lock from the first dive. The first instance to win SET lock val NX PX for the key does the rebuild; the others, having lost the lock, do what the losers do — poll for the fill or serve stale. Valkey is the shared in-flight registry: the lock key is the cross-process equivalent of the in-process table entry.

So the two layers compose. Coalescing inside each instance collapses that instance’s concurrent misses to one attempt on the lock; the lock across instances collapses those attempts to one rebuild for the fleet. Together they take a fleet-wide flood — every instance, every concurrent request — down to a single source read.

# Two layers: coalesce in-process, then the lock across processes.
# 1. in-process: the first miss starts the rebuild; later misses attach.
# 2. cross-process: the rebuild contends for the shared lock —
SET lock:set:EMS0ODMggk1d5N "token" NX PX 5000
# one instance wins and reads the source; the rest serve stale or poll.

Coalescing dedupes within a process for free; the SET NX PX lock extends the same merge across the fleet, so the whole system makes one source read.

§3

Count the source reads

source · the three regimes

Compare the three regimes over one burst. Set the burst size — the concurrent misses on the key — and the number of instances, and the readout counts source reads with no protection (one per miss, per instance), with in-process coalescing (one per instance), and with the lock layered on (one for the fleet).

Source reads in one burst. Select a regime; slide the misses per instance and the instances. The bars use a log scale so the single fleet-wide read stays visible next to the unprotected flood.
200
6
1200 none 6 in-process 1 + lock source reads per burst (log scale)
readout · Select a regime and set the burst to count the source reads.

No protection makes one source read per miss; in-process coalescing makes one per instance; the lock makes exactly one for the whole fleet.

§4

On EchoStore — the flights map

table.ex · handle_call({:fill, id}) · verbatim

This is EchoStore’s read path, exactly. A read tries L1 caller-side; on a miss it calls the owner with {:fill, id}. The owner keeps a flights map keyed by id. The first miss launches a flight; a concurrent miss on the same id finds the entry, appends its caller to the waiter list, and bumps the :coalesced counter — it does not start a second load:

def handle_call({:fill, id}, from, state) do
  # ... L1 re-check elided ...
  case Map.fetch(state.flights, id) do
    {:ok, {ref, waiters}} ->
      :counters.add(state.spec.counters, counter(:coalesced), 1)
      {:noreply, put_in(state.flights[id], {ref, [from | waiters]})}

    :error ->
      ref = launch_flight(state, id)
      {:noreply, put_in(state.flights[id], {ref, [from]})}
  end
end

When the flight finishes, the owner replies to every waiter with the one answer and clears the entry. The flight runs GET ecc:{table}:id; on {:ok, nil} it calls the loader and writes both layers with SET … PX. The moduledoc names the law: “Concurrent misses on a key coalesce onto a single in-flight load … every waiter reads the one answer.”

Notes on Valkeyacross processes the merge rides one key: SET lock NX PX is the shared in-flight registry, the cross-process equivalent of the owner’s flights entry — valkey.io/commands/set.

the application · the herd drill, committed

One fill, 199 waiters coalesced

The merge is not asserted — the committed drill runs 200 simultaneous cold readers against the owner and counts the result: the loader runs once, 199 waiters coalesce onto the one flight, and every reader holds the one answer.

bcs.4.md · the single-flight drill, against live Valkeyfrozen
200 concurrent cold readers
loader runs                   1            ← one fill for the whole herd
coalesced waiters             199          ← every reader holds the one answer
the pattern

The first miss starts the rebuild; later misses attach to the in-flight one and share its result. Within a process this needs no extra key; across processes the SET NX PX lock is the shared in-flight registry.

its EchoStore application

EchoStore’s owner is the in-flight table: the flights map admits one load per id, concurrent misses append to the waiter list and bump :coalesced, and every waiter reads the one answer — the merge, as committed code.

Coalescing is the merge under both defences: the first miss rebuilds, every later miss attaches, and the lock carries that merge from one process to the whole fleet.

§5

References

sources · related

Sources

  • Valkey — SET — NX/PX for the cross-process lock that extends the merge across instances, and PX for the L2 fill.
  • Redis — SET — the canonical command reference for the lock the merge rides across a fleet.
  • Redis — Documentation — the expiry and locking primitives that extend an in-process merge across a fleet.
  • Sanfilippo, S. — antirez weblog — the Redis creator on single-instance locks and coordinating one writer.

Related in this course