PTierDB: Building Better Read-Write Cost Balanced Key-Value Stores for Small Data on SSD

Li Liu1 and Ke Zhou2
1Wuhan National Laboratory for Optoelectronics, Huazhong University of Science and Technology, Wuhan, China
lillian hust@hust.edu.cn
2Key Laboratory of Information Storage System, Ministry of Education of China, Wuhan, China
zhke@hust.edu.cn

ABSTRACT


The popular Log-Structured Merge (LSM) tree based Key-Value (KV) stores make trade-offs between write cost and read cost via different merge policies, i.e., leveling and tiering. It has been widely documented that leveling severely hampers write throughput, while tiering hampers read throughput. The characteristics of modern workloads are seriously challenging LSM-tree based KV stores for high performance and high scalability on SSDs. In this work, we present PTierDB, an LSMtree based KV store that strikes the better balance between read cost and write cost for small data on SSD via an adaptive tiering principle and three merge policies in the LSM-tree, leveraging both the sequential and random performance characteristics of SSDs. Adaptive tiering introduces two merge principles: prefixbased data split which bounds the lookup cost and coexisted merge and move which reduces data merging. Based on adaptive tiering, three merge policies make decisions to mergesort or move data during the merging processes for different levels. We demonstrate the advantages of PTierDB with both microbenchmarks and YCSB workloads. Experimental results show that, compared with state-of-the-art KV stores and the KV implementations with popular merge policies, PTierDB achieves a better balance between read cost and write cost, and yields up to 2.5x improvement in the performance and 50% reduction of write amplification.



Full Text (PDF)