Dynamic application placement with allocation restrictions, vertical stacking and even load distribution

• US 20070022426A1
• Filed: 07/17/2006
• Published: 01/25/2007
• Est. Priority Date: 07/25/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Steinder, Malgorzata, Karve, Alexei
• Granted Patent: US 7,877,755 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

A solution to a variant of a class constrained multiple knapsack problem. Previous solutions require that memory demand of every application be identical and do not consider minimizing placement changes. Previous techniques do not consider optimizing placement to improve load balancing as is described subsequently. Thus, the present invention provides systems, methods and apparatus, encapsulated in software, to provide the dynamic placement of application instances on a heterogeneous cluster of server machines. It depends on the existence of a visible and controllable platform, systems management and other business services that signal events and accept commands. It provides dynamically placing applications on servers such as to maximize a total amount of satisfied application demands, minimize a number of placement changes from a current placement, and minimize imbalance of load distribution of said applications on said at least one server.

Claims

1. A method for placement of applications comprising:

dynamically placing applications on at least one server such as to;

maximize a total amount of satisfied application demands,

minimize a number of placement changes from a current placement, and

minimize imbalance of load distribution of said applications on said at least one server,

the step of dynamically placing comprising the steps of;

obtaining the current placement of the applications;

computing a suggested new placement that maximizes the total amount of satisfied demands while minimizing the number of placement changes;

modifying the suggested placement in forming an updated placement to minimize the imbalance of load distribution of said applications without lowering the total amount of satisfied demands and without increasing the number of placement changes; and

executing placement changes on said current placement to effect said updated placement.

2. A method for placement of applications as recited in claim 1, further comprising computing a set of placement changes needed to convert the current placement into the updated placement.

3. A method for placement of applications as recited in claim 1, wherein the step of obtaining comprises:

observing applications on each of said at least one server, and

recording a status of each of said applications on each of said at least one server.

4. A method for placement of applications as recited in claim 1, wherein the step of computing comprises:

initializing a best placement to be the current placement;

finding a best allocation of capacity to each of said applications using the current placement;

calculating residual capacities of each of said at least one server and residual demands of each of said applications;

calculating a residual placement of said residual demands using said residual capacities;

combining said residual placement with said current placement to obtain a combined placement;

substituting said combined placement to be said best placement if said combined placement is better than said best placement

if all residual demands are satisfied, making said best placement to be said suggested placement, otherwise removing at least one application instance from the said current placement and repeating the steps of finding, calculating residual capacities, calculating a residual placement, combining, and substituting until all residual demands are satisfied or no more application instances may be removed from said current placement;

when no application instance may be removed from the said current placement, choosing said best placement to be said suggested placement.

5. A method for placement of applications as recited in claim 1, wherein the step of modifying comprises:

initializing utilization goal of each said at least one server to correspond to a hypothetical distribution of demand that maximizes a goodness of complete placement of said applications with respect to load balancing;

initializing a server set to comprise said at least one server;

finding a distribution of said application demands using said suggested placement that maximizes a goodness of placement of said applications with respect to load balancing;

finding a particular server having a highest utilization in said most balanced distribution of said application demands compared to the utilization goal of said particular server;

if said highest utilization exceeds said utilization goal of said particular server, finding a best application instance to remove from said particular server, finding a best new server to which to move said best application instance, calculating the best amount of demand allocated to said best application instance that should be moved from said particular server to said best new server, and moving said best application instance from said particular server to said new server;

if no best application instance is found, removing said particular server from said server list; and

repeating the steps of finding server, finding a best application, finding a best server, calculating, moving, and removing until said server set is empty.

6. A method for placement of applications as recited in claim 5, wherein said complete placement includes at least one instance of each of said applications on each said at least one server whenever an allocation restriction flag for said each of said applications on each said at least one server is not set to false.

8. A method for placement of applications as recited in claim 1, wherein the step of executing comprises:

calculating a set of placement changes required to transform said current placement into said updated placement.

9. A method for placement of applications as recited in claim 5, wherein the step of finding a best application instance to remove, excludes removing applications that are predetermined not to be removable from said particular server, and excludes removing application instances the removal of which does not improve utilization of said particular server compared to said utilization goal of said particular server.

10. A method for placement of applications as recited in claim 5, wherein the step of finding the best new server to which to move said best application instance excludes finding a specific server such that said allocation restriction flag for the specific server and said best application is set to false, and excludes finding the specific server such that residual load-independent capacity of the specific server is lower than load-independent demand of said best application, and excludes finding the specific server such that the utilization of the specific server compared to utilization goal of said specific server worsens as a result of moving said best application to the specific server.

11. A method for placement of applications as recited in claim 4, wherein when a new instance of a specific application is created on a particular server, in the step of calculating a residual placement of said residual demands using said residual capacities the amount of demand allocated to the new instance of the specific application is not allowed to exceed an allocation limit for the specific application on the particular server.

12. A method for placement of applications as recited in claim 4, the best amount of demand allocated to said best application instance that should be moved from said particular server to said best new server is such that after transferring said best amount of demand from said particular server to said best new server the goodness of computed placement with respect to load balancing is maximized.

13. A method for placement of applications as recited in claim 4, in the step of calculating the best amount of demand allocated to said best application instance that should be moved from said particular server to said best new server, the capacity of said best new server allocated to said best application instance after said best application instance is moved from said particular server to said best new server does not exceed said allocation limit of said application on said best new server.

16. An apparatus for placement of applications as recited in claim 13, wherein the means for obtaining comprises:

means for observing applications on each of said at least one server, and

means for recording a status of each of said applications on each of said at least one server.

30. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing placement of applications, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

31. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing placement of applications, said method steps comprising the steps of claim 1.

7. As is 6, wherein a number of said application instances of each of said applications on each said at least one server is such that each of said applications can use the entire capacity of each said at least one server.

14. An apparatus to place applications comprising:

means for dynamically placing applications on at least one server such as to;

maximize a total amount of satisfied application demands,

minimize a number of placement changes from a current placement, and

minimize imbalance of load distribution of said applications on said at least one server,

the means for dynamically placing comprising;

means for obtaining the current placement of the applications;

means for computing a suggested new placement that maximizes the total amount of satisfied demands while minimizing the number of placement changes;

means for modifying the suggested placement in forming an updated placement to minimize the imbalance of load distribution of said applications without lowering the total amount of satisfied demands and without increasing the number of placement changes, and

means for executing placement changes on said current placement to effect said updated placement.

15. An apparatus for placement of applications as recited in claim 14, further comprising means for computing a set of placement changes needed to convert the current placement into the updated placement.

17. An apparatus for placement of applications as recited in claim 14, wherein means for computing comprises:

means for initializing a best placement to be the current placement;

means for finding a best allocation of capacity to each of said applications using the current placement;

means for calculating residual capacities of each of said at least one server and residual demands of each of said applications;

means for calculating a residual placement of said residual demands using said residual capacities;

means for combining said residual placement with said current placement to obtain a combined placement;

means for substituting said combined placement to be said best placement if said combined placement is better than said best placement

if all residual demands are satisfied, employing means for making said best placement to be said suggested placement, otherwise employing means for removing at least one application instance from the said current placement and repeating the steps of finding, means for calculating residual capacities, means for calculating a residual placement, combining, and means for substituting until all residual demands are satisfied or no more application instances may be removed from said current placement;

when no application instance may be removed from the said current placement, means for choosing said best placement to be said suggested placement

18. An apparatus for placement of applications as recited in claim 14, wherein means for modifying comprises:

means for initializing utilization goal of each said at least one server to correspond to a hypothetical distribution of demand that maximizes a goodness of complete placement of said applications with respect to load balancing;

means for initializing a server set to comprise said at least one server;

means for finding a distribution of said application demands using said suggested placement that maximizes a goodness of placement of said applications with respect to load balancing;

means for finding a particular server having a highest utilization in said most balanced distribution of said application demands compared to the utilization goal of said particular server;

if said highest utilization exceeds said utilization goal of said particular server, means for finding a best application instance to remove from said particular server, means for finding a best new server to which to move said best application instance, and means for moving said best application instance from said particular server to said new server;

if no best application instance is found, means for removing said particular server from said server list; and

repeating the steps of finding server, finding a best application, finding a best server, moving, and removing until said server set is empty.

19. An apparatus for placement of applications as recited in claim 18, further comprising at least one limitation taken from a group of limitations consisting of:

said complete placement includes at least one instance of each of said applications on each said at least one server whenever an allocation restriction flag for said each of said applications on each said at least one server is not set to false;

a number of said application instances of each of said applications on each said at least one server is such that each of said applications can use the entire capacity of each said at least one server;

the means for executing comprises means for calculating a set of placement changes required to transform said current placement into said updated placement;

the means for finding a best application instance to remove, excludes removing applications that are predetermined not to be removable from said particular server, and excludes removing application instances the removal of which does not improve utilization of said particular server compared to said utilization goal of said particular server;

the means for finding the best new server to which to move said best application instance excludes finding a specific server such that said allocation restriction flag for the specific server and said best application is set to false, and excludes finding the specific server such that residual load-independent capacity of the specific server is lower than load-independent demand of said best application, and excludes finding the specific server such that the utilization of the specific server compared to utilization goal of said specific server worsens as a result of moving said best application to the specific server; and

when a new instance of a specific application is created on a particular server, in the means for calculating a residual placement of said residual demands using said residual capacities the amount of demand allocated to the new instance of the specific application is not allowed to exceed an allocation limit for the specific application on the particular server.

32. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing placement of applications, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 14.

20. A application placement method comprising providing placement of applications on a cluster of servers to facilitate load balancing, the step of providing comprising the steps of:

obtaining a current placement of applications,

computing a suggested new placement of applications,

modifying the suggested placement in forming a computed placement by computing and replacing a set of triples such that moving an application in each triple from a server of origin of said application to a destination server maximizes utility of the computed placement with respect to load balancing, and

executing the computed placement.

21. A method for placement of applications as recited in claim 20, wherein the set of triples comprises:

application, server of origin, and destination server.

22. A method for placement of applications as recited in claim 20, wherein the step of computing and replacing the set of triples, excludes triples wherein the application in the said triple is predetermined not to be removed from the server of origin in said triple.

23. A method for placement of applications as recited in claim 20, wherein the step of computing and replacing the set of triples, excludes finding a triple wherein an allocation restriction flag for a specific destination server in said triple and specific application in said triple is set to false, and excludes finding a triple wherein residual load-independent capacity of the specific destination server in said triple is lower than load-independent demand of the specific application in said triple.

24. A method for placement of applications as recited in claim 20, wherein the step of computing and replacing a set of triples comprises the step of calculating a best amount of demand of a particular application in a particular triple that should be transferred from the server of origin of said particular application in the particular triple to a destination server in the particular triple.

25. A method for placement of applications as recited in claim 24, wherein the best amount of demand of the application in a particular triple to be transferred from the server of origin in the particular triple to the destination server in the particular triple is such that after transferring said best amount of demand from said particular server of origin to said particular destination server the goodness of computed placement with respect to load balancing is maximized.

26. A method for placement of applications as recited in claim 24, wherein in the step of calculating the best amount of demand of the application in a particular triple that should be transferred from server of origin in the particular triple to the destination server in the particular triple, the capacity of the destination server in said particular triple allocated to the application in said particular triple after instance of said application in said particular triple is moved from server of origin in said particular triple to destination server in said particular triple does not exceed said allocation limit of said application in said particular triple on said server in said particular triple;

33. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for application placement, said method steps comprising the steps of claim 20.

34. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing application placement, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 20.

27. An application placement method comprising:

providing a set of servers and a set of applications,

associating with each server n a load-independent capacity and a load-dependent capacity, said load-independent capacity corresponding to the server'"'"'s memory, said load-dependent capacity corresponding to the server'"'"'s CPU power;

associating with each application;

a load-independent demand value corresponding to the application'"'"'s memory,

and a load dependent demand value corresponding to CPU requirements,

a minimum number of instances that must be started for the application, min_m,

a maximum number of instances that may be started for the application, max_m;

associating with each application and each server parameters;

an allocation restriction flag, R_mn indicating whether an instance of the application m may be started on server n,

an allocation limit for application m instance on server n, π

_mn that indicates the maximum amount of CPU power that can be used by a single instance of application m on server n;

obtaining application placement currently in effect;

verifying if the placement currently in effect is sufficient to satisfy all application demands and respects all allocation restrictions and allocation limits;

if the current placement does not meet the said criteria, finding a new matrix solution to placement problem where each matrix cell mn, includes a number of instances of application m that may be started on server n such that;

minimum and maximum policies of all applications are observed,

allocation restrictions are observed,

load-independent capacity limits are observed, and

it is possible to allocate load of all dynamic clusters to instances without exceeding per-instance allocation limits and load-dependent capacity limits;

when a previous matrix exists, maximizing the total amount of satisfied application demand is maximized;

when more than one previous placement matrix exists, minimizing a number of changes between the previous and the new matrix;

when more than one previous matrix exists, finding a matrix that maximizes the amount of allows a load allocated to servers to be balanced; and

when said matrix is found, executing the set of placement changes required to transform the current placement matrix into the calculated placement matrix.

35. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for application placement, said method steps comprising the steps of claim 27.

28. A method for application placement comprising:

finding a new matrix solution to placement problem where each matrix cell mn, includes a number of instances of application m that may be started on server n such that;

minimum and maximum policies of all applications are observed,

allocation restrictions are observed,

load-independent capacity limits are observed, and

it is possible to allocate load of all dynamic clusters to instances without exceeding per-instance allocation limits and load-dependent capacity limits;

prioritizing candidate placement solutions according to a measure of placement utility;

calculating a suggested placement satisfying preliminary placement objectives;

modifying the suggested placement such that an additional placement objective is satisfied; and

re-balancing the suggested placement such as to maximize a goodness of placement with respect to load allocation such that a total amount of satisfied demand remains unchanged and a number of placement changes compared to a previous placement does not increase.

29. A method as recited in claim 28, further comprising at least one limitation taken from a group of limitations consisting of:

the step of re-balancing placement includes at least one implementation of steps of;

assessing the goodness of the suggested placement, and choosing a list of triples of replacement decisions and replace applications;

the list of triples includes application, server of origin, and destination server;

the goodness of placement includes focusing on an ability of the placement to facilitate load balancing by a request router, wherein optimal placement is such that the request router can perfectly balance the load across all servers using its load balancing policy;

the goodness of placement includes loading clustered on as few servers as possible to allow some servers to be turned off;

further comprising calculating placement utility with respect to load balancing, identifying a most profitable change and moving an instance between servers.

36. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing application placement, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 28.