Q66 — Design a distributed cache (like Redis or Memcached)

What the system must do

A distributed cache stores key-value pairs in memory for fast access, shared across multiple application servers. The goal: sub-millisecond reads, horizontal scalability, and high availability. This is the infrastructure that every other design in Part 12 depends on.

Core operations: GET(key) → value, SET(key, value, TTL), DELETE(key)

Non-functional requirements:

Sub-millisecond P99 latency for reads and writes
Horizontal scalability (add nodes to increase capacity)
High availability (node failure doesn't lose all cached data)
Eviction (bounded memory — when full, evict according to a policy)

Why an in-memory key-value store is fast

Before designing, understand what makes Redis fast. Data is in RAM — no disk I/O on the read path. Redis is single-threaded for command processing (recent versions use I/O threads + a command thread) — no lock contention. Data structures (sorted sets, hashes, lists) are highly optimized C implementations. A Redis GET on a local node takes ~50 microseconds end-to-end including network.

The challenge: a single Redis instance is bounded by one machine's RAM (typically 64–256GB in practice). To cache more data than fits on one machine, you must distribute across multiple nodes.

Distributing data across nodes — consistent hashing

With N cache nodes, you need to know which node holds a given key. Naive approach: node = hash(key) % N. Problem: when N changes (node added/removed), almost all keys remap to different nodes — the entire cache is invalidated. This is the same problem as in Q34.

Consistent hashing (Q34) solves this: place nodes on a hash ring, each key maps to the first node clockwise from its hash. Adding/removing a node only remaps keys that were between the added/removed node and its neighbor — O(1/N) of the keyspace is remapped.

Virtual nodes (vnodes) ensure even distribution: each physical node has 150–300 virtual positions on the ring, preventing hot spots.

The client library (Redis Cluster's client, or a smart proxy) knows the ring topology and routes each GET/SET directly to the correct node — no proxy hop.

Redis Cluster — the production model

Redis Cluster partitions data across nodes using hash slots, not pure consistent hashing. There are 16,384 fixed hash slots. Each key maps to a slot: slot = CRC16(key) % 16384. Each node is responsible for a range of slots. This is equivalent to consistent hashing with fixed virtual slots.

When you add or remove a node, you migrate slots (and their data) from existing nodes to the new configuration. Migration is gradual — the cluster continues serving traffic during the move.

Cluster topology: 3 primary nodes (each holding a shard of the 16,384 slots) + 3 replica nodes (one replica per primary). Each replica asynchronously replicates from its primary.

A write goes to the primary for the slot. Reads can go to replicas (with possible staleness) or to the primary (always fresh). Redis Cluster defaults to reading from primaries for consistency.

Replication and availability

Every primary has one or more replicas. Replication is asynchronous — the primary acknowledges the write to the client before the replica has applied it. This means:

In normal operation: reads from replicas may be slightly behind (milliseconds)
On primary failure: the replica promotes itself (automatic failover via Raft-like election). Data written after the last replication sync is lost — a small window of data loss is accepted for performance

If you need zero data loss: use synchronous replication (WAIT command — wait until N replicas acknowledge before responding to client). This increases write latency. The trade-off between performance and durability is explicit.

Eviction policies

The cache is memory-bounded. When RAM is full, Redis must evict entries to make room for new ones. Eviction policy is a configuration decision that determines which entries are removed:

LRU (Least Recently Used): evict the key that has not been accessed for the longest time. Good default for general caching — keys that nobody has accessed recently are probably not hot.

LFU (Least Frequently Used): evict the key accessed the fewest total times. Better for workloads where recency matters less than access frequency — a key accessed once yesterday vs. a key accessed 1,000 times last week.

allkeys-lru / volatile-lru: allkeys means all keys are eviction candidates. volatile means only keys with TTLs set are candidates — keys without TTLs are never evicted (useful for pinned data).

noeviction: reject writes when full. Forces the application to handle the error.

Redis's practical LRU is an approximation (samples 5 random keys and evicts the LRU among them) — exact LRU tracking is expensive; approximate LRU is almost as good.

Cache stampede and thundering herd protection

When a popular cache entry expires, all concurrent requests for it miss and simultaneously hit the database — the thundering herd (Q19). The database gets N parallel queries for the same data.

Solutions:

Probabilistic early expiration (PER): before the TTL expires, with a small probability proportional to time-to-expiry, recompute the cached value. One request starts refreshing while others still hit the cache. The probability ramps up as expiry approaches. No thundering herd at expiry time.

Mutex/lock on cache miss: on a miss, only one request acquires a lock and fetches from the DB; others wait for the lock and then get the freshly populated cache value. Implemented with SET key_lock ... NX PX 5000 (Redis SETNX — set if not exists with TTL). Simple, effective. The waiting requests add latency but the DB only takes one hit.

Cache invalidation strategies

When the source of truth (the database) is updated, stale cached data must be handled.

TTL-based invalidation: every cache entry has a TTL. Stale data is accepted for up to TTL seconds. Simple, no active invalidation needed. Appropriate when brief staleness is acceptable (product prices, user profiles).

Write-through invalidation: on every database write, explicitly delete or update the cache key. Cache is always fresh (or empty). More complex — the write path must update both DB and cache. If the cache update fails, you get temporary inconsistency (DEL is usually safer than SET for invalidation — forces the next read to recompute).

Event-driven invalidation: database changes publish events (CDC/outbox — Q49) to Kafka. A cache invalidation service consumes events and deletes the relevant cache keys. Decoupled, eventual consistency, but adds latency between DB update and cache invalidation.

The mental model

code

Why fast: data in RAM, optimized data structures, single command thread (no contention)

Distribution: consistent hashing → key maps to node deterministically
  Redis Cluster: 16,384 hash slots, each key → slot → node
  Adding nodes: migrate slots, minimal key remapping

Replication: primary (writes) + replicas (reads, failover)
  Async replication: fast but small data-loss window on primary failure
  Sync replication (WAIT): no data loss, higher write latency

Eviction (when RAM full):
  LRU: evict least recently accessed → good general default
  LFU: evict least frequently accessed → better for frequency-based workloads
  allkeys vs volatile: all keys eligible vs only keys with TTL

Cache stampede:
  All misses hit DB simultaneously on expiry
  Fix: mutex (SETNX lock) or probabilistic early expiration

Cache invalidation:
  TTL: accept staleness for up to N seconds — simple
  Write-through DEL: delete on every DB write — fresh but coupled
  Event-driven: CDC → Kafka → invalidation service — decoupled, eventual

Redis Cluster topology:
  3 primaries (shards) + 3 replicas (HA)
  Client routes GET/SET directly to correct shard node
  Automatic failover on primary failure (replica promotes)

Designing a distributed cache means solving four problems in concert: where does each key live (consistent hashing), what happens when nodes fail (replication and failover), what happens when memory is full (eviction policy), and how do you handle stale data (invalidation strategy). Each decision has a trade-off between consistency, performance, and operational complexity.