Dynamically computing load balancer subset size in a distributed computing system

Patent metadata

Field	Value
Publication number	US-11956308-B2
Application number	US-202318198575-A
Country	US
Kind code	B2
Filing date	May 17, 2023
Priority date	Nov 1, 2019
Publication date	Apr 9, 2024
Grant date	Apr 9, 2024

Abstract

A distributed computing system uses dynamically calculates a subset size for each of a plurality of load balancers. Each of a plurality of load balancers logs requests from client devices for connections to back-end servers and periodically sends a request report to a traffic aggregator, which aggregates the report requests from the load balancers in the corresponding zone. Each traffic aggregator sends the aggregated request data to a traffic controller, which aggregates the request data to determine a total number of requests received at the system. The total request data is transmitted through each traffic aggregator to each load balancer instance, which calculates a percentage of the total number of requests produced by the load balancer and determines a subset size based on the calculated percentage.

First claim

The invention claimed is:

1. A method for dynamically subsetting a plurality of load balancers in a distributed computer system, the method comprising:
receiving, at each of one or more traffic aggregators from each of a plurality of load balancers assigned to that traffic aggregator, a request report including a number of requests received by that load balancer;
sending, from each of the one or more traffic aggregators to a traffic controller, aggregated request data comprising a total number of requests received by the load balancers assigned to that traffic aggregator;
computing, by the traffic controller based on the aggregated request data from each traffic aggregator, a total number of requests received by all of the load balancers in the distributed computer system; and
sending, from the traffic controller to each of the plurality of load balancers in the distributed computer system, data corresponding to the total number of requests received by all of the load balancers, wherein each load balancer of the plurality of load balancers in the distributed computer system computes a subset size based, at least in part, on a percentage of the total number of requests that are received at the load balancer.

2. The method of claim 1 , wherein the subset size comprises a number of connections between one or more clients and one or more back-end servers.

3. The method of claim 1 , wherein a request received by a load balancer comprises a request for a connection from a client to one or more back-end servers.

4. The method of claim 1 , further comprising:
periodically recomputing, by the traffic controller, the total number of requests based on updated aggregated request data received from each of the one or more traffic aggregators; and
sending, by the traffic controller, an updated total number of requests to each of the plurality of load balancers in the distributed computer system, wherein each load balancer of the plurality of load balancers in the distributed computer system computes an updated subset size based on a percentage of total demand that is received at the load balancer.

5. The method of claim 4 , further comprising:
determining, by at least one traffic aggregator of the one or more traffic aggregators, that an updated request report has not been received from at least one load balancer assigned to that traffic aggregator; and
computing, by the at least one traffic aggregator, updated aggregated request data based in part on a most recent request report received from the at least one load balancer.

6. The method of claim 1 , further comprising:
detecting, by at least one traffic aggregator of the one or more traffic aggregators, an addition of at least one load balancer to the distributed computer system;
sending updated aggregated request data to the traffic controller, the updated aggregated request data including a number of requests received at the additional load balancer;
computing, by the traffic controller based on the updated aggregated request data, an updated total number of requests; and
sending, from the traffic controller to each of the plurality of load balancers in the distributed computer system, the updated total number of requests, wherein each load balancer of the plurality of load balancers in the distributed computer system computes an updated subset size based on a percentage of total demand received at the load balancer.

7. The method of claim 1 , further comprising:
storing, by the traffic controller, historical data regarding the number of requests received at the plurality of load balancers in the distributed computer system;
predicting, using the stored historical data, upcoming demand on the plurality of load balancers in the distributed computer system; and
determining, based on the predicted upcoming demand, whether to add additional load balancers to the distributed computer system.

8. A system comprising:
a processor for executing computer program instructions; and
a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations for dynamically subsetting a plurality of load balancers in a distributed computer system, the operations comprising:
receiving, at each of one or more traffic aggregators from each of a plurality of load balancers assigned to that traffic aggregator, a request report including a number of requests received by that load balancer;
sending, from each of the one or more traffic aggregators to a traffic controller, aggregated request data comprising a total number of requests received by the load balancers assigned to that traffic aggregator;
computing, by the traffic controller based on the aggregated request data from each traffic aggregator, a total number of requests received by all of the load balancers in the distributed computer system; and
sending, from the traffic controller to each of the plurality of load balancers in the distributed computer system, data corresponding to the total number of requests received by all of the load balancers in the distributed computer system, wherein each load balancer of the plurality of load balancers in the distributed computer system computes a subset size based, at least in part, on a percentage of the total number of requests that are received at the load balancer.

9. The system of claim 8 , wherein the subset size comprises a number of connections between one or more clients and one or more back-end servers.

10. The system of claim 8 , wherein a request received by a load balancer comprises a request for a connection from a client to one or more back-end servers.

11. The system of claim 8 , wherein the operations further comprise:
periodically recomputing, by the traffic controller, the total number of requests based on updated aggregated request data received from each of the one or more traffic aggregators; and
sending, by the traffic controller, an updated total number of requests to each of the plurality of load balancers in the distributed computer system, wherein each load balancer of the plurality of load balancers in the distributed computer system computes an updated subset size based on a percentage of total demand that is received at the load balancer.

12. The system of claim 11 , wherein the operations further comprise:
determining, by at least one traffic aggregator of the one or more traffic aggregators, that an updated request report has not been received from at least one load balancer assigned to that traffic aggregator; and
computing, by the at least one traffic aggregator, updated aggregated request data based in part on a most recent request report received from the at least one load balancer.

13. The system of claim 8 , wherein the operations further comprise:
detecting, by at least one traffic aggregator of the one or more traffic aggregators, an addition of at least one load balancer to the distributed computer system;
sending updated aggregated request data to the traffic controller, the updated aggregated request data including a number of requests received at the additional load balancer;
computing, by the traffic controller based on the updated aggregated request data, an updated total number of requests; and
sending, from the traffic controller to each load balancer of the plurality of load balancers in the distributed computer system, the updated total number of requests, wherein each load balancer of the plurality of load balancers in the distributed computer system computes an updated subset size based on a percentage of total demand received at the load balancer.

14. The system of cla

Assignees

• Uber Technologies Inc

Inventors

• Varanasi Prashant
• Liao Chien-Chih
• Newton Simon Jeffrey

Classifications

• H04L67/1004

  Server selection for load balancing · CPC title

• H04L67/1036 Primary

  Load balancing of requests to servers for services different from user content provisioning, e.g. load balancing across domain name servers · CPC title

• H04L47/125 Primary

  by balancing the load, e.g. traffic engineering · CPC title

• H04L47/28

  in relation to timing considerations · CPC title

• H04L67/01

  Protocols · CPC title