Consistent Hashing
Master consistent hashing: distributed data partitioning, virtual nodes, and scalable system design.
What is consistent hashing?
Consistent hashing is a placement technique for choosing an owner from a changing set of nodes. It hashes both keys and node positions into the same ordered space. A key belongs to the first node position reached while walking around that space.
Its core invariant is limited movement during membership change. Adding or removing one node should transfer only the ranges whose owner changed, rather than recomputing almost every key as hash(key) % nodeCount usually does.
Consistent hashing answers where a key should go. It does not copy data, reach consensus, detect failures, move bytes, or make a write strongly consistent. Those behaviors need separate replication, membership, streaming, and consistency protocols.
Put keys and owners in one ordered space
Stable coordinate system
Hash space
A deterministic hash turns each key and node identity into a position. The production hash space is large; lesson diagrams use a small circle so ownership is visible.
Node position
Token
A token is one position owned by a physical node. One node may own many tokens, which split its responsibility into smaller ranges.
Clockwise lookup
Successor owner
Hash the key, find the first token at or after that position, and wrap to the first token when the lookup passes the end of the space.
Movement unit
Token range
The interval after one token and through the next token shares an owner. Membership change transfers ranges, not arbitrary individual keys.
One consistent-hash lookup
Every participant must use the same hash, token map, and ownership direction for the result to be deterministic.
Identity
Stable key
Choose the business identity that must keep the same owner, such as a cache key, tenant ID, or session ID.
Coordinate
Hash position
Apply the agreed hash function and map the result into the ring's numeric range.
Lookup
First token clockwise
Use a sorted token map and a successor search. Wrap around when no larger token exists.
Route
Physical owner
Send the request to the node behind that token, or begin a replica walk when the system stores more than one copy.
See what moves when membership changes
The lab uses the same 72 deterministic key hashes for every comparison. Change the number of virtual positions, then add node D or remove node C. The before and after bars show measured ownership of this fixture, while the modulo baseline shows how many of those exact keys would change owners under hash % nodeCount.
Compare membership changes
Loading the deterministic ring and key fixtures.
Loading the membership model...
Read the result correctly
- The moved percentage is an observation from the fixed sample, not a universal promise for every key distribution.
- Adding one equally weighted node to
Nbalanced nodes tends toward moving about1 / (N + 1)of keys to the new node. - Removing one balanced node tends toward moving that node's prior share.
- More virtual positions usually reduce ownership variance, but they add token-map, maintenance, and failure-neighbor overhead.
- Weighted placement should be modeled through explicit capacity weights and measured distribution, not by assuming every physical node is identical.
Implement the lookup as a small deterministic contract
The essential data structure is a sorted token list. A binary successor search makes lookup O(log T) for T token positions. Membership updates can be less frequent and more expensive, but every client or coordinator must converge on the same token map before routing safely.
Treat membership as a control-plane change
1 Version
Publish the new token map
Give the membership view an epoch or version so stale routers can be detected instead of silently disagreeing about ownership.
2 Transfer
Stream the changing ranges
Copy or rebuild the affected data while the old owner can still serve it. Bound bandwidth so rebalancing does not consume the live request budget.
3 Cut over
Switch authoritative routing
Move reads and writes under an explicit handoff contract. Define how concurrent writes, retries, and a failed transfer are reconciled.
4 Verify
Retire the old ownership
Delete old copies only after integrity, replica count, and request routing are proven for the new map.
Walk replicas across distinct failure boundaries
A ring can nominate several tokens for one key, but several adjacent tokens may belong to the same physical node. Counting those token positions as independent replicas creates false durability. Production storage systems therefore skip duplicate physical owners, and topology-aware strategies can also spread replicas across racks or datacenters.
Use the lab to change the replication factor, placement policy, key position, and failure. The trace shows which tokens are selected or skipped and whether the remaining copies survive the injected boundary.
Trace placement across failures
Loading token, node, domain, and incident fixtures.
Loading the replica model...
Replication factor is not a consistency level. Three placed copies do not say how many must acknowledge a write, how reads reconcile versions, or what happens during a partition. Define those rules independently.
Choose the placement family deliberately
Elastic key ownership
Ring-based consistent hashing
Use a ring when keys or requests need stable affinity while a node set changes and the system can operate token metadata plus controlled movement.
Explicit resharding
Fixed hash slots
Use a fixed slot space when operators should move named slot ranges explicitly. Redis Cluster uses 16,384 hash slots and states that it does not use consistent hashing.
Stateless balancing
Round robin or least request
Use ordinary load balancing when requests do not need key affinity. It can respond to live load more directly than a deterministic hash.
Do not reach for a ring when the real requirement is different
- Use range partitioning when ordered scans and adjacent-key locality dominate.
- Use a partition directory when placement must reflect changing, explicit metadata.
- Use rendezvous or jump hashing when their membership and storage contracts fit better than maintaining a token ring.
- Use a topology-aware database strategy rather than a home-grown ring when the system also needs repair, replica consistency, failure detection, and safe rebalancing.
- Treat a hot key separately. Virtual nodes improve aggregate ownership distribution; they do not split one key across owners.
Operate the movement, not only the hash function
Range share
Ownership balance
Bytes, keys, and requests per physical node
Moved bytes
Membership cost
Transfer rate, duration, retries, and foreground impact
Map epoch
Routing agreement
Stale clients, rejected versions, and ownership mismatches
Replica health
Failure coverage
Distinct nodes and failure domains for every range
Production checklist
- Choose the routing key from the affinity contract and document how multi-key operations behave.
- Use a stable, well-tested hash implementation across languages and versions.
- Measure key count, bytes, request rate, and hot-key skew by owner; none alone proves balance.
- Version membership and define behavior for stale routers during a rollout.
- Throttle range movement and reserve foreground CPU, disk, and network capacity.
- Place replicas on distinct physical nodes and, where required, distinct failure domains.
- Exercise node join, graceful removal, abrupt loss, partial transfer, stale membership, and rollback.
- Verify ownership and checksums before deleting the prior copy of a moved range.
Verify the claims against primary references
- The original ACM consistent hashing paper defines the technique in the context of changing cache populations.
- Apache Cassandra's current Dynamo architecture documentation explains token rings, virtual nodes, distinct physical replicas, and topology-aware placement.
- Cassandra's production token guidance describes the balance between expansion flexibility, streaming peers, and availability.
- Envoy's current ring-hash load-balancer documentation documents host weights, ring sizing, and the expected
1 / Ndisruption for one host change. - Redis documents its different fixed hash-slot model explicitly, including the 16,384-slot key space and operator-driven resharding.