This is one of my favorite results of all times. A really simple neat trick that any developer can use in a variety of situations without really having to understand how it works. Think of the following hypothetical: you have a bunch of bins and a bunch of balls and you want to load up the bins as evenly as possible. If the bins and the balls were of same size, a round-robin strategy would work well. If they were not, you’d expect that just putting a ball in a bin at random would work well, however here we propose a different scheme that will perform better. Pick two bins at random and put the ball in the least loaded bin.
Why this performs better is out of the scope of this post, there are a lot of papers that discuss complex proofs on the topic. Instead lets take an example from the systems domain. You have N servers that accept web requests. Let us assume that there are m requests. Each server is stateless, so you can route each request to any server you want. Here are some options on how to do it: (1) Round-robin, (2) Route to a random server, (3) Route to the least loaded server, (4) Pick k servers at random and route to the least loaded one. The last approach will outperform the first three, especially when:
- Requests have different resource demands
- The server farm is heterogeneous
- The information about which server is least loaded is stale
- Any combination of the above
Azar shows the above strategy works better than simple random choice. Talwar and Wieder of MSR, show in their paper that in case #1 the load gap, meaning the difference between the average and most loaded server, does not depend on the number of requests and thus scales infinitely with the number of servers. Mitzenmacher in his paper, shows how increasing the number k of randomly selected servers can help with stale information about server load.
paper cruncher 