ring

Consistent hashing with virtual nodes

What to watch

Which keys move when a fifth node joins

Seed: 1 (default). The program asks a question at the interesting moment; with Predict on, the run stops there so you can answer before you see what happens.

Run it

Edit any file and press Run. The tabs hold the program and the packages it uses.

# package main
use github.com/synodlang/examples/ring
use github.com/synodlang/examples/ringlook
use std/lesson
use std/lists
use std/sim

define main
  set nodes to (sim.Cluster of 4 running ring)
  set keys to {"user:1", "user:2", "user:3", "cart:7", "cart:9", "order:12"}
  each k in keys
    emit (message ring.Placed with Key k, Owner (item 0 of (ring.Owners of k among nodes count 1))) by sim.Nobody
  after 2s
    lesson.Ask "A fifth node joins the ring. How many keys move?" choosing {"All six: every key is hashed again", "None: the new node starts empty", "Only the keys the new node takes over: one of the six", "Half of them"}
    set grown to (lists.Append (sim.Spawn ring) to nodes)
    each k in keys
      emit (message ring.Placed with Key k, Owner (item 0 of (ring.Owners of k among grown count 1))) by sim.Nobody
  sim.StopAt 4s
# package ring
use std/lists
use std/maps
use std/math
use std/sim
use std/text

Placed has
  set Key to ""
  set Owner to sim.Nobody

define Vnodes
  result 8

# Each node owns several points on a ring of [0, 1), derived from its name
define TokensOf [n: node]
  set tokens to {}
  each i in (lists.Range 1 to Vnodes)
    set tokens to (lists.Append (math.Hash (text.Join {(sim.Name n), "#", (text.From i)})) to tokens)
  result tokens

# Clockwise distance from a key's point to the nearest point of a node
define Distance from [h: number] to [n: node]
  set best to 1
  each t in (TokensOf n)
    set d to (math.Remainder of (t minus h) by 1)
    if (d less than best)
      set best to d
  result best

# The first r nodes clockwise from the key own it
define Owners of [k: text] among [ns: list of node] count [r: number]
  set h to (math.Hash k)
  set distances to {}
  each n in ns
    set item n of distances to (Distance from h to n)
  result (lists.Take r from (maps.KeysByValue distances))
# package ringlook
use github.com/synodlang/examples/ring
use std/look
use std/sim
use std/theme

when sim.Started
  draw (look.Circle 200) as wheel
    look.Fill wheel with theme.Paper
    look.Stroke wheel with theme.Line

# A node is a small disc at its first token, drawn over the marks of all its tokens; its keys are listed beside it,
# and a join starts every column again at its owner, since the keys are then written again
when (sim.Added n)
  each t in (ring.TokensOf n)
    draw (look.Circle 4) as mark
      look.Fill mark with theme.Quiet
    look.Orbit mark around look.Center at t
  draw (look.Circle 14) as disc
    look.Fill disc with theme.Ink
  draw (look.Label (sim.Name n)) as name
    look.Fill name with theme.Paper
  draw (look.Group {disc, name}) as card for n
  look.Orbit card around look.Center at (item 0 of (ring.TokensOf n))
  each m in sim.Nodes
    draw (look.Rect 64 by 18) as slot for m
    look.Place slot beside (card of m)
    look.Tween "y" of slot to (card of m) over 0s

# A key is written at the next free row of its owner's column; a key that changes owner moves to the new owner's column
when (sim.Emitted ring.Placed by origin)
  set row to (slot of ring.Placed.Owner)
  draw (look.Label ring.Placed.Key) as tag for ring.Placed.Key
  look.Tween "x" of tag to row over 0s
  look.Tween "y" of tag to row over 0s
  draw (look.Rect 64 by 18) as next
  look.Place next below row
  look.Tween "x" of row to next over 0s
  look.Tween "y" of row to next over 0s

On your own machine: synod run ./ring. Source on GitHub · all examples