Computing cluster with latency control

• US 9,262,216 B2
• Filed: 02/14/2012
• Issued: 02/16/2016
• Est. Priority Date: 02/14/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Bodik, Peter, Ferguson, Andrew D., Kandula, Srikanth, Boutin, Eric
• Primary Examiner(s): Gillis, Brian J
• Assistant Examiner(s): Lin, Steve
• Application Number:
  US13/372,717
• Publication Number:
  US 20130212277A1
• Time in Patent Office: 1,463 Days
• Field of Search: 709/226
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A computing cluster operated according to a resource allocation policy based on a predictive model of completion time. The predictive model may be applied in a resource control loop that iteratively updates resources assigned to an executing job. At each iteration, the amount of resources allocated to the job may be updated based on of the predictive model so that the job will be scheduled to complete execution at a target completion time. The target completion time may be derived from a utility function determined for the job. The utility function, in turn, may be derived from a service level agreement with service guarantees and penalties for late completion of a job. Allocating resources in this way may maximize utility for an operator of the computing cluster while minimizing disruption to other jobs that may be concurrently executing.

Claims

1. A method implemented by one or more processing units, the method comprising:

analyzing a structure of a job to determine;

dependencies among tasks of the job, the dependencies including one task using output from another task, and

a critical path of the job;

building a model of execution time of the job by a computing cluster, the model based on the dependencies among the tasks and a length of the critical path, the model relating aggregate time spent to complete the tasks of the job to resources allocated to the job; and

at a plurality of times;

assessing processing remaining on the job,

updating the model based on the processing remaining, the updating including considering the dependencies, the critical path, and execution failures of individual tasks of the job, and

adjusting the resources allocated to the job based on the updated model and a utility function.

2. The method of claim 1, wherein:

the utility function defines utility for completing the job as a function of the execution time to complete the job.

3. The method of claim 2, wherein:

the job is submitted by a customer of an operator of the computing cluster;

the customer has a service level agreement with the operator defining the execution time to complete the job; and

the utility function is based on the service level agreement.

4. The method of claim 1, the method further comprising:

at another time;

assessing the processing remaining on the job, and

not updating the model based on the processing remaining after considering the dependencies, the critical path, and any execution failures of the individual tasks of the job.

5. The method of claim 1, wherein:

the adjusting the resources allocated to the job comprises selecting an amount of resources to allocate to the job based on a computation to increase utility described by the utility function.

6. The method of claim 1, wherein:

the building the model occurs prior to the plurality of times by simulating the execution of the job for a plurality of levels of the resources allocated to the job.

7. The method of claim 1, wherein the analyzing the structure comprises:

analyzing a code base of the job.

8. The method of claim 1, wherein:

the analyzing the structure of the job comprises tracking progress of the job during one or more prior executions of the job; and

at least two of the tasks are executed in parallel according to the structure.

9. At least one computer-readable memory device or storage device storing computer-executable instructions that, when executed by one or more processing devices, cause the one or more processing devices to perform acts comprising:

building a model of execution of a job by a computing cluster, the building comprising;

analyzing a structure of the job to determine dependencies among tasks of the job, a completion time of the job, and a length of a critical path of the job,

simulating task failures in execution of the job, and

relating aggregate time spent to complete the tasks of the job to an allocation of resources of the computing cluster for the execution of the job;

updating the model based on progress in an actual execution of the job, the updating including considering the dependencies, the critical path, and actual execution failures of the tasks of the job; and

dynamically allocating the resources of the computing cluster to the job based on the updated model.

10. The at least one computer-readable memory device or storage device of claim 9, wherein:

the dynamically allocating the resources comprises adjusting the resources based on one or more of;

a utility function relating the completion time of the job to a metric of utility;

a deadline associated with the job;

or

a requested completion time for the job.

11. The at least one computer-readable memory device or storage device of claim 9, wherein:

the dynamically allocating the resources comprises adjusting the resources based on a utility function that considers a required completion time associated with the job.

12. The at least one computer-readable memory device or storage device of claim 9, wherein:

the simulating the task failures comprises adjusting the completion time based on time required to re-perform a failed individual task.

13. The at least one computer-readable memory device or storage device of claim 9, the acts further comprising estimating progress of the job, the estimating comprising computing, for each of a plurality of stages in the job, a quantity indicating time spent completing individual tasks that are associated with the stages executing and enqueued on the computing cluster.

14. The at least one computer-readable memory device or storage device of claim 9, wherein:

the completion time of the job is associated with the length of the critical path of the job.

15. The at least one computer-readable memory device or storage device of claim 9, wherein:

the analyzing the structure of the job to determine the dependencies among the tasks of the job includes determining that at least one individual task depends from two other individual tasks.

16. A system comprising:

a plurality of processing units; and

a scheduler configured to execute on the plurality of processing units and cause the plurality of processing units to;

receive a job for execution, the job comprising tasks,

construct a model of the execution of the job based on a directed graph representing dependencies among the tasks of the job and a length of a critical path of the job, the model relating aggregate time spent to complete the tasks to computing resources allocated to the job;

updating the model based on assessed progress of the execution of the job, the updating considering processing time associated with failures during the execution of some of the tasks, and

dynamically allocate the computing resources based on the updated model.

17. The system of claim 16, wherein:

the system further comprises a database associating service level data with the job; and

the computing resources are dynamically allocated based on a determination, made using the model, of an amount of the computing resources to achieve a completion time indicated by the service level data.

18. The system of claim 16, wherein nodes of the directed graph represent individual tasks of the job.

19. The system of claim 18, wherein edges of the directed graph represent the dependencies among the tasks of the job.

20. The system of claim 16, wherein:

the scheduler is further configured to determine the assessed progress of the execution of the job by computing, for stages in the job, a quantity indicating time spent for the stages.