2026-09-14Systems16 min read

Consistent hashing from first principles

Build up consistent hashing one step at a time: from a single database to sharding, hash rings, adding and removing databases, and balancing the ring with virtual nodes.

1. What is consistent hashing?

Imagine spreading your application's data across three databases. Everything works until you add a fourth database. Suddenly, much of the existing data needs to move, even between databases that have not changed.

Consistent hashing is a way to decide where data belongs while keeping most of those decisions unchanged when a database joins or leaves.

It is useful in distributed databases, caches, and systems that route requests across a changing set of servers. Moving less data means less work during scaling and fewer cache misses when cache servers change.

The word "consistent" here is about keeping the mapping from a key to a server stable. It does not mean that replicas automatically contain identical data.

We will build the idea from scratch, starting with one client, one application server, and one database.

2. Start with one database

Suppose we are building an application that stores user profiles. Each profile has a unique user ID.

A client asks for a profile. The application server receives the request, looks up the ID in the database, and returns the result.

There is no routing decision to make. Whether we are reading user 42 or saving user 900, every database operation goes to the same place.

That is simple, and it can work well for a long time.

3. As the application grows, split the data

Eventually, one database may not have enough storage or capacity to handle all the reads and writes.

One way to scale is sharding: split the data across multiple databases. Instead of keeping every user in one database, DB1 stores some users, DB2 stores others, and DB3 stores the rest.

These are shards, not three copies of the same dataset.

The application server can now talk to all three databases. But for a request concerning one user, we would like it to contact just the database that owns that user's profile.

That introduces a question we did not have before:

Given a user ID, which database should the server choose?

4. Use a hash to choose a database

A hash function turns an input, such as a user ID, into a number. For our purposes, it needs two useful properties: the same input always produces the same output, and different inputs spread reasonably well across the output range.

We can turn that number into a database number:

database number = hash(Id) % 3 + 1

The % operator gives the remainder after division. With a nonnegative hash value, dividing by 3 leaves a remainder of 0, 1, or 2. Adding 1 turns those into database numbers 1, 2, or 3.

Using the illustrative hash value from the diagram:

Id       = 2341231225
hash(Id) = 6967
 
6967 % 3 = 1
1 + 1    = 2
 
Destination: DB2

Reads and writes use the same rule. If we save a profile to DB2, a later request for that user will also go to DB2.

Here, Id means the data key, such as the user ID, not a freshly generated ID for each request. Otherwise, two requests for the same profile could end up at different databases.

So far, this is an inexpensive way to route requests without maintaining a separate lookup entry for every user.

5. What happens when we add DB4?

We need more capacity, so we add a fourth database. Our routing formula becomes:

database number = hash(Id) % 4 + 1

Our example user now has a different destination:

Before: 6967 % 3 + 1 = 2  -> DB2
After:  6967 % 4 + 1 = 4  -> DB4

That might seem reasonable: the new database needs some data. The problem is that movement is not limited to data going to DB4.

Consider another key whose hash is 8:

Before: 8 % 3 + 1 = 3  -> DB3
After:  8 % 4 + 1 = 1  -> DB1

Neither DB3 nor DB1 was added or removed, yet this key changes owners too.

With uniformly distributed hashes, approximately 75% of keys change databases when moving from three to four databases this way. Not every key moves, but the disruption reaches across the existing shards.

Strictly speaking, the hash function itself has not changed: hash(Id) still returns 6967 for our example. The routing formula changed because its divisor changed.

Also, changing the formula does not move stored records. The system must migrate affected data and coordinate reads and writes during that transition. Otherwise, a request can arrive at DB4 while its data is still on DB2.

6. What happens when a database leaves?

Return to our original three databases. This time, suppose DB3 is removed, leaving DB1 and DB2.

The formula becomes:

database number = hash(Id) % 2 + 1

The user in the diagram happens to stay on DB2:

Before: 6967 % 3 + 1 = 2  -> DB2
After:  6967 % 2 + 1 = 2  -> DB2

The two-database formula is % 2 + 1; the %4 label on the diagram's "After" line is a typo.

One unchanged key does not mean the mapping is stable. A key with hash 9, for example, moves between the two surviving databases:

Before: 9 % 3 + 1 = 1  -> DB1
After:  9 % 2 + 1 = 2  -> DB2

With uniformly distributed hashes, approximately two-thirds of keys change databases. Again, even databases that stayed online are affected.

This example removes DB3 so the remaining database numbers are still 1 and 2. If DB2 were removed instead, we would need to map the two formula outputs to the surviving databases, DB1 and DB3.

A planned removal and a crash also differ in an important way: we can copy data out of a healthy database before removing it. If it crashes, routing somewhere else does not recover its data. We need replicas or a recovery process.

The underlying problem is now clear: using the database count as the divisor ties many routing decisions to the size of the cluster.

7. Keep the hash space fixed, and turn it into a ring

Instead of changing the buckets whenever the database count changes, let us give keys and databases positions in a fixed space.

Choose a hash function whose output is an unsigned 32-bit integer, from 0 through 2^32 - 1, or 4,294,967,295. That is a convenient example range, not a requirement of consistent hashing.

First, imagine those numbers on a number line. Hash each data key and place it at its number. Hash stable database IDs, such as "DB1" and "DB2", into the same range and place them on the line too.

Now bend the number line into a circle. Just after the largest value, we wrap around to 0. The endpoints are consecutive around the ring, not the same hash value.

The routing rule is:

Start at the key's hash position and move clockwise. The first database you reach owns that key.

If a key lands exactly on a database's position, that database owns it. If there is no database before the end of the range, continue past 0.

For easy arithmetic, use a separate miniature example with positions 0 through 99, increasing clockwise:

DB1 is at 20
DB2 is at 50
DB3 is at 80
 
A key at 12 -> DB1 at 20
A key at 34 -> DB2 at 50
A key at 68 -> DB3 at 80
A key at 92 -> wrap past 0 -> DB1 at 20

Each database owns the stretch after the previous database, up to and including itself, moving clockwise. DB2, for example, owns positions greater than 20 through 50.

The ring is a mental model. In code, it can be a sorted list of database hash positions: find the first position greater than or equal to the key's hash, or wrap to the first entry.

Notice what is missing: there is no % numberOfDatabases in the routing rule.

8. Add a database: split one stretch of the ring

Now place a new database, DB4, on the ring. Existing keys and databases keep their hash positions.

To identify the affected keys, start at the new database and trace anticlockwise to the previous database. The keys in that stretch now encounter the new database first when routing clockwise.

Continuing our miniature example, place DB4 at 35, between DB1 at 20 and DB2 at 50:

Before:
Positions greater than 20 through 50 -> DB2
 
After:
Positions greater than 20 through 35 -> DB4
Positions greater than 35 through 50 -> DB2

The key at 34 moves from DB2 to DB4. A key at 40 stays on DB2. Keys owned by DB1 and DB3 stay where they were.

Only the new database's stretch changes ownership. Anticlockwise tracing helps us see that stretch; requests still route clockwise.

The system must transfer those records from the old owner to the new one. Consistent hashing reduces the scope of the transfer; it does not perform it automatically.

With balanced ownership, adding a fourth database moves roughly one-quarter of the keys, rather than the roughly three-quarters moved by modulo routing. A ring with only one position per database may be far from balanced, as we will see shortly.

9. Remove a database: hand its stretch to the next one

For a separate removal example, reset to our original miniature ring: DB1 at 20, DB2 at 50, and DB3 at 80, with no DB4.

Remove DB2.

Previously, keys after 20 through 50 reached DB2 first. Without DB2, those same keys continue clockwise until they reach DB3.

Before:
Positions greater than 20 through 50 -> DB2
Positions greater than 50 through 80 -> DB3
 
After:
Positions greater than 20 through 80 -> DB3

To find the affected stretch, trace anticlockwise from the removed database to the previous active database. To find the new owner, go clockwise from the removed database to the next active one.

Those are two different directions for two different purposes. The previous database marks the boundary; it does not receive the moved keys.

Only the removed database's keys change owners. Keys already assigned to surviving databases keep their owners.

If DB2 failed unexpectedly, DB3 still needs access to a replica or recovered copy of DB2's data to serve those keys. Consistent hashing handles placement, not replication or failure detection.

10. A ring can still be badly balanced

We have reduced unnecessary movement, but we have not guaranteed an even distribution.

A hash function spreads values across its range. That does not mean three particular database IDs will land at equally spaced positions.

Suppose our miniature ring instead places DB1 at 10, DB2 at 20, and DB3 at 30.

DB2 owns a stretch of length 10, and DB3 owns a stretch of length 10. DB1 owns the remaining stretch of length 80, wrapping from after 30, past 99 and 0, through 10.

With uniformly distributed key hashes, DB1 would hold about 80% of the keys, while each other database holds about 10%.

If those keys receive similar traffic, DB1 will also handle most of the requests. Adding databases is not very helpful if one of them still does most of the work.

The problem is giving each physical database only one position on the ring.

11. Spread each database across virtual nodes

Instead of placing DB1 on the ring once, place several labels for it:

hash("DB1#1")
hash("DB1#2")
hash("DB1#3")

Do the same for DB2 and DB3. Each label gets its own position on the ring, but all DB1 labels point to the same physical database.

These positions are called virtual nodes, often shortened to vnodes.

The lookup rule barely changes:

Move clockwise from the key's hash to the first virtual node, then send the request to the physical database behind it.

A request that reaches DB2#3 goes to DB2. Virtual nodes are not extra database processes, and they do not create extra copies of a record.

Instead of owning one potentially huge stretch, each database owns several smaller stretches scattered around the ring. With enough well-distributed virtual nodes, a large stretch in one place is more likely to be offset by smaller stretches elsewhere.

The diagram shows three positions per database to keep the picture readable. More positions generally improve balance, at the cost of a larger routing map and more ranges to manage. They improve balance statistically; they do not guarantee perfectly equal spacing or load.

When a new physical database joins, we add its virtual nodes. Each takes a small stretch from its next clockwise neighbor, so data can arrive from several existing databases. When a physical database leaves, we remove all its virtual nodes, and their stretches pass to the next surviving virtual nodes.

The principle is unchanged: only the stretches whose owner changes need to move.

We can also assign more virtual nodes to a database with more capacity. But balancing key counts is not the same as balancing traffic: one extremely popular key can still overload its owner. That needs additional techniques such as caching or replication.

The full idea now fits together: sharding gives us more storage and capacity; hashing gives us a repeatable routing decision; a fixed ring keeps most decisions stable as databases change; and virtual nodes make ownership more balanced.

Consistent hashing does not avoid all data movement. It avoids making most of the cluster reshuffle just because one database joined or left.

12. Where is consistent hashing used in real life?

The databases in our diagrams could also be cache servers or application servers. The same question appears in each case: which machine should handle this key, and how much should change when machines join or leave?

Distributed caches: keeping cached data useful

Imagine an online store that caches product details across several Memcached servers. The application uses a product ID as the key to choose a cache server.

Some Memcached clients support consistent hashing for this selection. When another cache server is added, only the keys assigned to it change destinations. Most requests still reach the servers holding their cached values.

Unlike database records, cache entries often do not need to be copied to their new owner. A lookup at the new server misses, the application fetches the product from the database, and the result fills the new cache.

The benefit: fewer keys change destinations, so more cached entries remain useful and the database receives fewer extra requests than it would during a broad reshuffle.

Distributed databases: spreading stored records

Apache Cassandra uses a token ring to distribute data by partition key. A partition key might be a user ID, grouping the records that belong to that user. Its hash determines a position in the token space, and nodes own ranges of that space.

Cassandra supports virtual nodes, allowing one physical machine to own multiple token ranges. When capacity is added, ownership of some ranges changes and the corresponding data is streamed to the new owners.

Real deployments also keep replicas on multiple machines. The ring helps determine placement; replication and other database mechanisms handle durability and consistency.

The benefit: the cluster can grow without repartitioning every record. Cassandra's exact token range and replication rules differ from our simplified 32-bit, single-owner example, but the core idea is the same.

Imagine several servers that generate image thumbnails and keep local copies. If requests for the same image go to random servers, each server may repeat the work and store its own copy.

A load balancer can instead hash the image URL and consistently choose the same backend. NGINX, for example, supports consistent hashing through its upstream hash directive with the consistent parameter.

When a backend joins or leaves, only part of the URL-to-server mapping changes. Most images continue to be served by the machines that already have them cached.

The benefit: better reuse of local cached results. The tradeoff is that one extremely popular image can still send too much traffic to one backend.

13. Pros and cons of consistent hashing

Pros

Less data movement when scaling. Adding or removing a machine changes only the affected ranges, rather than reshuffling keys across the whole cluster.
More cache reuse. Keys whose owners do not change can continue using their existing cached entries, reducing cache misses and pressure on the backing database.
Repeatable routing without a lookup entry for every key. Given the same hash function and ring membership, different application servers can independently choose the same owner.
Flexible capacity distribution. Virtual nodes spread ownership across smaller ranges, and assigning more of them to a larger machine can give it a greater share of the data.

Cons

More machinery than modulo routing. The system must maintain the ring, track membership changes, and make sure routers agree on the current owners. An outdated routing map can send a request to the wrong machine.
Balance is approximate. Virtual nodes improve distribution, but equal key counts do not guarantee equal storage use or request load. Records can differ in size, and popular keys can create hotspots.
Data movement still costs resources. Joining and leaving machines require data transfers or cache refills. Those consume network bandwidth and processing capacity, so transitions need care.
It does not make failures harmless. Finding the next owner does not put the missing data there. Replication, recovery, and coordination during migrations remain separate requirements.
Virtual nodes add overhead. More virtual nodes mean a larger routing map and more ranges to manage. Their number is a tradeoff, not a setting to increase without limit.

Consistent hashing is a good fit when machines change over time and preserving most key-to-machine assignments matters. For a small, fixed set of shards, simpler routing may be enough. The reason to choose it is not that a ring is clever; it is that changing capacity should not force unrelated data to move.