Maglev

Maglev consistent hashing for Elixir and Erlang.

A Maglev table gives every backend an almost equal share of a fixed-size slot table, and keeps most keys pointing at the same backend when the backend set changes. Lookups are a single tuple index, independent of how many backends there are.

The algorithm comes from Maglev: A Fast and Reliable Software Network Load Balancer (Eisenbud et al., NSDI '16), section 3.4. The paper is also available from USENIX, which hosts a later revision alongside the session slides.

Contents

• Installation
• Quick start
• How it works
• Choosing a table size
• Weighted backends
• Backend keys
• Independence from input order
• Assigning work consistently
• API summary
• Choosing among consistent hashing algorithms
• Performance
• Resilience to backend changes
• Using from Erlang
• Scope
• Development
• References
• License

Installation

Requires Elixir 1.14 or later and OTP 25 or later. Add maglev to the dependency list in mix.exs:

def deps do
  [
    {:maglev, "~> 0.2.1"}
  ]
end

Quick start

table = Maglev.new(["10.0.0.1", "10.0.0.2", "10.0.0.3"])

Maglev.lookup(table, "session-42")
#=> "10.0.0.2"

Maglev.entry_counts(table)
#=> %{"10.0.0.1" => 21846, "10.0.0.2" => 21846, "10.0.0.3" => 21845}

A table is an immutable term. When the backend set changes, a new one is built and swapped in; there is no mutation and no process to supervise.

table = Maglev.new(["10.0.0.1", "10.0.0.3"])

Callers holding a hash already — a packet five-tuple hash, for instance — can skip the built-in hashing, which is about half the cost of a lookup:

Maglev.lookup_index(table, precomputed_hash)

Any non-negative integer is accepted and reduced with rem(index, size), of any width. No mixing is applied, so the caller's hash carries the distribution on its own: a value with fewer bits of entropy than the table has slots, or one that is not uniformly distributed, leaves slots unreachable or unevenly loaded.

How it works

The table is an array of size slots, each holding one backend. A lookup hashes the key to a slot index and reads it, so lookup cost does not depend on the number of backends.

Construction decides which backend owns each slot. Every backend is given a preference order over all slots, generated from two independent hashes of its name:

offset          = h1(name) rem size
skip            = h2(name) rem (size - 1) + 1
preference[j]   = (offset + j * skip) rem size

Because size is prime, every skip value is coprime to it, so the sequence visits each slot exactly once before repeating. The preference order is never materialised — it is generated one term at a time from a cursor, so a backend costs two integers rather than a size-element list.

Backends then take turns. On each turn a backend claims its most preferred slot that is still empty, advancing its cursor past any slot already taken. The fill ends when every slot is claimed. Since turns are evenly distributed, so are slots.

Worked example

The paper's own example uses three backends, seven slots, and the (offset, skip) pairs (3, 4), (0, 2) and (3, 1). Those give the preference orders:

B0: 3 0 4 1 5 2 6
B1: 0 2 4 6 1 3 5
B2: 3 4 5 6 0 1 2

Taking turns produces:

Removing B1 and rebuilding moves its two slots, and one further slot that belonged to B0:

That extra slot is the cost the algorithm accepts in return for even distribution. This example is a test case, so any change to the construction that breaks agreement with the paper fails the suite.

Choosing a table size

The size must be prime and defaults to 65537. Maglev.table_sizes/0 lists usable primes from 251 to 131071.

Distribution quality is bounded by the ratio of slots to backends. Around 100 slots per backend holds imbalance near one percent. Larger tables also absorb backend churn with less movement, at a higher build cost; lookup cost is effectively unchanged.

Weighted backends

Backends with unequal serving capacity can be given unequal shares:

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

Maglev.entry_counts(table)
#=> %{"large-host" => 49152, "small-host" => 16385}

:weights takes a map, where backends left out weigh 1, or a one-argument function for backends that carry their own weight:

Maglev.new(hosts, key_fun: & &1.id, weights: & &1.cores)

Only ratios matter, so %{a: 2, b: 4} and %{a: 1, b: 2} build the same table. Weights must be positive integers, which keeps the arithmetic that assigns slots exact — independently configured nodes cannot diverge the way float rounding would let them.

Weighting decides who takes each turn. 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 claims on every iteration, one at a third of it claims roughly every third iteration. With equal weights every backend is eligible on every iteration, and the construction reduces exactly to the unweighted one.

Accuracy

Accuracy depends on how many slots the lightest backend earns, which is size * min_weight / total_weight, rather than on the ratio itself:

The last row shows the floor at work: every backend receives at least one slot, and that takes precedence over the requested ratio. A ratio the table cannot express is approximated rather than honoured, so a wider table or narrower weights are needed. Maglev.entry_counts/1 reports what each backend actually received.

Build cost grows with the ratio between the largest and smallest weight. Weights within an order of magnitude of each other cost nothing noticeable; a lopsided set costs several times an evenly weighted one, and no amount of rescaling avoids it, since the cost tracks the ratio and reducing weights by their common divisor leaves the ratio unchanged. See Performance for how the construction limits that growth.

Backend keys

Backend terms are encoded to binaries before hashing:

Deterministic mode means equal terms encode identically however they were built, so a map does not hash differently depending on key insertion order. It 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; backends that collide this way are rejected, since the algorithm cannot distinguish them.

:key_fun overrides the encoding entirely, which is the usual approach for structs:

Maglev.new(hosts, key_fun: & &1.id)

Which hash functions are used

The h1 and h2 in the construction above are two disjoint 64-bit windows of one SHA-256 digest of the encoded backend key. Lookup hashing is separate: Maglev.lookup/2 uses :erlang.phash2/2, which is fast and BEAM-native but not portable outside the BEAM.

Those choices mean a table built here will not match a table built by another Maglev implementation, and that is by design rather than an oversight. Envoy, for instance, derives offset and skip from xxHash64 seeded 0 and 1, and hashes request keys through its own hash policy; either difference alone produces a different slot assignment. Maglev.slots/1 is intended for a datapath that takes its table from this library — exporting slots to a datapath that also computes its own Maglev table will send traffic to different backends on each side.

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 nodes reading the same backends from service discovery in different orders would build different tables and disagree about where every key belongs.

This library sorts backends by encoded key before construction, so a given set yields one table whatever order it arrives in. Independently configured nodes converge without coordinating. Maglev.backends/1 and Maglev.entry_counts/1 reflect that sorted order.

Sorting also improves resilience, because it keeps the fill order stable when the backend set changes. Removing one backend from a set of 1000 moves 0.68% of a 65537-slot table with sorting, against 3.07% when survivors are left in arbitrary order.

The same conclusion has been reached elsewhere. Envoy's Maglev implementation was found to reassign keys when service discovery returned the same hosts in a different order, and now sorts hosts by hash key before construction for this reason (envoyproxy/envoy#20703).

Assigning work consistently

Load balancing is where the algorithm comes from, but on the BEAM the more common use is deciding which node or process owns a given piece of stateful work. Hashing a stable identifier — an order reference, a device id, a tenant — gives every node the same answer without a coordinator or a lookup service:

defmodule Registry do
  def put(nodes), do: :persistent_term.put(__MODULE__, Maglev.new(nodes))

  def owner(key), do: __MODULE__ |> :persistent_term.get() |> Maglev.lookup(key)
end

Every event for a key reaches the same owner, so a process handling them serially preserves per-key ordering without any cross-node negotiation. When a node leaves, only its share of keys is reassigned; every other key keeps its owner, which is the property that makes this survivable during a rolling restart. Sizing the table for capacity rather than for the current node count means adding a node later moves only that node's share.

The guarantee is stable assignment, not exclusivity. Two nodes disagreeing about membership will briefly disagree about ownership, so work that must never run twice needs a lock regardless.

Sharing a table between processes

A table is an immutable term, so passing it in a message copies the whole slot tuple. :persistent_term instead shares a single copy across all schedulers with no copying on read, which is what makes the pattern above cheap.

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 whose cost scales with the number of processes and the size of their heaps, and on a busy node that can exceed the build itself by a wide margin.

Rebuild frequency belongs in minutes or hours, not seconds. The design premise is that backend sets change rarely, and a table rebuilt from a per-health-check or per-request path will spend far more time in the write than in any amount of hashing it saves. Where membership is genuinely noisy, debounce the changes and rebuild on a timer rather than on each event.

Compare tables with Maglev.slots/1 rather than with ==. A table records how it was built as well as what it decided, so two tables that route every key identically can still compare unequal — across a release that changes which fill strategy a given weight distribution selects, for instance. Deciding whether to publish a rebuild by comparing structs would occasionally write for a table that routes exactly as the one it replaces, and pay the collection scan for it.

API summary

Maglev.slots/1 is the form to hand to an external datapath that performs its own lookups, and the form to diff between two tables to measure how far a backend set change moved traffic.

Choosing among consistent hashing algorithms

The overprovisioning figures are from section 5.3 of the paper, measured at 1000 backends and a 65537-entry table.

Maglev hashing suits cases where even distribution matters more than minimal movement, and where the backend set changes rarely enough that a full rebuild is acceptable. Uneven distribution forces every backend to be provisioned for its worst case, and that headroom is paid for continuously, whereas the extra movement is paid for only when backends actually change.

Ring or rendezvous hashing remain the better fit where a backend set changes constantly, or where any avoidable key movement is costly. Jump hashing is the strongest option when backends are numbered rather than named and only ever added or removed at the end.

Performance

Figures below come from a 24-core workstation on OTP 27, at 1000 backends and a 65537-slot table.

Build cost by slot-storage strategy, reproducible with mix run bench/populate_bench.exs:

:atomics is what ships. The fill is the one genuinely imperative step in the algorithm — it writes each slot once and reads slots constantly to test whether they are taken — and a persistent map makes every write allocate. The array never escapes construction, so the mutation is not observable.

The fill accounts for roughly 84% of build time, at about 655,000 slot probes against a theoretical average of 726,000.

Lopsided weights

That loop walks every backend on every iteration and skips the ones not yet eligible to claim a slot, which is free when weights are equal and wasteful when they are not: the iteration count grows with the weight ratio while the number of claims stays at size. A second strategy holds the turn order in a priority queue keyed on each backend's next eligible iteration, so ineligible backends are never visited. Which one runs is decided from the weights, and the two produce identical tables — an equivalence property checks that against the reference implementation, so the choice can only affect build time.

At 1000 backends and a 65537-slot table, each measurement in a fresh process:

Neither strategy dominates, which is why both ship. Selection reads the weights once and costs single-digit microseconds against builds of tens of milliseconds, so the selected column is the chosen strategy's own cost.

The boundary is approximate. The curves cross near a weight ratio of 40 at 100 backends and near 85 at 1000, and no single threshold fits both, because the queue's cost per claim grows faster than the log2(count) term it is weighed against. The threshold errs late: selecting the queue too readily would penalise near-equal weights, while selecting it too late only penalises lopsided sets that are slow under either strategy. The largest penalty measured from a wrong choice is about 1.7x, against gains of 5x to 20x where the queue genuinely wins.

One caveat these figures cannot show. Scanning works entirely in :atomics and allocates nothing, while the queue allocates ordered-set nodes on the process heap. Measured in a fresh process the queue looks its best; called from a long-lived process holding a large heap, it will do worse, and the crossover moves accordingly. Builds happen rarely enough that this is unlikely to matter, but the figures above are a best case for the queue and not a typical one.

Lookup cost, reproducible with mix run bench/lookup_bench.exs:

Hashing the key costs about as much as the index itself, which is what lookup_index/2 exists to skip. Growing the table 2600-fold adds 18% per lookup, which is cache pressure from a larger tuple rather than more work.

Resilience to backend changes

Removing k of n backends must move at least k/n of the table, since the departing backends' slots have to go somewhere. Ring and rendezvous hashing move exactly that much. Maglev hashing moves more, and a larger table moves less:

These replicate figure 12 of the paper and run as part of the test suite under mix test --include slow.

Using from Erlang

The API is plain functions over a struct:

Table = 'Elixir.Maglev':new([<<"a">>, <<"b">>, <<"c">>]),
Backend = 'Elixir.Maglev':lookup(Table, <<"key">>),
Counts = 'Elixir.Maglev':entry_counts(Table).

Options are a proplist, matching Elixir's keyword lists:

Table = 'Elixir.Maglev':new([<<"a">>, <<"b">>], [{size, 8191}]).

Scope

Consistent hashing only. The packet forwarding described in the rest of the paper — kernel bypass, connection tracking, GRE encapsulation, health checking, BGP announcement — is outside what this library does.

The paper pairs consistent hashing with per-machine connection tracking, and treats hashing as the fallback for when connection state is missing. Systems needing connection affinity across rebuilds are expected to hold that state themselves; this library provides the deterministic mapping underneath.

Development

The test suite covers the guarantees stated in the paper as properties, rather than as fixed examples:

mix test                    # unit and property tests
mix test --include slow     # adds the table movement measurements
mix test --cover            # coverage report

Benchmarks:

mix run bench/populate_bench.exs   # build strategies
mix run bench/lookup_bench.exs     # lookup path

Static analysis and formatting:

mix dialyzer
mix format --check-formatted

The fill has two implementations. lib/maglev/populate/reference.ex is map-based and written for clarity rather than speed; lib/maglev/populate/atomics.ex is what ships. The reference is the behavioural definition, and an equivalence property checks the two agree slot for slot, so an optimisation cannot silently change which backend a key lands on.

References

• Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer, NSDI '16 — sections 3.4 and 5.3 cover the hashing.
• Karger et al., Consistent Hashing and Random Trees, STOC '97.
• Thaler and Ravishankar, Using Name-Based Mappings to Increase Hit Rates, IEEE/ACM Transactions on Networking, 1998 — rendezvous hashing.
• Envoy's Maglev load balancer — the weighting semantics implemented here.

License

Apache License 2.0. See LICENSE.