Hadoop Common
  1. Hadoop Common
  2. HADOOP-2423

The codes in FSDirectory.mkdirs(...) is inefficient.

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 0.15.1
    • Fix Version/s: 0.17.0
    • Component/s: None
    • Labels:
      None
    • Release Note:
      Improved FSDirectory.mkdirs(...) performance. In NNThroughputBenchmark-create, the ops per sec in was improved ~54%.

      Description

      FSDirectory.mkdirs(...) creates List<String> v to store all dirs. e.g.

      //Suppose 
      src = "/foo/bar/bas/"
      //Then,
      v = {"/", "/foo", "/foo/bar", "/foo/bar/bas"}
      

      For each directory string cur in v, no matter cur already exists or not, it will try to do a unprotectedMkdir(cur, ...). Then, cur is parsed to byte[][] in INodeDirectory.addNode (...).

      We don't need to do the parsing for each string in v. Instead, byte[][] should be stored. Also, the loop should not continue once it finds an existing subdirectory.

      1. 2423_20080311.patch
        7 kB
        Tsz Wo Nicholas Sze
      2. 2423_20080310.patch
        7 kB
        Tsz Wo Nicholas Sze
      3. 2423_20080304d.patch
        8 kB
        Tsz Wo Nicholas Sze
      4. 2423_20080304c.patch
        8 kB
        Tsz Wo Nicholas Sze
      5. 2423_20080304b.patch
        8 kB
        Tsz Wo Nicholas Sze
      6. 2423_20080304.patch
        5 kB
        Tsz Wo Nicholas Sze
      7. 2423_20080303.patch
        13 kB
        Tsz Wo Nicholas Sze
      8. 2423_20080130.patch
        14 kB
        Tsz Wo Nicholas Sze

        Issue Links

          Activity

          Tsz Wo Nicholas Sze made changes -
          Link This issue is related to HDFS-1832 [ HDFS-1832 ]
          Owen O'Malley made changes -
          Component/s dfs [ 12310710 ]
          Nigel Daley made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Tsz Wo Nicholas Sze made changes -
          Release Note Improved FSDirectory.mkdirs(...) performance. In NNThroughputBenchmark-create, the ops per sec in was improved ~54%.
          Hide
          Hudson added a comment -
          Show
          Hudson added a comment - Integrated in Hadoop-trunk #428 (See http://hudson.zones.apache.org/hudson/job/Hadoop-trunk/428/ )
          dhruba borthakur made changes -
          Resolution Fixed [ 1 ]
          Status Patch Available [ 10002 ] Resolved [ 5 ]
          Fix Version/s 0.17.0 [ 12312913 ]
          Hide
          dhruba borthakur added a comment -

          I just committed this. Thanks Nicholas.

          Show
          dhruba borthakur added a comment - I just committed this. Thanks Nicholas.
          Hide
          Hadoop QA added a comment -

          -1 overall. Here are the results of testing the latest attachment
          http://issues.apache.org/jira/secure/attachment/12377629/2423_20080311.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/1950/testReport/
          Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1950/artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
          Checkstyle results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1950/artifact/trunk/build/test/checkstyle-errors.html
          Console output: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1950/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/12377629/2423_20080311.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/1950/testReport/ Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1950/artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html Checkstyle results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1950/artifact/trunk/build/test/checkstyle-errors.html Console output: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/1950/console This message is automatically generated.
          Tsz Wo Nicholas Sze made changes -
          Status Open [ 1 ] Patch Available [ 10002 ]
          Hide
          Tsz Wo Nicholas Sze added a comment -

          Since there are already a lot of tests for mkdir, no additional tests added.

          Show
          Tsz Wo Nicholas Sze added a comment - Since there are already a lot of tests for mkdir, no additional tests added.
          Tsz Wo Nicholas Sze made changes -
          Attachment 2423_20080311.patch [ 12377629 ]
          Hide
          Tsz Wo Nicholas Sze added a comment -

          > I am only worried about limit 0 in String.split().
          The only different for split(p, 0) and split(p, -1) is the root path, i.e. "/". However, root path is treated as a special case in the codes (for both before and after the patch.) In addition to the regression tests, I manually tested it.

          2423_20080311.patch: fixed a bug.

          Show
          Tsz Wo Nicholas Sze added a comment - > I am only worried about limit 0 in String.split(). The only different for split(p, 0) and split(p, -1) is the root path, i.e. "/". However, root path is treated as a special case in the codes (for both before and after the patch.) In addition to the regression tests, I manually tested it. 2423_20080311.patch: fixed a bug.
          Hide
          Konstantin Shvachko added a comment -

          +1
          I am only worried about limit 0 in String.split(). There was a reason for -1, which I don't remember now,
          but could you please verify some corner cases, like creating a file/directory in the root, probably renaming, etc..

          Show
          Konstantin Shvachko added a comment - +1 I am only worried about limit 0 in String.split(). There was a reason for -1, which I don't remember now, but could you please verify some corner cases, like creating a file/directory in the root, probably renaming, etc..
          Tsz Wo Nicholas Sze made changes -
          Attachment 2423_20080310.patch [ 12377563 ]
          Hide
          Tsz Wo Nicholas Sze added a comment - - edited

          1. This is indeed a very good point. The codes becomes much simpler.

          2. Sure.

          3. Since path should not have consecutive "/", split with limit -1 or 0 are the same. So, I think the split with less number of parameters is preferred.

          4. Because of (1), the changes of addNode(String path, T newNode, boolean inheritPermission) are reverted. We could make the change from throwing FileNotFoundException to returning null later.

          5. Since addChild(...) does not throw FileNotFoundException, nothing to catch now.

          Show
          Tsz Wo Nicholas Sze added a comment - - edited 1. This is indeed a very good point. The codes becomes much simpler. 2. Sure. 3. Since path should not have consecutive "/", split with limit -1 or 0 are the same. So, I think the split with less number of parameters is preferred. 4. Because of (1), the changes of addNode(String path, T newNode, boolean inheritPermission) are reverted. We could make the change from throwing FileNotFoundException to returning null later. 5. Since addChild(...) does not throw FileNotFoundException, nothing to catch now.
          Hide
          Konstantin Shvachko added a comment - - edited

          This looks much better. There is room for more optimization.

          1. Rather than calling rootDir.addNode() you should call parentDir.addChild().
            This is what essentially happens in your code.
            But doing this explicitely will let you avoid creating the new addNode() with redundant parameters.
          2. The inheritPermission logic should go from addNode() into addChild() in this case.
          3. String[] strings = path.split(Path.SEPARATOR, -1);
            why limit = -1 in the current code is replaced by 0?
          4. <T extends INode> T addNode(String path, byte[][] pathComponents, INode parentNode, T newNode, boolean inheritPermission)
            parentNode should be of type INodeDirectory
            String path, don't need the first parameter:
            return null rather than throwing an exception; and throw FileNotFoundException in the calling method.
          5. In FSDirectory.mkdirs() the FileNotFoundException thrown by addNode() is absorbed. Should it be?
          Show
          Konstantin Shvachko added a comment - - edited This looks much better. There is room for more optimization. Rather than calling rootDir.addNode() you should call parentDir.addChild(). This is what essentially happens in your code. But doing this explicitely will let you avoid creating the new addNode() with redundant parameters. The inheritPermission logic should go from addNode() into addChild() in this case. String[] strings = path.split(Path.SEPARATOR, -1); why limit = -1 in the current code is replaced by 0? <T extends INode> T addNode(String path, byte[][] pathComponents, INode parentNode, T newNode, boolean inheritPermission) parentNode should be of type INodeDirectory String path, don't need the first parameter: return null rather than throwing an exception; and throw FileNotFoundException in the calling method. In FSDirectory.mkdirs() the FileNotFoundException thrown by addNode() is absorbed. Should it be?
          Tsz Wo Nicholas Sze made changes -
          Attachment 2423_20080304d.patch [ 12377125 ]
          Hide
          Tsz Wo Nicholas Sze added a comment -

          2423_20080304d.patch: fixed another bug. The one passed all the tests.

          Show
          Tsz Wo Nicholas Sze added a comment - 2423_20080304d.patch: fixed another bug. The one passed all the tests.
          Tsz Wo Nicholas Sze made changes -
          Attachment 2423_20080304c.patch [ 12377116 ]
          Hide
          Tsz Wo Nicholas Sze added a comment -

          2423_20080304c.patch: fixed a bug.

          Show
          Tsz Wo Nicholas Sze added a comment - 2423_20080304c.patch: fixed a bug.
          Tsz Wo Nicholas Sze made changes -
          Attachment 2423_20080304b.patch [ 12377108 ]
          Hide
          Tsz Wo Nicholas Sze added a comment -

          2423_20080304b.patch: further improved ops per sec to 127.2

          Show
          Tsz Wo Nicholas Sze added a comment - 2423_20080304b.patch: further improved ops per sec to 127.2
          Tsz Wo Nicholas Sze made changes -
          Attachment 2423_20080304.patch [ 12377099 ]
          Hide
          Tsz Wo Nicholas Sze added a comment -

          2423_20080304.patch:

          The ops per sec in NNThroughputBenchmark create increases from 82.6 to 107.0 in my machine.

          Show
          Tsz Wo Nicholas Sze added a comment - 2423_20080304.patch: The ops per sec in NNThroughputBenchmark create increases from 82.6 to 107.0 in my machine.
          Hide
          Konstantin Shvachko added a comment -

          This patch actually does 2 things.

          1. It introduces a class that caches INodes and local names on the path.
          2. Optimizes the mkDirs() using this class.

          I agree both tasks are important, but if you just want to optimize mkDirs() as stated above then it could be done much easier.
          The INode.getExistingPathINodes() should be made package private rather than INode-private.
          And then you can get all components of the path and all existing inodes along the path by

          FSDirectory.mkDirs(src, ... ) {
              byte[][] components = INode.getPathComponents(src);
              INode[] inodes = new INode[components.length];
              rootDir.getExistingPathINodes(components, inodes);
          
              // create missing inodes
              ...............
          }
          

          After that you just find first null in the array of inodes, and start adding directories using addNode() and fill in the null elements one by one.
          You don't even need to start from the rootDir for every component.

          Introducing the caching class is important but will take more effort, because we would probably want to to convert all String-path
          parameters to it and use across all name-node parts. This is going to be a big change, and it will require proper testing,
          benchmarking, etc.

          IMO optimizing mkDirs is important by itself, since it is extensively used by our clients.

          Show
          Konstantin Shvachko added a comment - This patch actually does 2 things. It introduces a class that caches INodes and local names on the path. Optimizes the mkDirs() using this class. I agree both tasks are important, but if you just want to optimize mkDirs() as stated above then it could be done much easier. The INode.getExistingPathINodes() should be made package private rather than INode-private. And then you can get all components of the path and all existing inodes along the path by FSDirectory.mkDirs(src, ... ) { byte [][] components = INode.getPathComponents(src); INode[] inodes = new INode[components.length]; rootDir.getExistingPathINodes(components, inodes); // create missing inodes ............... } After that you just find first null in the array of inodes, and start adding directories using addNode() and fill in the null elements one by one. You don't even need to start from the rootDir for every component. Introducing the caching class is important but will take more effort, because we would probably want to to convert all String-path parameters to it and use across all name-node parts. This is going to be a big change, and it will require proper testing, benchmarking, etc. IMO optimizing mkDirs is important by itself, since it is extensively used by our clients.
          Tsz Wo Nicholas Sze made changes -
          Attachment 2423_20080303.patch [ 12376996 ]
          Hide
          Tsz Wo Nicholas Sze added a comment -

          2423_20080303.patch: updated with current trunk

          Show
          Tsz Wo Nicholas Sze added a comment - 2423_20080303.patch: updated with current trunk
          Tsz Wo Nicholas Sze made changes -
          Link This issue relates to HADOOP-2002 [ HADOOP-2002 ]
          Tsz Wo Nicholas Sze made changes -
          Assignee Tsz Wo (Nicholas), SZE [ szetszwo ]
          Tsz Wo Nicholas Sze made changes -
          Attachment 2423_20080130.patch [ 12374425 ]
          Hide
          Tsz Wo Nicholas Sze added a comment -

          Yes, but this one is mainly for mkdir.

          Show
          Tsz Wo Nicholas Sze added a comment - Yes, but this one is mainly for mkdir.
          Hide
          Konstantin Shvachko added a comment -

          Is this similar or a part of HADOOP-2002?

          Show
          Konstantin Shvachko added a comment - Is this similar or a part of HADOOP-2002 ?
          Tsz Wo Nicholas Sze made changes -
          Field Original Value New Value
          Description FSDirectory.mkdirs(...) creates a list of string storing all FSDirectory.mkdirs(...) creates List<String> v to store all dirs. e.g.

          {code}
          //Suppose
          src = "/foo/bar/bas/"
          //Then,
          v = {"/", "/foo", "/foo/bar", "/foo/bar/bas"}
          {code}

          For each directory string *cur* in v, no matter *cur* already exists or not, it will try to do a unprotectedMkdir(cur, ...). Then, *cur* is parsed to byte[][] in INodeDirectory.addNode (...).

          We don't need to do the parsing for each string in v. Instead, byte[][] should be stored. Also, the loop should not continue once it finds an existing subdirectory.
          Tsz Wo Nicholas Sze created issue -

            People

            • Assignee:
              Tsz Wo Nicholas Sze
              Reporter:
              Tsz Wo Nicholas Sze
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development