×

Window-based scheduling using a key-value data store

  • US 8,959,518 B2
  • Filed: 03/30/2012
  • Issued: 02/17/2015
  • Est. Priority Date: 03/30/2012
  • Status: Active Grant
First Claim
Patent Images

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.

View all claims
  • 9 Assignments
Timeline View
Assignment View
    ×
    ×