Design a Distributed Cache (Redis / Memcached)

L1: In-Process Cache (Caffeine / Guava)

An in-process L1 cache absorbs extreme read spikes directly inside application heap memory, eliminating network latency before requests reach a distributed Redis cluster. Multi-level caching, sharding, and eviction form the foundational mechanisms that interviewers examine.

• Zero-Hop Latency: Embedded directly within each application server JVM or process memory, delivering sub-0.1ms latency without network hops.
• Memory Footprint: Approximately 100 MB per instance to ensure cache allocations do not exhaust JVM heap or trigger garbage collection pauses.
• Bounded TTL: Short durations of 10 to 30 seconds limit staleness because the L1 cache does not receive synchronized push invalidations from Redis.
• Eviction Strategy: Window TinyLFU (used by Caffeine) maintains near-optimal hit ratios and outperforms classic LRU for skewed access patterns.
• Use Cases: Highest-frequency keys including dynamic configuration flags, active user sessions, and viral product catalog entries.
• Architectural Trade-off: Each application server maintains an isolated L1 cache, meaning updates can leave different instances returning divergent values until the short TTL expires. This eventual consistency is acceptable for read-heavy catalog data, but unsuitable for linearizable data models.

Request flow:
  1. Check L1 in-process cache. On hit, return value immediately (< 0.1ms)
  2. On L1 miss, check L2 distributed cache (Redis): on hit, return value and backfill L1 (< 1ms)
  3. On L2 miss, read from primary database: return value, populate L2, and backfill L1 (5-50ms)

Cache Client Library

Sub-millisecond read SLOs require an intelligent client library. Embedded directly within each application process, the client manages sharded routing, connection pooling, compression, and circuit breaking without proxy hops.

• Hash Slot Routing: For Redis Cluster, computes CRC16(key) % 16384, looks up the target node in its cached slot map, and transmits requests directly to the responsible master shard without proxy overhead. Custom consistent hashing deployments instead use the configured hash ring.
• Slot Map Cache: Stores the complete cluster slot-to-node topology in application memory, refreshing the table automatically upon receiving MOVED redirects or via periodic 60-second polling.
• Connection Pooling: Maintains persistent TCP socket pools of 10 to 20 connections per cache node, avoiding recurring TCP handshake and TLS negotiation overhead.
• Pipelining: Batches multiple commands into a single network round trip, reducing per-command overhead and network round trips during batch lookups.
• Compression: Automatically compresses payloads larger than 1 KB with LZ4 prior to transmission, reducing memory footprint and network bandwidth transparently.
• Circuit Breaker: Isolates failing nodes when five consecutive health checks fail, halting outbound requests to that instance for 30 seconds and falling back to the primary database or stale L1 data to prevent cascading thread starvation.
• Timeouts and Retries: Enforces a strict 2ms request timeout with a single retry, ensuring a lagging cache node does not block client threads.

Consistent Hashing: Data Distribution

Consistent hashing organizes keys and nodes onto a circular identifier ring, ensuring that scaling the cluster up or down reallocates only a minimal fraction of the total keys.

Why Simple Modulo Hashing Fails

Using naive modulo hashing where node = hash(key) % N causes nearly every key to remap whenever the cluster size N changes. Adding or removing even a single node invalidates approximately (N - 1) / N of cached entries, triggering a catastrophic cache miss storm that overwhelms the primary database.

Consistent Hashing Architecture

Consistent hashing projects both keys and physical nodes onto a continuous 32-bit circular ring spanning 0 to 2^32 - 1. Each key is assigned to the first node encountered moving clockwise from its hashed position. When a new node joins, it only assumes responsibility for keys located between itself and its immediate counterclockwise predecessor, which limits key remapping to roughly 1/N of the total keyspace. Similarly, when a node is removed or fails, only its local keys migrate to its clockwise neighbor, leaving the remainder of the cluster undisturbed.

Virtual Nodes (Vnodes)

To prevent hash skew where uneven node distribution creates hot shards, each physical node is assigned 100 to 200 virtual node positions distributed evenly across the ring. Virtual nodes smooth out key density across the cluster, ensuring that when a physical host fails, its workload disperses across multiple surviving servers rather than concentrating onto a single neighbor.

Ring positions:
  vnode_A1: 1000    vnode_B1: 2500    vnode_A2: 5000
  vnode_C1: 6000    vnode_B2: 7500    vnode_C2: 9000
  
  Key "user:123" hashes to 3000 -> assigned to vnode_A2 (position 5000)

In-Memory Storage Engine and Layout

Each cache shard maintains an in-memory hash table providing average O(1) time complexity for lookups, inserts, and deletes, paired with specialized memory allocators to prevent fragmentation under continuous write churn.

Core Storage Engine

The primary storage layer operates like an optimized C++ hash table (such as std::unordered_map). High-throughput hash functions like MurmurHash3 or xxHash minimize collision probability across keys. Collisions are resolved through separate chaining with linked lists or open addressing with Robin Hood hashing. To prevent latency spikes during table resizing, progressive incremental rehashing migrates entries across two internal tables in small increments when the load factor exceeds 0.75.

Memory Layout Optimization

Continuous allocation and deallocation of variable-length cache values can cause severe external memory fragmentation, leading to premature out-of-memory errors despite free RAM. Systems employ specialized allocators to maintain high payload density:

• Slab Allocator (Memcached Approach): Pre-allocates fixed 1 MB memory pages partitioned into uniform chunk classes (such as 64B, 128B, 256B, 512B, 1KB, up to 1 MB), placing each entry into the smallest fitting chunk class to eliminate external fragmentation.
• Jemalloc (Redis Approach): Utilizes an advanced general-purpose memory allocator with multiple memory arenas and fine-grained size bins, minimizing fragmentation while dynamically adapting to variable-length payloads without rigid chunk boundaries.

Eviction Policies and Lifecycle Management

When memory reaches provisioned capacity limits, an eviction policy determines which keys to discard to accommodate incoming writes. Selecting the right policy directly governs hit ratio stability under skewed or shifting access distributions.

Least Recently Used (LRU)

LRU evicts the entry that has gone unaccessed for the longest duration, optimizing for strong temporal locality where recently referenced data is likely to be queried again.

• Data Structure: Combines an O(1) hash map with a doubly linked list tracking access order.
• Read Updates: On a successful GET, the corresponding node is unlinked and spliced to the head of the doubly linked list.
• Eviction Execution: When memory is exhausted, the tail node representing the stalest key is evicted in O(1) time.

Approximated LRU (Redis Approach)

Strict LRU requires 16 bytes of pointer metadata (prev and next) per entry, which consumes gigabytes of RAM across hundreds of millions of keys. Redis avoids this overhead through probabilistic sampling:

• Sampling Algorithm: When memory exceeds maxmemory, the engine samples a configurable number of random keys (typically 5) and evicts the candidate with the longest idle time.
• Memory Efficiency: Sampling eliminates explicit linked-list pointers while approximating true LRU behavior within a few percentage points of accuracy.

Least Frequently Used (LFU)

LFU evicts keys with the lowest cumulative access frequency, making it ideal for power-law workloads where 20% of catalog keys drive 80% of read traffic. Unlike LRU, a one-off sequential table scan will not flush established hot keys from memory. Redis implements LFU using an 8-bit Morris logarithmic counter paired with configurable exponential decay, allowing historical popularity to decrease gradually so older items do not occupy cache memory indefinitely.

TTL-Based Expiration

Keys with an explicit time-to-live are reclaimed through a complementary pair of passive and active expiration mechanisms:

• Passive Expiration: Evaluates key expiration during read lookups, immediately deleting the expired record and returning a cache miss.
• Active Expiration: A background timer periodically samples a random batch of volatile keys (such as 20 keys ten times per second) and purges expired entries to reclaim RAM before client queries occur.

Replication and Failover Architecture

Replication decouples read scaling from write throughput while protecting cache availability during physical hardware failures.

Cluster Replication Model

Each primary shard coordinates with one or more asynchronous read replicas. Writes are executed on the primary shard and acknowledged immediately to preserve sub-millisecond latency, after which modifications stream asynchronously to replicas. Reads target the primary by default to ensure read-your-writes consistency, while read replicas can absorb offloaded queries for workloads that tolerate replication lag.

• Heartbeat Failure Detection: Shards exchange periodic gossip heartbeats to monitor node health and detect network partitions.
• Automated Replica Promotion: When a primary fails to respond within the configured timeout, surviving peers conduct an election to promote an eligible replica with the highest replication offset to primary status.
• Consistency Trade-off: Because replication operates asynchronously, an acknowledged write can be lost if the primary crashes before streaming updates to its replicas. In caching architectures, this brief window of data loss is acceptable because missing entries are backfilled on demand from the database.

Cache Coherence and Stale Write Protection

Cache-aside invalidation can race with concurrent reads when a database update and a cache refill execute concurrently. To maintain coherence, the application commits the database modification before invalidating the cached entry, and incorporates version numbers or monotonic timestamps into cache values. When refilling the cache after a miss, the client verifies that the database version is newer than the currently cached version before writing. For enterprise architectures requiring durable invalidation propagation across distributed regions, a transactional outbox or Change Data Capture (CDC) pipeline publishes versioned invalidation events to Kafka, providing durable and replayable delivery across cache clusters. If network delivery is delayed, the configured TTL bounds normal cache lifetime, subject to the cache expiration and serving policy.

• Commit-First Invalidation: Commit the primary database transaction before issuing cache invalidation requests to prevent premature cache repopulation with old data.
• Versioned Refill Guard: Attach version numbers to cached payloads to reject refill attempts where a slow concurrent read could overwrite newer committed data.
• Durable Invalidation Streaming: Propagate invalidation notices through an asynchronous change stream or CDC pipeline to provide durable and replayable delivery across regional cache clusters.
• Bounded TTL Fallback: Enforce an upper bound on cache lifespan so uninvalidated entries eventually expire even if network partitions interrupt pub/sub invalidation events.

Cluster Architecture (Redis Cluster Hash Slots)

Redis Cluster partitions the keyspace across 16,384 deterministic hash slots, providing clients with predictable routing across independent master shards without requiring a centralized proxy layer. This deterministic slot model contrasts with consistent hashing rings used by Memcached and Twemproxy topologies.

• Deterministic Hash Slots: The cluster divides the keyspace into 16,384 discrete slots distributed evenly across primary nodes. Clients compute CRC16(key) % 16384 to identify the responsible slot.
• Explicit Slot Allocation: Each primary master owns an assigned range of slots (for example, Node A manages slots 0 to 5,460, Node B manages 5,461 to 10,922, and Node C manages 10,923 to 16,383).
• Direct Client Routing: Smart client libraries cache the slot-to-node mapping locally, transmitting commands directly to the target primary socket without intermediary hops.
• MOVED Redirect Protocol: During cluster rebalancing or node migration, a contacted node that no longer owns the requested slot returns a MOVED slot target_ip:port response, instructing the client to execute the command on the new node and update its internal slot table.