Veröffentlicht · wird verbessert
Konsistentes Hashing-Anleitung · 4/6
Dieses Kapitel ist vorerst nur auf Englisch verfügbar.
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.
The ring holds N·V points.
| Operation | Sorted array (bisect) | Sorted tree (TreeMap, std::map) |
|---|---|---|
Lookup get | O(log(N·V)) | O(log(N·V)) |
| Add a node | O(V·N·V) (array shifts) | O(V·log(N·V)) |
| Remove a node | O(V·N·V) | O(V·log(N·V)) |
| Build from scratch | O(N·V·log(N·V)) (one sort) | O(N·V·log(N·V)) |
| Space | O(N·V) | O(N·V) |
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] CAssuming a well-spread hash, the expected numbers are:
| Event | hash % N | Consistent hashing |
|---|---|---|
| N to N+1 | about K·N/(N+1) | about K/(N+1) |
| N to N-1 | about K·(N-1)/N | the departed node's keys, about K/N |
| Who receives keys | almost every node | only the new node (on add) |
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.
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.
| Method | Lookup | Memory | Moved on add | Remove any node | Notes |
|---|---|---|---|---|---|
hash % N | O(1) | O(1) | almost all | almost all move | only for fixed N |
| Ring, 1 point | O(log N) | O(N) | about 1/(N+1) | yes | high variance |
| Ring, V vnodes | O(log(N·V)) | O(N·V) | about 1/(N+1) | yes | the common default |
| Rendezvous (HRW) | O(N) | O(N) | about 1/(N+1) | yes | easy weights and replicas |
| Jump hash | O(log N) | O(1) | about 1/(N+1) | last bucket only | returns a bucket number |
| Maglev | O(1) | table size | slightly above minimal | yes | built for load balancers |
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.
O(log(N·V)) and memory is O(N·V).K/(N+1) keys in expectation, the unavoidable minimum.1/sqrt(V) at the price of memory and update cost.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.