Power of Two Choices

For each request, the load balancer picks two servers at random and sends the request to the one with fewer requests in progress. It looks at two servers instead of all of them, yet spreads load nearly as well as least connections, and it copes far better when its information about the servers is a little out of date. Below, compare it with least connections and random on the same traffic.

Speed1x

Each server drawn stands for one of your servers, and each dot for 100 real requests. "In progress" under the balancer is the live count; with load reports on, the line below it is what the balancer actually decides from. Switching the algorithm restarts the run with exactly the same requests.

Sizing the fleet

Daily active users

Requests per user per day

Peak factorx average

Busiest hour vs the daily average. The book's estimate uses 2x.

One server handlesreq/s

Measured by load testing one server until it cannot go faster.

Target load at peak% busy

Headroom for spikes and unevenness. 50 to 70% is common.

Traffic right nowx planned peak

1. Average requests per second
DAU x requests per user per day / 86,400
= 1,000,000 x 50 / 86,400 = 579 req/s
2. Peak requests per second
average x peak factor = 579 x 2 = 1,157 req/s
3. Servers needed n
n = peak / (one server x target load), rounded up = 10
4. Load on each server, on average
traffic now / (n x one server) = 58%
5. Servers looked at per request
least connections: all n = 10; two choices: 2; random: 0
Two looks are enough to remove most of random's unevenness, whatever the size of the fleet.
6. Herding, with load reported every T seconds
with live counts there is no herd; set the load reports above to see its size
Two choices costs almost nothing extra over random and needs no full scan of the servers, which is why large-scale balancers use it as their least-request method.

Where these formulas come from

Steps 1 and 2 are the estimation method from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1, including its 2x peak. Step 6 is a worst case: in practice requests that complete between reports soften it, but every new request in the window is still aimed at the same server. The claim that two choices is nearly as good as checking every server is the research result Envoy's documentation cites (Mitzenmacher and others).

Limits of power of two choices

Nearly as good, not as good

With live, exact counts, checking every server is still slightly better. Two choices wins when checking all of them is expensive or the counts are out of date, which in large systems is most of the time.

Still blind to errors

It compares requests in progress, so a server that fails requests instantly still looks idle and wins its comparisons, as on the Least Connections page. Health checks are still needed.

More choices help a little

Picking three or four instead of two improves things only slightly; the big step is from one random server to two. Envoy lets you set the number, with 2 as the default.

Old information is the point

Every balancer that learns about load from reports, or shares the job with other balancers, has information that is a little old. Two choices was designed for exactly that.

How Envoy and NGINX use two choices

Envoy makes it its least request method; NGINX offers it as a variant of random.

Envoy: least request

When all hosts have the same weight, Envoy's least request balancer "selects N random available hosts as specified in the configuration (2 by default) and picks the host which has the fewest active requests". Its documentation cites research showing "this approach is nearly as good as an O(N) full scan", calls it "P2C (power of two choices)", and says it "is particularly useful for load balancer implementations due to its resistance to herding behavior."

NGINX: random two

random two tells NGINX "to randomly select two servers and then choose a server using the specified method." "The default method is least_conn", so by default it is exactly the algorithm on this page.

Sources and credibility

Both are the projects' own documentation (primary sources). Quoted phrases are short attributed quotations; everything else is described in our words. Check the pages for current behaviour.