Consistent hashing explained simply with 10 keys

Consistent hashing explained simply: keep the hash space fixed when the server count changes, then move only the key range claimed or released by one server.

The ring picture is useful, but the movement count is the point. With a small fixed example, ordinary modulo hashing moves seven of ten keys when a server is added. A hash ring moves one.

That reduction does not make the system replicated, available, or balanced by request traffic. Those need separate mechanisms.

Why modulo hashing remaps most keys

Suppose ten keys have hash values 6, 19, 27, 41, 54, 63, 72, 84, 91, and 98.

With three servers numbered 0, 1, and 2, ordinary partitioning can choose server as hash modulo 3.

The ten assignments are 0, 1, 0, 2, 0, 0, 0, 0, 1, and 2.

Add server 3 and change the divisor to 4. The assignments become 2, 3, 3, 1, 2, 3, 0, 0, 3, and 2.

Only hashes 72, 84, and 98 stay on the same numbered server. Seven of ten keys move even though the new server adds only one quarter of the final capacity.

The problem is not hashing itself. The divisor is cluster membership, so changing the number of servers changes the placement function for almost every key.

At large scale, those remaps can mean cache misses, data copying, or a temporary dual-read migration. A small membership change can create work across the whole cluster.

Consistent hashing removes server count from the key hash calculation.

Consistent hashing explained simply on a 0 to 99 ring

Keep a fixed circular hash space from 0 through 99. After 99, the next position is 0.

Place four servers at positions A=0, B=25, C=50, and D=75. Assign each key to the first server encountered clockwise from its hash position.

Hashes 6 and 19 go to B. Hashes 27 and 41 go to C. Hashes 54, 63, and 72 go to D. Hashes 84, 91, and 98 wrap around to A.

This clockwise rule matches the partitioning description in Amazon's Dynamo paper.

Each server owns the interval after its predecessor through its own position. Boundary conventions can differ, but every implementation must pick one consistently.

The lookup data structure is usually a sorted list or ordered map of server positions. Find the first position greater than or equal to the key hash, then wrap to the first entry if none exists.

That lookup takes logarithmic time with binary search over ring positions. The hash space does not need an array with one slot per possible hash.

Add one server and count one moved key

Add server E at position 90. It lands between D at 75 and A at 0.

E takes ownership of the interval after 75 through 90. In the ten-key sample, only hash 84 lies in that interval.

Hash 84 moves from A to E. Hashes 91 and 98 remain on A, and every key below 75 keeps its old owner.

The ring changed one local boundary instead of changing the placement function for every key.

If hashes are uniform and ranges are balanced, adding one equal-capacity server to N servers moves roughly one over N+1 of the keys. That is an expectation, not a per-cluster guarantee.

The original consistent hashing paper defines the goal more generally: a consistent hash function changes minimally when its range changes.

The same locality appears during removal. If C at position 50 fails, hashes 27 and 41 move to D, the next clockwise server. The other eight sample keys keep their owners.

Minimal remapping still requires a transfer process. The placement rule identifies affected keys; it does not copy bytes, throttle rebalancing, or decide when the new owner is ready.

One point per server creates skew

The evenly spaced four-server ring above is unusually tidy. Hashing server identifiers to positions produces random gaps.

Imagine A lands at 0, B at 8, C at 52, and D at 77. Their owned intervals have lengths 23, 8, 44, and 25 around the 100-position ring.

With uniformly hashed keys, C expects about 44 percent of the keys while B expects about 8 percent. The algorithm remaps locally but does not promise equal single-point ranges.

Amazon's Dynamo design calls out this non-uniform distribution as a limitation of the basic algorithm.

A physical server can also have more CPU, memory, or storage than its peers. Treating every server as one equal point ignores that heterogeneity.

Virtual nodes improve the distribution of ownership. They are not replicas of the data by definition.

Virtual nodes spread ownership across the ring

Represent each physical server with many independently hashed positions, often called virtual nodes or tokens.

If A, B, and C each own 100 scattered positions, each physical server receives many small intervals instead of one large interval.

Random variation remains, but aggregating many intervals usually produces a much tighter ownership distribution than one point per server.

When B fails, its small intervals pass to several clockwise neighbors. The transferred load is less likely to land on one physical machine.

When a new server joins, its virtual positions take small intervals from many existing owners. Rebalancing can draw from the cluster rather than one neighbor.

Dynamo used virtual nodes for these reasons and could assign more virtual nodes to higher-capacity hardware.

There is a cost. More positions mean more membership metadata, a larger sorted token list, and more transfer ranges to track during a change.

The useful tuning question is not whether virtual nodes are good. It is how many positions produce acceptable ownership variance without making control-plane and rebalancing work cumbersome.

Replication is a second decision

A ring gives one primary owner for a key. Durability and availability require additional copies.

Dynamo stores a key at its coordinator and at N-1 clockwise successor nodes. It calls the distinct storage owners the key's preference list.

Virtual nodes complicate this walk because several adjacent token positions may belong to the same physical server. Dynamo skips positions as needed so the preference list contains distinct physical machines.

That distinction prevents a misleading design. Three virtual positions on one machine are not three failure-independent replicas.

Replication also needs a consistency policy, read and write coordination, repair, and version handling. Consistent hashing supplies placement, not those semantics.

Fanout's system design course treats partitioning, replication, consistency, and failure recovery as connected but separate design choices.

The systems paper reading list is a useful continuation for Dynamo and other production storage designs.

Membership and failure detection sit outside the ring

Every participant needs a sufficiently current view of which physical servers and tokens are active.

The ring cannot decide that a silent server has failed. A membership service, gossip protocol, lease, health detector, or operator action supplies that fact.

Two clients with different membership views can route the same key to different owners.

The original Karger work was motivated partly by operating when clients did not have identical cache views, but a storage system still needs reconciliation rules.

Dynamo propagated membership and token ownership through gossip and used seed nodes to avoid logically separate rings during joins.

A safe rollout therefore has stages: announce membership, stream affected data, verify the new replicas, switch ownership, and retire old copies according to the system's protocol.

Removing a failed server may be logically immediate while rebuilding its lost replicas takes much longer.

Minimal remapping limits the scope of that work. It does not make the work atomic or free.

Uniform keys do not mean uniform traffic

A good hash function can spread many distinct keys evenly while one popular key still dominates requests.

If a celebrity event receives 100 times the traffic of other keys, its owner can become hot even when every server stores the same number of keys.

The Dynamo paper states its load argument with an assumption: even under skew, the popular end contains enough keys for hashing to spread their traffic.

That assumption fails for a single extreme hot key. More virtual nodes will not split one key across owners.

Common responses include caching or replicating the hot value, request coalescing, salting a splittable key, or applying application-aware routing.

Those measures trade simplicity for consistency, invalidation, aggregation, or coordination work.

Consistent hashing balances expected key ownership. Traffic, bytes per value, and compute per request can each have a different distribution.

A hash ring is not the only consistent scheme

The ring is attractive when nodes have stable identities, weighted ownership, or explicit ranges that must be streamed during membership changes.

Other schemes make different tradeoffs. Rendezvous hashing scores every candidate node for a key and chooses the best score, avoiding an explicit ring but requiring candidate evaluation or an acceleration structure.

Jump consistent hash uses no stored ring and maps a key to sequentially numbered buckets with minimal movement.

Its authors report better speed and balance than the Karger ring for that model. Its main limitation is the requirement for sequential bucket numbering, which is awkward for arbitrary server membership.

The algorithm should fit the control plane. A ring with virtual nodes is not automatically superior because it is familiar from system design interviews.

Ask whether servers join by arbitrary identity, whether capacity weights change, whether ranges must be enumerable, and whether every client can store the membership map.

Review the mechanism in this order

First, name the fixed hash space and the exact ownership boundary rule.

Second, run a membership change and count moved keys. Do not stop at drawing a ring.

Third, measure ownership by physical server after aggregating virtual positions. Report variance, not only the average.

Fourth, separate the primary placement rule from replica placement and require distinct physical failure domains.

Fifth, identify who publishes membership, how stale views behave, and how data transfer is completed safely.

Finally, test request and byte skew. A balanced key count can hide a hot key or a server holding unusually large values.

Consistent hashing solves a narrow problem well: it keeps most key-to-owner mappings stable while membership changes. A production design must add transfer, replication, membership, and skew handling around that property.