{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:44:28Z","timestamp":1760060668616,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Hunan Provincial Department of Education Scientific Research Outstanding Youth Project","award":["22B0222"],"award-info":[{"award-number":["22B0222"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers"],"abstract":"<jats:p>In this paper we introduce Range Query Timestamp Counter (RQ-TSC), a general approach to provide scalable and linearizable range query operations for highly concurrent lock-based data structures. RQ-TSC is a multi-versioned building block that relies on hardware timestamps (e.g., obtained through hardware timestamp counter register on x86_64) to generate version timestamps, which greatly reduce a point of contention on a shared atomic counter. To evaluate the performance of RQ-TSC, we apply it to three data structures: a linked list, a skip list, and a binary search tree. Experiments show that our approach can improve scalability significantly. Moreover, in almost all cases, range queries on these data structures built from our design perform as well as or better than state-of-the-art concurrent data structures that support linearizable range queries.<\/jats:p>","DOI":"10.3390\/computers14090381","type":"journal-article","created":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T08:55:02Z","timestamp":1757580902000},"page":"381","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scaling Linearizable Range Queries on Modern Multi-Cores"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-3000-3261","authenticated-orcid":false,"given":"Chen","family":"Zhang","sequence":"first","affiliation":[{"name":"College of Information and Intelligence, Hunan Agricultural University, Changsha 410128, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhengming","family":"Yi","sequence":"additional","affiliation":[{"name":"College of Information and Intelligence, Hunan Agricultural University, Changsha 410128, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7150-0008","authenticated-orcid":false,"given":"Xinghui","family":"Zhu","sequence":"additional","affiliation":[{"name":"College of Information and Intelligence, Hunan Agricultural University, Changsha 410128, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,9,11]]},"reference":[{"key":"ref_1","unstructured":"Facebook (2025, September 07). RocksDB: A Persistent Key-Value Store for Fast Storage Environments. Available online: https:\/\/rocksdb.org\/."},{"key":"ref_2","unstructured":"Kejriwal, A., Gopalan, A., Gupta, A., Jia, Z., Yang, S., and Ousterhout, J. (2016, January 22\u201324). SLIK: Scalable Low-Latency Indexes for a Key-Value Store. Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC 16), Denver, CO, USA."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Raju, P., Kadekodi, R., Chidambaram, V., and Abraham, I. (2017, January 28). PebblesDB: Building Key-Value Stores Using Fragmented Log-Structured Merge Trees. Proceedings of the 26th Symposium on Operating Systems Principles, SOSP \u201917, Shanghai, China.","DOI":"10.1145\/3132747.3132765"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/3399718","article-title":"KiWi: A Key-Value Map for Scalable Real-Time Analytics","volume":"7","author":"Basin","year":"2020","journal-title":"ACM Trans. Parallel Comput."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kobus, T., Kokoci\u0144ski, M., and Wojciechowski, P.T. (2022, January 2\u20136). Jiffy: A Lock-Free Skip List with Batch Updates and Snapshots. Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP \u201922, Seoul, Republic of Korea.","DOI":"10.1145\/3503221.3508437"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Arbel-Raviv, M., and Brown, T. (2018, January 24\u201328). Harnessing Epoch-Based Reclamation for Efficient Range Queries. Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP \u201918, Vienna, Austria.","DOI":"10.1145\/3178487.3178489"},{"key":"ref_7","unstructured":"Petrank, E., and Timnat, S. (2013, January 14\u201318). Lock-Free Data-Structure Iterators. Proceedings of the 27th International Symposium on Distributed Computing-Volume 8205, DISC 2013, Jerusalem, Israel."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Chatterjee, B. (2017, January 5\u20137). Lock-Free Linearizable 1-Dimensional Range Queries. Proceedings of the 18th International Conference on Distributed Computing and Networking, ICDCN \u201917, Hyderabad, India.","DOI":"10.1145\/3007748.3007771"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Matveev, A., Shavit, N., Felber, P., and Marlier, P. (2015, January 4\u20137). Read-Log-Update: A Lightweight Synchronization Mechanism for Concurrent Programming. Proceedings of the 25th Symposium on Operating Systems Principles, SOSP \u201915, Monterey, CA, USA.","DOI":"10.1145\/2815400.2815406"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Nelson-Slivon, J., Hassan, A., and Palmieri, R. (2022, January 2\u20136). Bundling Linked Data Structures for Linearizable Range Queries. Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP \u201922, Seoul, Republic of Korea.","DOI":"10.1145\/3503221.3508412"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Wei, Y., Ben-David, N., Blelloch, G.E., Fatourou, P., Ruppert, E., and Sun, Y. (2021, January 27). Constant-Time Snapshots with Applications to Concurrent Data Structures. Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP \u201921, Virtual Event, Republic of Korea.","DOI":"10.1145\/3437801.3441602"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1145\/319996.319998","article-title":"Multiversion Concurrency Control\u2014Theory and Algorithms","volume":"8","author":"Bernstein","year":"1983","journal-title":"ACM Trans. Database Syst."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Calciu, I., Sen, S., Balakrishnan, M., and Aguilera, M.K. (2017, January 8\u201312). Black-Box Concurrent Data Structures for NUMA Architectures. Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS \u201917, Xi\u2019an, China.","DOI":"10.1145\/3037697.3037721"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1145\/2541228.2555297","article-title":"Boosting Timestamp-Based Transactional Memory by Exploiting Hardware Cycle Counters","volume":"10","author":"Ruan","year":"2013","journal-title":"ACM Trans. Archit. Code Optim."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Shavit, N., and Touitou, D. (1995, January 20\u201323). Software Transactional Memory. Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, PODC \u201995, Ottawa, ON, Canada.","DOI":"10.1145\/224964.224987"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Herlihy, M., and Moss, J.E.B. (1993, January 16\u201319). Transactional Memory: Architectural Support for Lock-Free Data Structures. Proceedings of the 20th Annual International Symposium on Computer Architecture, ISCA \u201993, San Diego, CA, USA.","DOI":"10.1145\/165123.165164"},{"key":"ref_17","unstructured":"McKenney, P.E., and Slingwine, J. (2025, September 07). Read-Copy Update: Using Execution History to Solve Concurrency Problems. Available online: http:\/\/www.rdrop.com\/~paulmck\/scalability\/paper\/rclockpdcsproof.pdf."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., and Wei, Y. (2024, January 2\u20136). VERLIB: Concurrent Versioned Pointers. Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP \u201924, Edinburgh, UK.","DOI":"10.1145\/3627535.3638501"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ben-David, N., Blelloch, G.E., and Wei, Y. (2022, January 2\u20136). Lock-free locks revisited. Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP \u201922, Seoul, Republic of Korea.","DOI":"10.1145\/3503221.3508433"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/3460874","article-title":"Lock-Free Contention Adapting Search Trees","volume":"8","author":"Winblad","year":"2021","journal-title":"ACM Trans. Parallel Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1145\/1837853.1693488","article-title":"A Practical Concurrent Binary Search Tree","volume":"45","author":"Bronson","year":"2010","journal-title":"SIGPLAN Not."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"David, T., Guerraoui, R., and Trigonakis, V. (2013, January 3\u20136). Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask. Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP \u201913, Farminton, PA, USA.","DOI":"10.1145\/2517349.2522714"},{"key":"ref_23","unstructured":"Fraser, K. (2004). Practical Lock-Freedom, University of Cambridge, Computer Laboratory. Technical Report UCAM-CL-TR-579."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","article-title":"Linearizability: A Correctness Condition for Concurrent Objects","volume":"12","author":"Herlihy","year":"1990","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Kashyap, S., Min, C., Kim, K., and Kim, T. (2018, January 23\u201326). A scalable ordering primitive for multicore machines. Proceedings of the Thirteenth EuroSys Conference, EuroSys \u201918, Porto, Portugal.","DOI":"10.1145\/3190508.3190510"},{"key":"ref_26","unstructured":"Intel (2025, August 19). Clock() or Gettimeofday() or Ippgetcpuclocks()?. Available online: https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/articles\/technical\/best-timing-function-for-measuring-ipp-api-timing.html."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Grimes, O., Nelson-Slivon, J., Hassan, A., and Palmieri, R. (2023, January 15\u201319). Opportunities and Limitations of Hardware Timestamps in Concurrent Data Structures. Proceedings of the 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS), St. Petersburg, FL, USA.","DOI":"10.1109\/IPDPS54959.2023.00068"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Dodds, M., Haas, A., and Kirsch, C.M. (2015, January 15\u201317). A Scalable, Correct Time-Stamped Stack. Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL \u201915, Mumbai, India.","DOI":"10.1145\/2676726.2676963"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Giles, E., Doshi, K., and Varman, P. (2018, January 1\u20134). Hardware transactional persistent memory. Proceedings of the International Symposium on Memory Systems, MEMSYS \u201918, Alexandria, VA, USA.","DOI":"10.1145\/3240302.3240305"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Krishnan, R.M., Kim, J., Mathew, A., Fu, X., Demeri, A., Min, C., and Kannan, S. (2020, January 16\u201320). Durable Transactional Memory Can Scale with Timestone. Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS \u201920, Lausanne, Switzerland.","DOI":"10.1145\/3373376.3378483"},{"key":"ref_31","unstructured":"Boyd-Wickizer, S., Kaashoek, M.F., Morris, R.T., and Zeldovich, N. (2025, September 07). OpLog: A Library for Scaling Update-Heavy Data Structures. Available online: https:\/\/people.csail.mit.edu\/nickolai\/papers\/boyd-wickizer-oplog-tr.pdf."},{"key":"ref_32","unstructured":"Heller, S., Herlihy, M., Luchangco, V., Moir, M., Scherer, W.N., and Shavit, N. (2005, January 12\u201314). A Lazy Concurrent List-Based Set Algorithm. Proceedings of the 9th International Conference on Principles of Distributed Systems, OPODIS\u201905, Pisa, Italy."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Prencipe, G., and Zaks, S. (2007). A Simple Optimistic Skiplist Algorithm. Structural Information and Communication Complexity, Springer.","DOI":"10.1007\/978-3-540-72951-8"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Arbel, M., and Attiya, H. (2014, January 15\u201318). Concurrent Updates with RCU: Search Tree as an Example. Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC \u201914, Paris, France.","DOI":"10.1145\/2611462.2611471"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Brown, T.A. (2015, January 21\u201323). Reclaiming Memory for Lock-Free Data Structures: There Has to Be a Better Way. Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC \u201915, Donostia-San Sebasti\u00e1n, Spain.","DOI":"10.1145\/2767386.2767436"},{"key":"ref_36","unstructured":"Radovic, Z., and Hagersten, E. (2003, January 8\u201312). Hierarchical backoff locks for nonuniform communication architectures. Proceedings of the Ninth International Symposium on High-Performance Computer Architecture, HPCA-9 2003, Anaheim, CA, USA."},{"key":"ref_37","unstructured":"Evans, J. (2025, September 07). Scalable Memory Allocation Using Jemalloc. Available online: http:\/\/www.facebook.com\/notes\/facebookengineering\/scalable-memory-allocation-using-jemalloc\/480222803919."}],"container-title":["Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-431X\/14\/9\/381\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:43:43Z","timestamp":1760035423000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-431X\/14\/9\/381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,11]]},"references-count":37,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2025,9]]}},"alternative-id":["computers14090381"],"URL":"https:\/\/doi.org\/10.3390\/computers14090381","relation":{},"ISSN":["2073-431X"],"issn-type":[{"type":"electronic","value":"2073-431X"}],"subject":[],"published":{"date-parts":[[2025,9,11]]}}}