Hot key throttling by querying and skipping task queue entries

Patent metadata

Field	Value
Publication number	US-11675616-B2
Application number	US-202017097976-A
Country	US
Kind code	B2
Filing date	Nov 13, 2020
Priority date	Nov 13, 2020
Publication date	Jun 13, 2023
Grant date	Jun 13, 2023

Abstract

Methods and apparatuses for scheduling tasks with a job scheduler are disclosed. In one embodiment, the method comprises: tracking a number of active tasks for each key of a plurality of keys; writing, by a scheduler, a query to identify a next scheduled task among a plurality of scheduled tasks ordered by time in a task queue, the query having an index that excludes tasks associated with a list of one or more keys of the plurality of keys that have a count of active tasks greater than a first limit associated with each key; querying, by a scheduler, the task queue using the query to identify the next scheduled task among the plurality of scheduled tasks, the next scheduled task being associated with a key not excluded by the query; and executing the next scheduled task.

First claim

We claim:

1. A method comprising:
tracking, by a scheduler, a number of actively executing tasks associated with each key of a plurality of keys;
tracking, by the scheduler, an indication of a time that an actively executing task most recently returned to the scheduler for execution from a task queue as a result of previously querying the task queue was returned to the scheduler, wherein the task queue comprises a plurality of scheduled tasks ordered by time;
writing, by the scheduler, a new query to identify a next scheduled task among the plurality of scheduled tasks, the new query having an index that excludes scheduled tasks associated with a list of one or more keys of the plurality of keys count which are associated with a number of actively executing tasks greater than a first limit associated with each key and includes the indication in the index of the time of the task most recently returned to the scheduler;
querying, by the scheduler, the task queue using the new query to identify the next scheduled task among the plurality of scheduled tasks, the next scheduled task being associated with a key not excluded by the new query, wherein querying the task queue includes skipping entries in the task queue to begin scanning at a location in the task queue based on the indication in the index of the new query;
returning, as a result of the new query, the next scheduled task to the scheduler; and
executing the next scheduled task.

2. The method of claim 1 wherein each key of the plurality of keys corresponds to a merchant.

3. The method of claim 1 wherein the limit is different for at least two of the keys of the plurality of keys.

4. The method of claim 1 further comprising:
determining which of the plurality of keys to include in the list based on results of the tracking;
storing the list in memory; and
accessing the list in memory to obtain an indication of the one or more keys for use in writing the query.

5. The method of claim 1 further comprising tracking the number of active tasks for keys in the plurality of keys per shard, and wherein the query excludes the one or more of the keys that have a count of active tasks greater than the first limit or greater than a shard limit associated with each key.

6. The method of claim 1 wherein each key in the list of one or more keys has saturated its allowed concurrency, such that performing the query results in locating the next scheduled task that has not saturated its allowed concurrency.

7. The method of claim 1 wherein the indication of the time of the task most recently returned from the task queue comprises its timestamp.

8. The method of claim 1 further comprising:
determining composition of keys in the list has changed; and
performing a new query of the database, where the new query having the index that excludes tasks associated with the list but not including the indication of the time of the task most recently returned from the database to cause scanning of the database to begin with the earliest of the plurality of scheduled tasks when performing the query.

9. The method of claim 1 wherein the query index includes a plurality of fields, wherein a first field of the plurality of fields comprises the indication of the time of the task most recently returned from the database and a second field of the plurality of fields specifies the list of one or more keys of the plurality of keys, the second field being after the first field in the plurality of fields.

10. A network arrangement comprising:
a database to store a plurality of scheduled tasks ordered by time; and
a scheduler having one or more processors to:
track a number of actively executing tasks associated with each key of a plurality of keys;
track an indication of a timestamp that an actively executing task most recently returned to the scheduler for execution from the database as a result of previously querying the database was returned to the scheduler;
write a new query to identify a next scheduled task among the plurality of scheduled tasks, the new query having an index that excludes scheduled tasks associated with a list of one or more keys of the plurality of keys which are associated with a number of actively executing tasks greater than a first limit associated with each key and includes the indication in the index of the timestamp of the task most recently returned to the scheduler;
query the database using the new query to identify the next scheduled task among the plurality of scheduled tasks, the next scheduled task being associated with a key not excluded by the new query, wherein querying the database includes skipping entries in the database to begin scanning at a location in the database based on the indication in the index of the new query;
return, as a result of the new query, the next scheduled task to the scheduler; and
execute the next scheduled task.

11. The network arrangement of claim 10 wherein each key of the plurality of keys corresponds to a merchant.

12. The network arrangement of claim 10 wherein the first limit is different for at least two of the keys of the plurality of keys.

13. The network arrangement of claim 10 wherein the one or more processors are configured to:
determine which of the plurality of keys to include in the list based on results of the tracking;
store the list in memory; and
access the list in memory to obtain an indication of the one or more keys for use in writing the query.

14. The network arrangement of claim 10 wherein the query index includes a plurality of fields, wherein a first field of the plurality of fields specifies the watermark and a second field of the plurality of fields specifies the list of one or more keys of the plurality of keys, the second field being after the first field in the plurality of fields.

15. The network arrangement of claim 10 wherein the one or more processors are configured to:
determine composition of keys in the list has changed; and
perform a new query of the database, where the new query having the index that excludes tasks associated with the list but not including the indication of the time of the task most recently returned from the database to cause scanning of the database to begin with the earliest of the plurality of scheduled tasks when performing the query.

16. One or more non-transitory computer readable storage media having instructions stored thereupon which, when executed by a scheduler having at least a processor and a memory therein, cause the scheduler to perform operations comprising:
tracking a number of actively executing tasks associated with each key of a plurality of keys;
tracking an indication of a timestamp that an actively executing task most recently returned to the scheduler for execution from a task queue as a result of previously querying the task queue was returned to the scheduler, wherein the task queue comprises a plurality of scheduled tasks ordered by time;
writing a new query to identify a next scheduled task among the plurality of scheduled tasks, the new query having an index that excludes scheduled tasks associated with a list of one or more keys of the plurality of keys which are associated with a number of actively executing tasks greater than a first limit associated with each key and includes the indication in the index of the timestamp of the task most recently returned to the scheduler;
querying the task queue using the new query to identify the next scheduled task among the plurality of scheduled tasks, the next scheduled task being associated with a key not excluded by the new query, wherein queryi

Assignees

• Mintz Michael
• Vaseeharan Thirukumaran
• Levin Aaron
• Judd David
• Wilson Nathaniel
• Stripe Inc

Inventors

• Mintz Michael
• Vaseeharan Thirukumaran
• Levin Aaron
• Judd David
• Wilson Nathaniel

Classifications

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/4818 Primary

  Priority circuits therefor · CPC title