Load balancing deterministically-subsetted processing resources using fractional loads

Patent metadata

Field	Value
Publication number	US-11119827-B2
Application number	US-202016775292-A
Country	US
Kind code	B2
Filing date	Jan 29, 2020
Priority date	Aug 13, 2018
Publication date	Sep 14, 2021
Grant date	Sep 14, 2021

Abstract

Systems and methods are described for load balancing between a set of servers. Subsets of servers from the set of servers are assigned, via deterministic subsetting, to respective clients from a set of clients. Unlike conventional load balancing techniques using deterministic subsetting, the disclosed techniques enable configuring a client to distribute different amounts of load among the servers in its server subset. Techniques for constructing the subsets are also described.

First claim

What is claimed is:

1. A load-balancing method for balancing a processing load of a plurality of clients among a plurality of servers, the method comprising:
assigning a different subset of the plurality of servers to each respective client in the plurality of clients, each respective client being configured to distribute processing requests only to the servers in the subset assigned thereto;
for each respective client in the plurality of clients, determining load weights for distributing processing requests to the servers in the subset assigned thereto, wherein each of the load weights indicates a relative volume of processing requests to be transmitted from the respective client to servers in the subset assigned to the respective client, the load weights for each respective client are determined such that each server of the plurality of servers processes substantially a same unit amount of processing requests and such that at least one server of the plurality of servers is assigned to multiple clients in the plurality of clients, and at least one of the load weights for each respective client is a fraction of another one of the load weights for the client; and
controlling the plurality of clients to distribute processing requests based on the determined load weights,
wherein the assigning a different subset of the plurality of servers to each respective client comprises:
representing the plurality of servers in a continuous logical ring in a memory, with a respective server slice of a first width in the ring representing each server;
evenly dividing the ring into sub-portions of a second width, the number of the sub-portions being equal to the number of clients in the plurality of clients; and
assigning the subset to the respective client based upon a corresponding one of the sub-portions.

2. The method of claim 1 , wherein, for the particular client, the subset of the plurality of servers assigned to the particular client and respective load weights in the subset assigned thereto are determined based upon the number of servers in the plurality of servers, the number of clients in the plurality of clients, and an identifier of the client.

3. The method of claim 1 , wherein the assigning a different subset of the plurality of servers to each respective client comprises: evenly dividing the plurality of servers into said subsets based upon the number of servers in the plurality of servers and the number of clients in the plurality of clients.

4. The method of claim 1 , wherein determining respective load weights for distributing the processing requests to the servers in the subset assigned to each respective client comprises:
determining the respective load weights based upon respective widths of portions of corresponding server slices overlapping with the sub-portion corresponding to the respective client.

5. A load balancing computer processing system, comprising a plurality of clients, each respective client comprising communication circuitry and a processor,
wherein the processor is configured to control the communication circuitry of the respective client to distribute processing requests to a respective subset of a plurality of servers over a communication network by transmitting a first weighted-quantity of the processing requests to each of one or more of the servers in the respective subset and transmitting to at least one other server in the respective subset a second weighted-quantity of the processing requests, the second weighted-quantity being a fraction of the first weighted-quantity such that the respective client is configured to distribute a same volume of processing requests as other clients in the plurality of clients and such that at least one server of the plurality of servers is assigned to multiple clients,
wherein the first weighted-quantity and the second weighted-quantity are determined based upon at least the number of servers in the plurality of servers, and the number of clients in the plurality of clients,
wherein the load balancing computer processing system further comprises a control server, the control server is configured to determine the respective subset of servers and a proportion of processing requests to be sent to each server in the respective subset based upon information about other said clients, information about the plurality of servers, size of the respective subset of servers, and a unique identifier for the client,
wherein determining the respective subset of servers and the proportion of processing requests to be sent to each server in the respective subset comprises:
evenly dividing the plurality of servers into subsets of servers based upon the number of servers in the plurality of servers and the number of clients in the plurality of clients, and wherein determining the respective subset of servers and the proportion of processing requests to be sent to each server in the respective subset further comprises:
representing the plurality of servers in a continuous logical ring, with a respective slice of a first width in the ring representing each server;
evenly dividing the ring into sub-portions of a second width, a total number of the sub-portions being equal to the number of clients in the plurality of clients; and
determining the respective subset based upon a corresponding one of the sub-portions.

6. The load balancing computer processing system according to claim 5 , wherein the one or more of the servers comprise a majority of servers in the respective subset of servers.

7. The load balancing computer processing system according to claim 5 , wherein the first weighted-quantity and the second weighted-quantity are determined based also upon the size of the respective subset of servers.

8. The load balancing computer processing system according to claim 5 , wherein at least one client in the plurality of clients is configured to transmit the second weighted-quantity of processing requests to a first one of the other servers in the respective subset and to transmit a third weighted-quantity of processing requests to a second one of the other servers, the second and third weighted-quantities each being a fraction of the first weighted-quantity.

9. The load balancing computer processing system according to claim 5 , wherein at least one of said respective subset of servers having a different number of servers than others of the respective subset of servers.

10. The load balancing computer processing system according to claim 5 , wherein said each client is further configured to determine, independently of other said clients, the respective subset of servers, and a proportion of processing requests to be sent to each server in the respective subset based upon information about other said clients, information about the plurality of servers, size of the respective subset of servers, and a unique identifier for the client.

11. The load balancing computer processing system according to claim 5 , wherein each server in the plurality of servers is configured to be homogeneous with respect to other servers in the plurality of servers.

12. The load balancing computer processing system according to claim 5 , further comprising the plurality of servers, each server being configured to receive processing requests from at least one of the clients, and at least one of the servers being configured to receive first and second amounts of the processing requests from two clients, a total sum of the first and second amounts of the processing requests being equal to the first weighted-quantity of the processing requests.

13. The load balancing computer processing system according to claim 5 , wherein said each client rece

Assignees

• Twitter Inc

Inventors

• Anderson Bryce
• Furse Daniel
• Ma Eugene
• Oanta Ruben

Classifications

• H04L67/1027

  Persistence of sessions during load balancing · CPC title

• H04L67/1004

  Server selection for load balancing · CPC title

• H04L67/1025

  Dynamic adaptation of the criteria on which the server selection is based · CPC title

• H04L67/1001

  for accessing one among a plurality of replicated servers · CPC title

• H04L67/1031

  Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests · CPC title