Your application stores cached product pages on three servers. A simple calculation chooses a server for each product, and requests usually find the data where they expect it. Then you add a fourth server to handle more traffic, and suddenly many requests look in the wrong place.
The extra capacity is real, but changing the placement rule has made much of the cache cold. Consistent hashing addresses this disruption by limiting how many keys change their assigned server when membership changes. Understanding that promise also means understanding what hashing does not handle, including data copying, failed writes and overloaded individual keys.
Introduction
This article explains consistent hashing with a small cache cluster and a ring numbered from zero to ninety-nine. The numbers are deliberately simple so we can follow several keys by hand before introducing larger hash spaces and virtual nodes.
A key is an identifier used to find a value, such as product:123. A hash function turns that key into a deterministic number. Deterministic means that the same input, processed with the same algorithm and encoding, produces the same output.
We will compare an ordinary remainder calculation with consistent hashing, add and remove a server, and examine balance, replication and routing updates. The example is a placement model, not a complete database or a guarantee that changing cluster membership is automatically safe.
Start with a Familiar Placement Rule
Suppose the cache has servers A, B and C. Assign them numbers zero, one and two. One common rule hashes the product key and takes the remainder after division by three.
server number = hash(key) % server count
The % symbol means remainder. If a key's hash is 16, division by three leaves remainder one, so the request goes to B. Another key with hash 21 has remainder zero and goes to A.
When hashes are reasonably well distributed and there are many similar-sized keys, this can spread the key count across the three servers. Clients do not need a separate directory entry for every product; they repeat the calculation.
The rule depends on both the hash and the server count. That second dependency becomes troublesome when the cluster changes. Even keys unrelated to the new server can receive a different remainder.
See What Adding a Fourth Server Changes
Add D as server number three. The rule now takes the remainder after division by four. Hash 16 maps to zero, so its key moves from B to A. Hash 21 maps to one, so that key moves from A to B.
Neither key moved to D, yet both changed assignment. Across many uniformly distributed hashes, changing from three to four buckets with this simple numbering remaps a large share of keys, not merely the new server's eventual share.
For a disposable cache, the application can fetch missing values from the database and repopulate them. That is logically possible but potentially expensive. A wave of misses can overload the database at the same time operators are trying to increase capacity.
For durable data, looking on the new server is not enough. The bytes remain at their old location until a migration process copies and reconciles them. A placement rule and a data-transfer protocol solve different parts of the problem.
We want adding D to change the ownership of only the keys D needs to take over, while leaving most other assignments intact.
Put the Servers on a Ring
Imagine the numbers zero through ninety-nine arranged in a circle. After ninety-nine, continue at zero. This is our small teaching hash space; real systems generally use many more possible values.
Place A at position 20, B at 50 and C at 80. Hash a product key to a position on the same ring. Walk clockwise from that position until reaching a server. That server owns the key in this simple model.
0 ---- A:20 ---- B:50 ---- C:80 ---- 99
^ |
|--------------- wraps around --------|
A key at 10 reaches A. A key at 25 reaches B. A key at 60 reaches C. A key at 90 passes the end of the number line, wraps around and reaches A.
The important relationship is between each server and the interval immediately before its position. We will treat the interval as excluding the preceding server's token and including the owning server's token, so boundary values have one defined owner.
Follow a Few Keys by Hand
Use five imaginary products with hash positions 10, 25, 47, 60 and 90. Their original owners are easy to inspect:
| Hash position | First server clockwise | Owner |
|---|---|---|
| 10 | 20 | A |
| 25 | 50 | B |
| 47 | 50 | B |
| 60 | 80 | C |
| 90 | 20 after wrapping | A |
There is no requirement that the product identifiers themselves be ordered. Their hash positions determine placement. Two neighbouring product numbers can land far apart, which helps distribute sequential application identifiers.
The ring is a logical arrangement. It does not mean requests must travel physically through every server in clockwise order. A client or router with the sorted token list can calculate the owner directly.
That distinction prevents a common misunderstanding: consistent hashing is usually about deciding where a request belongs, not building a network where A must forward every request through B and C.
Add a Server Without Rearranging Everything
Now place D at position 65, between B and C. D takes ownership of keys after 50 and up to 65. Previously, those keys reached C at 80.
Our key at 60 moves from C to D. The keys at 10, 25, 47 and 90 keep their owners. No key needs to move from A to B merely because the number of servers changed.
Before: B:50 ---------------- C:80
After: B:50 ---- D:65 ------- C:80
Keys in (50, 65] change from C to D.
This limited reassignment is the core idea. Existing token positions stay fixed, and the new server takes a portion of an existing ownership interval.
The example does not give D exactly one quarter of the ring. With one token per server, placement can be uneven. We have improved the amount of movement, but must still discuss how to distribute ownership fairly.
Remove a Server and Follow Its Keys
If B leaves the four-server ring, its interval needs a new owner. Keys after A at 20 and up to B's old position at 50 now continue clockwise to D at 65.
Our keys at 25 and 47 move from B to D. Keys owned by A and C remain where they were. Again, the mapping changes locally around the removed token rather than recomputing every assignment from a new divisor.
For a cache, those reassigned keys may miss until values are loaded onto D. For replicated storage, another copy may already exist at the intended successor, depending on the replication policy. The hash ring alone does not establish that a valid copy is available.
A temporary failure and a planned permanent removal may need different handling. Immediately changing membership every time one health probe fails can cause unnecessary movement and repeated cold caches.
Use health and membership policies that reflect the workload. The placement algorithm needs a reliable answer to which servers are members; it cannot determine that answer from the hash of a product key.
Understand What Consistent Means Here
The word consistent describes stability of the mapping as the server set changes. It does not mean the stored data is strongly consistent, that every reader sees the latest write or that replicas automatically agree.
A cache cluster can use consistent hashing while serving stale values. A database can use it as part of partitioning while separately implementing replication and conflict resolution. Those are different properties.
The original Amazon Dynamo paper is a primary reference for combining consistent hashing with other distributed-storage mechanisms. The full system includes far more than a ring.
For an interview or design review, name the exact promise: adding a server should reassign a limited subset of keys under the algorithm's assumptions. Then separately explain durability, read consistency and failure recovery.
Using one attractive term for all those guarantees makes diagrams look simpler while hiding the decisions that determine whether the system is safe to operate.
Improve Balance with Virtual Nodes
One token per physical server can produce large ownership differences. A randomly positioned server may inherit a large interval while another receives a very small one. Adding a single token can also transfer a disproportionate amount from one neighbour.
Virtual nodes give each physical server several positions on the ring. These are logical ownership points, not additional machines or operating-system processes. A might own tokens A1, A2 and A3 distributed around the circle.
When a new physical server joins with several tokens, it takes smaller portions from multiple places. That can spread both stored data and migration work more evenly than taking one large interval from one server.
Apache Cassandra's partitioning documentation explains token rings and multiple tokens per physical node. It also describes operational tradeoffs, so more virtual nodes should not be treated as a free universal improvement.
Maintain a mapping from each virtual token to its physical server. Requests ultimately need an actual endpoint, and replica selection must avoid counting several tokens on the same machine as independent copies.
Distinguish Key Balance from Byte and Traffic Balance
An even number of keys does not guarantee equal work. One product description may be two kilobytes while another cached result is several megabytes. Equal key counts can therefore produce unequal memory or disk use.
Popularity adds another dimension. A celebrity's profile might receive a million requests while an ordinary profile receives ten. Hashing distributes the keys, but every request for the celebrity still targets the same logical key.
Virtual nodes improve distribution across many keys. They do not split the work of one hot key automatically. That problem may need replication, local caching, request coalescing or a different data model.
Measure keys, bytes and request cost per physical server. A cluster can look balanced on one chart while a single node reaches its network limit or repeatedly evicts large objects.
When making capacity decisions, identify which resource is constrained. Adding servers helps only if the ownership and access pattern can make use of them without leaving the dominant workload concentrated on one place.
Account for Different Server Capacities
Some clusters mix machines with different memory or processing capacity. Assigning the same expected share to a large server and a much smaller one may overload the smaller member.
A weighted design gives stronger servers more ownership positions or another larger share under the algorithm's supported weighting mechanism. The intended weight should reflect usable capacity for this workload, rather than an arbitrary hardware label.
Changing weights also changes placement. A weight update that appears to be a harmless configuration edit can move substantial data or redirect many cache requests. Treat it as a membership-related operation with the same observation and rollback needs.
Do not use rapidly changing instantaneous CPU as a reason to rebuild the ring continuously. The movement itself creates work, and a momentarily busy server may become even less stable if its ownership changes repeatedly.
For request-only load balancing, a different algorithm may adapt more directly to current load. Stable key affinity and immediate load equalisation are related goals, but neither automatically gives the other.
Keep All Routers on the Same Mapping
If one application instance knows about D and another still uses the old three-server ring, they can send the same key to different places. During a rolling configuration update, this disagreement is a normal possibility.
For a disposable cache, the result may be duplicated entries and extra misses. If cached values are updated or invalidated, different owners can also retain different versions unless the cache design accounts for the transition.
For authoritative data, routing disagreement is more serious. Two servers must not independently accept conflicting writes because different clients believe they are the owner. Use a versioned ownership map and a transfer protocol that enforces the valid write owner.
A proxy layer can centralise routing updates, while client-side routing avoids an extra network hop. Both have operational costs. Client routing needs reliable configuration distribution; proxies need their own capacity and availability design.
Give each mapping an identifiable generation and include that information in diagnostics. It should be possible to explain why a request went to server C after another request for the same key went to D.
Specify the Hash Function and Encoding
Every component must hash the same bytes using the same algorithm. Differences in character encoding, case normalisation or string formatting can produce different owners even when the visible key looks identical.
For example, hashing the number 123 as a binary integer is different from hashing the text "123". Joining tenant and product identifiers without an unambiguous separator can also create accidental key collisions in the input representation.
Define a canonical encoding for composite keys. Include relevant namespace or tenant identity where keys are only unique within that scope. Document how token values are interpreted and how ties are resolved.
Avoid language-runtime hash functions whose outputs can change between processes or releases. A distributed mapping needs a stable contract, not merely a function that is convenient inside one dictionary implementation.
Changing the hash algorithm is a data-placement migration. Version the change and plan how clients and stored data move together. Otherwise a library upgrade can effectively create a new ring without anyone explicitly adding a server.
Add Replication as a Separate Policy
Suppose each key should have two copies. A simple teaching policy chooses the first owner clockwise and then the next distinct physical server. A key owned by D might therefore also be stored on C.
Distinct physical server matters with virtual nodes. Two tokens owned by D are not two independent copies: both disappear if D fails. Real deployments may also require copies in different racks or availability zones.
The replication policy must define how writes reach those copies, how reads choose among them and what happens when one is unavailable. The ring helps choose locations; it does not decide when a write is durable enough to acknowledge.
Adding a server can change replica sets as well as primary ownership. Even keys whose first owner stays the same may need a new replica under the placement policy. Estimate that data movement instead of counting only keys whose primary owner changes.
Keep repair and membership changes coordinated. A server should not be declared fully ready merely because it has received its token list if it has not yet obtained the data copies its role requires.
Use Stable Routing Where Affinity Is Valuable
Consistent hashing is useful beyond stored database partitions. A proxy can route requests with the same session or resource key to the same backend, improving the chance of using that backend's local cache.
Envoy documents ring-hash and related choices in its supported load-balancing algorithms. The important design question is whether preserving affinity is worth the possible imbalance it creates.
A session key should be chosen deliberately. Hashing every request from a large corporate network by source IP can concentrate unrelated users on one server. Hashing a stable authenticated account identifier may be more appropriate for one application and still too concentrated for another.
Affinity is not persistence. If a backend stores essential session state only in memory, reassigning the session after failure loses that state. A shared durable session store or a recoverable stateless design is still needed where the product requires continuity.
The best routing choice depends on what becomes cheaper when requests meet the same backend. If there is little locality benefit, a simpler load-balancing strategy may distribute current request load more effectively.
Plan Cache Warm-Up After a Membership Change
Even limited movement can produce a significant burst. If D takes responsibility for twenty million cached keys, those entries may all be absent initially. Consistent hashing reduces the affected population but does not make the new cache warm.
Bring D into service gradually when the cache implementation supports it. Prewarm selected popular values, cap origin concurrency and coalesce simultaneous requests for the same missing key so one database fetch can serve several waiting callers.
Avoid trying to prewarm every cold key if most will never be requested. Focus on measured popularity and the origin's spare capacity. A warm-up process should not create more database load than the traffic it is meant to protect.
Track misses and origin latency by mapping generation. A short cache-hit dip after adding a server may be expected; prolonged database saturation means the transition needs a tighter budget or different design.
Scale-in deserves the same care. Removing a cache server sends its key population elsewhere. Repeatedly adding and removing nodes around a threshold can keep the cache in permanent recovery.
Understand What Data Movement Still Requires
For a durable store, the ring identifies which keys should move. A migration process must copy their current values, track concurrent changes, validate the result and switch write ownership at a defined boundary.
If the source accepts writes while the copy runs, the destination needs those later updates too. A snapshot without a change stream can leave the new owner missing edits that arrived after its rows were copied.
Deletion must be transferred as well. Copying only present values can resurrect old records if the destination or a returning replica still holds data that the source deleted.
During cutover, old routers should receive a controlled redirect, retry response or forwarding behaviour that respects the current ownership generation. They must not continue writing freely to a retired owner.
Those concerns deserve their own migration design. Consistent hashing makes the set of affected data more manageable; it does not replace the mechanisms that keep that data correct while ownership changes.
Test the Mapping Before Testing the Cluster
Start with deterministic examples like the five keys on our small ring. Verify wraparound, exact token matches and server removal. Every key should have one primary owner under a given mapping.
Generate a larger synthetic key population and measure how many keys move when a server is added. Under an approximately balanced equal-capacity design, the new server should receive roughly its intended share, with variation depending on token allocation and sample size.
Test real key and value distributions as well. Uniform random keys cannot reveal a workload dominated by one popular tenant or a few huge values. Measure movement by bytes and request cost, not only by count.
Run the same test vectors in every routing implementation. A .NET client, a Java service and a proxy must agree on ownership if they participate in the same placement scheme.
Finally, test mixed mapping generations, a server that repeatedly fails health checks and interrupted warm-up. These scenarios expose operational problems that a correct standalone hash function cannot detect.
Walk Through a Controlled Cache Expansion
Return to A, B and C, with D ready to join. Before advertising D, verify that it can serve requests, has the intended memory limit and uses the same cache-key encoding as the existing nodes. A healthy process that interprets keys differently is not ready to share the cluster.
Create the next mapping generation and estimate its effect using recent request samples. Identify how much traffic will move to D and which old nodes currently serve those keys. This gives a practical origin-load estimate rather than only a mathematical fraction of hash space.
Suppose the moved keys account for 25% of requests, and the cluster receives 20,000 requests per second. An entirely cold D could create up to 5,000 requests per second needing some form of refill under this simplified assumption. If the database has spare capacity for only 500, an immediate unrestricted switch is unsafe.
The team can prewarm a bounded popular subset, limit refill concurrency and gradually adjust supported traffic weight. Cached stale data may be usable for selected values under the application's freshness rules, while requests for sensitive current state follow their authoritative path.
After publishing the mapping, observe actual miss rate, request latency and memory use on D. Confirm that old clients converge to the new generation. Keep the previous configuration available for diagnosis, but recognise that switching back can itself cause movement and does not erase the load already generated.
The expansion is complete when D serves its intended workload reliably and the origin returns to its normal operating range. Merely seeing four green server icons proves much less.
Avoid Confusing Failure Detection with Data Ownership
A health check answers a limited question, such as whether a server responded to a probe. A failed check might mean the process stopped, the network path failed or the probe itself encountered a delay.
For an expendable read cache, routing around a temporarily unavailable node may be appropriate. The application can rebuild values elsewhere, subject to the refill limits already discussed. The cost is extra work and potentially inconsistent cached copies during transition.
For a database owner, declaring the server absent has stronger consequences. If another server starts accepting writes while the original still accepts them, the system may create conflicting authoritative histories. The hashing rule cannot tell those servers which one has the right to commit.
Keep membership decisions and write-authority changes connected to the database's supported coordination protocol. Use epochs, leases or another documented mechanism where required, and make stale ownership rejectable at the point of mutation.
This is why a production database's join and removal commands often perform more work than editing a list of addresses. They coordinate the data and authority transition that the ring calculation merely describes.
Keep a Placement Record Operators Can Explain
Record which mapping generation was active, which physical server owned each token and why membership changed. During an incident, this lets the team connect a rise in misses or a misplaced write to a specific transition.
Expose the mapping for a supplied diagnostic key through an authorised tool. The tool can show the canonical key, hash position, selected owner and replica destinations without retrieving the underlying private value.
Compare expected ownership with observed storage and routing. A server holding old copies is not necessarily a defect during migration, but a client still writing under an obsolete generation needs attention. Useful diagnostics distinguish temporary retained data from active authority.
Summary
Consistent hashing limits key reassignment when the server set changes. Mapping keys and servers onto a stable ring lets a new server take over part of the space without changing most unrelated assignments.
Virtual nodes and suitable weighting can improve balance, but key counts, stored bytes and request traffic are different measures. One hot key, inconsistent routing maps or a cold new cache can still create serious load problems.
Treat hashing as a placement tool. Replication, data transfer, write ownership and recovery need separate rules. Understanding those boundaries makes the technique useful without expecting a ring diagram to provide guarantees it was never designed to supply.