SD5.6 · LESSON 6 OF 6

Stampedes and failures

Design a cache key, freshness policy and miss path while calculating load and mean-latency effects.

THE IDEA

Stampedes and failures

At a 90% hit rate, 1,000 requests a second leave only 100 for the origin, and the mean latency is 0.9 × 2 + 0.1 × 50 = 6.8 ms. If the cache fails, all 1,000 land on an origin sized for 200: five times over. A hot key that expires can trigger a stampede, hundreds of simultaneous fills. Coalesce duplicate fills so one request loads and the rest wait, stagger expiry with jitter, and bound the fallback load by shedding what the origin cannot serve.

requests per second1000hit rate0.9origin capacity (req/s)200

mean latency at 2 ms hit / 50 ms miss: 6.8 ms origin load: 100 req/s against capacity 200 → 0.5× ok 500 concurrent misses on one hot key: 500 fetches at once

The hit rate hides how much the origin can really carry. When the cache fails or a hot entry expires, the full workload lands on a source sized only for misses. Coalesce duplicate fills, stagger expiry with jitter, and bound the fallback load.

Take the cache down and change the origin capacity.

Predict first. Can a high hit rate hide insufficient origin capacity?

Chapter context

A cache serves a previously obtained representation instead of repeating work. Its correctness depends on which requests can share a value and how long that value may remain useful. Fast retrieval of the wrong representation is still an error.

TRY IT YOURSELF

Part 1. Do it hands-on

Compute normal and outage load by hand, then write the load, coalescing, jitter and shedding helpers.

requests per second1000hit rate0.9origin capacity (req/s)200

mean latency at 2 ms hit / 50 ms miss: 6.8 ms origin load: 100 req/s against capacity 200 → 0.5× ok 500 concurrent misses on one hot key: 500 fetches at once

origin req/s at 90% hits origin req/s in an outage times over a 200 req/s origin fetches for 500 coalesced misses high hit rate hides weak origin capacity? (yes/no)

To do: 1000 requests/s at a 90% hit rate. Requests per second reaching the origin?
To do: The cache fails completely. Requests per second reaching the origin?
To do: The origin is provisioned for 200 requests/s. During the outage it is how many times over capacity?
To do: A hot key expires and 500 concurrent requests miss it. With request coalescing (one fill, others wait), origin fetches?
To do: Can a high hit rate hide insufficient origin capacity? Type yes or no

Part 2. Do it in code

origin_load(rps, hit_rate): (1 − hit_rate) × rps.
mean_latency(hit_rate, t_hit, t_miss): hit_rate·t_hit + (1 − hit_rate)·t_miss.
overload_factor(load, capacity): load / capacity.
outage_load(rps, hit_rate): the load on the origin if the cache is down (everything misses).
fetches_without_coalescing(n_concurrent_misses): n. fetches_with_coalescing(requests): requests is a list of keys that miss at the same moment; one fill per distinct key.
ttl_with_jitter(base, jitter_fraction, u): u in [0, 1]; base × (1 + jitter_fraction × (2u − 1)) so that entries do not all expire together.
shed(load, capacity): (accepted, rejected) when requests above capacity are refused instead of queued forever.

def origin_load(rps, hit_rate):
    pass

def mean_latency(hit_rate, t_hit, t_miss):
    pass

def overload_factor(load, capacity):
    pass

def outage_load(rps, hit_rate):
    pass

def fetches_without_coalescing(n_concurrent_misses):
    pass

def fetches_with_coalescing(requests):
    pass

def ttl_with_jitter(base, jitter_fraction, u):
    pass

def shed(load, capacity):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can a high hit rate hide insufficient origin capacity?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

If h is hit probability, t-hit hit-path time and t-miss complete miss-path time:

E[T]=h\,t_{hit}+(1-h)t_{miss},\quad R_{origin}\approx(1-h)R.

The miss time here already includes lookup overhead. Means do not establish tail latency, and background refresh can add origin traffic.

Worked example

At 90% hits, 2-ms hit paths and 50-ms complete miss paths, mean latency is 0.9×2+0.1×50=6.8 ms. For 1000 requests/s, nominal origin demand is 100 requests/s. During a complete cache outage, it could become 1000 requests/s rather than remaining at the normal miss rate.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
hit=.9
assert isclose(hit*2+(1-hit)*50,6.8)
assert isclose((1-hit)*1000,100)
assert 1000/100 == 10

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A hit ratio is not a correctness guarantee. Mean latency does not reveal p95. Shared caching requires a safe identity and privacy policy; TTL does not replace authorization.