Distributed Cache

A distributed cache is a server, or a cluster of servers, that keeps data in memory and is shared by all your application servers. It's one of the most common ways to both cut latency and take load off your database. This note covers when to use one and what changes once the cache is spread across several machines. For strategies, invalidation and eviction, see Caching.

When to use one#

Three situations call for a shared cache.

• Store aggregated metrics. An analytics dashboard pulls from many sources, and the numbers are expensive to compute. A background job computes them (say hourly) and stores the results in the cache, so dashboard requests just read them.
• Reduce database queries. User sessions are often kept in a distributed cache so every app server can read them without hitting the database. This matters most with many concurrent users.
• Speed up expensive queries. A "posts from people you follow" query joins and filters several tables and can be slow on a disk-based database. Run it once, cache the result, and serve repeats from memory.

What to decide (and say out loud)#

Once you add a cache, make four decisions explicit.

1. Eviction policy: LRU, LFU or FIFO for when the cache is full.
2. Invalidation strategy: how cached data is refreshed when the source changes. For example, if you cache popular events for a ticketing site, you must invalidate an event when its venue changes in the database.
3. Write strategy: write-through, write-around or write-back (see Caching).
4. What you store and in which data structure. Modern caches aren't just key-value stores. To serve "most popular events", a Redis sorted set scored by popularity lets you fetch the top N directly. Saying "we'll cache the events" without naming the key and structure is a missed opportunity, and it invites follow-up questions.

Redis vs Memcached#

The two common choices differ mostly in features.

Pick Redis unless you have a specific reason to want Memcached's simplicity and multi-threading.

Spreading keys across cache nodes#

One cache node has limits: memory, throughput, and it's a single point of failure. So you split keys across several nodes. The question is how a client knows which node holds a key.

Why hash(key) % N breaks#

With 3 nodes, hash(key) % 3 picks the node. Add a 4th and switch to % 4, and most keys now map to a different node (roughly 3 out of 4 when going from 3 to 4). Every remapped key is a cache miss, and all those misses hit the database at once.

Consistent hashing#

Place both nodes and keys on a hash ring. Each key belongs to the first node clockwise from it. Adding a node only takes over the keys between it and its neighbor, so about $1/N$ of keys move instead of most of them. Virtual nodes (each physical node placed at many points on the ring) even out how much of the ring each node owns.

The full walkthrough, with ring examples, is in Scaling Writes. For a cache, a remapped key is only a miss: annoying, but the data still exists in the database.

Cache stampede (thundering herd)#

A very popular key expires, and thousands of requests miss at the same moment and all hit the database. Adding cache nodes doesn't help, because the key doesn't exist anywhere.

In an interview, lock-on-miss is the easiest fix to explain.

Key takeaways#

• Use a distributed cache to serve precomputed results, shared sessions, and the results of expensive queries.
• Always name what you cache, the key format and the data structure (e.g. a sorted set for "top N").
• Redis is the default. Memcached is a simpler, multi-threaded, strings-only alternative.
• Use consistent hashing so adding a node moves only about $1/N$ of keys.
• Protect hot keys from stampedes with lock-on-miss, jittered TTLs or background refresh.