Distributed Cache (Redis-like)

What is being asked

Design a distributed cache like Redis or Memcached. Cover the single-node data structure, how keys are spread across nodes, and what happens on failure.

Requirements

Functional

• get, set with optional time to live, delete.
• Eviction when memory is full.

Non-functional

• Sub-millisecond operations.
• Scale to terabytes by adding nodes.
• Losing a node should lose little data and not take the cache down.

Design

1. On one node: a hash table gives constant-time lookup. For least-recently-used eviction, entries are also linked in a doubly linked list; each access moves the entry to the front, and eviction removes from the back. Both are constant time.
2. Expiry: check on access (lazy), plus a background task that samples keys and removes expired ones.
3. Across nodes: the key space is divided into hash slots, each owned by a node. The client hashes the key, looks up the slot's owner and talks to that node directly.
4. Failure: each primary has a replica that receives its writes asynchronously. When a primary is declared dead by a majority, its replica is promoted.

Key decisions and trade-offs

• Consistent hashing or hash slots. Plain hash mod N remaps almost every key when a node is added. Slots or a hash ring move only a small share.
• Eviction policy. LRU suits most workloads. LFU keeps frequently used items through a burst of one-off keys. Exact LRU costs memory per entry, so real systems approximate it by sampling.
• Asynchronous replication is fast but can lose the last writes on failover. For a cache this is usually acceptable.
• Single-threaded command execution avoids locks and is fast enough because the work is memory-bound; scale by adding shards.

Follow-up questions

• What is a cache stampede and how do you prevent one?
• How do you handle one key that takes a large share of all traffic?
• How would you add a node without a pause in service?
• How do the application and the database stay consistent with the cache?