Load balancing with granularly redistributable workloads

• US 9,632,840 B2
• Filed: 04/22/2014
• Issued: 04/25/2017
• Est. Priority Date: 04/22/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chan, Yuk L., Cramer, Christopher, King, Robert G., Naphade, Deepti M., Pava, Jairo A.
• Primary Examiner(s): BROPHY, MATTHEW J
• Application Number:
  US14/258,588
• Publication Number:
  US 20150301869A1
• Time in Patent Office: 1,099 Days
• Field of Search: None
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

In one embodiment, a computer-implemented method includes receiving a plurality of tasks to be assigned to a plurality of subgroups of virtual servers. A first plurality of the tasks is assigned to a first subgroup, where the first subgroup includes two or more virtual servers. For each of the first plurality of tasks assigned to the first subgroup, a virtual server is selected within the first subgroup, and the task is assigned to the selected virtual server. A first virtual server is migrated, by a computer processor, from the first subgroup of virtual servers to a second subgroup of virtual servers, if at least one predetermined condition is met, where the migration maintains in the first subgroup at least one of the first plurality of tasks assigned to the first subgroup.

Claims

1. A computer-implemented, comprising:

receiving a plurality of tasks to be assigned to a plurality of subgroups of virtual servers, wherein the plurality of subgroups of virtual servers runs atop a hypervisor, wherein the hypervisor runs on a physical server;

assigning a first plurality of the tasks to a first subgroup of virtual servers, wherein the first subgroup of virtual servers comprises two or more virtual servers;

for each of the first plurality of tasks assigned to the first subgroup of virtual servers, selecting a virtual server within the first subgroup of virtual servers and assigning the task to the selected virtual server;

migrating, by a computer processor, a first virtual server from the first subgroup of virtual servers to a second subgroup of virtual servers if at least one predetermined condition is met, wherein the migration maintains in the first subgroup of virtual servers at least one of the first plurality of tasks assigned to the first subgroup of virtual servers; and

calculating a first target quantity of virtual servers to be maintained in the first subgroup of virtual servers, wherein the first target quantity of virtual servers is based on a guaranteed capacity for the first subgroup of virtual servers and an average number of workloads assigned to the first subgroup of virtual servers.

2. The method of claim 1, wherein the at least one of the first plurality of tasks maintained in the first subgroup of virtual servers comprises one or more tasks assigned to other virtual servers within the first subgroup of virtual servers.

3. The method of claim 1, wherein migrating the first virtual server decreases a completion delay of the first subgroup of virtual servers.

4. The method of claim 1, further comprising selecting the second subgroup of virtual servers as a destination subgroup for the migration of the first virtual server, wherein the second subgroup of virtual servers has a free capacity that is no less than a utilization of the first virtual server in the first subgroup of virtual servers combined with a free capacity of the first subgroup of virtual servers.

5. The method of claim 1, further comprising

calculating a second target quantity of virtual servers to be maintained in the second subgroup of virtual servers.

6. The method of claim 5, wherein migrating the first virtual server moves the quantities of virtual servers in both the first subgroup of virtual servers and the second subgroup of virtual servers closer to their respective target quantities of virtual servers.

7. The method of claim 5, wherein the first target quantity for the first subgroup of virtual servers is based on at least one of a guaranteed capacity allotted to the first subgroup of virtual servers and a quantity of workloads assigned to the first subgroup of virtual servers.

8. A system comprising:

a first-level load balancer configured to receive a plurality of tasks to be assigned to a plurality of subgroups of virtual servers and to assign a first plurality of the tasks to a first subgroup of virtual servers, wherein the first subgroup of virtual servers comprises two or more virtual servers;

a second-level load balancer configured to, for each of the first plurality of tasks assigned to the first subgroup of virtual servers, select a virtual server within the first subgroup of virtual servers and assign the task to the selected virtual server;

a migrator configured to migrate a first virtual server from the first subgroup of virtual servers to a second subgroup of virtual servers if at least one predetermined condition is met, wherein the migration maintains in the first subgroup of virtual servers at least one of the first plurality of tasks assigned to the first subgroup of virtual servers; and

a re-balancer configured to calculate a first target quantity of virtual servers to be maintained in the first subgroup of virtual servers, wherein the first target quantity of virtual servers is based on a guaranteed capacity for the first subgroup of virtual servers and an average number of workloads assigned to the first subgroup of virtual servers,

wherein the plurality of subgroups of virtual servers runs atop a hypervisor, wherein the hypervisor runs on a physical server.

9. The system of claim 8, wherein the at least one of the first plurality of tasks maintained in the first subgroup of virtual servers comprises one or more tasks assigned to other virtual servers within the first subgroup of virtual servers.

10. The system of claim 8, wherein migrating the first virtual server decreases a completion delay of the first subgroup of virtual servers.

11. The system of claim 8, wherein the migrator is further configured to select the second subgroup of virtual servers as a destination subgroup of virtual servers for the migration of the first virtual server, wherein the second subgroup of virtual servers has a free capacity that is no less than a utilization of the first virtual server in the first subgroup combined with a free capacity of the first subgroup of virtual servers.

12. The system of claim 8, wherein the re-balancer is further configured to

calculate a second target quantity of virtual servers to be maintained in the second subgroup of virtual servers.

13. The system of claim 12, wherein migrating the first virtual server moves the quantities of virtual servers in both the first subgroup of virtual servers and the second subgroup of virtual servers closer to their respective target quantities of virtual servers.

14. The system of claim 12, wherein the first target quantity for the first subgroup of virtual servers is based on at least one of a guaranteed capacity allotted to the first subgroup of virtual servers and a quantity of workloads assigned to the first subgroup of virtual servers.

15. A computer program product comprising a computer readable storage medium having non-transitory computer readable program code embodied thereon, the computer readable program code executable by a processor to perform a method comprising:

receiving a plurality of tasks to be assigned to a plurality of subgroups of virtual servers, wherein the plurality of subgroups of virtual servers runs atop a hypervisor, wherein the hypervisor runs on a physical server;

assigning a first plurality of the tasks to a first subgroup of virtual servers, wherein the first subgroup of virtual servers comprises two or more virtual servers;

for each of the first plurality of tasks assigned to the first subgroup of virtual servers, selecting a virtual server within the first subgroup of virtual servers and assigning the task to the selected virtual server; and

migrating a first virtual server from the first subgroup of virtual servers to a second subgroup of virtual servers if at least one predetermined condition is met, wherein the migration maintains in the first subgroup of virtual servers at least one of the first plurality of tasks assigned to the first subgroup of virtual servers without migrating the at least one of the first plurality of tasks assigned to the first subgroup of virtual servers; and

calculating a first target quantity of virtual servers to be maintained in the first subgroup of virtual servers, wherein the first target quantity of virtual servers is based on a guaranteed capacity for the first subgroup of virtual servers and an average number of workloads assigned to the first subgroup of virtual servers.

16. The computer program product of claim 15, wherein the at least one of the first plurality of tasks maintained in the first subgroup of virtual servers comprises one or more tasks assigned to other virtual servers within the first subgroup of virtual servers.

17. The computer program product of claim 15, wherein migrating the first virtual server decreases a completion delay of the first subgroup of virtual servers.

18. The computer program product of claim 15, the method further comprising selecting the second subgroup of virtual servers as a destination subgroup of virtual servers for the migration of the first virtual server of virtual servers, wherein the second subgroup has a free capacity that is no less than a utilization of the first virtual server in the first subgroup of virtual servers combined with a free capacity of the first subgroup of virtual servers.

19. The computer program product of claim 15, the method further comprising

calculating a second target quantity of virtual servers to be maintained in the second subgroup of virtual servers;

wherein migrating the first virtual server moves the quantities of virtual servers in both the first subgroup of virtual servers and the second subgroup of virtual servers closer to their respective target quantities of virtual servers.

20. The computer program product of claim 19, wherein the first target quantity for the first subgroup of virtual servers is based on at least one of a guaranteed capacity allotted to the first subgroup of virtual servers and a quantity of workloads assigned to the first subgroup of virtual servers.