The Bw-Tree Key-Value Store and Its Applications to Server/Cloud Data Management in Production

The Bw-Tree is an ordered key-value store, built by layering a B-tree form access method over a cache/storage sub-system (LLAMA) that is lock-free and organizes storage in a log-structured manner. It is designed to optimize performance on modern hardware, specifically (i) multi-core processors with multi-level memory/cache hierarchy, and (ii) flash memory based SSDs with fast random reads (but inefficient random write performance). The Bw-Tree is shipping in three of Microsoft’s server/cloud products – as the key sequential index in SQL Server Hekaton (main memory database), as the indexing engine inside Azure DocumentDB (distributed document-oriented store), and as an ordered key-value store in Bing ObjectStore (distributed back-end supporting many properties in Bing).

Learning Objectives

Bw-Tree data structure
Lock-free design for high concurrency
Log-structured storage design for flash based SSDs
Page-oriented store (LLAMA) for building access methods on top
Bw-Tree Applications in Production at Microsoft