System and method for executing, tracking and recovering long running computations

• US 5,524,241 A
• Filed: 04/18/1995
• Issued: 06/04/1996
• Est. Priority Date: 02/04/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Ghoneimy, Adel, Kleissner, Karl, Hsu, Meichun
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US08/426,415
• Time in Patent Office: 413 Days
• Field of Search: 395/600, 395/182.13, 395/182.18
• US Class Current: 707/676
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 2201/87 Monitoring of transactions
• CPC Class Codes: G06F 9/4494 data driven
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A transaction description database represents long running computations as a flow or set of computational steps with data arcs therebetween. The description database defines each step'"'"'s input and output signals, input condition criteria for creating an instance of the step, an application program associated with the step, and criteria for selecting a resource to execute the step. A flow controller controls the process of executing instances of each defined type of long running transaction. Execution of a long running transaction begins when a corresponding set of externally generated input event signals are received by the flow controller. During execution of a long running transaction, each step of the transaction is instantiated only when a sufficient set of input signals is received to execute that step. At that point an instance of the required type of step is created and then executed by a selected resource. After termination of a step, output signals from the step are converted into input event signals for other steps in the long running transaction in accordance with data stored in the transaction description database. Each step executes an application program and is treated as an individual computation insofar as durable storage of its computational results. Log records are durably stored upon instantiation, execution and termination of each step of a long running transaction, and output event signals are also logged, thereby durably storing sufficient data to recover a long running transaction with virtually no loss of the work that was accomplished prior to a system failure.

Claims

1. In a distributed computer system having a plurality of interconnected computers, a long running transaction management apparatus comprising:

A) flow description means for storing flow description data representing each of a number of types of long running transactions as a flow comprising a set of steps with arcs therebetween, each said step comprising a respective computer-executable application routine and each said arc comprising a respective data signal path, said flow description data specifying input condition criteria for starting execution of each said step upon occurrence of a specified number of specified input events and resource selecting criteria for selecting a resource to execute each said step, said flow description data thereby providing a respective template corresponding to each said transaction type;

B) a flow controller coupled to said flow description means for creating and executing a number of instances of transactions corresponding to said transaction types in accordance with the corresponding templates stored in said flow description means, said flow controller operable (i) to select dynamically a respective resource for performing the execution of said step in accordance with the resource selecting criteria stored in said flow description means, said flow controller selecting said resource after executing any and all steps of said transaction instance that said flow description data indicates as being prior to said step, and (ii) to initiate execution of each step in each of said instances of said transactions when said input condition criteria for said step as stored in said flow description means are satisfied; and

C) means for durably storing status information and a number of results from each said executed step for use by said flow controller in tracking execution and in recovery following interruptions in execution of instances of said long running transactions, whereby said flow controller can cause reinitiation of execution following any interruption of the execution of said instances of said long-running transactions.

2. The long running transaction management system of claim 1, wherein

said flow description means further includes (including) output event table means for defining a number of output event signals generated by each step of each long running transaction, port table means for defining a number of input ports for each step of each long running transaction, and arc table means for storing data denoting for each defined output event signal a destination step and said destination step'"'"'s input port to which said output event signal should be sent;

said flow controller means further includes (A) step termination means for receiving a number of output parameters generated by executed steps of said created instances of said long running transactions and generating a set of corresponding output event signals in accordance with said output event table means, and (B) arc resolution means for routing said output event signals to input ports of corresponding steps of said created instances of long running transactions in accordance with said arc table means.

3. The long running transaction management system of claim 1,

wherein said flow controller means further includes means for generating durable log records corresponding to (A) each created instance of one of said long running transactions, (B) termination of execution of each created instance of one of said long running transactions, (C) each said step in one of said long running transactions for which execution has been initiated, and (D) termination of each step in one of said long running transactions for which execution has been initiated;

and

said system further includes transaction restarting means for restarting long running transactions interrupted by a system failure by reviewing said durable log records and restarting execution of said interrupted long running transactions so as to avoid reexecuting steps thereof that have already been terminated.

4. The long running transaction management system of claim 1, wherein

said flow description means further includes output event definition means for defining for any specified one of said steps (A) a number of output conditions, (B) criteria for selecting a first of said output conditions after executing said step, (C) a number of event signals, associated with each defined output condition, to be generated after executing said step, including a specification of parameters to be included in each said event signal, and (D) data denoting for each defined output event signal a destination step to which said output event signal is to be sent;

said flow controller means further includes means for (A) evaluating said criteria for selecting said first of said output conditions after executing each said step, (B) generating a number of said event signals associated with said selected first output condition after executing said step, and (C) sending said generated output event signals to the corresponding destination step defined by said flow description means;

whereby specified ones of said steps can send different output event signals to different destination steps in accordance with defined criteria that are evaluated after execution of said specified ones of said steps.

5. The long running transaction management system of claim 1,

further including a plurality of resource resolution functions, each resource resolution function defining criteria for selecting a resource to execute a specified step when said specified step is instantiated;

wherein said flow description means further includes means for associating with each one of said defined steps one of said resource resolution functions; and

wherein said flow controller means further includes means for executing, each time that a step is instantiated, the resource resolution function associated with said instantiated step and thereby selecting a resource for executing said instantiated step.

6. The long running transaction management system of claim 5, wherein

said flow controller means further includes a plurality of concurrently executing processes for instantiating said steps of said created instances of long running transactions, for selecting a resource to execute each instantiated step, for receiving output event signals generated by executed steps, and for sending said output event signals to other steps of said created instances of long running transactions;

wherein the number of said plurality of concurrently executing processes in said flow controller means remains constant regardless of the number of instantiated steps extant in the system.

7. The long running transaction management system of claim 1,

wherein said flow controller performs a plurality of separate, durably stored, sub-transactions for:

(A) instantiating each step of said created instances of long running transactions, (B) after execution of each step by a selected resource, receiving output event signals from said resource, and (C) mapping said received output event signals into input event signals for other steps.

8. The long running transaction management system of claim 1, further comprising:

history management means including means for storing and retrieving status data concerning said created instances of said ones of said long running transactions during execution thereof, wherein said status data includes status information for each said step of said created instances of said ones of said long running transactions;

whereby long running transactions are executed in units of steps, and each long running transaction'"'"'s status is tracked by storage of status data concerning execution of the steps associated with said each long running transaction.

9. In a distributed computer system having a plurality of interconnected computers, a method for managing long running transactions comprising the steps of:

A) storing flow description data, said flow description data representing each of a number of types of long running transactions as a respective flow, each said flow comprising a set of steps with arcs therebetween, each said step comprising a computer-executable application routine and each said arc comprising a data signal path, said flow description data specifying input condition criteria for starting execution of each said step upon occurrence of a specified number of specified input events and resource selecting criteria for selecting a resource to execute each said step, said flow description data thereby providing a template corresponding to each said transaction type;

B) creating and executing a number of instances of transactions corresponding to said transaction types, said executing step being performed in accordance with said stored templates and including, for each said step of each said transaction instance, the steps of

(i) dynamically selecting a resource for performing execution of said step in accordance with the stored resource selecting criteria, said selecting step being performed after executing any and all steps of said transaction instance that said flow description data indicates as being prior to said step, and

(ii) initiating execution of said step when said stored input condition criteria for said step are satisfied;

C) durably storing status information and results from each said executed step for use in tracking execution of said transaction instances and in recovery following interruptions in execution of transaction instances; and

D) using said stored status information for reinitiation of execution following any interruption of the execution of transaction instances.

10. The method of performing long running transactions of claim 9, further comprising the steps of

generating durable log records corresponding to (A) each created instance of one of said long running transactions, (B) termination of execution of each created instance of one of said multiplicity of long running transactions, (C) each said step in one of said long running transactions for which execution has been initiated, and (D) termination of each said step in one of said multiplicity of long running transactions for which execution has been initiated;

and

restarting ones of said long running transactions interrupted by a system failure by reviewing said durable log records and restarting execution of said interrupted long running transactions so as to avoid reexecuting steps thereof that have already been terminated.

11. The method of performing long running transactions of claim 9, wherein

said flow description data includes output event data defining for any specified one of said steps (A) a plurality of output conditions, (B) criteria for selecting a first of said output conditions after executing said step, (C) a number of event signals, associated with each defined output condition, to be generated after executing said step, including a specification of parameters to be included in each said event signal, and (D) data denoting for each defined output event signal a destination step to which said output event signal is to be sent;

said method further comprises the steps of (A) evaluating said criteria for selecting said first of said output conditions after executing each said step, (B) generating a number of said event signals associated with said selected first output condition after executing said step, and (C) sending said generated output event signals to the corresponding destination step defined by said flow description data;

whereby specified ones of said steps can send different output event signals to different destination steps in accordance with defined criteria that are evaluated after execution of said specified ones of said steps.

12. The method of performing long running transactions of claim 9, wherein

said system further includes a plurality of resource resolution functions, each resource resolution function defining criteria for selecting a resource to execute a specified step when said specified step is instantiated;

said flow description data includes data associating with each one of said defined steps one of said resource resolution functions;

said method further comprises the step of executing, each time that a step is instantiated, the resource resolution function associated with said instantiated step and thereby selecting a resource for executing said instantiated step.

13. The method of performing long running transactions of claim 12,

further comprising the step of concurrently executing processes for instantiating said steps of said created instances of long running transactions, for selecting a resource to execute each instantiated step, for receiving output event signals generated by executed steps, and for sending said output event signals to other steps of said created instances of long running transactions;

wherein the number of said plurality of concurrently executing processes remains constant regardless of the number of instantiated steps extant in the system.

14. The method of performing long running transactions of claim 9, further comprising the step of performing a plurality of separate, durably stored, sub-transactions for:

(A) instantiating each step of said instances of long running transactions, (B) after execution of each step by a selected resource, receiving a number of output event signals from said resource, and (C) mapping said received output event signals into input event signals for other steps.

15. The method of performing long running transactions of claim 9,

wherein said flow description data includes output event data defining a number of output event signals generated by each step of each long running transaction, port data for defining a number of input ports for each step of each long running transaction, and arc data denoting for each defined output event signal a destination step and said destination step'"'"'s input port to which said output event signal should be sent;

said method further comprises the steps of (A) receiving a number of output parameters generated by executed steps of said created instances of said long running transactions and generating a set of corresponding output event signals in accordance with said output event data, and (B) routing said output event signals to input ports of corresponding steps of said created instances of said long running transactions in accordance with said arc data.