At the delta where nine mighty rivers converged into one torrential estuary stood an immense circular stone basin carved a thousand years ago: the Sushui Prime Basin.

The shoreline formed a vast, unbroken circle of dressed granite, chiseled with exactly sixty-five thousand five hundred thirty-seven numbered mooring berths, ordered from berth zero to berth sixty-five thousand five hundred thirty-six. Why sixty-five thousand five hundred thirty-seven? Because the ancient watermasters understood subtle mathematics: it was a massive prime number, divisible by nothing in heaven or earth save one and itself.

Every dawn, tens of thousands of cargo barges rode the tide through the outer water gate. Burned into the stern of every barge was an imperial vermillion seal carrying five distinct impressions: the sender merchant, departure dock, recipient warehouse, destination wharf, and a unique cargo tally secret.

Deep within the prime basin operated four prestigious transport guilds—the Azure Dragon, Black Tortoise, White Tiger, and Vermilion Bird fleets. Every arriving barge had to be routed to one of these fleets for immediate unloading and distribution.

In the early days, the gatekeepers used the simplest arithmetic: count how many guilds were on duty today, divide the barge’s tally secret by that count, and send the boat to whoever matched the remainder. But during one violent summer thunderstorm, three heavy keelboats of the White Tiger fleet were shattered against the shoals and forced into drydock. With the guild count reduced by one, the modulo calculation shifted for every single vessel. Thousands of chained barges midway through unloading at the Azure Dragon wharves were abruptly rerouted overnight to the Black Tortoise and Vermilion Bird! Ledgers tore, mooring ropes tangled, and the entire harbor froze in gridlock for half a month.

Later, the harbor masters adopted the widely praised “Silk Ribbon Ring”—a closed ribbon where guilds pinned their markers at random intervals, and arriving vessels dropped onto the ring to slide clockwise toward the nearest post. Yet misfortune persisted. When the guild masters rolled dice to set their stakes, the distribution clustered terribly. The Vermilion Bird fleet was assigned an ocean of water and worked their sailors to exhaustion, while the Azure Dragon fleet held only a cramped puddle where crews spent afternoons cracking melon seeds. Worse still, when morning tides brought an avalanche of ships through the gate, the gatekeeper had to unroll yards of silk scrolls, scanning back and forth through the markers to find each match. Ships backed up outside the river gates for leagues.

Then arrived Imperial Surveyor Qi from the Board of Works. He set down a bronze gong and three unbending rules.

Standing atop the watchtower, Surveyor Qi addressed the harbor masters: “River tides wait for no man; a boat passing the gate must be dispatched at a single glance. Workloads must be balanced down to the grain. And when one fleet withdraws for repairs, not a single undisturbed ship shall ever shift its mooring by an inch.”

The watermen came to call this system “The Permuted Tallies.”

First Rule: Private Strides Across the Prime Circle. The harbor abandoned silk rings. The sixty-five thousand five hundred thirty-seven stone berths carved into the granite quay became the sole foundation. Using each fleet’s official heraldic seal, Surveyor Qi computed two fixed integers: an Anchor Offset and a Stride Skip. Because the total number of berths was a prime number, and the stride was never zero, any fleet marching from its offset with fixed leaps was mathematically guaranteed to visit every single berth across the circle without a single omission or duplicate. This sequence became that fleet’s private, immutable preference list for all berths.

Second Rule: The Gong of Alternating Tallies. On the day when berths were assigned for the season, the bronze gong sounded across the basin. The guild masters assembled before the pavilion, competing no longer. At the first gong strike, the Azure Dragon fleet declared its first-choice berth and staked its banner. The Black Tortoise declared its first choice. The White Tiger and Vermilion Bird did the same. At the second gong strike, each fleet declared its second preference. If a berth had already been claimed by an earlier banner, that fleet simply marched forward along its stride rhythm until it found an unoccupied stone berth. Round by round, gong by gong, the guilds claimed berths in lockstep turns. When all sixty-five thousand five hundred thirty-seven berths were claimed, a marvel emerged: every fleet held virtually the exact same number of mooring slips, balanced as if weighed upon a jeweler’s scale!

Third Rule: The Instant Glance. When dawn cargo barges surged through the water gate, the gatekeeper never unfurled a scroll. He simply took the remainder of the barge’s five-seal tally divided by sixty-five thousand five hundred thirty-seven, looked directly up at that numbered stone berth, and shouted the name on the flag: “Berth thirty-four thousand, Azure Dragon!” It was an instantaneous dispatch: no queues, no binary tree searches, no iterative scans. The water gate swung open like thunder, and thousands of ships sped straight to their berths like loosed arrows.

The true elegance shone during the next tempest. When the White Tiger fleet took lightning damage and withdrew to drydock, the harbor masters simply pulled the White Tiger banners from their stone slips. The surviving Azure Dragon, Black Tortoise, and Vermilion Bird fleets merely ran their stride rhythms to fill those vacated slips. Berths originally belonging to Azure Dragon remained Azure Dragon. Those belonging to Black Tortoise remained Black Tortoise. Among the tens of thousands of barges unloading throughout the prime basin, not a single one was forced to change its port!

From that day forth, ten thousand sails crested the Sushui waters, and even when all the empire’s commerce gathered at once, the gates never jammed again.

By now you’ve probably recognized it: this is the celebrated Maglev Consistent Hashing Algorithm, designed and published by Google in their 2016 network load balancing architecture.

What it is

Maglev Hashing is the core consistent hashing and table lookup algorithm presented by Google in the 2016 NSDI paper Maglev: A Fast and Reliable Software Network Load Balancer. It powers Google’s edge software load balancers, Envoy Proxy’s maglev cluster load balancing, and modern cloud-native networking engines like Cilium.

Traditional consistent hashing architectures (such as ring-based Ketama) suffer from two core limitations:

1. Uneven Load Distribution & High Memory Footprint: To achieve acceptable balance across backends on a traditional hash ring, hundreds or thousands of “virtual nodes” must be allocated per server. This inflates memory consumption while still leaving significant load variance.
2. Lookup Latency ($O(\log N)$): For every incoming packet, the load balancer must perform a binary search across an ordered array or red-black tree to locate the nearest point on the ring, introducing CPU cache misses and stalling packet processing at line rate.

Maglev introduced a radically different lookup-table design:

• Prime Lookup Table ($M$): A fixed-size array of prime size $M$ (typically $M = 65537$), substantially larger than the number of backends $N$.
• Deterministic Permutation Generation: For each backend $i$, two independent hash functions compute an initial offset $offset_i = hash_1(i) \pmod M$ and a stride $skip_i = hash_2(i) \pmod {(M - 1)} + 1$. Because $M$ is prime, $skip_i$ is coprime to $M$, ensuring that the sequence $P_i[j] = (offset_i + j \times skip_i) \pmod M$ generates a full pseudo-random permutation visiting all $M$ slots without repetition.
• Round-Robin Table Population: An iterative allocation loop runs across rounds. In each round, every healthy backend claims its next preferred unoccupied slot. If a slot is already taken, it advances along its permutation until finding an empty slot, continuing until all $M$ slots are claimed.
• Instant $O(1)$ Line-Rate Lookup: When a packet arrives, the router computes the hash of the packet’s 5-tuple (source IP, source port, destination IP, destination port, protocol) modulo $M$, and reads the assigned backend directly by array index: backend = lookup_table[hash(packet) % M]. This constant-time, branchless lookup requires no synchronization and executes with near-zero latency.

Why it matters

1. True $O(1)$ Line-Rate Forwarding: In modern 40GbE/100GbE software-defined networks, packet processing budgets are measured in nanoseconds. Maglev replaces $O(\log N)$ binary searches with a single flat array access. The lookup table fits comfortably within CPU L2/L3 caches, enabling commodity x86 servers and kernel eBPF programs to dispatch millions of packets per second at wire speed.

2. Near-Zero Load Imbalance (Minimal Load Variance): Unlike the Poisson-distributed variance of traditional hash rings, Maglev’s turn-by-turn round-robin allocation guarantees that each backend is assigned virtually the exact same number of slots ($\lfloor M/N \rfloor$ or $\lceil M/N \rceil$). Hotspots and traffic skews are eliminated by construction.

3. Minimal Connection Disruption (Consistent Flow Affinity): When a backend fails or new capacity is added, the lookup table is regenerated. Crucially, slots previously belonging to surviving backends overwhelmingly retain their original assignments; only the slots belonging to failed nodes are redistributed among healthy peers. Existing network flows maintain consistent backend routing without connection resets or session drops.

Metaphor mapping

• Sixty-five thousand five hundred thirty-seven berths → Prime-sized lookup table ($M = 65537$)
• Five-seal impression on barge sterns → Network packet 5-tuple (source IP/port, destination IP/port, protocol)
• Transport guilds → Backend servers / endpoints
• Anchor offset and stride skip → Backend hash parameters $offset$ and $skip$
• Stride permutation across berths → Deterministic pseudo-random permutation ($P_i$)
• Gong strikes and round-robin flag placement → Iterative round-robin lookup table population algorithm
• Gatekeeper’s single glance and modulo index → Constant-time $O(1)$ direct array lookup
• Tempest repairs filling only vacant slips → Minimal disruption and stable flow affinity during node failure