[
https://issues.apache.org/jira/browse/HDFS-17871?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18051260#comment-18051260
]
ASF GitHub Bot commented on HDFS-17871:
---------------------------------------
hadoop-yetus commented on PR #8179:
URL: https://github.com/apache/hadoop/pull/8179#issuecomment-3738997137
:broken_heart: **-1 overall**
| Vote | Subsystem | Runtime | Logfile | Comment |
|:----:|----------:|--------:|:--------:|:-------:|
| +0 :ok: | reexec | 1m 5s | | Docker mode activated. |
|||| _ Prechecks _ |
| +1 :green_heart: | dupname | 0m 0s | | No case conflicting files
found. |
| +0 :ok: | codespell | 0m 0s | | codespell was not available. |
| +0 :ok: | detsecrets | 0m 0s | | detect-secrets was not available.
|
| +1 :green_heart: | @author | 0m 0s | | The patch does not contain
any @author tags. |
| -1 :x: | test4tests | 0m 0s | | 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.
|
|||| _ trunk Compile Tests _ |
| +1 :green_heart: | mvninstall | 34m 4s | | trunk passed |
| +1 :green_heart: | compile | 0m 48s | | trunk passed with JDK
Ubuntu-21.0.7+6-Ubuntu-0ubuntu120.04 |
| +1 :green_heart: | compile | 1m 12s | | trunk passed with JDK
Ubuntu-17.0.15+6-Ubuntu-0ubuntu120.04 |
| +1 :green_heart: | checkstyle | 0m 34s | | trunk passed |
| +1 :green_heart: | mvnsite | 1m 16s | | trunk passed |
| +1 :green_heart: | javadoc | 0m 47s | | trunk passed with JDK
Ubuntu-21.0.7+6-Ubuntu-0ubuntu120.04 |
| +1 :green_heart: | javadoc | 0m 41s | | trunk passed with JDK
Ubuntu-17.0.15+6-Ubuntu-0ubuntu120.04 |
| +1 :green_heart: | spotbugs | 2m 6s | | trunk passed |
| +1 :green_heart: | shadedclient | 27m 14s | | branch has no errors
when building and testing our client artifacts. |
|||| _ Patch Compile Tests _ |
| +1 :green_heart: | mvninstall | 1m 1s | | the patch passed |
| +1 :green_heart: | compile | 0m 39s | | the patch passed with JDK
Ubuntu-21.0.7+6-Ubuntu-0ubuntu120.04 |
| +1 :green_heart: | javac | 0m 39s | | the patch passed |
| +1 :green_heart: | compile | 0m 59s | | the patch passed with JDK
Ubuntu-17.0.15+6-Ubuntu-0ubuntu120.04 |
| +1 :green_heart: | javac | 0m 59s | | the patch passed |
| +1 :green_heart: | blanks | 0m 0s | | The patch has no blanks
issues. |
| +1 :green_heart: | checkstyle | 0m 23s | | the patch passed |
| +1 :green_heart: | mvnsite | 1m 7s | | the patch passed |
| +1 :green_heart: | javadoc | 0m 33s | | the patch passed with JDK
Ubuntu-21.0.7+6-Ubuntu-0ubuntu120.04 |
| +1 :green_heart: | javadoc | 0m 33s | | the patch passed with JDK
Ubuntu-17.0.15+6-Ubuntu-0ubuntu120.04 |
| +1 :green_heart: | spotbugs | 2m 2s | | the patch passed |
| +1 :green_heart: | shadedclient | 27m 8s | | patch has no errors
when building and testing our client artifacts. |
|||| _ Other Tests _ |
| +1 :green_heart: | unit | 43m 44s | | hadoop-hdfs-rbf in the patch
passed. |
| +1 :green_heart: | asflicense | 0m 34s | | The patch does not
generate ASF License warnings. |
| | | 150m 13s | | |
| Subsystem | Report/Notes |
|----------:|:-------------|
| Docker | ClientAPI=1.52 ServerAPI=1.52 base:
https://ci-hadoop.apache.org/job/hadoop-multibranch/job/PR-8179/2/artifact/out/Dockerfile
|
| GITHUB PR | https://github.com/apache/hadoop/pull/8179 |
| Optional Tests | dupname asflicense compile javac javadoc mvninstall
mvnsite unit shadedclient spotbugs checkstyle codespell detsecrets |
| uname | Linux caf8c1016fdb 5.15.0-164-generic #174-Ubuntu SMP Fri Nov 14
20:25:16 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux |
| Build tool | maven |
| Personality | dev-support/bin/hadoop.sh |
| git revision | trunk / 9426d7553fe2fcfb1214bb01b56817d128e2e106 |
| Default Java | Ubuntu-17.0.15+6-Ubuntu-0ubuntu120.04 |
| Multi-JDK versions |
/usr/lib/jvm/java-21-openjdk-amd64:Ubuntu-21.0.7+6-Ubuntu-0ubuntu120.04
/usr/lib/jvm/java-17-openjdk-amd64:Ubuntu-17.0.15+6-Ubuntu-0ubuntu120.04 |
| Test Results |
https://ci-hadoop.apache.org/job/hadoop-multibranch/job/PR-8179/2/testReport/ |
| Max. process+thread count | 3735 (vs. ulimit of 5500) |
| modules | C: hadoop-hdfs-project/hadoop-hdfs-rbf U:
hadoop-hdfs-project/hadoop-hdfs-rbf |
| Console output |
https://ci-hadoop.apache.org/job/hadoop-multibranch/job/PR-8179/2/console |
| versions | git=2.25.1 maven=3.9.11 spotbugs=4.9.7 |
| Powered by | Apache Yetus 0.14.0 https://yetus.apache.org |
This message was automatically generated.
> Performance Issue: `findDeepest()` in RBF traverses entire tree when parent
> path doesn't exist
> ----------------------------------------------------------------------------------------------
>
> Key: HDFS-17871
> URL: https://issues.apache.org/jira/browse/HDFS-17871
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: rbf
> Reporter: xorsum
> Priority: Minor
> Labels: pull-request-available
> Attachments: BenchmarkFindDeepest.java
>
>
> h2. Problem
> The current implementation of
> `org.apache.hadoop.hdfs.server.federation.resolver.MountTableResolver#findDeepest`
> method in RBF has a performance issue: when the tree doesn't contain a
> parent path for the queried path, the `while` loop iterates through *all
> entries* in the TreeMap, resulting in `O(N)` time complexity instead of the
> expected `O(log N)`.
> h2. Example
> Consider a mount table containing:
> - `/user/hive/warehouse/db1.db/table1`
> - `/user/hive/warehouse/db1.db/table2`
> - `/user/hive/warehouse/db2.db/table3`
> When querying a path like `/xyz/random/path/file.txt`, the algorithm will:
> - `floorEntry("/xyz/random/path/file.txt")` returns the largest entry in the
> tree
> - Check `isParentEntry()`: false
> - Call `lowerEntry()` repeatedly until reaching the first entry in the tree
> - Worst case: Iterates through ALL entries in `O(N)` time
> h2. Proposed Solution
> We can improve the `findDeepest` method by checking the parent path directly,
> instead of using `floorEntry`.
> I benchmarked the performance of these two implementations.
> The benchmark results show that the improved method is 50x faster than the
> original method.
> {quote}================================================================================
> BENCHMARK COMPARISON RESULTS
> ================================================================================
> 【Original Method - findDeepest】
> Total Execution Time: 1,924,288,819 ns (1924.29 ms)
> Total Lookup Count: 15,302,856
> Avg Time Per Query: 320,607.93 ns (0.32 ms)
> Avg Lookups Per Query: 2,549.63
> 【Improved Method - findDeepestImproved】
> Total Execution Time: 38,030,989 ns (38.03 ms)
> Total Lookup Count: 24,008
> Avg Time Per Query: 6,336.39 ns (0.01 ms)
> Avg Lookups Per Query: 4.00
> 【Performance Improvement】
> Time Saved: 98.02%
> Lookup Count Reduced: 99.84%
> Speedup Factor: 50.60x
> 【Correctness Verification】
> ✓ All results match! Both methods returned identical results.
> ================================================================================
> {quote}
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
