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?