Bwe-tree: An Evolution of Bw-tree on Fast Storage

Modern data-centric applications frequently need to store and read data with low latency. These requirements are difficult to achieve, even on high performance processors paired with fast solid state drives (SSDs). To this end, LSM tree is widely used in many systems such as in RocksDB and considered as an ideal index structure that fits SSDs. However, in spite of many improvements to LSM tree over the years, fundamental problems of limited read performance and expensive compaction operations remain. Microsoft Research proposed Bw-tree, a variant of B+ tree layered on top of log structured storage. Bw-tree achieves fast ingestion of data, similar to LSM tree, meanwhile it has less drawback on read performance and compaction. However, except for Microsoft, the industrial strength implementation of Bw-tree is rare. The open source OpenBw-Tree from Carnegie Mellon University was designed only for main memory. This paper describes Bw
^e
-tree, an implementation and a significant evolution of Bw-tree on fast storage. It makes two contributions. First, Bw
^e
-tree addresses reliability and performance issues revealed during running Bw-tree on fast storage in production, by revising structural modification operations, introducing page concurrency control, and storing large-size values off-tree. Performance improvements over Bw-tree are verified by experiments. Second, it demonstrates that Bw-tree is an effective alternative tree structure on SSDs. Compared to RocksDB (LSM tree) and BerkeleyDB (B+ tree), Bw
^e
-vtree performs dramatically better (up to 3X or more) for the YCSB workloads. Our Bw
^e
-vtree implementation has been integrated into production systems in Alibaba, including a flagshin cloud-native database service.