Method for decentralized load distribution in an event-driven system using localized migration between physically connected nodes and load exchange protocol preventing simultaneous migration of plurality of tasks to or from a same node
First Claim
1. A method of decentralized load distribution in an event-driven system, the method comprising the steps of:
- receiving a data flow to be processed by a plurality of tasks at a plurality of nodes in the event- driven system having stateful and stateless event processing components wherein the plurality of tasks are selected from the group consisting of hierarchical tasks, wherein a hierarchical task is a task that is dependent on the output of another task, nonhierarchical tasks, wherein a nonhierarchical task is a task that is not dependent on the output of another task, and mixtures thereof;
collecting statistics about the execution of each task hosted at each node;
creating a list of neighbor nodes, using the collected statistics, to which a task can be partially or wholly transferred;
selecting at least one target task at a source node for consideration to migrate, to a target node, the target node selected from the list of neighbor nodes, to distribute the system load of processing the at least one target task;
choosing the target node to which the at least one target task can be migrated wherein the target node meets predetermined criteria in terms of load distribution quality such that the target node must be physically connected to;
(a) the source node hosting the target task, (b) a parent node hosting a parent task of the target task, and (c) a child node hosting a child task of the target task; and
establishing a load exchange protocol at each node for governing the number of migrations of target tasks,wherein local decentralized load migrations lead to overall system load distribution in the event-driven system; and
wherein the load exchange protocol comprises all of the following;
(i) a decision to migrate the target task should not lead to oscillation such that a target task is migrated more than once to the target node and back to a node first hosting the target task;
(ii) no simultaneous migration of 2 or more tasks to a single target node in a single machine cycle shall occur;
(iii) no simultaneous migrations of 2 or more tasks from a node in a single machine cycle shall occur; and
(iv) an end result of target task migration should improve load distribution in some manner.
1 Assignment
0 Petitions
Accused Products
Abstract
A computer-implemented method, computer program product and computer readable storage medium directed to decentralized load distribution in an event-driven system. Included are receiving a data flow to be processed by a plurality of tasks at a plurality of nodes in the event-driven system having stateful and stateless event processing components, wherein the plurality of tasks are selected from the group consisting of hierarchical tasks (a task that is dependent on the output of another task), nonhierarchical tasks (a task that is not dependent on the output of another task) and mixtures thereof. Tasks are considered for migration to distribute the system load of processing tasks. The target node, to which the at least one target task is migrated, is chosen wherein the target node meets predetermined criteria in terms of load distribution quality. The computer-implemented method, computer program product and computer readable storage medium of the present invention may also include migrating tasks to target nodes to reduce cooling costs and selecting at least one node to go into quiescent mode.
-
Citations
21 Claims
-
1. A method of decentralized load distribution in an event-driven system, the method comprising the steps of:
-
receiving a data flow to be processed by a plurality of tasks at a plurality of nodes in the event- driven system having stateful and stateless event processing components wherein the plurality of tasks are selected from the group consisting of hierarchical tasks, wherein a hierarchical task is a task that is dependent on the output of another task, nonhierarchical tasks, wherein a nonhierarchical task is a task that is not dependent on the output of another task, and mixtures thereof; collecting statistics about the execution of each task hosted at each node; creating a list of neighbor nodes, using the collected statistics, to which a task can be partially or wholly transferred; selecting at least one target task at a source node for consideration to migrate, to a target node, the target node selected from the list of neighbor nodes, to distribute the system load of processing the at least one target task; choosing the target node to which the at least one target task can be migrated wherein the target node meets predetermined criteria in terms of load distribution quality such that the target node must be physically connected to;
(a) the source node hosting the target task, (b) a parent node hosting a parent task of the target task, and (c) a child node hosting a child task of the target task; andestablishing a load exchange protocol at each node for governing the number of migrations of target tasks, wherein local decentralized load migrations lead to overall system load distribution in the event-driven system; and wherein the load exchange protocol comprises all of the following; (i) a decision to migrate the target task should not lead to oscillation such that a target task is migrated more than once to the target node and back to a node first hosting the target task; (ii) no simultaneous migration of 2 or more tasks to a single target node in a single machine cycle shall occur; (iii) no simultaneous migrations of 2 or more tasks from a node in a single machine cycle shall occur; and (iv) an end result of target task migration should improve load distribution in some manner. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer program product comprising:
-
a nontransitory computer recordable storage medium having computer readable program code for decentralized load distribution in an event-driven system comprising; computer readable program code configured for receiving a data flow to be processed by a plurality of tasks at a plurality of nodes in the event-driven system having stateful and stateless event processing components, wherein the plurality of tasks are selected from the group consisting of hierarchical tasks, wherein a hierarchical task is a task that is dependent on the output of another task, nonhierarchical tasks, wherein a nonhierarchical task is a task that is not dependent on the output of another task, and mixtures thereof; computer readable program code configured for collecting statistics about each task hosted at each node; computer readable program code configured for creating a list of neighbor nodes, using the collected statistics, to which a task can be partially or wholly transferred; computer readable program code configured for selecting at least one target task at a source node for consideration to migrate, to a target node, the target node selected from the list of neighbor nodes, to distribute the system load of processing the at least one target task; computer readable program code configured the target node to which the at least one target task can be migrated wherein the target node meets predetermined criteria in terms of load distribution quality such that the target node must be physically connected to;
(a) the source node hosting the target task, (b) a parent node hosting a parent task of the target task, and (c) a child node hosting a child task of the target task; andcomputer readable program code configured for establishing a load exchange protocol at each node for governing the number of migrations of target tasks, wherein decentralized load migrations lead to overall system load distribution in the event-driven system; and wherein the load exchange protocol comprises all of the following; (i) a decision to migrate the target task should not lead to oscillation such that a target task is migrated more than once to the target node and back to a node first hosting the target task; (ii) no simultaneous migration of 2 or more tasks to a single target node in a single machine cycle shall occur; (iii) no simultaneous migrations of 2 or more tasks from a node in a single machine cycle shall occur; and (iv) an end result of target task migration should improve load distribution in some manner. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A nontransitory computer readable storage medium storing instructions that, when executed by a computer, causes the computer to perform a method of decentralized load distribution in an event-driven system, the method comprising the steps of:
-
receiving a data flow to be processed by a plurality of tasks at a plurality of nodes in the event- driven system having stateful and stateless event processing components, wherein the plurality of tasks are selected from the group consisting of hierarchical tasks, wherein a hierarchical task is a task that is dependent on the output of another task, nonhierarchical tasks, wherein a nonhierarchical task is a task that is not dependent on the output of another task, and mixtures thereof; collecting statistics about each task hosted at each node; creating a list of neighbor nodes, using the collected statistics, to which a task can be partially or wholly transferred; selecting at least one target task at a source node for consideration to migrate, to a target node, the target node selected from the list of neighbor nodes, to distribute the system load of processing the at least one target task; choosing the target node to which the at least one target task can be migrated wherein the target node meets predetermined criteria in terms of load distribution quality such that the target node must be physically connected to;
(a) the source node hosting the target task, (b) a parent node hosting a parent task of the target task, and (c) a child node hosting a child task of the target task; andestablishing a load exchange protocol at each node for governing the number of migrations of target tasks, wherein local decentralized load migrations lead to overall system load distribution in the event-driven system; and wherein the load exchange protocol comprises all of the following; (i) a decision to migrate the target task should not lead to oscillation such that a target task is migrated more than once to the target node and back to a node first hosting the target task; (ii) no simultaneous migration of 2 or more tasks to a single target node in a single machine cycle shall occur; (iii) no simultaneous migrations of 2 or more tasks from a node in a single machine cycle shall occur; and (iv) an end result of target task migration should improve load distribution in some manner. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
Specification