xorsum created HDFS-17871:
-----------------------------
Summary: 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
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]
