  Log-Structured-Merge (LSM) tree-based key value stores are facing critical
challenges of fully leveraging the dramatic performance improvements of the
underlying storage devices, which makes the compaction operations of LSM key
value stores become CPU-bound, and slow compactions significantly degrade key
value store performance. To address this issue, we propose LUDA, an LSM key
value store with CUDA, which uses a GPU to accelerate compaction operations of
LSM key value stores. How to efficiently parallelize compaction procedures as
well as accommodate the optimal performance contract of the GPU architecture
challenge LUDA. Specifically, LUDA overcomes these challenges by exploiting the
data independence between compaction procedures and using cooperative sort
mechanism and judicious data movements. Running on a commodity GPU under
different levels of CPU overhead, evaluation results show that LUDA provides up
to 2x higher throughput and 2x data processing speed, and achieves more stable
99th percentile latencies than LevelDB and RocksDB.
