[
https://issues.apache.org/jira/browse/MAPREDUCE-2162?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12926411#action_12926411
]
Joydeep Sen Sarma commented on MAPREDUCE-2162:
----------------------------------------------
it seems that the first thing to do is switch from deciding speculations based
on progress rates and instead make decisions based by comparing the remaining
time for a task (which can be computed using the progress rate) and the average
completion time of tasks of the same type/job. justifications:
- i asked Matei yesterday whether there was any fundamental reason for using
progress rates in their original work. he didn't seem to recollect any.
- let's assume for a minute that we used task durations instead of progress
rates in the same equation (ie. speculate task T if duration(T) >
avg_duration(Job) + stddev_duration(job)). this does not suffer from the
problem described in this jira. as a stalled task runs longer and longer - it
eventually will go above the RHS.
- it's much easier to describe the benefit of a speculation decision in terms
of potential time saved. for example - if we speculated _only_ the slowest task
(T ~N~ ) - then the best case time saved on the job becomes T ~N~ - T ~N-1~ .
It's much easier for users/admins to understand speculation decisions that can
be explained in terms of potential latency savings. It's also easier to build
cost models (latency reduction, cpu cycles saved) based on run time (as opposed
to progress rates).
- if in future #rows processed are available - then they can be accomodated -
One can normalize the task duration with the number of rows and use that
instead of the raw duration time.
---
Assuming we use task durations - we still need to decide on a speculation
criteria. There are couple of criteria that already in place (for us):
- don't speculate tasks for first LAG seconds
- don't speculate tasks that are projected (based on progress rate) to complete
in N seconds (MAPREDUCE-2062)
One other negative criteria is obvious. Assume we are dealing with a task with
projected remaining time _R_ (using progress rate), total time _T_ where the
job's average task duration is _M_:
- if _R_ < _M_ - then it makes no sense to speculate (the logic being that if
we relaunch the task - it can be expected to take around _M_ seconds. So the
current task will outrun the speculative attempt).
- if _T_ is in 'normal' range - then also it doesn't make sense to speculate.
we need to define normal.
i am not sure that normal is best measured by mean + stddev. The reason is that
tasks are frequently multi-modal in their durations (for example we are joining
data sets a, b, c - mapper splits from a b and c will have different run times
(depending on compression, size of row, filter condition etc.). ideally we
should track mean duration per data set - but we don't have that available. the
mean and stddev don't mean much in these conditions.
So my suggestion is to define normal to be in terms of percentiles. If a tasks
total duration (projected) is within some N % (say 90) - then we should exclude
it from speculation. if a task stalls - it will eventually show up in the top
percentile and be speculated. we can also supplement percentiles with absolute
numbers (if a more than M tasks are slower than the task being considered -
just don't speculate it)
----
elmination is great - but could still leave us with always trying to speculate
slowest 10% (for example) of tasks. that's a lot for a busy cluster. at this
point i think we should look at the cost/benefit of choosing some K slowest
tasks (by remaining time) to speculate.
The benefit of speculating a task is limited to the latency difference with the
next slowest task. As an example: if the three slowest tasks had remaining time
of 100s, 200s and 201s - then speculating only the last one will produce
hardly any gain (1s !!!) - but speculating the last two can give us 101s gain
(best case). The complication here is that one needs to consider the
cost/benefit of speculating some K tasks at a time (and not one at a time).
one simple way of specifying this may be to consider speculation opportunities
that result in at least X% or Y seconds decrease in latency. this needs some
more thinking.
> speculative execution does not handle cases where stddev > mean well
> --------------------------------------------------------------------
>
> Key: MAPREDUCE-2162
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-2162
> Project: Hadoop Map/Reduce
> Issue Type: Bug
> Reporter: Joydeep Sen Sarma
>
> the new speculation code only speculates tasks whose progress rate deviates
> from the mean progress rate of a job by more than some multiple (typically
> 1.0) of stddev. stddev can be larger than mean. which means that if we ever
> get into a situation where this condition holds true - then a task with even
> 0 progress rate will not be speculated.
> it's not clear that this condition is self-correcting. if a job has thousands
> of tasks - then one laggard task, inspite of not being speculated for a long
> time, may not be able to fix the condition of stddev > mean.
> we have seen jobs where tasks have not been speculated for hours and this
> seems one explanation why this may have happened. here's an example job with
> stddev > mean:
> DataStatistics: count is 6, sum is 1.7141054797775723E-8, sumSquares is
> 2.9381575958035014E-16 mean is 2.8568424662959537E-9 std() is
> 6.388093955645905E-9
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
