Design a Distributed Cache

Prompt

"Design a distributed in-memory key-value cache that many services inside the company can share. Think Memcached or Redis, but you own it."

Clarifying questions

• What is the access pattern: read-heavy or mixed? Read-heavy. Assume roughly 20 reads per write.
• What sizes are keys and values? Keys are short strings under 256 bytes. Values are opaque blobs, typically 1-10 KB, capped at 1 MB.
• Is it a cache or a store? Can we lose data? A cache. Losing an entry is acceptable; serving a stale entry for a bounded window is acceptable. Callers must handle misses.
• Do we need TTLs? Yes. Per-key TTL, default a few minutes, max a day.
• Is strong consistency between replicas required? No. Read-your-writes on the node you wrote to is nice to have; cross-replica staleness of a few hundred milliseconds is fine.
• Single region or global? Start single-region, then discuss multi-region as a follow-up.
• What latency budget do callers have? Sub-millisecond p50, under 5 ms p99 inside the data centre.

Requirements

Functional

• get(key), set(key, value, ttl), delete(key); batched mget is a strong nice-to-have.
• Entries expire by TTL and are evicted under memory pressure.
• Clients can find which node owns a key without a central lookup on every call.

Non-functional

• Latency: p99 under 5 ms for single-key operations.
• Availability: losing any single node must not take the cache down, and must not cause a stampede on the backing store.
• Elastic: adding or removing nodes should move only a small fraction of keys.

Back-of-envelope

• Assume 200 internal services, aggregate peak of 2 million requests per second (RPS) against the cache.
• Read:write is 20:1, so about 1.9 M reads/s and 100 K writes/s.
• Working set: say 50 million distinct hot keys x 4 KB average value = 200 GB of live data. Add ~30% overhead for key strings, hash table slots, LRU pointers and TTL metadata: about 260 GB.
• Bandwidth: 2 M ops/s x 4 KB = 8 GB/s aggregate, which is 64 Gbit/s. That is far too much for one host, so the design is sharded from the start.
• Node sizing: with 64 GB usable RAM per node, 260 GB needs 5 nodes; add replication factor 2 and headroom, so plan for 12-16 nodes. Each node then serves about 150 K ops/s and ~4-5 Gbit/s, comfortable for a single-process event-loop server.
• Storage per year is not meaningful here: data is in-memory and expires. Memory per node and egress per node are the numbers that matter.