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 "Sangjin Lee (JIRA)" <ji...@apache.org> on 2016/05/12 22:23:13 UTC
[jira] [Commented] (HDFS-9053) Support large directories
efficiently using B-Tree
[ https://issues.apache.org/jira/browse/HDFS-9053?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15282164#comment-15282164 ]
Sangjin Lee commented on HDFS-9053:
-----------------------------------
There has been no movement on this for a while. We'll need to move it out of scope for 2.8.0 soon. Let me know if you disagree.
> 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, HDFS-9053.003.patch, HDFS-9053.004.patch, HDFS-9053.005.patch, HDFS-9053.006.patch, HDFS-9053.007.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, the time complexity is O\(n), (the search is O(log n), but insertion/deleting causes re-allocations and copies of arrays), for large directory, the operations are expensive. If the children grow to 1M size, the ArrayList will resize to > 1M capacity, so need > 1M * 8bytes = 8M (the reference size is 8 for 64-bits system/JVM) 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)
---------------------------------------------------------------------
To unsubscribe, e-mail: hdfs-issues-unsubscribe@hadoop.apache.org
For additional commands, e-mail: hdfs-issues-help@hadoop.apache.org