Scalable task scheduling

• US 8,826,284 B1
• Filed: 03/27/2012
• Issued: 09/02/2014
• Est. Priority Date: 10/31/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Fuller, Alfred R. K.
• Primary Examiner(s): NGUYEN, VAN H
• Application Number:
  US13/431,908
• Time in Patent Office: 889 Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

A server system having one or more processors and memory receives, from a client, a request to perform a first task. The server system determines whether a first slot in a primary task queue having a plurality of slots is available, where the first slot was selected in accordance with a slot-selection function designed to probabilistically distribute respective target slots for a plurality of successive tasks across a plurality of different non-consecutive slots in the primary task queue. In accordance with a determination that the first slot is available, the server system inserts the first task in the first slot in the primary task queue. In accordance with a determination that the first slot is unavailable, the server system inserts the first task at an entry point of a secondary task queue.

Claims

1. A method comprising:

at a respective server system having one or more processors and memory storing one or more programs that when executed by the one or more processors cause the respective server system to perform the method, the method comprising;

receiving, from a client, a request to perform a first task;

determining whether a first slot in a primary task queue having a plurality of slots is available, wherein the first slot was selected in accordance with a slot-selection function designed to probabilistically distribute respective target slots for a plurality of successive tasks across a plurality of different non-consecutive slots in the primary task queue;

in accordance with a determination that the first slot is available, inserting the first task in the first slot in the primary task queue; and

in accordance with a determination that the first slot is unavailable, inserting the first task at an entry point of a secondary task queue.

2. The method of claim 1, wherein:

prior to determining whether the first slot in the primary task queue is available;

the first task is initially inserted at an entry point of the secondary task queue; and

the first slot in the primary task queue is identified when the task reaches an exit point of the secondary task queue.

3. The method of claim 1, wherein the request to perform the first task includes information identifying the first slot in the primary task queue.

4. The method of claim 1, wherein the output of the slot-selection function is based at least in part on a number of slots in the primary task queue.

5. The method of claim 4, wherein the number of slots in the primary task queue is stored, under control of the server system at a location accessible to a computer system executing the slot-selection function, as a slot-count value.

6. The method of claim 5, wherein the slot-count value is varied based at least in part on a number of entries in the secondary task queue.

7. The method of claim 5, wherein the slot-count value is used as a parameter in the slot-selection function.

8. The method of claim 7, further comprising, prior to receiving the request from the client, providing the slot-count value to the client.

9. The method of claim 1, wherein the slot-selection function is a hash function with a modulus equal to a number of the slots in the primary task queue or a random or pseudo-random number generator with a modulus equal to the number of the slots in the primary task queue.

10. The method of claim 1, wherein:

a first set of slots in the primary task queue are assigned to a first worker process; and

the method further comprises;

at a first time, making a first group of two or more tasks in the first set of slots available to the first worker process;

at a second time, after the first time, receiving a batch delete instruction to delete all of the tasks in the first group from the primary task queue; and

in response to the batch delete instruction, deleting all of the tasks in the first group from the primary task queue.

11. The method of claim 10, further comprising:

determining that the first worker process is processing tasks at a rate that is slower than a predefined minimum rate; and

in response to the determining;

selecting a subset of slots from the first set; and

removing the subset of slots from the first set; and

assigning the subset of slots to a respective worker process distinct from the first worker process.

12. The method of claim 10, wherein:

a second set of slots in the primary task queue, distinct from the first set of slots are assigned to a second worker process; and

the method further comprises;

at a third time, independent of the first time and the second time, making a second group of two or more tasks in the second set of slots available to the second worker process;

at a fourth time, after the third time, receiving a batch delete instruction to delete all of the tasks in the second group from the primary task queue; and

in response to the batch delete instructions, deleting all of the tasks in the second group from the primary task queue.

13. The method of claim 12, wherein the first set of slots and the second set of slots are determined based on a rate at which tasks are being assigned to distinct subsets of the slots.

14. A server system, comprising:

one or more processors;

memory; and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for;

receiving, from a client, a request to perform a first task;

determining whether a first slot in a primary task queue having a plurality of slots is available, wherein the first slot was selected in accordance with a slot-selection function designed to probabilistically distribute respective target slots for a plurality of successive tasks across a plurality of different non-consecutive slots in the primary task queue;

in accordance with a determination that the first slot is available, inserting the first task in the first slot in the primary task queue; and

in accordance with a determination that the first slot is unavailable, inserting the first task at an entry point of a secondary task queue.

15. The system of claim 14, wherein the output of the slot-selection function is based at least in part on a number of slots in the primary task queue.

16. The system of claim 15, wherein the number of slots in the primary task queue is stored, under control of the server system at a location accessible to a computer system executing the slot-selection function, as a slot-count value.

17. The system of claim 14, wherein the slot-selection function is a hash function with a modulus equal to a number of the slots in the primary task queue or a random or pseudo-random number generator with a modulus equal to the number of the slots in the primary task queue.

18. The system of claim 14, wherein:

a first set of slots in the primary task queue are assigned to a first worker process; and

the one or more programs further comprise instructions for;

at a first time, making a first group of two or more tasks in the first set of slots available to the first worker process;

at a second time, after the first time, receiving a batch delete instruction to delete all of the tasks in the first group from the primary task queue; and

in response to the batch delete instruction, deleting all of the tasks in the first group from the primary task queue.

19. The system of claim 18, the one or more programs further comprise instructions for:

determining that the first worker process is processing tasks at a rate that is slower than a predefined minimum rate; and

in response to the determining;

selecting a subset of slots from the first set; and

removing the subset of slots from the first set; and

assigning the subset of slots to a respective worker process distinct from the first worker process.

20. The system of claim 18, wherein:

a second set of slots in the primary task queue, distinct from the first set of slots are assigned to a second worker process; and

the one or more programs further comprise instructions for;

at a third time, independent of the first time and the second time, making a second group of two or more tasks in the second set of slots available to the second worker process;

at a fourth time, after the third time, receiving a batch delete instruction to delete all of the tasks in the second group from the primary task queue; and

in response to the batch delete instructions, deleting all of the tasks in the second group from the primary task queue.

21. The system of claim 20, wherein the first set of slots and the second set of slots are determined based on a rate at which tasks are being assigned to distinct subsets of the slots.

22. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a computer system with one or more processors, cause the computer system to:

receive, from a client, a request to perform a first task;

determine whether a first slot in a primary task queue having a plurality of slots is available, wherein the first slot was selected in accordance with a slot-selection function designed to probabilistically distribute respective target slots for a plurality of successive tasks across a plurality of different non-consecutive slots in the primary task queue;

in accordance with a determination that the first slot is available, insert the first task in the first slot in the primary task queue; and

in accordance with a determination that the first slot is unavailable, insert the first task at an entry point of a secondary task queue.

23. The non-transitory computer readable storage medium of claim 22, wherein the output of the slot-selection function is based at least in part on a number of slots in the primary task queue.

24. The non-transitory computer readable storage medium of claim 23, wherein the number of slots in the primary task queue is stored, at a location accessible to a computer system executing the slot-selection function, as a slot-count value.

25. The non-transitory computer readable storage medium of claim 22, wherein the slot-selection function is a hash function with a modulus equal to a number of the slots in the primary task queue or a random or pseudo-random number generator with a modulus equal to the number of the slots in the primary task queue.

26. The non-transitory computer readable storage medium of claim 22, wherein:

a first set of slots in the primary task queue are assigned to a first worker process; and

the one or more programs further comprise instructions to;

at a first time, make a first group of two or more tasks in the first set of slots available to the first worker process;

at a second time, after the first time, receive a batch delete instruction to delete all of the tasks in the first group from the primary task queue; and

in response to the batch delete instruction, delete all of the tasks in the first group from the primary task queue.

27. The non-transitory computer readable storage medium of claim 26, the one or more programs further comprise instructions to:

determine that the first worker process is processing tasks at a rate that is slower than a predefined minimum rate; and

in response to the determining;

select a subset of slots from the first set; and

remove the subset of slots from the first set; and

assign the subset of slots to a respective worker process distinct from the first worker process.

28. The non-transitory computer readable storage medium of claim 26, wherein:

a second set of slots in the primary task queue, distinct from the first set of slots are assigned to a second worker process; and

the one or more programs further comprise instructions to;

at a third time, independent of the first time and the second time, make a second group of two or more tasks in the second set of slots available to the second worker process;

at a fourth time, after the third time, receive a batch delete instruction to delete all of the tasks in the second group from the primary task queue; and

in response to the batch delete instructions, delete all of the tasks in the second group from the primary task queue.

29. The non-transitory computer readable storage medium of claim 28, wherein the first set of slots and the second set of slots are determined based on a rate at which tasks are being assigned to distinct subsets of the slots.