Complexity

Consistent hashing has three costs worth separating: the lookup cost for one key, the memory the ring occupies, and the number of keys that must move when membership changes. The last one is the reason the algorithm exists, so it matters most. Below, N is the number of physical nodes, V the vnodes per node and K the total number of keys.

Time and space of a hash ring

The ring holds N·V points.

A lookup is a single binary search, so even 100 nodes with 200 vnodes each, 20,000 points, take about 15 comparisons. In practice hashing the key often costs more than the search. Calling insort once per point shifts the tail of the array every time, so if membership changes often, prefer a sorted tree or collect everything and sort once. If changes are rare and lookups dominate, a contiguous sorted array is usually the faster choice.

import bisect

def build(points_with_owner):
    # O(M log M) once, instead of M separate insort calls
    items = sorted(points_with_owner)
    points = [p for p, _ in items]
    owner = dict(items)
    return points, owner

points, owner = build([(80, "C"), (10, "A"), (45, "B")])
print(points, owner[points[bisect.bisect_left(points, 50) % len(points)]])  # [10, 45, 80] C

How many keys move

Assuming a well-spread hash, the expected numbers are:

K/(N+1) is exactly what the new node must receive to hold a fair share, so no scheme can move less. In that sense consistent hashing is optimal. It is an expectation, though: with few vnodes, the real amount depends on how large an arc the newcomer happened to land on.

Load balance

With one point per node, the largest of the N gaps that random points cut into a circle is about ln N times the average. With 100 nodes, the busiest one can carry around 5 times its fair share. With V vnodes, a node's share is the sum of V arcs, and the relative spread shrinks roughly like 1/sqrt(V). That is why deployments commonly use tens to hundreds of vnodes per node. More vnodes cost memory and make membership changes slower, so V is a trade-off.

import math

for v in (1, 10, 100, 1000):
    print(v, f"relative spread about {1 / math.sqrt(v):.0%}")
# 1 100%, 10 32%, 100 10%, 1000 3%

These figures only indicate orders of magnitude. If the key distribution itself is skewed, or a few hot keys dominate traffic, vnodes do not help; you need replication or a separate cache tier.

Comparison with alternatives

Rendezvous lookups scale with the node count, but for a few dozen nodes they are fast enough and the code is the shortest. Jump hash needs no memory and balances almost perfectly, but nodes are numbered 0..N-1 rather than named, and removing a bucket from the middle is not supported. It suits data shards whose count grows in order better than caches where any server can fail.

def jump_hash(key: int, num_buckets: int) -> int:
    # Lamping & Veach (2014): O(log n) time, no memory
    b, j = -1, 0
    while j < num_buckets:
        b = j
        key = (key * 2862933555777941757 + 1) & 0xFFFFFFFFFFFFFFFF
        j = int((b + 1) * ((1 << 31) / ((key >> 33) + 1)))
    return b

print(jump_hash(123456789, 10), jump_hash(123456789, 11))

Growing from 10 to 11 buckets changes about 1/11 of the keys, and every key that changes goes to the new bucket 10.

Summary

• Ring lookup is O(log(N·V)) and memory is O(N·V).
• Adding a node moves about K/(N+1) keys in expectation, the unavoidable minimum.
• Vnodes cut the spread roughly to 1/sqrt(V) at the price of memory and update cost.
• Few nodes: rendezvous. Numbered shards: jump hash. General purpose: a vnode ring.