Maglev Hashing

Google's Maglev (NSDI 2016) is the L4 load balancer in front of google.com — every packet it forwards needs a backend decision at line rate, millions of times per second per machine. A ring walk is O(log N) with pointer-chasing cache misses; Maglev wanted one hash, one array index. Its answer: precompute a lookup table of fixed prime size M (65537 in the paper) mapping every slot to a backend, then route with table[hash(packet_5tuple) % 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 (where its preference sequence starts) and skip (its stride). Its preference sequence is (offset + i * skip) % M for i = 0, 1, 2, ... — and because M is prime, any skip in 1..M-1 is coprime to M, so the sequence visits every slot exactly once: a full permutation of the table.

Then fill round-robin: backend 1 claims its first unfilled preferred slot, backend 2 claims its first, backend 3 its first; back to backend 1 for its next preference, and so on until all M slots are taken. Every backend wins slots at the same rate, so counts differ by at most a few — with our toy M = 17 and three backends the final split is 6/6/5.

Here is the exercise's actual visible-test trace. With offset from md5 and skip from sha1: A gets (10, 15), B gets (7, 16), C gets (12, 9), so their preference orders begin

A: 10, 8, 6, 4, 2, 0, 15, 13, 11, ...
B: 7, 6, 5, 4, 3, 2, 1, 0, 16, 15, 14, ..., 9, ...
C: 12, 4, 13, 5, 14, 6, 15, 7, 16, ...
round 1: A->10  B->7   C->12
round 2: A->8   B->6   C->4
round 3: A->2   B->5   C->13     (A skips filled 6 and 4)
round 4: A->0   B->3   C->14
round 5: A->15  B->1   C->16
round 6: A->11  B->9   -> full (17 slots)

giving exactly 0:A,1:B,2:A,3:B,4:C,5:B,6:B,7:B,8:A,9:B,10:A,11:A,12:C,13:C,14:C,15:A,16:C.

Membership changes force a rebuild — but every surviving backend keeps its permutation, so it re-claims mostly the same slots: only ~1/N of slots change hands when one backend leaves. And the build is deterministic: every Maglev machine computes the identical table from the identical backend list, so a cluster of them routes consistently with zero coordination. The costs: O(M) memory regardless of N, and O(M log M)-ish rebuild work on every membership change — both fine for a load balancer.

Your exercise

ADD_NODE (dedupe repeats, print OK), BUILD (print <slot>:<owner> for all 17 slots, comma-joined), LOOKUP (print table[sum(key.encode()) % 17]). The grader-caught mistakes: filling depth-first instead of round-robin — letting A place all 17 of its preferences first produces a legal-looking but totally different table, and the expected string above only comes from strict rotation. Forgetting to advance a backend's preference pointer past slots it finds filled — that re-offers the same slot forever. And the empty-table tokens: BUILD with no nodes prints 0:None,1:None,... — Python's literal None in each slot — while LOOKUP foo on that table prints NONE in caps; confusing the two fails the third visible test on exact string match.