[ go ] [ golang ] [ loadbalancing ] [ algorithm ] [ load ] [ balance ] [ poc ] [ random ] [ round-robin ] [ power of two choices ]
Contents
I recently read an article that was linked on hacker news about the power of two load balancing algorithm. This isn’t a new or complicated concept, but I’d never explored it and wanted to experiment with it a bit for fun.
This is a very over simplified example, but it’s pretty cool nonetheless. I will be using balls and requests interchangeably in this post.
Overview
Suppose you have 1 million ping-pong balls and 100 buckets. We want to distribute the ping-pong balls as evenly as possible. There are a couple simple approaches we could take. None of the approaches below take into account server load or currently open connections. These are all static or “dumb” load balancing algorithms.
The first is round-robin. This will put a ball in the first bucket, then the second, then the third, and on down the line until we get to the last bucket and then start again at first bucket. This is simple and will evenly spread the balls across the buckets. It’s also pretty easy to reason about.
We could could some kind of hashing on the request and use that to assign a bucket.
We could randomly choose a bucket for each request. However, because each request is going to be randomly assigned to a bucket every bucket has the same chance of being chosen for each request. This tends to lead to some buckets getting overfilled and others under filled.
Another options is to randomly choose 2 buckets, and then assign the request to the bucket with the lesser amount of balls.
These last two, random and best of two is what the blog post I read was about and I thought it would be fun to write a very simple proof of concept.
Experiment
I used Go to write the POC. I wrote two functions, one for each approach. These functions use that approach to fill the buckets and then send the difference between the most full and least full buckets back over a channel (I wanted to be able to run many iterations of the experiment and using goroutines speeds that up).
Once we have run our experiment the desired amount of time we take the average of all results for each approach and report that average.
The code is short, and I’ll include a playground link at the end of the post.
Here is the function I am using to randomly fill buckets:
func RandomFill(wg *sync.WaitGroup, c chan int) {
defer wg.Done()
var b [buckets]int
max := 0
min := math.MaxInt
// fill buckets
for i := 0; i < balls; i++ {
b[rand.Intn(buckets)]++
}
// check buckets
for i := 0; i < buckets; i++ {
if b[i] < min {
min = b[i]
}
if b[i] > max {
max = b[i]
}
}
c <- (max - min)
}
And here is my function for best of two choices:
func BestOfTwo(wg *sync.WaitGroup, c chan int) {
defer wg.Done()
var b [buckets]int
var b1, b2, max int
min := math.MaxInt
// fill buckets
for i := 0; i < balls; i++ {
for {
b1 = rand.Intn(buckets)
b2 = rand.Intn(buckets)
if b1 != b2 {
break
}
}
if b[b1] < b[b2] {
b[b1]++
} else {
b[b2]++
}
}
// check buckets
for i := 0; i < buckets; i++ {
if b[i] < min {
min = b[i]
}
if b[i] > max {
max = b[i]
}
}
c <- (max - min)
}
Result
I’ve set my program to distribute 1 million balls into 100 buckets, and ran the test 10,000 times.
My results consistently show a spread of ~500 balls when randomly choosing a bucket, and ~4 balls when using the best of two choices!
Avg spread for RandomFill = 500
Avg spread for BestOfTwo = 4
I had reduced the iterations to 10 on the playground to avoid using too many resources, but here is the playground link if you’d like to see for yourself.