Hash rings

0004 · Hashing · 9 min · Alex Xu, System Design Interview Vol 1, Ch. 5

A hash ring is the concrete data structure under consistent hashing. Hash outputs are fixed-width integers on a circular space 0 .. 2³²−1 (hex is just how we display them). Servers and keys both map to positions on that circle.

Clockwise successor: The owner of a key: the first server at or after the key’s position, walking in increasing integers and wrapping past the top back to 0.
Segment (arc): The stretch a server owns — every position after its own, up to but not including the next server clockwise.

Ownership is clockwise, not closest

The single most-missed detail: a key belongs to the clockwise successor, not the numerically nearest server. From the key’s position you always walk forward. Each server therefore owns the arc behind it — from the previous server’s position up to its own.

key @ 450 server @ 700

450 walks clockwise to the first server at or after it.

key @ 850 wrap past 2³²−1 → 0 server @ 100

Past the last server, wrap around and continue clockwise.

Bounded remapping

Because each server owns a contiguous arc, removing Server B moves only B’s segment to the next server clockwise — roughly 1/N of keys. Servers A and C keep everything they had. This is the whole point: failure and scaling touch one segment, not the entire keyspace.

Lookup at scale

You don’t scan the ring. Store a sorted list of (ring_position, server_id) entries — one per virtual node — and binary search for the first position ≥ the key’s hash, in O(log V). A virtual node is an extra ring position mapped back to a physical server, created by hashing labels like server-A#0, server-A#1, …, so each machine appears many times and the load evens out.

Check yourself

1A key hashes to position 450 on a ring with servers at 100, 300, and 700. Which server owns it?

Ownership is the clockwise successor, not the nearest number: walk forward from 450 to the first server at or after it — 700.

2A key hashes to 850 on a ring whose highest server is at 700 (lowest at 100). Who owns it?

Past the last server you wrap around through 0 and continue clockwise — so 850 lands on the server at 100.

3How do production systems find the clockwise successor without scanning billions of ring slots?

The ring is stored as a sorted array of (ring_position, server_id) virtual-node entries; a binary search finds the successor in O(log V).

Anki cards

↓ Download CSV

On a hash ring, does routing use closest numeric distance or clockwise successor?

Clockwise successor — walk forward (increasing integers) to the first server at or after the key position; wrap to 0 if past the end.

What arc does a server own on the hash ring?

All positions after its own ring position up to (but not including) the next server clockwise.

Key hashes to 450 on a ring with servers at 100, 300, and 700. Which server owns it?

Server at 700 (first server at or after 450 going clockwise).

How do production systems find the clockwise successor without scanning billions of slots?

Store a sorted list of (ring_position, server_id) virtual-node entries; binary search in O(log V) time.

When Server B is removed from a 3-node ring, what fraction of keys typically remap?

Roughly 1/N — only keys on B's segment move to the next clockwise server; A and C keys stay put.

What is a virtual node on the hash ring?

An extra ring position mapped back to the same physical server (e.g. hash("server-A#0"), hash("server-A#1")) to spread load evenly.