Building a BW-tree takes more than just BuzzWords
Wang Z, Pavlo A, Lim H, Leis V, Zhang H, Kaminsky M, Andersen DG (2018)
Publication Type: Conference contribution
Publication year: 2018
Publisher: Association for Computing Machinery
Pages Range: 473-488
Conference Proceedings Title: Proceedings of the ACM SIGMOD International Conference on Management of Data
Event location: Houston, TX
ISBN: 9781450317436
Abstract
In 2013, Microsoft Research proposed the Bw-Tree (humorously termed the "Buzz Word Tree"), a lock-free index that provides high throughput for transactional database workloads in SQL Server's Hekaton engine. The Bw-Tree avoids locks by appending delta record to tree nodes and using an indirection layer that allows it to atomically update physical pointers using compare-and-swap (CaS). Correctly implementing this techniques requires careful attention to detail. Unfortunately, the Bw-Tree papers from Microsoft are missing important details and the source code has not been released. This paper has two contributions: First, it is the missing guide for how to build a lock-free Bw-Tree. We clarify missing points in Microsoft's original design documents and then present techniques to improve the index's performance. Although our focus here is on the Bw-Tree, many of our methods apply more broadly to designing and implementing future lock-free in-memory data structures. Our experimental evaluation shows that our optimized variant achieves 1.1-2.5× better performance than the original Microsoft proposal for highly concurrent workloads. Second, our evaluation shows that despite our improvements, the Bw-Tree still does not perform as well as other concurrent data structures that use locks.
Authors with CRIS profile
Involved external institutions
Carnegie Mellon University
United States (USA) (US)
Intel Corporation
United States (USA) (US)
Technische Universität München (TUM)
Germany (DE)
United States (USA) (US)
Intel Corporation
United States (USA) (US)
Technische Universität München (TUM)
Germany (DE)
How to cite
APA:
Wang, Z., Pavlo, A., Lim, H., Leis, V., Zhang, H., Kaminsky, M., & Andersen, D.G. (2018). Building a BW-tree takes more than just BuzzWords. In Gautam Das, Christopher Jermaine, Ahmed Eldawy, Philip Bernstein (Eds.), Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 473-488). Houston, TX, US: Association for Computing Machinery.
MLA:
Wang, Ziqi, et al. "Building a BW-tree takes more than just BuzzWords." Proceedings of the 44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018, Houston, TX Ed. Gautam Das, Christopher Jermaine, Ahmed Eldawy, Philip Bernstein, Association for Computing Machinery, 2018. 473-488.
BibTeX: Download