Breathing New Life into An Old Tree: Resolving Logging Dilemma of $B^{+}$-tree on Modern Computational Storage Drives

Download PDF

Abstract

Having dominated databases and various data management systems for decades, 𝐵+-tree is infamously subject to a logging dilemma: One could improve 𝐵+-tree speed performance by equipping it with a larger log, which nevertheless will degrade its crash recovery speed. Such a logging dilemma is particularly prominent in the presence of modern workloads that involve intensive small writes. In this paper, we propose a novel solution, called per-page logging based 𝐵+-tree, which leverages the emerging computational storage drive (CSD) with built-in transparent compression to fundamentally resolve the logging dilemma. Our key idea is to divide the large single log into many small (e.g., 4KB), highly compressible per-page logs, each being statically bounded with a 𝐵+-tree page. All per-page logs together form a very large over-provisioned log space for 𝐵+-tree to improve its operational speed performance. Meanwhile, during crash recovery, 𝐵+-tree does not need to scan any per-page logs, leading to a recovery latency independent from the total log size. We have developed and open-sourced a fully functional prototype. Our evaluation results show that, under small-write intensive workloads, our design solution can improve 𝐵+-tree operational throughput by up to 625.6% and maintain a crash recovery time of as low as 19.2 ms, while incurring a minimal storage overhead of only 0.5-1.6%.