Dynamic and evolutionary placement in an event-driven component-oriented network data processing system

• US 7,979,578 B2
• Filed: 09/02/2009
• Issued: 07/12/2011
• Est. Priority Date: 09/02/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lakshmanan, Geetika T., Strom, Robert E.
• Primary Examiner(s): Nguyen; Phuoc
• Application Number:
  US12/552,565
• Publication Number:
  US 20110055426A1
• Time in Patent Office: 678 Days
• Field of Search: 709/223, 709/224, 709/238, 709/239
• US Class Current: 709/238
• 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

Method, system and computer readable program code for dynamic and evolutionary component placement in an event processing system having producers, consumers, a plurality of nodes between the producers and the consumers, and a flow graph representing operator components to be executed between the producers and the consumers. A description of a change to the system is received. At each node, next-hop neighbor nodes for each consumer are identified. A routing value is assigned to each next-hop neighbor node for each consumer and the routing values are updated according to an update rule that represents a chromosome in a routing probe. The update rule in a routing probe is selectively updated from a plurality of update rules at the consumer. The probability of selecting a particular update rule is reinforced or decayed based on the success of an update rule in allowing routing probes to create many different efficient routes. At each producer, nests of scouting probes are adaptively selected from an available set of nests and dispatched to execute hypothetical placement of a query by an independent agent called a “leader”. A placement of the operator components that minimizes performance cost of the system relative to the hypothetical placement is selected. Each scouting probe contains chromosomes that guide placement. Scouting probes in two different nests have different chromosomes. The performance cost of the hypothetical changed placement is evaluated and the performance evaluation is used to evolve at least one chromosome of a scouting ant in each nest.

Claims

1. A computer implemented method for dynamic and evolutionary component placement in an event processing system that has at least one producer, at least one consumer, a plurality of nodes and a plurality of links between the at least one producer and the at least one consumer, and a flow graph that represents a plurality of operator components to be executed between the at least one producer and the at least one consumer, the computer implemented method running, in a decentralized manner without requiring any global state or centralized controller, on the plurality of nodes of the event processing system, comprising:

receiving a description of at least one change to the event processing system;

identifying, at each node of the plurality of nodes, a plurality of next-hop neighbor nodes for each at least one consumer;

assigning a routing value to each of the identified plurality of next-hop neighbor nodes for each at least one consumer to form routing values, and the routing values are updated according to an update rule where the update rule is adaptively selected in response to current network conditions from among a plurality of update rules available at the consumer, and the probability of selecting an update rule depends on the success of the update rule in allowing routing probes to create many different and efficient routes;

estimating, using the routing values in a context of the at least one change to the event processing system, a performance cost of the event processing system based on at least one hypothetical changed placement of the operator components of the flow graph at nodes along at least one path from a producer to a consumer through the next-hop neighbor nodes for each at least one consumer;

autonomously orchestrating, from each producer, hypothetical placement and evaluating the performance cost of the at least one hypothetical changed placement and on the basis of the evaluation autonomously evolving at least one parameter with respect to the at least one hypothetical placement in response to changes in the data, network or other characteristics to improve the performance cost of the at least one hypothetical placement; and

responsive to the autonomously orchestrating and evaluating hypothetical placement, selecting a changed placement of the operator components of the flow graph that minimizes the performance cost of the event processing system relative to the at least one hypothetical changed placement.

2. A computer implemented method for dynamic and evolutionary component placement in an event processing system that has at least one producer, at least one consumer, a plurality of nodes and a plurality of links between the at least one producer and the at least one consumer, a plurality of routing probes and scouting probes, and a flow graph that represents a plurality of operator components to be executed between the at least one producer and the at least one consumer, the computer implemented method running, in a decentralized manner without requiring any global state or centralized controller, on the plurality of nodes of the event processing system, comprising:

receiving a description of at least one change to the event processing system;

identifying, at each node of the plurality of nodes, a plurality of next-hop neighbor nodes for each at least one consumer;

assigning a routing value to each of the identified plurality of next-hop neighbor nodes for each at least one consumer to form routing values, the routing values provided by at least one routing probe and are updated according to an update rule, and where the update rule is adaptively selected in response to current network, data and other conditions from among a plurality of update rules available at the consumer, and the probability of selecting an update rule depends on the success of the update rule in allowing routing probes to create many different and efficient routes;

estimating, using the routing values in a context of the at least one change to the event processing system, a performance cost of the event processing system based on at least one hypothetical changed placement of the operator components of the flow graph at nodes along at least one path from a producer to a consumer through the next-hop neighbor nodes for each at least one consumer;

autonomously dispatching, from each producer, diverse scouting probes with different parameters that conduct the hypothetical placement and autonomously evaluating the success of these parameters with respect to the scouting probes and evolving at least one parameter with respect to the scouting probes that conduct the at least one hypothetical placement in response to changes in the data, network or other characteristics in order to obtain scouting probes having the evolved at least one parameter that improve the performance cost of placement in the event processing system; and

responsive to the autonomously orchestrating and evaluating, selecting a changed placement of the operator components of the flow graph that minimizes the performance cost of the event processing system relative to the at least one hypothetical changed placement.

3. The computer implemented method of claim 2 wherein the routing values provided by the at least one routing probe are assigned and updated by a plurality of update rules available at the at least one consumer.

4. The computer implemented method of claim 2 further comprising autonomously evaluating at a consumer the success of routing probes that provide the routing values and selecting routing update rules for the routing probes from one or more routing update rules that lead to greater success in placement of components than other rules given current network, data and other conditions.

5. The computer implemented method of claim 4 wherein the success of routing probes is measured in a decentralized manner at a consumer that receives the routing probes by factors that include but are not limited to counting the number of scouts that reach the at least one consumer having hypothetically placed all the operator components of the flow graph assigned to them and by counting the number of different paths that scouts take.

6. The computer implemented method of claim 2 wherein the effectiveness of the scouting probes in hypothetically placing all the operator components of the flow graph assigned to them is measured by a fitness score that is computed at each producer that released the scouting probes.

7. The computer implemented method of claim 6 wherein the fitness score is a weighted combination of factors that represent the effectiveness of achieving placement success given current network and data conditions and the current flow graph by a scouting probe that include but are not limited to (a) success in placing all the operator components of the flow graph assigned to the scouting probe, (b) the performance cost of placement as defined by the objective function specified by the application and (c) time taken to place the operator components of the flow graph.

8. The computer implemented method of claim 2 wherein the scouting probes contain at least one parameter defined as a chromosome in the scouting probes.

9. The computer implemented method of claim 2 wherein the scouting probes contain at least one parameter which is autonomously initialized and adaptively updated from time to time in response to changes in the network, data and other characteristics.

10. The computer implemented method of claim 2 wherein the scouting probes contain at least one parameter and two scouting probes may be combined to result in a third scouting probe wherein the at least one parameter of one of the two scouting probes is a first parameter and the at least one parameter of the other of the two scouting probes is a second parameter and the at least one parameter of the third scouting probe is a third parameter, the first and second parameters being combined to form the third parameter.

11. The computer implemented method of claim 9 wherein the third parameter has similarity in values with the first and second parameters by being identical or some derived result of the combination of the first and second.

12. The computer implemented method of claim 9 wherein the third parameter has no similarity in values with the first and second parameters and is computed randomly.

13. The computer implemented method of claim 8 wherein the parameters are selected from the group consisting of a threshold of acceptable computational load on a one node (load threshold), limit on the number of operator components in a query to hypothetically place on one node, a threshold which if exceeded allows the operator components of the flow graph to be migrated from the node where they are currently hosted to a new node in the network (load migration factor) and combinations thereof.

14. The computer implemented method of claim 2 wherein the update rule is embedded in the at least one routing probe.

15. A computer program product, comprising:

a tangible computer storage medium having computer readable program code for dynamic and evolutionary component placement in an event processing system that has at least one producer, at least one consumer, a plurality of nodes and a plurality of links between the at least one producer and the at least one consumer, a plurality of routing probes and scouting probes, and a flow graph that represents a plurality of operator components to be executed between the at least one producer and the at least one consumer, the computer implemented method running, in a decentralized manner without requiring any global state or centralized controller, on the plurality of nodes of the event processing system, the computer program product comprising;

computer readable program code configured for receiving a description of at least one change to the event processing system;

computer readable program code configured for identifying, at each node of the plurality of nodes, a plurality of next-hop neighbor nodes for each at least one consumer;

computer readable program code configured for assigning a routing value to each of the identified plurality of next-hop neighbor nodes for each at least one consumer to form routing values, the routing values provided by at least one routing probe and are updated according to an update rule, and where the update rule of routing values is adaptively selected in response to current network, data and other conditions from among a plurality of update rules available at the consumer;

computer readable program code configured for estimating, using the routing values in a context of the at least one change to the event processing system, a performance cost of the event processing system based on at least one hypothetical changed placement of the operator components of the flow graph at nodes along at least one path from a producer to a consumer through the next-hop neighbor nodes for each at least one consumer;

computer readable program code configured for autonomously dispatching, from each producer, diverse scouting probes with different parameters that conduct the hypothetical placement and autonomously evaluating the success of these parameters with respect to the scouting probes and evolving at least one parameter with respect to the scouting probes that conduct the hypothetical placement in response to changes in the data, network or other characteristics in order to obtain scouting probes having the evolved at least one parameter that improve the performance cost of placement in the event processing system; and

responsive to the autonomously orchestrating and evaluating, computer readable program code configured for selecting a changed placement of the operator components of the flow graph that minimizes the performance cost of the event processing system relative to the at least one hypothetical changed placement.

16. The computer program product of claim 15 further comprising computer readable program code configured for autonomously evaluating at a consumer the success of routing probes that provide the routing values and selecting routing update rules for the routing probes from one or more routing update rules that lead to greater success in placement of components than other rules given current network, data and other conditions.

17. The computer program product of claim 16 wherein the success of routing probes is measured in a decentralized manner at a consumer that receives the routing probes by factors that include but are not limited to counting the number of scouts that reach the at least one consumer having hypothetically placed all the operator components of the flow graph assigned to them and by counting the number of different paths that scouts take.

18. The computer program product of claim 15 wherein the effectiveness of the scouting probes in hypothetically placing all the operator components of the flow graph assigned to them is measured by a fitness score that is computed at each producer that released the scouting probes.

19. The computer program product of claim 18 wherein the fitness score is a weighted combination of factors that represent the effectiveness of achieving placement success given current network and data conditions and the current flow graph by a scouting probe that include but are not limited to (a) success in placing all the operator components of the flow graph assigned to the scouting probe, (b) the performance cost of placement as defined by the objective function specified by the application and (c) time taken to place the operator components of the flow graph.

20. The computer program product of claim 15 wherein the scouting probes contain at least one parameter embedded in the scouting probes.

21. The computer program product of claim 15 wherein the scouting probes contain at least one parameter which is autonomously initialized and adaptively updated from time to time in response to changes in the network, data and other characteristics.

22. The computer program product of claim 15 wherein the scouting probes contain at least one parameter and two scouting probes may be combined to result in a third scouting probe wherein the at least one parameter of one of the two scouting probes is a first parameter and the at least one parameter of the other of the two scouting probes is a second parameter and the at least one parameter of the third scouting probe is a third parameter, the first and second parameters being combined to form the third parameter.

23. The computer program product of claim 22 wherein the third parameter has similarity in values with the first and second parameters by being identical or some derived result of the combination of the first and second.

24. The computer program product of claim 22 wherein the third parameter has no similarity in values with the first and second parameters and is computed randomly.

25. The computer program product of claim 21 wherein the parameters are selected from the group consisting of a threshold of acceptable computational load on a one node (load threshold), limit on the number of operator components in a query to hypothetically place on one node, a threshold which if exceeded allows the operator components of the flow graph to be migrated from the node where they are currently hosted to a new node in the network (load migration factor) and combinations thereof.

26. The computer program product of claim 15 wherein the update rule is embedded in the at least one routing probe.

27. A dynamic and evolutionary component placement system in an event processing system that has at least one producer, at least one consumer, a plurality of nodes and a plurality of links between the at least one producer and the at least one consumer, a plurality of routing probes and scouting probes, and a flow graph that represents a plurality of operator components to be executed between the at least one producer and the at least one consumer, the computer implemented method running, in a decentralized manner without requiring any global state or centralized controller, on the plurality of nodes of the event processing system, the dynamic and evolutionary component placement system comprising:

a receiver for receiving a description of at least one change to the event processing system;

an identifier for identifying, at each node of the plurality of nodes, a plurality of next-hop neighbor nodes for each at least one consumer;

an assignor for assigning a routing value to each of the identified plurality of next-hop neighbor nodes for each at least one consumer to form routing values, the routing values provided by at least one routing probe and are updated according to an update rule, and where the update rule of routing values is adaptively selected in response to current network, data and other conditions from among a plurality of update rules available at the consumer;

an estimator for estimating, using the routing values in a context of the at least one change to the event processing system, a performance cost of the event processing system based on at least one hypothetical changed placement of the operator components of the flow graph at nodes along at least one path from a producer to a consumer through the next-hop neighbor nodes for each at least one consumer;

a dispatcher for autonomously dispatching, from each producer, diverse scouting probes with different parameters that conduct the hypothetical placement and autonomously evaluating the success of these parameters with respect to the scouting probes and evolving at least one parameter with respect to the scouting probes that conduct the hypothetical placement in response to changes in the data, network or other characteristics in order to obtain scouting probes having the evolved at least one parameter that improve the performance cost of placement in the event processing system; and

responsive to the autonomously orchestrating and evaluating, a selector for selecting a changed placement of the operator components of the flow graph that minimizes the performance cost of the event processing system relative to the at least one hypothetical changed placement.