[jira] [Commented] (HDFS-9053) Support large directories efficiently using B-Tree

["Yi Liu (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/HDFS-9053?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14740370#comment-14740370 ] 

Yi Liu commented on HDFS-9053:
------------------------------

Current patch only includes my implementation of B-Tree, I will post the patch integration with {{INodeDirectory}} later. 
Code logic of B-Tree is more complex than other normal data structure, the most challenged part is remove/merge, insert/split, iteration.  I refer to google implementation of B-Tree in Go language (https://github.com/google/btree), and borrow their merge, split logic. So the correctness of that part should be already verified in practice. I checked the B-Tree implementation carefully according to B-Tree definition, also did many tests to make sure B-Tree implementation correct.  Later, I will give some performance data of insertion/deletion/searching comparing between B-Tree and ArrayList.
The implementation in patch is low memory footprint, if the elements size is not large (less than the maximum degree of B-Tree node), the B-Tree will only have one root node and contains an array for the elements, and the children array is null. I use java array for the elements and children, and control the expand in the code myself to save the object overhead and can use fewer memory compared to use ArrayList.

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