Job scheduling using expected server performance information

Patent metadata

Field	Value
Publication number	US-9442760-B2
Application number	US-201414506482-A
Country	US
Kind code	B2
Filing date	Oct 3, 2014
Priority date	Oct 3, 2014
Publication date	Sep 13, 2016
Grant date	Sep 13, 2016

Abstract

A job scheduler that schedules ready tasks amongst a cluster of servers. Each job might be managed by one scheduler. In that case, there are multiple job schedulers which conduct scheduling for different jobs concurrently. To identify a suitable server for a given task, the job scheduler uses expected server performance information received from multiple servers. For instance, the server performance information might include expected performance parameters for tasks of particular categories if assigned to the server. The job management component then identifies a particular task category for a given task, determines which of the servers can perform the task by a suitable estimated completion time, and then assigns based on the estimated completion time. The job management component also uses cluster-level information in order to determine which server to assign a task to.

First claim

What is claimed is:

1. A computer program product comprising one or more computer-readable memories storing computer-executable instructions which, when executed by one or more processors cause the one or more processors to perform a computer-implemented method that controls how a cluster system determines a particular server among a plurality of servers to which a job assignment associated with a computational job is to be given for execution, and wherein the computer-implemented method comprises acts of:
maintaining at each server expected server performance information comprising expected performance parameters of tasks having varying characteristics if assigned to the server, wherein the expected server performance information is based on tracking expected performance parameters for different categories of tasks;
maintaining cluster-level information that is not specific to any given server;
for a given computational job to be executed at the cluster system, identifying a plurality of tasks associated with the computational job;
for the given computational job, identifying task dependencies among the plurality of tasks;
for the given computational job, determining which of the plurality of tasks is ready for execution based on the task dependencies;
at a plurality of job schedulers, accessing cluster level information through an interface with a cluster management component, and accessing expected performance information regarding one or more server's capability to handle tasks for a particular category of tasks to which a task to be assigned belongs, the expected performance information being accessed by the plurality of job schedulers through either the interface with the cluster management component, or an interface with the plurality of servers;
for each task that is ready for execution, at least one of the plurality of job schedulers selecting which server to assign a task to based on (i) expected server performance information accessed by the plurality of job schedulers, and (ii) cluster level information accessed by the plurality of job schedulers; and
submitting a request to the selected server to perform one or more of the tasks that are ready for execution.

2. The computer program product in accordance with claim 1 , wherein selecting which server to assign a task to is performed for only one computational job at a time.

3. The computer program product in accordance with claim 1 , wherein the expected performance parameters of tasks having varying characteristics if assigned to the server comprises:
for each of a plurality of task categories, an estimated wait time estimating how long before the corresponding server will be able to process tasks of the corresponding task category.

4. The computer program product in accordance with claim 3 , wherein the plurality of task categories is categorized by server resources to be used to perform the corresponding tasks.

5. The computer program product in accordance with claim 4 , wherein submitting a request to the selected server comprises notifying the selected server of the server resources to be used to perform the corresponding tasks.

6. The computer program product in accordance with claim 4 , wherein the server resources by which the plurality of task categories are categorized comprises server processing resources.

7. The computer program product in accordance with claim 4 , wherein the server resources by which the plurality of task categories are categorized comprises server memory resources.

8. The computer program product in accordance with claim 1 , wherein selecting which server to assign a task to based on (i) expected server performance information received regarding a server's capability to handle tasks for a particular category of tasks to which the task to be assigned belongs, and (ii) cluster level information, comprises:
estimating a task completion time that estimates the time by which the task could be completed by if performed by a particular server; and
determining that the estimated task completion time associated with the particular server is acceptable.

9. The computer program product in accordance with claim 8 , wherein determining that the estimated task completion time associated with the particular server is acceptable comprises:
for each of one or more other servers, estimating a task completion time that estimates the time by which the task could be completed by if performed by the other corresponding server; and
determining that the estimated task completion time for the particular server is the least of the estimated completion times for the task.

10. The computer program product in accordance with claim 8 , wherein estimating a task completion time that estimates the time by which the task could be completed by if performed by a particular server comprises factoring in confidence of the expected server's performance information.

11. The computer program product in accordance with claim 10 , wherein estimating a task completion time that estimates the time by which the task could be completed by if performed by a particular server comprises factoring in staleness of the expected server's performance information.

12. The computer program product in accordance with claim 8 , wherein the estimated task completion time comprises an estimated wait time before the particular server is estimated to be available to initiate the task.

13. The computer program product in accordance with claim 12 , wherein the estimated task completion time comprises factoring in a probability of success of task completion.

14. The computer program product in accordance with claim 13 , wherein the probability of success of task completion is estimated by using the cluster-level information.

15. The computer program product in accordance with claim 12 , wherein the estimated task completion time comprises an initialization time expected for the particular server to acquire execution files to be used to perform the task.

16. The computer program product in accordance with claim 12 , wherein the estimated task completion time comprises an estimated run time for performing the tasks by the particular server once the task is initiated.

17. The computer program product in accordance with claim 16 , wherein the estimated run time comprises processor run time and input/output (I/O) time.

18. The computer program product in accordance with claim 17 , wherein input/output time is estimated by using the cluster-level information.

19. The computer program product in accordance with claim 1 , wherein the computer-implemented method further comprises:
monitoring performance of a task by a particular server after the particular server is requested to perform the task.

20. The computer program product in accordance with claim 19 , wherein monitoring performance of a task by a particular server comprises receiving updates on server performance from the particular server.

21. The computer program product in accordance with claim 19 , the computer-implemented method further comprises taking corrective action if the task is not being performed as expected.

22. The computer program product in accordance with claim 21 , wherein the corrective action comprises assigning the task to a different server.

23. The computer program product in accordance with claim 22 , wherein assigning the task to a different server is performed without immediately deleting the task from the particular server that was first assign

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Boutin Eric
• Ekanayake Jaliya
• Lin Wei
• Shi Bin
• Zhou Jingren

Classifications

• G06F9/5016

  the resource being the memory · CPC title

• G06F2209/5017

  Task decomposition · CPC title

• G06F2209/501

  Performance criteria · CPC title

• G06F9/4806

  Task transfer initiation or dispatching · CPC title

• G06F9/4881 Primary

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