[jira] [Commented] (HDFS-15140) Replace FoldedTreeSet in Datanode with SortedSet or TreeMap
[
https://issues.apache.org/jira/browse/HDFS-15140?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17083996#comment-17083996
]
HuangTao commented on HDFS-15140:
-
about the patch, I find two points need to change
{code}
ReplicaInfo orig = b.getOriginalReplica();
- builders.get(volStorageID).add(orig);
+ unsortedBlocks.get(volStorageID).add(b); # replace b with orig
{code}
{code}
+unsortedBlocks.put(
+v.getStorageID(), new ArrayList(131072)); # should
use a constant variable
{code}
> Replace FoldedTreeSet in Datanode with SortedSet or TreeMap
> ---
>
> Key: HDFS-15140
> URL: https://issues.apache.org/jira/browse/HDFS-15140
> Project: Hadoop HDFS
> Issue Type: Bug
> Components: datanode
>Affects Versions: 3.3.0
>Reporter: Stephen O'Donnell
>Assignee: Stephen O'Donnell
>Priority: Major
> Attachments: HDFS-15140.001.patch, HDFS-15140.002.patch
>
>
> Based on the problems discussed in HDFS-15131, I would like to explore
> replacing the FoldedTreeSet structure in the datanode with a builtin Java
> equivalent - either SortedSet or TreeMap.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: hdfs-issues-unsubscr...@hadoop.apache.org
For additional commands, e-mail: hdfs-issues-h...@hadoop.apache.org
[jira] [Commented] (HDFS-15140) Replace FoldedTreeSet in Datanode with SortedSet or TreeMap
[ https://issues.apache.org/jira/browse/HDFS-15140?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17026925#comment-17026925 ] Stephen O'Donnell commented on HDFS-15140: -- All failing tests pass locally so I think they are unrelated. I am also open to simply switching FoldedTreeSet with TreeMap, and then we can avoid the need to sort the block reports. The cost of TreeMap would be about 33MB of extra heap per 1M blocks, but the access time is similar to FoldedTreeSet, so we would not gain performance with this change. The hope is that we would avoid the degradation which occurs in foldedTreeSet for an unknown reason after some time. Discussing this offline, someone asked me whether this would impact IBRs. I don't believe this will impact IBRs in any way. The reason, is that the IBR related blocks are added to the IncrementalBlockReportManager where they are stored in an unrelated structure and then transmitted to the namenode via the heartbeat thread (but not as part of the heartbeat). > Replace FoldedTreeSet in Datanode with SortedSet or TreeMap > --- > > Key: HDFS-15140 > URL: https://issues.apache.org/jira/browse/HDFS-15140 > Project: Hadoop HDFS > Issue Type: Bug > Components: datanode >Affects Versions: 3.3.0 >Reporter: Stephen O'Donnell >Assignee: Stephen O'Donnell >Priority: Major > Attachments: HDFS-15140.001.patch, HDFS-15140.002.patch > > > Based on the problems discussed in HDFS-15131, I would like to explore > replacing the FoldedTreeSet structure in the datanode with a builtin Java > equivalent - either SortedSet or TreeMap. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: hdfs-issues-unsubscr...@hadoop.apache.org For additional commands, e-mail: hdfs-issues-h...@hadoop.apache.org
[jira] [Commented] (HDFS-15140) Replace FoldedTreeSet in Datanode with SortedSet or TreeMap
[
https://issues.apache.org/jira/browse/HDFS-15140?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17026099#comment-17026099
]
Hadoop QA commented on HDFS-15140:
--
| (x) *{color:red}-1 overall{color}* |
\\
\\
|| Vote || Subsystem || Runtime || Comment ||
| {color:blue}0{color} | {color:blue} reexec {color} | {color:blue} 0m
46s{color} | {color:blue} Docker mode activated. {color} |
|| || || || {color:brown} Prechecks {color} ||
| {color:green}+1{color} | {color:green} @author {color} | {color:green} 0m
0s{color} | {color:green} The patch does not contain any @author tags. {color} |
| {color:red}-1{color} | {color:red} test4tests {color} | {color:red} 0m
0s{color} | {color:red} The patch doesn't appear to include any new or modified
tests. Please justify why no new tests are needed for this patch. Also please
list what manual steps were performed to verify this patch. {color} |
|| || || || {color:brown} trunk Compile Tests {color} ||
| {color:green}+1{color} | {color:green} mvninstall {color} | {color:green} 19m
29s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} compile {color} | {color:green} 1m
6s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} checkstyle {color} | {color:green} 0m
50s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} mvnsite {color} | {color:green} 1m
14s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} shadedclient {color} | {color:green}
15m 15s{color} | {color:green} branch has no errors when building and testing
our client artifacts. {color} |
| {color:green}+1{color} | {color:green} findbugs {color} | {color:green} 2m
27s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} javadoc {color} | {color:green} 1m
12s{color} | {color:green} trunk passed {color} |
|| || || || {color:brown} Patch Compile Tests {color} ||
| {color:green}+1{color} | {color:green} mvninstall {color} | {color:green} 1m
8s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} compile {color} | {color:green} 1m
2s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} javac {color} | {color:green} 1m
2s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} checkstyle {color} | {color:green} 0m
41s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} mvnsite {color} | {color:green} 1m
9s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} whitespace {color} | {color:green} 0m
0s{color} | {color:green} The patch has no whitespace issues. {color} |
| {color:green}+1{color} | {color:green} shadedclient {color} | {color:green}
14m 11s{color} | {color:green} patch has no errors when building and testing
our client artifacts. {color} |
| {color:green}+1{color} | {color:green} findbugs {color} | {color:green} 2m
35s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} javadoc {color} | {color:green} 1m
15s{color} | {color:green} the patch passed {color} |
|| || || || {color:brown} Other Tests {color} ||
| {color:red}-1{color} | {color:red} unit {color} | {color:red}120m 26s{color}
| {color:red} hadoop-hdfs in the patch failed. {color} |
| {color:green}+1{color} | {color:green} asflicense {color} | {color:green} 0m
31s{color} | {color:green} The patch does not generate ASF License warnings.
{color} |
| {color:black}{color} | {color:black} {color} | {color:black}185m 4s{color} |
{color:black} {color} |
\\
\\
|| Reason || Tests ||
| Failed junit tests | hadoop.hdfs.TestDFSClientRetries |
| | hadoop.hdfs.server.datanode.TestDataNodeLifeline |
| | hadoop.hdfs.server.namenode.ha.TestDelegationTokensWithHA |
| | hadoop.hdfs.server.namenode.ha.TestHAAppend |
\\
\\
|| Subsystem || Report/Notes ||
| Docker | Client=19.03.5 Server=19.03.5 Image:yetus/hadoop:c44943d1fc3 |
| JIRA Issue | HDFS-15140 |
| JIRA Patch URL |
https://issues.apache.org/jira/secure/attachment/12992138/HDFS-15140.002.patch |
| Optional Tests | dupname asflicense compile javac javadoc mvninstall
mvnsite unit shadedclient findbugs checkstyle |
| uname | Linux 3ddfe47bc316 4.15.0-74-generic #84-Ubuntu SMP Thu Dec 19
08:06:28 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux |
| Build tool | maven |
| Personality | /testptch/patchprocess/precommit/personality/provided.sh |
| git revision | trunk / 7f3e1e0 |
| maven | version: Apache Maven 3.3.9 |
| Default Java | 1.8.0_232 |
| findbugs | v3.1.0-RC1 |
| unit |
https://builds.apache.org/job/PreCommit-HDFS-Build/28720/artifact/out/patch-unit-hadoop-hdfs-project_hadoop-hdfs.txt
|
| Test Results |
https://builds.apache.org/job/PreCommit-HDFS-Build/28720/testReport/ |
| Max.
[jira] [Commented] (HDFS-15140) Replace FoldedTreeSet in Datanode with SortedSet or TreeMap
[ https://issues.apache.org/jira/browse/HDFS-15140?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17025964#comment-17025964 ] Stephen O'Donnell commented on HDFS-15140: -- Test failures seem to be related to "unable to create native thread". Fixed the style issues and pushed a new version to see if the tests come back better. > Replace FoldedTreeSet in Datanode with SortedSet or TreeMap > --- > > Key: HDFS-15140 > URL: https://issues.apache.org/jira/browse/HDFS-15140 > Project: Hadoop HDFS > Issue Type: Bug > Components: datanode >Affects Versions: 3.3.0 >Reporter: Stephen O'Donnell >Assignee: Stephen O'Donnell >Priority: Major > Attachments: HDFS-15140.001.patch, HDFS-15140.002.patch > > > Based on the problems discussed in HDFS-15131, I would like to explore > replacing the FoldedTreeSet structure in the datanode with a builtin Java > equivalent - either SortedSet or TreeMap. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: hdfs-issues-unsubscr...@hadoop.apache.org For additional commands, e-mail: hdfs-issues-h...@hadoop.apache.org
[jira] [Commented] (HDFS-15140) Replace FoldedTreeSet in Datanode with SortedSet or TreeMap
[
https://issues.apache.org/jira/browse/HDFS-15140?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17025943#comment-17025943
]
Hadoop QA commented on HDFS-15140:
--
| (x) *{color:red}-1 overall{color}* |
\\
\\
|| Vote || Subsystem || Runtime || Comment ||
| {color:blue}0{color} | {color:blue} reexec {color} | {color:blue} 1m
5s{color} | {color:blue} Docker mode activated. {color} |
|| || || || {color:brown} Prechecks {color} ||
| {color:green}+1{color} | {color:green} @author {color} | {color:green} 0m
0s{color} | {color:green} The patch does not contain any @author tags. {color} |
| {color:red}-1{color} | {color:red} test4tests {color} | {color:red} 0m
0s{color} | {color:red} The patch doesn't appear to include any new or modified
tests. Please justify why no new tests are needed for this patch. Also please
list what manual steps were performed to verify this patch. {color} |
|| || || || {color:brown} trunk Compile Tests {color} ||
| {color:green}+1{color} | {color:green} mvninstall {color} | {color:green} 26m
24s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} compile {color} | {color:green} 1m
16s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} checkstyle {color} | {color:green} 0m
51s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} mvnsite {color} | {color:green} 1m
19s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} shadedclient {color} | {color:green}
17m 40s{color} | {color:green} branch has no errors when building and testing
our client artifacts. {color} |
| {color:green}+1{color} | {color:green} findbugs {color} | {color:green} 2m
58s{color} | {color:green} trunk passed {color} |
| {color:green}+1{color} | {color:green} javadoc {color} | {color:green} 1m
41s{color} | {color:green} trunk passed {color} |
|| || || || {color:brown} Patch Compile Tests {color} ||
| {color:green}+1{color} | {color:green} mvninstall {color} | {color:green} 1m
31s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} compile {color} | {color:green} 1m
24s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} javac {color} | {color:green} 1m
24s{color} | {color:green} the patch passed {color} |
| {color:orange}-0{color} | {color:orange} checkstyle {color} | {color:orange}
0m 47s{color} | {color:orange} hadoop-hdfs-project/hadoop-hdfs: The patch
generated 2 new + 88 unchanged - 0 fixed = 90 total (was 88) {color} |
| {color:green}+1{color} | {color:green} mvnsite {color} | {color:green} 1m
23s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} whitespace {color} | {color:green} 0m
0s{color} | {color:green} The patch has no whitespace issues. {color} |
| {color:green}+1{color} | {color:green} shadedclient {color} | {color:green}
15m 32s{color} | {color:green} patch has no errors when building and testing
our client artifacts. {color} |
| {color:green}+1{color} | {color:green} findbugs {color} | {color:green} 3m
1s{color} | {color:green} the patch passed {color} |
| {color:green}+1{color} | {color:green} javadoc {color} | {color:green} 1m
31s{color} | {color:green} the patch passed {color} |
|| || || || {color:brown} Other Tests {color} ||
| {color:red}-1{color} | {color:red} unit {color} | {color:red}136m 56s{color}
| {color:red} hadoop-hdfs in the patch failed. {color} |
| {color:green}+1{color} | {color:green} asflicense {color} | {color:green} 0m
34s{color} | {color:green} The patch does not generate ASF License warnings.
{color} |
| {color:black}{color} | {color:black} {color} | {color:black}215m 55s{color} |
{color:black} {color} |
\\
\\
|| Reason || Tests ||
| Failed junit tests |
hadoop.hdfs.server.namenode.web.resources.TestWebHdfsCreatePermissions |
| | hadoop.hdfs.server.datanode.TestDataNodeReconfiguration |
| | hadoop.hdfs.TestDeadNodeDetection |
| | hadoop.hdfs.server.blockmanagement.TestBlockStatsMXBean |
| |
hadoop.hdfs.server.blockmanagement.TestReconstructStripedBlocksWithRackAwareness
|
| | hadoop.hdfs.server.datanode.TestDataNodeVolumeMetrics |
| | hadoop.hdfs.server.blockmanagement.TestPendingInvalidateBlock |
| | hadoop.hdfs.server.mover.TestMover |
| | hadoop.hdfs.server.mover.TestStorageMover |
| | hadoop.hdfs.server.namenode.TestNamenodeCapacityReport |
| | hadoop.hdfs.server.namenode.TestCheckPointForSecurityTokens |
| | hadoop.hdfs.TestMultipleNNPortQOP |
| | hadoop.hdfs.server.datanode.TestDataNodeVolumeFailureToleration |
| | hadoop.hdfs.server.namenode.web.resources.TestWebHdfsDataLocality |
| | hadoop.hdfs.server.namenode.TestStartup |
| | hadoop.hdfs.server.namenode.ha.TestDelegationTokensWithHA |
| | hadoop.hdfs.server.namenode.TestCacheDirectives |
| |
[jira] [Commented] (HDFS-15140) Replace FoldedTreeSet in Datanode with SortedSet or TreeMap
[ https://issues.apache.org/jira/browse/HDFS-15140?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17025824#comment-17025824 ] Stephen O'Donnell commented on HDFS-15140: -- After thinking about this for some time, I reckon it makes sense to remove the sorted structure in the datanode volume map, and replace it with an unsorted version, for the following reasons: 1. Gets, adds and removes are significantly slower in both FoldedTreeSet and TreeMap when compared with HashMap and GSet. We only create a block report once per 6 hours or so, so it does not make sense to pay the sorted structure overhead for all accesses, just to provided sorted block reports. 2. There is already contention around the DN lock, so it makes sense to make this structure as fast as possible, as it must always be accessed under a lock. 3. A DN with a sensible number of blocks (< 5M) can have the block report sorted outside of the lock in about 1.5 seconds. As the blocks are organised per storage for the block report, any given sort will be less than the total blocks. Eg, a DN with 20M blocks (way to many) and 20 volumes, will only do have to sort 1M blocks at a time. We can even sort each volume is parallel if we thread it and find this sorting overhead makes the block report take too long. 3. The sort can be performed outside of the DN lock, so if it takes a little time it is not big deal. After looking at HashMap and the structure which was originally used in the DN, GSet, I found the performance of GSet to be much better than foldedTreeSet for all operations, and it has a comparable memory footprint to foldedTreeSet. HashMap on the other hand has a 60 byte per entry overhead in my tests, so for a larger DN, it would have a notable impact on the Heap usage. I have submitted a patch with this change, but it may need a new test to consider the reports are actually sorted as expected. > Replace FoldedTreeSet in Datanode with SortedSet or TreeMap > --- > > Key: HDFS-15140 > URL: https://issues.apache.org/jira/browse/HDFS-15140 > Project: Hadoop HDFS > Issue Type: Bug > Components: datanode >Affects Versions: 3.3.0 >Reporter: Stephen O'Donnell >Assignee: Stephen O'Donnell >Priority: Major > Attachments: HDFS-15140.001.patch > > > Based on the problems discussed in HDFS-15131, I would like to explore > replacing the FoldedTreeSet structure in the datanode with a builtin Java > equivalent - either SortedSet or TreeMap. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: hdfs-issues-unsubscr...@hadoop.apache.org For additional commands, e-mail: hdfs-issues-h...@hadoop.apache.org
[jira] [Commented] (HDFS-15140) Replace FoldedTreeSet in Datanode with SortedSet or TreeMap
[
https://issues.apache.org/jira/browse/HDFS-15140?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17023077#comment-17023077
]
Stephen O'Donnell commented on HDFS-15140:
--
One problem I have with this change, is that I have no idea why the
FoldedTreeSet structure degrades so badly after some period of time. It would
be great to figure out what that is and fix it.
The datanode originally used a ResizableGSet for the block map, which is
unsorted. However, along with the introduction of FoldedTreeSet, we introduced
sorted block reports and the namenode now relies upon them being sorted.
Therefore, there are (at least) two choices here:
1. Replace FoldedTreeSet with another sorted structure. Eg TreeMap would work.
2. Switch back to the GSet in the datanode, and then sort the blocks each time
we create a block report.
In benchmarks I ran, TreeMap seems to perform marginally better than
FoldedTreeMap on adds and deletes. For gets, for sets under 8M entries,
FoldedTreeSet is marginally faster and then for larger sets TreeMap is faster.
The performance gap seems to widen as the sets get bigger in TreeMap's favour.
However, a major plus point to FoldedTreeSet, is its reduce memory overhead.
Loading each structure with 1M entries and capturing a heap dump, we can see
TreeMap has an overhead of about 40 bytes per entry, as each object is stored
into a TreeMap$Entry:
{code}
num #instances #bytes class name
--
1: 100 4000 java.util.TreeMap$Entry
2: 1000129 24003096 java.lang.Long
3: 100 2400 com.sodonnell.BlockMock
{code}
FoldedTreeSet however, has an overhead of about 5 bytes per entry due to
storing up to 64 objects in each tree node:
{code}
num #instances #bytes class name
--
1: 100 2400 com.sodonnell.BlockMock
2: 159414263344 [Ljava.lang.Object;
3: 15625 875000 com.sodonnell.FoldedTreeSet$Node
{code}
Therefore switching to TreeMap would cost about (40 - 5) * 1M blocks = 33.37MB
of additional heap per 1M blocks and give comparable get, delete and add
performance.
For option (2), we could capture the list of blocks for a block report, then
drop the DN lock and sort them. Block Reports are sent per volume, so sorting
volume by volume would be doable.
Benchmarking a sort on an array of objects, where the compare is performed
against a long gives:
{code}
Time taken to sort 50 elements: 338
Time taken to sort 100 elements: 337
Time taken to sort 200 elements: 632
Time taken to sort 400 elements: 1438
Time taken to sort 800 elements: 3244
Time taken to sort 1600 elements: 7260
{code}
The extra sort would require materializing another list of references to the
objects, but even for 20M blocks (a lot for a DN) at 4 bytes per reference this
is only about 76MB which would be quickly GC'ed afterwards.
> Replace FoldedTreeSet in Datanode with SortedSet or TreeMap
> ---
>
> Key: HDFS-15140
> URL: https://issues.apache.org/jira/browse/HDFS-15140
> Project: Hadoop HDFS
> Issue Type: Bug
> Components: datanode
>Affects Versions: 3.3.0
>Reporter: Stephen O'Donnell
>Assignee: Stephen O'Donnell
>Priority: Major
>
> Based on the problems discussed in HDFS-15131, I would like to explore
> replacing the FoldedTreeSet structure in the datanode with a builtin Java
> equivalent - either SortedSet or TreeMap.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: hdfs-issues-unsubscr...@hadoop.apache.org
For additional commands, e-mail: hdfs-issues-h...@hadoop.apache.org
