Designing a Scalable Distributed Cache
A deep dive into engineering an elastic, fault‑tolerant distributed cache—covering requirements, partitioning, replication, eviction, failure handling, real‑world trade‑offs, and interview‑ready testing.
In interviews candidates often jump straight to “Redis + TTL”, but the real challenge is designing a cache that stays fast, consistent, and alive when nodes appear, disappear, or hot keys explode. The hidden trap is assuming a single‑node pattern scales linearly; without proper partitioning, eviction, and failure handling the system collapses under load. This guide uncovers the non‑obvious engineering decisions that turn a toy cache into a production‑grade, elastic layer.
01Defining functional & non‑functional requirements for a distributed cache
Start by quantifying the latency gap you need to close. If the backing database averages 120 ms per request, a cache should answer in <5 ms to be worthwhile—a 24× speedup. Next decide consistency: strong (read‑after‑write must see the latest value) or eventual (stale reads are acceptable). For a social‑feed you may tolerate a few seconds of staleness, but a checkout service needs strong guarantees. Scalability expectations translate into target QPS and node count; a 10 M ops/sec workload on a 12‑core machine will saturate at ~30 M ops/sec per core for Memcached under idealized, single-core synthetic benchmarks (per the Memcached site). In real-world deployments, network overhead, TCP context switching, and hardware constraints typically drag actual throughput down to 10–20% of this theoretical maximum. Finally, factor operational cost: managed services like AWS ElastiCache add ~30 % overhead but give automatic failover within 30 s (AWS docs). By writing these SLAs—latency ≤5 ms, 99.99 % availability, 70‑90 % DB load reduction (DigitalOcean study)—you create a decision surface that guides every later trade‑off.
02Partitioning the key space: consistent hashing vs rendezvous hashing
Both algorithms map a key to a shard, but their mechanics differ. Consistent hashing places nodes on a ring and hashes keys to the next clockwise node; adding a node inserts a new point, moving only keys that fall between its predecessor and itself—on average O(1/n) keys. Rendezvous (HRW) hashing computes a score for each node‑key pair and picks the highest; it guarantees the same key distribution variance regardless of node count, often yielding tighter balance. Worked example: Suppose three cache nodes A, B, and C with hashes 1000, 3000, and 7000 on a 0‑10000 ring. Key “user:123” hashes to 4200, so it lands on C. Add node D at 5000; only keys between 3000‑5000 move to D, reducing reshuffle. The Go implementation below demonstrates how to prototype a consistent hash ring using a sorted slice of node positions and binary search to find the next node clockwise, handling wrap-around correctly. If your workload shows hot‑key clustering, rendezvous can spread those keys more evenly because each key evaluates all nodes each time, at the cost of O(N) scoring per request. Choose consistent hashing when you need O(1) lookup and low rebalancing overhead; choose rendezvous when you have few nodes and want the lowest variance distribution.
package main
import (
"hash/fnv"
"sort"
)
type Ring struct {
nodes []uint32
hashMap map[uint32]string
}
func NewRing() *Ring {
return &Ring{hashMap: make(map[uint32]string)}
}
func (r *Ring) AddNode(node string) {
hash := r.hash(node)
r.nodes = append(r.nodes, hash)
r.hashMap[hash] = node
sort.Slice(r.nodes, func(i, j int) bool { return r.nodes[i] < r.nodes[j] })
}
func (r *Ring) GetNode(key string) string {
if len(r.nodes) == 0 {
return ""
}
hash := r.hash(key)
idx := sort.Search(len(r.nodes), func(i int) bool {
return r.nodes[i] >= hash
})
if idx == len(r.nodes) {
idx = 0
}
return r.hashMap[r.nodes[idx]]
}
func (r *Ring) hash(key string) uint32 {
h := fnv.New32a()
h.Write([]byte(key))
return h.Sum32()
}03Replication patterns and consistency trade‑offs
Four classic patterns appear in interviews: cache‑aside, read‑through, write‑through, and write‑behind. Cache‑aside reads from the DB on a miss and writes back only when the application updates; this reduces write amplification because writes go to the DB unless a miss occurs (Martin Fowler). Write‑through pushes every write to the cache and DB synchronously, guaranteeing the cache is never stale but doubling write latency. Write‑behind batches writes, improving throughput but risking data loss on crash. For multi‑node caches you add replication. A quorum model (e.g., 2‑of‑3) lets reads wait for a majority to return, giving strong consistency at the expense of higher latency. During a network partition, CAP forces you to sacrifice either availability or consistency; most caches choose availability and fall back to stale reads, using TTL or version tags to bound staleness. Worked example: With a 3‑replica shard, a write quorum of 2 means a write succeeds after any two replicas ack. If node C is partitioned, the write still succeeds (nodes A + B), but a read that only contacts C would return the old value. Adding version numbers to each entry lets the client reconcile divergent copies later.
import redis
import json
# cache‑aside write in Python
r = redis.StrictRedis(host='cache', port=6379, db=0)
def get_user(user_id):
key = f'user:{user_id}'
cached = r.get(key)
if cached:
return json.loads(cached)
# miss – fetch from DB (pseudo)
user = db_fetch_user(user_id)
r.set(key, json.dumps(user), ex=300) # TTL 5 min
return user04Eviction & expiration policies with real numbers
Caches must free space without hurting hot data. LRU evicts the least recently used entry in O(1) using a doubly‑linked list plus hashmap; LFU tracks access frequency, ideal for skewed hot‑keys but costs O(log N) per update if implemented with a [Heap and Priority Queue](/courses/heap-and-priority-queue). TTL provides time‑based expiry, useful for data that becomes stale predictably. Redis ships a matrix of policies (noeviction, allkeys‑lru, volatile‑lru, allkeys‑lfu, etc.). Worked example: Assume a 1 GB cache, average item size 10 KB → 100 k entries. A read‑heavy workload (80 % reads) has a hot‑key set of 5 k items accessed 70 % of the time. Using pure LRU, the hot set stays in memory, yielding an 85 % hit‑ratio. Adding a 5‑minute TTL to volatile keys (volatile‑lru) evicts stale cold entries faster, raising the hit‑ratio to 93 % (a typical observed improvement of 10–20% depending heavily on the specific workload trace, per Redis docs). The following Java snippet uses Guava to implement a hybrid cache with both size and time-based eviction, mirroring this approach. Choose LFU when the hot set changes slowly; choose LRU when recency dominates access patterns.
import com.google.common.cache.Cache;
import com.google.common.cache.CacheBuilder;
import java.util.concurrent.TimeUnit;
public class HybridCache {
private final Cache<String, User> cache;
public HybridCache() {
this.cache = CacheBuilder.newBuilder()
.maximumSize(100_000) // ~1GB assuming 10KB avg item size
.expireAfterWrite(5, TimeUnit.MINUTES)
.build();
}
public User get(String key) {
return cache.getIfPresent(key);
}
public void put(String key, User user) {
cache.put(key, user);
}
}05Failure handling, hot‑key stampede mitigation, and graceful degradation
A robust cache must survive node crashes and hot‑key spikes. Heartbeat probes (e.g., gossip or TCP ping) detect failures within seconds; the cluster then promotes replicas and re‑balances shards. For hot‑key stampedes—many clients miss the same key simultaneously—use request coalescing: the first request fetches from DB, others wait on a future/promise. A leaky‑bucket limiter can also throttle the DB fetch rate. Netflix’s EVCache combines these with a “cache‑aside with stale‑while‑revalidate” pattern: serve a stale entry for up to 30 s while a background refresh runs, preventing DB overload. During a full‑zone outage, switch the cache client to read‑only mode and let the application fallback to DB reads, accepting higher latency but preserving availability. Warm‑up new shards by pre‑loading the top‑N hot keys (e.g., top 1 % of traffic) to avoid cold‑start latency spikes after re‑sharding. The Java example below demonstrates a basic coalescing pattern using CompletableFuture.
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ConcurrentHashMap;
public class StampedeMitigation {
private final ConcurrentHashMap<String, CompletableFuture<String>> inFlight = new ConcurrentHashMap<>();
public CompletableFuture<String> get(String key) {
return inFlight.computeIfAbsent(key, k -> {
// Simulate DB fetch
return CompletableFuture.supplyAsync(() -> fetchFromDB(k));
});
}
private String fetchFromDB(String key) {
// Actual DB call
return "value_for_" + key;
}
}06Real‑world implementations: Redis Cluster, Memcached, EVCache, managed services
Redis Cluster shards data into 16 384 slots; each node owns a subset, and the cluster can hold up to 1 000 shards (Redis docs). Replication factor of 3 gives automatic failover, but cross‑slot operations require multi‑key transactions. These transactions are strictly limited because Redis Cluster requires all keys in a multi-key operation to hash to the exact same hash slot (enforced via hash tags like {user123}:profile), preventing cross-shard atomic operations. Memcached follows a single‑threaded per‑core model, achieving ~30 M ops/sec per core on modern hardware under ideal conditions (memcached.org); however, real-world performance varies significantly due to network latency and hardware differences. It lacks built‑in persistence, so you must accept data loss on crash. AWS ElastiCache adds Multi‑AZ replication with <30 s RTO, handling node replacement automatically (AWS). Google Cloud Memorystore offers similar managed Redis with automatic scaling but caps at 300 GB per instance. Netflix’s EVCache builds on Netflix OSS, using a custom client that retries on failures and aggregates metrics; it reports >99.9 % hit‑rate across >1 000 services (Netflix tech blog). Choosing between them hinges on operational budget (managed vs self‑hosted), required durability, and language ecosystem support.
07Interview‑ready testing, benchmarking, and presenting results
Before you pitch a design, back it with numbers. Use YCSB to generate a workload mix (e.g., 80 % reads, 20 % writes) and record 95th‑percentile latency, throughput, and cache hit‑ratio. Note that YCSB's standard redis binding requires explicit cluster-mode configuration (or a smart client proxy) to handle Redis Cluster's slot-based routing, as a simple host list will fail on cross-slot redirections. Simulate node loss by shutting down a shard and measuring how quickly the client re‑balances (Redis CLUSTER REBALANCE). Compare eviction policies by swapping Redis config between allkeys‑lru and allkeys‑lfu while keeping the same trace; a 5 % hit‑ratio lift often shows up for skewed workloads. Plot results in a table: Scenario, Latency 95p, Throughput, Hit‑ratio. When presenting, frame the numbers as a justification: “With a 5‑minute TTL + LRU we achieve 93 % hit‑ratio, cutting DB load by 85 % and meeting the <5 ms SLA.” This data‑driven narrative convinces interviewers that you can move beyond abstract diagrams to concrete performance evidence.
# Example YCSB run for a Redis cluster
./bin/ycsb load redis -s -P workloads/workloada -p redis.hosts=10.0.0.1:6379,10.0.0.2:6379 > load.log
./bin/ycsb run redis -s -P workloads/workloada -p operationcount=1000000 -p redis.hosts=10.0.0.1:6379,10.0.0.2:6379 > run.log
# Parse latency and hit‑ratio from run.log
awk '/Average/ {print $3}' run.log08Common interview questions
Note: The following answers are illustrative. Adapt them to the specific context and constraints of the interview question.
Design a globally distributed cache for a social‑media feed that must stay available 99.99 % under network partitions
Use an eventually consistent, multi‑region cache with write‑through and versioned keys; employ quorum reads for critical paths and fall back to stale reads with a short TTL when a region is isolated.
Compare cache‑aside, write‑through, and write‑behind for a high‑write e‑commerce checkout service
Cache‑aside minimizes write amplification (writes go only to DB), write‑through guarantees cache freshness at the cost of doubled latency, and write‑behind batches DB writes for throughput but risks data loss on crash; choose cache‑aside when write volume is high and occasional stale reads are acceptable.
Explain how you would prevent a cache‑stampede on a hot product‑detail key during a flash‑sale
Implement request coalescing so the first miss triggers a DB fetch while subsequent requests await the same future; optionally serve a stale entry with a short grace period (stale‑while‑revalidate) and rate‑limit DB calls with a leaky bucket.
Choose between consistent hashing and rendezvous hashing for a 10‑node cache cluster and justify the trade‑offs
Pick consistent hashing for O(1) lookup and minimal key movement when nodes join/leave (only O(1/n) keys shift). Choose rendezvous if you need the lowest variance in key distribution and can tolerate O(N) scoring per request, which is acceptable for a small 10‑node cluster.
Select an eviction policy for a read‑heavy analytics dashboard and quantify its impact on hit‑ratio
Combine LRU with a 5‑minute TTL (allkeys‑lru + volatile‑ttl). In a 1 GB cache with 10 KB items, this hybrid approach can raise hit‑ratio from ~85 % to ~93 %—a 10‑20 % gain—by evicting cold entries faster while preserving hot recency.