LSM-Tree based Key-Value Store on Open-Channel SSD

An Efficient Design and Implementation of LSM-Tree based Key-Value Store on Open-Channel SSD on Eurosys 2014.

In Software-Defined Flash the internal of SSD are exposed to applications. This paper utilize this new interface to redesign log-structured merge tree (LSM-tree) based KV store to fully utilize SSD’s high bandwidth. The system is called LOCS, which is the abbreviation for LSM-tree-based KV store on Open-Channel SSD.

LevelDB is a widely used LSM-tree based KV store. It accumulate fresh updates at one level, and transform to read-only table when it is full.

leveldb

Enabling Concurrent Access to Multiple Channels

The first optimization of LOCS is to enable concurrent access to multiple channels, because the internal parallelism of SSD is exposed to LevelDB.

Write Traffic Control Policy

The write throughput is traded for the read performance

The basic idea is to reduce the write to trade for read performance.

Write Ahead Log

In LevelDB, the write log is written to HDD. However, the logs can be discarded whenever a MemTable is dumped to the SSD. Thus, the LOCS write the logs to a small part of high-performance non-volatile memory (NVM), such as PCM or battery-backup DRAM.