Load balancing deterministically-subsetted processing resources using fractional loads
AssigneeTwitter, Inc.
InventorsBryce ANDERSON, Daniel Furse, Eugene Ma, Ruben Oanta
Life of this patent
Estimating the term…
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.
Claims25
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, said each 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 respective load weights for distributing processing requests to the servers in the subset assigned thereto, wherein 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.
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.
A non-transitory computer readable storage medium storing computer program instructions that, when executed by a processor of a client in a computer processing system, causes the client to balance load distributed over a communication network among a plurality of servers, comprising:
- determining a total number of the plurality servers as a server set size, a total number of a plurality clients as a client set size, an unique identifier assigned to the client, and a subset size for the client, the subset size being a total number of servers to be connected with the client;
- and
- based upon the determined server set size, client set size, subset size, and identifier assigned to the client, determining a subset of servers from the plurality of servers, and relative load weights for servers in the selected subset, so that a same volume of processing requests is distributed to the plurality of servers by the client as other clients in the plurality of clients, each of the relative load weights indicating relative amounts of processing requests transmitted from the client to respective server in the subset, and the selected subset having a size of at least the determined subset size and of a same size as respective subsets of selected by each other client in the plurality of clients,
- wherein at least one of the relative load weights for one server in the selected subset is a fraction of another of the relative load weights for another server in the selected subset.
Dependencies are inferred from the claim text.