maglev

# Maglev

[![Hex.pm](https://img.shields.io/hexpm/v/maglev.svg)](https://hex.pm/packages/maglev)
[![Documentation](https://img.shields.io/badge/documentation-hexdocs-purple.svg)](https://hexdocs.pm/maglev)
[![CI](https://github.com/thatsme/maglev_ex/actions/workflows/ci.yml/badge.svg)](https://github.com/thatsme/maglev_ex/actions/workflows/ci.yml)
[![License](https://img.shields.io/badge/license-Apache--2.0-blue.svg)](LICENSE)

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](https://research.google/pubs/maglev-a-fast-and-reliable-software-network-load-balancer/)
(Eisenbud et al., NSDI '16), section 3.4. The paper is also available from
[USENIX](https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/eisenbud),
which hosts a later revision alongside the session slides.

## Contents

- [Installation](#installation)
- [Quick start](#quick-start)
- [How it works](#how-it-works)
- [Choosing a table size](#choosing-a-table-size)
- [Weighted backends](#weighted-backends)
- [Backend keys](#backend-keys)
- [Independence from input order](#independence-from-input-order)
- [Sharing a table between processes](#sharing-a-table-between-processes)
- [API summary](#api-summary)
- [Choosing among consistent hashing algorithms](#choosing-among-consistent-hashing-algorithms)
- [Performance](#performance)
- [Resilience to backend changes](#resilience-to-backend-changes)
- [Using from Erlang](#using-from-erlang)
- [Scope](#scope)
- [Development](#development)
- [References](#references)
- [License](#license)

## Installation

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

```elixir
def deps do
  [
    {:maglev, "~> 0.1.0"}
  ]
end
```

## Quick start

```elixir
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.

```elixir
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:

```elixir
Maglev.lookup_index(table, precomputed_hash)
```

## 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:

| Slot | 0  | 1  | 2  | 3  | 4  | 5  | 6  |
| ---- | -- | -- | -- | -- | -- | -- | -- |
| Owner| B1 | B0 | B1 | B0 | B2 | B2 | B0 |

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

| Slot | 0  | 1  | 2  | 3  | 4  | 5  | 6  |
| ---- | -- | -- | -- | -- | -- | -- | -- |
| Owner| B0 | B0 | B0 | B0 | B2 | B2 | B2 |

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.

| Backends | Suggested size | Slots per backend |
| -------- | -------------- | ----------------- |
| up to 20 | 2039           | 100+              |
| up to 80 | 8191           | 100+              |
| up to 160| 16381          | 100+              |
| up to 650| 65537          | 100+              |
| up to 1300| 131071        | 100+              |

## Weighted backends

Backends with unequal serving capacity can be given unequal shares:

```elixir
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:

```elixir
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:

| Weights | Slots | Lightest receives | Error  |
| ------- | ----- | ----------------- | ------ |
| 1:2     | 65537 | 21846             | 0.002% |
| 1:100   | 65537 | 649               | 0.018% |
| 1:1000  | 65537 | 66                | 0.807% |
| 1:1000  | 251   | 1                 | 299%   |

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:

| Term        | Encoding                                        |
| ----------- | ----------------------------------------------- |
| binary      | used as-is                                      |
| atom        | `Atom.to_string/1`                              |
| integer     | `Integer.to_string/1`                           |
| anything else | `:erlang.term_to_binary/2` in deterministic mode |

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:

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

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

## 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:

```elixir
: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

| Function | Purpose |
| -------- | ------- |
| `Maglev.new/2` | Build a table over a backend set |
| `Maglev.lookup/2` | Select a backend for a key |
| `Maglev.lookup_index/2` | Select a backend for a precomputed hash |
| `Maglev.slots/1` | The whole table as a list of backends, by slot index |
| `Maglev.backends/1` | The backends the table was built over |
| `Maglev.weights/1` | The weight each backend was built with |
| `Maglev.entry_counts/1` | Slots claimed per backend |
| `Maglev.size/1` | Number of slots |
| `Maglev.table_sizes/0` | Prime sizes suitable for `:size` |

`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

| | Balance | Movement on change | Lookup | Rebuild |
| --- | --- | --- | --- | --- |
| Ring (Karger) | uneven; needs ~30% overprovisioning at 1000 backends | minimal — only the departing backend's keys | O(log n) search | incremental |
| Rendezvous (HRW) | uneven; needs ~50% overprovisioning at the same scale | minimal | O(n) — hashes against every backend | none |
| Jump | near-perfect | minimal, but only supports adding and removing at the end | O(ln n) | none |
| Maglev | within one slot | higher — moves some slots belonging to unaffected backends | O(1) table index | full rebuild |

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`:

| Strategy | Build time | Memory |
| -------- | ---------- | ------ |
| `:atomics` | 19.0 ms | 1.00 MB |
| Functional `:array` | 70.0 ms | 54.6 MB |
| Map | 74.1 ms | 44.0 MB |
| ETS | 101.1 ms | 6.96 MB |

`: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`:

| Table size | `lookup_index/2` | `lookup/2` |
| ---------- | ---------------- | ---------- |
| 251 | 18.7 ns | 40.0 ns |
| 8191 | 19.7 ns | 41.4 ns |
| 65537 | 21.3 ns | 42.9 ns |
| 655373 | 22.1 ns | 43.2 ns |

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:

| Backends removed | Floor | 65537 slots | 655373 slots |
| ---------------- | ----- | ----------- | ------------ |
| 0.1% | 0.10% | 0.68% | 0.43% |
| 1% | 1.00% | 3.30% | 1.57% |
| 10% | 10.0% | 13.56% | 11.05% |

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:

```erlang
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:

```erlang
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](https://research.google/pubs/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](https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/load_balancers)
  — the weighting semantics implemented here.

## License

Apache License 2.0. See [LICENSE](LICENSE).