CCL-BTree: A Crash-Consistent Locality-Aware B+-Tree for Reducing XPBuffer-Induced Write Amplification in Persistent Memory.

In persistent B+ -Tree, random updates of small key-value (KV) pairs will cause severe XPBuffer-induced write amplification (XBI-amplification) because CPU cacheline size is smaller than media access granularity in persistent memory (PM). We observe that XBI-amplification directly determines the application performance when the PM bandwidth is exhausted in multi-thread scenarios. However, none of the existing work can efficiently address the XBI-amplification issue while maintaining superior range query performance. In this paper, we design a novel crash-consistent locality-aware B+-Tree (CCL-BTree). It preserves the key order between adjacent leaf nodes for efficient range query and proposes a leaf-node centric buffering strategy that merges writes and then flushes them together to reduce the number of flushes to the PM media. For crash-consistency, all the buffered KVs are recorded in write-ahead logs. CCL-BTree further devises write-conservative logging to skip unnecessary log operations, and locality-aware garbage collection to avoid random PM writes in reclaiming log data. Our experiments show that CCL-BTree reduces the XBI-amplification by up to 81%, improves the insert throughput by up to 9.35×, and achieves good range query performance compared to state-of-the-art persistent B+-Trees.

Recommended citation: Zhenxin Li, Shuibing He, Zheng Dang, Peiyi Hong, Xuechen Zhang, Rui Wang, and Fei Wu. CCL-BTree: A Crash-Consistent Locality-Aware B+-Tree for Reducing XPBuffer-Induced Write Amplification in Persistent Memory. In Proceedings of the Nineteenth European Conference on Computer Systems (EuroSys 2024). Association for Computing Machinery, New York, NY, USA, 441–455. https://dl.acm.org/doi/abs/10.1145/3627703.3629582