hadoop-hdfs-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Yi Liu (JIRA)" <j...@apache.org>
Subject [jira] [Comment Edited] (HDFS-9053) Support large directories efficiently using B-Tree
Date Tue, 29 Sep 2015 06:56:04 GMT

    [ 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)

Mime
View raw message