Lesson 07 · Wrapping past the top - Build a Consistent Hash Ring

Wrapping past the top

A ring is a circle, so a key sitting past the last node has to come back around to the first. Today you handle that wraparound, the case that makes the ring truly circular rather than just a sorted line.

The goal

Own a key that falls past the last node by wrapping to the first node.

Start here - the target

TO DO

Scenario: A key past the last node wraps to the first

Givena ring with nodes alpha (28075), beta (58567), and gamma (5130), where beta is the last node clockwise

WhenGet is called for cherry (position 59512, past beta)

ThenGet("cherry") returns gamma - the walk wraps past the top of the ring to the lowest-positioned node

Andon a ring with only alpha, every key wraps to alpha, so Get("cherry") and Get("apple") both return alpha

Background

The ring closes on itself, so position 65535 is immediately followed by position 0. cherry sits at 59512, past beta (58567, the highest node), so there is no node clockwise before the top of the ring. Walking clockwise you fall off the top, reappear at 0, and the first node you meet is gamma at 5130 - the lowest-positioned node. So cherry belongs to gamma.

In code this is the “no node at or after the key” branch: when the clockwise scan finds nothing, the owner is simply the first node in ring order. The single-node ring is the cleanest way to see it - with only alpha on the ring, every key either finds alpha directly or wraps around to it, so every key lands on alpha. That is also a reassuring sanity check: one node owns the entire keyspace, exactly as it should.

Make it work

// If no node sits at or after the key, wrap: the owner is the
// lowest-positioned node (index 0 in ring order).
// scan for first position >= kp ...
// if none found:
//   return the first node on the ring

CheckpointDONE

Keys past the last node wrap correctly to the first node. Commit and stop here.