Consistent Hashing

Consistent Hashing: Stable Data Placement in Changing Clusters

Distributed systems face a deceptively simple problem:

Given a key and a changing set of machines, which machine should own that key?

The obvious answer is:

server = hash(key) % N

It is fast and deterministic. While $N$ remains fixed, it works well.

The trouble begins the moment the cluster changes. Add one server and $N$ changes. Remove one and $N$ changes again. Because ownership depends directly on $N$, a large fraction of keys suddenly receive different owners.

For a cache this can mean millions of misses.
For a distributed database it can mean large-scale data movement.
For a request router it can mean sessions landing on different machines.

Consistent hashing solves this by making ownership depend on position rather than cluster size. Both keys and servers are placed on a circular hash space; each key belongs to the next server clockwise. That single change produces the algorithm’s most valuable property: when the cluster changes, only a small, local portion of the keyspace normally needs to move.

1. Why Modulo Hashing Breaks

Suppose four servers exist: A, B, C, D.
A key hashes to 17:

17 % 4 = 1  → bucket 1

Add a fifth server:

17 % 5 = 2  → different bucket

The key itself did not change. The original servers did not change. Only the number of servers changed, yet ownership changed.

With many keys the effect is severe. Changing $N$ can invalidate a huge percentage of existing assignments. In a cache the sequence is particularly damaging:

server added
     ↓
many keys change owners
     ↓
old cache entries become irrelevant
     ↓
hit rate collapses
     ↓
requests flood the backing store
     ↓
database load spikes

Consistent hashing was designed to avoid this global reshuffling.

2. The Hash Ring

Imagine the output of a good hash function as a large ordered space. For a 32-bit hash:

$$0 \dots 2^{32}-1$$

Connect the two ends and the space becomes a ring. Both servers and keys are hashed into that same space.

The ring has no privileged beginning. When a lookup reaches the maximum hash value it wraps around to zero. Every point therefore has a well-defined successor.

3. Ownership Rule

A key belongs to the first server encountered when walking clockwise from the key’s position.

The server does not need to know how many servers exist; it only needs the ordered positions of the current servers.

4. Efficient Lookup

Implementations do not literally walk a circle. They keep the ring positions in sorted order:

12  → Z
41  → X
83  → Y
127 → Z
…

For a key whose hash is 70, binary-search for the first position $\ge 70$. If none exists, wrap to the first position.

lookup(key):
    h = hash(key)
    position = first ring position ≥ h
    if position does not exist:
        position = first ring position
    return server(position)

With $V$ virtual-node positions the cost is $O(\log V)$.

5. Adding a Server

Insert the new server at its hash position. It steals only the keys that previously belonged to its immediate clockwise neighbour and that now fall into the newly created arc. Everything else stays put.

Only the interval between the new server and its predecessor moves.

6. Removing a Server

The keys that previously belonged to the departed server continue clockwise to the next surviving server. All other ranges remain unchanged.

7. How Much Data Moves?

With $N$ evenly balanced servers and $K$ keys, one server owns roughly $\frac{1}{N}$ of the keyspace. An idealized membership change therefore moves approximately $\frac{K}{N}$ keys.

Example: 100 servers, 10 million keys → expected movement of about 100 000 keys. Far smaller than reshuffling most of the data set.

8. The Balance Problem

A single random position per physical server produces arcs of unequal length. One server may own 55 % of the ring while another owns 12 %. The system is stable but unbalanced. This is why production systems use virtual nodes.

9. Virtual Nodes

Each physical server is given many positions (commonly 100–200), created by hashing distinct identifiers such as server-A#0, server-A#1, …. The positions are scattered around the ring.

By the law of large numbers the aggregate ownership becomes nearly uniform. More importantly, when a server fails its many small ranges are inherited by many different successors instead of one neighbour. Heterogeneous capacity is handled simply by giving stronger machines more virtual nodes.

10. Replication

After finding the primary owner, continue clockwise and select the next $R-1$ distinct physical servers. Encountering multiple virtual nodes of the same physical server does not count as additional replicas; they share the same failure domain.

11. Implementation Sketch

Maintain a sorted map:

hash position → physical server

Lookup is binary search. Adding a server generates its virtual nodes, inserts the positions, and transfers only the newly owned ranges. Removal is the reverse.

The algorithm itself is small. The hard engineering usually lies elsewhere: membership, rebalancing, consistency, and failure detection.

12. What Consistent Hashing Does Not Solve

It does not determine membership.
It does not detect that a server is dead.
It does not guarantee that every node has the identical view of the ring at the same instant.

Those problems are solved by service discovery, gossip, failure detectors, configuration stores, or consensus protocols. Consistent hashing assumes a membership view and answers: “Given this set of nodes, who owns this key?”

13. Core Properties

• Monotonicity – keys move from old servers to new ones, not arbitrarily among old servers.
• Locality – membership changes affect only neighbouring ranges.
• Balance – virtual nodes make ownership approximately uniform.
• Determinism – the same ring yields the same owner on every node.
• Incremental scaling – capacity can be added without rebuilding the entire keyspace.
• Natural successor ordering – useful for both replica placement and failover.

14. Disadvantages and Practical Limitations

Despite its strengths, consistent hashing is not free of cost:

• Implementation complexity – maintaining a correct sorted ring, handling wrap-around, generating virtual nodes, and transferring ranges cleanly requires careful engineering and thorough testing.
• Hash-function quality – a poorly distributed hash produces hot spots and uneven arcs even with virtual nodes.
• Metadata and lookup overhead – hundreds of virtual nodes per server increase memory for the ring and make each lookup $O(\log V)$ rather than $O(1)$.
• Temporary imbalance during rebalancing – while ranges are being transferred, some servers temporarily hold extra load.
• Dependence on accurate membership – if nodes have divergent views of the ring, they will route to different owners and create consistency problems.
• Limited flexibility for ordered data – pure consistent hashing does not preserve key order, so range queries are awkward unless combined with other techniques.
• Resource spikes on large membership changes – although only $\approx K/N$ keys move, moving them still consumes network and disk bandwidth.

These limitations explain why some systems prefer rendezvous hashing (no explicit ring) or jump consistent hashing (constant-time, minimal memory) for certain workloads.

15. Alternatives in Brief

• Rendezvous (highest-random-weight) hashing – scores every server for a key and picks the highest; no ring required.
• Jump consistent hashing – extremely fast bucket selection with almost no memory; excellent when the number of buckets is known and ordered.

A ring remains attractive when you need explicit ownership ranges, ordered successors, virtual-node weighting, and natural clockwise replication.

16. The Mental Model

Modulo hashing:

key → global calculation that depends on N → bucket

Consistent hashing:

key → position on a circle → clockwise successor

Changing one server changes only the neighbourhood around that server. The global redistribution problem becomes a local ownership problem.

Virtual nodes keep the ownership balanced.
Replication keeps it resilient.
A sorted ring keeps lookups efficient.
Separate membership machinery keeps the system operational.

Final Takeaway

When the set of machines is static, ordinary hashing may be sufficient.
When machines continuously join, leave, and fail, the question changes from “Which bucket does this key map to given $N$ machines?” to “Which machine is responsible for the region containing this key?”

Place servers and keys on the same circular hash space. Assign each key to the next server clockwise. Use virtual nodes for balance. Use replication for durability. The result is a powerful property:

Changing the cluster does not require changing the entire keyspace—only the affected neighbourhood needs to move.

That geometric insight is why consistent hashing remains a foundational technique in distributed caches, partitioned databases, storage systems, and any service whose machine set is never truly static.

System-design problems