Reducer delay scheduling [610335]

Reducer delay scheduling
HADOOP MapReduce
C O U R S E : D I S T R I B U T E D S Y S T E M S
M A S T E R P R O G R A M : A R T I F I C I A L I N T E L L I G E N C E A N D D I S T R I B U T E D C O M P U T I N G , Y E A R I .
F A C U LT Y O F M AT H E M AT I C S A N D C O M P U T E R S C I E N C E , W E S T U N I V E R S I T Y O F T I M I S O A R A , R O M A N I A .
S T U D E N T:
C O D R U TA G U L E R

Introduction
One Hadoop job is made from parallel map tasks, a shuffle and sort phase.
Users are writing code for map and reduce tasks, while the Hadoop MapReduce framework manages shuffling, sorting,
and coordination of parallel tasks.

Problem illustration
The map tasks arerunning onthelocal nodes anjobtracker schedules tasks onthe free nodes from the
cluster ,inbelow Job Tracker need toschedule with high priority J3onnode 6and the data block isnot
available .Ifadelay isapplied inthis case ,JobTracker willskip J3until aslot become available .With ahigh
priority jobcauses higher jobresponse time .Solution tothis problem isscheduling thejobs intheway to
order toreduce theoverload ofJobTracker .

STATEMENT
Shuffle and reduce task durations in a job are strongly affected by whether they start before or
after completion of the last map task

Reducer scheduling
Start time for shuffle and reduce task can be controlled by changing job parameter :
reduce.slowstart.completedmaps .
1) if a default value 0.05 => shuffle/reduce tasks are started when 5% of map tasks complete.
2) if we change to 90% => shuffle/reduce tasks is delayed until 90% of map tasks are complete
3) if we change to 1%= > shuffle/reduce tasks begins after just 1% of map tasks are complete

Reducer Delay
Task lead time using default parameters

Reducer Delay
Shuffle/reduce tasks is delayed until 90% of map tasks are complete

Reducer Delay
Start of shuffle/reduce tasks begins after just 1% of map tasks are complete

Algorithm : Naive Fair Sharing
when a heartbeat is received from node n:
if n has a free slot then
sort jobs in increasing order of number of running tasks
for j in jobs do
if j has unlaunched task t with data on n then
launch t on n
else if j has unlaunched task t then
launch t on n
end if
end for
end if

Algorithm : Naive Fair Sharing
In order that waiting have a significant impact on job response , is needed that one hold of one
any below condition:
◦Many jobs
◦Small jobs
◦Long jobs
Data locality problems
◦Head -of-line Scheduling
◦Sticky Slot

Algorithm : Fair Sharing with Simple
Delay Scheduling
Input: RT: set of unscheduled reduce tasks
Algorithm 2 Fair Sharing with Simple Delay Scheduling
Initialize j.skipcount to 0 for all jobs j.
when a heartbeat is received from node n:
if n has a free slot then
sort jobs in increasing order of number of running tasks
for j in jobs do
if j has unlaunched task t with data on n then
launch t on n
set j.skipcount = 0
else if j has unlaunched task t thenif j.skipcount ≥ D then
launch t on n
else
set j.skipcount = j.skipcount +1
end if
end if
end for
end if

Algorithm : Fair Sharing with Simple
Delay Scheduling
◦The non -locality decreases exponentially with D
◦The amount of waiting by a job required to achieve a given level of locality is a fraction of the average
task length and linearly decrease with number of slots per node L

Algorithm : Delay Scheduling in HFS
Delay Scheduling in HFS
Maintain three variables for each job j, initialized as
j.level = 0, j.wait = 0, and j.skipped = f alse.
when a heartbeat is received from node n:
for each job j with j.skipped = true, increase j.wait by the time
since the last heartbeat and set j.skipped = f alse
if n has a free slot then
sort jobs using hierarchical scheduling policy
for j in jobs do
if j has a node -local task t on n then
set j.wait = 0 and j.level = 0
return t to n
else if j has a rack -local task t on n and ( j.level ≥ 1 orj.wait ≥ W1) then
set j.wait = 0 and j.level = 1
return t to n
else if j.level = 2 or ( j.level = 1 and j.wait ≥ W2) or
(j.level = 0 and j.wait ≥ W1 +W2) then
set j.wait = 0 and j.level = 2
return any unlaunched task t in j to n
else
set j.skipped = true
end if
end for
end if

Algorithm : Delay Scheduling in HFS
◦Replication improves performance and also decreases it as the threshold limit is crossed. By default
HDFS replicates each block into 3 locations. Two copies are stored on different nodes of the same rack
and one copy in different rack for reliability.

Conclusion
Reducer willhave delay ifisnotscheduled aadequate bandwidth between them and theMappers and willdecrease theperformance of
thecluster .
Ifismoved theload ofJob Tracker onTask Tracker, thealgorithms /experiments show areduced execution time foraJob, when the
shuffle traffic canmaximize theavailable bandwidth .