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, extended with a top-K preference list for replica-aware routing.
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}");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.
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.
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 for larger rings. The
inner scan avoids modulo arithmetic by chaining two range iterators.
- 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.
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).
# 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, majorRequires cargo-release:
cargo install cargo-release
Licensed under either of
at your option.