Design Distributed Cache

Three layers: smart client (caches hash-slot-to-node map, routes directly to the correct shard), shard cluster (each shard = leader + 1-2 replicas, owns a range of 16384 hash slots), and persistence layer (RDB snapshots + AOF log written to disk from each leader). Sentinel or the cluster's gossip protocol handles automatic failover. No single point of failure when configured with replicas.

(a) Hash-slot sharding. Redis Cluster divides the keyspace into 16384 slots. Each key maps to a slot via CRC16(key) mod 16384. Each shard (leader node) owns a contiguous range of slots. The client caches the slot-to-node map and routes commands directly -- no proxy needed.

On cluster rebalance (adding/removing nodes), slots migrate between shards. During migration, a client may receive a MOVED redirect (slot permanently moved -- update map) or ASK redirect (slot mid-migration -- retry once at new node). Smart clients handle both transparently.

# Hash slot calculation example
key = "user:42"
slot = CRC16("user:42") % 16384  # = 7218
# Slot 7218 falls in Shard B's range (5461-10922)
# Client routes SET/GET directly to Shard B leader

# Hash tags force related keys to same slot
"order:{user42}:history"  → CRC16("user42") % 16384
"cart:{user42}:items"     → CRC16("user42") % 16384
# Both land on the same shard — enables multi-key Lua scripts

(b) Eviction policies. When maxmemory is hit, Redis must evict keys to make room. Policies:

• volatile-lru -- evict least-recently-used among keys with a TTL set
• allkeys-lru -- evict LRU across all keys (most common for cache use)
• allkeys-lfu -- evict least-frequently-used (better for skewed access patterns)

Redis uses approximated LRU: sample N random keys (default 5), evict the one with the oldest last-access timestamp. Not true LRU (no linked list), but very close in practice and O(1) per eviction. Increasing the sample size to 10 gets within 1% of true LRU accuracy.

# redis.conf eviction settings
maxmemory 80gb
maxmemory-policy allkeys-lru
maxmemory-samples 10

(c) Persistence.

• RDB = point-in-time snapshot. Redis forks, child writes entire dataset to disk. Fast restore, but you lose all writes since the last snapshot on crash.
• AOF = append-only file. Every write command appended to log. Three fsync modes: always (safe, slow), everysec (lose ~1 s on crash -- recommended), no (OS decides).
• RDB+AOF hybrid (Redis 4+) = AOF rewrite starts with an RDB prefix (compact binary) followed by AOF tail of recent writes. Fast restore + minimal data loss. This is the default in Redis 7.

AOF rewrite. Over time, AOF grows large. Redis triggers background rewrite: forks a child process that writes a minimal set of commands to recreate the current dataset. Parent buffers new writes during rewrite, appends them after. Result: compact AOF, no downtime.

(d) Replication. Async leader-to-follower streaming. Leader sends write commands to all replicas after executing locally. On leader failure:

• Sentinel mode: external Sentinel processes monitor the leader. Quorum agrees leader is down, promotes a follower, updates clients.
• Cluster mode: replicas initiate a Raft-like voting process. Other leaders vote to elect one replica as new leader. No external process needed.

Full resync vs partial resync. When a replica reconnects after a brief disconnect, Redis attempts partial resync using the replication backlog buffer (a ring buffer of recent writes on the leader). If the disconnect was short and the backlog hasn't wrapped, only the missed writes are sent. If the backlog overflowed, a full resync is triggered: leader forks, creates RDB, streams entire dataset. This is expensive -- configure repl-backlog-size to at least 256 MB in production to minimize full resyncs.

sequenceDiagram
    participant C as Client
    participant SC as Smart Client
    participant L as Shard Leader
    participant AOF as AOF Log
    participant R as Replica

    C->>SC: SET user:42 "data"
    SC->>SC: CRC16("user:42") mod 16384 = slot 7218
    SC->>L: route to Shard B (owns 5461-10922)
    L->>L: write to in-memory hash table
    L->>AOF: append SET command
    L-->>C: OK
    L->>R: async replicate SET command
    R->>R: apply to memory
          

Cache-aside pattern (the most common Redis usage):

# Read path (cache-aside)
value = redis.GET(key)
if value is None:           # cache miss
    value = db.query(key)   # load from DB
    redis.SET(key, value, EX=3600)  # populate cache, 1hr TTL
return value

# Write path (invalidate on write)
db.update(key, new_value)   # write to DB first
redis.DEL(key)              # invalidate cache
# Next read will miss → refill from DB with fresh data

Why DEL on write instead of SET? If you SET the cache on write, a race between two concurrent writers can leave stale data in cache permanently. Consider: Writer A reads DB, Writer B reads DB, Writer B updates DB, Writer B writes cache, Writer A (with stale data) overwrites cache. Now cache is stale forever. DEL is safer: worst case, you get one extra cache miss.

Lua scripting for atomic multi-step operations:

-- Rate limiter: sliding window counter
-- KEYS[1] = rate limit key, ARGV[1] = window (sec), ARGV[2] = max requests
local current = redis.call('INCR', KEYS[1])
if current == 1 then
    redis.call('EXPIRE', KEYS[1], ARGV[1])
end
if current > tonumber(ARGV[2]) then
    return 0  -- rate limited
end
return 1  -- allowed

Lua scripts execute atomically on a single shard. No other command runs between lines. This is how Redis replaces what would otherwise require distributed locks or database transactions.

Every cache design decision is a tradeoff between latency, consistency, durability, and operational complexity. Here are the key ones:

• RDB vs AOF vs Hybrid. RDB: fast restores, periodic data loss. AOF: minimal loss, slower restores (replay entire log). Hybrid: best of both -- RDB prefix for speed, AOF tail for safety. Use hybrid in production.
• Cluster mode vs Sentinel. Sentinel: simpler, single logical instance, no sharding. Good to ~100 GB. Cluster: built-in sharding + failover, scales to TB. Choose cluster when data exceeds single-node RAM.
• Cache-aside vs Write-through. Cache-aside: app manages cache (read: check cache, miss = load DB + SET; write: update DB + invalidate cache). Write-through: cache layer intercepts all writes to DB. Cache-aside is simpler and more common; write-through has fewer stale reads but adds write latency.
• Redis vs Memcached. Memcached: multi-threaded, simple KV, no persistence, no pub/sub. Redis: single-threaded (I/O threads in 6+), rich data structures, persistence, pub/sub, Lua. Memcached wins on raw multi-core GET throughput; Redis wins on everything else.
• Approximated LRU vs true LRU. True LRU requires a doubly-linked list (memory overhead per key). Redis samples N keys and evicts the worst. With N=10, accuracy is within 1% of true LRU. Tradeoff: tiny accuracy loss for massive memory savings.
• Single-threaded vs multi-threaded. Redis is single-threaded for command execution (no locks, no races). Redis 6+ adds I/O threads for network read/write parsing, keeping the core single-threaded. Dragonfly goes fully multi-threaded with shared-nothing per-core architecture -- higher throughput, more complexity.
• Proxy vs smart client. Proxy (Twemproxy, Envoy): app connects to one endpoint, proxy routes. Simpler client, extra network hop (~0.2 ms). Smart client (Jedis, Lettuce): app caches slot map, routes directly. No extra hop, but client must handle MOVED/ASK. Production Redis Cluster uses smart clients for lowest latency.
• TTL-based expiration vs explicit invalidation. TTL: simple, eventually consistent, bounded staleness. Explicit invalidation: immediate freshness, but requires tracking all write paths. Best practice: use both -- active invalidation for correctness, TTL as safety net.

Caches fail in subtle ways. Unlike databases, a cache failure doesn't always throw an error -- it degrades silently (stale data, increased latency, DB overload). Understanding these modes is essential.

1. Start with the access pattern. "Read-heavy workload, cache-aside pattern, Redis as L2 between app and DB." This frames the problem correctly.
2. Name the sharding scheme. "CRC16 mod 16384 hash slots, client-side routing, MOVED/ASK redirects." Shows you know Redis internals, not just the API.
3. Explain eviction before they ask. "allkeys-lru with sample size 10. Approximated LRU, not true LRU -- the O(1) tradeoff." This is the detail that separates senior from mid-level.
4. Persistence is not optional. "RDB+AOF hybrid. RDB prefix for fast restart, AOF tail for sub-second data loss." Don't hand-wave "we'll use persistence" -- name the mode.
5. Address the thundering herd. Without prompting, mention cache stampede mitigation: lock-based fill, probabilistic early expiration, or background refresh. Shows production experience.
6. Know when Redis is wrong. "Above 100 GB per node, consider sharding more aggressively or using a disk-backed store. Redis is not a database replacement." Showing boundaries earns trust.

How cache architecture evolves as scale grows from a single app server to millions of requests per second across a global fleet.