You are viewing a plain text version of this content. The canonical link for it is here.
Posted to hdfs-issues@hadoop.apache.org by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org> on 2010/04/28 10:15:32 UTC
[jira] Created: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Reducing NameNode memory usage by an alternate hash table
---------------------------------------------------------
Key: HDFS-1114
URL: https://issues.apache.org/jira/browse/HDFS-1114
Project: Hadoop HDFS
Issue Type: Improvement
Components: name-node
Reporter: Tsz Wo (Nicholas), SZE
NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12874895#action_12874895 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
Thanks Suresh that he found out an interesting post explaining [why java.util.HashMap uses power of two table length|http://www.roseindia.net/javatutorials/javahashmap.shtml].
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12881764#action_12881764 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
> There is also a way to check if the VM is 64 bit or 32 bit, either its out of ManagementFactory or one of the system properties. Digging around I don't see it, but I have used it before. I think it is vendor specific though.
I used System.getProperty("sun.arch.data.model") in the patch. See http://java.sun.com/docs/hotspot/HotSpotFAQ.html#64bit_detection
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: h1114_20100617.patch
h1114_20100617.patch: the UnsupportedOperationException thrown in put(..) should be NullPointerException.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Status: Patch Available (was: Open)
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: benchmark20100618.patch
benchmark20100618.patch: additional codes for benchmark and memory footprint measurement.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Scott Carey (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12878462#action_12878462 ]
Scott Carey commented on HDFS-1114:
-----------------------------------
if you are using a power of two hash table, you can avoid problems caused by hash value clustering by using a Fibonacci Hash. Essentially, use the multiplicative hash with a special value g:
(h * g) & mask
where h is the hash value and g is the 'golden ratio' number for the size of the table used. Since multiplication on today's processors is far faster than division or remainders, this can be used to 'uncluster' hash values. A single consecutive run of values gets maximally distributed into the space, and high and low bits are redistributed evenly so that the mask does not increase collisions. Whether this is a desired property or not will depend on the properties of the hash values and whether or not an open addressing solution is used.
Open addressing can further reduce the memory footprint by allowing the raw object to be placed in the map instead of a container object or list.
some links found from a few searches:
http://www.brpreiss.com/books/opus4/html/page214.html
http://staff.newport.ac.uk/ctubb01/ct/advp/hashtables.pdf
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Suresh Srinivas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12875211#action_12875211 ]
Suresh Srinivas commented on HDFS-1114:
---------------------------------------
# Not using supplemental hash function will result in severe clustering when we move to sequential block IDs (as only higher bits are used for hash).
# Why do we need configurability of either using java HashMap or this new implementation?
#* With new impl, BlockInfo implements LinkedElement interface. On switching to java HashMap would it continue to implement this interface and incur the cost of {{next}} member in BlockInfo?
# In "Arrays" section the GC behavior description was not clear. Not sure how the GC behavior is better with arrays?
# Static array size for the map simplifies the code, but pushes complexity to the cluster admin by adding one more configuration. This configuration is an internal implementation detail which a cluster admin may not understand and get it right. If it configured wrong and the cluster continues to work, cluster admin may not be aware of performance degradation.
# I feel we should implement resizing to avoid introducing config param. It is a rare event on a stable cluster. NN has enough heap head room to account for floating garage and YG guarantee. Hence availability of memory should not be an issue. Worst case scenario, resize may trigger a full GC.
# If we implement resizing we should also think about 2^N table size as it has potential to waste a lot of memory during doubling, especially considering millions of entries in the table.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: h1114_20100617b_y0.20.1xx.patch
h1114_20100617b_y0.20.1xx.patch: for y0.20.1xx
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch, h1114_20100617b_y0.20.1xx.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: h1114_20100614b.patch
h1114_20100614b.patch:
- changed BlocksMap and BlockInfo in order to use LightWeightGSet.
- changed TestGSet for faster execution time. It took 3.141 seconds in my machine.
- added new tests for the exception cases.
Have run a large set of tests (see TestGSet.runMultipleTestGSet()) with various parameters. It took 5.5 hours and passed all tests.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879990#action_12879990 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
Note that we should minus 4*1000000 ~= 4MB for HashMap since it does not require the reference for LightWeightGSet.LinkedElement.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: h1114_20100616b.patch
h1114_20100616b:
- Rewrote codes on capacity computation
- By following Java, throwing NPE instead of IllegalArugmentException when the parameter is null.
- Split toString() to two methods.
- Catching specific exception and added more comments on the test.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879949#action_12879949 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
Thanks Suresh.
Hudson is not responding. Ran tests locally
{noformat}
[exec] +1 overall.
[exec]
[exec] +1 @author. The patch does not contain any @author tags.
[exec]
[exec] +1 tests included. The patch appears to include 17 new or modified tests.
[exec]
[exec] +1 javadoc. The javadoc tool did not generate any warning messages.
[exec]
[exec] +1 javac. The applied patch does not increase the total number of javac compiler warnings.
[exec]
[exec] +1 findbugs. The patch does not introduce any new Findbugs warnings.
[exec]
[exec] +1 release audit. The applied patch does not increase the total number of release audit warnings.
{noformat}
Passed all tests except TestFiHFlush sometimes fails; see HDFS-1206.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: h1114_20100615.patch
h1114_20100615.patch: added close(). Otherwise, some tests will fail with OutOfMemory.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: gset20100702.tex
gset20100702.tex: source file of the pdf.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, gset20100702.pdf, gset20100702.tex, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch, h1114_20100617b2_y0.20.1xx.patch, h1114_20100617b_y0.20.1xx.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12862583#action_12862583 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
I believe we can save from 24 to 40 bytes per entry. It depends on the chosen implementation (will give more details later).
In a large clusters, there are ~60m blocks. Then, we may save from 1.5GB to 2.5GB NN memory.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Suresh Srinivas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879944#action_12879944 ]
Suresh Srinivas commented on HDFS-1114:
---------------------------------------
+1 for the patch.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Status: Patch Available (was: Open)
Hudson does not seem working. It did not pick up my previous for a long time. Re-submit.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: gset20100702.pdf
gset20100702.pdf: added a result section.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, gset20100702.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch, h1114_20100617b2_y0.20.1xx.patch, h1114_20100617b_y0.20.1xx.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12862118#action_12862118 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
The data structure we need in BlocksMap is a GettableSet.
{code}
/**
* A set which supports the get operation.
* @param <E> The type of the elements.
*/
public interface GettableSet<E> extends Iterable<E> {
/**
* @return the size of this set.
*/
int size();
/**
* @return true if the given element equals to a stored element.
* Otherwise, return false.
*/
boolean contains(Object element);
/**
* @return the stored element if there is any. Otherwise, return null.
*/
E get(Object element);
/**
* Add the given element to this set.
* @return the previous stored element if there is any.
* Otherwise, return null.
*/
E add(E element);
/**
* Remove the element from the set.
* @return the stored element if there is any. Otherwise, return null.
*/
E remove(Object element);
}
{code}
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12878621#action_12878621 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
Scott, thanks for your comments and the useful links.
Since Block IDs are random, we don't need the extra computation in our case. For general hash table implementation, it is definitely a good idea.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: h1114_20100607.patch
Suresh, thanks for your comment. I will update the design doc soon.
h1114_20100607.patch: LightWeightGSet
- Not yet changed BlocksMap
- Need more tests and decrease the test running time (currently is ~15 minutes).
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, h1114_20100607.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Status: Patch Available (was: Open)
Try resubmitting.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: gset20100608.pdf
> 1. Not using supplemental hash function will result in severe clustering when we move to sequential block IDs (as only higher bits are used for hash).
It is not a problem in our case because the hashCode() implematation in Block uses both higher and lower bits of the block ID.
> 3. In "Arrays" section the GC behavior description was not clear. Not sure how the GC behavior is better with arrays?
The GC algorithm traverses the objects to determine which objects can be garbage collected. The GC behavior is better in arrays in the sense that there are fewer references in arrays.
> 2, 4, 5 & 6
All this items are related to configuration and the hash table length. See the new design doc.
gset20100608.pdf: rewrote Section 7
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Scott Carey (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879633#action_12879633 ]
Scott Carey commented on HDFS-1114:
-----------------------------------
bq. # Capacity should be divided by a reference size 8 or 4 depending on the 64bit or 32bit java version
What about -XX:+UseCompressedOops ?
All users should be using this flag on a 64 bit JVM to save a lot of space. It only works up to -Xmx32G though, beyond that its large pointers again.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Suresh Srinivas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12882253#action_12882253 ]
Suresh Srinivas commented on HDFS-1114:
---------------------------------------
Minor comment: TestGSet in Y20 version can be a junit4 test. You do not need to extend TestCase.
+1 for the patch.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch, h1114_20100617b_y0.20.1xx.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Status: Resolved (was: Patch Available)
Hadoop Flags: [Reviewed]
Fix Version/s: 0.22.0
Resolution: Fixed
I have committed this.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Suresh Srinivas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879864#action_12879864 ]
Suresh Srinivas commented on HDFS-1114:
---------------------------------------
# For figuring out 64 bit, should we consider the max heap size. If max heap size > 2G consider it as 64 bit machine. Since max heap size on 32 bit machines vary, 1.4G to 2G, such machines in that range could be wrongly classified as 32 bit. Is this an alternative worth considering?
# Minor: "print detail" to "print detailed"
# Minor: For end of line comments should there be space after //. Java coding conventions explicitly do not talk about this though. Currently there 3043 comments with space after // and 384 without that :-)
# Minor: In exceptions tests, in my previous comment, what I meant was you are better of printing to log in Assert.fail(). Printing log when expected thing happens is not that useful. That said, this is minor, you can leave it as it is.
# I am not sure what the point of commenting out 5 hours test is. When do we expect it to be uncommented and run? Should it be moved to some other test that is run as smoke test for release qualification?
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879975#action_12879975 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
Ran some benchmarks. When the modulus is large, which means that number of collisions is small, LightWeightGSet is much better than GSetByHashMap.
|| datasize || modulus || GSetByHashMap|| LightWeightGSet||
| 65536 | 1025 | 219 | 234|
| 65536 | 1048577 | 516 | 296|
| 65536 | 1073741825 | 500 | 281|
| 262144 | 1025 | 1422 | 1531|
| 262144 | 1048577 | 3078 | 2156|
| 262144 | 1073741825 | 3094 | 2281|
| 1048576 | 1025 | 7172 | 7313|
| 1048576 | 1048577 | 13531 | 9844|
| 1048576 | 1073741825 | 14485 | 10718|
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Suresh Srinivas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12882307#action_12882307 ]
Suresh Srinivas commented on HDFS-1114:
---------------------------------------
+1 for the new patch.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch, h1114_20100617b2_y0.20.1xx.patch, h1114_20100617b_y0.20.1xx.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Scott Carey (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12880423#action_12880423 ]
Scott Carey commented on HDFS-1114:
-----------------------------------
bq. This is a good point. Is there a way to determine if UseCompressedOops is set in runtime?
Well, there is ManagementFactory.getRuntimeMXBean().getInputArguments(), but later versions of Java are going to be making +UseCompressedOops the default.
There is also a way to check if the VM is 64 bit or 32 bit, either its out of ManagementFactory or one of the system properties. Digging around I don't see it, but I have used it before. I think it is vendor specific though.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE reassigned HDFS-1114:
--------------------------------------------
Assignee: Tsz Wo (Nicholas), SZE
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12861725#action_12861725 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
In Java 1.6, java.util.HashMap has an array of HashMap.Entry
{code}
//HashMap
transient Entry[] table;
{code}
where HashMap.Entry has the following members
{code}
//HashMap.Entry
final K key;
V value;
Entry<K,V> next;
final int hash;
{code}
In the BlocksMap, we have the following invariants
- K == V == BlockInfo
- key == value, i.e. they point to the same BlockInfo object.
Therefore, we may reduce the memory footprint by
# eliminating HashMap.Entry class
# keeping only one object reference
# possibly eliminating next and hash
Will provide more design details.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Konstantin Shvachko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12862509#action_12862509 ]
Konstantin Shvachko commented on HDFS-1114:
-------------------------------------------
Do you have an estimate on how much space this will save in NN's memory footprint?
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879989#action_12879989 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
Comparing memory footprint on a 32-bit VM over 1,000,000 elements
{noformat}
num #instances #bytes class name
----------------------------------------------
1: 1000040 24000960 java.util.HashMap$Entry
2: 1000000 24000000 org.apache.hadoop.hdfs.util.TestGSet$IntElement
3: 23 8390960 [Ljava.util.HashMap$Entry;
HashMap: 53.78 MB
num #instances #bytes class name
----------------------------------------------
1: 1000000 24000000 org.apache.hadoop.hdfs.util.TestGSet$IntElement
2: 1 4194320 [Lorg.apache.hadoop.hdfs.util.LightWeightGSet$LinkedElement;
LightWeightGSet: 26.89 MB
{noformat}
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Suresh Srinivas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879582#action_12879582 ]
Suresh Srinivas commented on HDFS-1114:
---------------------------------------
# BlocksMap.java
#* typo exponient. Should be exponent?
#* Capacity should be divided by a reference size 8 or 4 depending on the 64bit or 32bit java version
#* Current capacity calculation seems quite complex. Add more explanation on why it is implemented that way.
# LightWeightGSet.java
#* "which uses a hash table for storing the elements" should this say "uses array"?
#* Add a comment that the size of entries is power of two
#* Throw HadoopIllegalArgumentException instead of IllegalArgumentException (for 20 version of the patch it could remain IllegalArugmentException)
#* remove() - for better readability no need for else if and else since the previous block returns
#* toString() - prints the all the entries. This is a bad idea if some one passes this object to Log unknowingly. If all the details of the HashMap is needed, we should have some other method such as dump() or printDetails() to do the same.
# TestGSet.java
#* In exception tests, instead of printing log when expected exception happened, print a log in Assert.fail(), like Assert.fail("Excepected exception was not thrown"). Check for exceptions should be more specific, instead Exception. It is also good idea to document these exceptions in javadoc for methods in GSet.
#* println should use Log.info instead of System.out.println?
#* add some comments to classes on what they do/how they are used
#* add some comments to GSetTestCase members denominator etc. and constructor
#* add comments to testGSet() on what each of the case is accomplishing
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: GSet20100525.pdf
GSet20100525.pdf: a design doc.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: h1114_20100617b2_y0.20.1xx.patch
Thanks Suresh.
h1114_20100617b2_y0.20.1xx.patch: used the original junit 4 TestGSet
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch, h1114_20100617b2_y0.20.1xx.patch, h1114_20100617b_y0.20.1xx.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879836#action_12879836 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
> What about -XX:+UseCompressedOops ?
This is a good point. Is there a way to determine if UseCompressedOops is set in runtime?
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Hudson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12879988#action_12879988 ]
Hudson commented on HDFS-1114:
------------------------------
Integrated in Hadoop-Hdfs-trunk-Commit #311 (See [http://hudson.zones.apache.org/hudson/job/Hadoop-Hdfs-trunk-Commit/311/])
HDFS-1114. Implement LightWeightGSet for BlocksMap in order to reduce NameNode memory footprint.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Status: Open (was: Patch Available)
Thanks for the detail review, Suresh.
1. BlocksMap.java
done.
2. LightWeightGSet.java
done all except the follwoing.
* remove() - for better readability ...
Implicit else is better the explicit else?
3. TestGSet.java
* In exception tests, ...
Catching specific exceptions but I did not change the messages.
* println should use Log.info instead of System.out.println?
No, print(..) and println(..) work together.
* add some comments to ...
* add some comments to ...
* add comments to ...
Added more some comments.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Status: Open (was: Patch Available)
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12884372#action_12884372 ]
Tsz Wo (Nicholas), SZE commented on HDFS-1114:
----------------------------------------------
Ravi has done some performance analysis on Yahoo! production cluster fs image.
46400490 files & directories , 70074790 blocks = 116475280
FsImage Disk size - 7.5GB.
| || heap size at NN startup || fsimage loading time |
| Without the patch | 19.64 GB | 603 s |
| With the patch | 17.03 GB | 577 s|
| % improvement | 13.2% | 4.3%|
Thanks Ravi!
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Fix For: 0.22.0
>
> Attachments: benchmark20100618.patch, GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch, h1114_20100617b2_y0.20.1xx.patch, h1114_20100617b_y0.20.1xx.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HDFS-1114) Reducing NameNode memory usage by an
alternate hash table
Posted by "Tsz Wo (Nicholas), SZE (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-1114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tsz Wo (Nicholas), SZE updated HDFS-1114:
-----------------------------------------
Attachment: h1114_20100617b.patch
h1114_20100617b.patch: slightly changed the comments and removed unnecessary spaces.
I did not change the capacity calculation because the current computation is conservative on the special cases.
> Reducing NameNode memory usage by an alternate hash table
> ---------------------------------------------------------
>
> Key: HDFS-1114
> URL: https://issues.apache.org/jira/browse/HDFS-1114
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: name-node
> Reporter: Tsz Wo (Nicholas), SZE
> Assignee: Tsz Wo (Nicholas), SZE
> Attachments: GSet20100525.pdf, gset20100608.pdf, h1114_20100607.patch, h1114_20100614b.patch, h1114_20100615.patch, h1114_20100616b.patch, h1114_20100617.patch, h1114_20100617b.patch
>
>
> NameNode uses a java.util.HashMap to store BlockInfo objects. When there are many blocks in HDFS, this map uses a lot of memory in the NameNode. We may optimize the memory usage by a light weight hash table implementation.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.