Consistent hashing: how to design a distributed cache

In this article

1. Before you start
2. Why interviewers ask this
3. Consistent hashing from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the system design learning path.

Why interviewers ask this

Consistent hashing is the standard answer to "how do you spread a cache over many machines without a disaster when the machine count changes?" Interviewers use it in the distributed-systems part of an interview loop to see whether you understand that the placement rule, not the cache software, decides what happens on a resize.

A weak answer says "hash the key and take it modulo the number of servers," and is stuck when asked to add a server. A strong answer explains why modulo breaks, draws the ring, adds virtual nodes without being prompted, and says how replication and failures fit in. It is also the core of most "design a distributed cache" and "design a key-value store" questions in the machine learning system design and general system design rounds.

Consistent hashing from first principles

Distributed cache

A distributed cache is a set of servers that together hold copies of frequently read data in memory, so that most reads skip the slower database and no single machine holds everything.

Hash ring

A hash ring is the output range of a hash function treated as a circle, where the largest value wraps around to the smallest, so keys and servers can both be placed on it.

Virtual node

A virtual node is a position on the hash ring that one physical server occupies among many, which spreads that server's share of the keys into many small slices.

In plain words

Imagine a circular running track with mile markers. Each cache server stands at a marker. Every key is also dropped on the track at a marker. To find a key's server, walk forward from the key until you meet the first server. If a new server joins, it stands at one marker. It takes over only the keys between its predecessor and itself. Everyone else keeps their keys. The analogy breaks in one place: real servers stand at random markers, so the gaps can be uneven. Step 4 fixes that.

In one precise sentence: hash both servers and keys onto the same circle, and assign each key to the first server at or after its position going clockwise (DeCandia et al., 2007).

Step 1: Modulo hashing remaps almost every key

The simplest placement rule is node = hash(key) modulo N, where N is the number of servers. It works until N changes. A key stays on its server only if its hash gives the same remainder for N and for N + 1, and that happens for roughly one key in N + 1.

In a simulation with 100,000 keys, going from 10 nodes to 11 moved 90.9% of the keys under modulo hashing, against an ideal minimum of 9.1%.¹ For a cache, each moved key is a miss on its next read, so 91% of the traffic lands on the database at once. The remainder rule ties every key to the node count. Input: a key and N. Output: a node that changes whenever N does. What you want is a rule where only the keys that must move do.

Step 2: Put nodes and keys on a ring

A hash function produces numbers in a fixed range, such as 64 bits. Treat that range as a circle in which the largest value wraps around to the smallest, and give every server a position by hashing its name. Each key gets a position by hashing the key itself.

DeCandia et al. (2007), describing Amazon's Dynamo store, state it this way: each node gets a random value in the space, which is its position on the ring, and each key is hashed to a position as well. Nothing is decided by N any more: the position of a server depends only on its own name. Input: names and keys. Output: points on one circle. You now have a structure where a server's neighbours are well defined.

Step 3: Walk clockwise to find the owner

To look up a key, hash it to its position and walk clockwise to the first server position at or after it. In code, the server positions are kept in a sorted list and the lookup is a binary search with wrap-around, which costs O(log n) for n positions.

When a server joins, it takes over only the arc between its predecessor and itself. The source puts it directly: the principal advantage is that the departure or arrival of a node affects only its immediate neighbours and other nodes remain unaffected. In the same simulation, adding the eleventh node with one position each moved 8.8% of the keys, close to the ideal 9.1%.¹ Removing a server is the mirror: its keys move to its clockwise neighbour. The cost of this simple version appears next.

Step 4: Virtual nodes even out the load

With one random position per server, the arcs between positions are uneven, so some servers own much more of the circle than others. In the simulation, with 10 nodes and one position each, the busiest node held 3.09 times the mean load and the quietest held 0.03 times.¹

The fix is a virtual node: each physical server takes many positions on the ring. Dynamo uses the same idea and calls the positions tokens. The paper lists three advantages: when a node fails, its load spreads over the remaining nodes; a new node takes roughly equal load from each existing node; and the number of virtual nodes can match a machine's capacity. With 100 virtual nodes per server the busiest node fell to 1.18 times the mean, and with 1,000 it fell to 1.05.¹ The price is memory for the sorted list of positions and a slightly more expensive lookup table.

1 · Modulo breaks2 · Build the ring3 · Walk clockwise4 · Add virtual nodesReplay

Step-by-step description

1. Changing N remaps almost every key.
2. Nodes and keys share one circular hash space.
3. A key belongs to the next node clockwise.
4. Many points per node even out the load.

• Going from 10 nodes to 11 moved 90.9% of the keys under modulo hashing.
• Adding the eleventh node with one position each moved 8.8% of the keys.
• The busiest node held 3.09 times the mean load with one position each, and 1.18 times with 100 virtual nodes.

Worked example

The simulation placed 100,000 keys on 10 nodes, then added an eleventh node, for modulo hashing and for rings with 1, 10, 100 and 1,000 virtual nodes per server. Hashes are the first eight bytes of a Secure Hash Algorithm (SHA) 256-bit digest, so the run is repeatable.¹

The ideal share moved is 1 in 11, or 9.1%, and rings land near it with some sampling noise.¹ The takeaway is the pair of columns: the ring fixes movement, virtual nodes fix balance, and a few hundred virtual nodes per server are enough to get within about 20% of the mean in this setup.

Text description of the diagram

• With 1 virtual node per node the busiest node holds 3.09 times the mean load and the quietest holds 0.03 times.
• With 1,000 virtual nodes the busiest holds 1.05 times and the quietest 0.96 times.

Trade-offs and edge cases

The ring is not the only placement scheme, and the right one depends on how often the cluster changes and how much state you can keep.

Fixed hash slots are the main alternative. Redis Cluster splits its key space into 16384 slots, computes the slot as the 16-bit cyclic redundancy check (CRC16) of the key modulo 16384, and gives each master node a subset of the slots (Redis cluster specification, as of October 2026). Resharding moves whole slots, so only the keys in those slots move. It is not a ring, but it has the same property of moving only a share of the keys.

Text description of the diagram

• Modulo hashing moved 90.9% of the keys when 10 nodes became 11.
• A ring moves only about one key in N.
• Redis Cluster splits its key space into 16384 slots, and resharding moves whole slots.

Other schemes fix other weaknesses. Jump consistent hash needs no stored ring and divides keys evenly, but its buckets must be numbered sequentially, so it suits storage better than web caching (Lamping and Veach, 2014). Consistent hashing with bounded loads caps each server's load at a chosen multiple of the average while moving few keys (Mirrokni et al., 2016).

Each node also manages its own memory. When a node is full it evicts entries by itself, and most caches use a least-recently-used (LRU) policy for that, which drops the entry untouched for the longest time (Microsoft Azure Architecture Center, Cache-Aside pattern, page dated 2025-09-11, read October 2026). The ring decides which node owns a key; the node decides what to throw away.

A time to live (TTL), an expiry set on each entry, bounds how stale a cached copy can get; Amazon Web Services (AWS) lists setting an appropriate expiration among the ways to keep cached data fresh (Amazon Web Services (AWS) caching patterns, as of October 2026). To see how one node's LRU works, read LRU cache implementation in Python.

Edge cases: a hot key, one key read so often that a single node cannot serve it, is not fixed by any placement rule; replicate that key or add a small local cache in front. Heterogeneous machines get more virtual nodes in proportion to capacity. The same hashing idea shards the indexes of embedding and vector search and the work of the data engineering pipelines. A different cache with the same name, the key-value (KV) cache inside a language model server, is covered in the large language model (LLM) inference path.

How to answer it in an interview

The spoken structure: say why modulo fails, say the ring and the clockwise rule, then add virtual nodes, replication and the cost.

Common mistakes

• "I hash the key and take it modulo the number of servers." (wrong) It remaps about 91% of keys in a ten-to-eleven resize and causes a miss storm. (right) "I use a ring, so only about one key in N moves."
• "A ring balances load by itself." (wrong) One position per server left one node at 3.09 times the mean in the simulation. (right) "I add virtual nodes to even out the arcs."
• "Consistent hashing solves hot keys." (wrong) It decides placement, not demand; a popular key still lands on one server. (right) "I replicate or locally cache hot keys."
• "Replicas go on the next virtual nodes." (wrong) Those may belong to the same physical server. (right) "I replicate to the next distinct physical servers."

Follow-up questions

Read-through vs write-through cache?

A read-through cache loads missing data itself on a read miss; a write-through cache is updated on every write, right after the database. Cache-aside is a pattern, also called lazy loading, in which the application reads the database after a miss and stores the result in the cache; read-through does the same fill inside the cache layer (Microsoft Azure Architecture Center, Cache-Aside pattern, read October 2026). A write-through cache is updated right after the primary database, which raises the hit rate but also stores rarely read data (AWS caching patterns, as of October 2026).

Design a distributed LRU Cache with consistent hashing, replication, and eviction?

Place servers on a ring with virtual nodes, send each key to its clockwise owner, and copy it to the next distinct servers for replication. Each node keeps its own LRU structure, evicts the least recently used entry when full, and gives entries a TTL to bound staleness.

Design a flexible in-memory cache with customizable capacity and eviction policies?

Make capacity and policy settings of each node, not of the ring: a memory budget and an eviction rule such as LRU, behind one interface. Microsoft notes that a single global eviction policy might not suit all items, so allow a per-item override for entries that are expensive to reload.

How do you add replication to a consistent-hash ring?

Replicate each key at the next N minus 1 distinct servers clockwise from its owner; Dynamo calls the owner the coordinator and the list of replicas the preference list. Skip positions that belong to a server already in the list, because virtual nodes would otherwise put two replicas on one machine.

What happens when a cache node fails?

Its keys move to the clockwise neighbours, and the first read of each is a miss that reloads from the database. Virtual nodes spread those misses over many servers instead of one, which keeps any single neighbour from being overwhelmed.

How do you migrate to a new cache node without a cold cache?

A new node starts empty, so every key it takes over misses once. Ramp it in by giving it a few virtual nodes first and adding more over time, or let it fall back to the old owner on a miss while it fills. Microsoft also notes that many systems prime the cache at startup with data they expect to need.

Sources

1. Dynamo: Amazon's Highly Available Key-value Store — SOSP 2007 (DeCandia et al.), 14 Oct 2007
2. Consistent Hashing with Bounded Loads — arXiv (Mirrokni, Thorup, Zadimoghaddam), 3 Aug 2016
3. A Fast, Minimal Memory, Consistent Hash Algorithm — arXiv (Lamping and Veach), 9 Jun 2014
4. Redis cluster specification — Redis documentation (date = read date), 24 Oct 2026
5. Cache-Aside pattern (Azure Architecture Center) — Microsoft Learn (page dated 2025-09-11, read 2026-10-24), 24 Oct 2026
6. Caching patterns (Database Caching Strategies Using Redis) — AWS whitepaper, marked historical (date = read date), 24 Oct 2026