A68: Random subsetting with rendezvous hashing LB policy

[s-matyukevich]

Replaces https://github.com/grpc/proposal/pull/383

Related to https://github.com/grpc/proposal/pull/430 which describes an LB policy that could be used in combination with random subsetting to correct the resulting server-side load imbalance.

[s-matyukevich]

Bump on this. It has been almost a month since the proposal was submitted and no one from gRPC maintainers commented on it yet. cc @markdroth and @ejona86 since you both reviewed previous version of the proposal and have full context.

[atollena]

The general problem that we're trying to solve is that LB policies like RR and WRR proactively maintain connections to all endpoints and therefore waste a lot of resources on idle connections when the client is idle. To deal with this, we will eventually want to add an LB policy that tracks the number of simultaneous RPCs in flight on the channel over the last N minutes and scale the number of connections accordingly. This new policy would operate similarly to the subsetting policy described in this gRFC: it would filter the set of addresses passed down to the child policy.

This is also the general problem that we are trying to solve with this gRFC and https://github.com/grpc/proposal/pull/430. And making the subset size dynamic would be ideal, but seems much harder, as the subset size impacts load balancing, and server load must be reasonably predictable. I don't know of any published work on making the number of connections dynamic (no fixed subset size) while also keeping the server load reasonably balanced. So I'm very curious where you are at with those discussion and if you have rough ideas on how you would address load balancing.

[ejona86]

I don't know of any published work on making the number of connections dynamic (no fixed subset size) while also keeping the server load reasonably balanced.

Basically the theory is you would size a minimum subset like you are doing here to a degree. But if the client causes a lot of load, then you scale up, potentially to all backends. IIRC, we were thinking of defining load as "concurrent RPCs." Most of the discussion was spent avoiding wildly scaling up/down, like with bursty clients, causing damage.

[markdroth]

This is also the general problem that we are trying to solve with this gRFC and #430. And making the subset size dynamic would be ideal, but seems much harder, as the subset size impacts load balancing, and server load must be reasonably predictable. I don't know of any published work on making the number of connections dynamic (no fixed subset size) while also keeping the server load reasonably balanced. So I'm very curious where you are at with those discussion and if you have rough ideas on how you would address load balancing.

I think the approach that we have in mind would probably result in slightly less ideally balanced server load than the results you've seen, specifically because the connections will no longer be perfectly balanced. But in cases where the RPC rate from different clients diverge wildly, or where RPC rates are very bursty, maintaining unnecessary idle connections can cost significant amounts of memory and some additional CPU. I think there are situations where the costs of that unnecessary overhead is expensive enough that it's worth taking steps to reduce it, even if it results in slightly less optimally balanced server load.

Like anything else in this space, it's a bit of a balancing act (pun intended). There will definitely be cases where the approach that we have in mind won't work well, but there will be cases where it will. But we think it will be a useful tool to have in our toolbox at some point.

[s-matyukevich]

What are the next steps here? Can someone with the right permissions merge this?

[ejona86]

@dfawley, Mark is the listed approver currently, but I'm fine merging this as it seems things are in order. Since the first implementation is in Go, you may want to take a look, but you agree the approvers seems ready?

[dfawley]

@dfawley, Mark is the listed approver currently, but I'm fine merging this as it seems things are in order. Since the first implementation is in Go, you may want to take a look, but you agree the approvers seems ready?

This LGTM overall, but I'm a little concerned about this comment from Mark and its impact on this gRFC: https://github.com/grpc/proposal/pull/423/files#r1676227354

Have you had this discussion yet, @s-matyukevich? Otherwise, should we wait to merge this until that's been finalized (more of a Q for @ejona86)? @markdroth did approve, so maybe he didn't see it as a blocker.

[markdroth]

I don't really anticipate any problems on the Envoy side, but it would be good to get a sanity check from @wbpcode before merging this, just to be safe. I'll ping him offline to request his input.

[markdroth]

Thanks for confirmation, @wbpcode!

I think that's all the open questions here, so I'll go ahead and merge. Thanks!