An Empirical Study of Load Balancing Algorithms

What is The Power Of Two Random Choices?

In a centralized load balancing architecture, implementing a least loaded policy is very simple because it has a complete view of the cluster's traffic. It can do it by keeping counters of open connections to every host, and route traffic to the least loaded one. But adding more load balancers to keep up with the traffic growth will complicate matters and new problems will arise.

To implement a least loaded policy in a distributed load balancing architecture, we need a way to periodically propagate host load information to all the load balancers. Usually done with a delay to minimize the cost of the load data collection. Since the load data is always stale, the load of each server will spike up and down like a roller coaster because multiple load balancers will select the same least loaded host. This happens again when the load information gets updated and a new least loaded host is selected, while the previously least loaded host becomes busy, developing a herd-like behavior. To solve this issue, the authors of The Power of Two Random Choices: A Survey of Techniques and Results" observed that distributing the load by picking hosts randomly (guaranteeing a O(log number_of_servers) load) performs better than least loaded policy in a distributed architecture.

Deriving from that fact, they devised a strikingly simple solution that would solve the issue of the herd behavior. It works by choosing two hosts either via hashing or randomly and then picking the least loaded of the two. The algorithm guarantees that the max load of a server is O(log log number_of_servers).

Client Example

An example of the code used by the client to assign requests to servers, using liblb/p2c Go package, which implements The Power Of Two Random Choices algorithm.

// Power of Two choices example
lb := p2c.New("", "", "")
for i := 0; i < 10; i++ {
    // uses random power of two choices, because the key length == 0
    host, err := lb.Balance("")
    if err != nil {
    // load should be ~33% per host
    fmt.Printf("Send request #%d to host %s\n", i, host)
    // when the work assigned to the host is done

Experiment Results

liblb simulation architecture liblb simulation architecture liblb simulation architecture
P2C's Experiment Results
For info on the graphs


  • Aware of actual load of the servers, and distributes traffic accordingly.
  • Very easy to implement in a couple of lines.
  • Guarantees a server's load to be O(log log n) where n is the number of servers.


  • The application needs to implement a way to propagate the load information to the load balancers.
  • It has no way of assigning certain requests to certain servers (affinity), which makes it not suitable for systems that utilizes caches to minimize heavy computations.

Use Cases

liblb P2C Balancer API docs

GoDoc liblb/p2c