Build a wide-column store (Cassandra / DynamoDB family) (13 scenes)
Scene 04

The ring — keys and nodes on a circle — arc ownership and the clockwise neighbor

When servers and keys live on the same circular hash space, adding a server only steals the arc back to its clockwise neighbor — about 1/N of the keys move, not (N−1)/N.

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

  1. Watch
  2. Try it
  3. Predict
  4. Capture
mode: single-replicaS0S2S4S6user-42ARC SIZES (deg)S070°S280°S4120°S690°ideal: 90° · range: 70–120°4 servers on the ring — arcs are visibly unequal already; one server owns the biggest slice.
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
What to watch for

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

Highlighted lines are the ones running in the diagram right now.

ring.successor
find the server that owns the arc this key falls into
# tokens is a sorted list of node positions on a 360 ring
def successor(h):
    # smallest token >= h, wrapping around 360
    i = upper_bound(tokens, h)
    if i == len(tokens):
        i = 0   # wrap past the top of the ring
    return owner_of(tokens[i])
 
def route(key):
    return successor(hash(key) mod 360)
ring.addNode
drop a token onto the ring; only one arc gets cut
def addNode(node, token):
    insert_sorted(tokens, token)
    cw_neighbour = successor(token + 1)
    # only the slice (predecessor(token), token] moves;
    # every other arc on the ring is untouched.
    for key in cw_neighbour.keys_in_range(
        predecessor(token), token,
    ):
        stream(key, cw_neighbour -> node)

Where this sits in Build a wide-column store (Cassandra / DynamoDB family)

Scene 04 of 13, in the The ring act — Consistent hashing + vnodes — adding a server moves only ~1/N of keys.. Map both keys and servers onto a circle; each key belongs to the next server clockwise.

Up next. The ring is great in theory, but in a 4-server cluster, those four arcs are wildly unequal — one server gets crushed.

All 13 scenes in Build a wide-column store (Cassandra / DynamoDB family) · Every curriculum

Built with Arqly
Every scene in Build a wide-column store (Cassandra / DynamoDB family) builds on the one before it.All 13 Build a wide-column store (Cassandra / DynamoDB family) scenes