Systems and methods for performing scheduling for a cluster

Patent metadata

Field	Value
Publication number	US-9870258-B1
Application number	US-201615164098-A
Country	US
Kind code	B1
Filing date	May 25, 2016
Priority date	Jul 13, 2012
Publication date	Jan 16, 2018
Grant date	Jan 16, 2018

Abstract

Multiple scheduler verticals can allocate tasks to resources that are shared by the scheduler verticals. Information regarding a state of each resource may be stored in memory accessible by the multiple scheduler verticals, and a processor updates the information. The scheduler verticals schedule events to be performed by any of the resources, and submit updates to reflect the scheduled events in the information. In the event of conflicting events, an update corresponding to only one of the conflicting events is committed. Moreover, disruptions may be preplanned and scheduled so as to minimize impact on scheduled tasks.

First claim

The invention claimed is:

1. A system, comprising:
a first scheduler vertical;
a second scheduler vertical; and
a memory accessible by the first scheduler vertical and the second scheduler vertical, the memory storing an assignment of work for machines;
wherein the first scheduler vertical is in communication with one or more processors and programmed to:
access the memory;
determine timeslots for scheduling a first set of tasks; and
schedule the first set of tasks;
wherein the second scheduler vertical is in communication with one or more processors and programmed to:
access the memory;
determine, concurrently with the first scheduler vertical, timeslots for scheduling a second set of tasks; and
schedule the second set of tasks; and
reschedule conflicting tasks that conflict with any of the first set of tasks scheduled by the first scheduler vertical;
wherein the first scheduler vertical is configured to execute decisions regarding allocation of tasks among machines more quickly than the second schedule vertical.

2. The system of claim 1 , wherein in scheduling the first set of tasks the first scheduler vertical is further configured to:
receive a first copy of the assignment of work for the machines from the memory at a first time; and
commit to the memory a first additional task at a second time.

3. The system of claim 2 , wherein in scheduling the second set of tasks the second scheduler vertical is further configured to:
receive a second copy of the assignment of work for the machines from the memory at a third time;
commit to the memory a second additional task at a fourth time.

4. The system of claim 3 , wherein an amount of second scheduler vertical scheduling time between the third time and the fourth time is greater than an amount of first scheduler vertical scheduling time between the first time and the second time.

5. The system of claim 3 , wherein:
if the third time at which the second scheduler vertical receives the second copy of the assignment of work is between the first time and the second time, the second copy of the assignment of work is the same as the first copy of the assignment of work.

6. The system of claim 5 , wherein:
if the second scheduler vertical fails to commit the second additional task based on a conflict, the second scheduler vertical:
receives a third copy of the assignment of work from the memory subsequent to the fourth time;
determines a new timeslot for the second additional task; and
subsequently commits to the memory the second additional task.

7. The system of claim 1 , wherein the one or more processors are configured to:
receive a request for a given task; and
determine whether to assign the given task to the first scheduler vertical or the second scheduler vertical.

8. The system of claim 1 , wherein the second scheduler vertical is configured to execute decisions regarding allocation of tasks with better placement characteristics than the first scheduler vertical.

9. A method, comprising:
determining, by a first scheduler vertical, timeslots for scheduling a first set of tasks;
scheduling, by the first scheduler vertical, the first set of tasks;
determining, by a second scheduler vertical concurrently with the first scheduler vertical, timeslots for scheduling a second set of tasks;
scheduling, by the second scheduler vertical, the second set of tasks; and
rescheduling, by the second scheduler vertical, conflicting tasks that conflict with any of the first set of tasks scheduled by the first scheduler vertical;
wherein the first scheduler vertical is configured to execute decisions regarding allocation of tasks among machines more quickly than the second schedule vertical.

10. The method of claim 9 , wherein scheduling the first set of tasks further comprises:
receiving a first copy of the assignment of work for the machines from the memory at a first time; and
committing to the memory a first additional task at a second time.

11. The method of claim 10 , wherein scheduling the second set of tasks further comprises:
receiving a second copy of the assignment of work for the machines from the memory at a third time; and
committing to the memory a second additional task at a fourth time.

12. The method of claim 11 , wherein an amount of second scheduler vertical scheduling time between the third time and the fourth time is greater than an amount of first scheduler vertical scheduling time between the first time and the second time.

13. The method of claim 11 , wherein:
if the third time at which the second scheduler vertical receives the second copy of the assignment of work is between the first time and the second time, the second copy of the assignment of work is the same as the first copy of the assignment of work.

14. The method of claim 13 , further comprising:
if the second scheduler vertical fails to commit the second additional task based on a conflict:
receiving, by the second scheduler vertical, a third copy of the assignment of work from the memory subsequent to the fourth time;
determining, by the second scheduler vertical, a new timeslot for the second additional task; and
subsequently committing, by the second scheduler vertical, to the memory the second additional task.

15. The method of claim 9 , further comprising:
receiving, at one or more processors, a request for a given task; and
determining whether to assign the given task to the first scheduler vertical or the second scheduler vertical.

16. The method of claim 9 , wherein the second scheduler vertical is configured to execute decisions regarding allocation of tasks with better placement characteristics than the first scheduler vertical.

Assignees

• Google Inc
• Google Llc

Inventors

• Wilkes John
• Wang Todd Pu-Tse
• Cirne Walfredo
• Oppenheimer David
• Grant Brian
• Hickey Jason
• Backman Kai-Peter
• Hellerstein Joseph
• Bort David

Classifications

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• G06F9/4881 Primary

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

• G06F9/4818

  Priority circuits therefor · CPC title