Scheduling mapReduce tasks based on estimated workload distribution

#The present invention relates generally to the field of task scheduling, and more specifically to scheduling MapReduce tasks.

#MapReduce is a programming model and an associated implementation for processing and generating large data sets with a parallel, distributed algorithm on a cluster. A MapReduce program is composed of a Map procedure that performs filtering and sorting, and a Reduce procedure that performs a summary operation. A MapReduce system orchestrates the processing by marshalling the distributed servers, running the various tasks in parallel, managing all communications and data transfers between the various parts of the system, and providing for redundancy and fault tolerance. MapReduce systems are therefore responsible for efficiently managing workloads associated with a job.

#As disclosed herein, 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.

#FIG. 1 is a functional block diagram depicting a MapReduce infrastructure in accordance with some embodiments of the present invention;

#FIG. 2 is a functional block diagram depicting a decision point module in accordance with some embodiments of the present invention;

#FIG. 3 is a flowchart depicting a decision point selection method in accordance with one embodiment of the present invention;

#Existing methods for managing MapReduce workloads include allocating heterogeneous hardware resources, allocating additional task slots and processing said slots in parallel, or customizing a partitioned interface to split input data for reduce tasks into more manageable chunks. These methods pose a number of problems, however, such as an inability to achieve an exact load balance, overhead costs associated with parallel processing, and a lack of consistency and accuracy. All of these existing methods make scheduling decisions at different points; some make scheduling decisions after a first map task is finished, and some make scheduling decisions after all map tasks are finished. Scheduling tasks after the first map task is finished creates no delay, but also creates a poor load balance. Scheduling tasks after all map tasks are completed creates a good load balance, but also creates a long delay in the process. Disclosed herein is a method for determining a decision point that optimizes load balance and minimizes delay.

#FIG. 1 is a functional block diagram depicting a MapReduce infrastructure 100 in accordance with some embodiments of the present invention. As depicted, MapReduce infrastructure 100 includes a task tracker 110 and a job tracker 150. MapReduce infrastructure 100 may be utilized to manage a workload associated with MapReduce tasks.

#As depicted, task tracker 110 includes a map module 120, a reduce module 130, and a heartbeat sender 140. Each MapReduce job may comprise many individual tasks that task tracker 110 monitors and executes. In particular, map module 120 monitors and executes map tasks and reduce module 130 monitors and executes reduce tasks. Map module 120 includes a map task runner 122 and a map info collector 124. Map task runner 122 is configured to execute map operations corresponding to a task. Map information collector 124 is configured to receive information corresponding to the map operations executed by map task runner 122. In one embodiment, map information collector 124 is configured to monitor map task runner 122 and collect information corresponding to the tasks executed by map task runner 122. Map info collector 124 may also be configured to send information it collects to heartbeat sender 140.