Virtual Nodes

Your ring from the last lesson works, but with one position per node it hands out wildly uneven shares. In this lesson you give every node many positions, and you swap the byte-sum toy hash for one that actually scatters.

One point per node is lopsided

N random cut points split a circle into N arcs of very unequal length, and a node owns exactly one arc. We measured it: ten nodes with one point each, 100,000 keys, and the busiest node held 232% of its fair share while the quietest held 15%. Nothing about the ring rule is wrong. The cut points are simply few.

The fix: K points per node

Give each real node K positions instead of one. Hash name#0, name#1, ... name#(K-1) and place all K virtual nodes (vnodes) on the ring, each owned by the real node. A node's share is now the sum of K small arcs, and sums of independent pieces concentrate: the relative spread shrinks like 1/sqrt(K). Same ten nodes, same keys:

points per node :     1     10    100   1000
quietest node   :   15%    64%    92%    95%
busiest node    :  232%   169%   116%   104%

Production values: libketama places 160 points per memcached server, Cassandra historically used 256 tokens per node. The cost is memory, N x K ring entries, and each lookup is still one binary search.

Store ring entries as (position, node) pairs sorted by position, then node name, exactly as before. The search finds the first entry at or after the key's hash, and the answer is that entry's node. Never key a map by position: two vnodes can share a position, and a map silently keeps only one.

A hash that mixes

Vnodes only help if the positions scatter. The byte sum does not:

hsum("A#0") = 148   hsum("A#1") = 149   hsum("A#2") = 150
hsum("B#0") = 149   hsum("B#1") = 150   hsum("B#2") = 151

Every vnode of every node lands in one tiny cluster, so most keys fall outside it and wrap to the same first entry. The ring algorithm guarantees minimal key movement. Only a well-mixing hash delivers uniform load.

From here on the course uses h32: FNV-1a followed by the MurmurHash3 finalizer, over the string's UTF-8 bytes, in 32-bit unsigned arithmetic.

h = 2166136261
for each byte b of the string:
    h = h XOR b
    h = (h * 16777619) mod 2^32
h = h XOR (h >> 16)
h = (h * 2246822507) mod 2^32
h = h XOR (h >> 13)
h = (h * 3266489909) mod 2^32
h = h XOR (h >> 16)

Check values: h32("") is 2872998923, h32("a") is 444641715, h32("hello") is 2290972270, h32("A#0") is 2353899868. Positions now span 0..2^32-1. The starter implements h32 for your language; read it, because the 32-bit wrap-around (Math.imul in JavaScript, wrapping_mul in Rust, fixed-width unsigned types elsewhere) is the part that differs per language.

Common mistakes

• Strictly greater instead of at-or-after. A key that hashes exactly onto a vnode belongs to it. With VNODES 4 and nodes A, B, C, the key A#2 lands on A's own point, so LOOKUP A#2 must print A. A strict comparison prints B.
• Forgetting the wrap. Keys above the highest point go to the first entry on the ring.
• Incomplete removal. All K points must leave the ring. POINTS exposes leftovers.
• Characters instead of bytes. Hash UTF-8 bytes, and treat each byte as unsigned. A signed char in C or C++ gives a different hash for any key with an accent.

Your exercise

Implement the ring with a configurable number of points per node, plus a LOAD command that measures how evenly it spreads 1,000s of keys. The starter reads the commands and provides h32; you write placing a node, removing it and looking a key up.