Struct PowerOfTwo 

pub struct PowerOfTwo {
    pub metric: LoadMetric,
    /* private fields */
}

Power-of-two-choices (P2C) load-aware selection: sample two candidates, keep the lighter one, and coin-flip a tie.

Cost: two load reads per selection, whatever the cluster size

The two candidates are drawn uniformly at random from the candidate set and only those two are measured, so a selection costs O(1) load reads against LeastLoaded’s O(n) scan.

That is a statement about load READS and nothing more. It is NOT a claim that a selection is O(1): every selection, under every policy, first collects the candidate positions in crate::backends::BackendList::next_available_backend_with_key, which walks the cluster’s backend list and records the position of each healthy backend in a buffer the list reuses across selections, before any policy runs. That walk is in the caller, this policy does not remove it, and no policy here is sub-linear per request. So P2C is not the “cheap” alternative to a scan — picking it to shorten a per-request walk that lives somewhere else buys nothing.

What the two-read bound does buy is real but narrower: under LoadMetric::ConnectionTime a load read is a PeakEWMA::observe call that decays the backend’s average to the selection’s instant, so two of them per selection instead of n is measurable work removed — under Connections/Requests a load read is a field read and the saving is small.

The reason to choose this policy over LeastLoaded is balance, not cost: P2C buys most of least-loaded’s balance — the classic result is a maximum load of O(log log n) where uniform-random gives O(log n) — without ever computing a global minimum. Sōzu’s workers each select from their own view, and that missing global minimum is what keeps them from herding: no worker can steer toward “the least loaded backend” because no worker ever computes one.

power_of_two_touches_exactly_two_backends pins the read count, and power_of_two_sample_size_is_two_not_the_whole_set measures the same property from the selection distribution alone. Both exist because a test that only checks “a backend came back” passes for an O(n) scan too.

Tie-break: seeded-random, deliberately NOT deterministic-by-id

Unlike Rendezvous/Maglev, PowerOfTwo carries no affinity key — every call is an independent, unlabeled selection event, so there is no “the same key must land on the same backend across workers/restarts” requirement to preserve here. But answering “must we preserve agreement?” is not the same question as “does this mechanism create agreement?” — see the next section for why that distinction is the whole reason its seed is never DEFAULT_HASH_SEED.

A deterministic tie-break (e.g. “lowest backend id wins”) was considered and rejected: ties are common, not rare — every backend starts at zero load, so a cold start, a post-scale-up rebalance, or any tick where two backends carry identical load all resolve through this branch. Always awarding the tie to the same backend (e.g. the lowest id) would bias the distribution toward that backend on exactly the events P2C exists to spread out, reintroducing the herding effect P2C is designed to avoid — on every one of Sōzu’s single-threaded workers simultaneously, since they would all observe the same tie and resolve it the same deterministic way. A seeded RNG that advances per call keeps ties spread across the candidate set over the process lifetime while still satisfying the no-ambient-entropy-on-the-hot-path rule.

Seed source: the backend map’s OS-seeded generator, NOT DEFAULT_HASH_SEED

Rendezvous/Maglev feed their seed into a pure, stateless hash function: sharing DEFAULT_HASH_SEED fleet-wide is exactly what gives them cross-worker/cross-restart agreement for the same key. PowerOfTwo feeds its seed into a stateful, advancing StdRng, where the n-th tie-break depends on the whole call history. Seeding that from the same shared constant would make every worker, on every cold start, draw from a bit-for-bit identical keystream — so the very first tie any two workers hit after a synchronised redeploy (and ties are the common case here, see above) would resolve identically, fleet-wide, on every restart. That is the deterministic-tie-break herding problem above, reintroduced by the “fix” instead of prevented by it. The production seed therefore comes from BackendMap’s generator, which reads the OS once, at construction — off the datapath — so each worker’s keystream is independent, the same property the old thread-local rng() had, while BackendMap::with_seed gives a simulator a fixed, reproducible sequence (#1684).

Fields

metric: LoadMetric

Implementations

impl PowerOfTwo

pub fn with_seed(seed: u64, metric: LoadMetric) -> Self

A policy whose tie-breaks are the keystream of seed. Never DEFAULT_HASH_SEED in production — see the struct docs.

Trait Implementations

impl Debug for PowerOfTwo

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

Formats the value using the given formatter.

impl LoadBalancingAlgorithm for PowerOfTwo

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; Maglev rebuilds its table, and RoundRobin (with the round-robin fallback of Rendezvous and Maglev) resets its running weights.