Decentralized application placement for Web application middleware

• US 20070180083A1
• Filed: 01/31/2006
• Published: 08/02/2007
• Est. Priority Date: 01/31/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Steinder, Malgorzata, Pacifici, Giovanni, Tang, Chunqiang, Spreitzer, Michael, Adam, Constantin
• Granted Patent: US 7,496,667 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• 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

Abstract

A decentralized process to ensure the dynamic placement of applications on servers under two types of simultaneous resource requirements, those that are dependent on the loads placed on the applications and those that are independent. The demand (load) for applications changes over time and the goal is to satisfy all the demand while changing the solution (assignment of applications to servers) as little as possible.

Claims

1. A method for decentralized application resource allocation for a cluster of nodes, the method comprising:

receiving, at a local node, resource utilization data of applications from a subset of nodes in the node cluster, the local node including a current set of applications executing at the local node;

determining a new set of applications to execute at the local node which optimizes an objective function as computed locally by the local node based, at least in part, on the utilization data;

modifying which applications are executed at the local node according to the new set of executing applications; and

sending from the local node to the subset of nodes in the node cluster application execution changes between the new set of applications and the current set of applications at the local node.

2. The method of claim 1, wherein the receiving, determining, modifying and sending operations are performed independently and asynchronously at each node in the cluster of nodes.

3. The method of claim 1, further comprising utilizing an overlay construction algorithm to identify the subset of nodes for the local node, the subset of nodes being logical neighbors of the local node.

4. The method of claim 1, wherein receiving resource utilization data includes:

receiving a list of active applications from each node in the subset of nodes;

receiving a resource supply and demand for each active application in the list; and

receiving resource utilization data for each active application in the list.

5. The method of claim 1, wherein determining the new set of applications to execute at the local node further comprises:

defining a set of running applications executing on the local node;

sorting the running applications in increasing order of delivered density, wherein delivered density is defined as a ratio between an amount of CPU delivered to the application and a memory utilized by the application;

defining a set of standby applications, the standby applications including applications executing on the subset of nodes and not on the local node and applications not executing anywhere in the cluster of nodes;

filtering the set of standby applications by removing from the set of standby applications the applications for which there is no unsatisfied demand, the unsatisfied demand being defined as the difference between demand and supply for resources;

sorting the set of standby applications in decreasing order of unsatisfied density, the unsatisfied density defined as a ratio between the unsatisfied demand and the memory utilized by the application;

shifting load by attempting to assign as much load as possible from the local node to the subset of nodes;

building a plurality of local configurations by successively replacing applications from the sorted set of running applications with applications from the sorted set of standby applications; and

selecting from the local configurations an optimal configuration that maximizes CPU utilization on the local node.

6. The method of claim 1, wherein sending from the local node to the subset of nodes in the node cluster application execution changes includes using a gossip protocol, in which each node aggregates messages the node has received or originated during a predetermined interval of time, before sending the aggregated messages, inside a single message, to neighboring nodes.

7. The method of claim 1, further comprising:

locking, for each application that the local node starts and stops, all nodes located two logical hops away and preventing the nodes from starting and stopping the application; and

acquiring, from a designated node, a lock that prevents other nodes to start an application that currently is not running anywhere in the cluster of nodes.

8. A system for decentralized application resource allocation for a cluster of nodes, the system comprising:

a processor configured to execute a computer program;

a network interface coupled to the processor and configured to send and receive data over the computer network; and

a storage device embodying the computer program, the computer program including computer executable instructions configured for;

receiving, at a local node, resource utilization data of applications from a-subset of nodes in the node cluster, the local node including a current set of applications executing at the local node;

determining a new set of applications to execute at the local node which optimizes an objective function as computed locally by the local node based, at least in part, on the utilization data;

modifying which applications are executed at the local node according to the new set of executing applications; and

sending from the local node to the subset of nodes in the node cluster application execution changes between the new set of applications and the current set of applications at the local node.

9. The system of claim 8, wherein the receiving, determining, modifying and sending operations are performed independently and asynchronously at each node in the cluster of nodes.

10. The system of claim 8, further comprising computer executable instructions configured for utilizing an overlay construction algorithm to identify the subset of nodes for the local node, the subset of nodes being logical neighbors of the local node.

11. The system of claim 8, wherein receiving resource utilization data further comprises computer executable instructions configured for:

receiving a list of active applications from each node in the subset of nodes;

receiving a resource supply and demand for each active application in the list; and

receiving resource utilization data for each active application in the list.

12. The system of claim 8, wherein determining the new set of applications to execute at the local node further comprises computer executable instructions configured for:

defining a set of running applications executing on the local node;

sorting the running applications in increasing order of delivered density, wherein delivered density is defined as a ratio between an amount of CPU delivered to the application and a memory utilized by the application;

defining a set of standby applications, the standby applications including applications executing on the subset of nodes and not on the local node and applications not executing anywhere in the cluster of nodes;

filtering the set of standby applications by removing from the set of standby applications the applications for which there is no unsatisfied demand, the unsatisfied demand being defined as the difference between demand and supply for resources;

sorting the set of standby applications in decreasing order of unsatisfied density, the unsatisfied density defined as a ratio between the unsatisfied demand and the memory utilized by the application;

shifting load by attempting to assign as much load as possible from the local node to the subset of nodes;

building a plurality of local configurations by successively replacing applications from the sorted set of running applications with applications from the sorted set of standby applications; and

selecting from the local configurations an optimal configuration that maximizes CPU utilization on the local node.

13. The system of claim 8, wherein sending from the local node to the subset of nodes in the node cluster application execution changes includes computer executable instructions configured for using a gossip protocol, in which each node aggregates messages the node has received or originated during a predetermined interval of time, before sending the aggregated messages, inside a single message, to neighboring nodes.

14. The system of claim 8, further comprising computer executable instructions configured for:

locking, for each application that the local node starts and stops, all nodes located two logical hops away and preventing the nodes from starting and stopping the application; and

acquiring, from a designated node, a lock that prevents other nodes to start an application that currently is not running anywhere in the cluster of nodes.

15. A computer program product comprising a tangible media embodying computer program code, the computer program code comprising computer executable instructions configured for:

receiving, at a local node, resource utilization data of applications from a subset of nodes in the node cluster, the local node including a current set of applications executing at the local node;

determining a new set of applications to execute at the local node which optimizes an objective function as computed locally by the local node based, at least in part, on the utilization data;

modifying which applications are executed at the local node according to the new set of executing applications; and

sending from the local node to the subset of nodes in the node cluster application execution changes between the new set of applications and the current set of applications at the local node.

16. The computer program product of claim 15, wherein the receiving, determining, modifying and sending operations are performed independently and asynchronously at each node in the cluster of nodes.

17. The computer program product of claim 15, further comprising computer executable instructions configured for utilizing an overlay construction algorithm to identify the subset of nodes for the local node, the subset of nodes being logical neighbors of the local node.

18. The computer program product of claim 15, wherein receiving resource utilization data further comprising computer executable instructions configured for:

receiving a list of active applications from each node in the subset of nodes;

receiving a resource supply and demand for each active application in the list; and

receiving resource utilization data for each active application in the list.

19. The computer program product of claim 15, wherein determining the new set of applications to execute at the local node further comprising computer executable instructions configured for:

defining a set of running applications executing on the local node;

sorting the running applications in increasing order of delivered density, wherein delivered density is defined as a ratio between an amount of CPU delivered to the application and a memory utilized by the application;

defining a set of standby applications, the standby applications including applications executing on the subset of nodes and not on the local node and applications not executing anywhere in the cluster of nodes;

filtering the set of standby applications by removing from the set of standby applications the applications for which there is no unsatisfied demand, the unsatisfied demand being defined as the difference between demand and supply for resources;

sorting the set of standby applications in decreasing order of unsatisfied density, the unsatisfied density defined as a ratio between the unsatisfied demand and the memory utilized by the application;

shifting load by attempting to assign as much load as possible from the local node to the subset of nodes;

building a plurality of local configurations by successively replacing applications from the sorted set of running applications with applications from the sorted set of standby applications; and

selecting from the local configurations an optimal configuration that maximizes CPU utilization on the local node.

20. The computer program product of claim 15, wherein sending from the local node to the subset of nodes in the node cluster application execution changes includes computer executable instructions configured for using a gossip protocol, in which each node aggregates messages the node has received or originated during a predetermined interval of time, before sending the aggregated messages, inside a single message, to neighboring nodes.

21. The computer program product of claim 15, further comprising computer executable instructions configured for:

locking, for each application that the local node starts and stops, all nodes located two logical hops away and preventing the nodes from starting and stopping the application; and

acquiring, from a designated node, a lock that prevents other nodes to start an application that currently is not running anywhere in the cluster of nodes.