Power of two choices

Deep dive

How it works

In: set of backends with a local load signal (in-flight count, latency average) · Out: one chosen backend per request · State: per backend an in-flight counter and a latency average (order of 32 B) · Cost: O(1): two random draws, two comparisons.

1. Each balancer keeps per-backend load: in-flight count (incremented on send, decremented on response) and optionally a latency EWMA.
2. Per request: sample two distinct backends uniformly (or weight-proportionally), compute cost for each, pick the lower; break ties randomly.
3. Update load on completion. Failed or ejected backends are excluded from sampling (see circuit breaker).

Why it beats "global least loaded" in practice: with stale information (a load report every T seconds) all balancers pick the same minimum, it overflows, and load oscillates (Mitzenmacher, How useful is old information?). Random pairs give each backend a bounded share of the herd.

Cost functions:

• least requests: in_flight; simple, good when requests cost about the same.
• peak EWMA (Finagle, Linkerd): ewma_latency × (in_flight + 1); the EWMA jumps up instantly on a slow response and decays slowly (τ ≈ 10 s), so a degrading backend is avoided within one request.

Code

use std::time::{Duration, Instant};

/// Per-backend state for peak-EWMA cost.
pub struct Backend { pub addr: String, in_flight: u32, ewma_ns: f64, stamp: Instant }

pub struct P2c { backends: Vec<Backend>, rng: u64, tau_ns: f64 }

impl P2c {
    pub fn new(addrs: &[&str], seed: u64) -> Self {
        let now = Instant::now();
        let backends = addrs.iter()
            .map(|a| Backend { addr: a.to_string(), in_flight: 0, ewma_ns: 1e6, stamp: now }) // 1 ms prior
            .collect();
        P2c { backends, rng: seed | 1, tau_ns: Duration::from_secs(10).as_nanos() as f64 }
    }

    fn next_u64(&mut self) -> u64 { // xorshift64*
        self.rng ^= self.rng >> 12; self.rng ^= self.rng << 25; self.rng ^= self.rng >> 27;
        self.rng.wrapping_mul(0x2545_f491_4f6c_dd1d)
    }

    fn cost(&self, i: usize, now: Instant) -> f64 {
        let b = &self.backends[i];
        // Decay toward zero while idle so a once-slow backend gets retried eventually.
        let idle = now.duration_since(b.stamp).as_nanos() as f64;
        let ewma = b.ewma_ns * (-idle / self.tau_ns).exp();
        ewma * (b.in_flight as f64 + 1.0)
    }

    /// Choose a backend and count the request as in flight. Call `done` when it finishes.
    pub fn pick(&mut self) -> usize {
        let n = self.backends.len();
        assert!(n > 0);
        if n == 1 { self.backends[0].in_flight += 1; return 0; }
        let a = (self.next_u64() % n as u64) as usize;
        let mut b = (self.next_u64() % (n as u64 - 1)) as usize;
        if b >= a { b += 1; } // distinct second sample without rejection
        let now = Instant::now();
        let i = if self.cost(a, now) <= self.cost(b, now) { a } else { b };
        self.backends[i].in_flight += 1;
        i
    }

    pub fn done(&mut self, i: usize, rtt: Duration) {
        let now = Instant::now();
        let tau = self.tau_ns;
        let b = &mut self.backends[i];
        b.in_flight -= 1;
        let rtt = rtt.as_nanos() as f64;
        if rtt > b.ewma_ns {
            b.ewma_ns = rtt; // peak: react instantly to slowness
        } else {
            let w = (-(now.duration_since(b.stamp).as_nanos() as f64) / tau).exp();
            b.ewma_ns = b.ewma_ns * w + rtt * (1.0 - w); // time-weighted decay
        }
        b.stamp = now;
    }
}

#[test]
fn avoids_slow_backend() {
    let mut lb = P2c::new(&["a", "b", "c"], 42);
    let mut hits = [0u32; 3];
    for _ in 0..3000 {
        let i = lb.pick();
        hits[i] += 1;
        let ms = if i == 2 { 50 } else { 1 }; // backend c is 50x slower
        lb.done(i, Duration::from_millis(ms));
    }
    assert!(hits[2] < 300, "{hits:?}");
}

Complexity and constants

• O(1) per request: two RNG draws, two cost evaluations; order of 10s of ns, negligible next to a network hop.
• Max load for n balls into n bins: d = 1 gives ln n / ln ln n (1 + o(1)); d ≥ 2 gives ln ln n / ln d + O(1). Going from 1 to 2 is the big win; 2 to 3 saves a constant.
• Supermarket model (Poisson arrivals at rate λ per server, exponential service): P(queue ≥ i) = λ^((dⁱ − 1)/(d − 1)), doubly exponential decay for d ≥ 2 vs λⁱ for d = 1. At λ = 0.9 mean time is 10 vs 2.6; at λ = 0.99 it is 100 vs 5.4.
• State per backend: a counter and an EWMA, order of 32 bytes.

Efficiency

• Cost: two RNG draws and two cost evaluations, order of 10s of ns, far below one network hop; order of 32 B per backend. The bound is signal quality, not CPU: max load ln ln n / ln 2 + O(1) versus ln n / ln ln n for random choice (Azar et al.); at 99 % utilization mean time in system 5.4 versus 100 service times (Mitzenmacher).
• Levers:
  • count in-flight requests locally — freshest signal, no load-report protocol (Mitzenmacher, old information) — always
  • peak-EWMA cost ewma × (in_flight + 1) — a degrading backend is avoided within one response (Finagle, Linkerd) — varying request cost
  • client-side subsetting plus P2C inside the subset — caps connections per client (Finagle aperture) — many clients × many servers
  • per-thread balancers — no shared-atomic contention (this page) — multi-threaded proxies
  • stay at two choices — a third only gains a constant, factor ln d (Mitzenmacher survey) — always
• Naive → standard → state of the art:
• Uniform random pick · max load ln n / ln ln n; 100 service times mean at 99 % utilization
• Least loaded of all · exact, O(n), herds onto one backend when load data is stale
• P2C with peak EWMA, local in-flight counts, outlier ejection and subsetting · O(1); 5.4 service times mean at 99 % utilization

Implementation notes

• Count in-flight locally in each balancer; it is the freshest signal you have and needs no protocol. Server-reported utilization (Netflix Zuul) helps when many clients share servers.
• Weighted backends: sample proportionally to weight (alias table), or divide cost by weight.
• Pair with outlier ejection: a backend failing fast has low latency and low in-flight and attracts traffic ("black hole"). Count errors as slow responses (penalty RTT) or eject.
• Many clients × many servers: give each client a random subset (Finagle aperture, Google's deterministic subsetting) and run P2C within it to cap connection counts.
• Multi-threaded proxies: per-thread balancers with per-thread in-flight counts work well; sharing atomics adds contention for little gain.

Pitfalls

• Sampling with replacement (both picks the same backend) wastes the second choice; draw distinct indices.
• Cold start: new backends have no EWMA; a prior too low floods them, too high starves them. Start at the median of current backends.
• Pure latency cost without in-flight: a backend that times out slowly looks fine until responses arrive.
• Slow-start for new or recovering instances (warm caches, JIT): ramp weight over 30-60 s, or one new pod gets hammered.
• Server-side queueing invisible to the client (backends with their own work queues) needs server-reported load; client in-flight undercounts it.

Variants and alternatives

In production

Envoy (LEAST_REQUEST, choice_count 2), NGINX (random two least_conn), HAProxy (balance random(2)), Finagle (p2c, p2cPeakEwma), Linkerd (P2C + peak EWMA), Netflix Zuul (choice of 2 with server utilization), Sparrow scheduler.

Implementations

Sources

• Azar, Broder, Karlin, Upfal, Balanced Allocations, ACM STOC, 1994 (SIAM J. Computing, 1999). STOC · SICOMP
• Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE TPDS, 2001 (PhD thesis, 1996). paper
• Vvedenskaya, Dobrushin, Karpelevich, Queueing System with Selection of the Shortest of Two Queues: An Asymptotic Approach, Problems of Information Transmission, 1996.
• Mitzenmacher, How Useful Is Old Information?, IEEE TPDS, 2000. paper
• Ousterhout, Wendell, Zaharia, Stoica, Sparrow: Distributed, Low Latency Scheduling, SOSP, 2013. paper · code