BL-Tree: The Best of Both Worlds by Combining B+- Tree on Top and LSM - Tree on Bottom

The shattered and overlapped Level-0 data organization is the primary cause of write stall and read amplification problems in LSM-Tree-based Key-Value (KV) stores: (1) Level-0 to Level-1 compaction involves a large amount of data which induces write stalls, and (2) A point lookup needs to access multiple files in Level-0 which leads to significant read amplification. To address the problem, we propose BL-Tree by replacing the shattered Level-0 in LSM-Tree with a B+-Tree in byte-addressable Persistent Memory (PM). The sorted B+-Tree of Level-0 can accelerate the point lookup speed and reduce read/write amplification. BL-Tree further conducts the locality-aware and parallel compaction from the B+-Tree in PM (Level-0) to the lower levels of LSM-Tree in SSDs by only moving cold data downward, thus alleviating the write stalls and reducing the read/write amplification simultaneously. The extensive experiments on the prototype of BL- Tree show that it definitely avoids the write stalls and significantly reduces the read/write amplification. As a result, BL-Tree reduces the P99 tail latency by 65.2 × than LevelDB-PM and speeds up the throughput by more than 2 × under workloads with spatial locality than other KV stores.