Granted Patent B2

US 8,959,518 · App. 13/436,249 · Granted Feb 17, 2015

Abstract

Claims (37)

1. A scheduling system for scheduling executions of tasks within a distributed computing system, the scheduling system including:

at least one processor; and

a non-transitory computer readable storage medium storing instructions, which, when executed by the at least one processor implement

an entry generator configured to cause the at least one processor to store, using at least one key-value data store, time windows for scheduled executions of tasks therein using a plurality of nodes of the distributed computing system, each time window being stored as a time window data structure in conjunction with a time window key within the key-value store, and further configured to cause the at least one processor to generate scheduler entries, each scheduler entry being stored as a scheduler entry data structure in conjunction with a scheduler entry key within the key-value store and including a corresponding task of the tasks and an associated schedule for execution thereof, wherein each time window data structure is initially stored separately from each scheduler entry data structure, and the entry generator is configured to cause the at least one processor to calculate, for a selected task and based on its associated schedule, an upcoming task invocation and an associated, selected time window in which the upcoming task invocation falls, for storage of the upcoming task invocation therein; and

an execution engine configured to cause the at least one processor to execute the selected task within the selected time window within the distributed computing system,

wherein the entry generator is further configured to cause the at least one processor to assign the scheduler entry and associated upcoming task invocation to the selected time window of the time windows, including calculating a granularity of an invocation time of the associated upcoming task invocation to correlate with a timestamp of the selected time window, and

wherein the execution engine is further configured to cause the at least one processor to read the upcoming task invocation for the selected task to an in-flight map when a current time equals the time stamp of the selected time window, and in response thereto, sort the upcoming task invocation according to actual scheduled task invocations within the selected time window as to resolve any discrepancies.

2. The system of claim 1 , wherein the entry generator is configured to store each time window of the time windows within the at least one key-value data store, using a time stamp of a beginning of each time window as the time window key for the corresponding time window.

3. The system of claim 1 , wherein the entry generator is configured to store each task of the tasks within the at least one key-value data store, using a corresponding unique task identifier as the time window key, and including a pointer to associated task data.

4. The system of claim 1 , wherein the entry generator is configured to assign the scheduler entries to corresponding time windows including calculating a modulus of each invocation time of each upcoming task invocation to obtain a time corresponding to a time stamp of one of the time windows.

5. The system of claim 1 , wherein the entry generator is configured to include the scheduler entries within the time window including creating a linked list of task invocations of scheduler entries within the selected time window.

6. The system of claim 5 , wherein the entry generator is configured to add new task invocations to the linked list, including prepending or appending each new task invocation to the linked list in accordance with a determination that the new task invocation falls into a lower half or upper half, respectively, of the selected time window.

7. The system of claim 1 , wherein the entry generator includes a lock manager configured to acquire a lock on the selected time window of the time windows during a time of write operations executed with respect to including the upcoming task invocation therein.

8. The system of claim 1 , wherein the execution engine includes an entry reader configured to read the upcoming task invocation from the selected time window for inclusion within the in-flight map of scheduler entries to be executed, in association with corresponding nodes of the plurality of nodes on which the corresponding tasks are assigned for execution.

9. The system of claim 8 , wherein the entry reader is configured to read a preconfigured maximum number of task invocations from the time window to the in-flight map.

10. The system of claim 8 , wherein the execution engine is configured to read task invocations from the in-flight map to an execution queue for execution of associated tasks at corresponding invocation times thereof.

11. The system of claim 1 , further comprising a cluster coordinator configured to identify scheduler entries having task invocations scheduled for execution on an unavailable node of the plurality of nodes, and further configured to regenerate corresponding task invocations therefore within a new time window of the time windows.

12. A method comprising:

storing, using at least one key-value data store, time windows for scheduled executions of tasks therein using a plurality of nodes of a distributed computing system, each time window being stored as a time window data structure in conjunction with a time window key within the key-value store;

generating scheduler entries, each scheduler entry being stored as a scheduler entry data structure in conjunction with a scheduler entry key within the key-value store and including a corresponding task of the tasks and an associated schedule for execution thereof, wherein each time window data structure is initially stored separately from each scheduler entry data structure,

calculating, for a selected task and based on its associated schedule, an upcoming task invocation and an associated, selected time window in which the upcoming task invocation falls, for storage of the upcoming task invocation therein;

assigning the scheduler entry and associated upcoming task invocation to the selected time window of the time windows, including calculating a granularity of an invocation time of the associated upcoming task invocation to correlate with a timestamp of the selected time window;

reading the upcoming task invocation for the selected task to an in-flight map when a current time equals the time stamp of the selected time window;

sorting, in response to the reading, the upcoming task invocation according to actual scheduled task invocations within the selected time window as to resolve any discrepancies; and

executing the selected task within the selected time window and within the distributed computing system.

13. The method of claim 12 , wherein the scheduler entries are included within the selected time window as a linked list of task invocations of scheduler entries.

14. The method of claim 12 , wherein execution of the upcoming task invocation includes reading the upcoming task invocation from the selected time window for inclusion within the in-flight map of task invocations to be executed, in association with corresponding nodes of the plurality of nodes on which the corresponding task invocations are assigned for execution.

15. A computer program product including instructions recorded on a non-transitory computer readable storage medium and configured to cause at least one processor to:

store, using at least one key-value data store, time windows for scheduled executions of tasks therein using a plurality of nodes of a distributed computing system, each time window being stored as a time window data structure in conjunction with a time window key within the key-value store;

generate scheduler entries, each scheduler entry being stored as a scheduler entry data structure in conjunction with a scheduler entry key within the key-value store and including a corresponding task of the tasks and an associated schedule for execution thereof, wherein each time window data structure is initially stored separately from each scheduler entry data structure,

calculate, for a selected task and based on its associated schedule, an upcoming task invocation and an associated, selected time window in which the upcoming task invocation falls, for storage of the upcoming task invocation therein;

assign the scheduler entry and associated upcoming task invocation to the selected time window of the time windows, including calculating a granularity of an invocation time of the associated upcoming task invocation to correlate with a timestamp of the selected time window;

read the upcoming task invocation for the selected task to an in-flight map when a current time equals the time stamp of the selected time window;

sort, in response to the reading, the upcoming task invocation according to actual scheduled task invocations within the selected time window as to resolve any discrepancies; and

execute the selected task within the selected time window and within the distributed computing system.

16. The computer program product of claim 15 , wherein the scheduler entries are included within the selected time window as a linked list of task invocations of scheduler entries.

17. The computer program product of claim 15 , wherein the upcoming task invocation is read from the selected time window for inclusion within the in-flight map of task invocations to be executed, in association with corresponding nodes of the plurality of nodes on which the corresponding task invocations are assigned for execution.

Assignments (14)