Mailing-List: contact hdfs-issues-help@hadoop.apache.org; run by ezmlm
Precedence: bulk
Reply-To: hdfs-issues@hadoop.apache.org
Date: Fri, 9 Oct 2015 14:52:27 +0000 (UTC)
From: "Yi Liu (JIRA)" <jira@apache.org>
To: hdfs-issues@hadoop.apache.org
Message-ID: <JIRA.12863311.1441956186000.69351.1444402347990@Atlassian.JIRA>
In-Reply-To: <JIRA.12863311.1441956186000@Atlassian.JIRA>
References: <JIRA.12863311.1441956186000@Atlassian.JIRA>
 <JIRA.12863311.1441956186938@arcas>
Subject: [jira] [Comment Edited] (HDFS-9053) Support large directories
 efficiently using B-Tree
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

Yi Liu edited comment on HDFS-9053 at 10/9/15 2:51 PM:
-------------------------------------------------------

I find a good approach to improve B-Tree memory overhead to make it only increase *8 bytes* memory usage comparing with using {{ArrayList}} for small elements size. 
So we don't need to use ArrayList when #children is small (< 4K), and we can always use the {{BTree}}.
The main idea is to let {{BTree}} extend the BTree Node, then we don't need a separate root node, since {{BTree}} itself is the root.

{noformat}
java.util.ArrayList object internals:
 OFFSET  SIZE     TYPE DESCRIPTION                    VALUE
      0    16          (object header)                N/A
     16     4      int AbstractList.modCount          N/A
     20     4          (alignment/padding gap)        N/A
     24     4      int ArrayList.size                 N/A
     28     4          (alignment/padding gap)        N/A
     32     8 Object[] ArrayList.elementData          N/A
Instance size: 40 bytes (estimated, the sample instance is not available)
{noformat}

{noformat}
org.apache.hadoop.util.btree.BTree object internals:
 OFFSET  SIZE     TYPE DESCRIPTION                    VALUE
      0    16          (object header)                N/A
     16     4      int Node.elementsSize              N/A
     20     4      int Node.childrenSize              N/A
     24     8 Object[] Node.elements                  N/A
     32     8 Object[] Node.children                  N/A
     40     4      int BTree.size                     N/A
     44     4      int BTree.modCount                 N/A
Instance size: 48 bytes (estimated, the sample instance is not available)
{noformat}
We can see {{BTree}} only increases *8 bytes* comparing with {{ArrayList}} for a {{INodeDirectory}}.

[~jingzhao], [~szetszwo], please look at the new patch {{006}}.


was (Author: hitliuyi):
I find a good approach to improve B-Tree overhead to make it only increase *8 bytes* memory usage comparing with using {{ArrayList}} for small elements size. 
So we don't need to use ArrayList when #children is small (< 4K), and we can always use the {{BTree}}.
The main idea is to let {{BTree}} extend the BTree Node, then we don't need a separate root node, since {{BTree}} itself is the root.

{noformat}
java.util.ArrayList object internals:
 OFFSET  SIZE     TYPE DESCRIPTION                    VALUE
      0    16          (object header)                N/A
     16     4      int AbstractList.modCount          N/A
     20     4          (alignment/padding gap)        N/A
     24     4      int ArrayList.size                 N/A
     28     4          (alignment/padding gap)        N/A
     32     8 Object[] ArrayList.elementData          N/A
Instance size: 40 bytes (estimated, the sample instance is not available)
{noformat}

{noformat}
org.apache.hadoop.util.btree.BTree object internals:
 OFFSET  SIZE     TYPE DESCRIPTION                    VALUE
      0    16          (object header)                N/A
     16     4      int Node.elementsSize              N/A
     20     4      int Node.childrenSize              N/A
     24     8 Object[] Node.elements                  N/A
     32     8 Object[] Node.children                  N/A
     40     4      int BTree.size                     N/A
     44     4      int BTree.modCount                 N/A
Instance size: 48 bytes (estimated, the sample instance is not available)
{noformat}
We can see {{BTree}} only increases *8 bytes* comparing with {{ArrayList}} for a {{INodeDirectory}}.

[~jingzhao], [~szetszwo], please look at the new patch {{006}}.

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