Designing a Distributed Cache Service: Redis Cluster Internals and Hot Keys

Every architecture diagram has a box labeled "cache," and most engineers' knowledge of the box stops at GET/SET/TTL. Design the box itself — a managed, multi-tenant, distributed cache service — and you inherit a concentrated dose of distributed systems: sharding, failover, memory management under adversarial workloads, and the one problem sharding fundamentally cannot fix.

Requirements

Sub-millisecond p99 GET/SET, clusters from 1GB to 10TB, scale out/in without downtime, survive node loss with bounded data loss (it's a cache — losing data is acceptable, losing the service is not), multi-tenant isolation.

Sharding: hash slots, not consistent-hash rings

Redis Cluster's design choice is worth copying and worth explaining: the keyspace maps to 16,384 fixed slots (CRC16(key) mod 16384), and slots are assigned to nodes in contiguous ranges. Compare with a raw consistent-hash ring:

• Rebalancing = migrate whole slots — a bounded, enumerable unit with a live-migration protocol (keys stream to the new owner; requests for mid-migration keys get redirected with ASK).
• Cluster topology is a small table (slot → node) that clients cache — a smart client goes straight to the right node, no proxy hop; on topology change it gets a MOVED redirect and refreshes.
• Virtual-node balancing comes for free — slots are the virtual nodes.

The general lesson: fixed logical partitions + a partition-to-node map beats hashing-to-nodes directly, because it turns rebalancing from "rehash the world" into "move slot 7,204." (Kafka partitions, Dynamo vnodes, and every shard-map service are the same idea.)

Replication and failover: what a cache may cheaply promise

Each slot range gets a primary + replica(s) with asynchronous replication — a failover can lose the last few milliseconds of writes, and for a cache that is the right trade (the source of truth is the database behind it; a lost cache write is a future cache miss, not lost data — say that sentence in the interview). Failure detection and promotion run on a gossip protocol: nodes ping each other, a majority marking a primary as failed triggers replica promotion. The subtle requirement is the majority — without it, a partitioned minority promotes its own primaries and you get split-brain: two primaries for one slot range serving diverging data. A cache tolerates brief divergence, but tenants observing rollback of their own writes file tickets; the quorum rule is what bounds the mess.

Memory: eviction is the product

A cache at capacity is always deciding what to forget; eviction policy is user-visible behavior, not an implementation detail.

• LRU is approximated, not exact: a true doubly-linked LRU list costs 2 pointers per key (24+ bytes of overhead per tiny key) and cross-thread contention on every touch. Redis samples K random keys and evicts the least-recent among them — 90% of the benefit, none of the bookkeeping. LFU variants resist scans (one table dump shouldn't flush your working set).
• TTL expiry is lazy + probabilistic: keys are checked on access, plus a background sampler; a billion keys cannot all carry precise timers.
• Fragmentation is the silent killer: allocator behavior under churning value sizes can leave 30% of RAM unusable; slab-class allocation (memcached) or active defrag (Redis) is the counter.

Multi-tenancy makes eviction political: per-tenant memory quotas with per-tenant eviction, or one noisy tenant's churn evicts everyone else's working set. Isolation of eviction pressure is as important as isolation of CPU.

Hot keys: the problem sharding cannot solve

Sharding distributes keys, not popularity. One viral post's counter, one flash-sale product's stock, one celebrity's profile — a single key doing 500K QPS lands on one primary, and adding nodes changes nothing: the ceiling is one machine's capacity for one key. This is the distributed-cache version of the hot-partition problem, and the mitigation ladder is a great interview sequence because each rung has a cost:

1. Detect: per-node top-K sketch (count-min) -> flag keys > threshold
2. Client-side micro-cache: hot keys cached in the app process for 1-5s
   (staleness budget bought for a 100-1000x load reduction)
3. Key replication: hot key copied to R nodes; reads pick a random replica
   (writes now fan out -> only for read-hot, write-rare keys)
4. Key splitting: counter:{k} -> counter:{k}:0..9, read sums shards
   (write-hot keys; reads pay the aggregation)

Note rung 2 is the highest-leverage and the most commonly forgotten: the best distributed-cache design includes the caller's memory as tier zero.

The evil twin — hot slot after a poor hash or a user:{id}:* multi-key pattern forcing co-location (hash tags) — is solved by re-slotting, which is why the slot map being movable (design decision #1) matters.

Failure modes that define the SLO

Thundering herd / cache stampede: popular key expires; 10K requests miss simultaneously and hit the database. Fixes: request coalescing (one fetch, others wait), stale-while-revalidate, TTL jitter so co-created keys don't co-expire. Cold start: a rebooted 500GB node serving 0% hit ratio can knock over the database it protects — warm from a replica or snapshot before taking traffic, and cap miss-path concurrency (the cache should shed rather than forward a stampede). A cache service's real SLO is arguably "maximum miss rate delivered to the origin," not its own latency.

Interview probe	Answer sketch
Why not strong consistency?	Doubles latency and halves availability to protect data whose truth lives elsewhere
Resize from 3 to 5 nodes live?	Slot migration with ASK/MOVED redirects; keys move slot-by-slot, no global pause
One key at 1M QPS?	Client micro-cache + replicate-for-reads or split-for-writes; sharding alone can't help
Cache vs database inconsistency?	TTL as backstop, CDC-driven invalidation as optimization, never write-back for data you can't lose

The through-line: a cache buys performance by promising less — async replication, approximate LRU, acceptable loss. The craft is in choosing precisely which promises to break and making the breakage boring.