# maglev-hash
[](https://crates.io/crates/maglev-hash)
[](https://docs.rs/maglev-hash)
[](LICENSE-MIT)
Maglev consistent hashing with top-K preference lists for replica-aware routing.
This crate implements the lookup table construction algorithm from the
[Google Maglev paper](https://research.google/pubs/maglev-a-fast-and-reliable-software-network-load-balancer/),
extended with a top-K preference list for replica-aware routing.
## Usage
```rust
use maglev_hash::MaglevTable;
let nodes = vec!["node-a".to_string(), "node-b".to_string(), "node-c".to_string()];
let table = MaglevTable::new(nodes);
// Primary lookup — O(1)
let primary = table.get(&"my-key").unwrap();
println!("primary node: {primary}");
// Top-2 preference list (first element == primary)
let top2 = table.get_top_k(&"my-key", 2);
assert_eq!(top2[0], primary);
println!("fallback node: {}", top2[1]);
// Check if a specific node is in the top-2 for this key
let in_top2 = table.is_match(&"my-key", &"node-a".to_string(), 2);
println!("node-a in top-2: {in_top2}");
```
## Top-K Preference Lists (crate extension)
**Note:** top-K preference lists are *not* part of the original Maglev paper,
which defines only a single-node lookup. This crate extends the algorithm with
`get_top_k()` and `is_match()` for replica-aware routing.
`get_top_k(key, k)` returns up to K distinct nodes in a deterministic
preference order by walking the lookup table from the hashed slot and
collecting unique nodes. This guarantees that:
- The first element always agrees with `get()`.
- The ordering is deterministic and consistent across calls.
- When a node is removed, the relative ordering of remaining nodes is largely
preserved.
`is_match()` checks whether a specific node appears in the top-K for a key,
useful for determining if a node should accept a request when running with
replication.
### Tradeoffs vs. suffix hashing
An alternative approach is to hash the key with different suffixes (e.g.,
`get("key-0")`, `get("key-1")`) and deduplicate. Compared to that approach,
the table-walk method:
- **Guarantees** K distinct nodes in a single pass (no dedup retries).
- **Preserves consistency**: `get_top_k(key, 1)[0] == get(key)`.
- **Couples ranks**: removing a node at rank 1 can cascade and shift ranks 2+,
whereas suffix hashing gives each rank independent disruption.
## Performance
The `get_top_k()` and `is_match()` implementations use a `u64` bitset for
deduplication when the node count is ≤ 64 (zero heap allocation, single-
instruction set/test on x86_64), falling back to a heap-allocated
[`FixedBitSet`](https://crates.io/crates/fixedbitset) for larger rings. The
inner scan avoids modulo arithmetic by chaining two range iterators.
## Properties
- **O(1) lookups** — a single hash indexes into the table.
- **Minimal disruption** — when a node is added or removed, only ~1/n of keys
are remapped.
- **Uniform distribution** — load is spread evenly across nodes.
- **Deterministic** — same node set always produces the same table.
## Correctness guarantees
This crate is tested against pitfalls found in other consistent-hashing
implementations:
- **Deterministic seeds** — fixed seeds ensure all processes build identical
tables from the same node set. (Other crates use random SipHasher keys,
producing different tables on each run.)
- **Independent node hashing** — each node's hash is computed in isolation with
a fresh hasher. Adding or removing nodes does not change existing nodes' hash
values. (Other crates reuse a single hasher across nodes, creating
input-order-dependent tables.)
- **Minimal disruption for preference lists** — adding a node causes ~1/N
disruption at each rank of the preference list, not just the primary. Set
membership of the top-K is preserved with high probability.
- **On-the-fly permutation computation** — the lookup table is built without
pre-allocating the full N×M permutation matrix, using O(M) memory instead of
O(N×M).
## Development
```bash
# Set up pre-push hook (runs fmt, clippy, tests before each push)
git config core.hooksPath .githooks
# Release a new version (bumps Cargo.toml, commits, tags, pushes)
# CI publishes to crates.io automatically on tag push.
cargo release patch # or: minor, major
```
Requires [`cargo-release`](https://crates.io/crates/cargo-release):
`cargo install cargo-release`
## License
Licensed under either of
- [MIT license](LICENSE-MIT)
- [Apache License, Version 2.0](LICENSE-APACHE)
at your option.