maglev

# Changelog

All notable changes to this project are documented in this file.

The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.1.0/),
and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).

## [0.2.1] - 2026-08-06

No behaviour change. Slot assignment is identical to 0.2.0 and 0.1.0.

### Fixed

- The golden fixture is now declared as an `@external_resource`, so
  regenerating it recompiles the tests that read it. Without that, a
  regenerated fixture left the previous digests compiled in and the suite
  passed while checking nothing.

### Documentation

- Tables are compared 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 compare unequal across a release that changes which
  fill strategy a weight distribution selects.

## [0.2.0] - 2026-08-06

Tagged but never published to Hex; its contents are included in 0.2.1.

Lookup tables are unchanged by this release: the same backends and weights
produce the same slot assignment as 0.1.0, so upgrading moves no traffic. This
is now checked rather than argued — `test/fixtures/golden_0_1_0.txt` records
slot tables produced by the 0.1.0 package as published, and the suite rebuilds
them on every run.

### Changed

- Lopsided weights build faster. The existing fill walks every backend on every
  iteration and skips those not yet eligible to claim a slot, which is free at
  equal weights and wasteful as the weight ratio widens. 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. The strategy is
  chosen from the weights. At 1000 backends and a 65537-slot table, one backend
  weighted 10000 against the rest at 1 builds in 59 ms rather than 1395 ms,
  while evenly weighted sets keep their previous cost.

  The boundary between the two is approximate, and the threshold errs towards
  scanning so that near-equal weights are never moved onto the queue. Selecting
  the slower strategy near the boundary costs about 1.7x at most. The queue
  also allocates where scanning does not, so its advantage narrows when a build
  runs in a process already holding a large heap.

### Added

- A golden fixture pinning slot assignment to the 0.1.0 package as published.
  The equivalence properties establish that the fill strategies agree with the
  reference implementation, which is a definition that lives in this repository
  and could itself move; the fixture depends on no such reasoning. Forcing
  every pinned configuration through the priority queue reproduces 0.1.0
  exactly, including 1000 backends at 655373 slots with a weight ratio of
  10000, which is well beyond the range the properties generate.

### Documentation

- State which hash functions are used. The construction referred to `h1` and
  `h2` without defining them, while `Maglev.slots/1` was described as the form
  to hand to an external datapath — together implying an interoperability that
  does not exist. Tables built here match no other Maglev implementation,
  because the offset and skip hashes and the lookup hash both differ.
- Document that `Maglev.lookup_index/2` applies no mixing, so a narrow or
  skewed hash leaves slots unreachable or unevenly loaded.
- Describe consistent worker assignment, which is the more common use on the
  BEAM than packet routing.
- Give `:persistent_term` rebuild guidance in minutes or hours rather than
  seconds, since the write triggers a global garbage collection scan that can
  cost more than the build.
- Record that weights are reduced by their greatest common divisor, and that
  this does not reduce build cost, which tracks the ratio rather than the
  magnitude.

## [0.1.0] - 2026-08-06

First release.

### Added

- `Maglev.new/2` builds a lookup table over a set of backends, with a
  configurable prime table size and backend key encoding.
- `Maglev.lookup/2` and `Maglev.lookup_index/2` select a backend, the latter
  for callers that have already hashed the key.
- `Maglev.slots/1`, `Maglev.backends/1`, `Maglev.entry_counts/1` and
  `Maglev.size/1` expose the built table for inspection, monitoring and export
  to an external datapath.
- `Maglev.table_sizes/0` lists prime table sizes.
- Weighted backends via the `:weights` option, taking a map or a one-argument
  function, with `Maglev.weights/1` reporting what a table was built with.

### Notes

- Backends are sorted by encoded key before construction. The algorithm as
  published fills slots in backend index order, which would otherwise make the
  table depend on the order the backend list arrives in.
- Backends that encode to the same key are rejected, since the algorithm cannot
  distinguish them.
- Weights are positive integers rather than floats, so that the arithmetic
  deciding slot assignment is exact and cannot diverge between nodes.
- Every backend receives at least one slot, which takes precedence over the
  requested weight ratio when a table is too small to express it.

[0.2.1]: https://github.com/thatsme/maglev_ex/releases/tag/v0.2.1
[0.2.0]: https://github.com/thatsme/maglev_ex/releases/tag/v0.2.0
[0.1.0]: https://github.com/thatsme/maglev_ex/releases/tag/v0.1.0