Scheduling MapReduce jobs in the presence of priority classes

• US 8,869,159 B2
• Filed: 10/03/2012
• Issued: 10/21/2014
• Est. Priority Date: 05/26/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Balmin, Andrey, Hildrum, Kirsten W., Khandekar, Rohit M., Rajan, Deepak, Wolf, Joel L.
• Primary Examiner(s): KAWSAR, ABDULLAH AL
• Application Number:
  US13/633,954
• Publication Number:
  US 20130031558A1
• Time in Patent Office: 748 Days
• Field of Search: None
• US Class Current: 718/103
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

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.

Claims

1. A method for scheduling MapReduce jobs within and across multiple priority classes, wherein the method comprises:

obtaining a preferred ordering for multiple MapReduce jobs within each of the multiple priority classes based on a given metric, wherein each of the multiple priority classes comprises two or more of the multiple MapReduce jobs, and wherein the given metric is selected from a plurality of metrics based on a job type of the multiple MapReduce jobs, wherein the plurality of metrics comprises (i) a metric associated with weighted response time, (ii) a metric associated with weighted number of tardy jobs, (iii) a metric associated with weighted tardiness, (iv) a metric associated with weighted lateness and (v) a metric associated with service level agreement cost;

prioritizing the multiple priority classes subject to one or more dynamic minimum slot guarantees for each priority class to generate an ordering of the multiple priority classes; and

iteratively employing a MapReduce scheduler, according to the ordering of the multiple priority classes, to allocate resources at the level of priority classes to execute all of the two or more MapReduce jobs within a first priority class from the ordering of the multiple priority classes prior to executing a MapReduce job in the subsequent priority class in the ordering of the multiple priority classes, wherein said executing the two or more MapReduce jobs within the first priority class comprises executing the two or more MapReduce jobs according to said preferred ordering for the MapReduce jobs within the first priority class.

2. The method of claim 1, further comprising repeating said iteratively employing a MapReduce scheduler until there are no idle processors in the MapReduce schedule or no further need for additional allocations.

3. The method of claim 1, wherein said prioritizing comprises preventing starvation of one or more jobs in lower priority classes.

4. The method of claim 1, wherein within the multiple priority classes, class minima are appropriately allocated amongst the multiple jobs.

5. The method of claim 1, wherein said iteratively employing a MapReduce scheduler comprises allocating any additional slack slots in a cluster in an intelligent manner to one or more jobs.

6. The method of claim 1, further comprising performing bookkeeping after each iteration of employing the MapReduce scheduler to provide input data to a subsequent scheduling scheme.

7. The method of claim 1, further comprising optimizing a scheduling metric within one or more given constraints.

8. 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.

9. 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.

10. The method of claim 1, further comprising re-optimizing performance of the multiple MapReduce jobs when input data changes.