[ https://issues.apache.org/jira/browse/HDFS-9053?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14934689#comment-14934689 ]
Yi Liu edited comment on HDFS-9053 at 9/29/15 6:55 AM: ------------------------------------------------------- [~jingzhao], you have given a great review, thanks a lot, and it hits the two places I ever considered carefully how to do it better. {quote} In INodeDirectory#replaceChild, can we directly call addOrReplace instead of calling get first? {quote} Good point, I think we can use {{addOrReplace}} directly. Since there should be an INode with the name existing. To keep original behavior, I will remove the added one if {{addOrReplace}} returns null. {quote} Do you think we can avoid the following code? Maybe we can add the EK type to the ReadOnlyCollection/ReadOnlyList level? {quote} That's a good comment, I ever considered this carefully. I also thought adding the EK type as one of generic type to the ReadOnlyCollection/ReadOnlyList level, but I felt it looked not natural for a collection/list, and not all implementations of ReadOnlyList need to implement iterating starting from specified element, also I though it was OK since it's a private interface we use in HDFS. I will update according to your comment, if you feel it's not good later, I can change it back. {quote} DirectoryWithSnapshotFeature#getChildrenList#iterator(EK) forgot to increase pos? Maybe also add a new test for this (e.g., set a small ls limit and list a snapshot of a directory)? {quote} Great catch, let me update it, and add a new test in {{TestLargeDirectory}} to cover. {quote} In getListing, instead of continuing the iteration, can we just call size() to calculate the number of the remaining items? {quote} I ever tried to find a better way. {{size()}} will return the total number of elements in B-Tree, but we don't know the current index, so seems not able to calculate the number of the remaining items. was (Author: hitliuyi): [~jingzhao], you have given a great review, thanks a lot, and it hits the two places I ever considered carefully how to do it better. {quote} In INodeDirectory#replaceChild, can we directly call addOrReplace instead of calling get first? {quote} Good point, I think we can use {{addOrReplace}} directly. Since there should be an INode with the name existing. To keep original behavior, I will remove the added one if {{addOrReplace}} returns null. {quote} Do you think we can avoid the following code? Maybe we can add the EK type to the ReadOnlyCollection/ReadOnlyList level? {quote} That's a good comment, I ever considered this carefully. I also thought adding the EK type as one of generic type to the ReadOnlyCollection/ReadOnlyList level, but I felt it looked not natural for a collection/list, and not all implementations of ReadOnlyList need to implement iterating starting from specified element, also I though it was OK since it's a private interface we use in HDFS. I will leave this comment in next version of patch, if you feel we'd better to do this, I will update it, I am OK with the both ways. {quote} DirectoryWithSnapshotFeature#getChildrenList#iterator(EK) forgot to increase pos? Maybe also add a new test for this (e.g., set a small ls limit and list a snapshot of a directory)? {quote} Great catch, let me update it, and add a new test in {{TestLargeDirectory}} to cover. {quote} In getListing, instead of continuing the iteration, can we just call size() to calculate the number of the remaining items? {quote} I ever tried to find a better way. {{size()}} will return the total number of elements in B-Tree, but we don't know the current index, so seems not able to calculate the number of the remaining items. > Support large directories efficiently using B-Tree > -------------------------------------------------- > > Key: HDFS-9053 > URL: https://issues.apache.org/jira/browse/HDFS-9053 > Project: Hadoop HDFS > Issue Type: Improvement > Components: namenode > Reporter: Yi Liu > Assignee: Yi Liu > Priority: Critical > Attachments: HDFS-9053 (BTree with simple benchmark).patch, HDFS-9053 > (BTree).patch, HDFS-9053.001.patch, HDFS-9053.002.patch > > > This is a long standing issue, we were trying to improve this in the past. > Currently we use an ArrayList for the children under a directory, and the > children are ordered in the list, for insert/delete/search, the time > complexity is O(log n), but insertion/deleting causes re-allocations and > copies of big arrays, so the operations are costly. For example, if the > children grow to 1M size, the ArrayList will resize to > 1M capacity, so need > > 1M * 4bytes = 4M continuous heap memory, it easily causes full GC in HDFS > cluster where namenode heap memory is already highly used. I recap the 3 > main issues: > # Insertion/deletion operations in large directories are expensive because > re-allocations and copies of big arrays. > # Dynamically allocate several MB continuous heap memory which will be > long-lived can easily cause full GC problem. > # Even most children are removed later, but the directory INode still > occupies same size heap memory, since the ArrayList will never shrink. > This JIRA is similar to HDFS-7174 created by [~kihwal], but use B-Tree to > solve the problem suggested by [~shv]. > So the target of this JIRA is to implement a low memory footprint B-Tree and > use it to replace ArrayList. > If the elements size is not large (less than the maximum degree of B-Tree > node), the B-Tree only has one root node which contains an array for the > elements. And if the size grows large enough, it will split automatically, > and if elements are removed, then B-Tree nodes can merge automatically (see > more: https://en.wikipedia.org/wiki/B-tree). It will solve the above 3 > issues. -- This message was sent by Atlassian JIRA (v6.3.4#6332)