Window-based scheduling using a key-value data store
First Claim
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 implementan 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, andwherein 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.
9 Assignments
0 Petitions
Accused Products
Abstract
A scheduling system for scheduling executions of tasks within a distributed computing system may include an entry generator configured 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. The entry generator may be further configured to generate scheduler entries for inclusion within a time window of the time windows, each scheduler entry identifying a task of the tasks and an associated schedule for execution thereof. The system may further include an execution engine configured to select the time window and execute corresponding tasks of the included scheduler entries in order.
8 Citations
17 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14)
-
-
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. - View Dependent Claims (16, 17)
-
Specification