hadoop-hdfs-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Hadoop QA (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HDFS-9053) Support large directories efficiently using B-Tree
Date Tue, 20 Oct 2015 07:09:27 GMT

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

Hadoop QA commented on HDFS-9053:
---------------------------------

\\
\\
| (x) *{color:red}-1 overall{color}* |
\\
\\
|| Vote || Subsystem || Runtime || Comment ||
| {color:red}-1{color} | pre-patch |  23m 13s | Pre-patch trunk has 1 extant Findbugs (version
3.0.0) warnings. |
| {color:green}+1{color} | @author |   0m  0s | The patch does not contain any @author tags.
|
| {color:green}+1{color} | tests included |   0m  0s | The patch appears to include 8 new
or modified test files. |
| {color:green}+1{color} | javac |   8m 40s | There were no new javac warning messages. |
| {color:green}+1{color} | javadoc |  11m 28s | There were no new javadoc warning messages.
|
| {color:green}+1{color} | release audit |   0m 28s | The applied patch does not increase
the total number of release audit warnings. |
| {color:red}-1{color} | checkstyle |   2m  9s | The applied patch generated  7 new checkstyle
issues (total was 0, now 7). |
| {color:green}+1{color} | whitespace |   0m 11s | The patch has no lines that end in whitespace.
|
| {color:green}+1{color} | install |   2m  5s | mvn install still works. |
| {color:green}+1{color} | eclipse:eclipse |   0m 39s | The patch built with eclipse:eclipse.
|
| {color:green}+1{color} | findbugs |   5m 24s | The patch does not introduce any new Findbugs
(version 3.0.0) warnings. |
| {color:red}-1{color} | common tests |   8m 44s | Tests failed in hadoop-common. |
| {color:red}-1{color} | hdfs tests |  52m 27s | Tests failed in hadoop-hdfs. |
| | | 115m 59s | |
\\
\\
|| Reason || Tests ||
| Failed unit tests | hadoop.ha.TestZKFailoverController |
|   | hadoop.ipc.TestIPC |
|   | hadoop.fs.viewfs.TestViewFsAtHdfsRoot |
|   | hadoop.hdfs.TestLeaseRecovery2 |
\\
\\
|| Subsystem || Report/Notes ||
| Patch URL | http://issues.apache.org/jira/secure/attachment/12767526/HDFS-9053.007.patch
|
| Optional Tests | javadoc javac unit findbugs checkstyle |
| git revision | trunk / 9cb5d35 |
| Pre-patch Findbugs warnings | https://builds.apache.org/job/PreCommit-HDFS-Build/13075/artifact/patchprocess/trunkFindbugsWarningshadoop-hdfs.html
|
| checkstyle |  https://builds.apache.org/job/PreCommit-HDFS-Build/13075/artifact/patchprocess/diffcheckstylehadoop-common.txt
|
| hadoop-common test log | https://builds.apache.org/job/PreCommit-HDFS-Build/13075/artifact/patchprocess/testrun_hadoop-common.txt
|
| hadoop-hdfs test log | https://builds.apache.org/job/PreCommit-HDFS-Build/13075/artifact/patchprocess/testrun_hadoop-hdfs.txt
|
| Test Results | https://builds.apache.org/job/PreCommit-HDFS-Build/13075/testReport/ |
| Java | 1.7.0_55 |
| uname | Linux asf901.gq1.ygridcore.net 3.13.0-36-lowlatency #63-Ubuntu SMP PREEMPT Wed Sep
3 21:56:12 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux |
| Console output | https://builds.apache.org/job/PreCommit-HDFS-Build/13075/console |


This message was automatically generated.

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

Mime
View raw message