Design a Distributed Cache: Consistent Hashing, LRU and Hot Keys

The interface is intentionally small. Clients can store a value under a key and fetch it back later, and they can delete a key explicitly, typically when the underlying record in the database has changed and the cached copy is now wrong.

Every key can also carry a time to live so it disappears on its own after a chosen duration, which bounds how stale cached data can get. Finally, when memory runs out, the cache must make room by itself, discarding the keys that were used least recently. Persistence to disk, multi-key transactions and rich data structures are excluded; they matter for a full data store but distract from the core distribution problem.

Latency is the whole point. Reads and writes should complete in about 1 ms, because a cache that is not dramatically faster than the database is not worth operating. The system must scale horizontally, so that adding machines increases both memory and throughput without redesign.

It also needs to be highly available: losing one node should degrade capacity slightly, not take the cache offline and send every request to the database at once. To get that availability, we accept eventual consistency between a node and its replica. A replica that trails its primary by a few milliseconds is a reasonable price for a cache, since the database remains the source of truth.

Assume we want to hold about 1 billion keys averaging 1 KB each, roughly 1 TB of hot data. At peak the cluster serves around 1 million requests per second, and the overwhelming majority of them are reads rather than writes.

If each node offers about 64 GB of usable memory, 1 TB requires 16 primary nodes. Adding one replica per primary brings the cluster to 32 nodes. Spreading 1 million requests over 16 primaries gives each one about 62K operations per second, comfortably within what a single in-memory node can serve. The estimate makes an important point for interviews: memory capacity, not CPU, determines how many machines the cache needs, so sizing conversations should start from data volume.

The entities are the Key, the Value with its optional TTL, the Cache node that stores a slice of the data, and the Hash ring, which decides which node owns any given key. The ring is treated as a first-class entity because every client depends on having an up-to-date copy of it.

For clarity the operations are shown as REST: GET /cache/{key} returns the value or a 404 on a miss, PUT /cache/{key} stores a value with an optional ttl_seconds, and DELETE /cache/{key} removes it with a 204. A production cache would not use HTTP, though. It would speak a compact binary or text protocol over persistent TCP connections, similar in spirit to Redis's RESP, because at millisecond budgets the overhead of HTTP headers and parsing becomes significant.

Application servers talk to the cache through a client library that does the routing itself. It hashes each key, determines which node owns that portion of the key space, and sends the request directly there. This smart-client approach avoids a proxy hop on every operation.

Each primary node has a replica that receives a stream of its writes and can take over if the primary fails. A configuration service such as etcd or ZooKeeper tracks node health and publishes the current ring map, which every client keeps locally and refreshes when membership changes.

Reads follow the cache-aside pattern: on a miss, the application loads the record from the database and writes it into the cache for subsequent requests. Nodes do not coordinate with each other on ordinary reads and writes, so capacity grows almost linearly as machines are added.

The simplest placement rule is hash(key) mod N. It spreads keys evenly, but changing N remaps almost every key. Adding a single node to a 16-node cluster would make nearly the whole cache miss at once, and the resulting flood of database reads could take the database down. A central directory that records each key's location allows arbitrary placement, but it adds a lookup hop to every request and becomes a large, hot system of its own.

Consistent hashing avoids both problems. Nodes and keys are hashed onto the same circular space, and a key belongs to the first node found moving clockwise from its position. A newly added node takes over only the arc between itself and its predecessor, so with N nodes roughly 1/N of keys move; with five nodes, about a fifth.

A handful of points per server would leave arcs of very different sizes and uneven load. Giving each server around 150 virtual nodes scattered across the ring evens out ownership and spreads the work of rebalancing across many peers. Consistent hashing with virtual nodes is the choice, and the extra client logic is a small price.

Least recently used eviction can be implemented in constant time with two structures working together. A hash map points each key to its entry, giving O(1) lookup. A doubly linked list threads every entry in order of recency, with the most recently touched entry at the head and the stalest at the tail.

Every read moves the accessed entry to the head of the list, which takes only a few pointer updates because each node knows both of its neighbors. When a write arrives and memory is full, the entry at the tail is removed, since it has gone untouched the longest. In Java, LinkedHashMap constructed with access ordering and an overridden removeEldestEntry gives exactly this behavior in a few lines.

Expiry is handled two ways. Each read checks the entry's TTL and treats an expired key as a miss, and a background task periodically samples random keys and deletes those that have expired, so untouched keys do not linger. At very large scale, a Redis-style approximate LRU that samples a few keys and evicts the oldest saves memory over maintaining a perfect list.

Replication is asynchronous: the primary acknowledges a write immediately and streams it to its replica, which is typically only milliseconds behind. That keeps write latency low. When a primary stops sending heartbeats, the configuration service promotes its replica and distributes an updated ring map so clients redirect traffic within seconds.

Hot keys need separate treatment. Picture a celebrity profile receiving a million reads per second, all landing on one node. The first defense is a tiny in-process cache on each application server holding that value for a second or two. The second is to write several suffixed copies, such as key:1 through key:N, which hash to different nodes, and have readers choose one at random so the load is shared.

Finally, when a hot entry expires, thousands of requests can miss at the same moment and stampede the database. Allowing a single request to rebuild the value while the rest wait for its result keeps that spike contained.

Asynchronous replication keeps writes fast, but a failover can drop the last few writes the replica had not yet received; for a cache that is usually tolerable. A smart client removes the proxy hop, at the cost of every client needing to track the ring correctly. Approximate LRU uses less memory and CPU than an exact list, though it will not always evict the single oldest key.

TTL length is a dial between freshness and load. Long TTLs raise hit rates but serve staler data, while short TTLs keep data fresher and send more traffic to the database. The overall approach: place keys with a ring, evict with cheap bookkeeping, keep a replica for every primary, and spread out any key that gets too hot.