Scheduling mapReduce tasks based on estimated workload distribution

• US 9,852,012 B2
• Filed: 08/26/2015
• Issued: 12/26/2017
• Est. Priority Date: 08/26/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Duan, Ning, Fan, Liya, Huang, He Yuan, Wang, Jian, Wang, Zhi Hu
• Primary Examiner(s): Kamran, Mehran
• Application Number:
  US14/835,766
• Publication Number:
  US 20170060630A1
• Time in Patent Office: 853 Days
• Field of Search: None
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method for scheduling MapReduce tasks includes receiving a set of task statistics corresponding to task execution within a MapReduce job, estimating a completion time for a set of tasks to be executed to provide an estimated completion time, calculating a soft decision point based on a convergence of a workload distribution corresponding to a set of executed tasks, calculating a hard decision point based on the estimated completion time for the set of tasks to be executed, determining a selected decision point based on the soft decision point and the hard decision point, and scheduling upcoming tasks for execution based on the selected decision point. The method may also include estimating a map task completion time and estimating a shuffle operation completion time. A computer program product and computer system corresponding to the method are also disclosed.

Claims

1. A method comprising:

receiving a set of task statistics corresponding to task execution within a MapReduce job;

estimating a completion time for a set of tasks to be executed to provide an estimated completion time;

calculating a soft decision point based on a convergence of a workload distribution corresponding to a set of executed tasks;

calculating a hard decision point (HDP) based on the estimated completion time for the set of tasks to be executed according to the equation HDP=max{0, map task completion time−

shuffle operation completion time};

determining a selected decision point based on the soft decision point and the hard decision point; and

scheduling and executing upcoming tasks based on the selected decision point.

2. The method of claim 1, wherein the set of task statistics includes a job input size, a cluster size, an average map process rate, a shuffle data size, and a network bandwidth.

3. The method of claim 1, wherein calculating the soft decision point comprises calculating a point at which a workload is most evenly distributed among available resources.

4. The method of claim 1, wherein estimating the completion time comprises estimating a map task completion time and estimating a shuffle operation completion time.

5. The method of claim 1, wherein scheduling upcoming tasks comprises scheduling a next set of tasks to be executed at the selected decision point.

6. The method of claim 1, wherein receiving a set of task statistics comprises receiving a convergence of a workload distribution corresponding to the set of executed tasks.

7. The method of claim 1, wherein the selected decision point is the lesser of the soft decision point and the hard decision point.

8. A computer program product comprising:

one or more computer readable storage media and program instructions stored on the one or more computer readable storage media, the program instructions comprising instructions to;

receive a set of task statistics corresponding to task execution within a MapReduce job;

estimate a completion time for a set of tasks to be executed to provide an estimated completion time;

calculate a soft decision point based on a convergence of a workload distribution corresponding to a set of executed tasks;

calculate a hard decision point (HDP) based on the estimated completion time for the set of tasks to be executed according to the equation HDP=max{0, map task completion time−

shuffle operation completion time};

determine a selected decision point based on the soft decision point and the hard decision point; and

schedule and execute upcoming tasks based on the selected decision point.

9. The computer program product of claim 8, wherein the set of task statistics includes a job input size, a cluster size, an average map process rate, a shuffle data size, and a network bandwidth.

10. The computer program product of claim 8, wherein program instructions to calculate the soft decision point comprise instructions to calculate a point at which a workload is most evenly distributed among available resources.

11. The computer program product of claim 8, wherein program instructions to estimate the completion time comprise instructions to estimate a map task completion time and estimating a shuffle operation completion time.

12. The computer program product of claim 8, wherein the selected decision point is the lesser of the soft decision point and the hard decision point.

13. A system comprising:

one or more computer processors;

one or more computer-readable storage media;

program instructions stored on the computer-readable storage media for execution by at least one of the one or more processors, the program instructions comprising instructions to;

receive a set of task statistics corresponding to task execution within a MapReduce job;

estimate a completion time for a set of tasks to be executed to provide an estimated completion time;

calculate a soft decision point based on a convergence of a workload distribution corresponding to a set of executed tasks;

calculate a hard decision point (HDP) based on the estimated completion time for the set of tasks to be executed according to the equation HDP=max{0, map task completion time−

shuffle operation completion time};

determine a selected decision point based on the soft decision point and the hard decision point; and

schedule and execute upcoming tasks based on the selected decision point.

14. The system of claim 13, wherein the set of task statistics includes a job input size, a cluster size, an average map process rate, a shuffle data size, and a network bandwidth.

15. The system of claim 13, wherein program instructions to calculate the soft decision point comprise instructions to calculate a point at which a workload is most evenly distributed among available resources.

16. The system of claim 13, wherein program instructions to estimate the completion time comprise instructions to estimate a map task completion time and estimating a shuffle operation completion time.

17. The system of claim 13, wherein the selected decision point is the lesser of the soft decision point and the hard decision point.