Memcache at Facebook

In 2013, Facebook published Scaling Memcache at Facebook. It describes a cache tier that handles billions of requests per second in front of sharded MySQL. Each idea answers a failure the team hit.

The big idea

At this scale a cache is no longer just a speed boost. It holds the system up, so each design choice asks what happens when it fails.

Five ideas stand out.

• Cache-aside with delete. Web servers read from memcache, fall back to MySQL, and fill the cache. Writes go to MySQL, and the cache key is deleted, not updated.
• Leases. They stop a slow reader from writing back a stale value.
• Commit-log invalidation. Deletes come from the database's log, so every write is covered, even ones from batch jobs.
• Regional pools. Rarely used, large items are kept in one shared pool, rather than copied into every cluster.
• Gutter pool. A small spare pool takes over when a memcache server fails.

Walking through it

Leases. On a miss, memcache hands the client a token. A later set succeeds only if the token is still valid. A delete on that key invalidates outstanding tokens. A slow reader holding an old token can no longer write its stale value back.

Leases also stop stampedes. Memcache issues a token for a given key at most once every 10 seconds. Other clients that miss in that window are told to wait briefly and retry, by which time the value is usually there. The paper reports that this cut the peak database query rate for hot keys from about 17,000 per second to about 1,300.

Commit-log invalidation. A daemon called McSqueal tails the MySQL commit log and broadcasts deletes to every cluster. Invalidation then covers every write, including ones that skip the application. The deletes are batched through a routing layer to reduce packet rate.

Regional pools. A region holds several front-end clusters that each have their own memcache servers, and they share one storage cluster. Large items that are rarely read go into a shared regional pool, so they aren't duplicated in every cluster.

Gutter pool. When a memcache server fails, clients send its traffic to a small pool of idle servers, about 1% of the fleet, with short TTLs. The alternative is to rehash the dead server's keys onto healthy servers, which can cascade.

Cross-region writes. A write from a non-primary region sets a remote marker. Reads of that key then go to the primary region's database until replication catches up. That gives a pragmatic version of read-your-writes.

Common mistakes

• Copying the architecture without the problem. Most teams don't need a gutter pool or regional pools. Start with leases and delete-on-write, then add pieces when you hit the failure they fix.
• Invalidating only in application code. Batch jobs and other services write the database too. Consider invalidating from the commit log.
• Ignoring the stale-set race. A reader can write an old value after a writer's delete, unless you use leases or short TTLs.

Check yourself

1. What does a lease prevent? A slow reader writing back a stale value after a delete has already happened.
2. Why does a gutter pool beat rehashing a dead server's keys onto healthy servers? Rehashing pushes the dead server's keys onto healthy servers, which can cascade. The gutter pool absorbs that load instead.

Key takeaways

• Writes delete cache keys. Deletes, not sets, keep the cache correct under races.
• Leases stop stale writes and reduce stampedes.
• Commit-log invalidation covers writes from every source.
• Gutter pools and regional pools handle failures and cost at scale.

Further learning

The NSDI talk by Rajesh Nishtala presents the design in about 20 minutes.

An MIT lecture on the same paper covers the consistency races in more depth.

Scaling Memcache at Facebooknsdi13-final170_update.pdfusenix.org

Next: the caching overview.