Distributed Cache

Assume the primary database contains 10 TB of logical data, but product traffic is skewed: about 20 percent of the dataset accounts for most reads. Average cached value size is 2 KB including serialized payload. Keys and metadata add roughly 20 percent overhead, and allocator fragmentation plus eviction structures add another 15 percent.

Assume peak demand is 5 million reads per second and 250 thousand writes or invalidations per second across the service. Each cache node has 64 GB RAM, but only 48 GB is treated as safe usable cache capacity after reserving memory for the OS, replication backlog, buffers, and headroom. Each primary shard has one replica in the same region.

Hot data target: 10 TB x 20 percent = 2 TB of value bytes.

Memory overhead: 2 TB x 1.35 = 2.7 TB effective primary memory after key metadata, per-entry bookkeeping, allocator fragmentation, and eviction structures.

Usable node memory: 64 GB physical RAM minus OS, buffers, replication backlog, and safety headroom leaves about 48 GB. Primary shard count is 2.7 TB divided by 48 GB = 56.25, so choose 57 primaries or round to 64 for operational simplicity.

Replication: one same-region replica per shard makes the resident footprint about 5.4 TB and the fleet about 114 nodes. If two replicas are required for critical sessions, multiply the primary fleet by 3.

Throughput check: 5M reads per second divided by 100K reads per second per node = 50 serving nodes. Since the memory estimate already needs 57 primaries, the design is memory-bound. Add replicas can serve reads when consistency allows, raising read capacity while increasing write replication cost.

The primary index is the node-local hash table keyed by the exact cache key. For TTL cleanup, nodes may maintain a min-heap, timing wheel, or sampled expiration dictionary. For LRU, the linked list is not an index but an O(1) ordering structure. For LFU, use compact counters with decay so old popularity does not dominate forever.

Keys are independent. The only relationship is operational ownership: a key maps through the consistent-hash ring to a primary shard and one or more replica shards. Multi-key operations are difficult because keys may live on different shards, so they should be avoided or constrained with hash tags when necessary.

This design is a specialized NoSQL key-value store. Redis provides richer data structures, optional durability with snapshots or append-only files, scripting, streams, pub-sub, and Redis Cluster hash slots. It is excellent when the application benefits from server-side data structures but can be more complex to operate at very high memory density.

Memcached is intentionally simpler: opaque values, TTL, approximate LRU, no built-in persistence, and a multithreaded architecture optimized for high-throughput ephemeral caching. It is a strong fit when the cache is purely a performance layer and the database is always authoritative.

Naive sharding with hash(key) modulo N looks simple, but changing N remaps most keys. If 10 nodes become 11, almost every key changes modulo result, causing a massive cold-cache event and database spike.

Consistent hashing places both keys and nodes on a circular hash space. A key belongs to the first node clockwise from the key hash. Adding a new physical node claims only the ranges between its virtual-node positions and their previous owners, so roughly 1 divided by N plus 1 keys move. Removing a node moves only its ranges to neighboring owners.

Virtual nodes improve balance. Instead of one point per machine, each physical node owns many positions on the ring, such as 100 to 1000. This smooths random hash variance, supports weighted capacity by assigning larger machines more virtual nodes, and makes rebalancing more granular.

In interviews, call out the operational detail: clients must include a ring version or epoch. During resharding, the cluster may temporarily serve both old and new owners, proxy moved keys, or use dual reads. The goal is to minimize moved bytes and avoid simultaneous cache misses for the entire fleet.

Eviction decides what to remove when memory is full. Exact LRU uses a hash map for O(1) key lookup and a doubly linked list ordered by recency. On every hit, move the entry to the head. On eviction, remove from the tail. This is easy to explain and works well when recently used items are likely to be used again.

LFU tracks frequency and protects repeatedly accessed items from scans that would evict hot data under LRU. It needs decay, otherwise an item popular last week can live forever. Production LFU is often approximate because exact counters for every access are expensive and can add contention.

TTL eviction removes expired entries first and is mandatory for freshness. Random eviction is simple and surprisingly acceptable for some workloads, but it wastes memory under skewed traffic. Size-aware eviction is useful when large values can crowd out many small hot entries.

Redis-style approximate LRU samples a small number of keys and evicts the least recently used among the sample rather than maintaining a perfectly ordered global list. Approximation reduces per-access overhead and lock contention while delivering nearly the same hit ratio for many workloads.

The best answer ties policy to workload: sessions often use TTL plus noeviction or controlled eviction, product objects use TTL plus LRU, recommendation features often use LFU, and negative cache entries need short TTLs to avoid hiding newly created data.

Cache invalidation is hard because the cache and database are separate systems. Cache-aside is the most common pattern: read cache first, load from database on miss, populate cache, and on write update the database then delete or update the cache. It is simple and keeps the database authoritative, but stale reads can happen between database write and cache invalidation.

Write-through sends writes through the cache layer, which updates the backing store before acknowledging. This improves cache freshness and simplifies reads, but it increases write latency and couples cache availability to write availability.

Write-back or write-behind acknowledges once the cache accepts the write, then asynchronously flushes to the database. It is fast and can batch writes, but losing the cache node before flush risks data loss unless there is a durable write-ahead log. This is usually inappropriate for ordinary ephemeral caches unless explicitly designed as a buffered storage layer.

Write-around writes directly to the database and does not populate the cache. It avoids polluting cache with rarely read data, but the first subsequent read misses. This is good for bulk imports or write-heavy objects with low immediate read probability.

A senior answer mentions ordering. Use versions or update timestamps so a delayed invalidation cannot delete a newer value. For high-risk keys, prefer delete-on-write plus short TTL over update-in-place because the next read reloads from the source of truth.

Each shard has a primary that accepts writes and one or more replicas that receive a mutation stream. Asynchronous replication keeps write latency low, but replicas can lag. If clients read from replicas, they may see stale values or miss recently written values.

Failover promotes a replica when the primary is unhealthy. The control plane must fence the old primary with epochs so split brain does not create divergent values. Clients refresh topology and route writes to the promoted primary. Some misses are expected while the fleet converges.

For consistency, expose a small set of modes rather than pretending all reads are strongly consistent. Primary reads are fresher but concentrate traffic. Replica reads improve availability and throughput but are eventual. Quorum writes and reads can improve consistency but usually add too much latency and complexity for a cache.

Replication is also a capacity tool. Hot read keys can be served from multiple replicas, or deliberately copied to all nodes in a local region. The tradeoff is more memory usage and harder invalidation. Do this only for keys proven to be hot and small.

A hot key is a single key receiving disproportionate traffic. Even with perfect shard balance, that key maps to one shard and can saturate CPU, NIC, or lock paths. Mitigations include read replicas, local in-process caching, splitting counters into subkeys, and explicitly broadcasting tiny hot objects to multiple nodes.

Thundering herd happens when many requests miss the same key at once, often after TTL expiry or node restart. Request coalescing lets only one request fetch from the database while the rest wait or serve stale data. This is one of the highest-value cache protections in real systems.

Use TTL jitter so related keys do not expire simultaneously. For example, a nominal 10 minute TTL can be randomized between 8 and 12 minutes. For very hot keys, refresh asynchronously before expiry and allow stale-while-revalidate so users keep getting a slightly old value while one worker refreshes.

Protect the database with miss budgets, per-key locks, circuit breakers, and fallback behavior. A cache should fail soft; it should not multiply database traffic during an outage.

Cache penetration is repeated requests for keys that do not exist in the database. Without protection, every request misses the cache and hits the database. Negative caching stores a short-lived marker for not found results, reducing repeated database work while limiting the risk of hiding newly created records.

Bloom filters can reject impossible keys before the database lookup when the keyspace is well-defined. They trade small false positives for no false negatives. This works well for product ids, user ids, or content ids loaded from a known catalog.

Cache avalanche is a large synchronized drop in hit ratio, often caused by many expirations, a bad deployment flushing key prefixes, or a shard failure. Use staggered TTLs, warmup jobs, admission control, per-service miss limits, and progressive rollouts for invalidation jobs.

Also protect against oversized or unbounded keys. A few huge values can cause eviction churn and network spikes. Enforce maximum key length, maximum value size, compression only above a threshold, and separate pools for workloads with very different value sizes.

Use an in-process cache for ultra-low latency small working sets, but it duplicates memory per application instance and is hard to invalidate globally. Use a CDN for static or edge-cacheable content. Use database read replicas or materialized views when freshness and query semantics matter more than sub-millisecond key-value access. Use a full key-value store when durability and range operations are required.

Do not use a distributed cache as a bandage for unbounded queries, missing database indexes, or data that must be strongly consistent on every read. Avoid it when the working set is too large and too uniform to produce a meaningful hit ratio, or when the operational team cannot safely handle failover, eviction, and invalidation.