Skip to content

PATTERN Cited by 1 source

Power of Two Choices (P2C)

Power of Two Choices (P2C): instead of picking one backend uniformly at random, pick two at random and route the request to the one with fewer active requests / lower observed load. A tiny change to pure-random, but it exponentially flattens load distribution — well-known result from Mitzenmacher et al. (Harvard lecture notes).

Why it works: with pure random, bad luck can drop several requests in a row on the same unlucky pod. With P2C, every decision compares against a sample of two, so local imbalances get corrected constantly. The math: expected max load shrinks from log N / log log N (random) to log log N / log 2 (P2C) — approximately constant for practical N.

When to use it

  • Client-side LB where the caller has an observable "load" signal per backend (active requests is the usual one).
  • Default strategy when you don't have a specific reason to use weighted / shard-aware / consistency-hashing.
  • Works well under bursty traffic because the decision is stateless — no coordination between clients needed.

When it's not enough

  • You need stickiness (session affinity) for some reason → consistent hashing.
  • You need shard awareness (request has to go to the owner of a particular key) → key-based dispatch.
  • Workloads where the observable signal (active requests) doesn't reflect real load — e.g. long-tailed requests where one in-flight call can equal 100 short calls. Mitigations: weight by expected cost, use latency EWMA instead of count.

Seen in

  • sources/2025-10-01-databricks-intelligent-kubernetes-load-balancing — P2C is Databricks' default client-side LB algorithm, embedded in their Armeria RPC library. Their claim: "P2C strikes a strong balance between performance and implementation simplicity, consistently leading to uniform traffic distribution across endpoints." More exotic strategies (CPU/metric-skewed routing) were tried and retracted in favor of P2C + direct health signals. Kept-it-simple worked best.
  • Canonical implementations: Envoy's LEAST_REQUEST LB policy uses P2C under the hood.
Last updated · 200 distilled / 1,178 read