System and Method for Scalable Processing of Multi-Way Data Stream Correlations

• US 20090248749A1
• Filed: 06/04/2009
• Published: 10/01/2009
• Est. Priority Date: 05/04/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Haixun, Gu, Xiaohui, Yu, Philip Shi-lung
• Granted Patent: US 7,890,649 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A computer implemented method, apparatus, and computer usable program code for processing multi-way stream correlations. Stream data are received for correlation. A task is formed for continuously partitioning a multi-way stream correlation workload into smaller workload pieces. Each of the smaller workload pieces may be processed by a single host. The stream data are sent to different hosts for correlation processing.

Claims

1. A computer implemented method for processing multi-way stream correlations, the computer implemented method comprising:

receiving a set of input data streams;

aligning tuples of each input data stream of the set of input data streams with tuples of a master stream according to timestamps, to form aligned tuples;

splitting the set of input data streams into a plurality of sets of segments, wherein each set of segments of the plurality of sets of segments corresponds to a predetermined amount of time, wherein each segment of a set of segments of the plurality of sets of segments comprises the aligned tuples that arrived within the predetermined amount of time; and

sending each set of segments of the plurality of sets of segments to a different host in a set of hosts for join processing, wherein the join processing is performed on the aligned tuples that arrived within the predetermined amount of time.

3. The computer implemented method of claim 1, wherein the splitting step further comprises:

wherein each set of segments of the plurality of sets of segments comprises one segment from each input data stream of the set of input data streams.

4. The computer implemented method of claim 1, wherein the multi-way stream correlations are implemented by a sliding-window join over the aligned tuples that arrived within the predetermined amount of time.

5. The computer implemented method of claim 1, further comprising:

identifying correlation constraints;

calculating a routing path for each set of segments of the plurality of sets of segments for ensuring that the correlation constraints are satisfied, a workload of the different host in the set of hosts is balanced, and replication overhead of the plurality of sets of segments is minimized.

6. The computer implemented method of claim 1, further comprising:

selecting an input data stream of the set of input data streams with a highest rate of data flow to be designated as the master stream and denoting other input data streams of the set of input data streams as slave streams, wherein each input data stream of the set of input data streams has a variable rate of data flow;

partitioning the master stream into disjoint segments; and

partitioning slave streams into overlapped segments to meet correlation constraints.

7. The computer implemented method of claim 6, wherein the selecting step is dynamically changed during runtime further comprising:

monitoring a rate of data flow for each input data stream of the set of input data streams;

detecting a change in the rate of data flow for an input data stream of the set of input data streams;

responsive to detecting a change in the rate of data flow for an input data stream of the set of input data streams, determining whether the rate of data flow of the master stream is the highest rate of data flow of the input data streams in the set of input data streams; and

responsive to a determination that the rate of data flow of the master stream is not the highest rate of data flow of the input data streams in the set of input data streams, making the input data stream with the highest rate of data flow of the input data streams in the set of input data streams the master stream.

8. The computer implemented method of claim 7, wherein the selecting step further comprises:

responsive to the master stream being slower than any of the other data input streams of the set of input data streams, triggering a stream role switch for selecting the input data stream with the highest rate of data flow as the master stream and denoting the other data input streams of the set of input data streams as the slave streams; and

employing a transition phase to achieve the stream role switch according to the correlation constraints.

9. The computer implemented method of claim 6, wherein the partitioning the master stream into disjoint segments step is for adjusting a segment length of the disjoint segments and further comprises:

triggering segment adaptation when system conditions change;

performing a sampling-based profiling process to search for a new segment length.

10. The computer implemented method of claim 1, further comprising:

determining a join order for each set of segments of the plurality of sets of segments to divide the join processing of the multi-way stream join computation into multiple hops;

looking up locations of the aligned tuples at each hop; and

computing a minimum host set covering all the aligned tuples at each hop.

11. The computer implemented method of claim 10, wherein the join order is determined by observed join selectivity between different input data streams.

12. The computer implemented method of claim 10, wherein the looking up step is performed using a routing table, wherein the routing table includes placement information of the aligned tuples in a sliding-windows of different input data streams.

13. The computer implemented method of claim 10, wherein the computing step further comprises:

considering a host set selection by a previous hop; and

reusing the host set selection by the previous hop for minimizing intermediate result transferring.

2. (canceled)

14-20. -20. (canceled)

21. A computer program product, in a computer readable storage medium, for processing multi-way stream correlations, the computer program product comprising:

computer usable program code stored in the computer readable storage medium, wherein the computer usable program code is adapted to cause a processor in a computer to perform steps comprising;

receiving a set of input data streams, wherein each input data stream of the set of input data streams has a variable rate of data flow;

selecting an input data stream of the set of input data streams with a highest rate of data flow to be designated as a master stream, wherein the designation of the master stream changes based on the variable rate of data flow of each input data stream of the set of input data streams;

aligning tuples of each input data stream of the set of input data streams with tuples of the master stream according to timestamps, to form aligned tuples;

splitting, continuously, the set of input data streams into a plurality of sets of segments, wherein each set of segments of the plurality of sets of segments comprises one segment from each input data stream of the set of input data streams, wherein each set of segments of the plurality of sets of segments corresponds to a predetermined amount of time, wherein each segment of a set of segments of the plurality of sets of segments comprises the aligned tuples that arrived within the predetermined amount of time; and

sending each set of segments of the plurality of sets of segments to a different host in a set of hosts for join processing, wherein the join processing is performed on the aligned tuples that arrived within the predetermined amount of time.

22. The computer program product of claim 21, wherein the computer usable program code is adapted to cause the processor in the computer to perform the steps further comprising:

monitoring a rate of data flow for each input data stream of the set of input data streams;

detecting a change in the rate of data flow for an input data stream of the set of input data streams;

responsive to detecting a change in the rate of data flow for an input data stream of the set of input data streams, determining whether the rate of data flow of the master stream is the highest rate of data flow of the input data streams in the set of input data streams; and

responsive to a determination that the rate of data flow of the master stream is not the highest rate of data flow of the input data streams in the set of input data streams, making the input data stream with the highest rate of data flow of the input data streams in the set of input data streams the master stream.

23. A computer program product, in a computer readable storage medium, for processing multi-way stream correlations, the computer program product comprising:

computer usable program code stored in the computer readable storage medium, wherein the computer usable program code is adapted to cause a processor in a computer to perform steps comprising;

receiving a set of input data streams, wherein each input data stream of the set of input data streams has a variable rate of data flow;

selecting an input data stream of the set of input data streams with a highest rate of data flow to be designated as a master stream, wherein the designation of the master stream changes based on the variable rate of data flow of each input data stream of the set of input data streams;

aligning tuples of each input data stream of the set of input data streams with tuples of the master stream according to timestamps, to form aligned tuples;

splitting, continuously, the set of input data streams into a set of segments, wherein each segment of the set of segments comprises the aligned tuples that arrived within a predetermined amount of time for a specific input data stream;

determining a routing path for a segment of the set of segments based on routing paths of previous segments that comprised tuples aligned with the aligned tuples in the segment, wherein the routing path for the segment denotes a set of hosts that the segment needs to be sent to in order to produce a join result, wherein a multi-way stream join computation is split into multiple smaller join operator computations that are executed on the set of hosts;

storing the routing path for the segment in a data structure;

adding the routing path to the segment; and

sending each segment of the set of segments to the set of hosts in the routing path for join processing, wherein intermediate join results of the join result are routed across the set of hosts, and wherein the aligned tuples of each input data stream of the set of input data streams are routed separately.

24. The computer program product of claim 23, wherein the computer usable program code is adapted to cause the processor in the computer to perform the steps further comprising:

monitoring a rate of data flow for each input data stream of the set of input data streams;

detecting a change in the rate of data flow for an input data stream of the set of input data streams;

responsive to detecting a change in the rate of data flow for an input data stream of the set of input data streams, determining whether the rate of data flow of the master stream is the highest rate of data flow of the input data streams in the set of input data streams; and

responsive to a determination that the rate of data flow of the master stream is not the highest rate of data flow of the input data streams in the set of input data streams, making the input data stream with the highest rate of data flow of the input data streams in the set of input data streams the master stream.

25. The computer program product of claim 23, wherein the computer usable program code is adapted to cause the processor in the computer to perform the steps further comprising:

determining a join order for the segment to divide the join processing of the multi-way stream join computation into multiple hops;

looking up locations of the aligned tuples at each hop; and

computing a minimum host set covering all the aligned tuples at each hop.

26. The computer program product of claim 25, wherein the join order is determined by observed join selectivity between different input data streams.

27. An apparatus for processing multi-way stream correlations, the apparatus comprising:

a processor, and instructions stored in a memory, wherein the instructions are adapted to cause the processor to perform a plurality of steps comprising;

receiving a set of input data streams, wherein each input data stream of the set of input data streams has a variable rate of data flow;

selecting an input data stream of the set of input data streams with a highest rate of data flow to be designated as a master stream, wherein the designation of the master stream changes based on the variable rate of data flow of each input data stream of the set of input data streams;

aligning tuples of each input data stream of the set of input data streams with tuples of the master stream according to timestamps, to form aligned tuples;

splitting, continuously, the set of input data streams into a set of segments, wherein each segment of the set of segments comprises the aligned tuples that arrived within a predetermined amount of time for a specific input data stream;

determining a routing path for a segment of the set of segments based on routing paths of previous segments that comprised tuples aligned with the aligned tuples in the segment, wherein the routing path for the segment denotes a set of hosts that the segment needs to be sent to in order to produce a join result, wherein a multi-way stream join computation is split into multiple smaller join operator computations that are executed on the set of hosts;

storing the routing path for the segment in a data structure;

adding the routing path to the segment; and

sending each segment of the set of segments to the set of hosts in the routing path for join processing, wherein intermediate join results of the join result are routed across the set of hosts, and wherein the aligned tuples of each input data stream of the set of input data streams are routed separately.

28. The apparatus of claim 27, wherein the instructions are adapted to cause the processor to perform the plurality of steps further comprising:

monitoring a rate of data flow for each input data stream of the set of input data streams;

detecting a change in the rate of data flow for an input data stream of the set of input data streams;

responsive to detecting a change in the rate of data flow for an input data stream of the set of input data streams, determining whether the rate of data flow of the master stream is the highest rate of data flow of the input data streams in the set of input data streams; and

responsive to a determination that the rate of data flow of the master stream is not the highest rate of data flow of the input data streams in the set of input data streams, making the input data stream with the highest rate of data flow of the input data streams in the set of input data streams the master stream.

29. The apparatus of claim 27, wherein the instructions are adapted to cause the processor to perform the plurality of steps further comprising:

determining a join order for the segment to divide the join processing of the multi-way stream join computation into multiple hops;

looking up locations of the aligned tuples at each hop; and

computing a minimum host set covering all the aligned tuples at each hop.

30. The apparatus of claim 29, wherein the join order is determined by observed join selectivity between different input data streams.