When Simple Wins: The Power of Two Random Choices

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:

  • Clever Traffic Flow Control: You can apply filtering and routing rules: Where is the user? What device are they on? Is it a low bandwidth connection? Once the answers are apparent to the load balancer, it will route according to your specifications. So, too, it allows you to make alterations to your backend infrastructure without disrupting the clients enjoying your front-ends.

  • High Availability: Servers die sometimes. As sad as that is, a load balancer can detect when one of your servers is unavailable, then route traffic accordingly.

  • Performance: A conveniently placed load balancer can perform SSL-termination closer to the user, speeding up the key-exchange handshake considerably. Your users reach your site faster; especially if the load balancer has a backhaul connection to where the application is hosted.

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

  • HTTPS: Load Balancing HTTPS isn't as difficult as it once was, thanks in large part to Let's Encrypt. We've written about how you can use HAProxy to load balance Let's Encrypt HTTPS; it's relatively simple, but it's another thing to configure and manage.

  • Single Point of Failure: Putting one load balancer in-front of several servers introduces one point of failure. What if the load balancer goes down?

  • Load Balancing the... Load Balancers: If you've set-up multiple load balancers to accommodate colocated servers, it's quite a logistical pickle to keep everything running smoothly.

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:

  • Round Robin: ServerA -> ServerB -> ServerC. The next server in line gets the traffic. It's an egalitarian delight, but it leaves room for sophistication.

  • Least Connections: The server with the least amount of active connections receives the traffic. It's the load balancer's job to keep track of connections. This adds processing overhead, operations complexity, and scaling considerations.

  • Least Traffic: The server with the lowest bitrate gets the traffic. Like Least Connections, the load balancer needs to be aware of the servers' status.

  • Best: The best server, as determined by least connections, lowest bitrate, and lowest latency, receives the traffic. A wonderful idea, but "best" can fluctuate quickly; like the others that require the load balancer to keep tabs on the servers, there is overhead to consider.

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":

  • Do you want to easily load balance Let's Encrypt HTTPS traffic for your international user-base?

  • Do you have multiple servers or want to put servers in various locations? AWS + GCP, perhaps?

  • Want performant and smooth traffic distribution across your backend servers?

  • Are you interested in high-availability for your infrastructure?

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.

Show Comments

Get the latest posts delivered right to your inbox.