Indexing on Modern Hardware: Hekaton and Beyond

Justin Levandoski, David Lomet, Sudipta Sengupta, Adrian Birka, and Cristian Diaconu


Recent OLTP support exploits new techniques, running on modern hardware, to achieve unprecedented performance compared with prior approaches. In SQL Server, the Hekaton main-memory database engine embodies this new OLTP support. Hekaton uses the Bw-tree to achieve its great indexing performance. The Bw-Tree is a latch-free B-tree index that also exploits log-structured storage when used “beyond” Hekaton as a separate key value store. It is designed from the ground up to address two hardware trends: (1) Multi-core and main memory hierarchy: the Bw-tree is completely latch-free, using an atomic compare-and-swap instruction to install state changes on a “page address” mapping table; it performs updates as “deltas” to avoid update-in-place. These improve performance by eliminating thread blocking while improving cache hit ratios. (2) flash storage: the Bw-tree organizes secondary storage in a log-structured manner, using large sequential writes to avoid the adverse performance impact of random writes. We demontrate the architectural versatility and performance of the Bw-tree in two scenarios: (a) running live within Hekaton and (2) running as a standalone key value store compared to both BerkeleyDB and a state-of-the-art in-memory range index (latch-free skiplists). Using workloads from real-world applications (Microsoft XBox Live Primetime and enterprise deduplication), we show the Bw-tree is 19x faster than BerkeleyDB and 3x faster than skiplists.


Publication typeInproceedings
Published inProceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2014
> Publications > Indexing on Modern Hardware: Hekaton and Beyond