Joseph Peterson

Stampede a cache

Hundreds of readers ask the bakery’s cache for its menu. When the menu expires, watch the database, then tame the stampede four ways.

1,500 reads in 5.0 s, 94.3% from the cache. When the menu expired at 3.0 s, the database fetched it 23 times at once and 2 reads timed out.

Time

Virtual time 5.000 s, 1,704 events, seed 7

Against a stampede

Speed
Load
Placement

Writes

Nodes

  • One fetch of a page at a timeBroken 40 times, at worst 23 fetches of one page at once
  • No reader timed outBroken: 2 reads timed out
  • No reader got a page past its limitHeld

What happened

  1. 3.032 s The menu's entry expired at 3.000 s: its readers miss, and each one fetches it from the database
  2. 3.056 s The menu is fetched twice at once: a second reader missed before the first fetch came back
  3. 3.118 s The menu now has 5 fetches in flight at once
  4. 3.175 s The menu now has 10 fetches in flight at once
  5. 3.300 s All 8 database connections are busy, and 13 fetches wait in line for one
  6. 3.307 s The menu now has 20 fetches in flight at once
  7. 3.392 s The menu is cached again as version 1; 22 more fetches of it are in flight, and each that comes back stores it again
  8. 4.011 s Page 6 now has 5 fetches in flight at once
  9. 4.307 s A reader of the menu gave up after waiting 1,000 ms, with 6 fetches in line for the database
  10. 4.400 s The line for the database is empty again
  11. 5.000 s 2 readers gave up in the last second, 2 in all

What a cache promises

A cache keeps a copy of what the database would say, close to the reader, for a while. Most of the bakery’s 120 pages are cheap, and one, the menu, is asked for far more than the rest and takes 420 ms to build. A cache entry carries an expiry time. Until it passes, readers get the copy in a millisecond. When it passes, the next reader goes to the database, and so does every reader who arrives before the new copy is back.

That last part is the stampede. At 300 reads a second, an expired menu sends dozens of readers to the database at once. Its eight connections fill, the rest wait in line, and readers who wait a second give up. A fetch still in line when its last reader leaves is dropped; one already running finishes.

Three things to try

Let the menu expire. The first run does it: the entry expires at 3.0 s, the database fetches the menu 23 times at once, and two readers time out. Turn on coalescing and serving stale, and start over. One reader fetches; the others wait for that fetch or take the old copy, and nobody times out.

Flush every node at the morning rush. Choose the morning’s 600 reads a second and flush with nothing turned on. Every page misses at once: within a second more than 250 fetches wait for the database’s eight connections, and for about four seconds readers give up. The pages fetched again together expire together eight seconds later, so the overload comes back in waves, smaller each time. Turn on jitter and early refresh before you flush, and the expiries spread out: no second wave forms.

Lose a node. The pages live on four cache nodes. With modulo placement, losing one moves about three quarters of the pages to a new node, empty, so they all miss at once. On the hash circle, only the lost node’s quarter moves.

Then write to the menu with invalidation off, and count the readers who get the old version until it expires.

What the lines and lamps mean

Readers enter on the left and fan in to the four cache nodes. A node’s small lamps are the pages it holds, and their shape says fresh, expired, missing or being fetched. The database’s eight lamps are its connections; a lit lamp is a fetch running, and the count beside them is the line waiting. Under the picture, each moment’s reads are drawn by what they got: the cache, a stale copy, a fresh fetch, or a timeout, and a hollow bar is reads still waiting. The three properties under it are checked after every event.

Credits

Early refresh is the XFetch rule from Andrea Vattani, Flavio Chierichetti and Keegan Lowenstein, Optimal Probabilistic Cache Stampede Prevention (VLDB 2015). Coalescing stands in for the leases in Rajesh Nishtala et al., Scaling Memcache at Facebook (NSDI 2013). Serving stale while refreshing is RFC 5861. The hash circle is consistent hashing (David Karger et al., STOC 1997).

What it costs

Nothing to run. Every file is static, and your browser runs the simulation.

How it is built

The readers, the four nodes and the database are one TypeScript module that runs in virtual time. Every random draw in it, from when a reader arrives to how long a fetch takes, comes from one seeded stream, and your presses are recorded at the moment they happened. The same seed and the same presses give the same run, every time. The page opens on seed 7 at 5 s, 1,500 reads and 1,704 events in, drawn before any script runs; your browser replays them and takes over at that moment.

After every event, a checker counts each break of the three properties, and checks that every read ends exactly once and that every fetch the database starts comes back when it is due. A count that does not add up is a bug in the simulation, and it stops the run. The same simulator plays 600 seeded runs of random loads, switches, flushes, lost nodes and writes in the site’s tests, and deliberately broken caches prove those runs can find a real bug: one that forgets a waiting reader, one whose database never answers some fetches, one that serves a stale copy past its limit, one that ignores jitter, and one whose hash circle places pages by modulo.

Up and down to move, Enter to open, Esc to close