Systems and methods for performing scheduling for a cluster

Patent metadata

Field	Value
Publication number	US-9329892-B1
Application number	US-201514864130-A
Country	US
Kind code	B1
Filing date	Sep 24, 2015
Priority date	Jul 13, 2012
Publication date	May 3, 2016
Grant date	May 3, 2016

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 set of two or more hardware scheduler verticals adapted to receive requests for work to be performed by one or more of a plurality of machines;
a memory storing information regarding a state of each of the plurality of machines; and
a processor for use in updating the information;
wherein the scheduler verticals are adapted to retrieve copies of the information, schedule events other than disruptions to be performed by any of the plurality of machines, and submit updates to reflect the scheduled events in the information; and
wherein if multiple scheduler verticals schedule conflicting events for a given machine, an update transaction submitted by one of such scheduler verticals is committed and the remaining scheduled events are rejected.

2. The system of claim 1 , wherein the processor is operable to determine which of the conflicting events to commit to memory based on timing of submission of the updates.

3. The system of claim 1 , wherein the processor is operable to determine which of the conflicting events to commit to memory based on priority of each conflicting event.

4. The system of claim 1 , wherein the memory includes a calendar storing the committed events.

5. A method of concurrently scheduling, using a plurality of scheduler verticals, events to be performed by one or more machines, comprising:
receiving requests for work to be performed, the work including one or more events and not including disruptions;
receiving information regarding a state of the one or more machines;
scheduling, using the plurality of scheduler verticals, the one or more events on the one or more machines;
submitting the scheduled events to memory;
determining, using a processor, whether conflicting events are submitted to memory;
if conflicting events are submitted to memory, committing one of the conflicting events to memory and rejecting the remaining conflicting events.

6. The method of claim 5 , further comprising determining which of the conflicting events to commit to memory, the determining based on a timing associated with the submitting of the scheduled events.

7. The method of claim 5 , further comprising determining which of the conflicting events to commit to memory, the determining based on priority of each conflicting event.

8. The method of claim 5 , wherein submitting the scheduled events to memory is performed incrementally if multiple events are simultaneously scheduled on the machine.

9. The method of claim 8 , wherein each of the incrementally submitted events is committed to memory if it is not a conflicting event.

10. The method of claim 5 , wherein the events are tasks of a job, and if it is determined that any of the tasks will be rejected due to a conflict, none of the tasks are committed to memory.

Assignees

• Google Inc

Inventors

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

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

• G06F9/5027

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