jonnifyechomq

Single-flight & jittered TTL · dive 01

One fill
per herd

Concurrent misses on the same key coalesce onto a single in-flight load.

On a cache miss, fetch/3 sends {:fill, id} to the owner. The owner's handle_call/3 is where the second law holds: if a flight for this id is already in progress, append the caller to its waiters and count :coalesced — start no second flight. The flight is a spawn_monitor'd task: it GETs L2, runs the declared loader on a miss, writes both layers, and sends one result message back. The owner then replies that one answer to every waiter. A crashed flight fails all its waiters with {:error, {:flight_crashed, reason}} — no caller wedges.

The coalescing handler The flight Worked example Pattern & implementation References

The coalescing handler

Before fetch/3 sends {:fill, id}, it already did a caller-side :ets.lookup and found a miss. But time has passed: the owner's handle_call({:fill, id}) re-checks L1 first, because a flight from an earlier caller may have already won the race and inserted the row. If the row is now there and still valid, the handler replies immediately as a :hit, counts it, and never starts a flight.

If L1 is still empty, the handler looks in state.flights. Two outcomes:

  • A flight exists for this id: append from to its waiters, count :coalesced, reply :noreply. No second flight.
  • No flight exists: call launch_flight/2, record {ref, [from]} in state.flights[id], reply :noreply.

Both branches return {:noreply, state} — the owner is never blocked waiting for the load. Its mailbox continues to drain normally.

# EchoStore.Table — handle_call({:fill, id})
# The second law: one fill per herd. The owner re-checks L1 first (the
# race may have been won while this message was in the mailbox), then
# either appends to an existing flight or starts the first one.
def handle_call({:fill, id}, from, state) do
  now = System.monotonic_time(:millisecond)

  case :ets.lookup(state.name, id) do
    [{^id, value, expires_at, _version}] when now < expires_at ->
      # The race was won: another flight filled L1 between the caller's
      # miss and this message landing. Reply as a hit; no flight needed.
      :counters.add(state.spec.counters, counter(:hits), 1)
      {:reply, {:ok, value, :hit}, state}

    _ ->
      case Map.fetch(state.flights, id) do
        {:ok, {ref, waiters}} ->
          # A flight is already in progress. Append this caller to its
          # waiter list. The :coalesced counter records the save.
          :counters.add(state.spec.counters, counter(:coalesced), 1)
          {:noreply, put_in(state.flights[id], {ref, [from | waiters]})}

        :error ->
          # No flight exists. Start one; record its monitor ref and this
          # caller as the first waiter in state.flights[id].
          ref = launch_flight(state, id)
          {:noreply, put_in(state.flights[id], {ref, [from]})}
      end
  end
end

The flight

launch_flight/2 spawns an anonymous function under a monitor. It carries the owner's connector, loader, TTL, and a freshly minted version id of the table's declared kind. Inside the spawned process:

  1. Issue GET ecc:{table}:id to L2.
  2. On nil: run loader.(id) and on success SET ecc:{table}:id (version <> value) PX ttl_ms; send {:fill, value, version}.
  3. On a valid L2 frame (<<version::binary-14, value::binary>>): send {:l2, value, version}.
  4. On a short frame or loader error: send {:error, reason}.

The spawned process sends send(owner, {:flight, id, result}) and exits. handle_info({:flight, id, result}) pops the flight map entry, demonitors, inserts into L1 via insert/4, and calls Enum.each(waiters, &GenServer.reply(&1, reply)) — the one answer to every waiter in one sweep.

A crash before the send fires handle_info({:DOWN, ref, :process, _pid, reason}). The owner finds the matching flight, replies {:error, {:flight_crashed, reason}} to every waiter, and removes the entry. No caller is left waiting on a dead pid.

# EchoStore.Table — handle_info({:flight, id, result})
# The flight sent its result back to the owner. Pop the flights entry,
# demonitor the process, classify the result, insert into L1, and reply
# that one answer to every waiter in the list.
def handle_info({:flight, id, result}, state) do
  {{ref, waiters}, flights} = Map.pop(state.flights, id)
  Process.demonitor(ref, [:flush])

  reply =
    case result do
      {:l2, value, version} ->
        # Found in L2 — the fill sources the L2 frame; count it.
        :counters.add(state.spec.counters, counter(:l2_hits), 1)
        insert(state, id, value, version)
        {:ok, value, :l2}

      {:fill, value, version} ->
        # Loader ran and wrote both layers; count the fill.
        :counters.add(state.spec.counters, counter(:fills), 1)
        insert(state, id, value, version)
        {:ok, value, :fill}

      {:error, _} = err -> err
    end

  # The one answer fans out to every waiter atomically.
  Enum.each(waiters, &GenServer.reply(&1, reply))
  {:noreply, %{state | flights: flights}}
end

# handle_info({:DOWN, …}) — the flight crashed before sending its message.
# Fail every waiter cleanly; no caller wedges on a dead process.
def handle_info({:DOWN, ref, :process, _pid, reason}, state) do
  case Enum.find(state.flights, fn {_id, {r, _}} -> r == ref end) do
    {id, {^ref, waiters}} ->
      Enum.each(waiters, &GenServer.reply(&1, {:error, {:flight_crashed, reason}}))
      {:noreply, %{state | flights: Map.delete(state.flights, id)}}
    nil ->
      {:noreply, state}
  end
end

Worked example: the coalesce counter

Drag the slider to set how many callers miss simultaneously on the same key. The model runs the exact handle_call logic: first caller starts a flight, every subsequent caller appends and increments :coalesced. The loader is called exactly once. Read the running counter and the fetch/3 results.

Coalesce counter · concurrent misses on one id

1
flights started 1 :coalesced (callers saved) 0 loader calls: 1 — regardless of herd size

The owner's mailbox serializes concurrent misses so the loader is called exactly once — and :coalesced is the counter that proves it.

Pattern & implementation

the pattern (stampede prevention)

On a cache miss under load, a single-flight (or lock-on-miss) serializes concurrent fills so only one caller reaches the backing store. The others wait on the result. Redis Patterns Applied · R1 teaches the stampede-prevention pattern.

the implementation (EchoStore.Table)

The owner's GenServer mailbox is the serialization point. The first {:fill, id} starts a spawn_monitor'd flight; each subsequent one appends to state.flights[id]. One loader call; one Enum.each fans the result out.

The pattern says: run the loader once, share the result. The implementation makes the owner's mailbox the lock — no external lock service, no separate registry.

References

Sources

Related in this course