Scheduling Mapreduce Jobs in the Presence of Priority Classes

Abstract

Techniques for scheduling one or more MapReduce jobs in a presence of one or more priority classes are provided. The techniques include obtaining a preferred ordering for one or more MapReduce jobs, wherein the preferred ordering comprises one or more priority classes, prioritizing the one or more priority classes subject to one or more dynamic minimum slot guarantees for each priority class, and iteratively employing a MapReduce scheduler, once per priority class, in priority class order, to optimize performance of the one or more MapReduce jobs.

1 . A method for scheduling one or more MapReduce jobs in a presence of one or more priority classes, wherein the method comprises:
 obtaining a preferred ordering for one or more MapReduce jobs, wherein the preferred ordering comprises one or more priority classes;   prioritizing the one or more priority classes subject to one or more dynamic minimum slot guarantees for each priority class; and   iteratively employing a MapReduce scheduler, once per priority class, in priority class order, to optimize performance of the one or more MapReduce jobs.   
     
     
         2 . The method of  claim 1 , further comprising repeating the iterative process until there are no idle processors in the MapReduce schedule or no further need for additional allocations. 
     
     
         3 . The method of  claim 1 , wherein each job belongs to a priority class. 
     
     
         4 . The method of  claim 1 , wherein prioritizing the one or more priority classes subject to one or more dynamic minimum slot guarantees for each priority class comprises preventing starvation of one or more jobs in lower priority classes. 
     
     
         5 . The method of  claim 1 , wherein within the one or more priority classes, class minima are appropriately allocated amongst the one or more jobs. 
     
     
         6 . The method of  claim 1 , wherein iteratively employing a MapReduce scheduler, once per priority class, in priority class order comprises allocating any additional slack slots in a cluster in an intelligent manner to the one or more jobs. 
     
     
         7 . The method of  claim 1 , further comprising performing bookkeeping after each iteration to provide input data to a subsequent scheduling scheme. 
     
     
         8 . The method of  claim 1 , further comprising optimizing a scheduling metric within one or more given constraints. 
     
     
         9 . The method of  claim 1 , further comprising providing, via a scheduling manager component, a revised minimum number of slots per job, wherein the minimum is greater than or equal to an original minimum. 
     
     
         10 . The method of  claim 1 , further comprising implementing a Malleable Packing Scheme and implementing only a first layer of malleable packing with an expectation that a revised schedule will arrive in sufficient time. 
     
     
         11 . The method of  claim 1 , further comprising re-optimizing performance of the one or more MapReduce jobs when input data changes. 
     
     
         12 . The method of  claim 1 , further comprising providing a system, wherein the system comprises one or more distinct software modules, each of the one or more distinct software modules being embodied on a tangible computer-readable recordable storage medium, and wherein the one or more distinct software modules comprise a priority control module, a preemptive priority class allocation module, a non-preemptive priority subclass allocation module, and an enhanced FLEX scheduling module executing on a hardware processor. 
     
     
         13 . A computer program product comprising a tangible computer readable recordable storage medium including computer useable program code for scheduling one or more MapReduce jobs in a presence of one or more priority classes, the computer program product including:
 computer useable program code for obtaining a preferred ordering for one or more MapReduce jobs, wherein the preferred ordering comprises one or more priority classes;   computer useable program code for prioritizing the one or more priority classes subject to one or more dynamic minimum slot guarantees for each priority class; and   computer useable program code for iteratively employing a MapReduce scheduler, once per priority class, in priority class order, to optimize performance of the one or more MapReduce jobs.   
     
     
         14 . The computer program product of  claim 13 , wherein the computer useable program code for iteratively employing a MapReduce scheduler, once per priority class, in priority class order comprises computer useable program code for allocating any additional slack slots in a cluster in an intelligent manner to the one or more jobs. 
     
     
         15 . The computer program product of  claim 13 , further comprising computer useable program code for performing bookkeeping after each iteration to provide input data to a subsequent scheduling scheme. 
     
     
         16 . The computer program product of  claim 13 , further comprising computer useable program code for repeating the iterative process until there are no idle processors in the MapReduce schedule or no further need for additional allocations. 
     
     
         17 . The computer program product of  claim 13 , further comprising computer useable program code for providing, via a scheduling manager component, a revised minimum number of slots per job, wherein the minimum is greater than or equal to an original minimum. 
     
     
         18 . The computer program product of  claim 13 , further comprising computer useable program code for re-optimizing performance of the one or more MapReduce jobs when input data changes. 
     
     
         19 . A system for scheduling one or more MapReduce jobs in a presence of one or more priority classes, comprising:
 a memory; and   at least one processor coupled to the memory and operative to:
 obtain a preferred ordering for one or more MapReduce jobs, wherein the preferred ordering comprises one or more priority classes; 
 prioritize the one or more priority classes subject to one or more dynamic minimum slot guarantees for each priority class; and 
 iteratively employ a MapReduce scheduler, once per priority class, in priority class order, to optimize performance of the one or more MapReduce jobs. 
   
     
     
         20 . The system of  claim 19 , wherein the at least one processor coupled to the memory operative to iteratively employ a MapReduce scheduler, once per priority class, in priority class order is further operative to allocate any additional slack slots in a cluster in an intelligent manner to the one or more jobs. 
     
     
         21 . The system of  claim 19 , wherein the at least one processor coupled to the memory is further operative to perform bookkeeping after each iteration to provide input data to a subsequent scheduling scheme. 
     
     
         22 . The system of  claim 19 , wherein the at least one processor coupled to the memory is further operative to optimize a scheduling metric within one or more given constraints. 
     
     
         23 . The system of  claim 19 , wherein the at least one processor coupled to the memory is further operative to provide, via a scheduling manager component, a revised minimum number of slots per job, wherein the minimum is greater than or equal to an original minimum. 
     
     
         24 . The system of  claim 19 , wherein the at least one processor coupled to the memory is further operative to re-optimize performance of the one or more MapReduce jobs when input data changes. 
     
     
         25 . The system of  claim 19 , wherein the at least one processor coupled to the memory is further operative to repeat the iterative process until there are no idle processors in the MapReduce schedule or no further need for additional allocations.