With Hadoop being a great sell
story for parallel data processing, the infrastructure guys are trying to
squeeze the maximum buck out of it by pooling multiple consumers. No wonder,
there is competition among Hadoop jobs and you guessed it higher incidence of
errors. In this post, we analyze an approach for fair scheduling tasks by
determining health of a node.
We begin by describing Delay scheduling introduced first in DelayScheduling: A Simple Technique for Achieving Locality and Fairness in
Cluster Scheduling (2010) by Matei Zaharia , Khaled Elmeleegy , Dhruba
Borthakur , Scott Shenker , Joydeep Sen Sarma , Ion Stoica . Thereafter we describe the job scheduling
based on Node health degree published in Researchon Job Scheduling Algorithm in Hadoop by Yang Xia, Lei Wang, Qiang Zhao,
Gongxuan Zhang.
The justice done by fair scheduling is
subject to criticism of being too fair or unfair at times. It has been
demonstrated to be suspect to head of line scheduling (allocating the top task
in sorted queue to free node) and sticky slots (possibility of being allocated
to same node again and again).
Further, it suffers from problem of
not being able to preserve data locality, the placement
of computation near its input data. “Locality
is crucial for performance in large clusters because
network bisection
bandwidth becomes a bottleneck”
Enter delay scheduling, “in which a job waits for a limited
amount of time for a scheduling opportunity on a node that has data for it. …
When a node requests a task, if the head-of-line job cannot launch a local task, we skip it and
When a node requests a task, if the head-of-line job cannot launch a local task, we skip it and
look at subsequent jobs. However, if a
job has been skipped long enough, we start allowing it to launch non-local
tasks, to avoid starvation”
Snapshot of Hadoop Fair Scheduler algorithm with Delay
scheduling:
The above approach sounds pretty good with the data locality
taken care. However, Xia et al did not seem quite happy with it. Their
contention has been that what if the nodes are not healthy and error prone?
What is the use of fairly scheduling a task on a node which is not fit enough
to complete the task?
Xia, Wang, Zhao and Zhang have therefore tried to identity
variables that define a node and a task, called characteristic variables.
“The characteristic
variables of task describe resource usage and demand for MapReduce task…The
characteristic variables of node represent the status and quality of computing
resources on a node”
Characteristic Variables
|
|
Task
|
Node
|
average CPU utilization cusage
average I/O utilization Iusage
average memory usage Musage
|
average CPU idle rate Cldle
average I/O idle rate Ildle
average free memory Mldle
|
The scheduling algorithm is further outlined below:
“1) When an idle task slot
can be used, a pool is chosen according to the Fair scheduler;
2) if the node on which the idle task is located is
healthy, then go to 5;
3) if the node on which the idle task is located is sub
healthy, characteristic variables of the node are separately multiplied by the
reciprocal of Health Degree of node , then go to 5;
4) if the node on which the idle task is located is
unhealthy, then go to 8,and set timer on node ,its Health Degree is multiplied
by 0.9 every x minutes until it reaches the state of sub healthy;
5) Computing Euclidean distances between characteristic
variables of job task and characteristic variables of node, sorting them from
small to large;
6) Choosing an appropriate job according to Delay
Scheduler in the sorted set;
7) Assigning the task of a chosen job to a task slot to
run;
8) Finish”
Take note of step 3 where
the sub healthy nodes characteristics are ‘loaded’ to arrive at a fairness determined
by health.
We all know schedulers play a major role in architecture of some of the most complex systems as we discussed in one of our earlier post on multimedia search. A lot of text and code has been written on fair and capacity scheduler. This paper definitely describes a unique approach but further tests on high load multi-use clusters can further demonstrate the usage and possible incorporation in future code base.
Comments
Post a Comment