Scheduling Mapreduce Jobs in the Presence of Priority Classes

• US 20130031558A1
• Filed: 10/03/2012
• Published: 01/31/2013
• Est. Priority Date: 05/26/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wolf, Joel L., Rajan, Deepak, Hildrum, Kirsten W., Khandekar, Rohit M., Balmin, Andrey
• Granted Patent: US 8,869,159 B2
• Time in Patent Office: Days
• 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 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.