RS-store: RDMA-enabled skiplist-based key-value store for efficient range query

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

References

[1] Ousterhout J, Rosenblum M, Rumble S. The ramcloud storage system. ACM Transactions on Computer Systems, 2015, 33(3): 1–55

[2] Jose J, Subramoni H, Luo M. Memcached design on high performance RDMA capable interconnects. In: Proceedings of International Conference on Parallel Processing. 2011, 743–752

[3] Mitchell C, Geng Y, Li J. Using one-sided RDMA reads to build a fast, cpu-efficient key-value store. In: Proceedings of Annual Technical Conference. 2013, 103–114

[4] Kalia A, Kaminsky M, Andersen D G. Using RDMA efficiently for keyvalue services. In: Proceedings of 2014 ACM Conference on SIGCOMM. 2014, 295–306

[5] Wang Y, Zhang L, Tan J. 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

[6] Ge T, Zdonik S B. A skip-list approach for efficiently processing forecasting queries. Proceedings of the VLDB Endowment, 2008, 1(1): 984–995

[7] Wang D, Liu J. Peer-to-peer asynchronous video streaming using skip list. In: Proceedings of IEEE International Conference on Multimedia & Expo. 2006, 1397–1400

[8] Fuentes J, Luo F, Scherson I D. Synchronizing parallel geometric algorithms on multi-core machines. In: Proceedings of International Symposium on Computing & Networking. 2017, 401–407

[9] Wei X, Shi J, Chen Y. Fast in-memory transaction processing using RDMA and HTM. In: Proceedings of the 25th Symposium on Operating Systems Principles. 2015, 87–104

[10] Kalia A, Kaminsky M, Andersen D G. 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] Dragojevic A, Narayanan D, Castro M. Farm: fast remote memory. In: Proceedings of the 11th Symposium on Networked Systems Design and Implementation. 2014, 401–414

[12] Lu Y, Shu J, Chen Y. Octopus: an rdma-enabled distributed persistent memory file system. In: Proceedings of Annual Technical Conference. 2017, 773–785

[13] Huang G, Cheng X, Wang J. 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

[14] Huang C, Hu H, Qi X. 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

[15] Pugh W. Skip lists: a probabilistic alternative to balanced trees. In: Proceedings ofWorkshop on Algorithms and Data Structures. 1990, 668–676

[16] Pugh W. Concurrent maintenance of skip lists. Technical Report, College Park, MD, USA, 1998

[17] Fraser K. Practical lock-freedom. PhD Thesis, University of Cambridge, UK, 2004

[18] Herlihy M, Lev Y, Luchangco V. A simple optimistic skiplist algorithm. In: Proceedings of International Colloquium on Structural Information and Communication Complexity. 2007, 124–138

[19] Herlihy M, Lev Y, Shavit N. Concurrent lock-free skiplist with wait-free contains operator. US Patent 7,937,378, 2011

[20] Crain T, Gramoli V, Raynal M. Brief announcement: a contention friendly, non-blocking skip list. In: Proceedings of the 26th International Symposium on Distributed Computing. 2012, 423–424

[21] Guerraoui R, Trigonakis V. Optimistic concurrency with OPTIK. In: Proceedings of the 21st ACM Symposium on Principles and Practice of Parallel Programming. 2016, 1–12

[22] Atikoglu B, Xu Y, 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

[23] Nishtala R, Fugal H, Grimm S. Scaling memcache at facebook. In: Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation. 2013, 385–398

[24] Cha S K, Hwang S, Kim K. 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] Lehman P L, Yao S B. Efficient locking for concurrent operations on btrees. ACM Transactions on Database Systems, 1981, 6(4): 650–670

[26] Gavrielatos V, Katsarakis A, Joshi A. Scale-out ccnuma: exploiting skew with strongly consistent caching. In: Proceedings of the 13th EuroSys Conference. 2018, 1–15

[27] Cooper B F, Silberstein A, Tam E. Benchmarking cloud serving systems with YCSB. In: Proceedings of the 1st ACM Symposium on Cloud Computing. 2010, 143–154

RIGHTS & PERMISSIONS

Higher Education Press