Design a Distributed Cache (Memcached / Redis Cluster)

TL;DR. A distributed cache is a fleet of RAM-backed nodes sitting between stateless application servers and a slower origin database. The design pivots on three axes: how keys map to nodes (consistent hashing), what to evict when memory fills (LRU vs W-TinyLFU), and how to survive hot keys that exceed single-shard capacity (leases, singleflight, probabilistic early expiration). Facebook's memcache tier serves billions of requests per second^[1] with a 99% hit rate that reduces MySQL load by 100x^[2]. Netflix EVCache runs 22,000 instances across 4 regions handling 400M ops/sec against 14.3 PB of cached data^[3]. The client library is the part you will spend the most time maintaining.

Learning Objectives#

After this module, you will be able to:

• Map keys to shards using consistent hashing and explain when rendezvous hashing is preferable
• Choose eviction policies (LRU, LFU, W-TinyLFU, ARC) based on workload access patterns
• Design replication and failover for a cache tier that must survive node loss
• Mitigate hot keys and cache stampedes with leases, singleflight, and probabilistic early expiration
• Justify when to pick Memcached vs Redis Cluster vs a managed service like MemoryDB
• Estimate memory, node count, and bandwidth for a 10M ops/sec cache cluster

Intuition#

A distributed cache looks trivial. Hash a key, pick a server, store the value in RAM. A single-node prototype handles this in an afternoon.

Three forces break the naive approach at scale. First, memory. A 100 TB working set does not fit on one machine. You need 1,000 nodes, and now every key lookup requires a routing decision. If that routing is a simple modulo hash, adding one node remaps nearly every key and your hit rate drops to zero during the transition. Second, hot keys. A celebrity tweet or a viral product page concentrates millions of reads on one shard. That shard's NIC saturates, its tail latency spikes, and every other key on the same shard suffers collateral damage. Third, TTL cliffs. When a popular key expires, thousands of concurrent clients miss simultaneously and stampede the origin database.

The one insight that unlocks the design: the cache is not a database. It is a performance optimization with a memory budget. Every decision flows from that constraint. You can lose data (it is regenerable). You cannot lose availability (the origin cannot absorb the full load). You cannot lose routing stability (remapping all keys on every topology change is a self-inflicted outage).

Requirements#

Clarifying Questions#

• Q: Is this a pure cache (regenerable from origin) or a primary store? Assume: Pure cache. The origin database is the system of record. Cache loss means higher latency, not data loss.

• Q: What is the read:write ratio? Assume: 100:1. Reads dominate. Writes are origin-triggered invalidations or TTL-based expiry.

• Q: Multi-region required? Assume: Yes. Three regions, zone-local reads, cross-region replication for latency-sensitive data.

• Q: What consistency guarantee? Assume: Eventual. Stale reads are acceptable for seconds. Strong consistency is the origin's job.

• Q: What is the SLA target? Assume: p99 < 5 ms for cache hits, 99.99% availability on the read path.

• Q: Must we support rich data structures (sorted sets, lists) or just key-value blobs? Assume: Key-value blobs for the core design. Rich structures are a Redis-specific extension.

Functional Requirements#

• Store key-value pairs in RAM with configurable TTL per key
• Route keys to shards via consistent hashing with minimal remapping on topology changes
• Evict keys when memory fills, using a configurable policy (LRU default)
• Replicate shards optionally for high-value data that is expensive to regenerate
• Expose a memcached-compatible ASCII/binary protocol for broad client support

Non-Functional Requirements#

• Load: 10M ops/sec cluster-wide, 10K ops/sec per node (p99 < 1 ms)
• Capacity: 100 TB total across 1,000 nodes, 100 GB RAM per node
• Availability: 99.99% read path; shard failure must not drop user-visible requests
• Rebalance: adding or removing a node moves at most 1/N of keys
• Latency: p50 < 0.5 ms, p99 < 2 ms for cache hits within a region

Capacity Estimation#

Key derivations:

• Node count from QPS: Redis single-node handles ~100K ops/sec^[4]; memcached handles ~1M simple gets/sec per instance^[2:1]. At 10M cluster QPS, you need 100 Redis nodes or 10 memcached nodes for throughput alone.
• Node count from memory: 100 TB / 100 GB = 1,000 nodes. Memory is the binding constraint, not CPU.
• Slab overhead (memcached): ~50 bytes per item metadata^[5]. At 100B items, that is 5 TB of overhead (~5% on 1 KB items).
• Fragmentation headroom: budget 20% extra RAM for jemalloc fragmentation (Redis) or slab calcification (memcached)^[5:1][6].

API and Data Model#

API Design#

GET <key>
  Returns: value (bytes) + flags + CAS token
  Miss: NOT_FOUND (or lease token if leases enabled)

SET <key> <flags> <ttl> <bytes>\r\n<value>
  Returns: STORED | NOT_STORED (CAS mismatch)

DELETE <key>
  Returns: DELETED | NOT_FOUND

GETS <key1> <key2> ... <keyN>
  Returns: multiple values + CAS tokens (batched multi-get)

META GET <key> [flags: v N30 R10 t]
  Returns: value + metadata flags (W=win recache, Z=wait)
  Purpose: server-side lease and probabilistic early refresh[^7]

Design notes:

• Multi-get batching: clients group keys by shard, issue parallel requests, and reassemble. mcrouter does this transparently^[7].
• CAS (compare-and-swap): prevents stale-write races. The client reads a CAS token with GETS, then writes with CAS <token>. If another writer intervened, the CAS fails.
• Meta commands: memcached's meta protocol exposes lease semantics (N flag creates a stub on miss, W flag grants recache permission) without application-level coordination^[8].

Data Model#

-- Per-item layout (memcached slab allocator)
struct item {
    uint8_t   slab_class;     // which size class (1 of ~40)
    uint32_t  flags;          // application-defined
    uint32_t  exptime;        // absolute TTL (epoch seconds)
    uint64_t  cas_token;      // compare-and-swap version
    uint8_t   key_len;        // max 250 bytes[^7]
    uint32_t  value_len;      // max 1 MB default[^7]
    char      key[];
    char      value[];
}
// Total overhead: ~50 bytes per item[^5]

-- Redis Cluster slot mapping
HASH_SLOT = CRC16(key) mod 16384
-- Hash tags: {user:1000}.name and {user:1000}.age -> same slot[^9]

Memcached uses a slab allocator: memory is divided into 1 MB pages, each assigned to a size class (chunk sizes grow by factor 1.25). An item of 600 bytes fits the 640-byte class. Each class has its own LRU chain^[5:2].

Redis Cluster maps all keys to 16,384 hash slots via CRC16. Each master owns a subset of slots. Hash tags ({...}) force related keys to the same slot for multi-key operations^[9].

High-Level Architecture#

Look-aside cache architecture: the application talks to cache and origin independently. The cache does not know about the DB schema. Binlog-driven invalidation ensures deletes propagate without application coordination.

Write path (cache-aside with delete-on-write): The application writes to the origin DB, then deletes the cache key. Facebook uses delete rather than set because concurrent writers are commutative under delete but not under set^[2:2]. A stale reader's SET after a concurrent writer's DELETE would permanently cache stale data; with delete-on-write, the worst case is a transient miss.

Read path: Application calls GET key on the proxy. The proxy hashes the key to a shard. On hit, the shard returns the value in < 1 ms. On miss, the application reads the origin and issues SET to populate the cache.

Invalidation path: MySQL binlog changes flow through a pipeline (McSqueal at Facebook^[2:3]) that emits DELETE commands to the cache proxy. This ensures every cluster sees invalidations even if the writing application crashes before issuing its own delete.

Deep Dives#

Consistent hashing and key distribution#

The fundamental routing problem: given N cache nodes and a key, which node owns it? And when N changes to N+1, how many keys move?

Naive modulo hashing (node = hash(key) % N) remaps nearly all keys when N changes. Adding one node to a 100-node cluster moves ~99% of keys, causing a near-total cache miss storm.

Ring-based consistent hashing (Karger et al., 1997)^[10][11] places nodes and keys on a circular hash space. A key walks clockwise to the next node. Adding a node moves only 1/N of keys. To avoid skew from uneven node placement, each physical node is represented by V virtual nodes (vnodes). Ketama (last.fm, 2007) uses 160 vnodes per server with MD5 as the ring hash^[10:1].

Jump consistent hash (Lamping and Veach, Google, 2014)^[12] replaces the ring with a 5-line closed-form function. Zero memory overhead, O(ln N) per lookup, better balance than ring hashing on random buckets. Downside: assumes sequentially numbered buckets, so removing an arbitrary server is awkward.

Rendezvous hashing (HRW) (Thaler and Ravishankar, 1996)^[13] assigns a key to the node with the highest hash(key, node). O(N) per lookup, but stateless and naturally supports weighted nodes. At N > 1,000 physical nodes, the CPU cost becomes noticeable.

Each physical node appears as 100-160 vnodes on the ring. A key walks clockwise to the nearest vnode to find its owner. Adding Node D inserts new vnodes and moves only ~1/N of keys.

Production choice: mcrouter uses Ketama consistent hashing^[7:1]. Redis Cluster uses a fixed 16,384-slot hash ring with CRC16^[9:1]. Twemproxy supports both Ketama and modular hashing with auto-eject on failure^[14].

Hot keys and cache stampedes#

A hot key is one key whose QPS exceeds a single shard's capacity. A cache stampede (thundering herd) happens when a popular key expires and N concurrent callers all miss and hit the origin simultaneously.

The stampede problem: a key serving 500K reads/sec expires. All 500K clients miss. All hit the origin. The origin's per-partition limit (3,000 RCU on DynamoDB, ~100K QPS on MySQL) is exceeded by orders of magnitude. Cascading failure follows.

Defense 1: Leases (Facebook, NSDI 2013). On a miss, memcached hands the first requester a 64-bit lease token and tells subsequent clients "try again in a few milliseconds." Only the leaseholder reads the DB and back-populates the cache. A delete of the key invalidates outstanding leases, preventing the stale-write race^[1:1][2:4].

Defense 2: Singleflight (client-side coalescing). N in-process threads asking for the same key are funneled through a single in-flight call. The groupcache/singleflight package implements this in about 65 lines (the Do method itself is roughly 20)^[15]; Go's golang.org/x/sync/singleflight is a longer, feature-richer variant that adds DoChan and Forget. Limitation: only coalesces within one process. A fleet of 10,000 processes still stampedes the origin.

Defense 3: Probabilistic early expiration (XFetch). Each reader rolls a dice on every hit. With a small probability that grows as TTL approaches zero, the reader refreshes the value before it formally expires^[16]. Memcached's meta protocol exposes this via the N and R flags: mg key v N30 R10 grants a recache win if remaining TTL is under 10 seconds^[8:1].

The first caller wins the lease and refreshes. Singleflight coalesces concurrent in-process misses into one DB call. Subsequent clients share the result without additional origin load.

Hot-key mitigation beyond stampedes: Shadow the hot key across M shards (post:123:0 through post:123:M-1). Readers pick a random suffix. Writers update all M copies. Netflix EVCache achieves this naturally because the client replicates on write and reads from the local zone^[3:1][17].

Eviction policies beyond LRU#

When memory fills, the cache must choose which key to drop. The choice directly impacts hit rate, which directly impacts origin load.

LRU (Least Recently Used): evicts the key accessed longest ago. O(1) via doubly linked list + hash map. Good default on recency-skewed workloads. Thrashes on scan-heavy traces: a single full-table scan evicts the entire working set^[18].

LFU (Least Frequently Used): tracks access frequency. Better for Zipfian workloads where a small set of keys is accessed repeatedly. Bias problem: a key popular yesterday but cold today stays cached because its count is high.

W-TinyLFU (Caffeine, 2015): pairs a small LRU admission window with a TinyLFU frequency filter built on a 4-bit count-min sketch (8 bytes per entry)^[19]. The sketch counts are periodically halved to age out stale frequencies. A segmented LRU main region holds admitted items. W-TinyLFU achieves near-optimal hit rates across database, search, OLTP, and loop traces while using substantially less memory than ARC^[18:1].

ARC (Adaptive Replacement Cache, IBM): maintains two LRU lists (recently seen, frequently seen) plus two ghost lists of evicted keys. Self-tuning without workload-specific knobs. Downside: patented by IBM, and ghost lists effectively double the metadata memory requirement^[18:2].

Production reality: Memcached uses per-slab-class LRU with HOT/WARM/COLD/TEMP sub-chains^[5:3]. Redis offers 10 eviction policies including allkeys-lfu and volatile-lfu^[4:1]. Caffeine (JVM) uses W-TinyLFU and is the default in-process cache for Spring, Micronaut, and many JVM services^[18:3].

Real-World Example#

Facebook memcache (Nishtala et al., NSDI 2013) is the canonical production distributed cache. At publication, the fleet handled billions of requests per second across trillions of items^[1:2]. Each memcached instance served ~1M gets/sec^[2:5]. A 99% hit rate reduced MySQL read load by 100x; a 1% drop doubled DB load^[2:6].

The architecture is look-aside: memcached sits beside MySQL, not in front of it. Writes go to MySQL, then the app deletes the cache key. Each region has multiple memcached clusters (front-end pools). A shared regional pool holds less-popular keys to avoid per-cluster replication waste. A Gutter pool absorbs traffic for failed nodes without overloading survivors^[2:7].

mcrouter is the userspace proxy that ties it together: connection pooling, multi-key get fan-out, prefix-based namespace routing, shadow traffic to test clusters, and failover to Gutter. At peak, mcrouter handles ~5 billion requests per second across Facebook and Instagram caches (per the project README, circa 2019)^[7:2].

Netflix EVCache runs 22,000 server instances across 4 regions and 200 clusters, serving 400M ops/sec against 2 trillion items totaling 14.3 PB^[3:2]. The client library is topology-aware: writes fan out to all AZ replicas in the local region; reads pick the same-AZ replica to avoid cross-AZ data transfer cost. Cross-region replication uses metadata-only Kafka events (key + TTL, no value), a reader in the destination region that fetches the value locally, and a REST writer in the target region. SQS handles retries. Netflix reports 30M replication events/sec globally with 35% bandwidth savings from Zstandard batch compression^[3:3].

Netflix EVCache cross-region replication: metadata-only Kafka events avoid flooding the bus with 14 PB of values. The reader fetches locally and pushes compressed batches cross-region.

Trade-offs#

The single biggest meta-decision: Memcached vs Redis. Memcached is the right answer for pure caches where data is regenerable, items are simple blobs, and you want predictable tail latency with minimal per-item overhead (~50 bytes)^[5:5]. Redis is the right answer when you need rich data structures (sorted sets, streams, HyperLogLog), optional persistence, or cluster-managed failover. Do not use Redis Cluster as a system of record: replication is asynchronous, and writes can be lost during partition^[9:4]. AWS MemoryDB exists for people who want Redis API with durability (multi-AZ transactional log, single-digit ms writes, microsecond reads)^[20].

Scaling and Failure Modes#

At 10x load (100M ops/sec):

• Memory-bound: add nodes. Consistent hashing moves only 1/N of keys per addition.
• Hot keys saturate individual shards. Mitigation: shadow keys across M shards, client-side L1 cache with short TTL.
• Network becomes the bottleneck before CPU on memcached (1M ops/sec x 1 KB = 8 Gbps per node).

At 100x load (1B ops/sec):

• Client-side connection count explodes. Proxy layer (mcrouter) multiplexes thousands of app connections onto a few persistent server connections^[7:3].
• Cross-region replication lag increases. Mitigation: read-local-write-all (EVCache pattern)^[3:6].

At 1000x load (10B ops/sec):

• Facebook-scale. mcrouter already handles ~5B req/sec^[7:4]. Architecture shifts to multiple regional clusters with shared pools for cold data and per-cluster pools for hot data.

Failure modes:

• Node failure (no replication): keys on that node miss until the origin repopulates them. Consistent hashing redistributes load to remaining nodes. A Gutter pool (Facebook) absorbs the spike^[2:8].
• Node failure (replicated): Redis Cluster promotes a replica via gossip-based election within NODE_TIMEOUT * 2^[9:5]. Writes acknowledged by the failed primary but not yet replicated are lost.
• Network partition: Redis Cluster's "last failover wins" can cause write loss. The minority-side primary continues accepting writes that will be discarded when the partition heals^[9:6].
• Slab calcification (memcached): workload shifts from small to large items; the large-item slab class runs out while small classes hold unreusable memory. Enable slabs automove 1^[5:6][8:2].

Common Pitfalls#

Follow-up Questions#

Exercise#

Exercise 1: Hot-key mitigation design#

Your Redis Cluster has 100 shards, each rated at 100K ops/sec. A celebrity post causes post:12345:likes to receive 500K reads/sec. Design the mitigation path using shadow keys, client-side coalescing, and a promotion strategy. Decide: when to promote, how to detect the heat is gone, and what happens to writes during the promotion window.

Key Takeaways#

• Consistent hashing is non-negotiable. Modulo hashing causes near-total cache miss storms on topology changes. Pick ring-based (Ketama) or jump hash and make it boring.
• LRU is fine for most workloads. W-TinyLFU is a clear win when the working set is large and Zipfian, but adds complexity.
• Hot keys are the hardest real problem. Every production cache has stories. Have a shadow-key promotion path ready before you need it.
• DELETE-on-write, not SET-on-write. Concurrent writers are commutative under delete. This single decision prevents an entire class of permanent-stale-data bugs.
• The client library is the part you maintain most. It knows topology, handles failover, coalesces requests, and routes multi-gets. Pick one (or fork one) and own it.
• Redis Cluster is not a system of record. Async replication means write loss during partition. Use MemoryDB or a separate durable store for non-regenerable data.

Further Reading#

• Scaling Memcache at Facebook (NSDI 2013). The single most important paper on operating a distributed cache at planet scale; covers leases, gutter pools, cold-cluster warm-up, and cross-region invalidation.
• Redis Cluster specification. Canonical reference for 16,384 hash slots, gossip protocol, MOVED/ASK redirection, and failover semantics.
• TinyLFU: A Highly Efficient Cache Admission Policy. The frequency-sketch paper that beats LRU on almost every workload; the basis for Caffeine's W-TinyLFU.
• Building a Global Caching System at Netflix. 400M ops/sec, 14.3 PB, Kafka+SQS cross-region replication, 35% bandwidth savings from Zstandard compression.
• Optimal Probabilistic Cache Stampede Prevention (PVLDB 2015). The XFetch paper proving that probabilistic early refresh is optimal under certain assumptions.
• A Fast, Minimal Memory, Consistent Hash Algorithm. Lamping and Veach's jump consistent hash in 5 lines of code; zero memory, O(ln N) lookup.
• Why Pelikan (Twitter, 2019). A field report on what breaks with Redis and Twemcache at Twitter scale: fragmentation, unpredictable expiration, OOM kills.
• Caffeine Efficiency wiki. Ben Manes's comparative hit-rate plots across ARC, LIRS, W-TinyLFU on Wikipedia, Search, Database, and OLTP traces.

Flashcards#

References#