_Building a Bw-Tree Takes More Than Just Buzz Words_, SIGMOD 2018
‘An account of our disappointing journey to build a open-source lock-free Bw-Tree for the Peloton DBMS.’ ‘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.’ Finally: https://twitter.com/andy_pavlo/status/986647389820747776 : ‘Our results show that @ViktorLeis’s ART index and @xexd’s MassTree and a non-fancy B+Tree are currently the best for in-memory workloads. Skip Lists are always terrible.’
(tags: skip-lists algorithms data-structures storage bw-trees mass-trees benchmarks performance multithreading lock-free locking trees)