Skip to content

PATTERN Cited by 1 source

Multi-probe consistent hashing

Definition

Multi-probe consistent hashing is a variant of consistent hashing that trades slower lookups for linear space and no virtual nodes. Each physical node is assigned exactly one ring position; on lookup, the key is hashed multiple times through distinct hash functions, producing several candidate ring positions; the closest node clockwise from any of those candidates wins (Source: sources/2023-02-22-highscalability-consistent-hashing-algorithm).

Introduced by Ben Appleton and Michael O'Reilly (Google) in their 2015 paper Multi-Probe Consistent Hashing.

Why it matters

Raw consistent hashing has high arc-length variance; the canonical fix is virtual nodes, which balances at the cost of O(N × k) ring-BST memory and operational complexity. Multi-probe offers an alternative trade-off:

Property Raw ring Virtual nodes Multi-probe
Ring space O(N) O(N × k) O(N)
Lookup cost O(log N) O(log N × k) O(probes × log N)
Add/remove node O(log N) O(k × log N) Amortised O(1)
Load balance Poor Good Good
Operational complexity Low High (BST bloat) Medium

From the source:

"The Multi-probe consistent hashing offers linear O(n) space complexity to store the positions of nodes on the hash ring. There are no virtual nodes but a node is assigned only a single position on the hash ring. The amortized time complexity for the addition and removal of nodes is constant O(1). However, the key (data object) lookups are relatively slower."

Mechanism

Source's description:

"The basic gist of multi-probe consistent hashing is to hash the key (data object) multiple times using distinct hash functions on lookup and the closest node in the clockwise direction returns the data object."

The probe count is a tuning knob — more probes improve balance but raise per-lookup cost. The 2015 paper derives the probe count needed to achieve a given variance bound.

When to prefer multi-probe

  • Memory-constrained deployments where the O(N × k) vnode BST is too expensive.
  • Stable node sets where amortised O(1) add/remove amortises well.
  • Tolerance for slightly slower lookups — multi-probe hashes the key several times per query instead of once.

When vnodes win

  • Lookup-heavy workloads where per-query cost dominates.
  • Frequently-changing node sets where a smaller BST doesn't justify the probe overhead.
  • Heterogeneous hardware — vnodes let you assign more ring positions to bigger nodes; multi-probe needs a separate weighting mechanism.

Seen in

Last updated · 517 distilled / 1,221 read