The Bw-Tree

A B-tree for New Hardware Platforms

Presented by Liming Deng

Part I - Introduction

The New Environment

1. Multi-core CPU
2. Flash storage

The New Environment

Multi-core CPU

​

1. Latch-free
2. Cache-friendly

The New Environment

Flash storage ( Providing FTL)

• Host log structuring for itself

Part II - Architecture

Architecture

1. Focus on Bw-tree layer
2. Compare to other in-memory index structure

Architecture

1. Latch-free
1. Install state via CAS
2. Cache-friendly
• Delta update

put(x, a):

v = read(x)

return v == cas(x, v, a)

Part II - IN-MEMORY

LATCH FREE PAGES

IN-MEMORY LATCH FREE PAGES

Elastic Virtual Pages

Node

Internal index:

Separator key

Record or

Memory pointer to other

PID

IN-MEMORY LATCH FREE PAGES

Updates

​

1. Create a `update delta record`.
2. Use CAS to prepend `update delta` to Page P.
3. Use CAS to install the memory address of D to mapping table.

IN-MEMORY LATCH FREE PAGES

Consolidation

​

• Apply delta to base page P
• Use CAS to install new page P’ to mapping table.

​

​

​

How to search?

​

1. Traverse the delta chain
2. Not found? Go for the base page via a binary search.

IN-MEMORY LATCH FREE PAGES

Garbage Collection

​

1. Using Epoch-based reclamation: https://aturon.github.io/blog/2015/08/27/epoch/#epoch-based-reclamation

1. A global epoch counter (taking on values 0, 1, and 2);
2. A global list of garbage for each epoch;
3. An “active” flag for each thread;
4. An epoch counter for each thread.

​

Part III - SMO

SMO =

structure modification operation

Split

​

1. Child Split
2. Parent Update

SMO =

structure modification operation

Split

​

• Child Split
1. Create right sibling Q with Kp

SMO =

structure modification operation

Split

​

• Child Split
• Create sibling Q
• Install split delta.

​

Split delta = {

Kp, AddressOfQ

}

SMO =

structure modification operation

Split

​

• Child Split
• Create sibling Q
• Install split delta.
• Parent update
• Install index entry delta

SMO =

structure modification operation

Split

​

• Child Split
• Create sibling Q
• Install split delta.
• Parent update
• Install index entry delta

SMO =

structure modification operation

Merge

​

• Mark for delete: remove node delta for R
• Merging Children: merge delta for L
• Parent Update.
• index term delete delta

Last Part - Performance

Cache

Throughput

Thank You !