Facebook: scaling Memcache (NSDI 2013)

01 · CONTEXT

A cache in front of a database that could not cope alone

Facebook served a social network in which people consume far more content than they create. This asymmetry between reads and writes is the article's starting point: if the load is dominated by data fetches, a cache pays off a lot. The system described, built on memcached, came to handle billions of requests per second and to store trillions of items.

The base pattern is the cache look-aside filled on demand. On a read, the web server asks the cache; on a miss, it fetches from the database and writes the key-value pair to the cache. On a write, it writes to the database and sends a delete to the cache to invalidate the old data. The choice to delete rather than update has an explicit reason: deletes are idempotent. And the cache is not the source of truth, so it can discard items.

1. The user requests a page. The web server needs several pieces of data to assemble it and starts with the cache.

2. The web server asks the cache for the key. If the item is there, it is a hit and the database is not even queried.

3. If the item is not in the cache, it is a miss: the web server fetches the data from the database, which holds the authoritative copy.

4. With the data in hand, the web server writes the key-value pair to the cache. The next read of the same key will be served from memory.

5. On a write, the web server writes to the database and then sends a delete to the cache. The old data disappears and the next read reloads the new value.

Two goals guide the project's choices. One of them is unusual: the probability of reading slightly stale data is treated as a parameter to tune, like responsiveness. The team accepts exposing slightly stale data to protect storage from excessive load.

02 · IN THE CLUSTER: LATENCY AND LOAD

Thousands of servers, a page that requests hundreds of items

A popular page loaded, on average, 521 distinct items from memcache, and the items are spread across servers by consistent hashing. The result is that the web servers end up talking to all the cache servers in a short interval. This all-to-all pattern can cause congestion from incast or turn a single server into a bottleneck for many clients.

The complexity lives in the client, not in the server. The memcached servers do not talk to each other; routing, serialization, compression, and request batching live in a stateless client, which can be a library or the mcrouter proxy. For gets, the client uses UDP, which reduces latency and cost; a get error becomes a miss, and the web server avoids reinserting the entry so as not to overload an already stressed network or server. Sets and deletes go over TCP, via mcrouter on the same machine, because they need acknowledgment. To limit incast, a sliding window controls in-flight requests: it grows slowly with each success and shrinks when a request goes unanswered.

Two coherence failures appear in an on-demand cache. The stale set happens when concurrent updates arrive out of order and a server writes to the cache a value that is no longer the most recent. The thundering herd of reads happens when a heavily read and heavily written key is invalidated over and over and many reads fall onto the expensive path. The article's solution is leases: on a miss, memcached hands the client a token tied to that key, and only whoever presents a still-valid token can write. If a delete invalidated the token, the write is refused. A simple adjustment cures the herd: the server returns a token only once every 10 seconds per key, and whoever asks in that interval is told to wait a little.

1. A client requests a popular key that was just invalidated. The cache server gives a miss and hands that client a lease for that key.

2. Other clients request the same key right afterward. Instead of a second token, they are told to wait a little and try again, and the herd does not reach the database.

3. Whoever holds the lease fetches the value from the database and writes it to the cache presenting the token. Those that were waiting come back and generally already find the data.

4. If a delete arrives before that write, the token is invalidated and the set is refused. This way, a delayed write does not put a stale value on top of a newer one.

In a one-week measurement on keys especially prone to the herd, the peak of database queries was 17 thousand per second without leases and 1.3 thousand per second with leases. Since the database is sized for the peak, this becomes an efficiency gain. The same mechanism allows a shortcut: applications that can make progress with slightly stale data may accept the value marked as stale instead of waiting for the database.

Different workloads compete for the same memory, so the cluster is divided into pools. Without this, low-churn keys that were still valuable were evicted before high-churn keys that nobody accessed anymore; placing keys with different churn in distinct pools avoids this interference and makes it possible to size each pool by the cost of a miss. In some pools the article prefers to replicate a small set of heavily requested keys rather than split it further, and this requires delivering invalidations to all replicas.

03 · FAILURES AND THE GUTTER POOL

When the cache fails, the database pays

Failing to fetch from the cache generates excessive load on the backing services and can cause cascading failures. Automatic remediation of a few hosts is not instantaneous and can take a few minutes, enough time for the cascade to happen. To cover this interval, a small dedicated fleet, called Gutter, takes over the responsibilities of some failed servers. It represents about 1% of a cluster's memcached servers.

1. A cache server goes down. The client requests one of its keys and gets no response.

2. The client assumes the server failed and retries the request in a Gutter pool, a separate fleet of idle servers.

3. If Gutter also misses, the client fetches from the database and inserts the pair into Gutter. Subsequent requests for the same key already find the data there.

4. Gutter entries are short-lived: the price of protecting the database is serving slightly stale data for a short time.

Why not redistribute the failed server's keys among the others? Because access per key is uneven: whoever inherits a very hot key may become overloaded, and the failure turns into a cascade. Gutter diverts the load to idle servers and limits this risk. According to the article, the mechanism reduces the rate of client-visible failures by 99%.

04 · IN THE REGION: REPLICATION ACROSS CLUSTERS

More clusters, less dependence on a single one

Buying more servers does not solve everything: incast gets worse as the number of memcached servers grows. Facebook then split web and memcached into several front-end clusters that, together with a storage cluster holding the databases, form a region. The trade-off is explicit: data replication is given up in exchange for more independent failure domains.

The storage cluster has the authoritative copy and is responsible for invalidating the front-end clusters. For this, the SQL statements that change state are extended with the cache keys to invalidate when the transaction commits, and a daemon (mcsqueal) on each database reads the deletes from the commits and relays them to the caches of all clusters in the region, in batches to reduce packets. Since the invalidation is in the database's reliable logs, mcsqueal can replay lost or misrouted invalidations, something that sending directly from the web servers does not allow.

Each cluster stores what its users request, and replicating everything in all clusters wastes memory. To reduce the number of replicas, several clusters share the same set of memcached servers: this is the regional pool. The trade-off is stated: crossing cluster boundaries costs more latency and the network has 40% less average bandwidth between clusters than within one, while replication spends more servers to get less traffic between clusters, lower latency, and better fault tolerance. For this reason, the choice between replicating and keeping a single copy per region depends on the item.

A new cluster, or one coming back from maintenance, has an empty cache and a terrible hit rate. Cold Cluster Warmup lets the cold cluster's clients read from a warm cluster instead of from persistent storage, and brings the recovery to full capacity down from a few days to a few hours. To avoid inconsistency from a race, deletes in the cold cluster carry by default a two-second hold-off, during which add operations are rejected: if the add fails, the client knows there is newer data in the database and fetches it there. The article admits that the theoretical possibility remains of a delete being delayed longer than that, and considers it rare.

05 · ACROSS REGIONS: CONSISTENCY

The database replica may be lagging

With multiple regions, one region holds the master databases and the others have read-only replicas. In this design, maintaining consistency between memcache and persistent storage becomes the main technical challenge, and it arises from a single problem: the database replica may lag behind the master. The chosen model is eventual consistency on a best-effort basis, with emphasis on performance and availability; ideas with stricter semantics rarely leave the design phase because they are too expensive.

Consider a write in the master region. If the web server invalidated the cache in a replica region right after writing, the invalidation could arrive before the data reaches the replica, and the next read would put stale data back in the cache. This is why the invalidation originates from the storage cluster, via a daemon, and the stream of deletes shares the database replication channel.

Now, a write in a non-master region with a heavily lagging replica: the person may not see their own change. The article uses a remote marker. The web server creates a marker for the key in the region, writes to the master embedding the key and the marker to invalidate in the SQL, and deletes the key in the local cluster. On the next read, the miss leads the server to check the marker: if it exists, the query goes to the master; if not, to the local replica. It is an explicit trade-off, with more latency on the miss in exchange for a lower chance of reading stale data.

1. Write in the master region: the web server writes to the master MySQL, and the SQL carries the cache keys to invalidate.

2. mcsqueal reads what the database committed and deletes the keys in the master region's caches.

3. Replication carries the change to the replica; only then does the replica region's mcsqueal, which reads the replica, delete the key in the cache there. The invalidation never gets ahead of the data.

4. Write in a non-master region: the web server creates the key's marker, writes to the master, and deletes the key in the local cache.

5. On the next read, the local cache misses and the server finds the marker, so it sends the query to the master. The replica, which may still be lagging, is avoided.

06 · TRADE-OFFS

What each mechanism buys and charges

Notice the pattern: almost every mechanism accepts a bit of stale data or latency in exchange for protecting the database. It is the project's stated goal applied at each scale: in the cluster, leases and Gutter; in the region, regional pools and invalidation by commit; across regions, the remote marker.