Design a distributed cache

1. Clarify the requirements

Ask: Is this a look-aside cache in front of a database, or a primary data store? What's the value size? Do we need data structures (lists, sorted sets) or plain get/set? Is losing cached data acceptable? Single region or multi-region?

Functional requirements

• get(key), set(key, value, ttl), delete(key).
• Per-key TTL; eviction when memory is full.
• Cluster can grow and shrink without a full flush.

Non-functional requirements

• Latency: sub-millisecond p50 and a few milliseconds p99 inside a datacenter.
• Throughput: millions of operations per second across the cluster.
• Availability over consistency: a stale or missing value is acceptable; an unavailable cache shouldn't take the application down.

2. Estimates

Memory decides the node count, not CPU. That's typical for caches, and it's why value size and compression are worth asking about.

3. High-level architecture

Cache nodes are simple: an in-memory hash table, an eviction policy, TTL handling, and a network protocol. Keep them dumb and fast.

Cache clients (a library in each application server) hash the key, look up the owning shard in the cluster map, and talk to it directly. A config service backed by a consensus store (ZooKeeper, etcd) owns the cluster map, runs health checks, and pushes changes when nodes join, leave, or fail.

4. Partitioning

Use consistent hashing with virtual nodes. Each physical node owns many points on a hash ring; a key belongs to the first node clockwise from its hash. Adding or removing a node moves only about 1/N of the keys, instead of reshuffling everything as hash(key) mod N would. Virtual nodes smooth out the distribution and let bigger machines take more points. The details are in sharding and consistent hashing.

5. Data model and memory management

entry   key (bytes, ≤ 250 B), value (bytes, ≤ 1 MB), flags,
        expires_at, cas_version, lru_prev, lru_next

• Eviction: LRU via a doubly linked list per memory class, or sampled LRU (pick a few random keys, evict the oldest) to avoid list maintenance on every read.
• Expiry: lazy (check on read) plus a background sweep that samples keys, so expired entries don't hold memory indefinitely.
• Fragmentation: slab allocation (fixed-size chunk classes) avoids allocator fragmentation for many small values.
• Compare-and-set: a version number per entry lets clients update without lost writes.

6. Scaling and failure handling

• Replication. Each shard has a replica that receives writes asynchronously. On primary failure the config service promotes the replica and updates the cluster map. Asynchronous replication means a failover can lose the last few writes; acceptable for a cache.
• Hot keys. One celebrity key can saturate a single node. Detect hot keys (client-side sampling), then replicate them to several nodes and read from a random one, or keep a tiny in-process cache in the clients for the hottest few hundred keys.
• Cache stampede. When a popular key expires, thousands of requests miss at once and hammer the database. Use request coalescing (one request recomputes, others wait), a short lock key, or probabilistic early refresh before expiry.
• Node failure without replicas. The keys on that node become misses. Make sure the database can absorb a node's share of traffic, and add jitter to TTLs so mass expiry doesn't happen all at once after a restart.
• Multi-region. Usually one cache cluster per region, each populated from local reads, with invalidations broadcast across regions when the source of truth changes.

7. Trade-offs to call out

• Client-side routing vs proxy: fewer hops and no extra tier vs simpler clients and central control.
• Replication vs capacity: replicas double memory cost; skip them if misses are cheap.
• Consistency with the database: cache-aside with delete-on-write is simple but has race windows; write-through is more consistent but slower on writes. See caching strategies.
• AP over CP: during a partition, a cache should keep serving possibly stale data rather than refuse requests; see consistency models and CAP.

8. Common follow-up questions

1. How do you add a node without a spike in misses? Add it with a small weight (few virtual nodes) and ramp up, or warm it by copying keys from the nodes that are giving up ranges.
2. How do you invalidate a key cached in many places? Delete on write from the service that owns the data, publish invalidation events for other regions, and keep TTLs as a safety net.
3. What happens if the config service is down? Clients keep using their last known cluster map; membership changes pause, but traffic continues.
4. How do you monitor it? Hit ratio per key prefix, evictions per second, memory usage, p99 latency per node, and hot-key reports.
5. Would you build or use Redis/Memcached? In practice, use an existing engine and focus your design on partitioning, failover, and client behaviour; say that explicitly.