TaskInProgress.hasSpeculativeTask is very inefficient

• Key: HADOOP-2790
• Type: Bug
• Status: Closed
• Resolution: Fixed
• Priority: Major
• Assignee: Owen O'Malley
• Reporter: Owen O'Malley
• Fix Version/s: 0.17.0

Description

Each call to JobInProgress.findNewTask can call TaskInProgress.hasSpeculativeTask once per a task. Each call to hasSpeculativeTask calls System.getCurrentTimeMillis, which can result in hundreds of thousands of calls to getCurrentTimeMillis. Additionally, it calls TaskInProgress.isOnlyCommitPending, which calls .values() on the map from task id to host name and iterates through them to see if any of the tasks are in commit pending. It would be better to have a commit pending boolean flag in the TaskInProgress. It also looks like there are other opportunities here, but those jumped out at me. We should also look at this method in the profiler.

Comments

[Runping Qi]

This problem may well be one of the reasons for hadoop-2119.

Also, another obvious optimization is to check whether the speculative
execution flag is true up front.

[Amar Kamat]

Also, another obvious optimization is to check whether the speculative execution flag is true up front.

Even I noticed that few days back. But I thought HADOOP-2141 might fix that.

---

With HADOOP-2119, the calls to hasSpeculative() might reduce since we are optimizing the look-ups for finding the higher priority runnable tasks and totally avoiding speculative ones in these look-ups. So the check for speculative tasks will be done only if we have nothing else to run. But +1 to do it better than making all the checks all the time.
Following are the parameters used for deciding TaskInProgress.hasSpeculative() :

• activeTasks.size() <= MAX_TASK_EXECS [seems ok]
• runSpeculative [should be done earlier, but ok]
• averageProgress - progress >= SPECULATIVE_GAP [seems ok]
• System.currentTimeMillis() - startTime >= SPECULATIVE_LAG :
  This could be checked once in TaskInProgress.recomputeProgress() and a check will only be done in hasSpeculative() if the earlier check resulted as false. I guess we can still do better but my guess is that we cant totally avoid System.currentTimeMillis() in TaskInProgress.hasSpeculative(), no?
• completes == 0 [ok]
• !isOnlyCommitPending() :
  May be a Map for COMMIT_PENDING tasks can be maintained in TaskInProgress and the only check made is commitPendingStatuses.size() > 0 && commitPendingStatuses.contains(taskId). The space requirement will be same with a re-arrangement to be done in TaskInProgress.recomputeProgress().

  ---

  Comments?

[Amar Kamat]

!isOnlyCommitPending() :
May be a Map for COMMIT_PENDING tasks can be maintained in TaskInProgress and the only check made is commitPendingStatuses.size() > 0 && commitPendingStatuses.contains(taskId). The space requirement will be same with a re-arrangement to be done in TaskInProgress.recomputeProgress().

Actually the list of task statuses will be pretty small so either we can do what is currently done or maintain a boolean flag as Owen mentioned, +1.

System.currentTimeMillis() - startTime >= SPECULATIVE_LAG

As suggested by Devaraj, the time can be calculated in JobInProgress.findNewTask() and use this value in TaskInProgress.hasSpeculative(). The chances of ignoring a TIP for speculation that should be speculated will be extremely low as compared to using the time in TaskInProgress.recomputeProgress().

[Owen O'Malley]

As suggested by Devaraj, the time can be calculated in JobInProgress.findNewTask() and use this value in TaskInProgress.hasSpeculative().

+1 this is the clear solution

Please do move the runSpeculative check up.

I think the boolean for the commit pending would be pretty easy. If we can avoid calling .values(), we will avoid creating a second collection for each tip. Another point is that some of our customers run with the max task failures set to 100, so it is not free to scan the tasks in a tip.

[Owen O'Malley]

This patch does the easy part of the improvement. I really should benchmark it before it goes in. It moves the check for speculative execution much earlier, and it does 1 get time of day.

[Arun C Murthy]

+1

[Owen O'Malley]

Before the patch, findNewTask took 60s, with the patch it took 53s in my test case using Yourkit.

[Hadoop QA]

-1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12375694/2790.patch
against trunk revision 619744.

@author +1. The patch does not contain any @author tags.

tests included -1. The patch doesn't appear to include any new or modified tests.
Please justify why no tests are needed for this patch.

patch -1. The patch command could not apply the patch.

Console output: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1871/console

This message is automatically generated.

[Owen O'Malley]

Resolved conflict with 1985.

[Hadoop QA]

-1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12376796/2790-2.patch
against trunk revision 619744.

@author +1. The patch does not contain any @author tags.

tests included -1. The patch doesn't appear to include any new or modified tests.
Please justify why no tests are needed for this patch.

javadoc +1. The javadoc tool did not generate any warning messages.

javac +1. The applied patch does not generate any new javac compiler warnings.

release audit +1. The applied patch does not generate any new release audit warnings.

findbugs +1. The patch does not introduce any new Findbugs warnings.

core tests +1. The patch passed core unit tests.

contrib tests +1. The patch passed contrib unit tests.

Test results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1875/testReport/
Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1875/artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
Checkstyle results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1875/artifact/trunk/build/test/checkstyle-errors.html
Console output: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1875/console

This message is automatically generated.

[Devaraj Das]

Owen, could you please submit one patch for 0.16 branch. This patch doesn't apply cleanly there.

[Hudson]

Integrated in Hadoop-trunk #416 (See http://hudson.zones.apache.org/hudson/job/Hadoop-trunk/416/)

[Owen O'Malley]

Devaraj, the original patch would have worked for 0.16, but for now l decided to just put it in trunk.

[Hudson]

Integrated in Hadoop-trunk #417 (See http://hudson.zones.apache.org/hudson/job/Hadoop-trunk/417/)