Stackbook Logo
← Back to System Architectures

Designing a Distributed Cache

Design a horizontally scaled in-memory cache with consistent hashing, replication, eviction and stampede protection for millions of requests per second.

4 min read

A distributed cache sits between applications and slower stores, absorbing read traffic with sub-millisecond latency. Memcached and Redis Cluster are the familiar examples. This article designs one from scratch.

Requirements

Functional

  • GET, SET (with TTL), DELETE and atomic increment on string keys.
  • Values up to 1 MB, most under 10 KB.
  • Configurable eviction when memory is full.

Non-functional

  • 1 million reads per second and 100K writes per second at peak.
  • p99 latency under 2 ms within a region.
  • 99.99 percent availability; losing a node must not lose the whole dataset's availability.
  • Elastic scaling: add or remove nodes without invalidating most keys.
  • A cache is not the source of truth, so eventual consistency with the database is acceptable.

Capacity estimation

Assume 500 million live keys averaging 2 KB including metadata: roughly 1 TB of hot data. With 64 GB nodes using about 48 GB for data, we need around 21 nodes; with one replica each, about 42. Network: 1.1 million operations per second at 2 KB is about 2.2 GB/s, or 18 Gbps across the cluster, easily under 1 Gbps per node.

High-level design

 App servers (smart client: ring + routing table)
      |  hash(key) -> shard
      v
 +-----------+   +-----------+   +-----------+
 | Shard A   |   | Shard B   |   | Shard C   |
 | primary   |   | primary   |   | primary   |
 | replica   |   | replica   |   | replica   |
 +-----------+   +-----------+   +-----------+
      ^                ^               ^
      +---- Config service (membership, health) ----+

Clients embed a library that holds the cluster map and talks to nodes directly, avoiding a proxy hop. A small configuration service (backed by Raft or ZooKeeper) tracks membership and pushes updates.

Data model

Each node holds a hash table from key to an entry: key bytes, value bytes, expiry timestamp, last access time and a version. Memory is carved into slab classes (64 B, 128 B, up to 1 MB) to avoid fragmentation. A separate min-heap or timing wheel tracks expirations.

Key deep-dives

Partitioning. Use consistent hashing with virtual nodes: each physical node owns about 256 points on a 64-bit ring. Adding a node moves only about 1/N of keys, and virtual nodes smooth load imbalance. Alternatively use fixed hash slots (16384 as in Redis Cluster) mapped to nodes, which makes rebalancing a matter of moving slots.

Eviction. LRU is the default; approximate LRU (sample five keys, evict the oldest) avoids a global linked list lock. LFU resists scan pollution for skewed workloads. TTL expiry runs lazily on read plus a background sweeper.

Replication. Asynchronous primary-replica copying keeps writes fast. On primary failure the config service promotes the most up-to-date replica within seconds. A small window of acknowledged writes can be lost; for a cache that is acceptable.

Cache patterns. Cache-aside is the default: read cache, on miss read the database and populate. Write-through updates both and suits read-heavy data needing freshness. Write-behind batches database writes but risks loss.

Hot keys. A single celebrity key can saturate one node. Mitigate with a small client-side local cache (a few seconds TTL), or replicate the key under suffixed names (key#1 through key#8) and read randomly.

Stampedes. When a popular key expires, thousands of requests hit the database. Defenses: request coalescing (one loader per key via a short-lived lock), probabilistic early refresh, and stale-while-revalidate where an expired value is served while one worker refreshes it.

Failure modes and trade-offs

  • Node loss: replicas promote; clients retry once against the new primary. Without replicas, the lost 1/N of keys simply miss and cause a database load spike, so the database must be sized for at least a partial cold cache.
  • Cold start: warm new nodes by replaying hot key lists or gradually shifting traffic.
  • Network partition: a stale client map may route to a demoted primary. Use epoch numbers on the map so nodes reject outdated routing.
  • Consistency: a race between a delete and a concurrent populate can leave stale data. Use short TTLs as a backstop, versioned writes, or delete-after-write with a delayed second delete.
  • Memory versus cost: more replicas improve availability and read throughput but double RAM spend.

Key takeaways

  • Use consistent hashing with virtual nodes or fixed hash slots so scaling moves only a fraction of keys.
  • Smart clients remove the proxy hop and keep latency low; a tiny consensus service owns membership.
  • Asynchronous replication is the right trade for a cache, which is a performance layer rather than a source of truth.
  • Plan explicitly for hot keys and stampedes; they cause more outages than raw capacity does.
  • Size the backing database for a partially cold cache, because cache failure is a database failure in disguise.