Designing a Distributed Cache

What you'll learn

• 1. Problem Statement

  Design a distributed in-memory caching system capable of storing 1TB of data, serving 100,000 requests per second with sub-10ms latency, and maintaining high availability across multiple nodes. The system must handle node failures gracef…

• Back-of-the-Envelope Estimation

  - 1TB data across nodes: if each node holds 64GB usable memory, we need ~16 nodes minimum - 100K requests/second: a single node can handle ~80K ops/sec (single-threaded event loop), so 2-3 nodes suffice for throughput alone - Replication…

• 2. Requirements

• Functional Requirements

  - SET(key, value, TTL) -- Store a key-value pair with optional time-to-live - GET(key) -- Retrieve value by key; return null/miss if absent or expired - DELETE(key) -- Remove a key-value pair explicitly - Support variable-size values (by…

• Non-Functional Requirements

  - Latency: 25% of sampled keys are expired, immediately repeat the scan - Prevents memory from filling with dead keys that nobody reads

• 4. Data Partitioning (Sharding)

  A single machine cannot hold 1TB of data or handle all traffic. We distribute keys across multiple nodes using a deterministic hash function.

• Basic Approach

  Problem with modulo hashing: When nodes are added or removed, almost every key remaps to a different node. Adding 1 node to a 10-node cluster remaps ~90% of keys, causing a massive cache miss storm (thundering herd to the database). This…

• 5. Consistent Hashing

• The Hash Ring

  Consistent hashing maps both nodes and keys onto a circular ring (0 to 2^32 - 1). Each key is assigned to the first node encountered moving clockwise from the key's position on the ring.

• Adding/Removing Nodes

  When a node is added, only the keys between it and its predecessor on the ring need to move -- roughly 1/N of total keys (where N is the number of nodes).

• Virtual Nodes

  With only a few physical nodes, the ring has uneven key distribution. Virtual nodes solve this by mapping each physical node to multiple positions on the ring. Why it helps: With 3 physical nodes and no virtual nodes, one node might own…

• 6. Replication

  Each primary node replicates its data to one or more replicas for fault tolerance.

• Replication Strategy

• Why Asynchronous Replication?

  - Synchronous replication would require waiting for all replicas before acknowledging the write -- increases latency from in your API process, and every stage below is a response to a specific pain that killed the previous stage. Walkin…

• Stage 1 — MVP: In-process cache in the API server

  The simplest thing that could possibly work. - A single API server (monolith) with an in-memory HashMap or LinkedHashMap acting as the cache. - A single relational database (Postgres) behind it. - One client (mobile or web) hitting the A…

• Stage 2 — Scale-out: A shared cache tier

  - API layer becomes stateless; N replicas behind an L7 load balancer. - In-process caches get pulled out into a single shared Redis (or Memcached) node. - Sessions and other transient state move to the same shared cache. - DB stays singl…

• Stage 3 — Bottleneck: How do you shard the cache without a re-hash storm?

  The first real distributed-cache problem is how to grow past one node's RAM without every capacity change invalidating almost every key. Naïve hash(key) % N sharding remaps ~90% of keys whenever you add or remove a node, and every remapp…

• Stage 4 — Second bottleneck: The hot-key / thundering-herd problem

  Sharding solves aggregate load, but it does nothing for skewed load. A distributed cache's most characteristic failure mode is a single key — a celebrity user, a viral post, a global config value — receiving 50k+ reads/sec while its assi…

• Stage 5 — Third bottleneck: Multi-region latency & cache coherence

  Once the service is global, the shared-Redis-cluster-in-one-region model breaks in a new way: a client in Frankfurt does a cache lookup, that lookup crosses the Atlantic to the us-east cluster, and you've just added 90ms of network laten…

• Stage 6 — Mature architecture

  A distributed cache that has survived Stages 3–5 looks like this: Key pieces to name if you're drawing this on a whiteboard: L1 near-cache in each API pod, L2 Redis Cluster per region with primaries + replicas per shard, a coordination s…

• Cost vs Complexity — When to Pick What

  | Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Cache tier | In-process LinkedHashMap | Single managed Redis / ElastiCache node | Redis Cluster per region + L1 ne…

• Migration Path (MVP → Enterprise)

  You don't build the Stage-6 architecture on day one — you migrate to it in the order the pain shows up. A realistic sequence: 1. Pull the cache out of process. Replace the in-process HashMap with a single Redis node. Cache-aside pattern;…

• 15. Multi-Region Cache Topology

  When scaling a cache globally across multiple data centers, a critical architectural decision is whether to shard the hot dataset across all DCs or fully replicate it within each DC.

• The Flawed Approach: Sharding Across Data Centers

  If you distribute 10B hot entries across 10 data centers (each DC holding 1/10th of keys), clients will frequently need to query remote DCs for cache lookups. This introduces cross-DC latency (50-200ms) on cache misses -- defeating the e…

• The Correct Approach: Full Replication Per Data Center

  Each data center maintains a complete copy of the entire hot dataset. This ensures every frontend reads from its local cache cluster with sub-millisecond latency. Trade-off: This uses 10x more servers than a sharded approach, but guarant…

• Consistency Across DCs

  - Writes go to the central database first - Database propagates updates to all DC cache clusters asynchronously - Maximum staleness window (e.g., 48 hours) controlled via TTL - 99.999% of reads hit fresh data (most updates propagate with…

• Capacity Estimation Pattern

  ---

• 16. Cache Warmup Strategies

  When a cache server restarts or a new node is added, it starts empty. Without warmup, every request becomes a cache miss, sending a burst of traffic to the database -- a thundering herd effect.

• Snapshot-Based Warmup

  Periodically persist the set of hot keys and their values to disk (similar to Redis RDB snapshots):

• Randomized TTLs During Warmup

  If all cached entries share the same TTL, they expire simultaneously -- causing a synchronized cache miss storm. Instead, add jitter: This technique applies both during initial warmup and during normal operation to prevent periodic "clif…

• Gradual Traffic Ramp

  For newly provisioned DCs or major cache rebuilds: 1. Route only 1% of traffic to the new cache cluster initially 2. As hit rate climbs (monitored in real-time), gradually increase traffic share 3. Reach 100% traffic only after hit rate…

• 17. Redis: Data Types and Practical Knowledge

  Redis is the most widely used distributed cache. Understanding its data model and features is essential for system design discussions.

• Core Data Types

  | Type | Description | Backed By | Use Case | |------|-------------|-----------|----------| | Strings | Binary-safe, max 512MB | Simple dynamic string (SDS) | Counters, session tokens, serialized objects | | Lists | Ordered by insertion,…

• Key Commands Quick Reference

• Sorted Sets Internals (Skip List)

  Sorted sets use a skip list combined with a hash table: - Skip list provides O(log n) insertion, deletion, and range queries - Hash table provides O(1) score lookup by member - Each node exists in multiple "lanes" (levels) for fast trave…

• Redis Persistence

  Redis is in-memory but supports disk persistence: | Strategy | Mechanism | Trade-off | |----------|-----------|-----------| | None | Pure memory, no persistence | Fastest; data lost on restart | | RDB (Redis Database File) | Periodic poi…

• Redis Common Use Cases in System Design

  | Use Case | Implementation | Why Redis | |----------|---------------|-----------| | Session Store | String with TTL per session | Sub-ms reads, automatic expiry | | Rate Limiting | Sorted set with timestamp scores | ZRANGEBYSCORE for sl…

• Rate Limiting with Sorted Sets (Sliding Window)

  This gives precise sliding-window rate limiting with O(log n) per operation.

• Redis vs Memcached

  | Feature | Redis | Memcached | |---------|-------|-----------| | Data structures | Strings, Lists, Sets, ZSets, Hashes, Streams | Strings only | | Persistence | RDB + AOF | None (pure cache) | | Replication | Master-replica with automat…

• Memory Footprint

  Use redis-benchmark for load testing, INFO memory for monitoring.