# Finding Needles in a Haystack with Best-of-K

DevFeed: [Finding Needles in a Haystack with Best-of-K](<https://devfeed.tech/articles/finding-needles-in-a-haystack-with-best-of-k-12554.md>)

Original publisher: [Read original article](<http://brooker.co.za/blog/2024/03/25/needles.html>)

Author: Marc Brooker

Published: 2024-03-25T00:00:00Z

Content type: article

Language: en

Sources: [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog.md>), [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog-2.md>)

Topics: [distributed-systems](<https://devfeed.tech/topics/distributed-systems.md>), [systems](<https://devfeed.tech/topics/systems.md>), [Cloud](<https://devfeed.tech/topics/cloud.md>)

Tags: [cloud](<https://devfeed.tech/tags/cloud.md>), [distributed-systems](<https://devfeed.tech/tags/distributed-systems.md>), [performance](<https://devfeed.tech/tags/performance.md>), [production](<https://devfeed.tech/tags/production.md>), [scale](<https://devfeed.tech/tags/scale.md>), [systems](<https://devfeed.tech/tags/systems.md>)

## AI overview

The article examines best-of-k load balancing in distributed systems, where each request is sent to the least-loaded worker among a small random sample. It explains the algorithm's advantages over random selection and stale system-wide snapshots, then introduces capacity limits and an iterative variant intended to avoid rejections when total system capacity is sufficient.

## Source excerpt

Finding Needles in a Haystack with Best-of-K Keep track of those needles. As I've written about before, best of two and best of k are surprisingly powerful tools for load balancing in distributed systems. I have deployed them many times in large-scale production systems, and been happy with the performance nearly every time. There is one case where they don't perform so well, though: when the bins are very limited in size. Reminder: Best-of-K Consider a load balancing problem in a distributed system, where we have m requests to allocate to n workers. The simplest approach is to pick randomly, but unfortunately this leads to rather poor load distribution (see simulation results here). Surprisingly poor, even. The second simplest approach is to try use a snapshot of system-wide state (some eventually-consistent how busy is everybody? store), and pick the best one. This works well in slow-moving systems, but the stale data quickly causes bad decisions to be made (simulation results here). Enter best-of-k. In this simple algorithm, we pick k of the n workers, and send the request to the least loaded of those k. Typically, k is small, like 2 or 3. Best-of-k leads to a much better load distribution than random, is much more robust to stale data than best-of-n, and can be run in O(1) time. It's a great pick for a stateless load-balancing algorithm. What's interesting about best-of-k to distributed system builders that it allows a simple design with multiple dispatchers/load balancers that don't talk to each other, and only have stale knowledge of the busyness of the set of workers. That makes fault-tolerant distributed load balancing easier. No need for replication, no need for consensus protocols, no need for coordination of any kind. Avoiding coordination is how cloud systems scale. Capacity Limits In many practical systems, each of the n workers will have some maximum capacity limit (let's call it c) after which it can't accept any more requests. In these systems, we're