4 ms·
Do you have to pick two random buckets or just one random bucket and one adjacent bucket? Feels like picking an adjacent bucket would work just as well and inc
by xvector 3y ago
Do you have to pick two random buckets or just one random bucket and one adjacent bucket?
Feels like picking an adjacent bucket would work just as well and increase locality.
- magicalhippo 3y agoI was thinking about that, but I haven't had time to really dig into it. My gut feeling is that it won't be sufficient, but it might be a bad hunch.
- xvector 3y agoI graphed it: https://rentry.co/nkrc6 https://rentry.co/nkrc6 There's a difference, but it's minimal. Only the initial choice has to be random. As long as you have more than one bin to pick from, you are good regardless of your strategy (random vs adjacent).
- strikelaserclaw 3y agothanks for that, that is quite interesting
- rjmunro 3y agoIn a followup post he explains why actually almost the opposite is true - split your buckets into 2 groups, pick a random A and B from each group and if it's a draw, always load A first. This means buckets in the B group will likely be 1 less loaded than servers in the A group. https://medium.com/@mihsathe/load-balancing-a-very-counterintuitive-improvement-to-the-best-of-k-algorithm-608ffbdb7c8a https://medium.com/@mihsathe/load-balancing-a-very-counterin...