Struct Maglev 

pub struct Maglev { /* private fields */ }

Maglev consistent hashing (Google, NSDI’16).

Builds a precomputed lookup table of M (a prime, default 65537) slots from the stable, full backend set. Each backend derives a (offset, skip) permutation from two seeded hashes and claims slots in permutation order until the table is full; a backend’s share of slots is proportional to its weight.

The table holds one entry per distinct address: several backend ids at one address claim the slots of one backend, weighted by the heaviest of them over the full set (outranks_at_address), and the lookup returns the one candidate the caller retained at that address.

Rebuild discipline (never on the hot path)

The table is rebuilt only when the full backend set changes (Maglev::rebuild, wired into BackendList::add_backend / remove_backend), never per packet. Building the table is O(M) = 65537 slot writes; doing it per datagram would be a DoS amplifier (one unhealthy backend would trigger a full rebuild on every selection) and would also destroy Maglev’s stability, since the table would track a shifting subset.

Selection (handles a shrunk healthy subset without rebuilding)

At selection time the caller passes the healthy subset of backends. Lookup is near-O(1): compute slot = key % M, then probe forward through the table (table[(slot + i) % M]) and return the first entry whose address is present in the healthy subset. The table maps to the full set it was built from; membership is checked against the subset, so an unhealthy backend is simply skipped — no rebuild, and healthy keys stay pinned. If no table entry resolves to a healthy backend, fall back to round-robin over the subset. With no key it falls back to round-robin, which, as for Rendezvous, only a request with no source address reaches.

Implementations

impl Maglev

pub const DEFAULT_TABLE_SIZE: usize = 65537

Default prime table size. 65537 is the smallest prime above 2^16; large enough to keep per-key disruption small on backend churn, small enough to rebuild cheaply off the datapath.

pub fn new() -> Self

pub fn with_seed(seed: u64) -> Self

pub fn with_seed_and_size(seed: u64, size: usize) -> Self

pub fn rebuild(&mut self, backends: &[Rc<RefCell<Backend>>])

Rebuild the lookup table from backends. Called on backend-set change, NOT per packet. Honors backend weight via proportional slot share.

Trait Implementations

impl Debug for Maglev

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Maglev

fn default() -> Self

Returns the “default value” for a type.

impl LoadBalancingAlgorithm for Maglev

fn next_available_backend( &mut self, key: Option<u64>, backends: Candidates<'_>, ) -> Option<Rc<RefCell<Backend>>>

Select the next backend among candidates.

fn rebuild(&mut self, backends: &[Rc<RefCell<Backend>>])

Called by the control plane when the live backend set for a cluster changes, so table-based policies (Maglev) can recompute their lookup table off the datapath. The default is a no-op; only Maglev overrides it.