PebblesDB
Pandian Raju, Rohan Kadekodi, Vijay Chidambaram V et al. · Symposium on Operating Systems Principles · 2017
Key-value stores such as LevelDB and RocksDB offer excellent write throughput, but suffer high write amplification. The write amplification problem is due to the Log-Structured Merge Trees data structure that underlies these key-value stores. To remedy this problem, this paper presents a novel data structure that is inspired by Skip Lists, termed Fragmented Log-Structured Merge Trees (FLSM). FLSM introduces the notion of guards to organize logs, and avoids rewriting data in the same level. We build PebblesDB, a high-performance key-value store, by modifying HyperLevelDB to use the FLSM data structure. We evaluate PebblesDB using micro-benchmarks and show that for write-intensive workloads, PebblesDB reduces write amplification by 2.4-3x compared to RocksDB, while increasing write throughput by 6.7x. We modify two widely-used NoSQL stores, MongoDB and HyperDex, to use PebblesDB as their underlying storage engine. Evaluating these applications using the YCSB benchmark shows that throughput is increased by 18-105% when using PebblesDB (compared to their default storage engines) while write IO is decreased by 35-55%.
Cited by 317 works. doi:10.1145/3132747.3132765
Authors
References
- Space/time trade-offs in hash coding with allowable errors
- Ubiquitous B-Tree
- Benchmarking cloud serving systems with YCSB
- The log-structured merge-tree (LSM-tree)
- The input/output complexity of sorting and related problems
- Design tradeoffs for SSD performance
- FAWN
- Characterizing flash memory
- Bit error rate in NAND Flash memories
- Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC ’17)