Why not just use key mod N to pick a server?

With hash(key) mod N, changing N from one server count to another reshuffles almost every key, because the modulus changes for all of them. Consistent hashing avoids this by decoupling key positions from the number of servers.

What are virtual nodes?

Each physical server is placed at many points on the ring, called virtual nodes or replicas. Instead of one position per server, V positions spread the server's ownership into many small arcs, which evens out the load.

Why do virtual nodes improve load balance?

With one point per server, random placement can give some servers huge arcs and others tiny ones. Many virtual nodes average out these variations, so each physical server ends up with a fairer share of keys.

How does a key find its server on the ring?

The key is hashed to a position on the ring, then you walk clockwise until you hit the first server (virtual node). That server owns the key. If you pass the top of the ring, you wrap around to the start.

Where is consistent hashing used?

It powers distributed caches like memcached client sharding, key-value stores such as Amazon Dynamo, Cassandra and Riak, content delivery networks, and peer-to-peer distributed hash tables (DHTs) like Chord.

What happens to keys when a server is removed?

Only the keys owned by the removed server's virtual nodes are reassigned. Each affected key moves clockwise to the next surviving server, while all other keys stay exactly where they were.

How many virtual nodes should I use?

In practice systems use anywhere from around 100 to several hundred virtual nodes per server. More replicas give smoother balance but cost more memory and lookup-structure overhead.

How are keys mapped to the ring exactly?

A hash function maps each key and each virtual node label to a number in a fixed range, for example 0 to 2^32 − 1. That range is treated as a circle, so the largest value wraps around to the smallest.

Home▸Distributed & Parallel Computing▸Consistent Hashing — The Hash Ring

💍 Consistent Hashing — The Hash Ring

Map keys and servers onto a hash ring so adding or removing a node only remaps a small fraction of keys. Virtual nodes smooth the load — the technique behind distributed caches and DHTs.

Distributed & Parallel Computing3DModerate60 FPS

About Consistent Hashing

Consistent hashing solves a critical problem in distributed systems: how to assign data keys to servers so that adding or removing a node reshuffles as few keys as possible. The technique maps both keys and servers to positions on a circular hash ring of size 2^32. Each key is owned by the first server found clockwise from its position. With the naïve modulo approach (hash(key) mod N), changing N from one server count to another can remap almost every key — catastrophic for a live cache. Consistent hashing limits disruption to roughly 1/N of keys on average, because only the arc of the ring adjacent to the added or removed server changes hands.

Virtual nodes (also called replicas) are the practical refinement: each physical server is placed at V positions on the ring instead of one, splitting its ownership into many small arcs. This smooths out the load distribution dramatically — without virtual nodes a single server might claim 40% of keys by chance; with 100+ virtual nodes the distribution converges towards the ideal 1/N per server. Adjust the servers, virtual node count, and key set with the sliders, then add or remove servers to observe how few keys (highlighted in white) need to move.

Frequently Asked Questions

Why does modulo hashing cause massive key redistribution when servers change?

With hash(key) mod N, the slot each key maps to depends on N. When N changes — say from 4 to 5 — the modulus changes for virtually every key, remapping roughly (N−1)/N ≈ 80% of them. Consistent hashing eliminates this by decoupling key positions from server count: each key always maps to the same ring position, and only the clockwise lookup changes when a server is added or removed.

Exactly how many keys move when a server is added to the ring?

When a new server S is placed at position p on the ring, it claims the arc from the previous server (clockwise) up to p. Only keys that fall in that arc move — they transfer from their previous owner to S. On average that is 1/N of all keys, where N is the new server count. All other keys remain with their existing owners.

What problem do virtual nodes solve, and how many should you use?

With one position per server, random placement on the ring produces highly unequal arc lengths: some servers may get 3× the average load. Placing each physical server at V virtual-node positions divides the ring into V×N segments, averaging out the imbalance. Production systems (Amazon Dynamo, Cassandra) commonly use 100–200 virtual nodes per server, where the standard deviation of load falls below 10% of the mean.

How does a key lookup work in constant time?

The virtual-node positions are stored in a sorted array or balanced binary search tree. To find the owner of a key, hash the key to get its ring position, then perform a binary search for the smallest virtual-node position that is greater than or equal to the key's position (wrapping around to position 0 if none is found). This lookup runs in O(log(V×N)) time — effectively constant for fixed V and N.

Which real systems use consistent hashing?

Amazon Dynamo (2007) popularised consistent hashing with virtual nodes for its key-value store; Cassandra inherited the same architecture. Memcached client libraries (e.g., the ketama algorithm) use it to shard cache keys across a pool of servers. Content delivery networks and peer-to-peer distributed hash tables (DHTs) such as Chord and Kademlia also rely on ring-based hashing.

What happens to data when a server crashes and is removed?

If server S fails, its virtual-node positions become vacant. The keys S owned are now owned by the next clockwise server for each arc. If replication is configured (typically 3 replicas in Cassandra), the data already exists on the next N−1 clockwise servers, so the cluster continues serving reads without data loss. Write quorums ensure consistency during the failover.

How does consistent hashing relate to Chord DHT?

Chord (Stoica et al., 2001) is a peer-to-peer lookup protocol built directly on consistent hashing. Each peer is assigned a position on a 160-bit SHA-1 ring. Chord adds a "finger table" of O(log N) shortcuts per node so any key can be located in O(log N) hops — combining consistent hashing with an efficient distributed routing structure.

Can consistent hashing handle servers with different capacities?

Yes. By assigning more virtual nodes to a higher-capacity server — say 200 virtual nodes to a machine with twice the RAM versus 100 for a standard node — its share of the ring increases proportionally to its capacity. This weighted consistent hashing is used by Cassandra's token allocation and by cloud load balancers to route more traffic to larger instances.

What is "bounded load" consistent hashing?

In 2017, Google published "Consistent Hashing with Bounded Loads", which adds a capacity constraint: no server may hold more than (1 + ε) times the average number of keys. When a target server is overloaded, the key is assigned to the next clockwise server instead, spreading the load more evenly. This variant is used in Google's production load balancers.

How does the hash function choice affect the ring distribution?

A good hash function must distribute both keys and virtual-node labels uniformly across the 2^32-bit ring. Poor hash functions produce clustering, causing some arcs to be far longer than average even with many virtual nodes. In practice FNV-1a, MurmurHash3, and xxHash are popular choices for their speed and uniform distribution properties.

⚙ Under the hood

Map keys and servers onto a hash ring so adding or removing a node only remaps a small fraction of keys. Virtual nodes smooth the load — the technique behind distributed caches and DHTs.

consistent hashinghash ringvirtual nodesload balancingCanvas 2D

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install