Skip to content

CONCEPT Cited by 1 source

Hash ring

The hash ring is the topology used by consistent hashing to lay out nodes and keys: the output of the hash function is treated as a fixed circular address space in which the largest hash value wraps around to the smallest. Both node identifiers and data keys are hashed into the same space; a key is owned by the first node clockwise from its position (Source: sources/2023-02-22-highscalability-consistent-hashing-algorithm).

Why a ring

Framing from the source:

"The output space of the hash function is treated as a fixed circular space to form the hash ring. The largest hash value wraps around the smallest hash value. The hash ring is considered to have a finite number of positions."

A ring gives every node a contiguous arc (the region between itself and its clockwise predecessor) to own. Adding or removing a node perturbs only that arc — remaining arcs are untouched — which is the mechanical reason consistent hashing moves only k/N keys on membership change.

Ring address space sizing

The source's worked example is a 2¹⁰ = 1024 position ring, chosen for pedagogy. Production deployments use 32-bit or 64-bit ring spaces to avoid collisions; the source explicitly warns that the ring "must be of reasonable size to prevent collisions" but doesn't surface the production sizes, which is a gap worth knowing.

Implementation: BST over ring positions

The canonical implementation stores node positions in a self-balancing BST ordered by hash value:

  • Lookup (find next clockwise node for key k) — O(log n).
  • Insert / delete a node — O(log n) BST op + O(k/n) key redistribution.

The BST can live on a centralised HA coordinator or be replicated on every node and synchronised via gossip — Dynamo's choice (Source: sources/2023-02-22-highscalability-consistent-hashing-algorithm).

Last updated · 517 distilled / 1,221 read