Event-driven scheduling using directed acyclic graphs

• US 10,713,088 B2
• Filed: 03/23/2017
• Issued: 07/14/2020
• Est. Priority Date: 03/23/2017
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Hosmani, Chetan, Ballantyne, Dougal Stuart
• Primary Examiner(s): Swift, Charles M
• Application Number:
  US15/468,036
• Publication Number:
  US 20180276040A1
• Time in Patent Office: 1,209 Days
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt
• CPC Class Codes: G06F 9/4806 Task transfer initiation or dispatching
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Methods, systems, and computer-readable media for event-driven scheduling using directed acyclic graphs are disclosed. A directed acyclic graph is generated that comprises a plurality of nodes and a plurality of edges. The nodes represent jobs, and the edges represent dependency relationships between individual jobs. Based (at least in part) on one or more events, a job scheduler determines that one of the nodes represents a runnable job. One or more of the dependency relationships for the runnable job are satisfied by the one or more events. An execution schedule is determined for the runnable job. Based (at least in part) on the execution schedule, execution of the runnable job is initiated using one or more computing resources.

Claims

1. A system, comprising:

a plurality of computing resources of a provider network;

a data store; and

one or more computing devices configured to implement a job scheduler, wherein the job scheduler is configured to;

receive information descriptive of a plurality of jobs;

generate a directed acyclic graph comprising a plurality of nodes and a plurality of edges, wherein the nodes represent at least a portion of the plurality of jobs, wherein the edges represent dependency relationships between individual ones of the jobs, and wherein information descriptive of jobs having unsatisfied dependency relationships is stored in a queue of pending jobs in the data store, wherein the queue of pending jobs is separate from the directed acyclic graph;

based at least in part on one or more events generated external to the directed acyclic graph regarding one or more of the plurality ofjobs, and on analysis of the directed acyclic graph, determine that one of the nodes represents a runnable job, wherein one or more of the dependency relationships for the runnable job, represented by one or more edges of the plurality of edges associated with the one of the nodes, have been satisfied by the one or more events generated external to the directed acyclic graph; and

place the runnable job in a queue of runnable jobs separate from the directed acyclic graph; and

wherein at least a subset of the computing resources are configured to;

initiate execution of the runnable job from the queue of runnable jobs.

2. The system as recited in claim 1, wherein, based at least in part on an event associated with submission of a new job having one or more new dependency relationships with one or more earlier-submitted jobs, the job scheduler is further configured to:

add, to the directed acyclic graph, a new node representing the new job;

add, to the directed acyclic graph, one or more new edges representing the one or more new dependency relationships between the new job and the one or more earlier-submitted jobs; and

update, in the directed acyclic graph, one or more nodes representing the one or more earlier-submitted jobs without evaluating other nodes not associated with the one or more new dependency relationships.

3. The system as recited in claim 1, wherein the one or more events comprise an event associated with execution of a scheduled job having one or more dependency relationships with one or more later-submitted jobs, and wherein, based at least in part on the event associated with the execution of the scheduled job, the job scheduler is further configured to:

remove, from the directed acyclic graph, one or more edges representing at least one of the dependency relationships with the one or more later-submitted jobs; and

update, in the directed acyclic graph, one or more nodes representing the one or more later-submitted jobs without evaluating other nodes not having dependency relationships with the scheduled job.

4. A computer-implemented method, comprising:

generating a directed acyclic graph comprising a plurality of nodes and a plurality of edges, wherein the nodes represent a plurality of jobs, and wherein the edges represent dependency relationships between individual ones of the jobs;

based at least in part on one or more events generated external to the directed acyclic graph regarding one or more of the plurality of jobs, and on analysis of the directed acyclic graph, determining that one of the nodes represents a runnable job, wherein one or more of the dependency relationships for the runnable job, represented by one or more edges of the plurality of edges associated with the one of the nodes, are satisfied by the one or more events generated external to the directed acyclic graph;

determining an execution schedule for the runnable job, wherein the execution schedule is separate from the directed acyclic graph; and

based at least in part on the execution schedule, initiating execution of the runnable job using one or more computing resources.

5. The method as recited in claim 4, wherein the method further comprises, based at least in part on an event associated with submission of a new job having one or more new dependency relationships with one or more earlier-submitted jobs:

adding, to the directed acyclic graph, a new node representing the new job;

adding, to the directed acyclic graph, one or more new edges representing the one or more new dependency relationships between the new job and the one or more earlier-submitted jobs; and

updating, in the directed acyclic graph, one or more nodes representing the one or more earlier-submitted jobs without evaluating other nodes not associated with the one or more new dependency relationships.

6. The method as recited in claim 4, wherein the one or more events comprise an event associated with execution of a scheduled job having one or more dependency relationships with one or more later-submitted jobs, and wherein the method further comprises, based at least in part on the event associated with the execution of the scheduled job:

removing, from the directed acyclic graph, one or more edges representing at least one of the dependency relationships with the one or more later-submitted jobs; and

updating, in the directed acyclic graph, one or more nodes representing the one or more later-submitted jobs without evaluating other nodes not having dependency relationships with the scheduled job.

7. The method as recited in claim 4, further comprising:

determining that no nodes are dependent on the runnable job; and

based at least in part on determining that no nodes are dependent on the runnable job, removing the node representing the runnable job from the directed acyclic graph.

8. The method as recited in claim 4, further comprising:

determining that a newly submitted job has no dependency relationships with other jobs; and

based at least in part on determining that the newly submitted job has no dependency relationships with other jobs, placing the newly submitted job in a queue of runnable jobs without adding a node representing the newly submitted job to the directed acyclic graph.

9. The method as recited in claim 4, further comprising:

based at least in part on an event associated with failure or cancellation of a job and on a policy, removing, from the directed acyclic graph, one or more nodes representing one or more jobs having dependency relationships with the job or having dependency relationships with one or more removed nodes.

10. The method as recited in claim 4, further comprising:

loading, from a data store, information descriptive of a plurality of jobs having unsatisfied dependency relationships; and

rebuilding the directed acyclic graph after a scheduler failure based at least in part on the information descriptive of the plurality of jobs having unsatisfied dependency relationships.

11. The method as recited in claim 4, wherein the one or more events comprise an event associated with completion of a threshold percentage of a job.

12. The method as recited in claim 4, further comprising:

determining that a newly submitted job has a dependency relationship on an earlier-submitted job; and

based at least in part on determining that the newly submitted job has the dependency relationship on the earlier-submitted job, adding to the directed acyclic graph a node corresponding to the newly submitted job and a node corresponding to the earlier-submitted job.

13. The method as recited in claim 4, wherein determining the execution schedule for the runnable job comprises:

inserting the runnable job in an ordered list of runnable jobs based at least in part on one or more timestamps of job submission, wherein the list of runnable jobs is not resorted in the inserting the runnable job.

14. A computer-readable storage medium storing program instructions that, if executed, perform:

generating a directed acyclic graph comprising a plurality of nodes and a plurality of edges, wherein the nodes represent a plurality of jobs, and wherein the edges represent dependency relationships between individual ones of the jobs;

based at least in part on one or more events generated external to the directed acyclic graph regarding one or more of the plurality of jobs, and on analysis of the directed acyclic graph, determining that one of the nodes represents a runnable job, wherein one or more of the dependency relationships for the runnable job, represented by one or more edges of the plurality of edges associated with the one of the nodes, are satisfied by the one or more events generated external to the directed acyclic graph;

determining an execution schedule for the runnable job, wherein the execution schedule is separate from the directed acyclic graph, and comprises an execution order of the runnable job and one or more additional runnable jobs; and

based at least in part on the execution schedule, initiating execution of the runnable job using one or more computing resources of a provider network.

15. The computer-readable storage medium as recited in claim 14, wherein, based at least in part on an event associated with submission of a new job having one or more new dependency relationships with one or more earlier-submitted jobs, the program instructions are further computer-executable to perform:

adding, to the directed acyclic graph, a new node representing the new job;

adding, to the directed acyclic graph, one or more new edges representing the one or more new dependency relationships between the new job and the one or more earlier-submitted jobs; and

updating, in the directed acyclic graph, one or more nodes representing the one or more earlier-submitted jobs without evaluating other nodes not associated with the one or more new dependency relationships.

16. The computer-readable storage medium as recited in claim 14, wherein the one or more events comprise an event associated with execution of a scheduled job having one or more dependency relationships with one or more later-submitted jobs, and wherein, based at least in part on the event associated with the execution of the scheduled job, the program instructions are further computer-executable to perform:

removing, from the directed acyclic graph, one or more edges representing at least one of the dependency relationships with the one or more later-submitted jobs; and

updating, in the directed acyclic graph, one or more nodes representing the one or more later-submitted jobs without evaluating other nodes not having dependency relationships with the scheduled job.

17. The computer-readable storage medium as recited in claim 14, wherein the program instructions are further computer-executable to perform:

determining that no nodes are dependent on the runnable job; and

based at least in part on determining that no nodes are dependent on the runnable job, removing the node representing the runnable job from the directed acyclic graph.

18. The computer-readable storage medium as recited in claim 14, wherein the program instructions are further computer-executable to perform:

determining that a newly submitted job has no dependency relationships with other jobs; and

based at least in part on determining that the newly submitted job has no dependency relationships with other jobs, placing the newly submitted job in a queue of runnable jobs without adding a node representing the newly submitted job to the directed acyclic graph.

19. The computer-readable storage medium as recited in claim 14, wherein the program instructions are further computer-executable to perform:

based at least in part on an event associated with failure or cancellation of a job and on a policy, removing, from the directed acyclic graph, one or more nodes representing one or more jobs having dependency relationships with the job or having dependency relationships with one or more removed nodes.

20. The computer-readable storage medium as recited in claim 14, wherein the program instructions are further computer-executable to perform:

loading, from a data store, information descriptive of a plurality of jobs having unsatisfied dependency relationships; and

rebuilding the directed acyclic graph after a scheduler failure based at least in part on the information descriptive of the plurality of jobs having unsatisfied dependency relationships.