Lesson 05 · Placing nodes on the ring - Build a Consistent Hash Ring

Placing nodes on the ring

Now the ring gets its residents. A node takes a position on the ring by hashing its name, exactly like a key does. Today you build the Ring type and place nodes on it, so the ring knows who lives where.

The goal

Build a Ring that places named nodes at their hashed positions.

Start here - the target

TO DO

Scenario: Added nodes sit at their hashed positions

Givena new ring with nodes added in the order beta, gamma, alpha

Whenthe ring reports each node position with Pos and lists its Members

Thenalpha is at 28075, beta at 58567, and gamma at 5130

AndMembers returns the three node names sorted by position: gamma, alpha, beta

Background

A hash ring puts nodes and keys in the same space. A node joins the ring by hashing its own name with the very same Pos function a key uses, so alpha sits at position 28075 and gamma sits at 5130. That shared space is the whole trick: to find a key’s node we will just compare their positions on one circle.

Today the ring only needs to remember where each node sits. Store the positions and a map from position back to node name - you will look up nodes by position constantly. Notice that the order nodes are added does not matter; what matters is their order around the ring by position, which is why Members sorts by position rather than by insertion. Nodes alpha, beta, gamma are the cast for the next several lessons, so keep those exact positions handy.

Make it work

type Ring struct {
  positions []uint16          // node positions, we will keep these sorted later
  owner     map[uint16]string // position -> node name
}
func NewRing() *Ring { return &Ring{owner: map[uint16]string{}} }
func (r *Ring) Add(name string) {
  p := Pos(name)
  r.positions = append(r.positions, p)
  r.owner[p] = name
}
// Members: node names ordered by ring position.

CheckpointDONE

The ring places named nodes at their hashed positions. Commit and stop here.