Skip to content
sysgeeks

Design a Distributed Cache (Memcache), stage 3 of 9: decide

The key everyone wants

The database is provisioned for the normal miss rate. This one key is producing a large share of all misses.

System so far· 5 parts
1234CLIENTUsersSERVICEWeb serversSERVICEmcrouterCACHEmemcached poolDATABASEMySQL

Select a component to see what it is responsible for and which state it owns.

  1. 1Users → Web servers: Page request
  2. 2Web servers → mcrouter: get / multiget, delete
  3. 3mcrouter → memcached pool: Keys by consistent hash
  4. 4Web servers → MySQL: Query on miss; writes

What you need to know

0 of 1 checks done

  1. A thundering herd (or stampede) happens when many readers miss the same key at the same moment, and all of them go to the database to rebuild it. With a hot key, that moment is every time the key is deleted or expires.

  2. Raise the request rate and the rebuild time and watch how many queries reach the database with each strategy.

    A hot key expires. Rebuilding it takes one expensive query. Until that query finishes, every request for the key misses. The database can run about 200 of these queries at once before it slows down.
    5,000/s400 ms

    Queries reaching the database while the key is rebuilt (log scale). The dashed line is what it can run at once.

    • No protection2,000
    • Coalesce per server20
    • One rebuild, fleet-wide1
    • Serve stale, refresh behind1
    No protection:
    Every request that misses queries the database. 2,000 requests wait about 400 ms, longer, because the database is past capacity and every query slows down.
    Coalesce per server:
    Each of 20 servers lets one request rebuild; the rest on that server wait for it. 2,000 requests wait about 400 ms.
    One rebuild, fleet-wide:
    A short lock in the cache lets one request in the whole fleet rebuild. 2,000 requests wait about 400 ms.
    Serve stale, refresh behind:
    Keep serving the old value while one background request rebuilds it. Nobody waits; a few requests see a value that is a moment old.

  3. Check

    Without protection, what decides how many queries a hot key's miss sends to the database?