Design a distributed cache

A shared in-memory key-value cache, like Redis or Memcached, spread across many machines.

Why interviewers ask it

It tests partitioning, consistent hashing, eviction, replication and failure handling — the building blocks of most large systems.

Functional requirements

Non-functional requirements

From version 1 to the final design

  1. Version 1: one cache server with a hash map and LRU eviction.
  2. Version 2: several servers using hash % N routing.
  3. Version 3: consistent hashing with virtual nodes.
  4. Version 4: replicas, failover, hot-key handling and stampede protection.

The design, step by step

  1. Clients, or a proxy, route each key to a node with consistent hashing and virtual nodes.
  2. Each node: an in-memory hash table with LRU eviction and TTL expiry.
  3. Each shard has a replica for failover.
  4. Cluster membership comes from a configuration service, or nodes gossip with each other.

Deep dives

Common mistakes

Not true: Routing: hash % N keeps most keys on the same server when a server is added.
In fact: Changing N changes the answer for almost every key, so nearly all lookups miss at once. Consistent hashing moves only about 1/N of the keys.

In the interview

Keys are spread across nodes with consistent hashing and virtual nodes, so adding a node moves only a small share of the keys. Each node is an in-memory hash map with LRU eviction and TTLs, replicated for failover. Hot keys get extra replicas or a local cache, and stampedes are prevented by letting one request rebuild a key.

Part of Unit 8: High-level design questions in the free System Design course.