Uploaded image for project: 'Hadoop HDFS'
  1. Hadoop HDFS
  2. HDFS-12042

Lazy initialize AbstractINodeDiffList#diffs for snapshots to reduce memory consumption

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 2.9.0, 3.0.0-beta1, 2.8.2
    • Component/s: None
    • Labels:
      None
    • Hadoop Flags:
      Reviewed

      Description

      When snapshot diff operation is performed in a NameNode that manages several million HDFS files/directories, NN needs a lot of memory. Some of that memory is wasted due to suboptimal data structures, such as empty or under-populated ArrayLists, etc. Analyzing one heap dump with jxray (www.jxray.com), we observed the following problems with data structures:

      9. BAD COLLECTIONS
      
      Total collections: 99,707,902  Bad collections: 88,799,760  Overhead: 9,063,898K (18.2%)
      
      Top bad collections:
          Ovhd           Problem     Num objs      Type
      -------------------------------------------------
      3,056,014K (6.1%)      small     29435572     j.u.ArrayList
      2,641,373K (5.3%)     1-elem     21837906     j.u.ArrayList
      864,215K (1.7%)     1-elem      5291813     j.u.TreeSet
      808,456K (1.6%)     1-elem      3045847     j.u.HashMap
      602,470K (1.2%)      empty     18549109     j.u.ArrayList
      441,563K (0.9%)      empty      4356975     j.u.TreeSet
      373,088K (0.7%)      empty      5297007     j.u.HashMap
      270,324K (0.5%)      small       931394     j.u.HashMap
      

      The data structures created by HDFS code that suffer from the above problems are, in particular:

        4,228,182K (8.5%): j.u.ArrayList: 19412263 of small 2,111,087K (4.2%), 12932408 of 1-elem 1,717,585K (3.4%), 12784310 of empty 399,509K (0.8%)
           <-- org.apache.hadoop.hdfs.server.namenode.snapshot.FileDiffList.diffs <-- org.apache.hadoop.hdfs.server.namenode.snapshot.FileWithSnapshotFeature.diffs <-- org.apache.hadoop.hdfs.server.namenode.INode$Feature[] <-- org.apache.hadoop.hdfs.server.namenode.INodeFile.features <-- org.apache.hadoop.hdfs.server.blockmanagement.BlockInfo.bc <-- org.apache.hadoop.util.LightWeightGSet$LinkedElement[] <-- org.apache.hadoop.hdfs.server.blockmanagement.BlocksMap$1.entries <-- org.apache.hadoop.hdfs.server.blockmanagement.BlocksMap.blocks <-- org.apache.hadoop.hdfs.server.blockmanagement.BlocksMap$1.entries <-- org.apache.hadoop.hdfs.server.blockmanagement.BlocksMap.blocks <-- org.apache.hadoop.hdfs.server.blockmanagement.BlockManager.blocksMap <-- org.apache.hadoop.hdfs.server.blockmanagement.BlockManager$BlockReportProcessingThread.this$0 <-- j.l.Thread[] <-- j.l.ThreadGroup.threads <-- j.l.Thread.group <-- Java Static: org.apache.hadoop.fs.FileSystem$Statistics.STATS_DATA_CLEANER
      

      and

        575,557K (1.2%): j.u.ArrayList: 4363271 of 1-elem 409,056K (0.8%), 2439001 of small 166,482K (0.3%)
           <-- org.apache.hadoop.hdfs.server.namenode.INodeDirectory.children <-- org.apache.hadoop.util.LightWeightGSet$LinkedElement[] <-- org.apache.hadoop.util.LightWeightGSet.entries <-- org.apache.hadoop.hdfs.server.namenode.INodeMap.map <-- org.apache.hadoop.hdfs.server.namenode.FSDirectory.inodeMap <-- org.apache.hadoop.hdfs.server.namenode.FSNamesystem.dir <-- org.apache.hadoop.hdfs.server.namenode.FSNamesystem$NameNodeResourceMonitor.this$0 <-- org.apache.hadoop.util.Daemon.target <-- org.apache.hadoop.hdfs.server.namenode.FSDirectory.inodeMap <-- org.apache.hadoop.hdfs.server.namenode.FSNamesystem.dir <-- org.apache.hadoop.hdfs.server.namenode.FSNamesystem$NameNodeResourceMonitor.this$0 <-- org.apache.hadoop.util.Daemon.target <-- j.l.Thread[] <-- j.l.ThreadGroup.threads <-- j.l.Thread.group <-- Java Static: org.apache.hadoop.fs.FileSystem$Statistics.STATS_DATA_CLEANER
      

      There are several different reference chains that all lead to FileDiffList.diffs or INodeDirectory.children. The total percentage of memory wasted by these data structures in the analyzed dump is about 12%. By creating these lists lazily and/or with capacity that better matches their actual size, we should be able to reclaim a significant part of these 12%.

      1. HDFS-12042.01.patch
        6 kB
        Misha Dmitriev
      2. HDFS-12042.02.patch
        8 kB
        Misha Dmitriev
      3. HDFS-12042.03.patch
        8 kB
        Misha Dmitriev
      4. HDFS-12042.04.patch
        8 kB
        Misha Dmitriev

        Issue Links

          Activity

          Hide
          hadoopqa Hadoop QA added a comment -
          -1 overall



          Vote Subsystem Runtime Comment
          0 reexec 0m 24s Docker mode activated.
          +1 @author 0m 0s The patch does not contain any @author tags.
          -1 test4tests 0m 0s 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 mvninstall 13m 51s trunk passed
          +1 compile 0m 51s trunk passed
          +1 checkstyle 0m 38s trunk passed
          +1 mvnsite 0m 57s trunk passed
          +1 findbugs 1m 45s trunk passed
          +1 javadoc 0m 41s trunk passed
          +1 mvninstall 0m 50s the patch passed
          +1 compile 0m 48s the patch passed
          +1 javac 0m 48s the patch passed
          -0 checkstyle 0m 33s hadoop-hdfs-project/hadoop-hdfs: The patch generated 6 new + 17 unchanged - 1 fixed = 23 total (was 18)
          +1 mvnsite 0m 53s the patch passed
          +1 whitespace 0m 0s The patch has no whitespace issues.
          +1 findbugs 1m 50s the patch passed
          +1 javadoc 0m 39s the patch passed
          -1 unit 68m 32s hadoop-hdfs in the patch failed.
          +1 asflicense 0m 22s The patch does not generate ASF License warnings.
          94m 53s



          Reason Tests
          Failed junit tests hadoop.hdfs.server.namenode.ha.TestEditLogTailer
            hadoop.hdfs.server.namenode.TestTruncateQuotaUpdate
            hadoop.hdfs.server.namenode.TestFileTruncate
            hadoop.hdfs.TestErasureCodingPolicyWithSnapshotWithRandomECPolicy
            hadoop.hdfs.TestEncryptionZones
            hadoop.hdfs.server.namenode.snapshot.TestSnapshotDiffReport
            hadoop.hdfs.TestErasureCodingPolicyWithSnapshot
            hadoop.hdfs.TestDFSStripedOutputStreamWithFailure150
            hadoop.hdfs.server.namenode.snapshot.TestAclWithSnapshot
            hadoop.hdfs.TestDFSStripedOutputStreamWithFailure080
            hadoop.hdfs.server.datanode.fsdataset.impl.TestFsDatasetImpl
            hadoop.hdfs.TestEncryptionZonesWithKMS
            hadoop.hdfs.server.namenode.snapshot.TestRenameWithSnapshots



          Subsystem Report/Notes
          Docker Image:yetus/hadoop:14b5c93
          JIRA Issue HDFS-12042
          JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12874579/HDFS-12042.01.patch
          Optional Tests asflicense compile javac javadoc mvninstall mvnsite unit findbugs checkstyle
          uname Linux 394d0c52e9c1 3.13.0-116-generic #163-Ubuntu SMP Fri Mar 31 14:13:22 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
          Build tool maven
          Personality /testptch/hadoop/patchprocess/precommit/personality/provided.sh
          git revision trunk / 144753e
          Default Java 1.8.0_131
          findbugs v3.1.0-RC1
          checkstyle https://builds.apache.org/job/PreCommit-HDFS-Build/20052/artifact/patchprocess/diff-checkstyle-hadoop-hdfs-project_hadoop-hdfs.txt
          unit https://builds.apache.org/job/PreCommit-HDFS-Build/20052/artifact/patchprocess/patch-unit-hadoop-hdfs-project_hadoop-hdfs.txt
          Test Results https://builds.apache.org/job/PreCommit-HDFS-Build/20052/testReport/
          modules C: hadoop-hdfs-project/hadoop-hdfs U: hadoop-hdfs-project/hadoop-hdfs
          Console output https://builds.apache.org/job/PreCommit-HDFS-Build/20052/console
          Powered by Apache Yetus 0.5.0-SNAPSHOT http://yetus.apache.org

          This message was automatically generated.

          Show
          hadoopqa Hadoop QA added a comment - -1 overall Vote Subsystem Runtime Comment 0 reexec 0m 24s Docker mode activated. +1 @author 0m 0s The patch does not contain any @author tags. -1 test4tests 0m 0s 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 mvninstall 13m 51s trunk passed +1 compile 0m 51s trunk passed +1 checkstyle 0m 38s trunk passed +1 mvnsite 0m 57s trunk passed +1 findbugs 1m 45s trunk passed +1 javadoc 0m 41s trunk passed +1 mvninstall 0m 50s the patch passed +1 compile 0m 48s the patch passed +1 javac 0m 48s the patch passed -0 checkstyle 0m 33s hadoop-hdfs-project/hadoop-hdfs: The patch generated 6 new + 17 unchanged - 1 fixed = 23 total (was 18) +1 mvnsite 0m 53s the patch passed +1 whitespace 0m 0s The patch has no whitespace issues. +1 findbugs 1m 50s the patch passed +1 javadoc 0m 39s the patch passed -1 unit 68m 32s hadoop-hdfs in the patch failed. +1 asflicense 0m 22s The patch does not generate ASF License warnings. 94m 53s Reason Tests Failed junit tests hadoop.hdfs.server.namenode.ha.TestEditLogTailer   hadoop.hdfs.server.namenode.TestTruncateQuotaUpdate   hadoop.hdfs.server.namenode.TestFileTruncate   hadoop.hdfs.TestErasureCodingPolicyWithSnapshotWithRandomECPolicy   hadoop.hdfs.TestEncryptionZones   hadoop.hdfs.server.namenode.snapshot.TestSnapshotDiffReport   hadoop.hdfs.TestErasureCodingPolicyWithSnapshot   hadoop.hdfs.TestDFSStripedOutputStreamWithFailure150   hadoop.hdfs.server.namenode.snapshot.TestAclWithSnapshot   hadoop.hdfs.TestDFSStripedOutputStreamWithFailure080   hadoop.hdfs.server.datanode.fsdataset.impl.TestFsDatasetImpl   hadoop.hdfs.TestEncryptionZonesWithKMS   hadoop.hdfs.server.namenode.snapshot.TestRenameWithSnapshots Subsystem Report/Notes Docker Image:yetus/hadoop:14b5c93 JIRA Issue HDFS-12042 JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12874579/HDFS-12042.01.patch Optional Tests asflicense compile javac javadoc mvninstall mvnsite unit findbugs checkstyle uname Linux 394d0c52e9c1 3.13.0-116-generic #163-Ubuntu SMP Fri Mar 31 14:13:22 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux Build tool maven Personality /testptch/hadoop/patchprocess/precommit/personality/provided.sh git revision trunk / 144753e Default Java 1.8.0_131 findbugs v3.1.0-RC1 checkstyle https://builds.apache.org/job/PreCommit-HDFS-Build/20052/artifact/patchprocess/diff-checkstyle-hadoop-hdfs-project_hadoop-hdfs.txt unit https://builds.apache.org/job/PreCommit-HDFS-Build/20052/artifact/patchprocess/patch-unit-hadoop-hdfs-project_hadoop-hdfs.txt Test Results https://builds.apache.org/job/PreCommit-HDFS-Build/20052/testReport/ modules C: hadoop-hdfs-project/hadoop-hdfs U: hadoop-hdfs-project/hadoop-hdfs Console output https://builds.apache.org/job/PreCommit-HDFS-Build/20052/console Powered by Apache Yetus 0.5.0-SNAPSHOT http://yetus.apache.org This message was automatically generated.
          Hide
          hadoopqa Hadoop QA added a comment -
          -1 overall



          Vote Subsystem Runtime Comment
          0 reexec 0m 21s Docker mode activated.
          +1 @author 0m 0s The patch does not contain any @author tags.
          +1 test4tests 0m 0s The patch appears to include 1 new or modified test files.
          +1 mvninstall 14m 26s trunk passed
          +1 compile 0m 51s trunk passed
          +1 checkstyle 0m 36s trunk passed
          +1 mvnsite 0m 55s trunk passed
          +1 findbugs 1m 58s trunk passed
          +1 javadoc 0m 43s trunk passed
          +1 mvninstall 0m 52s the patch passed
          +1 compile 0m 49s the patch passed
          +1 javac 0m 49s the patch passed
          +1 checkstyle 0m 36s hadoop-hdfs-project/hadoop-hdfs: The patch generated 0 new + 18 unchanged - 1 fixed = 18 total (was 19)
          +1 mvnsite 0m 56s the patch passed
          +1 whitespace 0m 0s The patch has no whitespace issues.
          +1 findbugs 1m 53s the patch passed
          +1 javadoc 0m 47s the patch passed
          -1 unit 97m 12s hadoop-hdfs in the patch failed.
          +1 asflicense 0m 19s The patch does not generate ASF License warnings.
          124m 54s



          Reason Tests
          Failed junit tests hadoop.hdfs.server.datanode.fsdataset.impl.TestFsDatasetImpl
            hadoop.hdfs.TestDFSStripedOutputStreamWithFailure150
            hadoop.hdfs.TestDFSStripedOutputStreamWithFailure010



          Subsystem Report/Notes
          Docker Image:yetus/hadoop:14b5c93
          JIRA Issue HDFS-12042
          JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12874618/HDFS-12042.02.patch
          Optional Tests asflicense compile javac javadoc mvninstall mvnsite unit findbugs checkstyle
          uname Linux a92f7e0e9c60 3.13.0-116-generic #163-Ubuntu SMP Fri Mar 31 14:13:22 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
          Build tool maven
          Personality /testptch/hadoop/patchprocess/precommit/personality/provided.sh
          git revision trunk / 2b87faf
          Default Java 1.8.0_131
          findbugs v3.1.0-RC1
          unit https://builds.apache.org/job/PreCommit-HDFS-Build/20058/artifact/patchprocess/patch-unit-hadoop-hdfs-project_hadoop-hdfs.txt
          Test Results https://builds.apache.org/job/PreCommit-HDFS-Build/20058/testReport/
          modules C: hadoop-hdfs-project/hadoop-hdfs U: hadoop-hdfs-project/hadoop-hdfs
          Console output https://builds.apache.org/job/PreCommit-HDFS-Build/20058/console
          Powered by Apache Yetus 0.5.0-SNAPSHOT http://yetus.apache.org

          This message was automatically generated.

          Show
          hadoopqa Hadoop QA added a comment - -1 overall Vote Subsystem Runtime Comment 0 reexec 0m 21s Docker mode activated. +1 @author 0m 0s The patch does not contain any @author tags. +1 test4tests 0m 0s The patch appears to include 1 new or modified test files. +1 mvninstall 14m 26s trunk passed +1 compile 0m 51s trunk passed +1 checkstyle 0m 36s trunk passed +1 mvnsite 0m 55s trunk passed +1 findbugs 1m 58s trunk passed +1 javadoc 0m 43s trunk passed +1 mvninstall 0m 52s the patch passed +1 compile 0m 49s the patch passed +1 javac 0m 49s the patch passed +1 checkstyle 0m 36s hadoop-hdfs-project/hadoop-hdfs: The patch generated 0 new + 18 unchanged - 1 fixed = 18 total (was 19) +1 mvnsite 0m 56s the patch passed +1 whitespace 0m 0s The patch has no whitespace issues. +1 findbugs 1m 53s the patch passed +1 javadoc 0m 47s the patch passed -1 unit 97m 12s hadoop-hdfs in the patch failed. +1 asflicense 0m 19s The patch does not generate ASF License warnings. 124m 54s Reason Tests Failed junit tests hadoop.hdfs.server.datanode.fsdataset.impl.TestFsDatasetImpl   hadoop.hdfs.TestDFSStripedOutputStreamWithFailure150   hadoop.hdfs.TestDFSStripedOutputStreamWithFailure010 Subsystem Report/Notes Docker Image:yetus/hadoop:14b5c93 JIRA Issue HDFS-12042 JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12874618/HDFS-12042.02.patch Optional Tests asflicense compile javac javadoc mvninstall mvnsite unit findbugs checkstyle uname Linux a92f7e0e9c60 3.13.0-116-generic #163-Ubuntu SMP Fri Mar 31 14:13:22 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux Build tool maven Personality /testptch/hadoop/patchprocess/precommit/personality/provided.sh git revision trunk / 2b87faf Default Java 1.8.0_131 findbugs v3.1.0-RC1 unit https://builds.apache.org/job/PreCommit-HDFS-Build/20058/artifact/patchprocess/patch-unit-hadoop-hdfs-project_hadoop-hdfs.txt Test Results https://builds.apache.org/job/PreCommit-HDFS-Build/20058/testReport/ modules C: hadoop-hdfs-project/hadoop-hdfs U: hadoop-hdfs-project/hadoop-hdfs Console output https://builds.apache.org/job/PreCommit-HDFS-Build/20058/console Powered by Apache Yetus 0.5.0-SNAPSHOT http://yetus.apache.org This message was automatically generated.
          Hide
          misha@cloudera.com Misha Dmitriev added a comment -

          Looks like the failed test are unrelated and flaky - at least some of them failed in the previous builds as well.

          Show
          misha@cloudera.com Misha Dmitriev added a comment - Looks like the failed test are unrelated and flaky - at least some of them failed in the previous builds as well.
          Hide
          jojochuang Wei-Chiu Chuang added a comment -

          Thanks Misha Dmitriev, very good report and analysis.

          I am still reviewing the patch, but if I understand the patch correctly, the jist of the patch is to lazily instantiates AbstractINodeDiffList.diffs, because there are many empty diffs ArrayLists.

          One nit:

          • In INodeDirectory, can you simply update DEFAULT_FILES_PER_DIRECTORY to be 2? That constant is only used in addChild(). You can also use this constant in AbstractINodeDiffList#createDiffsIfNeeded

          I'll let others to review more carefully. Thanks.

          Show
          jojochuang Wei-Chiu Chuang added a comment - Thanks Misha Dmitriev , very good report and analysis. I am still reviewing the patch, but if I understand the patch correctly, the jist of the patch is to lazily instantiates AbstractINodeDiffList.diffs , because there are many empty diffs ArrayLists. One nit: In INodeDirectory, can you simply update DEFAULT_FILES_PER_DIRECTORY to be 2? That constant is only used in addChild() . You can also use this constant in AbstractINodeDiffList#createDiffsIfNeeded I'll let others to review more carefully. Thanks.
          Hide
          misha@cloudera.com Misha Dmitriev added a comment -

          Yes Wei-Chiu Chuang, you are correct. The essence of the patch is (1) instantiate AbstractINodeDiffList.diffs lazily to avoid empty ArrayLists, and (2) instantiate the above list and INodeDirectory.children() with very small initial capacity to reduce waste due to unused array slots in ArrayLists.

          I'll change DEFAULT_FILES_PER_DIRECTORY as you suggest.

          Note that the jxray analysis shows that a pretty high amount of memory (5.3%) could be further saved if we got rid of 1-element ArrayLists. They are wasteful, because such an ArrayList still consumes at least ~60 bytes, whereas it could be replaced with a simple pointer to the single object that it contains. That is:

          // Old code
          ArrayList<X> foo;
          X get(int i) { return foo.get(i); }
          ....
          
          // New code
          Object foo; // Can be either ArrayList<X> or pointer to a single X object
          X get(int i) {
            if (foo instanceof X) {
              if (i != 0) throw Exception("Wrong index!");
              return (X) foo;
            } else {
              return ((ArrayList<X>) foo).get(i);
            }
          }
          

          I've done such optimizations in the past and it can be done here. But as you can see, this results in a somewhat tricky code. Let me know what you think about this.

          Show
          misha@cloudera.com Misha Dmitriev added a comment - Yes Wei-Chiu Chuang , you are correct. The essence of the patch is (1) instantiate AbstractINodeDiffList.diffs lazily to avoid empty ArrayLists, and (2) instantiate the above list and INodeDirectory.children() with very small initial capacity to reduce waste due to unused array slots in ArrayLists. I'll change DEFAULT_FILES_PER_DIRECTORY as you suggest. Note that the jxray analysis shows that a pretty high amount of memory (5.3%) could be further saved if we got rid of 1-element ArrayLists. They are wasteful, because such an ArrayList still consumes at least ~60 bytes, whereas it could be replaced with a simple pointer to the single object that it contains. That is: // Old code ArrayList<X> foo; X get( int i) { return foo.get(i); } .... // New code Object foo; // Can be either ArrayList<X> or pointer to a single X object X get( int i) { if (foo instanceof X) { if (i != 0) throw Exception( "Wrong index!" ); return (X) foo; } else { return ((ArrayList<X>) foo).get(i); } } I've done such optimizations in the past and it can be done here. But as you can see, this results in a somewhat tricky code. Let me know what you think about this.
          Hide
          manojg Manoj Govindassamy added a comment -

          Misha Dmitriev,
          I believe lazy initialization has much bigger impact than replacing it with a simple object or the ArrayList. There is a very high probability for a file/dir not being part of Snapshot tree. But once it is part of the snapshot tree, the likelihood of seeing more than one snapshot is quite high. So IMHO, the second optimization of simple object or ArrayList might not be so useful.

          Show
          manojg Manoj Govindassamy added a comment - Misha Dmitriev , I believe lazy initialization has much bigger impact than replacing it with a simple object or the ArrayList. There is a very high probability for a file/dir not being part of Snapshot tree. But once it is part of the snapshot tree, the likelihood of seeing more than one snapshot is quite high. So IMHO, the second optimization of simple object or ArrayList might not be so useful.
          Hide
          misha@cloudera.com Misha Dmitriev added a comment -

          Hi Manoj Govindassamy,

          With all the due respect, the measurements and calculations done by jxray suggest the contrary. Take a look at this excerpt, that's just for ArrayLists:

          Top bad collections:
              Ovhd           Problem     Num objs      Type
          -------------------------------------------------
          3,056,014K (6.1%)      small     29435572     j.u.ArrayList
          2,641,373K (5.3%)     1-elem     21837906     j.u.ArrayList
          602,470K (1.2%)      empty     18549109     j.u.ArrayList
          

          The overhead for each problem category is calculated as "what would happen if all these ArrayLists are changed to a more optimal representation". Calculating the overhead and dealing with empty lists is obvious (lazy initialization), but as you can see, it will only reclaim 1.2% of memory. "Small" lists, by defintion in jxray, are those that have 2..4 elements. The overhead is calculated as "what would happen if we replace this ArrayList with a plain array". So by just reducing capacity of these ArrayLists, as I've done here, we will, unfortunately, save much less than the maximum 6.1%. Finally, the overhead of 1-element ArrayLists is calculated as "what would happen if they are replaced with direct pointers to contained objects", as I explained above. In that case, the saving will be 5.3% - much bigger than for empty ArrayLists. The reason is that empty ArrayLists are already partially optimized by JDK itself: they all point to the same shared empty internal array.

          Show
          misha@cloudera.com Misha Dmitriev added a comment - Hi Manoj Govindassamy , With all the due respect, the measurements and calculations done by jxray suggest the contrary. Take a look at this excerpt, that's just for ArrayLists: Top bad collections: Ovhd Problem Num objs Type ------------------------------------------------- 3,056,014K (6.1%) small 29435572 j.u.ArrayList 2,641,373K (5.3%) 1-elem 21837906 j.u.ArrayList 602,470K (1.2%) empty 18549109 j.u.ArrayList The overhead for each problem category is calculated as "what would happen if all these ArrayLists are changed to a more optimal representation". Calculating the overhead and dealing with empty lists is obvious (lazy initialization), but as you can see, it will only reclaim 1.2% of memory. "Small" lists, by defintion in jxray, are those that have 2..4 elements. The overhead is calculated as "what would happen if we replace this ArrayList with a plain array". So by just reducing capacity of these ArrayLists, as I've done here, we will, unfortunately, save much less than the maximum 6.1%. Finally, the overhead of 1-element ArrayLists is calculated as "what would happen if they are replaced with direct pointers to contained objects", as I explained above. In that case, the saving will be 5.3% - much bigger than for empty ArrayLists. The reason is that empty ArrayLists are already partially optimized by JDK itself: they all point to the same shared empty internal array.
          Hide
          misha@cloudera.com Misha Dmitriev added a comment -

          Addressed Wei-Chiu Chuang's comments.

          Show
          misha@cloudera.com Misha Dmitriev added a comment - Addressed Wei-Chiu Chuang 's comments.
          Hide
          manojg Manoj Govindassamy added a comment - - edited

          Misha Dmitriev,
          Looks good overall. Can we also please update TestSnapshot or TestSnapshotDeletion to cover the cases like diff toggling between null and not null during addDiff() and deleteSnapshotDiff() operation ?

          Nit: Few places we are using createDiffsIfNeeded() and in few other places we are doing a direct null check and returning null. Though it is contextually right, I am trying to assess the usefulness of that check. If a file/dir has snapshot enabled, then most likely its going to have the diffs. So, will the code be simpler if we just call createDiffsIfNeeded like in other places? But, this might lead to creating empty arraylist when actually not needed?

          Show
          manojg Manoj Govindassamy added a comment - - edited Misha Dmitriev , Looks good overall. Can we also please update TestSnapshot or TestSnapshotDeletion to cover the cases like diff toggling between null and not null during addDiff() and deleteSnapshotDiff() operation ? Nit: Few places we are using createDiffsIfNeeded() and in few other places we are doing a direct null check and returning null. Though it is contextually right, I am trying to assess the usefulness of that check. If a file/dir has snapshot enabled, then most likely its going to have the diffs. So, will the code be simpler if we just call createDiffsIfNeeded like in other places? But, this might lead to creating empty arraylist when actually not needed?
          Hide
          misha@cloudera.com Misha Dmitriev added a comment -

          Manoj Govindassamy,

          I'll add/update the tests and will post another patch.

          As for the second part: I agree that this change will make the code simpler. But currently we do have millions of empty ArrayLists pointed at by FileDiffList.diffs, and my change replaces them with null pointers. So, as you correctly say, if we call createDiffsIfNeeded() every time any read-only operation is attempted on FileDiffList, we may easily re-create millions of empty ArrayLists again.

          Show
          misha@cloudera.com Misha Dmitriev added a comment - Manoj Govindassamy , I'll add/update the tests and will post another patch. As for the second part: I agree that this change will make the code simpler. But currently we do have millions of empty ArrayLists pointed at by FileDiffList.diffs, and my change replaces them with null pointers. So, as you correctly say, if we call createDiffsIfNeeded() every time any read-only operation is attempted on FileDiffList, we may easily re-create millions of empty ArrayLists again.
          Hide
          hadoopqa Hadoop QA added a comment -
          -1 overall



          Vote Subsystem Runtime Comment
          0 reexec 0m 24s Docker mode activated.
          +1 @author 0m 0s The patch does not contain any @author tags.
          +1 test4tests 0m 0s The patch appears to include 1 new or modified test files.
          +1 mvninstall 13m 43s trunk passed
          +1 compile 0m 49s trunk passed
          +1 checkstyle 0m 36s trunk passed
          +1 mvnsite 0m 55s trunk passed
          +1 findbugs 1m 41s trunk passed
          +1 javadoc 0m 40s trunk passed
          +1 mvninstall 0m 53s the patch passed
          +1 compile 0m 46s the patch passed
          +1 javac 0m 46s the patch passed
          +1 checkstyle 0m 34s hadoop-hdfs-project/hadoop-hdfs: The patch generated 0 new + 18 unchanged - 1 fixed = 18 total (was 19)
          +1 mvnsite 0m 52s the patch passed
          +1 whitespace 0m 0s The patch has no whitespace issues.
          +1 findbugs 1m 47s the patch passed
          +1 javadoc 0m 37s the patch passed
          -1 unit 71m 56s hadoop-hdfs in the patch failed.
          +1 asflicense 0m 22s The patch does not generate ASF License warnings.
          97m 55s



          Reason Tests
          Failed junit tests hadoop.hdfs.TestDFSStripedOutputStreamWithFailure080
            hadoop.hdfs.TestDFSStripedInputStreamWithRandomECPolicy
          Timed out junit tests org.apache.hadoop.hdfs.server.blockmanagement.TestBlockStatsMXBean



          Subsystem Report/Notes
          Docker Image:yetus/hadoop:14b5c93
          JIRA Issue HDFS-12042
          JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12874727/HDFS-12042.03.patch
          Optional Tests asflicense compile javac javadoc mvninstall mvnsite unit findbugs checkstyle
          uname Linux 23eaad51ed9c 3.13.0-116-generic #163-Ubuntu SMP Fri Mar 31 14:13:22 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
          Build tool maven
          Personality /testptch/hadoop/patchprocess/precommit/personality/provided.sh
          git revision trunk / 94e39c6
          Default Java 1.8.0_131
          findbugs v3.1.0-RC1
          unit https://builds.apache.org/job/PreCommit-HDFS-Build/20063/artifact/patchprocess/patch-unit-hadoop-hdfs-project_hadoop-hdfs.txt
          Test Results https://builds.apache.org/job/PreCommit-HDFS-Build/20063/testReport/
          modules C: hadoop-hdfs-project/hadoop-hdfs U: hadoop-hdfs-project/hadoop-hdfs
          Console output https://builds.apache.org/job/PreCommit-HDFS-Build/20063/console
          Powered by Apache Yetus 0.5.0-SNAPSHOT http://yetus.apache.org

          This message was automatically generated.

          Show
          hadoopqa Hadoop QA added a comment - -1 overall Vote Subsystem Runtime Comment 0 reexec 0m 24s Docker mode activated. +1 @author 0m 0s The patch does not contain any @author tags. +1 test4tests 0m 0s The patch appears to include 1 new or modified test files. +1 mvninstall 13m 43s trunk passed +1 compile 0m 49s trunk passed +1 checkstyle 0m 36s trunk passed +1 mvnsite 0m 55s trunk passed +1 findbugs 1m 41s trunk passed +1 javadoc 0m 40s trunk passed +1 mvninstall 0m 53s the patch passed +1 compile 0m 46s the patch passed +1 javac 0m 46s the patch passed +1 checkstyle 0m 34s hadoop-hdfs-project/hadoop-hdfs: The patch generated 0 new + 18 unchanged - 1 fixed = 18 total (was 19) +1 mvnsite 0m 52s the patch passed +1 whitespace 0m 0s The patch has no whitespace issues. +1 findbugs 1m 47s the patch passed +1 javadoc 0m 37s the patch passed -1 unit 71m 56s hadoop-hdfs in the patch failed. +1 asflicense 0m 22s The patch does not generate ASF License warnings. 97m 55s Reason Tests Failed junit tests hadoop.hdfs.TestDFSStripedOutputStreamWithFailure080   hadoop.hdfs.TestDFSStripedInputStreamWithRandomECPolicy Timed out junit tests org.apache.hadoop.hdfs.server.blockmanagement.TestBlockStatsMXBean Subsystem Report/Notes Docker Image:yetus/hadoop:14b5c93 JIRA Issue HDFS-12042 JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12874727/HDFS-12042.03.patch Optional Tests asflicense compile javac javadoc mvninstall mvnsite unit findbugs checkstyle uname Linux 23eaad51ed9c 3.13.0-116-generic #163-Ubuntu SMP Fri Mar 31 14:13:22 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux Build tool maven Personality /testptch/hadoop/patchprocess/precommit/personality/provided.sh git revision trunk / 94e39c6 Default Java 1.8.0_131 findbugs v3.1.0-RC1 unit https://builds.apache.org/job/PreCommit-HDFS-Build/20063/artifact/patchprocess/patch-unit-hadoop-hdfs-project_hadoop-hdfs.txt Test Results https://builds.apache.org/job/PreCommit-HDFS-Build/20063/testReport/ modules C: hadoop-hdfs-project/hadoop-hdfs U: hadoop-hdfs-project/hadoop-hdfs Console output https://builds.apache.org/job/PreCommit-HDFS-Build/20063/console Powered by Apache Yetus 0.5.0-SNAPSHOT http://yetus.apache.org This message was automatically generated.
          Hide
          jojochuang Wei-Chiu Chuang added a comment - - edited

          The last patch looks mostly good. When you post another patch, could you also move

          // Profiling shows that most of these lists are between 1 and 4 elements.
          // Thus we allocate the list with a very small initial capacity.
          

          in INodeDirectory#addChild and AbstractINodeDiffList #createDiffsIfNeeded over to DEFAULT_FILES_PER_DIRECTORY?

          Show
          jojochuang Wei-Chiu Chuang added a comment - - edited The last patch looks mostly good. When you post another patch, could you also move // Profiling shows that most of these lists are between 1 and 4 elements. // Thus we allocate the list with a very small initial capacity. in INodeDirectory#addChild and AbstractINodeDiffList #createDiffsIfNeeded over to DEFAULT_FILES_PER_DIRECTORY?
          Hide
          misha@cloudera.com Misha Dmitriev added a comment -

          Addressed the last comment by Wei-Chiu Chuang, submitted HDFS-12042.04.patch.

          Show
          misha@cloudera.com Misha Dmitriev added a comment - Addressed the last comment by Wei-Chiu Chuang , submitted HDFS-12042 .04.patch.
          Hide
          jojochuang Wei-Chiu Chuang added a comment -

          LGTM.
          Would any one else like to chime in?

          Show
          jojochuang Wei-Chiu Chuang added a comment - LGTM. Would any one else like to chime in?
          Hide
          hadoopqa Hadoop QA added a comment -
          -1 overall



          Vote Subsystem Runtime Comment
          0 reexec 0m 14s Docker mode activated.
          +1 @author 0m 0s The patch does not contain any @author tags.
          +1 test4tests 0m 0s The patch appears to include 1 new or modified test files.
          +1 mvninstall 14m 10s trunk passed
          +1 compile 0m 57s trunk passed
          +1 checkstyle 0m 40s trunk passed
          +1 mvnsite 1m 1s trunk passed
          +1 findbugs 1m 45s trunk passed
          +1 javadoc 0m 42s trunk passed
          +1 mvninstall 0m 54s the patch passed
          +1 compile 0m 51s the patch passed
          +1 javac 0m 51s the patch passed
          +1 checkstyle 0m 35s hadoop-hdfs-project/hadoop-hdfs: The patch generated 0 new + 18 unchanged - 1 fixed = 18 total (was 19)
          +1 mvnsite 0m 56s the patch passed
          +1 whitespace 0m 0s The patch has no whitespace issues.
          +1 findbugs 1m 51s the patch passed
          +1 javadoc 0m 40s the patch passed
          -1 unit 69m 48s hadoop-hdfs in the patch failed.
          +1 asflicense 0m 20s The patch does not generate ASF License warnings.
          96m 51s



          Reason Tests
          Failed junit tests hadoop.hdfs.server.datanode.TestDataNodeVolumeFailure
            hadoop.hdfs.TestDFSStripedOutputStreamWithFailure080



          Subsystem Report/Notes
          Docker Image:yetus/hadoop:14b5c93
          JIRA Issue HDFS-12042
          JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12874975/HDFS-12042.04.patch
          Optional Tests asflicense compile javac javadoc mvninstall mvnsite unit findbugs checkstyle
          uname Linux 30ac0dce1acd 3.13.0-116-generic #163-Ubuntu SMP Fri Mar 31 14:13:22 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
          Build tool maven
          Personality /testptch/hadoop/patchprocess/precommit/personality/provided.sh
          git revision trunk / c1edca1
          Default Java 1.8.0_131
          findbugs v3.1.0-RC1
          unit https://builds.apache.org/job/PreCommit-HDFS-Build/20085/artifact/patchprocess/patch-unit-hadoop-hdfs-project_hadoop-hdfs.txt
          Test Results https://builds.apache.org/job/PreCommit-HDFS-Build/20085/testReport/
          modules C: hadoop-hdfs-project/hadoop-hdfs U: hadoop-hdfs-project/hadoop-hdfs
          Console output https://builds.apache.org/job/PreCommit-HDFS-Build/20085/console
          Powered by Apache Yetus 0.5.0-SNAPSHOT http://yetus.apache.org

          This message was automatically generated.

          Show
          hadoopqa Hadoop QA added a comment - -1 overall Vote Subsystem Runtime Comment 0 reexec 0m 14s Docker mode activated. +1 @author 0m 0s The patch does not contain any @author tags. +1 test4tests 0m 0s The patch appears to include 1 new or modified test files. +1 mvninstall 14m 10s trunk passed +1 compile 0m 57s trunk passed +1 checkstyle 0m 40s trunk passed +1 mvnsite 1m 1s trunk passed +1 findbugs 1m 45s trunk passed +1 javadoc 0m 42s trunk passed +1 mvninstall 0m 54s the patch passed +1 compile 0m 51s the patch passed +1 javac 0m 51s the patch passed +1 checkstyle 0m 35s hadoop-hdfs-project/hadoop-hdfs: The patch generated 0 new + 18 unchanged - 1 fixed = 18 total (was 19) +1 mvnsite 0m 56s the patch passed +1 whitespace 0m 0s The patch has no whitespace issues. +1 findbugs 1m 51s the patch passed +1 javadoc 0m 40s the patch passed -1 unit 69m 48s hadoop-hdfs in the patch failed. +1 asflicense 0m 20s The patch does not generate ASF License warnings. 96m 51s Reason Tests Failed junit tests hadoop.hdfs.server.datanode.TestDataNodeVolumeFailure   hadoop.hdfs.TestDFSStripedOutputStreamWithFailure080 Subsystem Report/Notes Docker Image:yetus/hadoop:14b5c93 JIRA Issue HDFS-12042 JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12874975/HDFS-12042.04.patch Optional Tests asflicense compile javac javadoc mvninstall mvnsite unit findbugs checkstyle uname Linux 30ac0dce1acd 3.13.0-116-generic #163-Ubuntu SMP Fri Mar 31 14:13:22 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux Build tool maven Personality /testptch/hadoop/patchprocess/precommit/personality/provided.sh git revision trunk / c1edca1 Default Java 1.8.0_131 findbugs v3.1.0-RC1 unit https://builds.apache.org/job/PreCommit-HDFS-Build/20085/artifact/patchprocess/patch-unit-hadoop-hdfs-project_hadoop-hdfs.txt Test Results https://builds.apache.org/job/PreCommit-HDFS-Build/20085/testReport/ modules C: hadoop-hdfs-project/hadoop-hdfs U: hadoop-hdfs-project/hadoop-hdfs Console output https://builds.apache.org/job/PreCommit-HDFS-Build/20085/console Powered by Apache Yetus 0.5.0-SNAPSHOT http://yetus.apache.org This message was automatically generated.
          Hide
          jojochuang Wei-Chiu Chuang added a comment -

          +1 on rev 04 patch.

          Show
          jojochuang Wei-Chiu Chuang added a comment - +1 on rev 04 patch.
          Hide
          jojochuang Wei-Chiu Chuang added a comment -

          Committed the patch to trunk, branch-2 and branch-2.8.
          For branch-2 and branch-2.8, I had to change a little bit of code to make Java 7 compiler happy.

          Thanks Misha Dmitriev for contributing the code and analysis, and thanks Manoj Govindassamy for comments!

          Show
          jojochuang Wei-Chiu Chuang added a comment - Committed the patch to trunk, branch-2 and branch-2.8. For branch-2 and branch-2.8, I had to change a little bit of code to make Java 7 compiler happy. Thanks Misha Dmitriev for contributing the code and analysis, and thanks Manoj Govindassamy for comments!
          Hide
          hudson Hudson added a comment -

          SUCCESS: Integrated in Jenkins build Hadoop-trunk-Commit #11959 (See https://builds.apache.org/job/Hadoop-trunk-Commit/11959/)
          HDFS-12042. Lazy initialize AbstractINodeDiffList#diffs for snapshots to (weichiu: rev bcba844d1144cc334e2babbc34c9d42eac1c203a)

          • (edit) hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/AbstractINodeDiffList.java
          • (edit) hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java
          • (edit) hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/TestTruncateQuotaUpdate.java
          Show
          hudson Hudson added a comment - SUCCESS: Integrated in Jenkins build Hadoop-trunk-Commit #11959 (See https://builds.apache.org/job/Hadoop-trunk-Commit/11959/ ) HDFS-12042 . Lazy initialize AbstractINodeDiffList#diffs for snapshots to (weichiu: rev bcba844d1144cc334e2babbc34c9d42eac1c203a) (edit) hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/AbstractINodeDiffList.java (edit) hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java (edit) hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/TestTruncateQuotaUpdate.java

            People

            • Assignee:
              misha@cloudera.com Misha Dmitriev
              Reporter:
              misha@cloudera.com Misha Dmitriev
            • Votes:
              0 Vote for this issue
              Watchers:
              12 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development