# `Maglev`
[🔗](https://github.com/thatsme/maglev_ex/blob/v0.2.1/lib/maglev.ex#L1)

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 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. A table rebuilt
from a per-health-check or per-request path spends 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 `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.

## 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 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. Rescaling does not
help, since the cost tracks the ratio and reducing weights by their common
divisor leaves the ratio unchanged.

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

# `backend`

```elixir
@type backend() :: term()
```

# `t`

```elixir
@type t() :: %Maglev{
  backends: tuple(),
  size: pos_integer(),
  slots: tuple(),
  strategy: module(),
  weights: tuple()
}
```

# `weight`

```elixir
@type weight() :: pos_integer()
```

# `backends`

```elixir
@spec backends(t()) :: [backend()]
```

Returns the backends the table was built over, ordered by encoded key.

## Examples

    iex> Maglev.new(["c", "a", "b"], size: 251) |> Maglev.backends()
    ["a", "b", "c"]

# `entry_counts`

```elixir
@spec entry_counts(t()) :: %{required(backend()) => pos_integer()}
```

Returns the slot count claimed by each backend.

Counts differ by at most one across backends. Monitoring the spread reveals
backends that are underrepresented because the table is too small for the
backend count.

## Examples

    iex> table = Maglev.new(["a", "b", "c"], size: 251)
    iex> table |> Maglev.entry_counts() |> Map.values() |> Enum.sort()
    [83, 84, 84]

# `lookup`

```elixir
@spec lookup(t(), term()) :: backend()
```

Returns the backend assigned to `key`.

The key is hashed with `:erlang.phash2/2`. Callers holding a hash already —
a packet five-tuple hash, for instance — should use `lookup_index/2` to avoid
hashing twice.

## Examples

    iex> table = Maglev.new(["a", "b"], size: 251)
    iex> Maglev.lookup(table, "some-key") in ["a", "b"]
    true

# `lookup_index`

```elixir
@spec lookup_index(t(), non_neg_integer()) :: backend()
```

Returns the backend for an already-computed 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.

## Examples

    iex> table = Maglev.new(["a", "b"], size: 251)
    iex> Maglev.lookup_index(table, 0) in ["a", "b"]
    true

# `new`

```elixir
@spec new(
  [backend()],
  keyword()
) :: t()
```

Builds a lookup table over `backends`.

## Options

  * `:size` - number of slots, which must be prime and at least the number of
    backends. Defaults to `65537`.
  * `:key_fun` - one-argument function returning the binary key to hash for a
    backend. Defaults to the encoding described in the module documentation.
  * `:weights` - relative share of the table each backend should receive,
    given either as a map of backend to positive integer or as a
    one-argument function. Backends missing from a map weigh 1. Defaults to
    equal weights.

Raises `ArgumentError` if `backends` is empty or contains duplicates, if
`:size` is not a prime greater than or equal to the backend count, or if any
weight is not a positive integer.

## Examples

    iex> table = Maglev.new(["a", "b"], size: 251)
    iex> Maglev.size(table)
    251

    iex> table = Maglev.new(["a", "b"], size: 65537, weights: %{"b" => 2})
    iex> Maglev.entry_counts(table)
    %{"a" => 21846, "b" => 43691}

# `size`

```elixir
@spec size(t()) :: pos_integer()
```

Returns the number of slots in the table.

# `slots`

```elixir
@spec slots(t()) :: [backend()]
```

Returns the full slot table as a list of backends, ordered by slot index.

The list has `size/1` elements. It 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.

## Examples

    iex> table = Maglev.new(["a", "b"], size: 251)
    iex> table |> Maglev.slots() |> length()
    251

# `table_sizes`

```elixir
@spec table_sizes() :: [pos_integer()]
```

Returns prime table sizes suitable for the `:size` option.

## Examples

    iex> 65537 in Maglev.table_sizes()
    true

# `weights`

```elixir
@spec weights(t()) :: %{required(backend()) => weight()}
```

Returns the weight the table was built with for each backend.

## Examples

    iex> Maglev.new(["a", "b"], size: 251, weights: %{"b" => 3}) |> Maglev.weights()
    %{"a" => 1, "b" => 3}

---

*Consult [api-reference.md](api-reference.md) for complete listing*