Continuous flow compute point based data processing

• US 6,654,907 B2
• Filed: 12/05/2000
• Issued: 11/25/2003
• Est. Priority Date: 12/06/1999
• Status: Expired due to Term

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Software Corporation
• Inventors: Shapiro, Richard A., Kukolich, Stephen A., Stanfill, Craig W.
• Primary Examiner(s): BADERMAN, SCOTT T
• Application Number:
  US09/731,234
• Publication Number:
  US 20010042224A1
• Time in Patent Office: 1,085 Days
• Field of Search: 714/16, 714/17, 714/51, 712/221, 712/228
• US Class Current: 714/16
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency

Abstract

A data processing system and method that provides two processes, checkpointing and compute point propagation, and permits a continuous flow of data processing by allowing each process to (1) return to normal operation after checkpointing or (2) respond to receipt of a compute point indicator, independently of the time required by other processes for similar responsive actions. Checkpointing makes use of a command message from a checkpoint processor that sequentially propagates through a process stage from data sources through processes to data sinks, triggering each process to checkpoint its state and then pass on a checkpointing message to connected “downstream” processes. A compute point indicator marks blocks of records that should be processed as a group within each process. A compute point indicator is triggered and sequentially propagates through a process stage from data sources through processes to data sinks without external control. Compute point indicators also effectively self-synchronize multiple data flows without external control. Use of compute point indicators rather than checkpoints avoids the time delay that saving state imposes, while permitting a continuous flow of data processing, including outputting results.

Claims

1. A method for initiating processing of blocks of data within at least one flow of data input to a graph having a plurality of process stages, including at least one subscriber process stage, at least one publisher process stage, and optionally at least one intermediate process stage, the method including:

generating a compute point indicator in response to a trigger event;

propagating the compute point indicator through the graph, from each subscriber process stage through any intermediate process stages to each publisher process stage, as part of the flow of data;

for each process stage, processing a current block of data associated with the process stage in response to receipt by the process stage of at least one compute point indicator from an immediately previous process stage associated with the process stage.

2. The method of claim 1, wherein for each process stage, processing a current block of data associated with the process stage is in response to receipt by the process stage of a compute point indicator from each immediately previous process stage associated with the process stage.

3. The method of claim 1, wherein the trigger event occurs periodically.

4. The method of claim 1, wherein the trigger event is based on an external stimulus.

5. The method of claim 1, wherein the trigger event is based on occurrence of selected data values within or derived from incoming data records in at least one flow of data being processed.

6. The method of claim 1, further including coupling two graphs through a first-in, first-out graph queue.

7. The method of claim 1, further including creating a checkpoint for the graph in response to a checkpoint trigger event.

8. The method of claim 7, further including, for at least one publisher process stage, keeping track of which data has been published by such publisher process stage in response to receipt by such publisher process stage of at least one compute point indicator, so that data is not republished by such publisher process stage if processing restarts from a checkpoint.

9. The method of claim 1, further including automatically synchronizing blocks of data within two or more flows of data input to one of the process stages without the need for communication between process stages or with a controller.

10. A computer program, stored on a computer-readable medium, for initiating processing of blocks of data within at least one flow of data input to a graph having a plurality of process stages, including at least one subscriber process stage, at least one publisher process stage, and optionally at least one intermediate process stage, the computer program comprising instructions for causing a computer to:

generate a compute point indicator in response to a trigger event;

propagate the compute point indicator through the graph, from each subscriber process stage through any intermediate process stages to each publisher process stage, as part of the flow of data;

for each process stage, process a current block of data associated with the process stage in response to receipt by the process stage of at least one compute point indicator from an immediately previous process stage associated with the process stage.

11. The computer program of claim 10, wherein for each process stage, the instructions for causing the computer to process a current block of data associated with the process stage includes instructions for causing the computer to perform such process in response to receipt by the process stage of a compute point indicator from each immediately previous process stage associated with the process stage.

12. The computer program of claim 10, wherein the trigger event occurs periodically.

13. The computer program of claim 10, wherein the trigger event is based on an external stimulus.

14. The computer program of claim 10, wherein the trigger event is based on occurrence of selected data values within or derived from incoming data records in at least one flow of data being processed.

15. The computer program of claim 10, further including instructions for causing the computer to coupled two graphs through a first-in, first-out graph queue.

16. The computer program of claim 10, further including instructions for causing the computer to create a checkpoint for the graph in response to a checkpoint trigger event.

17. The computer program of claim 16, further including, for at least one publisher process stage, instructions for causing the computer to keep track of which data has been published by such publisher process stage in response to receipt by such publisher process stage of at least one compute point indicator, so that data is not republished by such publisher process stage if processing restarts from a checkpoint.

18. The computer program of claim 10, further including instructions for causing the computer to automatically synchronize blocks of data within two or more flows of data input to one of the process stages without the need for communication between process stages or with a controller.

19. A system for initiating processing of blocks of data within at least one flow of data input to a graph having a plurality of process stages, including at least one subscriber process stage, at least one publisher process stage, and optionally at least one intermediate process stage, the system including:

means for generating a compute point indicator in response to a trigger event;

means for propagating the compute point indicator through the graph, from each subscriber process stage through any intermediate process stages to each publisher process stage, as part of the flow of data;

for each process stage, means for processing a current block of data associated with the process stage in response to receipt by the process stage of at least one compute point indicator from an immediately previous process stage associated with the process stage.

20. The system of claim 19, wherein for each process stage, the means for processing a current block of data associated with the process stage includes means for performing such processing in response to receipt by the process stage of a compute point indicator from each immediately previous process stage associated with the process stage.

21. The system of claim 19, wherein the trigger event occurs periodically.

22. The system of claim 19, wherein the trigger event is based on an external stimulus.

23. The system of claim 19, wherein the trigger event is based on occurrence of selected data values within or derived from incoming data records in at least one flow of data being processed.

24. The system of claim 19, further including means for coupling two graphs through a first-in, first-out graph queue.

25. The system of claim 19, further including means for creating a checkpoint for the graph in response to a checkpoint trigger event.

26. The system of claim 25, further including, for at least one publisher process stage, means for keeping track of which data has been published by such publisher process stage in response to receipt by such publisher process stage of at least one compute point indicator, so that data is not republished by such publisher process stage if processing restarts from a checkpoint.

27. The system of claim 19, further including means for automatically synchronizing blocks of data within two or more flows of data input to one of the process stages without the need for communication between process stages or with a controller.