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 17:49:06 +0000 (UTC)
From: "Hadoop QA (JIRA)" <jira@apache.org>
To: hdfs-issues@hadoop.apache.org
Message-ID: <JIRA.12863311.1441956186000.530.1444412946170@Atlassian.JIRA>
In-Reply-To: <JIRA.12863311.1441956186000@Atlassian.JIRA>
References: <JIRA.12863311.1441956186000@Atlassian.JIRA>
 <JIRA.12863311.1441956186938@arcas>
Subject: [jira] [Commented] (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=14950856#comment-14950856 ] 

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

\\
\\
| (x) *{color:red}-1 overall{color}* |
\\
\\
|| Vote || Subsystem || Runtime || Comment ||
| {color:blue}0{color} | pre-patch |  22m 41s | Pre-patch trunk compilation is healthy. |
| {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 55s | There were no new javac warning messages. |
| {color:green}+1{color} | javadoc |  11m 28s | There were no new javadoc warning messages. |
| {color:red}-1{color} | release audit |   0m 22s | The applied patch generated 1 release audit warnings. |
| {color:red}-1{color} | checkstyle |   2m  6s | The applied patch generated  8 new checkstyle issues (total was 0, now 8). |
| {color:red}-1{color} | whitespace |   0m 10s | The patch has 1  line(s) that end in whitespace. Use git apply --whitespace=fix. |
| {color:green}+1{color} | install |   1m 47s | mvn install still works. |
| {color:green}+1{color} | eclipse:eclipse |   0m 38s | The patch built with eclipse:eclipse. |
| {color:green}+1{color} | findbugs |   4m 47s | The patch does not introduce any new Findbugs (version 3.0.0) warnings. |
| {color:green}+1{color} | common tests |   7m 48s | Tests passed in hadoop-common. |
| {color:red}-1{color} | hdfs tests | 120m 50s | Tests failed in hadoop-hdfs. |
| | | 181m 56s | |
\\
\\
|| Reason || Tests ||
| Failed unit tests | hadoop.hdfs.TestWriteRead |
|   | hadoop.hdfs.server.namenode.ha.TestDNFencing |
|   | hadoop.hdfs.TestHFlush |
|   | hadoop.security.TestPermission |
|   | hadoop.hdfs.TestParallelRead |
|   | hadoop.fs.viewfs.TestViewFsHdfs |
|   | hadoop.hdfs.TestBlockReaderLocalLegacy |
|   | hadoop.hdfs.server.namenode.TestXAttrConfigFlag |
|   | hadoop.hdfs.TestPread |
|   | hadoop.hdfs.TestMiniDFSCluster |
|   | hadoop.hdfs.TestDFSStripedOutputStream |
|   | hadoop.hdfs.TestWriteConfigurationToDFS |
|   | hadoop.hdfs.TestDatanodeRegistration |
|   | hadoop.hdfs.web.TestWebHDFSXAttr |
|   | hadoop.hdfs.TestDFSRollback |
|   | hadoop.hdfs.TestDataTransferKeepalive |
|   | hadoop.hdfs.server.namenode.ha.TestDelegationTokensWithHA |
|   | hadoop.hdfs.TestDatanodeConfig |
|   | hadoop.hdfs.TestDFSFinalize |
|   | hadoop.hdfs.server.namenode.ha.TestGetGroupsWithHA |
|   | hadoop.fs.TestWebHdfsFileContextMainOperations |
|   | hadoop.fs.TestGlobPaths |
|   | hadoop.hdfs.TestDFSShell |
|   | hadoop.hdfs.tools.TestDFSHAAdminMiniCluster |
|   | hadoop.hdfs.TestSeekBug |
|   | hadoop.fs.loadGenerator.TestLoadGenerator |
|   | hadoop.hdfs.TestCrcCorruption |
|   | hadoop.fs.contract.hdfs.TestHDFSContractMkdir |
|   | hadoop.hdfs.TestAbandonBlock |
|   | hadoop.hdfs.TestGetFileChecksum |
|   | hadoop.hdfs.TestSafeModeWithStripedFile |
|   | hadoop.hdfs.tools.offlineImageViewer.TestOfflineImageViewerForContentSummary |
|   | hadoop.hdfs.TestFileCreationDelete |
|   | hadoop.hdfs.TestReadWhileWriting |
|   | hadoop.fs.viewfs.TestViewFileSystemWithAcls |
|   | hadoop.fs.contract.hdfs.TestHDFSContractConcat |
|   | hadoop.hdfs.TestDFSStripedOutputStreamWithFailure010 |
|   | hadoop.hdfs.util.TestDiff |
|   | hadoop.hdfs.security.TestDelegationToken |
|   | hadoop.fs.TestSymlinkHdfsDisable |
|   | hadoop.fs.contract.hdfs.TestHDFSContractRootDirectory |
|   | hadoop.hdfs.TestMissingBlocksAlert |
|   | hadoop.hdfs.TestBlocksScheduledCounter |
|   | hadoop.hdfs.TestSmallBlock |
|   | hadoop.cli.TestDeleteCLI |
|   | hadoop.hdfs.TestDFSClientRetries |
|   | hadoop.fs.viewfs.TestViewFsWithXAttrs |
|   | hadoop.hdfs.TestDFSMkdirs |
|   | hadoop.hdfs.tools.TestDFSAdmin |
|   | hadoop.hdfs.server.namenode.TestFavoredNodesEndToEnd |
|   | hadoop.hdfs.server.namenode.TestNameNodeMXBean |
|   | hadoop.hdfs.web.TestWebHDFSForHA |
|   | hadoop.fs.viewfs.TestViewFsDefaultValue |
|   | hadoop.fs.contract.hdfs.TestHDFSContractOpen |
|   | hadoop.hdfs.server.namenode.TestDeleteRace |
|   | hadoop.hdfs.TestFSInputChecker |
|   | hadoop.hdfs.web.TestWebHdfsWithAuthenticationFilter |
|   | hadoop.fs.contract.hdfs.TestHDFSContractRename |
|   | hadoop.hdfs.server.namenode.ha.TestXAttrsWithHA |
|   | hadoop.hdfs.server.namenode.ha.TestHAMetrics |
|   | hadoop.cli.TestErasureCodingCLI |
|   | hadoop.hdfs.TestRollingUpgradeRollback |
|   | hadoop.hdfs.TestRemoteBlockReader |
|   | hadoop.hdfs.server.namenode.TestNameNodeResourceChecker |
|   | hadoop.hdfs.tools.TestDFSAdminWithHA |
|   | hadoop.hdfs.TestBlockStoragePolicy |
|   | hadoop.hdfs.TestLeaseRecovery |
|   | hadoop.fs.viewfs.TestViewFsAtHdfsRoot |
|   | hadoop.hdfs.TestBlockReaderLocal |
|   | hadoop.fs.contract.hdfs.TestHDFSContractGetFileStatus |
|   | hadoop.cli.TestCryptoAdminCLI |
|   | hadoop.hdfs.tools.offlineImageViewer.TestOfflineImageViewerForXAttr |
|   | hadoop.hdfs.tools.TestDebugAdmin |
|   | hadoop.security.TestRefreshUserMappings |
|   | hadoop.hdfs.TestReadStripedFileWithDecoding |
|   | hadoop.hdfs.TestLargeBlock |
|   | hadoop.fs.viewfs.TestViewFileSystemWithXAttrs |
|   | hadoop.hdfs.tools.TestDFSZKFailoverController |
|   | hadoop.hdfs.TestDistributedFileSystem |
|   | hadoop.hdfs.TestListFilesInFileContext |
|   | hadoop.hdfs.tools.TestDelegationTokenFetcher |
|   | hadoop.fs.TestFcHdfsSetUMask |
|   | hadoop.hdfs.security.TestClientProtocolWithDelegationToken |
|   | hadoop.hdfs.TestLeaseRecovery2 |
|   | hadoop.hdfs.TestDatanodeReport |
|   | hadoop.hdfs.TestFileAppend2 |
|   | hadoop.fs.shell.TestHdfsTextCommand |
|   | hadoop.hdfs.TestFsShellPermission |
|   | hadoop.hdfs.TestHDFSServerPorts |
|   | hadoop.hdfs.TestRollingUpgradeDowngrade |
|   | hadoop.hdfs.TestFileLengthOnClusterRestart |
|   | hadoop.hdfs.security.TestDelegationTokenForProxyUser |
|   | hadoop.hdfs.TestWriteReadStripedFile |
|   | hadoop.TestGenericRefresh |
|   | hadoop.hdfs.TestParallelUnixDomainRead |
|   | hadoop.fs.TestSymlinkHdfsFileSystem |
|   | hadoop.hdfs.TestGetBlocks |
|   | hadoop.hdfs.security.token.block.TestBlockToken |
|   | hadoop.fs.contract.hdfs.TestHDFSContractAppend |
|   | hadoop.fs.contract.hdfs.TestHDFSContractDelete |
|   | hadoop.hdfs.web.TestWebHdfsTokens |
|   | hadoop.hdfs.TestErasureCodingPolicies |
|   | hadoop.hdfs.server.namenode.TestNNThroughputBenchmark |
|   | hadoop.hdfs.TestEncryptionZonesWithKMS |
|   | hadoop.hdfs.TestClientReportBadBlock |
|   | hadoop.hdfs.TestDFSStorageStateRecovery |
|   | hadoop.cli.TestHDFSCLI |
|   | hadoop.fs.TestSWebHdfsFileContextMainOperations |
|   | hadoop.hdfs.TestRestartDFS |
|   | hadoop.hdfs.TestFileAppend4 |
|   | hadoop.hdfs.web.TestWebHdfsUrl |
|   | hadoop.hdfs.TestSetTimes |
|   | hadoop.hdfs.server.namenode.ha.TestSeveralNameNodes |
|   | hadoop.hdfs.server.namenode.TestSecondaryWebUi |
|   | hadoop.fs.viewfs.TestViewFileSystemAtHdfsRoot |
|   | hadoop.fs.contract.hdfs.TestHDFSContractSeek |
|   | hadoop.hdfs.TestSetrepIncreasing |
|   | hadoop.fs.viewfs.TestViewFsWithAcls |
|   | hadoop.hdfs.TestLease |
|   | hadoop.hdfs.TestSafeMode |
|   | hadoop.hdfs.server.namenode.TestEditLogAutoroll |
|   | hadoop.hdfs.TestDFSUpgrade |
|   | hadoop.hdfs.TestDecommission |
|   | hadoop.hdfs.TestFileStatusWithECPolicy |
|   | hadoop.hdfs.protocol.datatransfer.sasl.TestSaslDataTransfer |
|   | hadoop.fs.TestHDFSFileContextMainOperations |
|   | hadoop.hdfs.TestFileCorruption |
|   | hadoop.hdfs.TestDatanodeStartupFixesLegacyStorageIDs |
|   | hadoop.hdfs.TestQuota |
|   | hadoop.hdfs.server.namenode.ha.TestHarFileSystemWithHA |
|   | hadoop.hdfs.TestFileStatus |
|   | hadoop.fs.TestResolveHdfsSymlink |
|   | hadoop.fs.TestSymlinkHdfsFileContext |
|   | hadoop.hdfs.TestEncryptionZonesWithHA |
|   | hadoop.hdfs.server.namenode.TestDeadDatanode |
|   | hadoop.hdfs.TestDFSStripedOutputStreamWithFailure000 |
|   | hadoop.cli.TestXAttrCLI |
|   | hadoop.fs.TestUrlStreamHandler |
|   | hadoop.hdfs.TestClose |
|   | hadoop.hdfs.TestMultiThreadedHflush |
|   | hadoop.hdfs.TestDFSClientExcludedNodes |
|   | hadoop.hdfs.TestFileConcurrentReader |
|   | hadoop.hdfs.TestClientBlockVerification |
|   | hadoop.security.TestPermissionSymlinks |
|   | hadoop.hdfs.server.namenode.ha.TestBootstrapStandby |
|   | hadoop.cli.TestAclCLI |
|   | hadoop.hdfs.TestDataTransferProtocol |
|   | hadoop.hdfs.TestBlockReaderFactory |
|   | hadoop.hdfs.server.namenode.TestNameNodeRespectsBindHostKeys |
|   | hadoop.hdfs.server.namenode.web.resources.TestWebHdfsDataLocality |
|   | hadoop.cli.TestCacheAdminCLI |
|   | hadoop.hdfs.TestDatanodeDeath |
|   | hadoop.hdfs.TestPipelines |
|   | hadoop.hdfs.web.TestWebHDFSAcl |
|   | hadoop.hdfs.tools.offlineImageViewer.TestOfflineImageViewerWithStripedBlocks |
|   | hadoop.hdfs.server.namenode.TestFSImage |
|   | hadoop.hdfs.web.TestWebHdfsWithMultipleNameNodes |
|   | hadoop.fs.TestUnbuffer |
|   | hadoop.hdfs.server.namenode.TestFsckWithMultipleNameNodes |
|   | hadoop.hdfs.server.namenode.ha.TestFailureOfSharedDir |
|   | hadoop.hdfs.TestRenameWhileOpen |
|   | hadoop.hdfs.web.TestHttpsFileSystem |
|   | hadoop.hdfs.server.namenode.ha.TestPendingCorruptDnMessages |
|   | hadoop.hdfs.TestWriteBlockGetsBlockLengthHint |
|   | hadoop.hdfs.tools.TestStoragePolicyCommands |
|   | hadoop.hdfs.server.namenode.TestNamenodeRetryCache |
|   | hadoop.hdfs.server.namenode.TestDecommissioningStatus |
|   | hadoop.hdfs.TestDFSStartupVersions |
|   | hadoop.hdfs.tools.offlineImageViewer.TestOfflineImageViewerForAcl |
|   | hadoop.hdfs.server.namenode.ha.TestHAStateTransitions |
|   | hadoop.hdfs.TestAppendSnapshotTruncate |
|   | hadoop.hdfs.TestParallelShortCircuitReadUnCached |
|   | hadoop.hdfs.TestDFSClientFailover |
|   | hadoop.hdfs.TestFSOutputSummer |
|   | hadoop.hdfs.server.namenode.TestHDFSConcat |
|   | hadoop.hdfs.server.namenode.ha.TestInitializeSharedEdits |
|   | hadoop.hdfs.web.TestFSMainOperationsWebHdfs |
|   | hadoop.hdfs.TestDFSInotifyEventInputStream |
|   | hadoop.hdfs.server.namenode.ha.TestRetryCacheWithHA |
|   | hadoop.hdfs.server.namenode.TestStartupOptionUpgrade |
|   | hadoop.hdfs.TestBalancerBandwidth |
|   | hadoop.hdfs.TestDFSPermission |
|   | hadoop.fs.viewfs.TestViewFileSystemHdfs |
|   | hadoop.hdfs.TestListFilesInDFS |
|   | hadoop.hdfs.TestModTime |
|   | hadoop.hdfs.TestReservedRawPaths |
|   | hadoop.hdfs.TestHDFSFileSystemContract |
|   | hadoop.fs.contract.hdfs.TestHDFSContractSetTimes |
|   | hadoop.hdfs.server.namenode.TestHostsFiles |
|   | hadoop.hdfs.TestFileCreation |
|   | hadoop.fs.viewfs.TestViewFsFileStatusHdfs |
|   | hadoop.hdfs.TestDFSShellGenericOptions |
|   | hadoop.hdfs.TestParallelShortCircuitRead |
|   | hadoop.hdfs.TestHDFSTrash |
|   | hadoop.hdfs.TestParallelShortCircuitLegacyRead |
|   | hadoop.hdfs.TestFileCreationEmpty |
|   | hadoop.hdfs.TestRead |
|   | hadoop.hdfs.TestFileAppend |
|   | hadoop.hdfs.web.TestWebHdfsFileSystemContract |
|   | hadoop.hdfs.server.namenode.TestSecureNameNode |
|   | hadoop.hdfs.TestDFSAddressConfig |
|   | hadoop.hdfs.web.TestWebHDFS |
|   | hadoop.hdfs.tools.offlineEditsViewer.TestOfflineEditsViewer |
|   | hadoop.hdfs.TestReplaceDatanodeOnFailure |
|   | hadoop.hdfs.server.namenode.TestAddBlock |
|   | hadoop.tools.TestJMXGet |
|   | hadoop.fs.TestFcHdfsCreateMkdir |
|   | hadoop.fs.TestFcHdfsPermission |
|   | hadoop.hdfs.server.namenode.ha.TestPipelinesFailover |
|   | hadoop.hdfs.TestFetchImage |
|   | hadoop.hdfs.TestInjectionForSimulatedStorage |
|   | hadoop.hdfs.server.namenode.TestNameNodeMetricsLogger |
|   | hadoop.hdfs.TestFileCreationClient |
|   | hadoop.hdfs.server.namenode.TestNameEditsConfigs |
|   | hadoop.hdfs.TestClientProtocolForPipelineRecovery |
|   | hadoop.hdfs.TestDFSRemove |
|   | hadoop.hdfs.TestFileAppendRestart |
|   | hadoop.fs.contract.hdfs.TestHDFSContractCreate |
|   | hadoop.net.TestNetworkTopology |
|   | hadoop.hdfs.TestDFSOutputStream |
|   | hadoop.hdfs.TestDisableConnCache |
|   | hadoop.hdfs.TestParallelShortCircuitReadNoChecksum |
|   | hadoop.hdfs.tools.TestGetGroups |
|   | hadoop.hdfs.server.namenode.ha.TestStandbyCheckpoints |
|   | hadoop.hdfs.tools.offlineImageViewer.TestOfflineImageViewer |
|   | hadoop.fs.TestEnhancedByteBufferAccess |
|   | hadoop.hdfs.TestBlockMissingException |
|   | hadoop.fs.permission.TestStickyBit |
| Timed out tests | org.apache.hadoop.hdfs.server.namenode.ha.TestHASafeMode |
\\
\\
|| Subsystem || Report/Notes ||
| Patch URL | http://issues.apache.org/jira/secure/attachment/12765801/HDFS-9053.006.patch |
| Optional Tests | javadoc javac unit findbugs checkstyle |
| git revision | trunk / 4aa9b3e |
| Release Audit | https://builds.apache.org/job/PreCommit-HDFS-Build/12892/artifact/patchprocess/patchReleaseAuditProblems.txt |
| checkstyle |  https://builds.apache.org/job/PreCommit-HDFS-Build/12892/artifact/patchprocess/diffcheckstylehadoop-common.txt |
| whitespace | https://builds.apache.org/job/PreCommit-HDFS-Build/12892/artifact/patchprocess/whitespace.txt |
| hadoop-common test log | https://builds.apache.org/job/PreCommit-HDFS-Build/12892/artifact/patchprocess/testrun_hadoop-common.txt |
| hadoop-hdfs test log | https://builds.apache.org/job/PreCommit-HDFS-Build/12892/artifact/patchprocess/testrun_hadoop-hdfs.txt |
| Test Results | https://builds.apache.org/job/PreCommit-HDFS-Build/12892/testReport/ |
| Java | 1.7.0_55 |
| uname | Linux asf907.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/12892/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
>
>
> 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)