Load balancer: Pluggable subsetting for load balancers

[conqerAtapple]

Title: Load balancer: Pluggable subsetting for load balancers

Description:
We would like to have a pluggable component for feeding the subset of endpoints that feeds into the load balancer system such that it allows different subsetting schemes like deterministic subsetting. This will keep the load balancing scheme decoupled from the subsetting scheme. Without a pluggable subsetting scheme, looks like we currently only have a cluster priority based subset.

[Relevant Links:]
https://blog.twitter.com/engineering/en_us/topics/infrastructure/2019/daperture-load-balancer

[mattklein123]

I agree that having some type of pluggable subsetting capability would be nice. Design proposals appreciated.

[conqerAtapple]

@mattklein123 i will try to write up a basic design by next week so that we can iterate over the details.

[conqerAtapple]

High Level Design For Generic Subsetting

Structural

Inheritance

                                      SubsetLoadBalancer (Abstract)
                                                   ^
					           |	
                        ---------------------------------------------------
                        |                                                  |
MetadataBasedSubsetLoadBalancer                                    DeterministicApertureSubsetLoadBalancer

Other Data Structures

RingInfo (Details TBD)

Contains information about metadata to calculate the position of the Envoy instance in the hash ring:

• Aperture size
• Weight distribution

Flow

Initialization

• thread local cluster initialization
• Initialize subset load balancer
  • MetadataBasedSubsetLoadBalancer initialization will be same as existing SubsetLoadBalancer
  • DeterministicApertureSubsetLoadBalancer will be initialized with EndpointRingInfo (TBD)

Refresh/Updates

MetadataBasedSubsetLoadBalancer: No changes from existing update logic for "SubsetLoadBalancer"

DeterministicApertureSubsetLoadBalancer:

• On updated with set of new/updated/deleted hosts will calculate the priority/weighted subsets based on the EndpointRingInfo

[conqerAtapple]

@mattklein123 @alyssawilk Added a basic design and flow design. Need to iterate on the details.

[alyssawilk]

Having both pluggable sub-setting and upstream aperture based SGTM. The only thing I'm not sold on is MetaDataBased for the legacy subset naming. cc @zuercher who I think implemented the subset LB and may have thoughts both on structure and naming.

[zuercher]

The name seems a bit cumbersome, but it's accurate. I think you could drop "Based" and it'd be fine.

It's not immediately obvious to me that those two load balancing implementations have a lot in common, but it's worth exploring.

[conqerAtapple]

@zuercher @alyssawilk @mattklein123 . I have finally got some time block to focus on this. After some thought into this, I feel that we could be better off by keeping the existing subsetting mechanism and add a new aperture load balancing algorithm. This allows existing subsetting mechanism to work with the new aperture load balancer. For example - we can have subsets of endpoints based on header metadata and each subset could be placed on a aperture ring( just like how hash ring load balancer works today with the current subsetting mechanism.

Initially I was thinking we could keep subsetting separate from load balancer so that algorithms like P2C and Deterministic weighed aperture could work on top of the subsetting. But thinking more on this, these algorithms could gave some dependencies on the subsetting and might not be completely separable.

If you agree, I can proceed with adding the new Deterministic Aperture load balancer along with the existing ones.

[alyssawilk]

@zuercher thoughts on this? I'm fairly out of date with subsetting code

[zuercher]

I'm fine with that. The subsets in the existing Envoy load balancer don't have the same semantic meaning as the subsets in the deterministic aperture load balancer described in the blog post. The former is a way to divide the members of a service into sets of addressable upstream servers based on the properties of the upstream servers. The d-aperture load balancer is a way to reduce the total number of connections used by N clients (envoy servers in our case) communicating with M upstream servers, while distributing requests evenly across the upstreams and without requiring coordination across clients (envoys).

[conqerAtapple]

Thanks @zuercher .

@alyssawilk @mattklein123 @zuercher Regarding the specifics of the implementation itself, here is my hight level thought ideas:

• Create d-aperture as a ThreadAwareLoadBalancer
• Since current ThreadAwareLoadBalancer implementation assumes Ring or Maglev LB, I might have to create a new type for d-aperture LB that directly inherits from ThreadAwareLoadBalancer.
• Fill in the plumbing in various places (example ClusterManagerImpl::loadCluster) to support the d-aperture LB.

Will fill in more details as I start the initial draft of the implementation.

Does the above plan sound ok?

[zuercher]

That sounds right.

[conqerAtapple]

Thanks @zuercher