Load balancing deterministically-subsetted processing resources using fractional loads

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.

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, 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 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:   determining a client width number based upon the number of servers in the plurality of servers and the number of clients in the plurality of clients; and   dividing the plurality of servers into said subsets in accordance with the determined client width number.   
     
     
         2 . The method of  claim 1 , wherein, for a particular client in the plurality of clients, 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, and
 wherein the dividing the plurality of servers into said subsets in accordance with the determined client width number comprises:   determining whether the client width number is not less than a preconfigured subset size;   upon determination that the client width number is not less than the preconfigured subset size, evenly dividing the plurality of servers into said subsets; and   upon determination that the client width number is less than the preconfigured subset size, forming a logical expanded set of servers by duplicating the plurality of servers, and, based upon the logical expanded set of servers, evenly dividing the plurality of servers into said subsets.   
     
     
         3 . The method of  claim 1 , wherein each of the load weights indicates a relative volume of processing requests to be transmitted from a client to servers in the subset assigned to the client. 
     
     
         4 . The method of  claim 1 , wherein the assigning a different subset of the plurality of servers to each respective client further 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.   
     
     
         5 . The method of  claim 4 , 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.   
     
     
         6 . A client in a load balancing computer processing system comprising a plurality of clients, the client comprising communication circuitry and at least one processor, wherein the at least one processor is configured to:
 control the communication circuitry 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 at least one server of the plurality of servers is assigned to multiple clients, and   determine the respective subset of servers and a proportion of processing requests to be sent to each server in the respective subset based at least upon information about other said clients, information about the plurality of servers, and size of the respective subset of servers,   wherein determining the respective subset of servers and the proportion of processing requests to be sent to each server in the respective subset comprises:   determining the number of clients in the plurality of clients, the number of the servers in the plurality of servers, and the specified subset size;   determining a client width number based upon the number of servers in the plurality of servers and the number of clients in the plurality of clients; and   dividing the plurality of servers into said subsets in accordance with the determined client width number.   
     
     
         7 . The client according to  claim 6 , wherein the one or more of the servers comprise a majority of servers in the respective subset of servers. 
     
     
         8 . The client according to  claim 6 , 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. 
     
     
         9 . The client according to  claim 8 , wherein the dividing the plurality of servers into said subsets in accordance with the determined client width number comprises:
 determining whether the client width number is less than a preconfigured subset size;   upon determination that the client width number is not less than the specified subset size, evenly dividing the plurality of servers into subsets of servers; and   upon determination that the client width number is less than the specified subset size, forming a logical expanded set of servers by duplicating the plurality of servers, and, based upon the logical expanded set of servers, evenly dividing the plurality of servers into subsets of servers.   
     
     
         10 . The client according to  claim 6 , wherein the client 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. 
     
     
         11 . The client according to  claim 6 , wherein at least one of said respective subset of servers having a different number of servers than others of the respective subset of servers. 
     
     
         12 . The client according to  claim 6 , wherein the client is configured to determine, independently of other said clients, the respective subset of servers, and the 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, the size of the respective subset of servers, and an unique identifier for the client. 
     
     
         13 . The client according to  claim 6 , wherein each server in the plurality of servers is configured to be homogeneous with respect to other servers in the plurality of servers. 
     
     
         14 . The client according to  claim 6 , wherein each of the servers is 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. 
     
     
         15 . The client according to  claim 6 , wherein the client is configured to receive the processing requests from a plurality of other devices. 
     
     
         16 . The client according to  claim 6 , wherein the first weighted-quantity is uniform among all clients in the plurality of clients, and wherein the second weighted-quantity is non-uniform among at least some of the clients in the plurality of clients. 
     
     
         17 . The client according to  claim 6 , wherein a first client in the plurality of clients is configured to transmit the second weighted-quantity of the respectively corresponding processing requests to a first one of the servers, and a second client of the plurality of clients is configured to transmit the second weighted-quantity of the respectively corresponding processing requests to the first one of the servers and a second one of the servers. 
     
     
         18 . The client according to  claim 6 , wherein each of the servers is configured as a HTTP backend server and each of the clients is configured as a HTTP proxy. 
     
     
         19 . The client according to  claim 6 , 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.   
     
     
         20 . The client according to  claim 6 , wherein the client is configured to establish a communication connection to each server in a corresponding subset of servers, and wherein at least one server in the plurality of servers is replaceable or removable without causing at least one of the plurality of clients to re-establish previously established connections to servers in a corresponding subset of servers. 
     
     
         21 . A non-transitory computer readable storage medium storing computer program instructions that, when executed by at least one 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, 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,   wherein determining a subset of servers from the plurality of servers comprises:   determining a client width number based upon the server set size and the client set size; and   dividing the plurality of servers into subsets of servers in accordance with the determined client width number.