Add `LoadBalancer` for generalizing `EndpointSelector`

[ikhoon]

Motivation:

A load-balancing strategy such as round robin can be used in EndpointSelector and elsewhere. For example, in the event loop scheduler, requests can be distributed using round robin to determine which event loop to use.

This PR is preliminary work to resolve #5289 and #5537

Modifications:

• LoadBalancer<T, C> is the root interface all load balancers should implement.
  • T is the type of a candidate selected by strategies.
  • C is the type of context that is used when selecting a candidate.
• UpdatableLoadBalancer<T, C> is a stateful load balancer to which new endpoints are updated. RampingUpLoadBalancer is the only implementation for UpdatableLoadBalancer. Other load balances will be re-created when new endpoints are added because they can always be reconstructed for the same results.
• Weighted is a new API that represents the weight of an object.
  • If an object is Weighted, a weight function is not necessary when creating weighted-based load balancers.
  • Endpoint now implements Weighted.
• EndpointSelectionStategy uses DefaultEndpointSelector to create a LoadBalancer<Endpoint, ClientRequestContext> internally and delegates the selection logic to it.
  • Each EndpointSelectionStategy implements LoadBalancerFactory to update the existing LoadBalancer or create a new LoadBalancer when endpoints are updated.
• The following implementations are migrated from **Strategy. Except for RampingUpLoadBalancer which has some minor changes, most of the logic was ported as is.
  • RampingUpLoadBalancer
    • Weight prefix is dropped for simplicity. There may be no problem conveying the behavior.
    • Refactored to use a lock to guarantee thread-safety and sequential access.
      • A RampingUpLoadBalancer is now created from a list of candidates. If an executor is used to build the initial state, null is returned right after it is created.
• AbstractRampingUpLoadBalancerBuilder is added to share common code for RampingUpLoadBalancerBuilder and WeightRampingUpStrategyBuilder
• Fixed xDS implementations to use the new API when implementing load balancing strategies.
• Deprecation) EndpointWeightTransition in favor of WeightTransition

Result:

• You can now create LoadBalancer using various load balancing strategies to select an element from a list of candidates.

List<Endpoint> candidates = ...;
LoadBalancer.ofRoundRobin(candidates);
LoadBalancer.ofWeightedRoundRobin(candidates);
LoadBalancer.ofSticky(candidates, contextHasher);
LoadBalancer.ofWeightedRandom(candidates);
LoadBalancer.ofRampingUp(candidates);

[github-actions[bot]]

🔍 Build Scan® (commit: 59e08110b8294c72a79c5e9d8418e36ed47ab6e9)

Job name	Status	Build Scan®
build-ubicloud-standard-16-jdk-8	✅	https://ge.armeria.dev/s/d5untxeghf2eu
build-ubicloud-standard-16-jdk-21-snapshot-blockhound	✅	https://ge.armeria.dev/s/4oe33v3vrxoqs
build-ubicloud-standard-16-jdk-17-min-java-17-coverage	✅	https://ge.armeria.dev/s/n26dyekmzdwzi
build-ubicloud-standard-16-jdk-17-min-java-11	✅	https://ge.armeria.dev/s/f6m3omlg6ju5i
build-ubicloud-standard-16-jdk-17-leak	✅	https://ge.armeria.dev/s/vtozmvbdw4qpi
build-ubicloud-standard-16-jdk-11	✅	https://ge.armeria.dev/s/7x7xin3io7mrc
build-macos-latest-jdk-21	✅	https://ge.armeria.dev/s/c257j3emzuuma

[trustin]

Can we have some example code that shows how this API will solve #5289 and #5537 ? I'm particularly interested in the following:

• What will happen to the existing event loop selection mechanism?
• The only common dominator between event loop selection and endpoint selection is perhaps round-robin? If not, what other algorithms will they share?
• How does this API allow us to solve #5537?

[ikhoon]

(I assume this is ready for review?)

The public API may be changed a bit but I think there are no dramatic changes in the implementations.

What will happen to the existing event loop selection mechanism?

I think relying on EventLoopScheduler to pick a connection is not intuitive and forces users to understand the internal threading model. Currently, EventLoop is the key to find pooled connections, but I would like to change the key to Endpoint.

I haven't fully prototyped the connection load-balancing logic but I'd like to design as follows.

• New abstractions for connection and connection pools.
  • ConnectionPool.maxNumConnections() will limit the maximum connection more intuitively than maxNumEventLoopsPerEndpoint.
    • For HTTP/2, maxNumConnections() will default to 1 or 2.
    • For HTTP/1, Integer.MAX_VALUE can be the sensible default value.
    • The user will be able to set the desired number of connections through the connection pool more easily.
    • Devs may not have to explain maxNumEventLoopsPerEndpoint on Discord channels and how to control the maximum number of connections.

  public interface ConnectionPool extends SafeCloseable {
  
    @Nullable
    Connection acquire(ClientRequestContext ctx);
  
    void release(Connection connection);
  
    void add(Connection connection);
  
    void remove(Connection connection);
  
    int maxNumConnections();
  }
  
  public class Connection {
    private SessionProtocol protocol;
    private Endpoint endpoint;
    private Channel channel;
    private EventLoop eventLoop;
  }
  

• LoadBalancer<Connection, ClientRequestContext> may be used to pick a connection in a connection pool.
  • A new LoadBalancer to pick a connection that has the least requests could be implemented later.

  ConnectionPool.builder()
                .loadBalancerFactory(connections -> LoadBalancer.ofSticky(connections, ...))
                .maxNumConnections(1)
                ...
  ClientFactory.builder()
               .http1ConnectionPoolFactory(... -> newConnectionPool())
               .http2ConnectionPoolFactory(... -> newConnectionPool())
  
  

• After an Endpoint is acquired, the Endpoint is used as a key to a ConnectionPool for the endpoint.

  Map<Endpoint, ConnectionPool> pools = new ConcurrentHashMap<>();
  ConnectionPool pool = pools.get(ctx.endpoint());
  Connection connection = pool.acquire(ctx);
  if (connection == null) {
    // create a new connection using Bootstrap and add it to the connection pool
  }
  

I will do more PoC on a separate branch and leave feedback on whether this proposal is possible without making significant changes to the current implementation.

[trustin]

@ikhoon Thanks a lot for elaboration. I think I like where this is going. Is this PR now ready for review, or are you gonna add some more to it?

[jrhee17]

ConnectionPool.maxNumConnections()

One concern I have with the proposed implementation is pending acquisitions. More specifically, if the existing connections can't handle the current request and reaches maxNumConnections, what would be the proposed behavior?

e.g. If MAX_CONCURRENT_STREAMS is exceeded and the hard limit is reached, do we just allow the number of connections to exceed ConnectionPool#maxNumConnections?

[ikhoon]

More specifically, if the existing connections can't handle the current request and reaches maxNumConnections, what would be the proposed behavior?

If a user wants to use explicitly N connections, we may respect the value. So the request should be pending or failed.

A connection acquisition strategy could be added to handle the situation.

enum ConnectionAcquisitionStrategy {
    /**
     * Creates the desired number of connections eagerly.
     */
    EAGER,
    /**
     * Creates connections lazily when they are needed.
     */
    LAZY
}

// Unlimited but a new connection is created only when there are no connections available.
ConnectionPool
  .builder()
  .connectionAcquisitionStrategy(LAZY)
  .maxNumConnections(0)

// Otherwise, ConnectionAcquisitionStrategy could be set to each limit.
// In the following example, 2 connections will be created and a new connection
// will be created when MAX_CONCURRENT_STREAMS is reached. 
ConnectionPool
  .builder()
  .minNumConnections(2, EAGER)
  .maxNumConnections(10, LAZY)

[ikhoon]

Ready to review. @minwoox PTAL when available.

[minwoox]

@ikhoon 👍 👍 👍