3 ms·

I have never been able to wrap my head around why 2 random works better in load balancing than leastconn. At least in caching it makes sense why it would work b

I have never been able to wrap my head around why 2 random works better in load balancing than leastconn. At least in caching it makes sense why it would work better than another heuristic.

beoberha 1y ago
Try giving Marc Brooker’s blog on this a read: https://brooker.co.za/blog/2012/01/17/two-random.html https://brooker.co.za/blog/2012/01/17/two-random.html It is only better than leastconn when you have stale information to base your decision on. If you have perfect, live information, best will always be optimal.
contravariant 1y ago
Technically it doesn't, it's just really hard to implement leastconn correctly. If you had perfect information and could just pick whichever was provably lowest that'd would probably work. However keeping that information up to date also takes effort. And if your information is outdated it's easy to overload a server that you think doesn't have much to do or underload one that's long since finished with its tasks. Picking between 2 random servers introduces some randomness without allowing the spread to become huge.
- hinkley 1y ago
  When the cost of different requests varies widely it’s difficult to get it right. When we rolled out docker I saw a regression in p95 time. I countered this by doubling our instance size and halving the count, which made the number of processes per machine slightly more instead of way less than the number of machines. I reasoned that the local load balancing would be a bit fairer and that proved out in the results.
  - contravariant 1y ago
    I'm not 100% sure if it's just load balancing. It would depend on the details of the setup but that situation also allows you to throw more resources at each request. I mean obviously there is a point where splitting up the instances doesn't help because you're just leaving more instances completely idle, or with too little resources to be helpful.
kgeist 1y ago
By the time you decide to route to a particular node, conditions on that node might have already changed. So, from what I understand, there can be worst-case scenarios in usage patterns where the same nodes keep getting stressed due to repeatedly stale data in the load balancer. Randomization helps ensure the load is spread out more uniformly.
yuliyp 1y ago
There are a few reasons: 1. Random is the one algorithm that can't be fooled. So even if there's something against number of connections as a load metric, not using that metric alone dampens the problems. 2. There is a lag between selection and actually incrementing the load metric for the next request, meaning that just using the load metric alone is prone to oscillation 3. A machine that's broken (immediately errors all requests) can capture almost all requests, while 2-random means its damage is limited to 2x its weight fraction 4. For requests which are a mix of CPU and IO work, reducing convoying (i.e. many requests in similar phases) is good for reducing CPU scheduling delay. You want some requests to be in CPU-heavy phases while others are in IO-heavy phases; not bunched.
- hinkley 1y ago
  I’m fine with the random part. What I don’t get is why 2 works just as well as four, or square root of n. It seems like 3 should do much, much better and it doesn’t. It’s one of those things I put in the “unreasonably effective” category.
  - nielsole 1y ago
    I wonder if someone tried a probabilistic "best of 1.5" or similar and if two is just a relatively high number.
    - hinkley 1y ago
      If I had to guess it’s related to e. In which case maybe choosing 2 30% of the time and 3 70% of the time is a better outcome.
      - adgjlsfhk1 1y ago
        it's not. you can get good behavior by choosing 1 90% of the time and 2 10% of the time.
  - Straw 1y ago
    It's because going from 1 to 2 changes the expected worst case load from an asymptotic log to an asymptotic log log, and further increases just change a constant. See https://en.wikipedia.org/wiki/Balls_into_bins_problem https://en.wikipedia.org/wiki/Balls_into_bins_problem

I have never been able to wrap my head around why 2 random works better in load balancing than leastconn. At least in caching it makes sense why it would work better than another heuristic.

beoberha 1y ago

Try giving Marc Brooker’s blog on this a read: https://brooker.co.za/blog/2012/01/17/two-random.html https://brooker.co.za/blog/2012/01/17/two-random.html It is only better than leastconn when you have stale information to base your decision on. If you have perfect, live information, best will always be optimal.

contravariant 1y ago

Technically it doesn't, it's just really hard to implement leastconn correctly. If you had perfect information and could just pick whichever was provably lowest that'd would probably work. However keeping that information up to date also takes effort. And if your information is outdated it's easy to overload a server that you think doesn't have much to do or underload one that's long since finished with its tasks. Picking between 2 random servers introduces some randomness without allowing the spread to become huge.

hinkley 1y ago
When the cost of different requests varies widely it’s difficult to get it right. When we rolled out docker I saw a regression in p95 time. I countered this by doubling our instance size and halving the count, which made the number of processes per machine slightly more instead of way less than the number of machines. I reasoned that the local load balancing would be a bit fairer and that proved out in the results.
- contravariant 1y ago
  I'm not 100% sure if it's just load balancing. It would depend on the details of the setup but that situation also allows you to throw more resources at each request. I mean obviously there is a point where splitting up the instances doesn't help because you're just leaving more instances completely idle, or with too little resources to be helpful.

kgeist 1y ago

By the time you decide to route to a particular node, conditions on that node might have already changed. So, from what I understand, there can be worst-case scenarios in usage patterns where the same nodes keep getting stressed due to repeatedly stale data in the load balancer. Randomization helps ensure the load is spread out more uniformly.

yuliyp 1y ago

There are a few reasons: 1. Random is the one algorithm that can't be fooled. So even if there's something against number of connections as a load metric, not using that metric alone dampens the problems. 2. There is a lag between selection and actually incrementing the load metric for the next request, meaning that just using the load metric alone is prone to oscillation 3. A machine that's broken (immediately errors all requests) can capture almost all requests, while 2-random means its damage is limited to 2x its weight fraction 4. For requests which are a mix of CPU and IO work, reducing convoying (i.e. many requests in similar phases) is good for reducing CPU scheduling delay. You want some requests to be in CPU-heavy phases while others are in IO-heavy phases; not bunched.

hinkley 1y ago
I’m fine with the random part. What I don’t get is why 2 works just as well as four, or square root of n. It seems like 3 should do much, much better and it doesn’t. It’s one of those things I put in the “unreasonably effective” category.
- nielsole 1y ago
  I wonder if someone tried a probabilistic "best of 1.5" or similar and if two is just a relatively high number.
  - hinkley 1y ago
    If I had to guess it’s related to e. In which case maybe choosing 2 30% of the time and 3 70% of the time is a better outcome.
    - adgjlsfhk1 1y ago
      it's not. you can get good behavior by choosing 1 90% of the time and 2 10% of the time.
- Straw 1y ago
  It's because going from 1 to 2 changes the expected worst case load from an asymptotic log to an asymptotic log log, and further increases just change a constant. See https://en.wikipedia.org/wiki/Balls_into_bins_problem https://en.wikipedia.org/wiki/Balls_into_bins_problem