I am currently pursuing the Ph.D. degree at HUST under the supervision of Prof. Jianxi Chen and Prof. Dan Feng.
I received the B.E. degree from the UESTC, Chengdu, in 2020. From 2020 to 2023, I was enrolled in the integrated Master-Ph.D. program at HUST, Wuhan, where I completed the requirements for the M.S. degree.
Persistent Memory (PM) offers both byte-address ability and non-volatility, making it well-suited for accelerating B+-Tree indexes. However, existing persistent B+-Tree indexes face significant performance challenges due to high structural modification operation (SMO) overhead. SMOs often result in costly item migrations and increased tail latency, which severely degrade the overall performance. In this paper, we present SSTree, a high-performance B+– Tree index specifically optimized to address SMO overhead. SSTree introduces three key innovations: (i) efficient leaf node expansion using a list of subnodes to postpone expensive node splits, (ii) delegated fingerprints to speed up search operations across subnodes, and (iii) proactive subnode compaction that employs out-of-place updates to optimize item organization. Our evaluation demonstrates that SSTree delivers up to 4.38× higher write throughput and up to 62× lower tail latency compared to state-of-the-art persistent B+-Tree indexes.
@inproceedings{Hong_2024,title={Optimizing Structural Modification Operation for B+-Tree on Byte-Addressable Devices},url={http://dx.doi.org/10.1109/iccd63220.2024.00043},doi={10.1109/iccd63220.2024.00043},booktitle={2024 IEEE 42nd International Conference on Computer Design (ICCD)},publisher={IEEE Computer Society},author={Hong, Dingze and Hu, Jinlei and Chen, Jianxi and Feng, Dan and Liu, Jian},year={2024},month=nov,pages={231--238},}
ICCD
RWORT: A Read and Write Optimized Radix Tree for Persistent Memory
Jinlei Hu, Wei Zijie, Chen Jianxi, and Dan Feng
In 2023 IEEE 41st International Conference on Computer Design (ICCD), Nov 2023
Tree index structures are widely employed in modern storage systems to support high-performance queries. Persistent memory (PM) brings a new opportunity and challenge for tree indexes. Among persistent tree indexes, we find the radix tree is more suitable than B-Tree for the byte-ability of PM. However, the hierarchy of radix remains excessively high, resulting in high read latency. Node splitting imposes a significant overhead on PM. To address these challenges, we propose RWORT, a read and write optimized radix tree for PM. The key focus of RWORT is to minimize random access in PM and provide efficient write operations. RWORT proposed a hierarchical compression mechanism to significantly reduce the tree height. Additionally, RWORT incorporates mini bloom filters to reduce unnecessary access on PM. For efficient write operations, RWORT uses the lazy split flag and the double-linked pointers to reduce the critical path delay. Furthermore, RWORT introduces a low-overhead ring-based bit tree allocator that improves allocation efficiency on PM. Our experiments show that RWORT improves up to 1.62x/4.91x respectively compared to the state-of-the-art radix tree/B-Tree. RWORT also exhibits higher performance in real-world storage systems such as Memcached.
@inproceedings{Hu_2023_RWORT,title={RWORT: A Read and Write Optimized Radix Tree for Persistent Memory},url={https://doi.ieeecomputersociety.org/10.1109/ICCD58817.2023.00038},doi={10.1109/ICCD58817.2023.00038},booktitle={2023 IEEE 41st International Conference on Computer Design (ICCD)},author={Hu, Jinlei and Zijie, Wei and Jianxi, Chen and Feng, Dan},year={2023},keywords={memory management;vegetation;delays;indexes;resource management;optimization},pages={194--197},publisher={IEEE Computer Society},address={Los Alamitos, CA, USA},month=nov,}
