Maglev consistent hashing.

A Maglev table assigns every backend an almost equal share of a fixed-size slot table. Keys hash into that table, so selecting a backend is a single array index rather than a search.

How it differs from ring and rendezvous hashing

Ring hashing and rendezvous hashing guarantee that removing a backend disturbs only the slots that pointed at it, and accept uneven distribution as the price. Maglev hashing inverts that trade. Every backend receives either div(size, backend_count) or div(size, backend_count) + 1 slots — a spread of at most one slot, whatever the table size — and in exchange a backend set change may move a small number of slots that belonged to unaffected backends.

The trade favours load balancing. Uneven distribution forces every backend to be provisioned for its worst-case share, and that headroom is paid for continuously; the occasional extra slot movement is paid for only when the backend set actually changes.

Table size

size must be prime, which is what makes each backend's slot preference sequence visit every slot exactly once. It also bounds distribution quality: a table roughly 100 times the backend count holds imbalance near one percent. table_sizes/0 lists usable primes.

Larger tables resist backend churn better and cost more to build. Build cost grows with table size, while lookup cost stays constant.

Example

iex> table = Maglev.new(["backend-a", "backend-b", "backend-c"], size: 1021)
iex> Maglev.lookup(table, "session-42") in Maglev.backends(table)
true

Sharing a table between processes

A table is an immutable term, so passing it in a message copies the whole slot tuple. Where many processes look up against one table, :persistent_term shares a single copy across all schedulers with no copying on read:

:persistent_term.put({:maglev, :api}, Maglev.new(backends))

{:maglev, :api}
|> :persistent_term.get()
|> Maglev.lookup(request_id)

Replacing the term is atomic, so a rebuild swaps in without readers observing a partial table. Writes are the expensive side: each one triggers a global garbage collection scan. That suits a table rebuilt when the backend set changes, and not one rebuilt per request.

Backend keys

Backend terms are encoded before hashing: binaries are used as-is, atoms and integers via their text form, and any other term through :erlang.term_to_binary/2 in deterministic mode, which requires OTP 25 or later. A backend's encoded key determines its slots, so the key must stay stable for the table to stay stable. Binaries are the safest choice. Note that :web and "web" encode identically and therefore collide.

Pass :key_fun to control the encoding directly. Two backends that encode to the same key are rejected, since they would be indistinguishable to the algorithm.

The two hashes that place a backend are disjoint 64-bit windows of one SHA-256 digest of its encoded key. Lookup hashing is separate: lookup/2 uses :erlang.phash2/2, which is fast and BEAM-native but not portable off the BEAM. A table built here therefore does not match one built by another Maglev implementation — Envoy, for instance, derives offset and skip from xxHash64 and hashes request keys through its own hash policy. slots/1 is meant for a datapath that takes its table from this library, not one computing its own.

Independence from input order

The construction in the paper fills slots by letting backends take turns in index order, which makes the resulting table depend on the order the backend list happens to be in. Two callers holding the same backends in different orders would build different tables and disagree about where every key belongs.

Backends are therefore sorted by encoded key before construction. A given set of backends yields one table, whatever order it is supplied in, so independently configured nodes converge without coordinating. backends/1 and entry_counts/1 reflect that sorted order.

Weighted backends

Passing :weights gives backends unequal shares of the table, for serving capacity that is not uniform:

Maglev.new(backends, weights: %{"large-host" => 3, "small-host" => 1})

Only the ratios matter, so %{a: 2, b: 4} and %{a: 1, b: 2} build the same table. Weights must be positive integers; the arithmetic stays exact, so independently configured nodes cannot disagree the way float rounding would let them.

A backend claims a slot on iteration t when t * weight reaches an accumulator that grows by the largest weight in the set after every claim. A backend at the largest weight therefore claims on every iteration, one at a third of it claims roughly every third iteration, and slot counts come out proportional to weight.

How closely counts track weights depends on how many slots the lightest backend earns, which is size * min_weight / total_weight, rather than on the ratio itself. Around 100 slots for the lightest backend holds the error near a tenth of a percent; at a few dozen it approaches one percent; below ten it degrades quickly. A 1:100 split across 65537 slots is accurate to 0.02%, while a 1:1000 split across 251 slots cannot be expressed at all.

In that last case the lighter backend still receives one slot. Every backend is eligible on the first iteration, so none is starved entirely while the table has room, and that floor takes precedence over the requested ratio. Lopsided ratios are therefore approximated, not honoured — widen the table or narrow the weights.

Build cost also scales with the ratio between the largest and smallest weight, because low-weight backends are visited on iterations where they cannot yet claim anything. One backend at weight 1000 among ninety-nine at weight 1 takes several times as long to build as an evenly weighted set of the same size. Weights within an order of magnitude of each other cost nothing noticeable.

entry_counts/1 reports what each backend actually received, which is the check for whether a given ratio came out as intended at a given table size.

Reference

Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer, NSDI '16. The lookup table construction is described in section 3.4. The paper notes that weighting is achieved by altering the relative frequency of backends' turns, but does not give an algorithm; the accumulator here follows Envoy's.