Skip to content
Scaling Memcache at Facebook 4 min

Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, Venkateshwaran Venkataramani · NSDI 2013

Scaling Memcache at Facebook

How Facebook made a plain cache scale: look-aside caching, lease tokens against thundering herds and stale sets, gutter pools and log-driven invalidation.

Read the original paper

Systems & Distributed · Black Belt · Pro · 4 min read

Scaling Memcache at Facebook

Facebook's front page is built from thousands of small facts: your friends' names, their latest posts, the counts under each photo. Fetching all of that from a database on every page view would melt any database. So Facebook put memcached, a simple in-memory cache, in front of it.

But a cache that works for one server fails in surprising ways at their scale. This paper is a tour of those failures and their fixes. Each fix is small, clever, and easy to reuse in your own designs: leases, a gutter pool, invalidation from the database log, and regional pools.

Use a look-aside cache, and treat the database as the source of truth. When you write, delete the cached key. Add leases so a burst of misses becomes one database query, and so a slow reader cannot overwrite fresh data with old data.

The basic pattern: a look-aside cache

In a look-aside cache, the application does the work. On a read it asks the cache first. If the key is missing, it reads the database and then puts the value in the cache. On a write it updates the database, then deletes the cached key, so the next read will load a fresh copy.

The cache is 'look-aside': the application asks the cache first, and on a miss it reads the database and fills the cache. On a write it changes the database and deletes the cached copy instead of updating it.

Why delete instead of update? Deletes are idempotent: doing one twice does no harm. An update that arrives out of order can leave an old value in the cache. Deleting is simpler to reason about, and the next reader repairs the key.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

3 more sections, 1 more diagram and 2 interactive elements to play with

  • Problem 1: the thundering herd
  • Problem 2: stale sets
  • More tools from the paper

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.