Maglev Hashing

Google's Maglev (NSDI 2016) is the layer-4 load balancer in front of google.com. Every packet needs a backend decision at line rate, millions of times per second per machine. A ring walk is O(log N) with cache-missing pointer chases; Maglev wanted one hash and one array index. Your program will build Maglev's lookup table and route keys through it.

A table of fixed size

Precompute a table of M slots, where M is prime (the paper uses 65537), and fill every slot with a backend. Routing is then table[hash(key) % M]. The clever part is filling the table so that it is balanced and stable across rebuilds.

Each backend derives two numbers from its name:

• offset = h32(name + "|offset") % M, where its preference sequence starts;
• skip = h32(name + "|skip") % (M - 1) + 1, its stride.

Its preference sequence is offset, offset + skip, offset + 2*skip, ... all modulo M. Because M is prime, any skip from 1 to M-1 is coprime to M, so the sequence visits every slot exactly once: a full permutation of the table.

Filling the table

Backends take turns, in name order. On its turn a backend walks forward through its own preference sequence, from where it stopped last time, and claims the first slot that is still empty. Repeat until all M slots are taken. Because every backend claims one slot per round, slot counts differ by at most 1.

A worked fill with M = 7 and backends x, y, z:

backend   offset  skip   preference sequence
x         2       3      2 5 1 4 0 3 6
y         5       2      5 0 2 4 6 1 3
z         0       1      0 1 2 3 4 5 6

round 1:  x takes 2    y takes 5    z takes 0
round 2:  x: 5 is taken, takes 1
          y: 0 and 2 are taken, takes 4
          z: 1 and 2 are taken, takes 3
round 3:  x: 4, 0, 3 are taken, takes 6        (table full)

slot:   0  1  2  3  4  5  6
owner:  z  x  x  z  y  y  x

Membership changes force a rebuild, but every surviving backend keeps its preference sequence, so it re-claims mostly the same slots. Measured with M = 65537: going from five backends to six changed 10,992 slots (16.8%, where the ideal is 1/6), and removing one of the six changed 11,009. The build is deterministic, so every Maglev machine computes the same table from the same backend list with no coordination. The costs are O(M) memory whatever N is, and a rebuild on every membership change.

Common mistakes

• Depth-first filling. Letting one backend take all its slots before the next gets a turn is legal-looking but gives a totally different, lopsided table. Fill strictly round-robin.
• Forgetting to move on. A backend that finds a slot taken must advance to its next preference, and remember where it stopped for its next turn. Re-offering the same slot never ends.
• Insertion order. Backends take turns in sorted name order, not in the order they were added, so the table does not depend on the order of ADD_NODE commands.
• The wrong stride range. skip is in 1..M-1, never 0. A zero stride visits one slot forever.
• A composite table size. If M is not prime, some skips share a factor with M and the sequence misses slots. The tests use primes only.

Your exercise

The starter keeps the backend list, rebuilds the table after every ADD_NODE and REMOVE_NODE, and reports CHURN, the number of slots whose owner changed in the last rebuild. You write the offset and skip, the table builder and the lookup.