SpaceComplexity

Consistent Hashing: The Complete System Design Interview Guide

June 3, 20269 min read
system-designinterview-prepdistributed-systemsalgorithms
Consistent Hashing: The Complete System Design Interview Guide
TL;DR
  • Naive modulo hashing remaps ~N/(N+1) keys whenever node count changes, turning every topology change into a cache stampede or expensive migration.
  • The hash ring maps both nodes and keys to a circular space; each key routes to the nearest clockwise node, so only ~1/N keys move when a node joins or leaves.
  • Virtual nodes (vnodes) give each physical server multiple ring positions, balancing load evenly and spreading failure load across many neighbors instead of one.
  • Replication works naturally on the ring: store each key on the next N clockwise nodes, which is exactly the Amazon Dynamo model.
  • Redis Cluster uses 16,384 fixed hash slots instead of a ring, achieving bounded data movement through slot reassignment rather than automatic ring placement.
  • Hotkey problem is the main gap consistent hashing does not solve: it distributes keys, not per-key load, so a single viral key still hammers one node.
  • Interview framing: reach for consistent hashing whenever the design involves partitioned data where nodes can join or leave, and name the hotkey limitation unprompted.

You have four cache nodes. Traffic doubles. You add a fifth. Suddenly your cache hit rate collapses, your database gets hammered, and your on-call engineer is having a very bad morning.

That engineer might be you.

This isn't a scaling failure. It's a hashing failure. Specifically, it's what happens when you use hash(key) % N and change N.

Consistent hashing is the fix. It comes up in nearly every distributed system design interview, and knowing it cold separates candidates who sound like they've read a blog post from candidates who sound like they've actually been paged at 2am.

Why Naive Hashing Breaks

The standard approach to distributing keys across N nodes: node = hash(key) % N.

Works fine until N changes. Change N from 4 to 5 and re-run that modulo. For most keys, the result lands on a different node. When you go from N to N+1 nodes, roughly N/(N+1) of your keys remap to new nodes. Go from 10 nodes to 11 and about 91% of your keys move.

For a database shard, that means a migration. For a cache, that means a thundering herd: every cache miss becomes a database read, all at once. Production engineers call this a cache stampede. It's about as fun as it sounds.

The core problem is that % N couples every key to every node. Change one node, touch every key.

Dog sitting in burning room with try-catch wrapper around it, "THIS IS FINE."

Accurate representation of your database the moment you add that fifth cache node.

How Consistent Hashing Works

Consistent hashing decouples keys from nodes by mapping both to the same circular space.

Imagine the hash space as a circle running from 0 to 2^32 - 1. Every number on the circle is a position. You hash each node (by hostname or IP) to get its position on the circle. You hash each key the same way.

To find which node owns a key: start at the key's position and walk clockwise until you hit a node.

          0
          │
   N3 ────┼──── key_a
          │
  270°    │    90°
          │
   N2 ─── ┼ ─── N1
          │
         key_b (owned by N3, next clockwise)
         180°

When you add a new node N4, it takes a position on the ring. Only the keys between N4 and its counter-clockwise neighbor need to move. Every other key is unaffected. With N existing nodes, roughly 1/N of keys migrate when you add or remove one node, regardless of how many total keys you have.

That's the whole trick. The ring makes node changes local rather than global.

The Hotspot Problem

Random placement sounds fine in theory. In practice, with a small number of nodes, you get uneven arcs. One node might own 40% of the ring. Another might own 8%.

Remove a single node and its entire key space dumps onto one neighbor. That neighbor just absorbed a proportional traffic spike with no warning. This is where virtual nodes come in.

Virtual Nodes Fix the Distribution

Instead of hashing each physical node to one ring position, you hash it to many positions. Each position is a virtual node (vnode). The physical node owns all the keys assigned to any of its vnodes.

Ring with 3 physical nodes, each with 3 vnodes:
  N1a  N2a  N3a  N1b  N2b  N3b  N1c  N2c  N3c
   │    │    │    │    │    │    │    │    │
───┼────┼────┼────┼────┼────┼────┼────┼────┼───

With enough vnodes, each physical node covers multiple small arcs spread around the ring, and distribution approaches uniformity. Cassandra uses 256 vnodes per physical node by default.

Three things fall out of this:

  1. Load distributes evenly under normal operations.
  2. When a node goes down, its keys spread across many neighbors rather than avalanching onto one.
  3. You can give beefier nodes more vnodes for a proportionally larger share.

The downside: more vnodes means more metadata. At some scale this overhead matters, but for most systems it's negligible.

Screenshot of an exam results page listing "Server 1" through "Server 10" as plain links with no routing logic, labeled "Poor Man's Load Balancer"

What happens when you skip virtual nodes and trust random placement with three physical nodes.

Replication Is Just the Next N Nodes

Consistent hashing composes naturally with replication. Store each key on the next N nodes clockwise from its hash position. This is exactly what Amazon Dynamo does: a replication factor of 3 means each key lives on three consecutive nodes on the ring.

When one node fails, its replicas serve reads. When it comes back or a replacement joins, it backfills from neighbors. The ring topology tells every node exactly which keys it should have and which neighbors to sync with.

Reads and writes use quorum (R + W > N) to balance consistency against availability. That's a separate discussion, but the ring is what makes the topology tractable.

When to Bring This Up in Your Interview

Consistent hashing belongs in any design involving partitioned data where nodes can join or leave. The phrase to reach for: "we want to minimize data movement when the cluster topology changes."

Specific scenarios:

  • Distributed cache: Partitioning keys across multiple cache nodes. Naive hashing causes cache storms on node changes; consistent hashing keeps disruption local. See the distributed cache walkthrough for how this fits into a full design.
  • Key-value store: Any sharding discussion for a system like Dynamo or Cassandra. The key-value store design covers this in more depth.
  • Load balancing with session affinity: Users should route to the same backend server within a session. Consistent hashing maps user IDs to backends, and adding a backend only moves ~1/N users.
  • Content delivery: Akamai's original consistent hashing paper (Karger et al., 1997) was literally about CDN cache routing. Adding a node doesn't invalidate the entire cache.

Most candidates who mention consistent hashing can describe the ring. Fewer can explain why the failure mode they're solving matters operationally. Be the second kind of candidate.

The 90-Second Explanation

When an interviewer asks, hit these four beats:

  1. The problem: naive modulo hashing remaps nearly all keys when N changes, causing cache stampedes or expensive migrations.
  2. The ring: map both nodes and keys to a circular hash space. Each key goes to the first node clockwise.
  3. The improvement: adding or removing a node only affects ~1/N of keys.
  4. Virtual nodes: each physical node maps to multiple ring positions for even load distribution and graceful failures.

Draw the ring. Yes, even in a Zoom call with a whiteboard you can barely reach. Even if your drawing looks like a polygon with ambitions. Interviewers remember candidates who make abstractions concrete.

The Tradeoffs to Know Cold

Every design choice has a cost, and naming the cost unprompted is a strong signal.

TradeoffDetail
Implementation complexityMaintaining a sorted ring and vnode metadata is non-trivial. Libraries exist (ketama for memcached, built into Cassandra), but rolling your own is a great way to discover new bugs at 3am.
Hotkey problemA single extremely popular key still hammers one node regardless of ring position. Consistent hashing distributes keys, not load per key. Mitigate with local replication or a separate hotkey tier.
Non-uniform distributionWithout vnodes, random placement can be very uneven. With too few vnodes, variance is still high.
Rebalancing timeEven though only 1/N of keys move, moving them takes real I/O. During a node addition, performance can degrade.
Metadata overheadTracking hundreds of vnodes per node across dozens of nodes is real state. It gets gossiped around the cluster and stored persistently.

The system design interview tips guide covers how to frame tradeoffs in general. For consistent hashing specifically, mention the hotkey problem immediately after explaining the ring. It shows you've thought past the happy path.

How Redis Does It Differently

Redis Cluster uses 16,384 fixed hash slots. Each slot is assigned to a master node. Keys map to slots via CRC16(key) % 16384. Moving a node means reassigning some slots.

This isn't consistent hashing in the traditional sense, but it achieves the same goal: bound data movement on topology changes. The advantage is simpler implementation and predictable slot boundaries. The downside is that slot reassignment is manual or configuration-driven rather than automatic.

Worth knowing the distinction. In an interview: "Redis Cluster uses hash slots, not a ring, but the goal is the same." Short, confident, shows you've actually thought about it.

Where It Appears in Production

  • Apache Cassandra: consistent hashing with 256 vnodes per node by default, replication factor typically 3.
  • Amazon Dynamo (the 2007 paper that put consistent hashing on the production map): N=3 replication, quorum reads/writes.
  • Memcached via ketama: created by Last.fm, maps each server to 100-200 ring positions using MD5.
  • Riak: built directly on the Dynamo model.
  • Akamai CDN: the Karger et al. 1997 STOC paper was written specifically for CDN caching.

Dropping one of these names is fine if it's natural. "This is essentially what Dynamo does" lands better than a name-drop with no context.

When Not to Use It

Consistent hashing solves one specific problem: minimizing remapping when node count changes. If your topology is static, naive modulo hashing is simpler and valid. If you need ordered range scans across shards, range-based partitioning is often a better fit. Know the alternative so you can explain why you chose the ring.

If you want to practice explaining this out loud under interview conditions, SpaceComplexity runs voice-based system design mocks where you can talk through the ring, handle follow-up questions in real time, and get rubric-based feedback on how well you actually communicated the tradeoffs.

Further Reading