Paper Info
Title
SifrDB: A Unified Solution for Write-Optimized Key-Value Stores in Large Datacenter.
Abstract
Key-value (KV) stores based on multi-stage structures are widely deployed in the cloud to ingest massive amounts of easily searchable user data. However, current KV storage systems inevitably sacrifice at least one of the performance objectives, such as write, read, space efficiency etc., for the optimization of others. To understand the root cause of and ultimately remove such performance disparities among the representative existing KV stores, we analyze their enabling mechanisms and classify them into two models of data structures facilitating KV operations, namely, the multi-stage tree (MS-tree) as represented by LevelDB, and the multi-stage forest (MS-forest) as typified by the size-tiered compaction in Cassandra. We then build a KV store on a novel split MS-forest structure, called SifrDB, that achieves the lowest write amplification across all workload patterns and minimizes space reservation for the compaction. In addition, we design a highly efficient parallel search algorithm that fully exploits the access parallelism of modern flash-based storage devices to substantially boost the read performance. Evaluation results show that under both micro and YCSB benchmarks, SifrDB outperforms its closest competitors, i.e., the popular MS-forest implementations, making it a highly desirable choice for the modern large-dataset-driven KV stores.
Year
DOI
Venue
2018
10.1145/3267809.3267829
SoCC '18: ACM Symposium on Cloud Computing Carlsbad CA USA October, 2018
Keywords
Field
DocType
Key-Value, Multi-Stage, LSM-tree, Parallel Search
Reservation,Data structure,Computer science,Workload,Write amplification,Real-time computing,Implementation,Exploit,Root cause,Distributed computing,Cloud computing
Conference
ISBN
Citations 
PageRank 
978-1-4503-6011-1
2
0.38
References 
Authors
17
4
Name
Order
Citations
PageRank
Fei Mei161.76
Qiang Cao2178.39
Hong Jiang32137157.96
Jingjun Li461.86