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
• Sharing a table between processes
• 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.1.0"}
  ]
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 scales with the ratio between largest and smallest weight, because low-weight backends are visited on iterations where they cannot yet claim a slot. One backend at weight 1000 among ninety-nine at weight 1 builds in 131 ms against 19 ms for the same set evenly weighted. Weights within an order of magnitude of each other cost nothing noticeable.

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).

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, not one rebuilt per request.

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.

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.