[ https://issues.apache.org/jira/browse/HDFS-9053?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14934634#comment-14934634 ]
Yi Liu edited comment on HDFS-9053 at 10/1/15 1:32 AM: ------------------------------------------------------- Thanks for the comments, Nicholas. {quote} Where are the numbers, especially the 4s, from? Do we assume a 32-bit world? {quote} {code} public class BTree<K, E extends BTree.Element<K>> implements Iterable<E> { ... private final int degree; private Node root; private int size; private transient int modCount = 0; ... } private final class Node { static final int DEFAULT_CAPACITY = 5; private Object[] elements; private int elementsSize; private Object[] children; private int childrenSize; ... } {code} Sorry, I should use 64-bits system/JVM to describe, and details are: Compared to ArrayList, we increases following things: private final int degree; <--------- 4 bytes Integer private Node root; <--------- reference, 4 bytes on 32-bits system/JVM, 8 bytes on 64-bits system/JVM private int size; <--------- 4 bytes Integer {{Node}} object overhead <---------- 12 bytes private Object[] children; <--------- null reference, 4 bytes on 32-bits system/JVM, 8 bytes on 64-bits system/JVM private int childrenSize; <--------- 4 bytes Integer. So totally 12+4+4+4+4+4+4 = 32 bytes on 32-bits system/JVM, and 16+4+8+4+8+4 = 44 bytes on 64-bits system/JVM. (I have not counted object alignment) was (Author: hitliuyi): Thanks for the comments, Nicholas. {quote} Where are the numbers, especially the 4s, from? Do we assume a 32-bit world? {quote} {code} public class BTree<K, E extends BTree.Element<K>> implements Iterable<E> { ... private final int degree; private Node root; private int size; private transient int modCount = 0; ... } private final class Node { static final int DEFAULT_CAPACITY = 5; private Object[] elements; private int elementsSize; private Object[] children; private int childrenSize; ... } {code} Sorry, I should use 64-bits system/JVM to describe, and details are: Compared to ArrayList, we increases following things: private final int degree; <--------- 4 bytes Integer private Node root; <--------- reference, 4 bytes on 32-bits system/JVM, 8 bytes on 64-bits system/JVM private int size; <--------- 4 bytes Integer {{Node}} object overhead <---------- 12 bytes private Object[] children; <--------- null reference, 4 bytes on 32-bits system/JVM, 8 bytes on 64-bits system/JVM private int childrenSize; <--------- 4 bytes Integer. So totally 12+4+4+4+4+4+4 = 32 bytes on 32-bits system/JVM, and 12+4+8+4+8+4 = 40 bytes on 64-bits system/JVM. (I have not counted object alignment) > 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 > > > 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)