{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T13:10:03Z","timestamp":1751375403703,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"Anhui Province Key Laboratory of High-Performance Computing, Huawei"},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61672480"],"award-info":[{"award-number":["61672480"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Disciplinary Innovation and Talent Introduction Program for Higher Education Institutions","award":["BP0719016"],"award-info":[{"award-number":["BP0719016"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>In CPU-parsimonious environments, such as disaggregated memory systems, the limited CPU power on the memory side constrains the ability to perform more operations. Thus, reducing CPU usage and enhancing concurrency performance are critical for indexing key-value storage in these scenarios. Current hash indexes support one-sided RDMA access and lock-free concurrency control with good performance but lack range query support. In contrast, existing tree indexes support range query but only implement expensive locks for concurrency control. Therefore, designing a tree index that supports lock-free concurrent access and one-sided RDMA is a significant challenge.<\/jats:p>\n          <jats:p>To address these issues, this paper proposes a lock-free tree index based on the van Emde Boas (vEB) tree, called vBoost. vBoost inherits the vEB tree\u2019s characteristics of index nodes without splitting or merging, and simplifies concurrency control by managing changes at a single node. It redesigns tree nodes with an 8-byte compact data structure, allowing each key-value pair to support RDMA_CAS atomic operations for lock-free concurrency. Additionally, vBoost leverages the RDMA Doorbell technique to reduce RTTs, enhancing range query and write performance. Evaluation results show that, vBoost achieves up to 3.85\u00d7 higher throughput and better scalability under YCSB workloads compared to state-of-the-art tree indexes.<\/jats:p>","DOI":"10.1145\/3722112","type":"journal-article","created":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T11:14:16Z","timestamp":1741346056000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Lock-free RDMA-friendly Index in CPU-parsimonious Environments"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0389-7178","authenticated-orcid":false,"given":"Yuting","family":"Li","sequence":"first","affiliation":[{"name":"University of Science and Technology of China","place":["Hefei, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4850-3299","authenticated-orcid":false,"given":"Yun","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China","place":["Hefei, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8765-2856","authenticated-orcid":false,"given":"Pengcheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co Ltd","place":["Shenzhen, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1617-1482","authenticated-orcid":false,"given":"Yonghui","family":"Xu","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co Ltd","place":["Shenzhen, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-3301-465X","authenticated-orcid":false,"given":"Weiguang","family":"Wang","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co Ltd","place":["Shenzhen, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCC.2024.3437472"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.80120"},{"key":"e_1_3_3_4_2","article-title":"Foundations of multithreaded, parallel, and distributed programming","author":"Andrews Gregory R.","year":"2000","unstructured":"Gregory R. Andrews. 2000. Foundations of multithreaded, parallel, and distributed programming. Wesley, University of Arizona, USA (2000).","journal-title":"Wesley, University of Arizona, USA"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/2043535.2043537"},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/978-3-642-17679-1_10","volume-title":"International Conference on Distributed Computing and Networking","author":"Braginsky Anastasia","year":"2011","unstructured":"Anastasia Braginsky and Erez Petrank. 2011. Locality-conscious lock-free linked lists. In International Conference on Distributed Computing and Networking. Springer, 107\u2013118."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312016"},{"key":"e_1_3_3_8_2","doi-asserted-by":"crossref","unstructured":"Wei Cao Yingqiang Zhang Xinjun Yang Feifei Li Sheng Wang Qingda Hu Xuntao Cheng Zongzhi Chen Zhenjun Liu Jing Fang et\u00a0al. 2021. Polardb serverless: A cloud native database for disaggregated data centers. In Proceedings of the 2021 International Conference on Management of Data. 2477\u20132489.","DOI":"10.1145\/3448016.3457560"},{"key":"e_1_3_3_9_2","first-page":"799","volume-title":"2020 USENIX Annual Technical Conference (USENIX ATC\u201920)","author":"Chen Zhangyu","year":"2020","unstructured":"Zhangyu Chen, Yu Hua, Bo Ding, and Pengfei Zuo. 2020. Lock-free concurrent level hashing for persistent memory. In 2020 USENIX Annual Technical Conference (USENIX ATC\u201920). 799\u2013812."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_3_3_11_2","unstructured":"Intel Corporation. 2024. oneTBB. (2024). https:\/\/github.com\/uxlfoundation\/oneTBBAccessed: 15-Jan-2025."},{"key":"e_1_3_3_12_2","first-page":"401","volume-title":"Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation","author":"Dragojevic Aleksandar","year":"2014","unstructured":"Aleksandar Dragojevic, Dushyanth Narayanan, Miguel Castro, and Orion Hodson. 2014. FaRM: Fast remote memory. In Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation. 401\u2013414."},{"key":"e_1_3_3_13_2","first-page":"249","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation","author":"Gao Peter X.","year":"2016","unstructured":"Peter X. Gao, Akshay Narayan, Sagar Karandikar, Joao Carreira, Sangjin Han, Rachit Agarwal, Sylvia Ratnasamy, and Scott Shenker. 2016. Network requirements for resource disaggregation. In 12th USENIX Symposium on Operating Systems Design and Implementation. 249\u2013264."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934908"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507762"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3694715.3695951"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626299"},{"key":"e_1_3_3_18_2","first-page":"437","volume-title":"2016 USENIX Annual Technical Conference","author":"Kalia Anuj","year":"2016","unstructured":"Anuj Kalia, Michael Kaminsky, and David G Andersen. 2016. Design guidelines for high performance RDMA systems. In 2016 USENIX Annual Technical Conference. 437\u2013450."},{"key":"e_1_3_3_19_2","first-page":"185","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation","author":"Kalia Anuj","year":"2016","unstructured":"Anuj Kalia, Michael Kaminsky, and David G. Andersen. 2016. FaSST: Fast, scalable and simple distributed transactions with two-sided RDMA datagram RPCs. In 12th USENIX Symposium on Operating Systems Design and Implementation. 185\u2013201."},{"issue":"13","key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"4023","DOI":"10.14778\/3565838.3565854","article-title":"DINOMO: An elastic, scalable, high-performance key-value store for disaggregated persistent memory","volume":"15","author":"Lee Sekwon","year":"2022","unstructured":"Sekwon Lee, Soujanya Ponnapalli, Sharad Singhal, Marcos K. Aguilera, Kimberly Keeton, and Vijay Chidambaram. 2022. DINOMO: An elastic, scalable, high-performance key-value store for disaggregated persistent memory. Proc. VLDB Endow. 15, 13 (2022), 4023\u20134037.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_3_21_2","first-page":"38","volume-title":"2013 IEEE 29th International Conference on Data Engineering","author":"Leis Viktor","year":"2013","unstructured":"Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In 2013 IEEE 29th International Conference on Data Engineering. 38\u201349."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933349.2933352"},{"key":"e_1_3_3_23_2","first-page":"302","volume-title":"2013 IEEE 29th International Conference on Data Engineering","author":"Levandoski Justin J.","year":"2013","unstructured":"Justin J. Levandoski, David B. Lomet, and Sudipta Sengupta. 2013. The Bw-Tree: A B-tree for new hardware platforms. In 2013 IEEE 29th International Conference on Data Engineering. 302\u2013313."},{"key":"e_1_3_3_24_2","first-page":"99","volume-title":"21st USENIX Conference on File and Storage Technologies","author":"Li Pengfei","year":"2023","unstructured":"Pengfei Li, Yu Hua, Pengfei Zuo, Zhangyu Chen, and Jiajie Sheng. 2023. ROLEX: A scalableRDMA-oriented learned key-value store for disaggregated memory systems. In 21st USENIX Conference on File and Storage Technologies. 99\u2013114."},{"key":"e_1_3_3_25_2","first-page":"158","volume-title":"2024 IEEE International Conference on Cluster Computing Workshops (CLUSTER Workshops\u201924)","author":"Li Yuting","year":"2024","unstructured":"Yuting Li, Yun Xu, Pengcheng Wang, Yonghui Xu, and Weiguang Wang. 2024. vBoost: A lock-free distributed index based on vEB tree for disaggregated memory. In 2024 IEEE International Conference on Cluster Computing Workshops (CLUSTER Workshops\u201924). 158\u2013159."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064015"},{"key":"e_1_3_3_27_2","first-page":"553","volume-title":"17th USENIX Symposium on Operating Systems Design and Implementation","author":"Luo Xuchuan","year":"2023","unstructured":"Xuchuan Luo, Pengfei Zuo, Jiacheng Shen, Jiazhen Gu, Xin Wang, Michael R. Lyu, and Yangfan Zhou. 2023. SMART: A high-performance adaptive radix tree for disaggregated memory. In 17th USENIX Symposium on Operating Systems Design and Implementation. 553\u2013571."},{"key":"e_1_3_3_28_2","unstructured":"Xuchuan Luo Pengfei Zuo Jiacheng Shen Jiazhen Gu Xin Wang Michael R. Lyu and Yangfan Zhou. 2023. SMART Source Code. https:\/\/github.com\/dmemsys\/SMART. GitHub repository Accessed: 2025-01-14."},{"key":"e_1_3_3_29_2","first-page":"313","volume-title":"20th USENIX Conference on File and Storage Technologies","author":"Lv Wenhao","year":"2022","unstructured":"Wenhao Lv, Youyou Lu, Yiming Zhang, Peile Duan, and Jiwu Shu. 2022. InfiniFS: An efficient metadata service for large-scale distributed filesystems. In 20th USENIX Conference on File and Storage Technologies. 313\u2013328."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2022.3188656"},{"key":"e_1_3_3_31_2","first-page":"456","volume-title":"IEEE International Conference on Cluster Computing","author":"Ma Teng","year":"2021","unstructured":"Teng Ma, Kang Chen, Shaonan Ma, Zhuo Song, and Yongwei Wu. 2021. Thinking more about RDMA memory semantics. In IEEE International Conference on Cluster Computing. 456\u2013467."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571829"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.14778\/3641204.3641218"},{"key":"e_1_3_3_34_2","first-page":"103","volume-title":"2013 USENIX Annual Technical Conference (USENIX ATC\u201913)","author":"Mitchell Christopher","year":"2013","unstructured":"Christopher Mitchell, Yifeng Geng, and Jinyang Li. 2013. Using one-sided RDMA reads to build a fast, CPU-efficient key-value store. In 2013 USENIX Annual Technical Conference (USENIX ATC\u201913). 103\u2013114."},{"key":"e_1_3_3_35_2","first-page":"451","volume-title":"2016 USENIX Annual Technical Conference","author":"Mitchell Christopher","year":"2016","unstructured":"Christopher Mitchell, Kate Montgomery, Lamont Nelson, Siddhartha Sen, and Jinyang Li. 2016. Balancing CPU and network in the cell distributed B-Tree store. In 2016 USENIX Annual Technical Conference. 451\u2013464."},{"key":"e_1_3_3_36_2","first-page":"351","volume-title":"Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems","volume":"1","author":"Ren Feng","year":"2024","unstructured":"Feng Ren, Mingxing Zhang, Kang Chen, Huaxia Xia, Zuoning Chen, and Yongwei Wu. 2024. Scaling up memory disaggregated applications with Smart. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Vol. 1. 351\u2013367."},{"key":"e_1_3_3_37_2","first-page":"69","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation","author":"Shan Yizhou","year":"2018","unstructured":"Yizhou Shan, Yutong Huang, Yilun Chen, and Yiying Zhang. 2018. LegoOS: A disseminated, distributed OS for hardware resource disaggregation. In 13th USENIX Symposium on Operating Systems Design and Implementation. 69\u201387."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613144"},{"key":"e_1_3_3_39_2","first-page":"81","volume-title":"21st USENIX Conference on File and Storage Technologies","author":"Shen Jiacheng","year":"2023","unstructured":"Jiacheng Shen, Pengfei Zuo, Xuchuan Luo, Tianyi Yang, Yuxin Su, Yangfan Zhou, and Michael R. Lyu. 2023. FUSEE: A fully memory-disaggregated key-value store. In 21st USENIX Conference on File and Storage Technologies. 81\u201398."},{"key":"e_1_3_3_40_2","first-page":"255","volume-title":"16th USENIX Symposium on Networked Systems Design and Implementation","author":"Shrivastav Vishal","year":"2019","unstructured":"Vishal Shrivastav, Asaf Valadarsky, Hitesh Ballani, Paolo Costa, Ki Suh Lee, Han Wang, Rachit Agarwal, and Hakim Weatherspoon. 2019. Shoal: A network architecture for disaggregated racks. In 16th USENIX Symposium on Networked Systems Design and Implementation. 255\u2013270."},{"key":"e_1_3_3_41_2","first-page":"2171","volume-title":"Masters Abstracts Int.","author":"Sultana Afroza","year":"2008","unstructured":"Afroza Sultana, Helen A. Cameron, and Peter C. J. Graham. 2008. Concurrent B-trees with lock-free techniques. In Masters Abstracts Int., Vol. 46. 2171."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.26"},{"issue":"3","key":"e_1_3_3_43_2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","article-title":"Preserving order in a forest in less than logarithmic time and linear space","volume":"6","author":"Boas Peter van Emde","year":"1977","unstructured":"Peter van Emde Boas. 1977. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters 6, 3 (1977), 80\u201382.","journal-title":"Information Processing Letters"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517824"},{"key":"e_1_3_3_45_2","unstructured":"Qing Wang Youyou Lu and Jiwu Shu. 2022. Sherman Source Code. https:\/\/github.com\/thustorage\/Sherman. GitHub repository accessed: 2025-01-14."},{"key":"e_1_3_3_46_2","first-page":"2835","volume-title":"2023 IEEE 39th International Conference on Data Engineering","author":"Wang Ruihong","year":"2023","unstructured":"Ruihong Wang, Jianguo Wang, Prishita Kadam, M. Tamer \u00d6zsu, and Walid G. Aref. 2023. dLSM: An LSM-based index for memory disaggregation. In 2023 IEEE 39th International Conference on Data Engineering. 2835\u20132849."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196895"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3468520"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815419"},{"key":"e_1_3_3_50_2","first-page":"51","volume-title":"20th USENIX Conference on File and Storage Technologies","author":"Zhang Ming","year":"2022","unstructured":"Ming Zhang, Yu Hua, Pengfei Zuo, and Lurong Liu. 2022. FORD: Fast one-sided RDMA-based distributed transactions for disaggregated persistent memory. In 20th USENIX Conference on File and Storage Technologies. 51\u201368."},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503587"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397249"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3606557.3606559"},{"key":"e_1_3_3_54_2","doi-asserted-by":"crossref","unstructured":"Yingqiang Zhang Chaoyi Ruan Cheng Li Xinjun Yang Wei Cao Feifei Li Bo Wang Jing Fang Yuhui Wang Jingze Huo et\u00a0al. 2021. Towards cost-effective and elastic cloud database deployment via memory disaggregation. Proceedings of the VLDB Endowment 14 10 (2021) 1900\u20131912.","DOI":"10.14778\/3467861.3467877"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467877"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300081"},{"key":"e_1_3_3_57_2","first-page":"15","volume-title":"2021 USENIX Annual Technical Conference","author":"Zuo Pengfei","year":"2021","unstructured":"Pengfei Zuo, Jiazhao Sun, Liu Yang, Shuangwu Zhang, and Yu Hua. 2021. One-sided RDMA-conscious extendible hashing for disaggregated memory. In 2021 USENIX Annual Technical Conference. 15\u201329."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3722112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T12:32:42Z","timestamp":1751373162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3722112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,30]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3722112"],"URL":"https:\/\/doi.org\/10.1145\/3722112","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2025,6,30]]},"assertion":[{"value":"2024-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-24","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}