uneven request distribution when using weighted LR LB

[wgallagher]

Title: uneven request distribution when using weighted LR LB

Description:

When LR LB is used with weights, each upstream tends to send a large series of requests to one host before moving onto the next. For example, we've seen 50 sequential requests into a single box when using a weight of 50. It seems like the LB strategy is to send 'n' requests to a given host before moving onto the next one.

Repro steps:

Setup a weighted cluster and observe the request distribution into

[mattklein123]

I'm not completely sure how to fix this in the power of 2 load balancer. The thing that comes to mind (needs some simulation to check) is to use both weight and number of requests to create a psuedo-weight for the two chosen hosts, then pick based on that.

[wgallagher]

Also, I should clarify as the title of this jira is vague. The request distribution is actually even it's just that hosts get bombarded with requests serially.

[htuch]

Why not use an EDF scheduler and weight based on # of requests?

[mattklein123]

@htuch what do you mean? Use an EDF weight schedule like for RR and pick 2 off the top and select the one with the least requests?

[chriselion]

@mattklein123 I think picking the min of (number of requests) / weight will work - if the weights are equal, it's the same as unweighted LR, and in the steady state, the number of requests for each host would be proportional to the weights.

For comparing 2 hosts, you can avoid the division and do e.g. min_index = requests[i] * weights[j] < requests[j] * weights[i] ? i : j; (although this might have overflow issues if you let the weights get large)

[mattklein123]

I will fix this.

[mattklein123]

I'm trying to fix this and the math turns out to be incredibly non-intuitive. Here is what I have so far:
2f81145

It's not a finished change, but there is some simulation code. Roughly, the algorithm I'm trying to use looks like this:

1. Pick 2 random hosts (I added some temporary code to try to make sure we actually pick 2 different hosts).
2. Calculate a scaled synthetic request count by dividing number of active requests (min 1) by the weight.
3. Calculate what % of requests host 1 should get of both hosts.
4. Use a random number to pick between host 1 and host 2 based on the target request %.

This actually seems to work correctly w/ 2 hosts. But it doesn't work correctly with more than 2 hosts. I think what is happening is that when hosts with the same weight are picked, it's somehow skewing the results, but the math here is beyond me.

I also found this paper which is directly applicable but I don't understand it either:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.1379&rep=rep1&type=pdf

I will play around with it a bit more tomorrow, but my current plan is to potentially do a full scan in the weighted case, and put in a TODO for a better algorithm. If anyone out there has any thoughts please speak up!

[mattklein123]

We could look into an EDF scheduler also, per @htuch, but that would require having a callback for when active requests go up and down for every host. The code changes to do this would be non-trivial.

[mattklein123]

Quick update here. @htuch and I met with the researcher who wrote http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.1379&rep=rep1&type=pdf this morning.

It turns out that paper and similar papers don't apply, as they are about the inversion of the problem. Basically, when requests have weight but all backends are the same weight. Apparently from a mathematical perspective this makes a big difference and there is no way to easily make P2C work with different backend weights.

The researcher did have some good ideas:

1. Duplicate all of the hosts based on weight, and then do straight P2C. This will work, at the expense of extra memory.
2. Use consistent hashing for weighting, but instead of actually hashing, just pick 2 random inputs, and then do P2C on those. So basically we could use a Maglev table with weights and then choose out of that. This is a really interesting observation.

The third option is the one I already started working on which is a modified EDF approach. I think I'm going to keep going with the EDF approach for now as it is very straightforward and almost all the code can be shared with RR. I will leave some comments in the code of other options and we can revisit in the future if necessary.