Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2021, Vol. 15 Issue (6) : 156617    https://doi.org/10.1007/s11704-020-0126-6
RESEARCH ARTICLE
RS-store: RDMA-enabled skiplist-based key-value store for efficient range query
Chenchen HUANG, Huiqi HU(), Xuecheng Qi, Xuan ZHOU, Aoying ZHOU
School of Data Science and Engineering, East China Normal University, Shanghai 200062, China
 Download: PDF(1876 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Many key-value stores use RDMA to optimize the messaging and data transmission between application layer and the storage layer, most of which only provide point-wise operations. Skiplist-based store can support both point operations and range queries, but its CPU-intensive access operations combined with the high-speed network will easily lead to the storage layer reaches CPU bottlenecks. The common solution to this problem is offloading some operations into the application layer and using RDMA bypassing CPU to directly perform remote access, but this method is only used in the hash tablebased store. In this paper, we present RS-store, a skiplist-based key-value store with RDMA, which can overcome the CPU handle of the storage layer by enabling two access modes: local access and remote access. In RS-store, we redesign a novel data structure R-skiplist to save the communication cost in remote access, and implement a latch-free concurrency control mechanism to ensure all the concurrency during two access modes. RS-store also supports client-active range query which can reduce the storage layer’s CPU consumption. At last, we evaluate RS-store on an RDMA-capable cluster. Experimental results show that RS-store achieves up to 2x improvements over RDMA-enabled RocksDB on the throughput and application’s scalability.

Keywords key-value store      skiplist      RDMA     
Corresponding Author(s): Huiqi HU   
About author:

Just Accepted Date: 17 November 2020   Issue Date: 07 September 2021
 Cite this article:   
Chenchen HUANG,Huiqi HU,Xuecheng Qi, et al. RS-store: RDMA-enabled skiplist-based key-value store for efficient range query[J]. Front. Comput. Sci., 2021, 15(6): 156617.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-020-0126-6
https://academic.hep.com.cn/fcs/EN/Y2021/V15/I6/156617
1 J Ousterhout, M Rosenblum, S Rumble. The ramcloud storage system. ACM Transactions on Computer Systems, 2015, 33(3): 1–55
https://doi.org/10.1145/2806887
2 J Jose, H Subramoni, M Luo. Memcached design on high performance RDMA capable interconnects. In: Proceedings of International Conference on Parallel Processing. 2011, 743–752
https://doi.org/10.1109/ICPP.2011.37
3 C Mitchell, Y Geng, J Li. Using one-sided RDMA reads to build a fast, cpu-efficient key-value store. In: Proceedings of Annual Technical Conference. 2013, 103–114
4 A Kalia, M Kaminsky, D G Andersen. Using RDMA efficiently for keyvalue services. In: Proceedings of 2014 ACM Conference on SIGCOMM. 2014, 295–306
https://doi.org/10.1145/2619239.2626299
5 Y Wang, L Zhang, J Tan. Hydradb: a resilient rdma-driven key-value middleware for in-memory cluster computing. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 2015, 1–11
https://doi.org/10.1145/2807591.2807614
6 T Ge, S B Zdonik. A skip-list approach for efficiently processing forecasting queries. Proceedings of the VLDB Endowment, 2008, 1(1): 984–995
https://doi.org/10.14778/1453856.1453962
7 D Wang, J Liu. Peer-to-peer asynchronous video streaming using skip list. In: Proceedings of IEEE International Conference on Multimedia & Expo. 2006, 1397–1400
https://doi.org/10.1109/ICME.2006.262800
8 J Fuentes, F Luo, I D Scherson. Synchronizing parallel geometric algorithms on multi-core machines. In: Proceedings of International Symposium on Computing & Networking. 2017, 401–407
https://doi.org/10.1109/CANDAR.2017.59
9 X Wei, J Shi, Y Chen. Fast in-memory transaction processing using RDMA and HTM. In: Proceedings of the 25th Symposium on Operating Systems Principles. 2015, 87–104
https://doi.org/10.1145/2815400.2815419
10 A Kalia, M Kaminsky, D G Andersen. Fasst: fast, scalable and simple distributed transactions with two-sided (RDMA) datagram RPCs. In: Proceedings of the 12th Symposium on Operating Systems Design and Implementation. 2016, 185–201
11 A Dragojevic, D Narayanan, M Castro. Farm: fast remote memory. In: Proceedings of the 11th Symposium on Networked Systems Design and Implementation. 2014, 401–414
12 Y Lu, J Shu, Y Chen. Octopus: an rdma-enabled distributed persistent memory file system. In: Proceedings of Annual Technical Conference. 2017, 773–785
13 G Huang, X Cheng, J Wang. X-engine: an optimized storage engine for large-scale e-commerce transaction processing. In: Proceedings of the 2019 International Conference on Management of Data. 2019, 651–665
https://doi.org/10.1145/3299869.3314041
14 C Huang, H Hu, X Qi. Rs-store: a skiplist-based key-value store with remote direct memory access. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2020, 314–323
https://doi.org/10.1007/978-3-030-59410-7_22
15 W Pugh. Skip lists: a probabilistic alternative to balanced trees. In: Proceedings ofWorkshop on Algorithms and Data Structures. 1990, 668–676
https://doi.org/10.1145/78973.78977
16 W Pugh. Concurrent maintenance of skip lists. Technical Report, College Park, MD, USA, 1998
17 K Fraser. Practical lock-freedom. PhD Thesis, University of Cambridge, UK, 2004
18 M Herlihy, Y Lev, V Luchangco. A simple optimistic skiplist algorithm. In: Proceedings of International Colloquium on Structural Information and Communication Complexity. 2007, 124–138
https://doi.org/10.1007/978-3-540-72951-8_11
19 M Herlihy, Y Lev, N Shavit. Concurrent lock-free skiplist with wait-free contains operator. US Patent 7,937,378, 2011
20 T Crain, V Gramoli, M Raynal. Brief announcement: a contention friendly, non-blocking skip list. In: Proceedings of the 26th International Symposium on Distributed Computing. 2012, 423–424
https://doi.org/10.1007/978-3-642-33651-5_39
21 R Guerraoui, V Trigonakis. Optimistic concurrency with OPTIK. In: Proceedings of the 21st ACM Symposium on Principles and Practice of Parallel Programming. 2016, 1–12
https://doi.org/10.1145/2851141.2851146
22 B Atikoglu, Y Xu, Frachtenberg E.Workload analysis of a large-scale keyvalue store. In: Proceedings of Joint International Conference on Measurement and Modeling of Computer Systems. 2012, 53–64
https://doi.org/10.1145/2318857.2254766
23 R Nishtala, H Fugal, S Grimm. Scaling memcache at facebook. In: Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation. 2013, 385–398
24 S K Cha, S Hwang, K Kim. Cache-conscious concurrency control of main-memory indexes on shared-memory multiprocessor systems. In: Proceedings of the 27th International Conference on Very Large Data Bases. 2001, 181–190
25 P L Lehman, S B Yao. Efficient locking for concurrent operations on btrees. ACM Transactions on Database Systems, 1981, 6(4): 650–670
https://doi.org/10.1145/319628.319663
26 V Gavrielatos, A Katsarakis, A Joshi. Scale-out ccnuma: exploiting skew with strongly consistent caching. In: Proceedings of the 13th EuroSys Conference. 2018, 1–15
https://doi.org/10.1145/3190508.3190550
27 B F Cooper, A Silberstein, E Tam. Benchmarking cloud serving systems with YCSB. In: Proceedings of the 1st ACM Symposium on Cloud Computing. 2010, 143–154
https://doi.org/10.1145/1807128.1807152
[1] Article highlights Download
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed