Hadoop Map/Reduce
  1. Hadoop Map/Reduce
  2. MAPREDUCE-1838

DistRaid map tasks have large variance in running times

    Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 0.20.1
    • Fix Version/s: 0.22.0
    • Component/s: contrib/raid
    • Labels:
      None
    • Hadoop Flags:
      Reviewed

      Description

      HDFS RAID uses map-reduce jobs to generate parity files for a set of source files. Each map task gets a subset of files to operate on. The current code assigns files by walking through the list of files given in the constructor of DistRaid

      The problem is that the list of files given to the constructor has the order of (pretty much) the directory listing. When a large number of files is added, files in that order tend to have the same size. Thus a map task can end up with large files where as another can end up with small files, increasing the variance in run times.

      We could do smarter assignment by using the file sizes.

      1. MAPREDUCE-1838.patch
        0.8 kB
        Ramkumar Vadali

        Activity

        Hide
        Ramkumar Vadali added a comment -

        I had considered sorting the files in decreasing order of size before writing to the sequence file. The idea was to assign these files in a round-robin manner to each split. But splits are required to be contiguous portions of the split file and it looks like we dont know the number of splits when generating the split file (is it the same as the number set in jobconf.setNumMapTasks?)

        One option is to simply shuffle the list of files before writing to the split file. That should help reduce the variance

        Show
        Ramkumar Vadali added a comment - I had considered sorting the files in decreasing order of size before writing to the sequence file. The idea was to assign these files in a round-robin manner to each split. But splits are required to be contiguous portions of the split file and it looks like we dont know the number of splits when generating the split file (is it the same as the number set in jobconf.setNumMapTasks?) One option is to simply shuffle the list of files before writing to the split file. That should help reduce the variance
        Hide
        dhruba borthakur added a comment -

        > One option is to simply shuffle the list of files before writing to the split file. That should help reduce the variance

        That sounds like a fine idea.

        Show
        dhruba borthakur added a comment - > One option is to simply shuffle the list of files before writing to the split file. That should help reduce the variance That sounds like a fine idea.
        Hide
        dhruba borthakur added a comment -

        The random shuffle will work only if speculative-execution is switched on for this job. Otherwise there is a non-trivial probability that one long mapper will delay the job completion to a large extent.

        Show
        dhruba borthakur added a comment - The random shuffle will work only if speculative-execution is switched on for this job. Otherwise there is a non-trivial probability that one long mapper will delay the job completion to a large extent.
        Hide
        Dmytro Molkov added a comment -

        @dhruba
        I do not fully understand your comment on speculative execution. The problem right now is getting too many large files into one mapper while everyone else gets small data input. As a result you have those huge mappers running for a while when all the other mappers finish quickly. I am not sure how speculative can help in this case since these map tasks have to run 5 times longer than other maps in any case.

        Show
        Dmytro Molkov added a comment - @dhruba I do not fully understand your comment on speculative execution. The problem right now is getting too many large files into one mapper while everyone else gets small data input. As a result you have those huge mappers running for a while when all the other mappers finish quickly. I am not sure how speculative can help in this case since these map tasks have to run 5 times longer than other maps in any case.
        Hide
        dhruba borthakur added a comment -

        I agree, speculation actually does not make this go any faster!

        Show
        dhruba borthakur added a comment - I agree, speculation actually does not make this go any faster!
        Hide
        Ramkumar Vadali added a comment -

        Shuffle files to raid before submitting the raid job.

        Show
        Ramkumar Vadali added a comment - Shuffle files to raid before submitting the raid job.
        Hide
        Hadoop QA added a comment -

        -1 overall. Here are the results of testing the latest attachment
        http://issues.apache.org/jira/secure/attachment/12448455/MAPREDUCE-1838.patch
        against trunk revision 959509.

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

        -1 tests included. The patch doesn't appear to include any new or modified tests.
        Please justify why no new tests are needed for this patch.
        Also please list what manual steps were performed to verify this patch.

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

        +1 javac. The applied patch does not increase the total number of javac compiler warnings.

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

        +1 release audit. The applied patch does not increase the total number of release audit warnings.

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

        -1 contrib tests. The patch failed contrib unit tests.

        Test results: http://hudson.zones.apache.org/hudson/job/Mapreduce-Patch-h4.grid.sp2.yahoo.net/277/testReport/
        Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Mapreduce-Patch-h4.grid.sp2.yahoo.net/277/artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
        Checkstyle results: http://hudson.zones.apache.org/hudson/job/Mapreduce-Patch-h4.grid.sp2.yahoo.net/277/artifact/trunk/build/test/checkstyle-errors.html
        Console output: http://hudson.zones.apache.org/hudson/job/Mapreduce-Patch-h4.grid.sp2.yahoo.net/277/console

        This message is automatically generated.

        Show
        Hadoop QA added a comment - -1 overall. Here are the results of testing the latest attachment http://issues.apache.org/jira/secure/attachment/12448455/MAPREDUCE-1838.patch against trunk revision 959509. +1 @author. The patch does not contain any @author tags. -1 tests included. The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch. +1 javadoc. The javadoc tool did not generate any warning messages. +1 javac. The applied patch does not increase the total number of javac compiler warnings. +1 findbugs. The patch does not introduce any new Findbugs warnings. +1 release audit. The applied patch does not increase the total number of release audit warnings. +1 core tests. The patch passed core unit tests. -1 contrib tests. The patch failed contrib unit tests. Test results: http://hudson.zones.apache.org/hudson/job/Mapreduce-Patch-h4.grid.sp2.yahoo.net/277/testReport/ Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Mapreduce-Patch-h4.grid.sp2.yahoo.net/277/artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html Checkstyle results: http://hudson.zones.apache.org/hudson/job/Mapreduce-Patch-h4.grid.sp2.yahoo.net/277/artifact/trunk/build/test/checkstyle-errors.html Console output: http://hudson.zones.apache.org/hudson/job/Mapreduce-Patch-h4.grid.sp2.yahoo.net/277/console This message is automatically generated.
        Hide
        Ramkumar Vadali added a comment -

        This is a 1-line change that shuffles a collection before writing it to the split file. So the existing unit-tests should be enough.
        The failure in contrib test does not seem to be an actual test failure.

        Show
        Ramkumar Vadali added a comment - This is a 1-line change that shuffles a collection before writing it to the split file. So the existing unit-tests should be enough. The failure in contrib test does not seem to be an actual test failure.
        Hide
        Rodrigo Schmidt added a comment -

        +1
        Agree that no unit tests are needed in this case.

        Show
        Rodrigo Schmidt added a comment - +1 Agree that no unit tests are needed in this case.
        Hide
        dhruba borthakur added a comment -

        I just committed this. Thanks Ram!

        Show
        dhruba borthakur added a comment - I just committed this. Thanks Ram!
        Hide
        Hudson added a comment -

        Integrated in Hadoop-Mapreduce-trunk-Commit #523 (See https://hudson.apache.org/hudson/job/Hadoop-Mapreduce-trunk-Commit/523/)

        Show
        Hudson added a comment - Integrated in Hadoop-Mapreduce-trunk-Commit #523 (See https://hudson.apache.org/hudson/job/Hadoop-Mapreduce-trunk-Commit/523/ )

          People

          • Assignee:
            Ramkumar Vadali
            Reporter:
            Ramkumar Vadali
          • Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development