BiloKey : A Scalable Bi-Index Locality-Aware In-Memory Key-Value Store

doi:10.1109/TPDS.2019.2891599

	BiloKey : A Scalable Bi-Index Locality-Aware In-Memory Key-Value Store
	Ma, Wenlong 1,2; Zhu, Yuqing 1,2; Li, Cheng 3; Guo, Mengying 1,2; Bao, Yungang 1,2
	2019-07-01
发表期刊	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
ISSN	1045-9219
卷号	30 期号:7 页码:1528-1540
摘要	Fast in-memory key value stores are the keys to building large-scale Internet services. The state-of-the-art solutions mainly focus on optimizing the performance for read-intensive workloads. Nevertheless, a wide range of applications demonstrate a significant amount of updates and range queries, which scale poorly with the current implementations. In this paper, we present BiloKey, a highly scalable in-memory key value store on multi-core machines, significantly outperforming Redis and Memcached for a variety of mixed read and write workloads. To achieve this, BiloKey leverages a fast bi-index comprised by a Hash Table index and a SkipList index, where the former supports feature rich operations including GET, UPDATE and DELETE with O(1) complexity, while the latter supports SCAN with O(logN) complexity. Furthermore, to make the bi-index design scale well, BiloKey adopts three techniques: lazy synchronization for reducing the overhead of maintaining index consistency, lock-free data structure for supporting multi-writers, and locality-aware data parallel processing for preserving the data locality of requests. Compared with two popular in-memory KV stores (i.e., Redis and Memcached), experimental results show that: (1) for write-intensive workloads, BiloKey outperforms Redis and Memcached by 7.8x and 3.7x on average (up to 11.5x and 4.8x), respectively; (2) for scan-intensive workloads, BiloKey achieves an average speedup of 2.3x against Redis; (3) for read-intensive workloads, BiloKey also outperforms Redis and Memcached by 1.2x and 1.8x on average.
关键词	In-memory key-value store multi-core scalability locality-aware networking hybrid index lock-free access
DOI	10.1109/TPDS.2019.2891599
收录类别	SCI
语种	英语
资助项目	State Key Development Program for Basic Research of China[2014CB340402] ; National Key R&D Program of China[2016YFB1000201] ; National Natural Science Foundation of China[61303054] ; National Natural Science Foundation of China[61420106013] ; National Natural Science Foundation of China[61432006]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:000472199900006
出版者	IEEE COMPUTER SOC
引用统计	被引频次：3[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4192
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhu, Yuqing
作者单位	1.Chinese Acad Sci, State Key Lab Comp Architecture, Inst Comp Technol, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 10048, Peoples R China 3.Univ Sci & Technol China, Sch Comp Sci & Technol, Hefei 230026, Anhui, Peoples R China
推荐引用方式 GB/T 7714	Ma, Wenlong,Zhu, Yuqing,Li, Cheng,et al. BiloKey : A Scalable Bi-Index Locality-Aware In-Memory Key-Value Store[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2019,30(7):1528-1540.
APA	Ma, Wenlong,Zhu, Yuqing,Li, Cheng,Guo, Mengying,&Bao, Yungang.(2019).BiloKey : A Scalable Bi-Index Locality-Aware In-Memory Key-Value Store.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,30(7),1528-1540.
MLA	Ma, Wenlong,et al."BiloKey : A Scalable Bi-Index Locality-Aware In-Memory Key-Value Store".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 30.7(2019):1528-1540.