Consistent hashing assigns keys to owners so that adding or removing a node can affect part of the dataset while preserving many previous assignments. It is useful when topology changes and redistributing everything would be expensive. Map stability does not guarantee balanced load or complete the data migration.
The problem arises when distributing a cache across instances, placing data in shards, or choosing a destination for related requests. These cases share a routing decision but have different contracts: losing a reconstructible entry and losing an authoritative write require different responses.
Hash modulo and changing size
A simple scheme computes hash(key) % N and uses the result as a position in a list of N nodes. The same key and configuration produce the same position. A directory lookup is unnecessary for every operation if all participants know the list.
When N represents the number of physical nodes and changes, the divisor changes too. With illustrative hashes, 10 % 3 gives 1 and 10 % 4 gives 2; 45 % 3 gives 0 and 45 % 4 gives 1. Many keys can change destination even though the existing nodes remain available. The mapping from positions to nodes also needs to remain defined.
Modulo is not inherently wrong. A fixed number of logical partitions or slots can preserve the calculation while a separate map changes which node owns each partition. This moves selected groups without recalculating their identity. The alternative is evaluated by movement granularity, directory cost, and required operations, rather than a universal preference.
A ring and a successor
In the ring model, a function places keys and node positions in a hash space. Points are ordered, and the end wraps back to the beginning. For a key, the first node point reached clockwise is found, including that point if it matches exactly: its successor is the primary owner in this example.
Each position owns the interval from its predecessor, excluded, up to itself, included: (predecessor, position]. The final interval can cross the origin. The function, key encoding, and identity used to calculate positions must be stable and shared; changing those rules can also remap the dataset.
An illustrative space from 0 to 99 makes the mechanism easy to follow. With A at 20, B at 50, and C at 80, A owns (80, 20]: values greater than 80 and less than or equal to 20, passing through the origin. B owns (20, 50] and C (50, 80]. A key placed at 90 reaches A, not C.
The diagram’s two groups show the map before and after adding D. Arrows represent only the schematic clockwise traversal; they do not represent replication, requests, or data movement. The reduced space is illustrative, rather than a required configuration.
--- config: look: handDrawn --- flowchart TD subgraph before["Before"] a0["A · position 20"] --> b0["B · position 50"] b0 --> c0["C · position 80"] c0 --> a0 end subgraph after["After"] a1["A · position 20"] --> d1["New D · position 35"] d1 --> b1["B · position 50"] b1 --> c1["C · position 80"] c1 --> a1 end before ~~~ after
Adding and removing nodes
D is added at 35, preserving the existing positions. Its predecessor is A at 20, and its successor is B at 50. D acquires (20, 35], previously owned by B. B retains (35, 50]; A’s and C’s intervals remain unchanged. This is the reduction in movement sought under these assumptions.
| Illustrative key hash | Before | After adding D |
|---|---|---|
| 10 | A | A |
| 30 | B | D |
| 45 | B | B |
| 70 | C | C |
| 90 | A | A |
If D is removed and the other positions remain, B receives (20, 35] again. If A is removed, its interval crossing the origin passes to the next owner. In every case, the new map must be distinguished from the availability of the bytes in that interval.
With N existing nodes of equal weight and balanced distribution, adding one can move approximately 1/(N+1) of the keys; removing one of N, approximately 1/N. These are estimates under suitable hashes and positions, rather than exact percentages for every ring. They also do not necessarily describe the proportion of bytes, requests, or migration time.
Virtual nodes and weights
A single position per node can produce unequal intervals. Virtual nodes, or tokens, assign several positions to one physical node. Each token owns its interval; the physical owner can receive many intervals spread across the space.
With enough well-distributed positions, assignments become more granular and redistribution can be spread across several owners. Weights can be represented by more positions for higher-capacity nodes. The resulting proportion is approximate; it must be measured against the real workload and each resource’s limits.
Adding new tokens or changing weights also changes assignments. To retain the stability benefit, the design must specify which positions remain and which change. Recalculating a completely different ring and calling it consistent hashing is insufficient.
The Dynamo architecture documented by Cassandra describes the ring and tokens in a storage system. Envoy’s ring hash load balancer applies the idea to routing. They illustrate different contracts, rather than claiming that every database or load balancer uses this strategy.
Keys, load, and hotspots
A uniform hash distributes positions; it does not equalize the work associated with each key. One user can generate far more requests than others, one object can occupy many more bytes, and one operation can cost more CPU. A single hot key still reaches its owner even when thousands of tokens exist.
The choice of key preserves or divides locality. Keeping a tenant’s data together helps certain queries and transactions but can concentrate load. Splitting that entity into buckets can distribute work, with costs for queries, ordering, and coordination. The decision belongs to the data model and its access patterns, rather than the hash function alone.
For a cache, coalescing repeated requests, a local layer, and reads compatible with their freshness can help. In authoritative storage, writes and invariants need the appropriate contract. Replication does not automatically turn a write to one key into work distributed across primaries.
Routing, movement, and availability
Participants need a coherent view of membership: which nodes and tokens exist and which map version they should use. Divergent configuration can send operations on the same key to different owners. A central router, distributed metadata, or updated clients are options with different costs; the ring itself does not coordinate those decisions.
Changing owner does not move data either. A migration must transfer the interval and concurrent writes, verify the destination, coordinate the change of authority, and retain a recovery path. Copies with different states may exist during the transition. Cutover needs explicit rules; returning to an old copy without reconciling new writes can lose information.
In caches, new destinations can cause misses and additional load on the origin. An abrupt addition can produce a cold cache; fallback and recovery require limits to avoid overloading the database. The stability of the remaining keys reduces work but does not eliminate that risk.
Replication, high availability, and backups are additional decisions. If a policy replicates across successors on the ring, it must choose distinct physical nodes and avoid counting several positions of the same physical node as independent replicas. A temporary failure does not always require removing the node from the map: the contract can use a replica or another service policy. Reads, writes, and repair depend on the required consistency; consistent hashing provides neither consensus nor atomicity on its own.
Choosing for the problem
Consistent hashing fits when preserving many assignments through topology changes matters and its operational coordination is acceptable. A logical-partition directory can provide more explicit control over owners and migrations; ranges can favor ordered queries. These techniques can be combined according to the design.
Evaluation must separate key count, bytes per owner, requests, latency, and redistribution cost. It must also explain how map changes are published, what happens during a failure, and when a copy becomes authoritative.
The ring answers where a key is assigned. The complete design must answer who can write it, where its data exists, and how the contract is preserved as ownership changes.