Consistent Hashing

With naive modulo hashing, adding or removing a node remaps nearly every key — causing massive cache invalidation or data migration. Consistent hashing solves this by arranging both nodes and keys on a circular ring, so only a small fraction of keys need to move when the cluster changes.

The Problem With Naive Hashing

The simplest way to distribute keys across N servers is hash(key) % N. Pick a hash function, take the modulo, route the request to that server. It works fine until you need to scale.

The moment you add or remove a node, N changes — and nearly every key maps to a different server.

# 3 nodes: keys route to servers 0, 1, 2
server = hash(key) % 3

# Add a 4th node — now almost every key remaps
server = hash(key) % 4

In a cache cluster, this means a cache miss storm — every key that remapped is suddenly a miss, and all those requests fall through to your database at the same time. In a database sharding setup, it means migrating the majority of your data to different nodes. Neither is acceptable at scale.

The Hash Ring

Instead of using modulo arithmetic, consistent hashing places both nodes and keys on a circular number line — the "ring" — with positions ranging from 0 to 2^32.

Each server is hashed to one or more positions on the ring. Each key is also hashed to a position. To find which server owns a key, you walk clockwise around the ring from the key's position until you hit a server.

Ring positions (simplified):
  0 -------- Server A (hash: 12) -------- Server B (hash: 45) -------- Server C (hash: 78) -------- 100

  Key "user:123" hashes to position 30 → walks clockwise → owned by Server B
  Key "user:456" hashes to position 60 → walks clockwise → owned by Server C
  Key "user:789" hashes to position 90 → walks clockwise → wraps around → owned by Server A

The ring is just a conceptual model. In practice you sort server hash positions in an array and use binary search to find the correct server for any key in O(log N).

Adding a Node

When you add a new server, it hashes to a position on the ring. It slots in between two existing servers. The only keys that need to move are the ones that were previously owned by the next clockwise server but now fall between the new server and its predecessor.

Typically, adding the Nth node causes only 1/N of all keys to relocate. Add a 4th server to a 3-server cluster and roughly 25% of keys move — not 75%.

Before: A → B → C (ring order)
Add D between A and B: A → D → B → C

Keys that were between A and B now belong to D.
All other keys are unaffected.

This is the core property that makes consistent hashing useful. Scaling up your cache cluster no longer triggers a thundering herd.

Removing a Node

When a server goes down or is decommissioned, its position disappears from the ring. The keys it owned are taken over by the next clockwise server. Only that server gains new keys — everything else in the cluster is untouched.

This makes failure handling much smoother. In a cache layer, a single node failure causes a bounded number of cache misses rather than invalidating the entire cache. The blast radius is proportional to 1/N of your keyspace.

Virtual Nodes

Basic consistent hashing has a distribution problem. With only a handful of physical servers, the hash positions land unevenly on the ring. One server might own 40% of the keyspace while another owns 5%.

The fix is virtual nodes. Instead of mapping each physical server to one ring position, you map it to many — say, 150 or 256 positions. Each virtual node position is hashed as hash("ServerA-1"), hash("ServerA-2"), ..., hash("ServerA-256").

Physical servers: A, B, C
Virtual nodes per server: 3 (simplified — real systems use 100-256)

Ring: A-2 → B-1 → C-3 → A-1 → B-3 → C-1 → A-3 → B-2 → C-2

With more positions, keyspace is distributed more evenly.

More virtual nodes mean better distribution, but also more memory and slightly more routing overhead. Cassandra uses 256 virtual nodes per physical node by default. The right number is a tradeoff between distribution quality and operational overhead.

Virtual nodes also make it easier to weight servers differently. A more powerful machine can be assigned more virtual nodes, giving it proportionally more of the keyspace.

Real World Usage

Consistent hashing shows up across the distributed systems landscape wherever data needs to be spread across nodes that can come and go.

Amazon DynamoDB uses consistent hashing to route requests based on partition keys. When you write an item, DynamoDB hashes the partition key to determine which storage node handles it — and the ring structure means rebalancing after node changes is minimal.

Apache Cassandra uses a similar model for distributing rows across its cluster. Each node owns a token range on the ring, and the virtual node approach (called "vnodes" in Cassandra terminology) ensures even distribution even when nodes differ in capacity.

Distributed Memcached clients implement consistent hashing in the client library. The application server itself decides which cache node to talk to based on the key hash — there's no central coordinator. Libraries like pylibmc and ketama implement this directly.

Load balancers use consistent hashing for session affinity (also called sticky sessions). Hash on the client's IP or session token to always route that client to the same backend server — useful when backend servers hold in-memory session state.

Key Takeaways

• Naive modulo hashing (hash(key) % N) remaps nearly all keys when N changes, causing cache stampedes or mass data migrations
• Consistent hashing places both servers and keys on a circular ring; each key is owned by the nearest clockwise server
• Adding or removing a node affects only 1/N of keys on average, not the entire keyspace
• Virtual nodes (multiple ring positions per physical server) fix uneven distribution in small clusters
• Cassandra defaults to 256 virtual nodes per server; more virtual nodes means better balance but higher overhead
• The same principle applies to caches, databases, and load balancers — anywhere you distribute work across nodes that can scale up or down

Next up: database indexes — how a B-tree lets your database find any row in O(log n) steps instead of scanning every row in the table.