Crate maglev_hash 

Maglev consistent hashing with top-K preference lists.

This crate implements the lookup table construction algorithm from the Google Maglev paper, extended with a top-K preference list for replica-aware routing.

Maglev consistent hashing

Maglev hashing assigns keys to nodes via a fixed-size lookup table whose size is a prime number. Each node generates a permutation of table slots; the table is filled round-robin from these permutations. This achieves:

• O(1) lookups — a single hash indexes into the table.
• Minimal disruption — when a node is added or removed, only a small fraction of keys are remapped (close to the theoretical 1/n optimum).
• Uniform distribution — load is spread evenly across nodes.

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() returns an ordered preference list of up to K distinct nodes for a given key by walking the lookup table from the hashed slot and collecting unique nodes. The first element always agrees with get(). This is useful for replica fallback: if the primary node is unavailable, the caller can try the next node in the list.

is_match() checks whether a specific node appears in the top-K preference list for a key, useful for determining if a node should accept a given 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.

Example

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}");

Structs

MaglevTable

Maglev consistent hashing table.