Complex dependency graph with bottom-up constraint matching for batch processing

• US 8,881,154 B2
• Filed: 12/22/2008
• Issued: 11/04/2014
• Est. Priority Date: 12/22/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Plancarte, Gustavo A., Wang, Tao, Kurup, Vijay B.
• Primary Examiner(s): Faherty, Corey S
• Application Number:
  US12/340,742
• Publication Number:
  US 20100162248A1
• Time in Patent Office: 2,143 Days
• Field of Search: None
• US Class Current: 718/101
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

Architecture that includes a batch framework engine incorporated into the server and that supports a rich set of dependencies between tasks in a single batch job. A bottom-up approach is employed where analysis is performed if a task can run based on the parent tasks. The framework runs batch jobs without the need of a client, and provides the ability to create dependencies between tasks, which allow the execution of tasks in parallel or in sequence. Using an AND/OR relationship engine, a task can require that all parent tasks (logical AND) meet requirements to run, or that only one parent (logical OR) is required to meet its requirements in order to run. Clean-up or non-important tasks can have the a flag set where even if such tasks fail when executing, the batch job will ignore these tasks when defining the final status of the job.

Claims

1. A computer-implemented batch processing system, comprising:

a processing unit;

a constraints component executing on the processing unit for defining set-based constraints between parent tasks and child tasks of a batch job, wherein a set-based constraint defines a dependency between a parent task and a child task and specifies a parent task status needed before a child task of the parent task can execute; and

a batch component executing on the processing unit for processing the batch job based on the child tasks and the set-based constraints by updating statuses for tasks in the batch job, performing constraint matching from the child tasks to the parent tasks based on the updated task statuses, and executing the tasks in the batch lob according to the constraints.

2. The system of claim 1, wherein the child task executes when all the parent tasks match an expected status as defined by a set-based constraint.

3. The system of claim 1, wherein the child task executes when one of the parent tasks matches an expected status as defined by a set-based constraint.

4. The system of claim 1, wherein the constraints component and batch component operate on a server without client intervention.

5. The system of claim 1, wherein the set-based constraints are applied directly on a database.

6. The system of claim 1, wherein the child tasks include a task flagged to be ignored when the batch job defines a final status.

7. The system of claim 1, wherein the batch job is finished when no job task is executing or ready after processing the constraints of the job.

8. The system of claim 1, wherein the batch component processes a child task when associated parent tasks have met dependency constraints.

9. A computer-implemented batch processing system, comprising:

a processing unit;

a constraints component of a server executing on the processing unit for defining set-based constraints between parent tasks and child tasks of a batch job, wherein a set-based constraint defines a dependency between a parent task and a child task and specifies a parent task status needed before a child task of the parent task can execute; and

a batch component of the server executing on the processing unit for processing the batch job based on the child tasks and the set-based constraints by updating statuses for tasks in the batch job, performing constraint matching from the child tasks to the parent tasks based on the updated task statuses, and executing the tasks in the batch job according to the constraints, the batch job is finished when no job task is designated as executing or ready after processing the constraints of the job.

10. The system of claim 9, wherein the child task executes when all the parent tasks match an expected status or when only one of the parent tasks matches an expected status.

11. The system of claim 9, wherein the constraints component and batch component operate on the server without client, intervention and the set-based constraints are applied directly on a database.

12. The system of claim 9, wherein the child tasks include a task flagged to be ignored when the batch job defines a final status.

13. The system of claim 9, wherein the batch component processes a child task when associated parent tasks have met dependency constraints.

14. A computer-implemented batch processing method, comprising:

receiving a batch job for execution, the batch job represented as a graph having root tasks, child tasks, and task constraints stored in a database, wherein a task constraint defines a dependency between a parent task and a child task and specifies a parent task status needed before a child task of the parent task can execute;

changing task statuses in the database;

performing constraint matching upward in the graph from the child tasks to the root tasks based on the changed task statuses; and

executing the job based on the constraints.

15. The method of claim 14, wherein the task statuses for the root tasks are changed to designate ready for processing in a hatch table of the database.

16. The method of claim 14, further comprising processing child tasks that match a dependency status of all parent tasks and have a constraint of logical AND.

17. The method of claim 16, further comprising processing child tasks that match a dependency status of at least one parent task and have a constraint of logical OR.

18. The method of claim 14, further comprising ignoring success or failure of a task flagged to be ignored during execution of the batch job when determining overall status of the batch job.

19. The method of claim 14, further comprising maintaining a constraints table on the database that represents dependencies between batch tasks.

20. The method of claim 14, wherein a task is independent in the batch job or has multiple dependencies defined in the batch job.