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("127.0.0.1:8009", "127.0.0.1:8008", "127.0.0.1:8007")
for i := 0; i < 10; i++ {
// uses random power of two choices, because the key length == 0
host, err := lb.Balance("")
if err != nil {
log.Fatal(err)
}
// 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
lb.Done(host)
}
Experiment Results
Strengths
- 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)wherenis the number of servers.
Weaknesses
- 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
- Used by Facebook's Scuba system, to distribute writes to the servers with the most free disk space.
- Distributed Load Balancers. Such as ELB, CloudFlare Load Balancer
- Client's load balancer in microservices architecture. Such as Finagle