Scheduling in computer clusters

• US 8,843,929 B1
• Filed: 07/15/2008
• Issued: 09/23/2014
• Est. Priority Date: 07/15/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Oppenheimer, David L., Henzinger, Monika H., Radez, Robin A.
• Primary Examiner(s): Faherty, Corey S
• Application Number:
  US12/173,697
• Time in Patent Office: 2,261 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 9/5033 considering data affinity
• CPC Class Codes: G06F 9/5044 considering hardware capabilities

Abstract

A computer-implemented method for assigning computing tasks to computers in a group is disclosed. The method includes determining, for each computer in a group of computers, an ability of the computer to execute tasks expected to be received by the group of computers; generating an ability indicator for each computer based on the ability determination for the computer; and assigning an incoming computing task to one of the computers using the ability indicator.

Claims

1. A computer-implemented method for assigning computing tasks to particular computers in a group of computers, the method comprising:

determining, for each computer, an ability of the computer to execute a number of differing tasks;

identifying, for each computer, a quantity of similarly-provisioned computers;

generating, for each computer, an indicator for the computer based on the determined ability of the computer, and based on the identified quantity of similarly-provisioned computers; and

assigning a particular task of the differing tasks to one or more computers based on the indicator of each computer, wherein the determined ability of the one or more computers is greater than a determined ability of a computer that has a lowest ability from among the remaining computers.

2. The method of claim 1, wherein assigning the particular task further comprises assigning the particular task to the one or more computers having a lowest indicator that are capable of executing the task.

3. The method of claim 2, further comprising applying a historical time window to tasks executed by the group of computers, and wherein generating the indicator further comprises generating the indicator for each computer using substantially only tasks performed during the time window.

4. The method of claim 1, further comprising transmitting data needed to execute the particular task to the assigned one or more computers.

5. The method of claim 1, wherein assigning the task to the one or more computers of the group of computers includes determining a cost of assigning the particular task to each computer, wherein the cost is a weighted combination of the indicator of the computer, a preemption impact of executing the particular task with the computer, and one or more other cost factors associated with the assignment of the particular task to the computer.

6. The method of claim 5, wherein the particular task is assigned to the one or more computers with the lowest cost among a sub-group of computers capable of executing the task.

7. The method of claim 1, wherein generating the indicator further comprises comparing the ability of the computer to execute the particular task to the indicator of other the remaining computers in the group of computers.

8. The method of claim 1, wherein assigning the particular task to one or more computers further comprises assigning the particular task to one or more computers within the group of computers that exhibits a least flexibility to execute future tasks that match a distribution corresponding to the tasks that are previously received.

9. The method of claim 1, wherein generating the indicator further comprises generating the indicator to reflect preferences of the differing tasks for certain computer features, and wherein a desirability of a computer is increased if the differing tasks that are capable of executing on that computer express a large number of preferences that are met by that computer.

10. The method of claim 1, further comprising identifying the tasks by identifying a historical grouping of tasks previously received by the group of computers.

11. The method of claim 10, wherein the historical grouping of tasks comprises the tasks currently executing on the group of computers.

12. The method of claim 10, wherein the historical grouping of tasks comprises tasks from a time period for a time of day corresponding to a time of day during which the tasks will be assigned.

13. A computer-implemented computer assignment system, comprising:

a cluster of heterogeneous computers connected to execute a group of tasks received by the cluster of heterogeneous computers;

a database storing values, for each computer, relating to an ability of the computer to execute a number of differing tasks, and storing values, for each computer, relating to a quantity of similarly-provisioned computers; and

a task scheduler to identify one or more computers from the cluster to be assigned a particular task of the group of tasks by identifying the one or more computers in the cluster whose assignment to execute the particular task will minimize a reduction in the cluster'"'"'s capability to execute other tasks from the group of tasks based on, for each computer, the ability of the computer, and based on the quantity of similarly-provisioned computers, wherein the ability of the one or more computers is greater than an ability of a computer that has a lowest ability from among the remaining computers.

14. The system of claim 13, wherein the group of tasks corresponds to tasks previously executed by the cluster.

15. The system of claim 13, wherein the group of tasks corresponds to tasks previously executed by the cluster during a time of day corresponding to a time when the task is to be assigned.

16. The system of claim 13, wherein the group of tasks includes tasks previously executed at least in part by another group of computers.

17. A computer-implemented computer assignment system, comprising:

a memory storing values, for each computer of a cluster of computers, relating to an ability of the computer to execute a number of differing tasks, and storing values, for each computer, relating to a quantity of similarly-provisioned computers;

means for identifying, for each computer, an indicator based on the stored ability value of the computer, and based on the quantity of similarly-provisioned computers; and

a task router to assign a particular task of the differing tasks to one or more computers based on the indicators of each computer, wherein the stored ability value of the one or more computers is greater than a stored ability value of a computer that has a lowest ability value from among the remaining computers.