Distributed Cache

Same startup, same engineer #4. Twelfth Monday.

Your CTO drops by. "Every service we've built now depends on caching. URL Shortener uses Redis. Instagram uses Redis + a graph cache. Netflix uses EVCache. We've been renting these caches from AWS ElastiCache. Time to understand how caches ACTUALLY work at scale so we can either buy properly or build our own. Ship a design in 12 weeks."

She pauses. "For context — Meta's TAO cache handles 10 billion reads per SECOND at 99.8%+ hit rate. Facebook's memcached fleet was famously scaled by Rajesh Nishtala and team from a few thousand nodes to serve every read on Facebook. Twitter built their own memcached fork. Netflix built EVCache. Discord runs one of the largest Redis clusters ever operated. When you understand these systems, you understand why 'just add Redis' isn't a joke — it's the single biggest lever for latency at every scale."

Here's the paradigm shift:

URL Shortener + Slack + Instagram + Twitter + Netflix + YouTube + WhatsApp + Dropbox + Uber + Payment System — each USED a distributed cache. None had to design one.

But if you're building the cache itself, the design pressures are completely different:
- Latency budget is 1-5ms max — every microsecond of overhead compounds across billions of ops/sec.
- Data is ephemeral by design — cache is not a database; it must tolerate loss.
- The bottleneck is the network, not the CPU — a modern in-memory KV can do 1M+ QPS per node; the socket bandwidth is what caps you.
- Hot keys will kill you — a viral tweet's like-count = ONE key getting 1M QPS. Uniform sharding doesn't help.

Meta's answer was to build TAO — a distributed graph cache with objects + associations, on top of MySQL. Reference: TAO SIGMOD 2013 paper. At its peak, TAO served 10 billion reads/second at 99.8%+ cache hit rate.

Facebook's memcached story — the Nishtala et al. paper "Scaling Memcache at Facebook" (NSDI 2013) — is the canonical distributed-cache paper. Read it if you interview for Meta. Reference: Scaling Memcache at Facebook (NSDI 2013).

The real 2024 numbers

• Meta TAO: 10B+ reads/sec, 99.8%+ cache hit rate, 500:1 read:write ratio (2021 benchmarks)
• Netflix EVCache: ~30 million ops/sec per cluster, ~30 clusters globally, ~2 PB total cache memory (Netflix Tech Blog: EVCache)
• Discord Redis: ~300 clusters × ~5 million ops/sec each = 1.5B ops/sec globally
• Redis Cluster max slots: 16,384 — the hash-slot number (Redis Cluster spec)
• Twitter: still runs a memcached fork (Twemcache) — even after moving many workloads to Redis
• AWS ElastiCache Redis: r6g.16xlarge = 419 GB, ~500K QPS — the workhorse instance type

Interview soundbite: "Distributed cache design is 4 primitives: (1) consistent hashing for shard placement, (2) replication for failure tolerance, (3) hot-key mitigation because 20% of keys get 80% of traffic, (4) client-server protocol optimization because network overhead > CPU at 1M+ QPS/node. Meta's TAO gets 99.8% hit rate at 10B reads/sec because every one of these is tuned. Naive 'add Redis' answers stop at (1)."

The whole journey at a glance

Every 10× in traffic surfaces a different bottleneck:

text
    ═══════════ DISTRIBUTED CACHE ACROSS 4 SCALES ═══════════

    L4 (10K QPS)       L5 (100K QPS)      L6 (1M QPS)              L7 (10B QPS Meta TAO)
    Redis single node  Redis Cluster      + hot-key mitigation     + graph-aware cache
    12 weeks · $500/mo 6 months · $10K/mo 18 months · $200K/mo     ongoing · $50M+/yr

    ┌────────┐         ┌────────┐         ┌── App tier ────────┐  ┌── Client-side L1 ────┐
    │  App   │         │  App   │         │  100+ pods         │  │  in-process cache    │
    │ pods   │         │ pods   │         └─┬──┬──┬──┬─────────┘  │  1ms latency         │
    └───┬────┘         └───┬────┘           │  │  │  │            └──┬──┬──┬──┬──────────┘
        │                  │              ┌─▼──▼──▼──▼─────┐        │  │  │  │
     ┌──▼───┐           ┌──▼──┐           │  Client-side   │    ┌───▼──▼──▼──▼──────────┐
     │ Redis│           │Redis│           │  hash + retry  │    │ Meta TAO regional     │
     │ 1    │           │Cluster           │  hedged reads  │    │ + follower cache      │
     │ node │           │ 6   │           └───┬──────┬─────┘    │ + read-through pattern│
     │ 16GB │           │shards│              │      │           └──┬──┬──┬──┬──────────┘
     │      │           │ + 6 │           ┌───▼──────▼───┐          │  │  │  │
     └───┬──┘           │reps │           │  Cache tier   │       ┌──▼──▼──▼──▼──────────┐
        │               └──┬──┘           │  40 primaries │       │ TAO leaders           │
        │                  │              │  + 40 replicas│       │ (per-shard consist.   │
        │                  │              │  cache.r6g.4xl│       │  hash + writes to     │
        │                  │              └───┬───────────┘       │  MySQL under)         │
     ┌──▼───┐          ┌───▼─┐            ┌───▼──────────┐        └──┬──┬──┬──┬──────────┘
     │Postgr│          │Postgr│            │Sharded MySQL │            │  │  │  │
     │(sourc│          │+ shar│            │(source of    │        ┌──▼──▼──▼──▼──────────┐
     │e of  │          │d PG  │            │ truth)       │        │ MySQL sharded        │
     │truth)│          │      │            │              │        │ (source of truth)    │
     └──────┘          └──────┘            └──────────────┘        │ + Manifold (S3-like) │
                                                                    └──────────────────────┘

    Bottleneck        Bottleneck          Bottleneck                Bottleneck
    Single node       Cross-shard         Hot key: 1 key            10B reads/sec at 99.8%
    memory limit +    aggregation +       gets 1M QPS →             hit rate needs graph-
    SPOF.             hot shard.          replicate hot keys       aware caching + async
                                          across N nodes.           write invalidation.

   Chapter 5      Chapters 6+6.5      Chapter 7+7.5              Chapter 8
   walks          walks through       walks through hot-key      walks through TAO's
   through        Redis Cluster       mitigation + hedged         graph-aware caching,
   L4 MVP         + consistent hash   requests + client L1        MySQL leader-follower,
                  + 16384 slots       cache                       and 10B reads/sec math

  Key insight: A cache is NOT a database. Data is ephemeral. Design pressures
  are latency + memory + hot-key mitigation. Meta's TAO at 10B reads/sec proves
  that with graph-aware caching + async write invalidation you can get 99.8%
  hit rate globally. Facebook's memcached paper (NSDI 2013) is the canonical
  read. If you name 4 primitives (consistent hash, replication, hot-key,
  client-server protocol optimization) you're L6+.

The same 4 tiers as clean architecture diagrams

L4 · 10K QPS · Redis single node · $500/mo · 12 weeks:

L5 · 100K QPS · Redis Cluster · $10K/mo · 6 months:

L6 · 1M QPS · Cluster + hot-key + hedged reads · $200K/mo · 18 months:

L7 · 10B QPS Meta TAO · graph cache + MySQL under · $50M+/yr:

Why every 10× breaks the architecture

1. Consistent hashing enters early. L4 = single node. L5+ = 16,384 hash slots distributed across N shards. Reference: Redis Cluster spec — 16K slots because that number gives good balance between granularity + gossip overhead.

1. Hot-key mitigation is the L6 signal. Uniform sharding fails when 1 key gets 1M QPS. Solutions: request coalescing (multiple concurrent reads share one backend call), replicate hot keys to N nodes (client picks random replica), client L1 cache (in-process, 1ms). Reference: Facebook memcached paper NSDI 2013 §3.

1. Graph-aware caching is the L7 lever. Meta's TAO doesn't cache KV — it caches OBJECTS (nodes) + ASSOCIATIONS (edges). This lets it answer "friends of friends who like X" in ONE cache lookup instead of N. That's how 10B reads/sec at 99.8% hit rate happens. Reference: TAO SIGMOD 2013 paper.

The 3 senior insights before we start Chapter 1

1. A cache is NOT a database. Every candidate says "we add Redis." Fewer explain that a cache is designed to LOSE data on failure and that the source-of-truth pattern (cache-aside vs write-through vs write-back) fundamentally changes correctness guarantees. Reference: Cache-aside pattern (Microsoft docs).

1. Hot keys are the L6+ interview probe. Uniform sharding doesn't help when 1 key gets 20% of traffic (Zipf's Law). If you can't name request coalescing + hot-key replication + client L1 cache you fail the L6 signal. Reference: Facebook memcached NSDI 2013 paper.

1. TAO is Meta's most-cited cache paper. Naming TAO signals L7 preparation. TAO is a graph-aware cache — nodes + edges — that lets Meta answer social-graph queries in one cache lookup. This is why Instagram feed can rank 10,000 candidate posts in <200ms. Reference: TAO SIGMOD 2013 paper.

Chapter map for the journey ahead

• Chapter 1 — Requirements (KV ops, TTL, atomic, cluster membership)
• Chapter 2 — Capacity estimation (10B ops/sec Meta reference, latency budgets)
• Chapter 3 — API design (GET/SET/DELETE, cluster discovery, gossip)
• Chapter 4 — Data model (in-memory hash table + slot map)
• Chapter 4.5 — Consistent hashing: 16K slots + virtual nodes
• Chapter 5 — L4 MVP: Redis single node. Works to 10K QPS
• Chapter 6 — L5: Redis Cluster + replication + client-side sharding
• Chapter 6.5 — Client-server protocol: RESP + pipelining + multiplexing
• Chapter 7 — L6: Hot-key mitigation, hedged requests, client L1
• Chapter 7.5 — Facebook memcached paper deep-dive (NSDI 2013)
• Chapter 8 — L7: TAO graph-aware caching + async write invalidation
• Chapter 9 — Failure modes: split-brain, cache stampede, invalidation lag
• Chapter 10 — Trade-off matrix (Redis vs Memcached vs DAX vs Hazelcast)
• Chapter 11 — Interview masterclass: 45-min mock, questions to ask
• Chapter 12 — Defense: the 20 hardest interview questions on distributed cache

Ready? Chapter 1 next: what did the CTO actually ask for?

The CTO said "ship a distributed cache design in 12 weeks." That sentence has ~200 different reasonable interpretations. Your first job — before you draw a single box — is to separate what you MUST build from what you MIGHT build later and what you WILL NOT build ever.

For a distributed cache, this decomposes cleanly.

Functional requirements (what the cache actually DOES)

The KV core — GET / SET / DELETE - GET key returns the value if present, nil if absent. p99 target: 1-3 ms LAN. - SET key value EX seconds stores with a mandatory TTL. Missing TTL is a bug; enforce at the client library level. - DELETE key removes; idempotent (deleting a missing key is not an error). - No range queries. No SQL. No secondary indexes. Every op is a single-key point op.

TTL support (the "not-a-database" difference) - Keys expire automatically. Redis uses probabilistic expiration + lazy expiration on GET. - TTL granularity: seconds is enough; millisecond TTL is a rare need. - Interviewer soundbite: "Every write must have a TTL. A missing TTL is a bug, not a shortcut." Miss this and you signal L4-thin.

Atomic operations - INCR / DECR for counters (view counts, rate limiters). - LPUSH / RPUSH / LPOP / RPOP for queues (Redis is a poor-man's queue at low scale). - MULTI / EXEC for multi-key transactions — only when keys hash to the same slot. This is the hash-tag detail. - Every atomic op runs on the primary of the owning shard. No cross-shard atomics.

Cluster membership (add/remove nodes gracefully) - Adding a node: existing shards' slots are re-mapped to the new node. Redis Cluster's CLUSTER SETSLOT MIGRATING/IMPORTING protocol handles this online. Migration is per-slot and streams keys. - Removing a node: slots migrate away first; then the node is decommissioned. Never remove a node while it still owns slots. - Node failure: the promoted async replica takes over automatically via gossip + quorum voting. ~5 s failover window.

Replication (each slot has 1 primary + N-1 replicas) - Async by default. Sync is available (WAIT command) but rarely used for cache workloads. - Replicas can serve reads with the READONLY hint — trades staleness for offloading the primary. - Replicas do NOT vote; only masters participate in the quorum for slot ownership.

Client discovery (client finds correct shard) - Client caches the slot → node map (CLUSTER SLOTS response) on start. - On MOVED response, client refreshes the map for the affected slot. - On ASK response (during migration), client retries against the target with an ASKING prefix. - Every cluster-aware library (ioredis, lettuce, go-redis) handles all three; never roll your own.

Non-functional requirements (what the cache MUST satisfy)

• p99 GET latency < 5 ms LAN. Non-negotiable — this is why we have a cache in the first place.
• p99 SET latency < 10 ms LAN. Slightly higher because writes wait for replication ack (even async).
• Availability: 99.99%. ~52 min/year — matches the DB tier's SLA.
• Throughput: 1M+ ops/sec cluster-wide. Linear scale by adding shards; per-node ceiling is network-bound.
• No data loss on single-node failure. Guaranteed by async replication + auto-failover, modulo the tiny replication-lag window.
• Read-your-writes within a session. A user should not "post something, refresh, and see the old value" — even for eventual-consistency semantics.

Out of scope (what the cache is NOT)

• Persistent storage. This is a CACHE. Data may vanish on OOM or reboot. If you need durability, you need the DB tier.
• Cross-region replication as a first-class feature. Cross-region belongs to a separate layer (invalidation broker, or the L7 TAO follower architecture).
• Complex queries. No JOINs, no aggregations, no full-text search. Every op is a single-key point op or an atomic on that single key.
• Strong global consistency. The cache is eventually consistent. Callers who need strong consistency go to the DB tier for that access.

Clarifying questions to ask the interviewer

Before you draw a box, ask:
1. What's the read:write ratio? (Cache is only a win if reads dominate. 1:1 workloads rarely benefit.)
2. What's the working-set size, roughly? (Drives whether one node or a cluster.)
3. Consistent hashing or random slot mapping? (Consistent hashing is the industry default; random is a red flag.)
4. Sync or async replication? (Async is correct default for cache workloads.)
5. What's the eviction policy — LRU, LFU, TTL, noeviction? (Never noeviction; that turns cache into failure.)
6. Client-side sharding or proxy-based? (Cluster-aware client is the industry default; proxy is a legacy pattern.)

The requirements → architecture map

Each requirement above maps directly to one design decision downstream:

If a candidate can walk this table unprompted, they have earned the L5 depth signal — before any diagram is drawn.