Distributed Cache System Design Interview: Sharding, Eviction, and Hot Keys

Adding cache shards can improve total capacity while leaving the busiest key overloaded. A high hit rate can also hide stale answers, expensive misses, and a database that collapses when one node disappears. Distributed cache system design interviews ask you to separate ownership, capacity, freshness, and source protection. Start by declaring what can be lost and what must remain correct.

The five linked records below support different follow-ups; they do not predict your exact interview. Official Redis documentation establishes named product behavior. Workloads, timelines, and proposed protocols in this guide are original exercises rather than production measurements or candidate reports.

Define a disposable cache and its source of truth

For an original baseline, cache public product descriptions backed by a durable database. Reads may tolerate bounded staleness, but writes commit to the database. A cache node can disappear without losing the authoritative product record. Checkout prices and permission decisions require their own stronger contracts.

A cache stores a reusable copy or computed result to avoid repeating more expensive work. Its design must specify key identity, value size, expiration, eviction, and how readers obtain a trustworthy answer after a miss. Distribution adds ownership and failure boundaries to that local contract.

Keep tenant, locale, schema version, and other result-changing dimensions in the key where needed. Two requests with different permissions cannot share a response merely because they ask for the same object ID. A missing dimension is a correctness bug, not simply a lower hit rate.

Separate a stored absence from a failed lookup. Negative caching can protect the database for genuinely absent products, but caching a temporary upstream error as “not found” can prolong an outage. Declare the lifetime and invalidation behavior for each result class.

Choose a sharding contract you can explain

A client-side consistent hash ring maps keys to responsible nodes and minimizes movement under membership changes relative to naive modulo routing. Virtual nodes distribute ownership more evenly, but balance depends on value sizes and request frequencies as well as key counts.

Redis Cluster uses a different concrete scheme. Its official cluster specification defines 16,384 hash slots, assigned to primary nodes, with hash tags for colocating selected keys. Do not call this a virtual-node ring or assume every multi-key command can cross arbitrary slots.

Whichever scheme you choose, explain who publishes the routing version and how clients learn changes. A stale client may route to the old owner during migration. Redirects, retries, and bounded topology refresh must avoid infinite loops or replaying a non-idempotent write blindly.

For a disposable cache, migration can sometimes drop copied data and warm the destination from the source. That simplifies data movement but creates cold misses. Copying hot values reduces the burst at cutover, while dual ownership introduces invalidation and stale-value complications. State which trade-off your workload permits.

Prove why more shards do not split one hot key

In an original workload, 20,000 requests per second target many products, but one product receives 8,000 of them. Four shards can spread the remaining 12,000 requests. The shard owning that product still receives its 8,000 hot-key requests even if the keyspace becomes perfectly balanced.

Adding four more shards may move the hot key, but it does not divide that key's traffic. A virtual-node scheme changes ownership, not the granularity of one value. Measure per-key demand and per-shard utilization before concluding that resharding solves the incident.

For read-heavy public data, a local process cache or multiple read replicas can absorb requests. This creates more copies to invalidate and a staleness budget to enforce. A read replica is helpful only if its capacity, lag, and routing are acceptable for the chosen value.

For a hot mutable counter, duplicating the value across nodes requires a merge or coordination contract. It is no longer just a read cache. Ask whether the system can shard the underlying operation, batch updates, or return approximate values; do not apply a public-description solution to a strict balance or inventory counter.

Separate expiration, eviction, and invalidation

Expiration removes eligibility based on time. Eviction removes entries under a capacity policy. Invalidation removes or refreshes an entry after a source change. Each can cause misses, but only their combined contract determines freshness.

Official Redis eviction documentation explains memory limits and policies, including approximate LRU and LFU. Redis LRU samples candidates instead of maintaining the exact global ordering from a textbook linked-list cache. Discuss the installed product's policy rather than assuming the interview's local LRU implementation describes it.

A TTL does not establish a universal bound from database commit to last stale read. If an old reader writes stale data after a newer commit, its newly started TTL can extend stale visibility. Expiration bounds the lifetime of that stored copy under the chosen clock; it does not eliminate the write race.

Use eviction evidence that includes byte sizes, churn, rejected writes, and backend cost. A large cheap object can crowd out many small expensive ones. Hit rate alone treats those outcomes alike. Account for allocator overhead, replication buffers, and headroom rather than equating total RAM with value capacity.

Trace a stale fill after invalidation

Consider the original product P9, initially at version v1. Reader R misses the cache and reads v1 from the database. Writer W commits v2 and invalidates the cache. R then fills the cache with v1 after the invalidation.

Every step can succeed, yet the next reader sees stale data. “Write database, then delete cache” does not cover a fill already in flight. Delayed deletion can reduce the chance in some workloads, but a fixed delay is not a proof under unbounded scheduling or slow queries.

One proposed protocol maintains a durable or reliably retained invalidation generation for each key. R reads the generation before fetching; the writer advances it after commit; R fills only if its observed generation is still current. The generation comparison and fill must be atomic at the cache authority, and readers must define behavior while the writer's invalidation is pending.

A generation prevents this specific post-invalidation stale fill only when it advances before R's fill and is not lost. A failed invalidation still needs retry, detection, and a declared staleness bound. Do not label the protocol linearizable unless the database/cache coordination actually establishes that stronger property.

Protect the database during a stampede

A hot key expires, and hundreds of callers all fetch it from the source. The cache was protecting the database until expiration synchronized expensive work. Request coalescing, often called single-flight, lets callers share one in-progress fetch within its stated scope.

A per-process single-flight still allows one fetch from each application process. If that is too much, use a distributed refresh lease or another centralized admission mechanism. A lease coordinates refresh work; it does not automatically protect authoritative writes or eliminate stale fills.

Suppose worker A's lease expires while it is paused. Worker B acquires a new lease and fills v2; A resumes with v1. A must not overwrite B's result simply because it once owned the lease. Compare a fencing generation or version at the write boundary, and never let an old owner release a newer owner's lease.

TTL jitter spreads simultaneous expiration across different keys. It does not divide a single hot key's first refresh. Stale-while-revalidate can keep serving an old public description during refresh, but set both freshness and maximum stale limits. Some values are unsuitable for stale serving, regardless of its latency benefit.

Design shard failure as a load event

A cache shard disappears. The immediate challenge is not just reconnecting clients: its popular keys become misses, and the database sees a sudden new workload. Estimate how much source capacity is available before allowing every request to fall through.

For a teaching calculation, 10,000 requests per second with a 95% cache hit rate create roughly 500 source reads per second if every miss performs one read. A drop to 70% creates 3,000 source reads per second, six times the original load. The arithmetic assumes no coalescing, retries, or background refresh; name those assumptions.

Use bounded concurrency, deadlines, admission control, and circuit-breaking where appropriate. Prioritize necessary requests over speculative warm-up. An unlimited retry policy can turn a short cache outage into a sustained source outage even after the cache returns.

Warm the recovered shard gradually from the hottest eligible keys. Avoid scanning and filling the entire database while live misses compete for the same resources. A partial cache is an acceptable operating state for our disposable baseline; an unavailable source may require a declared degraded response instead of invented data.

Make local caching and security decisions explicit

A local cache reduces network demand for hot reads, but each application process now owns a copy. It needs invalidation, bounded lifetime, and a response to disconnected invalidation channels. The official Redis client-side caching reference describes server-assisted tracking and invalidation; application correctness still depends on handling its connection lifecycle.

A reconnect should not silently retain copies that missed invalidations unless their independent expiration contract allows it. Flush affected local state or resynchronize under a declared protocol. A cache hit is not useful if it bypasses a revoked permission or deleted object requirement.

Namespace tenant-specific keys and enforce authorization before exposing data. Encryption and private network access protect transport and deployment boundaries, but cannot repair a response cached under the wrong user scope. Key construction deserves a threat model alongside eviction and routing.

Version serialized values so a deployment does not interpret an old shape as the new one. Treat oversized values and decompression work as capacity risks. Bound them before insertion and before response processing to keep one pathological entry from exhausting a node.

Practise with failure traces and useful measurements

Practice question	What to practise
Scale the cache to a distributed system	Separate cache ownership from durability.
Consistent Hashing Ring with Virtual Nodes for Shard Rebalancing	Trace virtual-node movement and load skew.
Prevent a Cache Stampede on a Hot Key	Bound refresh concurrency for one key.
Plan Eviction and Cleanup for a Production Cache	Choose eviction from memory and workload evidence.
Handle cache-update conflicts in distributed services	Reproduce a stale-fill race and state the fix.

Track request hit rate, byte hit rate, source reads avoided, per-key concentration, eviction churn, fill latency, stale-response age, and source saturation. Segment these by shard and tenant. A healthy fleet average can hide one overloaded shard or one costly class of miss.

Test the P9 race with deterministic barriers: pause R after reading v1, commit v2, advance invalidation, then resume R. Assert the declared result for both an ordinary fill and the generation-protected alternative. Also expire a refresh lease before the old worker resumes and check that it cannot overwrite a newer fill.

During a shard-loss exercise, verify bounded database concurrency and successful recovery of acknowledged source writes. No cache-only test can prove those source guarantees. State whether the experiment uses a simulated source or a real staging database.

Start the distributed cache scaling prompt by naming the source of truth and tracing one hot key through expiry, refresh, and node loss. A convincing answer explains which failures the cache may absorb, which stale results the product accepts, and how the source stays available when the cache stops helping.

Sources and Further Reading

• Redis: Cluster specification and hash slots
• Redis: Key eviction and approximate LRU
• Redis: Client-side caching and invalidation

Primary references checked September 30, 2026. Proposed consistency protocols require their stated assumptions; they are not automatic guarantees of Redis or consistent hashing.