jm + bw-trees   2

_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: :

'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.'
skip-lists  algorithms  data-structures  storage  bw-trees  mass-trees  benchmarks  performance  multithreading  lock-free  locking  trees 
5 weeks ago by jm
The Bw-Tree: A B-tree for New Hardware - Microsoft Research
The emergence of new hardware and platforms has led to reconsideration of how data management systems are designed. However, certain basic functions such as key indexed access to records remain essential. While we exploit the common architectural layering of prior systems, we make radically new design decisions about each layer. Our new form of B tree, called the Bw-tree achieves its very high performance via a latch-free approach that effectively exploits the processor caches of modern multi-core chips. Our storage manager uses a unique form of log structuring that blurs the distinction between a page and a record store and works well with flash storage. This paper describes the architecture and algorithms for the Bw-tree, focusing on the main memory aspects. The paper includes results of our experiments that demonstrate that this fresh approach produces outstanding performance.
bw-trees  database  paper  toread  research  algorithms  microsoft  sql  sql-server  b-trees  data-structures  storage  cache-friendly  mechanical-sympathy 
april 2013 by jm

Copy this bookmark: