Fragmented Log-Structured Merge Trees

Summary

Key-value stores such as LevelDB and RocksDB are widely deployed both inside companies such as Google and Face- book, and externally in diverse products such as BitCoin Core, MineCraft Pocket Edition, and AutoCAD 2016. Designing such stores is tricky because a number of competing performance goals have to be balanced: low latency for searches, high write throughput, and low write amplification. For exact searches (e.g., get value of key X), both low latency and high write throughput is obtained by writing sequentially in the form of Log-Structured Merge trees (LSM), and using Bloom Filters to identify the blocks that need to be read off storage. However, for range queries (e.g., get value of smallest key bigger than X), bloom filters cannot be used to provide low latency reads. The performance of such range queries be- comes crucial when workloads such as MySQL or filesystems are run on top of these high write-throughput stores. We present Fragmented Log-Structured Merge trees (FLSM), a new object store and data structure that aims to provide low latencies for range queries, while seeking to minimize write amplification and maintain high write throughput. Fragmented-LSM takes advantage of the high parallelism provided by next-generation non-volatile memory storage devices such as Phase Change Memory and Memristors.