How Facebook Scaled Memcache: Leases, Regions, Invalidations

A cache can still overload your database when many requests miss the same key at once, or when old values sneak back in after a write. Both problems grow as you add servers, clusters and regions. A 2013 paper, Scaling Memcache at Facebook, shows how Facebook (now Meta) solved both at billions of requests a second.

Picture a common setup. A social app for college students runs in two regions, meaning two groups of data centres far apart: Hyderabad holds the main databases, and Mumbai holds a read-only copy. About 60 lakh (6 million) people open it every day. The setup is made up, but the problems are real.

Reads beat writes by about 200 to 1. One feed page asks for around 300 small items: names, photos, like counts and comments. So the team keeps a fleet of memcached servers, which hold recently used data in memory.

Then one post goes viral on a Saturday night, and four things go wrong within an hour.

• The post's like count changed every few milliseconds. Each change deleted the cached count, so thousands of readers missed together. Database load jumped from 8,000 to 60,000 queries a second.
• A deleted comment came back on the post. A slow web server had written an old copy into the cache after the delete.
• A student in Mumbai edited her bio, refreshed, and saw the old one. The Mumbai database copy had not caught up yet.
• One cache server died. All its keys fell through to the database at once, and the database slowed even more.

Each of these failures has a named fix in the paper. This guide walks through every fix on the same app, in the order the paper builds them.

Facebook built a layered system around many memcached servers: smart clients, leases, a database-driven delete pipeline and rules for crossing regions. The memcached servers never talk to each other, so the complexity lives in the clients.

Facebook did tune memcached itself, for example with more threads and finer-grained locks. It also added server features: lease tokens, a short-lived store of recently deleted values, and deletes with a short hold-off that blocks re-adding the key. But the servers still never talk to each other, and routing, batching and failover live in the clients.

The paper uses two words carefully. Memcached is the open-source program: an in-memory hash table on one server, with get, set and delete. Memcache is the whole distributed system Facebook built from many memcached servers.

The paper was presented at NSDI 2013, a networking and systems conference. It says the system handles billions of requests per second and holds trillions of items. It builds the design in three steps, one per scale.

• In one cluster (paper section 3): many web and cache servers, where the problems are waiting time and database load after misses.
• In one region (section 4): several clusters sharing one set of databases, where the problem is keeping every cluster's copy in sync.
• Across regions (section 5): data centres far apart, where the problem is database copies that lag behind the main one.

Here is the app's setup, shaped like the paper's. Follow a read from the users to the cache, and a write down to the database. Then notice the daemon box, which sends deletes on the database's behalf.

The table maps each technique in this guide to the problem it fixes. Keep it handy as you read.

A look-aside cache sits beside the database, and your app code manages it: check the cache, read the database on a miss, then fill the cache. Facebook's app deleted keys after writes instead of updating them, because deletes are idempotent.

Idempotent means doing it twice gives the same result as doing it once. Deleting a key twice still leaves no key. Setting a key from two racing writers can leave whichever value arrived last, and that may be the older one.

The paper calls this a demand-filled look-aside cache. Demand-filled means a key enters the cache only when someone asks for it and misses. A hit is when the value is found, and a miss is when it is not.

Here is the pattern for a profile, with a Python dictionary standing in for memcached and another for the database. It runs as it is on Python 3.

cache = {}                          # stand-in for memcached
db = {"profile:42": "bio v1"}       # stand-in for the database
db_reads = 0

def get_profile(key):
    global db_reads
    value = cache.get(key)
    if value is not None:
        return value                # hit: no database work
    db_reads += 1
    value = db[key]                 # miss: go to the database
    cache[key] = value              # fill for the next reader
    return value

def update_profile(key, new_value):
    db[key] = new_value             # the database is the truth
    cache.pop(key, None)            # delete, never set

print(get_profile("profile:42"), get_profile("profile:42"), db_reads)
update_profile("profile:42", "bio v2")
print(get_profile("profile:42"), db_reads)

The write path never puts a value in the cache. The next reader misses, reads the fresh row and fills the cache. Memcache is not the source of truth, so it may also evict any key to free memory.

This pattern still has a gap. Between a reader's database read and its cache set, a writer can slip in. That gap is exactly how the deleted comment came back.

A lease is a 64-bit token that Facebook's memcached gives a client on a miss. It is bound to that one key. If the key is deleted before the client sets it, the token stops working and the set is refused.

A stale set is when a web server writes a value into the cache that is no longer the latest. It happens when a slow reader's set lands after a newer write. Here is how it happened on the viral post.

1. 1

   Server A misses

   Server A asks for the comment list, misses, and reads the database. The comment is still there.

2. 2

   Server A stalls

   Server A pauses for 300 milliseconds (made up) while its machine is busy with other work.

3. 3

   The comment is deleted

   The author deletes the comment. The database row changes, and the comment list key is deleted from the cache.

4. 4

   Server A wakes up

   Server A sets the old list, comment included. Without leases, that wrong value can sit in the cache until the next change or eviction.

5. 5

   With a lease

   Server A's miss came with a token. The delete cancelled that token, so memcached refuses the late set, and the next reader fetches the fresh list.

Picture Zaveri Bazaar in Mumbai, where each lane of jewellers keeps a slip with the day's gold rate. The association office holds the real rate. A shop that finds its slip missing sends one errand boy to fetch it, and the office notes his errand.

If the rate changes while he is walking back, the office strikes off his errand. When he arrives, his old slip is refused. The office is the database, the slip is the cached value, the errand is the lease, and striking it off is the delete.

Where the picture breaks: nobody stops the errand boy on the road. The slow server still reads the database and does its work. Only its final set is refused, when the token comes back cancelled.

The paper compares leases to load-link and store-conditional, a pair of processor instructions. There, a write succeeds only if nothing touched the value since you read it.

This toy model shows the mechanism in plain Python. It runs as it is, but leaves out the time limit you will meet in the next section.

import itertools

class LeaseCache:
    """Toy model of the paper's leases: one token per missed key."""
    def __init__(self):
        self.data, self.leases = {}, {}
        self.tokens = itertools.count(1)

    def lease_get(self, key):
        if key in self.data:
            return self.data[key], None     # hit
        if key in self.leases:
            return None, None               # someone else is filling: wait
        token = next(self.tokens)
        self.leases[key] = token
        return None, token                  # you won the right to fill

    def lease_set(self, key, value, token):
        if self.leases.get(key) != token:
            return False                    # token cancelled: refuse the set
        del self.leases[key]
        self.data[key] = value
        return True

    def delete(self, key):
        self.data.pop(key, None)
        self.leases.pop(key, None)          # a delete cancels the lease

cache = LeaseCache()
_, token_a = cache.lease_get("comments:7")  # server A misses
_, token_b = cache.lease_get("comments:7")  # server B misses too
print("A token:", token_a, "| B token:", token_b)
cache.delete("comments:7")                  # the comment is deleted
print("A's late set stored?", cache.lease_set("comments:7", "old list", token_a))

Facebook configured each memcached server to hand out at most one token per key every 10 seconds, so usually only one client goes to the database. The others are told to wait a short time and retry.

A thundering herd is a crowd of requests that all miss the same key at once and all rush to the database. The viral like count was a perfect example. Every like deleted the key, and every reader then missed together.

In the bazaar picture, only one errand boy per lane may go to the office. The other shops wait a moment, and the new rate soon arrives.

The paper says the lease holder typically sets the value within a few milliseconds. So by the time waiting clients retry, the value is usually there.

The paper measured this for one week on keys prone to herds. Without leases, the peak database query rate was 17,000 a second. With leases, it was 1,300, about 13 times lower.

Here is the read path with a lease. Start at the top and follow the No answer from the second question. That loop is where the crowd waits instead of hitting the database.

There is one more trick, called stale values. When a key is deleted, Facebook's servers move the old value into a short-lived store of recently deleted items. A get can then return either a token or a value marked stale.

Apps that can live with slightly old data, like a like count, take the stale value instead of waiting. The paper says most apps could do this without changes.

With leases on the like count keys, the team's next viral post peaks near 9,000 database queries a second instead of 60,000 (made up).

When a get gets no reply, Facebook's client assumes the server is down and asks a small spare pool called Gutter instead. Gutter is about 1% of a cluster's memcached servers, and it takes over for the few servers that have failed.

If the Gutter request also misses, the client reads the database and puts the value in Gutter. Gutter entries expire quickly, so Gutter needs no invalidations, at the price of slightly stale data.

The paper says Gutter cuts client-visible failures by 99%. It also turns 10% to 25% of failures into hits each day.

Why not just move the dead server's keys to the others? Keys are spread over servers with consistent hashing, a scheme that maps each key to one server and moves few keys when a server leaves. The paper notes that one key can make up 20% of a server's requests.

Moving that hot key onto a busy neighbour can knock that server over too, and the failure spreads. A spare pool that sits idle absorbs the load instead.

The team adds a Gutter pool of four idle servers. The next time a cache server dies, the database barely notices (made up).

Facebook put all the clever routing in the client, as a library or as mcrouter, a proxy that speaks the memcached protocol. Keeping clients stateless made them quick to change and deploy. Four of the paper's techniques stand out.

• Batching: the app maps which data depends on which, and fetches independent items together. The paper reports an average of 24 keys per request, with 95 at the 95th percentile.
• UDP for gets: UDP needs no connection, so gets are cheap. At peak, 0.25% of gets were discarded as late, dropped or out of order, and clients treat those errors as misses.
• TCP for sets and deletes: TCP confirms delivery, so changes go over TCP through an mcrouter running on the same machine as the web server.
• A sliding window: the client limits how many requests are in flight. The window grows slowly after each success and shrinks when a request goes unanswered.

The window fights incast congestion. That is when many servers reply to one client at the same moment and overflow the network switch between them.

Facebook's 2014 post introducing mcrouter says it handled close to 5 billion requests per second at peak. Its features include prefix routing, which routes keys by a shared prefix, and replicated pools, which write to every host and read from one. Automatic failover moves requests from an unresponsive server to another one. A reliable delete stream logs failed deletes to disk and replays them.

One scoping note for your own setup. Open-source memcached 1.6.24 has UDP off by default: "memcached -h" shows the UDP port as "default: 0, off". Check your version before copying the UDP trick.

Inside a region, Facebook let the database drive invalidation. A daemon called mcsqueal reads the SQL statements each database commits, pulls out the cache keys to delete, and sends batched deletes to every frontend cluster.

First, why many clusters at all? A frontend cluster is a group of web servers plus memcached servers. A region holds several frontend clusters and one storage cluster with the databases.

The paper gives two reasons not to grow one giant cluster. Popular items only get more popular as more web servers are added. And incast gets worse as the number of memcached servers grows.

The price of smaller clusters is that a popular key now lives in every cluster's cache. So every cluster must hear about every delete.

Facebook changed each SQL statement that modifies data to also carry the memcache keys to invalidate once the transaction commits. Follow the arrows in the diagram from the write to both clusters.

Batching matters because many databases talk to many cache servers across cluster lines. The paper reports an 18 times improvement in the median number of deletes per packet.

The writing web server also deletes the key in its own cluster. That gives read-after-write for the same user request: the writer sees its own change at once.

Why not let web servers broadcast deletes to every cluster? The paper gives two reasons. Web servers batch poorly. And when deletes got lost or misrouted by a config error, there was little recourse. Deletes in committed SQL can simply be replayed.

Regional pools and cold clusters

Copying every key into every cluster wastes memory on large, rarely read items. So Facebook let several frontend clusters share one set of memcached servers, called a regional pool. Reads cross a cluster boundary, which is slower, but only one copy is stored.

A new cluster starts with an empty cache, which would hammer the databases. Cold cluster warmup lets its clients read misses from a warm cluster instead, then add the value locally. The paper says this cuts warmup from a few days to a few hours.

Warmup has a race: the warm cluster may still hold a value that was just changed. So deletes to the cold cluster carry a two-second hold-off, during which add operations for that key are refused. A refused add tells the client to read the database.

A remote marker is a small flag in the local region's shared cache pool saying the local database copy may be behind for one key. While the flag exists, a cache miss reads from the master region instead of the local replica.

Some words first. The master region holds the databases that take writes. Replica regions hold read-only copies, kept up to date by MySQL replication. Replication lag is the delay before a write reaches a copy.

Writes made in the master region are already handled. Each replica region runs its own delete daemon beside its replica databases. It reads what that replica commits, so its deletes follow the replicated change instead of racing ahead.

If a web server in Hyderabad sent deletes straight to Mumbai, they could arrive before the data. A Mumbai reader would then miss, read the old row from the replica, and put it back in the cache.

Writes from a replica region are the hard case. That was the Mumbai student and her bio. Here is what the paper's web server does when a write affects key k.

1. 1

   Set the marker

   Set a remote marker for k in the local region's regional pool.

2. 2

   Write to the master

   Send the write to the master region. The SQL also lists k and the marker as keys to invalidate once it commits.

3. 3

   Delete locally

   Delete k from the local cluster's cache, so the next local read misses.

4. 4

   Read with a check

   On that miss, check for the marker. If it exists, read from the master region. If not, the local replica is safe.

5. 5

   Marker clears itself

   When replication delivers the write to the replica region, its daemon deletes the marker along with k.

Here is the read side. The paper names the trade plainly: extra latency on a miss, in exchange for a lower chance of reading stale data.

Remote markers are not perfect. Two writes to the same key can race, and one may delete a marker the other still needs. A marker can also be evicted. The paper says both cases are rare in practice.

This fits the paper's overall promise: best-effort eventual consistency, with an emphasis on performance and availability. Eventual consistency means copies agree in the end, with no hard promise of when.

Not under that name, but memcached's meta protocol gives you both powers. On memcached 1.6.24, tested on 19 October 2026, the first client to miss wins the right to refill, and a conditional set refuses a stale write.

Three flags on the meta get command, mg, do the work. N30 creates an empty placeholder for 30 seconds on a miss. The v flag returns the value, and c returns the CAS value, a version number that changes on every write.

The reply carries one of three letters. W means you won and should refill. Z means a win was already handed out, so wait or retry. X means the value is stale but usable.

To check it yourself, start a test memcached and run these four commands. The comments show what memcached 1.6.24 printed. On a busy server the number after c will differ.

# Start a local test server (memcached 1.6.x) in another terminal:
#   memcached -p 11211 -l 127.0.0.1

# 1. First reader misses and wins the right to refill
printf "mg like:42 v c N30\r\n" | nc -w 1 127.0.0.1 11211
# VA 0 c1 W

# 2. Second reader misses the same key a moment later
printf "mg like:42 v c N30\r\n" | nc -w 1 127.0.0.1 11211
# VA 0 c1 Z

# 3. The winner fills the key, sending back the CAS it saw (c1)
printf "ms like:42 4 C1 T60\r\n1001\r\n" | nc -w 1 127.0.0.1 11211
# HD

# 4. Everyone now gets the value
printf "mg like:42 v\r\n" | nc -w 1 127.0.0.1 11211
# VA 4
# 1001

The ms command is meta set, and C1 means store this only if the CAS is still 1. That plays the role of the lease token, without patching the server. Unlike Facebook's token, every reader sees the CAS, so W is advisory: only the client that got W should send it.

The stale-set race behaves the same way. In our test, the winner missed, then a writer marked the key stale with "md KEY I T30". The winner's late set with its old CAS got EX.

EX means the CAS no longer matched, so the old list never landed. Without the C flag, the same late set returned HD and stored the old value. That is the bug from step 4 earlier.

One row differs in a way that matters. Open-source memcached 1.6.24 has no time cap like Facebook's 10 seconds: in our test, each delete or "md I" handed out a fresh W at once. So on a key that changes every few milliseconds, rate-limit refills in your client.

The docs page describes EX for a failed CAS, and the X and W pair the next reader gets after "md I". The protocol spec, protocol.txt at the 1.6.24 tag, documents two more.

A late CAS set on a deleted key returns NF, for not found. Readers after the winner get Z, and readers of a stale key also get X, so they can serve the old value while one client refills.

One detail came only from our runs. When the winner never came back, a new W appeared once the placeholder's lifetime ran out: 2 seconds for one made with N2. That is undocumented as of 19 October 2026, so pin your memcached version and re-run the check after upgrades.

Explain it as one simple cache that grows in steps, and name the failure each new piece fixes.

1. 1

   Start with look-aside

   Read the cache, fill on a miss, delete on write. Say why you delete instead of set.

2. 2

   Fix one cluster

   Add leases for stale sets and herds, batching and a proxy for waiting time, and a Gutter pool for dead servers.

3. 3

   Split into clusters

   Explain hot keys and incast. Then show how a daemon on the commit log sends batched deletes to every cluster.

4. 4

   Go multi-region

   Draw a master region and a replica region. Explain replication lag, and how remote markers send risky misses to the master.

5. 5

   State the consistency promise

   Say clearly that this is best-effort eventual consistency, and that a little stale data is the price for protecting the databases.