Scaling Memcache at Facebook
A single-machine hash table turned into a multi-region cache tier, one named race and one named overload shape at a time.
Read the original ↗Board 15 on this site ends on the stampede: a hot key expires, a thousand requests miss at once, the database dies. This is the paper that hit every version of that problem at a scale where the fixes had to be real, and wrote down what it cost. It is also the clearest published account of what you have actually built when you put a cache in front of a database - which is a second copy of your data with no transaction across it.
Included with a plan
This discussion is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
Related on chalk
The same idea as a board, lab, video or lesson.
- BoardThe Slate Next to the Stovethe look-aside cache itself - hit, miss, and the two curses this paper spent a decade on
- BoardThe Slate, Properlythe stampede and single-flight; the paper's lease is that fix, with the stale-set race fixed as a bonus
- BoardThe Copy Clerksthe lagging replica the remote marker exists to route a just-written key around
- BoardSplitting the Ledgerthe cache tier partitioned into pools, and the key that is hot rather than big - replicated, not sharded
- BoardThe Thundering Herdthe same herd at another company, arriving from the reconnect side instead of an expiry
- BoardReplicationchange data capture off the replication log, which is where this paper's invalidations come from and why they are replayable
- LabThe slate next to the stovehit rate and eviction with a dial on them - the cache this paper is scaling, one server's worth
- LabSplitting the ledgerwhat a badly chosen key does to a pool, which is why some keys get replicated instead
- LabThe copy clerksthe stale read a replica region serves, priced in seconds - the thing the remote marker refuses to serve
- VideoCaching: the slate next to the stovethe cache at its simplest, before any of this is required
- VideoCaching properly: write strategies, stampedes, and invalidationcache-aside, write-through, stampede, single-flight - the vocabulary this paper is written in
- VideoReplication: the copy clerksthe lag between copies, which is the whole cross-region section
- VideoThe thundering herd: when everyone reconnects at oncewhat the herd does to the thing behind the cache
- LessonThe slate next to the stove (caching)Uses the board The Slate Next to the Stove
- LessonCounting the crowd without a register (HyperLogLog, count-min, top-k)Uses the board The Slate Next to the Stove
- LessonThe Slate, Properly (caching to real depth)Uses the board The Slate, Properly
- LessonKV: quorumUses the board The Copy Clerks
- LessonThe copy clerks (database replication)Uses the board The Copy Clerks
- LessonKV: the ringUses the board Splitting the Ledger
- LessonSplitting the ledger (sharding)Uses the board Splitting the Ledger
- LessonSlack - the case studyUses the board The Thundering Herd
- LessonReplicationUses the board Replication
Further reading
Read the original for the full argument and its evidence.
- The paper ↗NSDI 2013. Read it in the order it is written - cluster, region, regions - and pay particular attention to the leases subsection and to where the invalidations come from.
- TAO: Facebook's Distributed Data Store for the Social Graph ↗The companion piece from the same year, and the honest sequel: a write-through, graph-aware cache for the workload this paper's look-aside design served worst.
- The CacheLib Caching Engine ↗OSDI 2020. What the same problem looks like once flash is a sensible place to keep a cache and the single-machine engine has been rewritten around it. The useful contrast with this paper's tuning sections.