Multiversion Concurrency Control for Multiversion B-Trees
This work addresses the need for efficient concurrency control in multiversion B-trees, providing a practical solution for database systems requiring optimal range scan performance with minimal conflicts.
The authors present cMVBT, a concurrent multiversion B-tree that eliminates latching for range scans and uses optimistic latches for writes, achieving high write throughput and excellent range scan performance, outperforming version-chain-based methods in mixed workloads.
Multiversion concurrency control (MVCC) enables scans to read data from a committed snapshot (version), reducing conflicts with write operations compared to traditional concurrency approaches. Currently, versioned records are often managed in a B$^+$-tree using version chains. However, version chains introduce overhead during scans and can still lead to conflicts between scans and writers. The multiversion B-tree (MVBT) was designed for optimal range scan performance on arbitrary versions, but has been considered impractical due to its structural complexity and, until recently, the lack of effective concurrency control. In this paper, we present the concurrent MVBT (cMVBT), a redesign of the MVBT featuring a novel concurrency control protocol that uses optimistic latches for write operations and requires no latches for range scans, while preserving all the optimality guarantees of the original MVBT. Additionally, cMVBT supports continuous garbage collection without activity spikes, seamlessly integrating free-space management. Experiments with mixed workloads derived from a standard benchmark show that the cMVBT achieves low overhead, high write throughput, and excellent range scan performance, outperforming state-of-the-art methods based on version chains.