Back to System design

Design a Distributed Cache

medium
Scale: 100K-1M ops/s per node; <1ms p99 Storage: RAM × N nodes; cluster total = working set Meta (Memcached), Twitter, Netflix
Case StudyCachingSharding

A distributed cache pools the memory of many machines into one logical cache, fronted by clients that route via consistent hashing. Meta runs Memcached fleets in the tens of thousands of nodes ('Scaling Memcache at Facebook'). Twitter, Pinterest, Netflix run similar fleets.

Scale100K-1M ops/s per node; <1ms p99
StorageRAM × N nodes; cluster total = working set

Key Concepts

1
1. Sharding strategy. Client-side ketama (Memcached): client knows the ring, direct connect to owner shard — fewer hops, harder to evolve. Proxy (mcrouter, twemproxy, KeyDB): central control, easier rollout, extra hop. Redis Cluster: built-in slot-based partitioning (16384 slots), live rebalance.
1. Sharding strategy.
2
2. Replication is optional and policy-driven. Memcached has none — node loss means re-fetch from DB. Acceptable (cache data is by definition recomputable), but a cold cache after node loss hammers the DB. Redis Cluster supports primary + replica per shard, failover promotes replica. Multi-tier (local L1 + distributed L2): hottest keys served from in-process memory, never touch the network.
2. Replication is optional and policy-driven.
3
3. Eviction policies. LRU default — works for most. LFU better for skewed access. TinyLFU / W-TinyLFU best hit rate at small sizes (Caffeine, modern Memcached). Allkeys-LRU vs volatile-LRU (Redis): evict any key vs only TTL'd keys. Pick based on whether your cache should honor TTLs strictly.
3. Eviction policies.
4
4. Hot keys are the production pain. Single key (celebrity profile, viral post) saturates one node. Detect with top-K (Misra-Gries, count-min sketch). Replicate hot key across N nodes; load-balance reads. Client-side micro-cache in app process (10-30s TTL). Sharded counter: write to many sub-keys, sum at read time.
4. Hot keys are the production pain.
5
5. Cross-region and cold-start. Caches are typically per-region. Cross-region sync usually costs more than a regional DB miss. For session tokens, use globally distributed KV (DynamoDB Global Tables) instead. Cold start: shadow traffic from old cluster or persistent Redis (AOF) before switchover. References: Meta TAO, Twitter Twemcache, Netflix EVCache, Pinterest's multi-tier.
5. Cross-region and cold-start.

Related Problems

Caching Strategies: Cache-aside, Write-through, Write-backeasySharding Strategies: Range, Hash, Directory, GeomediumDesign a URL Shortener (TinyURL / bit.ly)mediumDesign Twitter / News FeedhardDesign WhatsApp / Chat Systemhard

High-level design

Client → (proxy?) → consistent-hash route → shard.
Per-shard: in-memory store (Memcached / Redis).
Optional per-shard replica for HA.
Client SDK handles retry, failover, batch fetch.
Hot-key detector emits alerts; load balancer for replicated hot keys.
Cold-start: shadow traffic from old cluster or replay from persistent log.

Components

  • Client library with consistent hashing + retry.
  • Cache nodes (Memcached, Redis).
  • Optional proxy layer (mcrouter, twemproxy, KeyDB).
  • Hot-key detector (top-K with Misra-Gries or count-min sketch).
  • Metrics: hit rate, evictions, memory, latency, hot-key alarms, slow-log.
  • Capacity planner: sizing by working-set estimate.

Sharding strategies

Client-side ketama: small, fast, no extra hop; harder to evolve.

Proxy-based (mcrouter, twemproxy): central control, easier rollout, extra hop.

Redis Cluster: built-in sharding, supports failover, slot-based partitioning (16384 slots).

Hash slot rebalance: live; small fraction of keys move.

Eviction policies

LRU (Least Recently Used): default; works for most workloads.

LFU (Least Frequently Used): better for skewed access; ignores recency.

TinyLFU + W-TinyLFU: best hit rate at small sizes; used in Caffeine, Memcached recent versions.

Allkeys-LRU vs volatile-LRU (Redis): evict any key vs only TTL'd keys.

FIFO: simple, rarely best.

Random: surprisingly OK for some workloads; zero metadata overhead.

Trade-offs

Client routing: efficient; protocol evolution requires client updates.

Proxy routing: easier to evolve; extra hop and cost.

Replication: better availability, eventual consistency in cache.

Memcached: simpler, smaller per-key overhead, no persistence.

Redis: data structures (lists, sets, sorted sets, streams), persistence (RDB, AOF), pub/sub.

Hot keys are the most common production pain. Detect early; mitigate before it becomes a crisis.

Real-world references

  • Meta Memcached fleet: tens of thousands of nodes; published 'Scaling Memcache at Facebook' paper.
  • Twitter Twemcache: heavily tuned Memcached fork with segmented LRU.
  • Netflix EVCache: Memcached + cross-AZ replication + warm-up via CDN-like push.
  • mcrouter: Meta's open-source Memcached proxy.
  • Redis Labs / Redis Enterprise: hosted Redis Cluster + multi-region active-active CRDTs.