Converting Concurrent Range Index Structure to Range Index Structure for Disaggregated Memory
Source abstract
Abstract
In this work, we propose the Spread approach, which tailors a concurrent range index structure to a range index structure for disaggregated memory connected via RDMA (Remote Direct Memory Access). The Spread approach leverages the concept of tolerating transient inconsistencies in a concurrent range index structure to reduce the amount of expensive RDMA operations. Based on the Spread approach, we converted Blink-tree, a concurrent range index structure, to a range index structure for disaggregated memory called RF-tree. In our experimental study, RF-tree shows comparable performance to Sherman, a state-of-the-art and carefully crafted range index structure for disaggregated memory.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Distributed systems and fault tolerance · Parallel Computing and Optimization Techniques · Advanced Data Storage Technologies
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science and Engineering, Konkuk University, Seoul 05029, Republic of Korea
Division of Computer Engineering, Hankuk University of Foreign Studies, Yongin 17035, Republic of Korea
Funding
National Research Foundation of Korea (NRF) · Institute of Information & communications Technology Planning & Evaluation (IITP)
References (31)
Show source-provided references
1. Disaggregated Memory for Expansion and Sharing in Blade Servers10.1145/1555815.1555789 ↗
2. Wang, Q., Lu, Y., and Shu, J. (2022). SIGMOD’22: Proceedings of the 2022 International Conference on Management of Data, Association for Computing Machinery.
3. Zuo, P., Sun, J., Yang, L., Zhang, S., and Hua, Y. (2021, January 14–16). One-sided RDMA-Conscious Extendible Hashing for Disaggregated Memory. Proceedings of the USENIX Annual Technical Conference (USENIX ATC 21), Virtual.
4. Tsai, S.Y., Shan, Y., and Zhang, Y. (2020, January 15–17). Disaggregating Persistent Memory and Controlling Them Remotely: An Exploration of Passive Disaggregated Key-Value Stores. Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC 20), Virtual.
5. Dragojević, A., Narayanan, D., Castro, M., and Hodson, O. (2014, January 2–4). FaRM: Fast Remote Memory. Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14), Seattle, WA, USA.
6. Ziegler, T., Vani, S.T., Binnig, C., Fonseca, R., and Kraska, T. (July, January 30). Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks. Proceedings of the ACM SIGMOD/PODS Conference, Amsterdam, The Netherlands.
7. Mitchell, C., Montgomery, K., Nelson, L., Sen, S., and Li, J. (2016, January 22–24). Balancing CPU and Network in the Cell Distributed B-Tree Store. Proceedings of the USENIX Annual Technical Conference (ATC), Denver, CO, USA.
8. Hwang, D., Kim, W.H., Won, Y., and Nam, B. (2018, January 12–15). Endurable Transient Inconsistency in Byte-addressable Persistent B+-tree. Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST), Oakland, CA, USA.
9. Mathew, A., and Min, C. (September, January 31). HydraList: A Scalable In-Memory Index Using Asynchronous Updates and Partial Replication. Proceedings of the 46th International Conference on Very Large Data Bases (VLDB), Tokyo, Japan.
10. Kim, W.H., Krishnan, R.M., Fu, X., Kashyap, S., and Min, C. (2021, January 26–29). PACTree: A High Performance Persistent Range Index Using PAC Guidelines. Proceedings of the 28th ACM Symposium on Operating Systems Principles (SOSP), Online.10.1145/3477132.3483589 ↗
11. Efficient Locking for Concurrent Operations on B-Trees10.1145/319628.319663 ↗
12. Skip Lists: A Probabilistic Alternative to Balanced Trees10.1145/78973.78977 ↗
13. Hu, Q., Ren, J., Badam, A., Shu, J., and Moscibroda, T. (2017, January 12–14). Log-Structured Non-Volatile Main Memory. Proceedings of the ATC17, Santa Clara, CA, USA.
14. Rumble, S.M., Kejriwal, A., and Ousterhout, J. (2014, January 17–20). Log-structured Memory for DRAM-based Storage. Proceedings of the 12th USENIX Conference on File and Storage Technologies (FAST 14), Santa Clara, CA, USA.
15. The End of a Myth: Distributed Transactions Can Scale10.14778/3055330.3055335 ↗
16. Design Guidelines for Correct, Efficient, and Scalable Synchronization Using One-Sided RDMA10.1145/3589276 ↗
17. Mitchell, C., Geng, Y., and Li, J. (2013, January 26–28). Using One-Sided RDMA Reads to Build a Fast, CPU-Efficient Key-Value Store. Proceedings of the USENIX Annual Technical Conference (USENIX ATC 13), San Jose, CA, USA.
18. Singhvi, A., Akella, A., Anderson, M., Cauble, R., Deshmukh, H., Gibson, D., Martin, M.M.K., Strominger, A., Wenisch, T.F., and Vahdat, A. (2021). SIGCOMM’21: Proceedings of the 2021 ACM SIGCOMM 2021 Conference, Association for Computing Machinery.
19. Wei, X., Chen, R., and Chen, H. (2020, January 4–6). Fast RDMA-based Ordered Key-Value Store using Remote Learned Cache. Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), Virtual.
20. Mellanox Technologies (2023, September 30). RDMA Aware Networks Programming User Manual. Available online: https://docs.nvidia.com/networking/display/rdmaawareprogrammingv17.
21. LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory10.14778/3384345.3384355 ↗
22. UTree: A Persistent B+-Tree with Low Tail Latency10.14778/3407790.3407850 ↗
23. Cooper, B.F., Silberstein, A., Tam, E., Ramakrishnan, R., and Sears, R. (2010, January 10–11). Benchmarking Cloud Serving Systems with YCSB. Proceedings of the 1st ACM Symposium on Cloud Computing (SoCC), Indianapolis, IN, USA.10.1145/1807128.1807152 ↗
24. (2023, August 20). Sherman Github. Available online: https://github.com/thustorage/Sherman.
25. Using RDMA Efficiently for Key-Value Services10.1145/2740070.2626299 ↗
26. Lee, S.K., Mohan, J., Kashyap, S., Kim, T., and Chidambaram, V. (2019, January 27–30). RECIPE: Converting Concurrent DRAM Indexes to Persistent-Memory Indexes. Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP), Huntsville, ON, Canada.10.1145/3341301.3359635 ↗
27. Fu, X., Kim, W.H., Shreepathi, A.P., Ismail, M., Wadkar, S., Lee, D., and Min, C. (2021). SOSP’21: Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, Association for Computing Machinery.
28. Memaripour, A., Izraelevitz, J., and Swanson, S. (2020, January 16–20). Pronto: Easy and Fast Persistence for Volatile Data Structures. Proceedings of the 25th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Lausanne, Switzerland.10.1145/3373376.3378456 ↗
29. Krishnan, R.M., Kim, W.H., Fu, X., Monga, S.K., Lee, H.W., Jang, M., Mathew, A., and Min, C. (2021, January 14–16). TIPS: Making Volatile Index Structures Persistent with DRAM-NVMM Tiering. Proceedings of the 2021 USENIX Annual Technical Conference (USENIX ATC 21), Virtual.
30. David, T., Dragojevic, A., Guerraoui, R., and Zablotchi, I. (2018, January 11–13). Log-free concurrent data structures. Proceedings of the 2018 USENIX Annual Technical Conference (ATC), Boston, MA, USA.
31. Friedman, M., Ben-David, N., Wei, Y., Blelloch, G.E., and Petrank, E. (2020, January 15–20). NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey. Proceedings of the 2020 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), London, UK.10.1145/3385412.3386031 ↗