Systems and methods for proxy-less load balancing
View Patent ↗Load balancing in a server pool may be achieved by rebalancing subsets of backend servers allocated to frontend servers. The rebalancing may be achieved by determining a max and min subset of servers and transferring backend servers between the subsets.
1. A method for balancing subsets of backend servers, the method comprising:
assigning, using a network controller, an index number to each backend server in a set of backend servers;
allocating, for each of a plurality of frontend servers, a respective subset of the set of backend servers based on a random shuffling of the index numbers assigned to the backend servers, wherein the allocating includes:
determining a subset size that is a desired number of backend servers in a subset,
dividing the plurality of frontend servers into rounds, each round having a number of frontend servers less than or equal to a number of backend servers in the set of backend servers divided by the subset size, and
for each round, generating a shuffled ordering of the index numbers for the set of backend servers and deterministically assigning each frontend server in the round to a respective subset of backend servers using the shuffled ordering;
determining that a size of a first subset of backend servers differs from a size of a second subset of backend servers; and
transferring a backend server in the first subset of backend servers to the second subset of backend servers.
2. The method of claim 1 further comprising identifying a backend server in the first subset of backend servers that is not included in the second subset of backend servers.
3. The method of claim 2 wherein the transferring a backend server comprises transferring the identified backend server from the first subset of backend servers to the second subset of backend servers.
4. The method of claim 2 further comprising identifying the backend server based on its respective index number.
5. The method of claim 1 wherein the first subset of backend servers comprises a subset having a greatest number of backend servers, and the second subset of backend servers comprises a subset having a lowest number of backend servers.
6. The method of claim 5 wherein the first subset of backend servers comprises a subset having the greatest number of backend servers and a lowest subset index number, and the second subset of backend servers comprises a subset having the lowest number of backend servers and a highest subset index number.
7. The method of claim 1 further comprising repeating the determining step and the transferring step until the difference in a size of the first subset of backend servers and the second set of backend servers meets a threshold value.
8. The method of claim 7 wherein the threshold value is 1.
9. A system for balancing subsets of backend servers, the system comprising:
a set of backend servers, each assigned an index number;
a network controller comprising a computer processor configured to:
allocate, for each of a plurality of frontend servers, a respective subset of the set of backend servers based on a random shuffling of the index numbers assigned to the backend servers, wherein the allocating includes:
determining a subset size that is a desired number of backend servers in a subset,
dividing the plurality of frontend servers into rounds, each round having a number of frontend servers less than or equal to a number of backend servers in the set of backend servers divided by the subset size, and
for each round, generating a shuffled ordering of the index numbers for the set of backend servers and deterministically assigning each frontend server in the round to a respective subset of backend servers using the shuffled ordering;
determine that a size of a first subset of backend servers differs from a size of a second subset of backend servers; and
transfer a backend server in the first subset of backend servers to the second subset of backend servers.
10. The system of claim 9 wherein the network controller is further configured to identify a backend server in the first subset of backend servers that is not included in the second subset of backend servers.
11. The system of claim 10 wherein the transferring a backend server comprises transferring the identified backend server from the first subset of backend servers to the second subset of backend servers.
12. The system of claim 10 wherein the network controller is further configured to identify the backend server based on its respective index number.
13. The system of claim 9 wherein the first subset of backend servers comprises a subset having a greatest number of backend servers, and the second subset of backend servers comprises a subset having a lowest number of backend servers.
14. The system of claim 13 wherein the first subset of backend servers comprises a subset having the greatest number of backend servers and a lowest subset index number, and the second subset of backend servers comprises a subset having the lowest number of backend servers and a highest subset index number.
15. The system of claim 9 wherein the network controller is further configured to repeat the determining step and the transferring step until a difference in a size of the first subset of backend servers and the second set of backend servers meets a threshold value.
16. The system of claim 15 wherein the threshold value is 1.
17. The method of claim 1 , wherein generating the shuffled ordering in a particular round comprises using a random number generator seeded with a value corresponding to the particular round.
18. The method of claim 1 , wherein the desired number of backend servers in a subset is an integer multiple of a minimum subset size.
19. The system of claim 9 , wherein generating the shuffled ordering in a particular round comprises using a random number generator seeded with a value corresponding to the particular round.
20. The system of claim 9 , wherein the desired number of backend servers in a subset is an integer multiple of a minimum subset size.