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