Memcache
paper link
https://drive.google.com/file/d/136_VFCXjQ5qTLn8XPEokMJvQ2qksytDf/view?usp=sharing
paper year
2013
thoughts
This paper is honestly way better than the Google papers I’ve covered so far, mostly because it’s so upfront about its own design. The Google papers explain things in a way that sounds almost perfect. But nothing in distributed systems is perfect. There are always assumptions and tradeoffs, and in those papers you have to dig them out yourself. Scaling Memcache at Facebook is the opposite: it points out exactly where the design is faulty and why they chose it anyway. They even say it in the conclusion, that a lot of their tradeoffs aren’t fundamental and come from the reality of evolving a live system with limited engineering time.
The paper is from 2013 and it’s a foundational one for caching, so when I wanted to explore caching, this was the obvious place to start.
The first big lesson is understanding your workload and being okay with the tradeoffs that come with it. The CAP theorem says that when the network partitions you have to pick between consistency and availability, and even when it doesn’t, you’re still trading consistency against latency. Facebook’s workload is very read heavy. Users consume an order of magnitude more content than they create, and they don’t need strong consistency, best effort eventual consistency works fine. If you like something and your friend sees that like a little late, nobody cares. They literally treat the probability of reading stale data as a knob they tune, and they’ll show slightly stale data if it protects the database from load. Because they know their workload so well, the whole design stays focused on the problem they actually have.
I also liked how raw the paper is about what really happens inside an engineering org. They already had an open source tool, memcached, which is just an in-memory hash table on a single machine. They say they picked it because it was the best choice given limited engineering resources and time. Then they built a distributed system around it. It has its share of faults, but they moved fast and engineered around those problems well.
They use memcache as a demand-filled look-aside cache, which is the pattern most systems use today, and this paper is the classic example of running it at massive scale. It’s called look-aside because the cache sits off to the side of the main path. The application checks the cache first, but the application itself owns the path to the database. In read-through caching, the cache sits directly in that path, between the application and the database, and fetches from the database for you.
A couple of other design choices stood out to me. First, UDP for GET requests. Intuitively you’d just use TCP everywhere, but UDP is connectionless, so each web server thread can talk to memcached servers directly without setting up and holding connections, and that cut their latency. If a UDP packet gets dropped or arrives out of order, the client just treats it as a cache miss and goes to the database. It even skips setting the value back into the cache afterwards, so it doesn’t add load to a network that might already be overloaded. Sets and deletes go over TCP instead, because those definitely need to go through.
Second is request batching using a dependency graph. Think of loading a Facebook page: one request can need hundreds of items, each living on a different memcached server. Fetching them one by one is too slow, but you can’t fire everything in parallel either, since some data depends on other data. You can’t load the tags on an image before you know which image it is. So they build a directed acyclic graph of the dependencies (fittingly, almost everything at Facebook ends up being some kind of graph) and use it to fetch as many items concurrently as possible.
Then there are two common problems, stale sets and the thundering herd, and they solve both with a concept called a lease.
Stale sets: say request A misses the cache, gets a lease token for that key, and goes to the database. Before A comes back, B updates the database and deletes the key from memcache. That delete invalidates A’s lease. So when A comes back and tries to set its now outdated value, memcached checks the token, sees it’s no longer valid, and rejects the set. Without this, A would overwrite the cache with stale data. It works similarly to load-link/store-conditional.
Thundering herd: this happens when a key gets heavy reads and writes at the same time. Every write deletes the key, and every delete sends a flood of reads straight to the database. With leases, memcached only hands out a token for a key once every 10 seconds. Anyone else who misses on that key within those 10 seconds is told to wait a short while and retry. Usually the client holding the lease sets the value within a few milliseconds, so by the time the others retry, the data is already in the cache. On their thundering-herd prone keys, this dropped the peak database query rate from 17K/s to 1.3K/s.
Another trick for reducing database load is cold cluster warmup. When a new cluster comes online, or one comes back after a failure or maintenance, its caches are empty and every request would hit the database. So on a miss in the cold cluster, the client fetches the key from a warm cluster (one with normal hit rates) and adds it into the cold cluster. This brings a cold cluster back to full capacity in a few hours instead of a few days. There’s a race, though. A client in the cold cluster updates the database, and someone else pulls the old value from the warm cluster before the warm cluster gets the invalidation. Now the cold cluster has stale data indefinitely. To avoid that, every delete in the cold cluster comes with a two second hold-off, during which adds for that key are rejected. If the add fails, the client knows there’s newer data and goes to the database instead. Deletes could in theory take longer than two seconds, but they almost never do, and they’re okay with that.
Another clever decision is the gutter pool. Normally a cache miss just means going to the database. But what if a memcached server doesn’t respond at all? They keep a small set of idle machines, about 1% of the memcached servers in a cluster, called Gutter. If a client gets no response to a get, it assumes the server is dead and retries against the gutter pool. If that’s also a miss, the client fetches from the database and puts the value into gutter. This buys time until automated remediation fixes the dead server, which can take a few minutes, without every one of those requests hammering the database. In practice it cut client visible failures by 99%. The interesting part is why they don’t just rehash the dead server’s keys onto the remaining servers. A single hot key can be 20% of a server’s traffic, so moving it to another server can overload that one too and cascade. Sending it to idle servers avoids that.
The catch is stale data. They don’t invalidate gutter at all, entries there just expire quickly. So you can read slightly stale data from gutter for a short window, and they’re okay with that tradeoff.
There’s that famous line that there are only two hard problems in computer science: naming things and cache invalidation. Their answer is to delete instead of update, because deletes are idempotent. If two deletes for the same key arrive in any order, or get replayed, the end result is the same: the key is gone, and the next read refills it from the database. Updates don’t have that property. If two updates land in the wrong order, you’re left with stale data. To drive invalidations, they run a daemon called McSqueal on every database. The keys to invalidate are embedded in the SQL statements, so McSqueal reads what the database commits, extracts the deletes, batches them, and sends them to mcrouter instances in each frontend cluster. Those unpack them and route each delete to the right memcached server. Since it’s all driven off the database’s commit log, lost or misrouted invalidations can simply be replayed. The web server that made the write also deletes the key in its own cluster right away, so the user sees their own write.
Another, admittedly controversial, design choice is how they go across regions. One region holds the master databases, and every other region has read-only replicas kept up to date through MySQL replication, plus its own memcache. All writes go to the master. The problem is that replicas can lag behind the master, so you can get stale reads in non-master regions. For a user writing from a non-master region, they use something called a remote marker. The web server sets a marker for the key in its region, writes to the master, and deletes the key locally. On the next miss, if the marker is there, the read goes to the master region instead of the possibly stale local replica. So they pay extra latency on a miss in exchange for a lower chance of stale data, and they’re okay with that.
The last piece is mcrouter, a proxy that runs on the same machine as each web server and talks the memcached protocol. Web servers are highly parallel, and keeping an open TCP connection from every web thread to every memcached server would eat way too much memory. So sets and deletes go over TCP through the local mcrouter, which coalesces all those connections. GETs over UDP skip mcrouter and go straight to the memcached servers.
Also worth noting, the cache and the persistent data are fully decoupled. The real data lives in MySQL and gets replicated through MySQL replication, and memcache is just a layer in front of it to absorb read load. That’s actually the first lesson they list in the conclusion: separating cache and persistent storage lets you scale each one independently.
The biggest takeaway for me is that you can engineer a great solution around whatever setup you already have, and evolve it as requirements change. You don’t need a clean slate to do good distributed systems work. That said, the design still has a real limitation. Memcache is a plain key-value store and knows nothing about the social graph, so graph data like friendships and likes gets stored as opaque blobs the application has to manage itself. Facebook built a separate system to solve this, which we’ll cover next.