Distributed Cache

Most designs use a cache; this one asks you to build it — a distributed, in-memory key-value store that many clients read and write with sub-millisecond latency, holding more data than any single machine's RAM. It's a rare "build the infrastructure" question, and it's really a tour of the fundamentals: Consistent Hashing, eviction, and replication, assembled into one system. It's the inside view of Redis.

1. Requirements

Functional:

• get(key), set(key, value, ttl), delete(key).
• Values expire (TTL) and evict under memory pressure.
• Capacity exceeds one machine — data spreads across many nodes.

Non-functional:

• Fast — sub-millisecond, in-memory.
• Scalable — add nodes to grow capacity/throughput.
• Available — a node failing shouldn't lose the whole cache or take it down.
• It's a cache: a lost entry is a miss (re-fetch from source), not a disaster — so we trade durability for speed.

2. One node: an in-memory map

A single cache node is a big in-memory hashmap: key → value, with each entry carrying an expiry. get/set/delete are hashmap operations — trivially fast. The interesting design is everything around scaling that beyond one box.

3. Partitioning across nodes: consistent hashing

Data exceeds one machine's memory, so partition keys across nodes. The naive hash(key) % N is a trap: add or remove a node and N changes, remapping almost every key — a catastrophic cache-wide miss storm. The fix is Consistent Hashing: place nodes on a hash ring and route each key to the next node clockwise. Adding/removing a node remaps only 1/N of keys, not all of them.

hash ring:  node A ── node B ── node C ── (wraps) ── A
key → hash(key) → walk clockwise → owning node
add a node → only keys between it and its predecessor move

Use virtual nodes (each physical node placed at many ring positions) so load spreads evenly and a removed node's keys redistribute across all survivors rather than dumping onto one neighbour.

4. Eviction

RAM is finite, so when a node fills, it must evict. The policy matters:

• LRU (least recently used) — evict the entry unused longest. The common default; good for typical access patterns.
• LFU (least frequently used) — evict the least-accessed; better when some keys are perennially hot.
• TTL — entries also expire by time regardless of use.

LRU is implemented with a hashmap plus a doubly-linked list (move to front on access, evict from the tail) — O(1) per operation.

5. Replication and availability

If a node dies, its slice of the cache vanishes. Pure caches sometimes accept that (misses just re-fetch from the source of truth). For better availability, replicate each partition to a replica node; on primary failure the replica takes over. This is a CAP choice: cache replication is usually async (AP) — you favour availability and speed over perfectly consistent replicas, because a slightly stale cached value is acceptable.

6. Client routing

How does a client find the node for a key? Either a smart client that knows the ring and routes directly (one hop, fast — how Redis Cluster works), or a proxy layer in front that routes. Smart clients avoid an extra network hop; the cluster must gossip membership so clients learn when nodes join/leave.

7. Deep dives

• Hot keys: one viral key overwhelms its owning node no matter the partitioning. Mitigate by replicating that key to multiple nodes, or a tiny client-side local cache for the hottest keys.
• Resharding: adding capacity moves 1/N of keys; with virtual nodes this is smooth and incremental.
• Consistency on write: write-through, write-around, or write-back to the backing store — a trade-off between freshness and write latency (Caching).
• Thundering herd on miss: many clients missing the same key at once stampede the source — use a lock/single-flight so one fetch repopulates it.

What to emphasise

Make consistent hashing the centrepiece, then eviction and the availability trade-off:

"Each node is just a fast in-memory map with TTLs; the real design is scaling past one box. I partition keys with consistent hashing on a ring with virtual nodes, so adding or removing a node only remaps 1/N of keys instead of the whole cache — avoiding a miss storm. Each node evicts with LRU when memory fills. For availability I replicate partitions asynchronously, which is an AP choice appropriate for a cache since a stale or missing entry just means a re-fetch. Clients route directly via knowledge of the ring to avoid an extra hop, and I'd handle hot keys by replicating them across nodes and single-flighting misses to avoid stampedes."

Next up: Online Auction — concurrent bids and a hard closing time.