[
https://issues.apache.org/jira/browse/MAPREDUCE-706?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Matei Zaharia updated MAPREDUCE-706:
------------------------------------
Attachment: mapreduce-706.patch
Here's a patch adding this feature. The patch includes MAPREDUCE-548 because it
depends on that issue.
This patch performs a fairly major restructuring of the fair scheduler to
support different scheduling algorithms within each pool. However, the
resulting code is simpler, more flexible and more efficient than the current
fair scheduler. Many of the changes in the patch are also just changes to unit
tests, which were necessary because deficits were removed (affecting behavior
slightly in some tests) and the names of some internal data structures changed.
At a high level, the patch changes the scheduler to perform hierarchical
scheduling, where a pool is chosen to assign a task to, and then the pool is
asked to choose a task from among its jobs. The pool can choose to use either
FIFO or fair sharing to do this.
To allow the same fair sharing code to be used across pools and across jobs,
the patch introduces a new abstract class called Schedulable that can represent
both a job (as JobSchedulable) and a pool (as PoolSchedulable). Schedulables
can be asked to assign tasks and can be queried for metrics used in various
scheduling algorithms, such as current number of running tasks, demand (number
of tasks required), weight, fair share, priority, etc. PoolSchedulables
aggregate the metrics from the jobs they contain. There are separate sets of
Schedulables for maps and reduces, to let the same code be reused for both task
types.
Apart from this large-scale change, the patch includes a few smaller but
important changes that simplify the fair scheduler and let existing features to
work with the new hierarchical model:
* Deficits are no longer used for fair sharing. Instead, we just assign tasks
to the job/pool with the fewest running tasks (scaled by weight). The scheduler
originally used deficits because they work well in CPU and packet scheduling
and because they let jobs "catch up" after temporary unfairness, but we found
that this can lead to bad behavior in a system with long tasks like Hadoop
(MAPREDUCE-544). In addition, preemption (MAPREDUCE-551) can now be used to
ensure jobs aren't starved of their share for too long a time. Deficits also
don't make sense with FIFO, so it would have been difficult to use the existing
code there. Therefore this patch removes deficits and moves to a simpler form
of fair sharing. The new algorithm should also let small jobs start faster,
without having to wait to accumulate a deficit.
* A new algorithm based on binary search is used for computing fair shares.
Computing weighted fair shares in the presence of minimum shares and maximum
shares (due to jobs whose demand is less than their share) is fairly tricky,
and the previous algorithm ignlred the low-demand case and ran in quadratic
time in the number of jobs. The new algorithm handles these cases, runs in
linear time in the number of jobs, and is only about 60 lines of code.
* Preemption now happens at a pool level and not at a job level. Up until now
the fair scheduler has contained only per-job data structures, so each job had
a minimum share assigned (a fraction of its pool) and kept track of whether it
was starved. This could lead to less than the right amount of tasks being
preempted if, for example, jobs' min shares rounded down to less than the share
of the pool. Per-job minimum shares also can't easily be assigned in FIFO
pools. Instead, the new code keeps track of min shares and starvation at the
level of pools. This leads to incompatible behavior with MAPREDUCE-551, but
that code has not been in any release yet so it should be fine to change it
here.
The new fair scheduler structure should make it straightforward to support
features such as maximum shares for pools (MAPREDUCE-698), new scheduling
algorithms within pools (e.g. shortest job first), and even sub-pools within
pools (e.g. an organization pool can contain a sub-pool for each user). Over
the next few days, I'll also post a design document detailing the new scheduler
structure and algorithms.
> Support for FIFO pools in the fair scheduler
> --------------------------------------------
>
> Key: MAPREDUCE-706
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-706
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: contrib/fair-share
> Reporter: Matei Zaharia
> Attachments: mapreduce-706.patch
>
>
> The fair scheduler should support making the internal scheduling algorithm
> for some pools be FIFO instead of fair sharing in order to work better for
> batch workloads. FIFO pools will behave exactly like the current default
> scheduler, sorting jobs by priority and then submission time. Pools will have
> their scheduling algorithm set through the pools config file, and it will be
> changeable at runtime.
> To support this feature, I'm also changing the internal logic of the fair
> scheduler to no longer use deficits. Instead, for fair sharing, we will
> assign tasks to the job farthest below its share as a ratio of its share.
> This is easier to combine with other scheduling algorithms and leads to a
> more stable sharing situation, avoiding unfairness issues brought up in
> MAPREDUCE-543 and MAPREDUCE-544 that happen when some jobs have long tasks.
> The new preemption (MAPREDUCE-551) will ensure that critical jobs can gain
> their fair share within a bounded amount of time.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
