Build a wide-column store (Cassandra / DynamoDB family) (13 scenes)
Scene 04 · The ring — keys and nodes on a circle
Map both keys and servers onto a circle; each key belongs to the next server clockwise.
Previously
Hash mod N reshuffled 80% of keys when N changed; we need a geometry where servers live in the same space as the keys, so adding one only nudges its neighborhood.
Scene 04
The ring: keys and nodes on the same circle
Diagram
The circle is the **ring** — the entire hash space drawn end-to-end, with hash 0 at the top and increasing clockwise. Server tags sit at fixed positions on the ring; the coloured slice each server owns, stretching counter-clockwise back to the previous server, is its **arc**. A key is hashed onto the ring (the dotted dot) and belongs to whichever server owns the arc it lands in.
the ring — one circular hash space for keys AND servers
an arc — the slice this server owns
user-42 lives in this arc → S6 owns it
Look at the ring. Four servers, four arcs. The key user-42 lives wherever its hash lands — and it lands inside the arc owned by S6. That ownership rule is the entire scheme.
Implementation
ring.successor
find the server that owns the arc this key falls into
1# tokens is a sorted list of node positions on a 360 ring2def successor(h):3 # smallest token >= h, wrapping around 3604 i = upper_bound(tokens, h)5 if i == len(tokens):6 i = 0 # wrap past the top of the ring7 return owner_of(tokens[i])89def route(key):10 return successor(hash(key) mod 360)
ring.addNode
drop a token onto the ring; only one arc gets cut
1def addNode(node, token):2 insert_sorted(tokens, token)3 cw_neighbour = successor(token + 1)4 # only the slice (predecessor(token), token] moves;5 # every other arc on the ring is untouched.6 for key in cw_neighbour.keys_in_range(7 predecessor(token), token,8 ):9 stream(key, cw_neighbour -> node)