Consistent hashing

The hash space stays fixed. Membership changes only edit nearby token ranges.

That is the useful part of consistent hashing.

In this seven-key model, a fifth node moves six keys with modulo hashing and one key on the ring.

Why modulo hashing moves so many keys

A simple sharding rule looks like this:

owner = hash(key) % node_count

It is easy to compute, but the node count is part of every assignment. Add or remove a node and the divisor changes. Many keys get a new remainder even when their old node is still healthy.

For a cache, that means a burst of misses. For stored data, it means moving data between machines.

The seven rows are only a small fixed example. The point is the dependency. Every assignment uses node_count, so one membership change can affect keys across the full hash space.

Put keys and tokens in the same hash space

Consistent hashing removes the changing divisor.

Hash every key into one fixed range. Give each node one or more tokenA position in the hash space that belongs to a node. positions in that same range. Draw the range as a ring so the value after the last position wraps to the first.

A key belongs to the first token at or clockwise from its hash:

owner = first_token_at_or_clockwise(hash(key))

A token owns the interval after its predecessor and through its own position. In interval notation, that is (predecessor, token]. A key that lands exactly on a token belongs to that token.

Select different keys, then add node E at position 52. E takes (38, 52] from C, the old successor. Keys outside that interval keep their owner.

One join changes one nearby range

Start with tokens at 12, 38, 67, and 88.

• photo hashes to 44, so C at 67 owns it.
• Add E at 52.
• E becomes the first token clockwise from 44, so photo moves to E.
• inbox hashes to 63. C at 67 is still its first clockwise token, so it stays with C.

Removing E reverses the change. E's interval returns to C.

This is the remapping guarantee to remember. Adding or removing one token changes the logical owners in that token's range, not keys scattered around the entire ring. Moving or refilling stored data is a separate step. A physical machine may own many tokens, so adding or removing one machine can change several separate ranges.

Virtual nodes spread ownership

One token per machine can produce uneven ranges. A machine with a long interval owns more keys than one with a short interval.

A virtual nodeIn this note, one token position and its owned range, assigned to a physical machine. is another token position for the same physical machine. More well-distributed positions break large ranges into smaller pieces and usually reduce ownership imbalance.

The chart counts 100 fixed hash positions. It shows the effect of these placements, not a guarantee that every extra token improves every ring.

With enough well-distributed tokens, giving a larger machine more tokens can approximate capacity weighting. The tradeoff is more metadata, more ranges to move, and more work when membership changes.

Replication is a separate rule

Consistent hashing chooses ownership. It does not decide how many copies to keep or how replicas agree.

A common token-ring design walks clockwise for replica owners while skipping tokens that belong to a physical machine already selected. Real systems may also keep replicas in different racks or zones. These rules must be defined separately from the primary lookup.

The rest of the storage system still needs to handle:

• failure detection and membership agreement
• data transfer when ranges move
• replica consistency and repair
• hot keys and uneven request rates
• unequal object sizes or a poor hash function
• overloaded or slow machines

Consistent hashing limits remapping. It does not solve distributed storage by itself.

The full rule

• Hash keys into one fixed range and place tokens in that range.
• Assign each key to the matching or next token clockwise.
• Treat a token's range as (predecessor, token].
• When a token joins, move only its new range from the old successor.
• When a token leaves, give its range to the next token clockwise.
• Use multiple well-distributed tokens per physical machine when one token creates too much imbalance.

Glossary

token

One position on the hash ring.

range

The interval (predecessor, token], owned by that token.

virtual node

In this note, one token position and its range, assigned to a physical node.

rebalancing

Changing logical ownership, then moving or refilling data through a separate mechanism.

Sources

• Consistent Hashing and Random Trees, Karger and coauthors, 1997
• Dynamo: Amazon's Highly Available Key-value Store, DeCandia and coauthors, 2007