Lesson 4 of 5

Hash rings

9 min read Hashing 3-question check Flashcards included
Next lesson Download flashcards

A hash ring is the concrete data structure under consistent hashing. Hash outputs are fixed-width integers on a circular space 0 .. 2³²−1, and 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, from just past the previous server’s position up to and including its own.

Ownership is clockwise, not closest

The 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.

clockwise continue clockwise key @ 450 key @ 850 wrap past 2³²−1 → 0 server @ 100 server @ 300 server @ 700
key @ 450
key @ 850
wrap past2³²−1 → 0
server @ 100
server @ 300
server @ 700
React Flow
450 walks forward to the first server at or after it. 850 is past the last server, so it wraps through 0 and lands on 100. The server at 300 owns neither.

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. 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, then binary search for the first position ≥ the key’s hash. That’s 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 and server-A#1, so each machine appears many times and the load evens out.

Source: Alex Xu, System Design Interview Vol 1, Ch. 5

Check your understanding

Answer to reveal the explanation. Nothing is scored.

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, which is 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, and a binary search finds the successor in O(log V).

Anki cards

↓ Download deck
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.