[
https://issues.apache.org/jira/browse/HDFS-17871?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18051429#comment-18051429
]
ASF GitHub Bot commented on HDFS-17871:
---------------------------------------
XorSum commented on PR #8179:
URL: https://github.com/apache/hadoop/pull/8179#issuecomment-3742113718
> Hi @XorSum I think it should hit in most cases. In cases where it does
hit, have there been tests to assess the performance difference?
Thanks for the review!
In our cluster, only a minority of paths are mounted, while the majority of
paths are unmounted.
Unfortunately, the original method is extremely slow when it fails to find a
mount point, as it traverses the entire tree.
This has become a performance bottleneck, making it critical for us to
optimize the unmounted path query performance.
This program is able to benchmark the performance difference:
https://gist.github.com/XorSum/823641e4b599bfc5c242cdb7b018f044#file-benchmarkfinddeepest-java
To test the case that **all queries hit**, we can delete the code in Line
103~109.
The results shows that, the improved method does not slow down the
performance.
This is because the `tree.floorEntry(path)` is able to find the hit entry
quickly.
```
================================================================================
BENCHMARK COMPARISON RESULTS
================================================================================
【Original Method - findDeepest】
Total Execution Time: 2,546,286 ns (2.55 ms)
Total Lookup Count: 3,001
Avg Time Per Query: 848.48 ns (0.00 ms)
Avg Lookups Per Query: 1.00
【Improved Method - findDeepestImproved】
Total Execution Time: 1,486,916 ns (1.49 ms)
Total Lookup Count: 3,001
Avg Time Per Query: 495.47 ns (0.00 ms)
Avg Lookups Per Query: 1.00
【Performance Improvement】
Time Saved: 41.60%
Lookup Count Reduced: 0.00%
Speedup Factor: 1.71x
【Correctness Verification】
✓ All results match! Both methods returned identical results.
```
To test the case that **all queries NOT hit**, we can delete the code in
Line 96~100.
The results shows that, the improved method significantly speed up the
performance.
```
================================================================================
BENCHMARK COMPARISON RESULTS
================================================================================
【Original Method - findDeepest】
Total Execution Time: 1,981,994,707 ns (1981.99 ms)
Total Lookup Count: 16,107,249
Avg Time Per Query: 660,444.75 ns (0.66 ms)
Avg Lookups Per Query: 5,367.29
【Improved Method - findDeepestImproved】
Total Execution Time: 33,253,666 ns (33.25 ms)
Total Lookup Count: 24,008
Avg Time Per Query: 11,080.86 ns (0.01 ms)
Avg Lookups Per Query: 8.00
【Performance Improvement】
Time Saved: 98.32%
Lookup Count Reduced: 99.85%
Speedup Factor: 59.60x
【Correctness Verification】
✓ All results match! Both methods returned identical results.
```
Let me know if you'd like me to provide additional benchmark results.
> 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]
