Hadoop HDFS
  1. Hadoop HDFS
  2. HDFS-1443 Improve Datanode startup time
  3. HDFS-1447

Make getGenerationStampFromFile() more efficient, so it doesn't reprocess full directory listing for every block

    Details

    • Type: Sub-task Sub-task
    • Status: Patch Available
    • Priority: Major Major
    • Resolution: Unresolved
    • Affects Version/s: 0.20.2
    • Fix Version/s: None
    • Component/s: datanode
    • Labels:
      None
    • Tags:
      datanode startup

      Description

      Make getGenerationStampFromFile() more efficient. Currently this routine is called by addToReplicasMap() for every blockfile in the directory tree, and it walks each file's containing directory on every call. There is a simple refactoring that should make it more efficient.

      This work item is one of four sub-tasks for HDFS-1443, Improve Datanode startup time.
      The fix will probably be folded into sibling task HDFS-1446, which is already refactoring the method that calls getGenerationStampFromFile().

      1. Test_HDFS_1447_NotForCommitt.java.patch
        6 kB
        Uma Maheswara Rao G
      2. HDFS-1447.patch
        7 kB
        Uma Maheswara Rao G

        Activity

        Hide
        Uma Maheswara Rao G added a comment -

        @Suresh:
        Thanks for taking a look. Yes, i know the max files per dir is 64 by default. Please check other JIRAs in this umberilla for further optimizations. Wanted to use the same scan for recoverTmpUnlinkedFiles with other JIRA.
        With the less file we may not get good improvements and with this single JIRA. Above figures are to show the relative improvement in optimizing the loops.

        @Todd, Yes, the scanning logic was good in HDFS-2384. But in FSDataSet case, we need to maintain the tree as well rite.
        Also in C code i have seen there is a genstamps array with blkids. Long array will consume more memory right?

        Show
        Uma Maheswara Rao G added a comment - @Suresh: Thanks for taking a look. Yes, i know the max files per dir is 64 by default. Please check other JIRAs in this umberilla for further optimizations. Wanted to use the same scan for recoverTmpUnlinkedFiles with other JIRA. With the less file we may not get good improvements and with this single JIRA. Above figures are to show the relative improvement in optimizing the loops. @Todd, Yes, the scanning logic was good in HDFS-2384 . But in FSDataSet case, we need to maintain the tree as well rite. Also in C code i have seen there is a genstamps array with blkids. Long array will consume more memory right?
        Hide
        Todd Lipcon added a comment -

        Also, what percent of startup time is devoted to CPU usage of this scan? In HDFS-2384 I uploaded a C program which does the block scan as efficiently as possible - but most of the gains there are from sorting by inum before statting.

        Show
        Todd Lipcon added a comment - Also, what percent of startup time is devoted to CPU usage of this scan? In HDFS-2384 I uploaded a C program which does the block scan as efficiently as possible - but most of the gains there are from sorting by inum before statting.
        Hide
        Suresh Srinivas added a comment -

        I have created 10000 blocks and metafies in one directory.

        In datanode storage directory, we typically have less than 100 block files. What kind of improvement do we see for that?

        Show
        Suresh Srinivas added a comment - I have created 10000 blocks and metafies in one directory. In datanode storage directory, we typically have less than 100 block files. What kind of improvement do we see for that?
        Hide
        Uma Maheswara Rao G added a comment -

        -1 findbugs. The patch appears to introduce 1 new Findbugs (version 1.3.9) warnings.

        Not related to this patch. Filed a separate JIRA HDFS-2449

        -1 release audit. The applied patch generated 2 release audit warnings (more than the trunk's current 0 warnings).

        Not related to this patch. Filed a separate JIRa HDFS-2448

        Since there is no functional change, not included new tests. There is no test failures because of this patch. Above failures are looks unrelated. ( related to protocol changes)

        thanks
        Uma

        Show
        Uma Maheswara Rao G added a comment - -1 findbugs. The patch appears to introduce 1 new Findbugs (version 1.3.9) warnings. Not related to this patch. Filed a separate JIRA HDFS-2449 -1 release audit. The applied patch generated 2 release audit warnings (more than the trunk's current 0 warnings). Not related to this patch. Filed a separate JIRa HDFS-2448 Since there is no functional change, not included new tests. There is no test failures because of this patch. Above failures are looks unrelated. ( related to protocol changes) thanks Uma
        Hide
        Hadoop QA added a comment -

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

        +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 appears to introduce 1 new Findbugs (version 1.3.9) warnings.

        -1 release audit. The applied patch generated 2 release audit warnings (more than the trunk's current 0 warnings).

        -1 core tests. The patch failed these unit tests:
        org.apache.hadoop.hdfs.TestDistributedFileSystem
        org.apache.hadoop.hdfs.server.datanode.TestDeleteBlockPool
        org.apache.hadoop.hdfs.TestAbandonBlock
        org.apache.hadoop.hdfs.TestRestartDFS

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

        Test results: https://builds.apache.org/job/PreCommit-HDFS-Build/1367//testReport/
        Release audit warnings: https://builds.apache.org/job/PreCommit-HDFS-Build/1367//artifact/trunk/patchprocess/patchReleaseAuditProblems.txt
        Findbugs warnings: https://builds.apache.org/job/PreCommit-HDFS-Build/1367//artifact/trunk/hadoop-hdfs-project/patchprocess/newPatchFindbugsWarningshadoop-hdfs.html
        Console output: https://builds.apache.org/job/PreCommit-HDFS-Build/1367//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/12499004/HDFS-1447.patch against trunk revision . +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 appears to introduce 1 new Findbugs (version 1.3.9) warnings. -1 release audit. The applied patch generated 2 release audit warnings (more than the trunk's current 0 warnings). -1 core tests. The patch failed these unit tests: org.apache.hadoop.hdfs.TestDistributedFileSystem org.apache.hadoop.hdfs.server.datanode.TestDeleteBlockPool org.apache.hadoop.hdfs.TestAbandonBlock org.apache.hadoop.hdfs.TestRestartDFS +1 contrib tests. The patch passed contrib unit tests. Test results: https://builds.apache.org/job/PreCommit-HDFS-Build/1367//testReport/ Release audit warnings: https://builds.apache.org/job/PreCommit-HDFS-Build/1367//artifact/trunk/patchprocess/patchReleaseAuditProblems.txt Findbugs warnings: https://builds.apache.org/job/PreCommit-HDFS-Build/1367//artifact/trunk/hadoop-hdfs-project/patchprocess/newPatchFindbugsWarningshadoop-hdfs.html Console output: https://builds.apache.org/job/PreCommit-HDFS-Build/1367//console This message is automatically generated.
        Hide
        Praveen Kumar K J V S added a comment -

        Good work.

        In the old code the time for processing is approximately O(n^n) hence the time for execution increases exponentially as the number of file increases in a directory

        In the new code the order is much linear.

        I wonder if there is way for making time complexity of the function logarithmic

        +1 if all the tests pass

        Show
        Praveen Kumar K J V S added a comment - Good work. In the old code the time for processing is approximately O(n^n) hence the time for execution increases exponentially as the number of file increases in a directory In the new code the order is much linear. I wonder if there is way for making time complexity of the function logarithmic +1 if all the tests pass
        Hide
        Uma Maheswara Rao G added a comment -

        Updated patch for review!

        Test results:
        I have created 10000 blocks and metafies in one directory.
        Verified the addToReplicasMap method with and without code changes.
        Found that , 27 times improvement.

        Performance stats with and without code changes:

        With Fix:
        addToReplicasMapWithNewChange Test completed in 969
        addToReplicasMapWithNewChange Test completed in 703
        addToReplicasMapWithNewChange Test completed in 672
        addToReplicasMapWithNewChange Test completed in 641
        addToReplicasMapWithNewChange Test completed in 640
        addToReplicasMapWithNewChange Test completed in 672
        addToReplicasMapWithNewChange Test completed in 625
        addToReplicasMapWithNewChange Test completed in 641
        addToReplicasMapWithNewChange Test completed in 641
        addToReplicasMapWithNewChange Test completed in 656
        Average Performance : 686

        Without Fix:
        addToReplicasMapWithOldCode Test completed in 19516
        addToReplicasMapWithOldCode Test completed in 19172
        addToReplicasMapWithOldCode Test completed in 19126
        addToReplicasMapWithOldCode Test completed in 19078
        addToReplicasMapWithOldCode Test completed in 19079
        addToReplicasMapWithOldCode Test completed in 19094
        addToReplicasMapWithOldCode Test completed in 19188
        addToReplicasMapWithOldCode Test completed in 19157
        addToReplicasMapWithOldCode Test completed in 19125
        addToReplicasMapWithOldCode Test completed in 19079
        Average Performance : 19161

        Seen ~27 times improvement for 10000 files in a directory. This improvement will be more when we take more number of files in directory.

        Approach:
        Here there will be 2 iterations.
        For the first iteration we calculated the blockID, genStamp, BlockFile Length and populated into corresponding datastructures.
        For the second iteration (just half of the files (only for block files)), constructed the Replica and added to volume map.

        Thanks
        Uma

        Show
        Uma Maheswara Rao G added a comment - Updated patch for review! Test results: I have created 10000 blocks and metafies in one directory. Verified the addToReplicasMap method with and without code changes. Found that , 27 times improvement. Performance stats with and without code changes: With Fix: addToReplicasMapWithNewChange Test completed in 969 addToReplicasMapWithNewChange Test completed in 703 addToReplicasMapWithNewChange Test completed in 672 addToReplicasMapWithNewChange Test completed in 641 addToReplicasMapWithNewChange Test completed in 640 addToReplicasMapWithNewChange Test completed in 672 addToReplicasMapWithNewChange Test completed in 625 addToReplicasMapWithNewChange Test completed in 641 addToReplicasMapWithNewChange Test completed in 641 addToReplicasMapWithNewChange Test completed in 656 Average Performance : 686 Without Fix: addToReplicasMapWithOldCode Test completed in 19516 addToReplicasMapWithOldCode Test completed in 19172 addToReplicasMapWithOldCode Test completed in 19126 addToReplicasMapWithOldCode Test completed in 19078 addToReplicasMapWithOldCode Test completed in 19079 addToReplicasMapWithOldCode Test completed in 19094 addToReplicasMapWithOldCode Test completed in 19188 addToReplicasMapWithOldCode Test completed in 19157 addToReplicasMapWithOldCode Test completed in 19125 addToReplicasMapWithOldCode Test completed in 19079 Average Performance : 19161 Seen ~27 times improvement for 10000 files in a directory. This improvement will be more when we take more number of files in directory. Approach: Here there will be 2 iterations. For the first iteration we calculated the blockID, genStamp, BlockFile Length and populated into corresponding datastructures. For the second iteration (just half of the files (only for block files)), constructed the Replica and added to volume map. Thanks Uma

          People

          • Assignee:
            Matt Foley
            Reporter:
            Matt Foley
          • Votes:
            0 Vote for this issue
            Watchers:
            8 Start watching this issue

            Dates

            • Created:
              Updated:

              Development