Distributed cache simulator

The simulation runs in simulated time, one request at a time, at 2,000 requests a second. Each request picks a key, the cache node that owns the key answers if it holds a fresh copy, and otherwise the request queries the database, which has 32 connections and takes 80 ms per query. Entries live for 10 seconds. The charts show one bar per simulated second.

• Watch the first seconds: the cache starts empty and the database is swamped. Press Restart cache later to see it again, then turn on Coalesce and restart once more.
• Every 10 seconds the hot keys expire together and the query chart spikes. Turn on TTL jitter to spread expiries out, or Serve stale to answer from the old copy while one request refreshes it.
• Press + under Nodes with hash mod N selected, and again with Hash ring. The log reports the share of keys that moved and the hit rate in the five seconds after.
• Update hottest key writes a new value and deletes the cached copy. The log counts how many database queries the next second brought for that one key.

A distributed cache is a key-value store held in the memory of several machines, placed in front of a database or service so that repeated reads are answered quickly and the slower system sees only a fraction of the traffic. Each key lives on one node (or a primary and its replicas), chosen from a hash of the key, so the cache's total size and throughput grow with the number of nodes.

The arithmetic is what makes caches worth running: if 95% of reads are hits, the database handles one read in twenty. It is also what makes them dangerous. A database sized for the misses of a warm cache cannot handle the load of a cold one, so anything that makes many keys miss at once (a restart, a change in the number of nodes, popular keys expiring together) can overload it.

• Cache-aside (lazy loading): the application looks in the cache; on a miss it reads the database and stores the result with a TTL. On a write it updates the database and deletes the cached entry, so the next read loads the new value. This is the pattern simulated here.
• Read-through: the same, but the cache itself loads missing entries from the database.
• Write-through: writes go to the cache, which writes them to the database before acknowledging, so recently written data is always cached.
• Write-back (write-behind): writes are acknowledged once in the cache and written to the database later, in batches. Writes are fast, but anything not yet written is lost if a node fails.

Deleting on write, rather than writing the new value into the cache, avoids one race: two writers updating the cache in a different order from the database. It leaves another, in which a slow reader puts an old value back after the delete. Facebook's memcache deployment handles that with leases: on a miss, the cache hands the reader a token, and a later delete invalidates the token so the old value cannot be stored.

The obvious way to pick a node is hash(key) mod N. It spreads keys evenly, but when N changes almost every key gets a new node: a key stays put only if its hash gives the same remainder for both values of N. Going from N to N + 1 nodes moves about N/(N + 1) of all keys, and every moved key is a miss.

Consistent hashing (Karger and others, 1997) places nodes and keys on the same circle of hash values; each key belongs to the first node clockwise from it. A new node takes over only the keys between itself and its predecessor, about 1/(N + 1) of them. Measured on 5,000 keys with this page's hash function:

A cache stampede (also thundering herd or dogpile) is what happens in the gap between a popular key going missing and its value being stored again. Every request for that key in the gap misses and queries the database. If the hottest key gets a few hundred requests a second and the query takes 80 ms, one expiry turns one query into dozens. If the extra queries push the database past its capacity, queries queue, the gap gets longer, and more requests pile in.

The simplest case is a cold start. In the first five simulated seconds after the cache starts empty:

• Coalescing (request collapsing): when a request misses and a query for the same key is already running, wait for that query's answer instead of starting another. Go's singleflight package does this within one process, nginx's proxy_cache_lock within one proxy, and Facebook's memcache leases across a whole cluster.
• Serve stale while revalidating: keep an expired entry for a grace period; a request in that period gets the old value at once while one background request refreshes it. HTTP caches support this as the stale-while-revalidate directive (RFC 5861), and nginx as proxy_cache_background_update. The cost is that some readers see data up to the TTL plus the grace period old.
• TTL jitter: randomize each entry's TTL (here by ±20%) so that keys loaded together expire apart.
• Probabilistic early expiration: refresh an entry before it expires, with a probability that rises as expiry approaches and with how long the value takes to compute. Vattani, Chierichetti and Lowenstein (2015) showed an optimal form, often called XFetch. It is not simulated here.

Each combination was run for 60 simulated seconds. The hottest key's queries are counted over the whole run, the other columns after the first ten seconds, once the cold start is over:

Requests arrive evenly, 2,000 a second. Each picks one of 1,000 keys with Zipf-distributed popularity (exponent 1.05), so key 0 is the hottest. Each node holds up to 400 entries with least-recently-used eviction. The database runs 32 queries at a time, each taking 80 ms; others wait in line. Keys are placed with FNV-1a followed by MurmurHash3's finalizer, by modulo or on a ring with 100 points per node. Network time between client and cache is not modelled, so a hit takes 0 ms.

The model is checked headless: the share of keys moved when a node is added matches N/(N + 1) for modulo and 1/(N + 1) for the ring to within a few percent, a single hot key with coalescing costs one query per TTL, and a read after an update returns the new value. The numbers in this article are computed from the same code when the page is built.

David Karger, Tom Leighton, Daniel Lewin and colleagues at MIT introduced consistent hashing in 1997 as a way to spread web caching across many machines; Leighton and Lewin went on to found Akamai. Brad Fitzpatrick wrote Memcached in 2003 for LiveJournal, and it became the standard cache tier for large websites; Facebook's 2013 paper "Scaling Memcache at Facebook" describes running it across clusters and regions, including leases against stale sets and thundering herds. Redis, first released by Salvatore Sanfilippo in 2009, gained Redis Cluster with hash slots in version 3.0 in April 2015.