When Simple Wins: The Power of Two Random Choices

By Kellen 

Fly is an Application Delivery Network. A large piece of the application delivery puzzle is fast and efficient load balancing. We've just rolled out Power of 2 Random Choices Load Balancing; every site sending traffic through Fly receives global HTTPS load balancing with The Power of 2 Random Choices. How does load balancing help you? What's special about The Power of 2 Random Choices? A-ha! Onward, to answers!

Bring the Balance

Many notable hosting services - Microsoft Azure, Amazon Web Services and Google Cloud, to name a few - offer "auto-scaling servers". They offer these services because traffic is highly variable. At anytime, your traffic could explode... From anywhere!

If you were self-hosting on a single piece of hardware, a great day on Hacker News or ProductHunt could bring you down in a hurry. Even if you're using an auto-scaling server, you could use something to help you receive traffic from your international audience, to increase rendering speeds and prepare your infrastructure for scale. If you're already a high-traffic site, you're susceptible to fortuitous spikes as well as the daily rolling of global traffic; its always prime-time somewhere.

Whether you're large or small, one server or many, an entity with intelligence to route and balance requests between your growing fleet of servers would be useful. That entity is the load balancer.

Now that we have some context, let's isolate a few main benefits that one can provide:

If you're setting up a load balancer yourself, there are some caveats and technical hurdles to be aware of:

Luckily, services like Fly exist to take care of load balancing for you, while removing the downside; you get a powerful control panel to apply smart routing and fast, reliable, global HTTPS load balancing... Now, with the Power of 2 Random Choices!

It Takes (The Power of) 2

Typically, you might find one of these algorithmic flavours within your load balancer:

While there is a time and place for each flavour, we wanted smoother and more efficient traffic distribution for most scenarios. Power of 2 Random Choices chooses two end-points at random, then of those two it selects the one with the 'Least Connections'.

Let's get a little math-y. Not math-y? Roll on downwards...

The theoretical limit of an entity receiving tasks, in our case the load balancer, is the following under regular, sequential distribution - with high probability. That means n entities receiving n tasks in round-robin format:

Θ( log n / log log n )

Applying Power of 2 Random Choices, which selects two entities independently, then determines the one among them with the lowest load, we see the limit's variation per server decrease by an entire log factor - also with high probability:

Θ(log log n)

Math off!

It's best suited for cases where there are lots of end-points. End-points can span across multiple regions, providing relief if traffic fluctuates region-at-a-time. The end result is consistent, even dispersal of site traffic across all of your available nodes.

If you're into whitepapers, you can checkout all the mathematical goodness within: "The Power of Two Random Choices: A Survey of Techniques and Results".

Summary: But do I need this...?

Ah, the mighty Power of 2 Random Choices. When plugged into Fly, it provides an easy-to-use and efficient method of HTTPS global load balancing. You might be wondering if a load balancer is something you really need. It is!... If the answer to any of the following questions is "yes":

Fly started when we wondered "what would a programmable edge look like"? Developer workflows work great for infrastructure like CDNs and optimization services. You should really see for yourself, though.