{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:32Z","timestamp":1781326712932,"version":"3.54.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"content-version":"vor","delay-in-days":1,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2504470,2212580"],"award-info":[{"award-number":["2504470,2212580"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>Concurrency-control (CC) mechanisms are essential for ensuring consistency in large-scale key-value stores, but traditional approaches face significant challenges. Mechanisms like 2PL and OCC incur high CPU overheads. Timestamp-based mechanisms are faster but require storing timestamps for every key, resulting in substantial space overhead and numerous I\/O operations in disk-based systems. We address these challenges by decomposing timestamp-based CC schemes into two components: a timestamp storage system and a CC protocol. We then show that the timestamp storage system can approximate timestamps for keys not used by ongoing transactions, substantially reducing memory requirements and I\/O while maintaining correctness for various protocols (STO, MVTO, and TicToc). We introduce FPSketch, an approximate timestamp storage system, and our evaluation with SplinterDB shows that FPSketch outperforms 2PL and OCC by up to 14\u00d7 on some workloads and disk-based CC systems by up to 5.9\u00d7. Remarkably, FPSketch with just 32KiB of memory yields performance comparable to an idealized in-memory implementations in our evaluation. FPSketch makes timestamp-based concurrency control mechanisms practical for disk-based key-value stores.<\/jats:p>","DOI":"10.1145\/3769793","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Focus! Fast On-disk Concurrency-control Using Sketches"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-3568-8322","authenticated-orcid":false,"given":"Deukyeon","family":"Hwang","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4890-7413","authenticated-orcid":false,"given":"Alex","family":"Conway","sequence":"additional","affiliation":[{"name":"Cornell Tech, New York City, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9595-3861","authenticated-orcid":false,"given":"Carlos","family":"Garcia Alvarado","sequence":"additional","affiliation":[{"name":"CruxOCM, Santa Rosa, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1517-8842","authenticated-orcid":false,"given":"Jun","family":"Yuan","sequence":"additional","affiliation":[{"name":"Datadog, New York City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0863-2470","authenticated-orcid":false,"given":"Naama","family":"Ben-David","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0784-7410","authenticated-orcid":false,"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[{"name":"VMware Research by Broadcom, Palo Alto, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4708-9479","authenticated-orcid":false,"given":"Adriana","family":"Szekeres","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Sattam Alsubaiee Yasser Altowim Hotham Altwaijry Alexander Behm Vinayak Borkar Yingyi Bu Michael Carey Inci Cetindil Madhusudan Cheelangi Khurram Faraaz et al. 2014. AsterixDB: A scalable open source BDMS. arXiv preprint arXiv:1407.0454 (2014).","DOI":"10.14778\/2733085.2733096"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Berk Atikoglu Yuehai Xu Eitan Frachtenberg Song Jiang and Mike Paleczny. 2012. Workload Analysis of a Large-scale Key-value Store. In SIGMETRICS.","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_2_1_3_1","volume-title":"An Introduction to Betrees and Write-Optimization. USENIX ;login","author":"Bender Michael A.","year":"2015","unstructured":"Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Yang Zhan. 2015. An Introduction to Betrees and Write-Optimization. USENIX ;login: (2015)."},{"key":"e_1_2_1_4_1","unstructured":"Philip A Bernstein Vassos Hadzilacos Nathan Goodman et al. 1987. Concurrency control and recovery in database systems. Vol. 370. Addison-Wesley Reading."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364328"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644201"},{"key":"e_1_2_1_7_1","volume-title":"18th USENIX Conference on File and Storage Technologies, FAST 2020","author":"Cao Zhichao","year":"2020","unstructured":"Zhichao Cao, Siying Dong, Sagar Vemuri, and David H. C. Du. 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In 18th USENIX Conference on File and Storage Technologies, FAST 2020, Santa Clara, CA, USA, February 24-27, 2020, Sam H. Noh and Brent Welch (Eds.). USENIX Association, 209-223. https:\/\/www.usenix.org\/conference\/fast20\/presentation\/cao-zhichao"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517879"},{"key":"e_1_2_1_9_1","volume-title":"LMDB: The Lightning Memory-Mapped Database Manager","author":"Chu Howard","year":"2015","unstructured":"Howard Chu. 2015. LMDB: The Lightning Memory-Mapped Database Manager. http:\/\/www.lmdb.tech\/doc\/"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588726"},{"key":"e_1_2_1_11_1","first-page":"49","volume-title":"SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores. In 2020 USENIX Annual Technical Conference (USENIX ATC 20)","author":"Conway Alexander","year":"2020","unstructured":"Alexander Conway, Abhishek Gupta, Vijay Chidambaram, Martin Farach-Colton, Richard Spillane, Amy Tai, and Rob Johnson. 2020. SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). 49-63."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_13_1","unstructured":"Couchbase Inc. 2010. Couchbase. https:\/\/www.couchbase.com."},{"key":"e_1_2_1_14_1","first-page":"11","article-title":"TPC Benchmark C Standard Specification","volume":"5","author":"Transaction Processing Performance Council","year":"2010","unstructured":"Transaction Processing Performance Council. 2010. TPC Benchmark C Standard Specification. Technical Report TPC-C Rev. 5.11.0. Transaction Processing Performance Council. https:\/\/www.tpc.org\/tpc_documents_current_versions\/pdf\/tpc-c_v5.11.0.pdf","journal-title":"Technical Report TPC-C Rev."},{"key":"e_1_2_1_15_1","first-page":"1","volume-title":"The Design and Operation of CloudLab. In 2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Duplyakin Dmitry","year":"2019","unstructured":"Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. 2019. The Design and Operation of CloudLab. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). USENIX Association, Renton, WA, 1-14. https:\/\/www.usenix.org\/conference\/atc19\/presentation\/duplyakin"},{"key":"e_1_2_1_16_1","first-page":"343","volume-title":"Chardonnay: Fast and General Datacenter Transactions for On-Disk Databases. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23)","author":"Eldeeb Tamer","year":"2023","unstructured":"Tamer Eldeeb, Xincheng Xie, Philip A. Bernstein, Asaf Cidon, and Junfeng Yang. 2023. Chardonnay: Fast and General Datacenter Transactions for On-Disk Databases. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA, 343-360. https:\/\/www.usenix.org\/conference\/osdi23\/presentation\/eldeeb"},{"key":"e_1_2_1_17_1","unstructured":"Facebook Inc. 2013. RocksDB. https:\/\/github.com\/facebook\/rocksdb."},{"key":"e_1_2_1_18_1","unstructured":"Apache Software Foundation. 2019. Apache Cassandra. http:\/\/cassandra.apache.org."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551832"},{"key":"e_1_2_1_20_1","volume-title":"Encyclopedia of Big Data Technologies","author":"Friedrich Steffen","unstructured":"Steffen Friedrich and Norbert Ritter. 2019. YCSB. In Encyclopedia of Big Data Technologies. Springer."},{"key":"e_1_2_1_21_1","unstructured":"Google Inc. 2019. LevelDB. https:\/\/github.com\/google\/leveldb."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457294"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682012"},{"key":"e_1_2_1_24_1","unstructured":"Cary Huang. 2024. A Deeper Look Inside PostgreSQL Visibility Check Mechanism. https:\/\/www.highgo.ca\/2024\/04\/19\/a-deeper-look-inside-postgresql-visibility-check-mechanism\/"},{"key":"e_1_2_1_25_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms. https:\/\/api.semanticscholar.org\/CorpusID:7469433","author":"Iacono John","year":"2012","unstructured":"John Iacono and Mihai Patrascu. 2012. Using hashing to solve the dictionary problem. In ACM-SIAM Symposium on Discrete Algorithms. https:\/\/api.semanticscholar.org\/CorpusID:7469433"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3625549.3658682"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389134"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/3011026"},{"key":"e_1_2_1_29_1","unstructured":"MongoDB. 2020. The database for modern applications. https:\/\/www.mongodb.com\/."},{"key":"e_1_2_1_30_1","volume-title":"Berkeley DB. In USENIX Annual Technical Conference, FREENIX Track. 183-191","author":"Olson Michael A","year":"1999","unstructured":"Michael A Olson, Keith Bostic, and Margo I Seltzer. 1999. Berkeley DB. In USENIX Annual Technical Conference, FREENIX Track. 183-191."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588727"},{"key":"e_1_2_1_33_1","volume-title":"PostgreSQL Source Code: src\/backend\/access\/transam\/slru.c. Source Code Repository. https:\/\/github.com\/postgres\/postgres\/blob\/master\/src\/backend\/access\/transam\/slru.c Accessed on","author":"SQL.","year":"2025","unstructured":"PostgreSQL. 2025. PostgreSQL Source Code: src\/backend\/access\/transam\/slru.c. Source Code Repository. https:\/\/github.com\/postgres\/postgres\/blob\/master\/src\/backend\/access\/transam\/slru.c Accessed on July 15, 2025."},{"key":"e_1_2_1_34_1","first-page":"765","volume-title":"Massively Parallel Multi-Versioned Transaction Processing. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24)","author":"Qian Shujian","year":"2024","unstructured":"Shujian Qian and Ashvin Goel. 2024. Massively Parallel Multi-Versioned Transaction Processing. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). USENIX Association, Santa Clara, CA, 765-781. https:\/\/www.usenix.org\/conference\/osdi24\/presentation\/qian"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3572848.3577433"},{"key":"e_1_2_1_36_1","unstructured":"Redis. 2022. Redis. https:\/\/redis.io\/"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/357353.357355"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882958"},{"key":"e_1_2_1_39_1","unstructured":"Karl Rupp. 2018. 42 years of microrocessor trend data. https:\/\/www.karlrupp.net\/2018\/02\/42-years-of-microprocessor-trend-data\/."},{"key":"e_1_2_1_40_1","first-page":"67","volume-title":"Evaluating the Power of Flexible Packet Processing for Network Resource Allocation. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17)","author":"Sharma Naveen Kr.","year":"2017","unstructured":"Naveen Kr. Sharma, Antoine Kaufmann, Thomas Anderson, Arvind Krishnamurthy, Jacob Nelson, and Simon Peter. 2017. Evaluating the Power of Flexible Packet Processing for Network Resource Allocation. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17). USENIX Association, Boston, MA, 67-82. https:\/\/www.usenix.org\/conference\/nsdi17\/technical-sessions\/presentation\/sharma"},{"key":"e_1_2_1_41_1","unstructured":"Jeff Shute Radek Vingralek Bart Samwel Ben Handy Chad Whipkey Eric Rollins Mircea Oancea Kyle Littlefield David Menestrina Stephan Ellner John Cieslewicz Ian Rae Traian Stancescu and Himani Apte. 2013. F1: A Distributed SQL Database That Scales. In VLDB."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3226595.3226638"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018","author":"Tang Dixin","year":"2018","unstructured":"Dixin Tang and Aaron J. Elmore. 2018. Toward Coordination-free and Reconfigurable Mixed Concurrency Control. In Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018, Boston, MA, USA, July 11-13, 2018, Haryadi S. Gunawi and Benjamin C. Reed (Eds.). USENIX Association, 809-822. https:\/\/www.usenix.org\/conference\/atc18\/presentation\/tang"},{"key":"e_1_2_1_44_1","unstructured":"Les Tokar. 2023. Crucial T700 PCIe 5 SSD Review - 12.4GB\/s Throughput with over 1.6 Million IOPS. https:\/\/www.thessdreview.com\/our-reviews\/nvme\/crucial-t700-pcie-5-ssd-review\/3\/."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522713"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056101"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13960-9_7"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13960-9_7"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067427"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588724"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882935"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769793","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769793","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:45:30Z","timestamp":1781325930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769793"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":51,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769793"],"URL":"https:\/\/doi.org\/10.1145\/3769793","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}