Consistent Hashing Explained

Consistent hashing is a technique for distributing keys across a changing set of servers so that adding or removing a server only remaps a small fraction of keys, instead of nearly all of them. It’s the algorithm quietly underneath distributed caches, sharded databases, and content delivery networks, because it solves a problem that a naive hash-and-modulo approach handles badly: what happens to your data layout when the number of servers changes.

The problem with modulo hashing

The obvious way to spread N keys across M servers is server = hash(key) % M. It’s simple and distributes evenly — right up until M changes. Add or remove a single server, and % M becomes % (M+1) or % (M-1), which changes the target server for nearly every key, not just the ones that logically belong to the server that joined or left. For a cache, that means a near-total cache wipe the moment you scale up or down. For a sharded database, it means a massive, disruptive data migration for what should be a routine capacity change.

The ring

Consistent hashing fixes this by mapping both servers and keys onto the same abstract space — usually visualized as a ring of hash values from 0 up to some maximum, wrapping back to 0. Each server is hashed to one or more points on this ring. Each key is also hashed onto the ring, and it belongs to whichever server’s point comes next going clockwise.

When a server is removed, only the keys that mapped to that server’s position move — and they move to the next server clockwise on the ring, not to some remapped position across the entire keyspace. When a new server joins, it claims a segment of the ring and takes over only the keys that fall in that segment, again leaving everything else untouched. Adding or removing one server out of M now remaps roughly 1/M of the keys instead of nearly all of them.

Virtual nodes

A single hash point per physical server creates an uneven distribution — some servers end up owning much larger arcs of the ring than others, purely by the luck of where their hash landed. The standard fix is virtual nodes: each physical server is hashed onto the ring at many points (dozens or hundreds), rather than just one. Keys still map to whichever virtual node comes next clockwise, but because each physical server now owns many small, scattered arcs instead of one large one, the overall load balances out much more evenly, and adding or removing a physical server redistributes a proportionally even slice of keys across the remaining nodes rather than dumping it all on one neighbor.

Where consistent hashing shows up

• Distributed caches. A cache cluster like Redis or Memcached deployed across multiple nodes uses consistent hashing (or a client-side equivalent) to decide which node owns a given key, so scaling the cluster up or down doesn’t invalidate the whole cache at once.
• Database sharding. Systems that split data across many nodes use consistent hashing as one strategy for assigning rows to shards — see database sharding for the broader landscape of partitioning approaches, of which this is one.
• Load balancers. A load balancer doing session-aware or cache-aware routing can use consistent hashing to route a given client or key to the same backend consistently, even as backends are added or removed.
• CDNs and edge networks. A CDN mapping content to edge nodes benefits from the same property: swapping out an edge node shouldn’t force every cached object in the network to be refetched and reassigned.

Consistent hashing vs plain modulo hashing

	Modulo hashing (hash % M)	Consistent hashing
Keys remapped when a node changes	Nearly all of them	Roughly 1/M of them
Implementation complexity	Trivial	Requires a ring structure and virtual nodes
Load balance with one hash point	Even, but brittle to changes	Uneven without virtual nodes
Load balance with virtual nodes	N/A	Even and stable under changes
Typical use	Fixed-size clusters	Elastic, frequently resized clusters

A practical note on lookups

Finding which node a key maps to on the ring is a “next point clockwise” search, which is efficiently implemented with a sorted structure — a balanced tree or sorted array of virtual-node positions works well, since it turns the lookup into a search for the next value greater than or equal to the key’s hash. The Big O of that lookup is logarithmic in the number of virtual nodes, which stays fast even as a cluster grows into the hundreds of nodes.

The takeaway

Consistent hashing places both servers and keys on the same ring so that a key’s owner is “whichever server comes next,” rather than a value computed fresh from the current server count. That one change means adding or removing a node reshuffles a small, proportional slice of keys instead of almost everything. Pair it with virtual nodes to keep the load evenly spread across physical servers, and it becomes the default choice anywhere a cluster’s size is expected to change over its lifetime — caches, shards, and edge networks alike.