{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T17:03:40Z","timestamp":1757610220290,"version":"3.44.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:p>This paper proposes Oze, a concurrency control protocol that handles heterogeneous workloads, including long-running update transactions. Oze explores a large scheduling space using a multi-version serialization graph to reduce false positives. Oze manages the graph in a decentralized manner to exploit many cores in modern servers. We further propose an OLTP benchmark, BoMB (Bill of Materials Benchmark), based on a use case in an actual manufacturing company. BoMB consists of one long-running update transaction and five short transactions that conflict with each other. Experiments using BoMB show that Oze can handle the long-running update transaction while achieving four orders of magnitude higher throughput than state-of-the-art optimistic and multi-version protocols and up to five times higher throughput than pessimistic protocols. We also show Oze performs comparably with existing techniques even in a typical OLTP workload, TPC-C, thanks to a protocol switching mechanism.<\/jats:p>","DOI":"10.14778\/3742728.3742730","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T13:32:53Z","timestamp":1756906373000},"page":"2321-2333","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Oze: Decentralized Graph-Based Concurrency Control for Long-Running Update Transactions"],"prefix":"10.14778","volume":"18","author":[{"given":"Jun","family":"Nemoto","sequence":"first","affiliation":[{"name":"Scalar, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takashi","family":"Kambayashi","sequence":"additional","affiliation":[{"name":"Nautilus Technologies, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takashi","family":"Hoshino","sequence":"additional","affiliation":[{"name":"Cybozu Labs, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hideyuki","family":"Kawashima","sequence":"additional","affiliation":[{"name":"Keio University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","author":"Andersen Institute of Bread & Life Co., Ltd.","year":"2024","unstructured":"Andersen Institute of Bread & Life Co., Ltd. 2024. Andersen Group. Retrieved May 15, 2025 from https:\/\/www.andersen-group.jp\/english\/"},{"key":"e_1_2_1_2_1","first-page":"2","article-title":"A Critique of ANSI SQL Isolation Levels","volume":"24","author":"Berenson Hal","year":"1995","unstructured":"Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil, and Patrick O'Neil. 1995. A Critique of ANSI SQL Isolation Levels. SIGMOD Rec. 24, 2 (May 1995), 1\u201310.","journal-title":"SIGMOD Rec."},{"key":"e_1_2_1_3_1","first-page":"2","article-title":"Concurrency Control in Distributed Database Systems","volume":"13","author":"Bernstein Philip A.","year":"1981","unstructured":"Philip A. Bernstein and Nathan Goodman. 1981. Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13, 2 (June 1981), 185\u2013221.","journal-title":"ACM Comput. Surv."},{"key":"e_1_2_1_4_1","first-page":"4","article-title":"Multiversion Concurrency Control\u2014Theory and Algorithms","volume":"8","author":"Bernstein Philip A.","year":"1983","unstructured":"Philip A. Bernstein and Nathan Goodman. 1983. Multiversion Concurrency Control\u2014Theory and Algorithms. ACM Trans. Database Syst. 8, 4 (Dec. 1983), 465\u2013483.","journal-title":"ACM Trans. Database Syst."},{"volume-title":"Benchmarking transaction and analytical processing systems","author":"Bog Anja","key":"e_1_2_1_5_1","unstructured":"Anja Bog. 2014. Benchmarking transaction and analytical processing systems. Springer."},{"key":"e_1_2_1_6_1","first-page":"4","article-title":"Concurrent Certifications by Intervals of Timestamps in Distributed Database Systems","volume":"13","author":"Boksenbaum C.","year":"1987","unstructured":"C. Boksenbaum, M. Cart, J. Ferri\u00e9, and J.-F. Pons. 1987. Concurrent Certifications by Intervals of Timestamps in Distributed Database Systems. IEEE Trans. Softw. Eng. 13, 4 (April 1987), 409\u2013419.","journal-title":"IEEE Trans. Softw. Eng."},{"key":"e_1_2_1_7_1","volume-title":"General purpose schedulers for database systems. Acta informatica 14, 3","author":"Casanova Marco A","year":"1980","unstructured":"Marco A Casanova and Philip A Bernstein. 1980. General purpose schedulers for database systems. Acta informatica 14, 3 (1980), 195\u2013220."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 1st ACM Symposium on Cloud Computing (SoCC '10)","author":"Cooper Brian F.","year":"2010","unstructured":"Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing (SoCC '10). 143\u2013154."},{"key":"e_1_2_1_9_1","article-title":"Spanner: Google's Globally Distributed Database","volume":"31","author":"Corbett James C.","year":"2013","unstructured":"James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. 2013. Spanner: Google's Globally Distributed Database. ACM Trans. Comput. Syst. 31, 3, Article 8 (Aug. 2013), 22 pages.","journal-title":"ACM Trans. Comput. Syst."},{"key":"e_1_2_1_10_1","volume-title":"Retrieved","author":"Transaction Processing Performance Council","year":"2010","unstructured":"Transaction Processing Performance Council. 2010. TPC Benchmark C - Standard Specification Revision 5.11. Retrieved May 15, 2025 from https:\/\/www.tpc.org\/tpcc\/"},{"key":"e_1_2_1_11_1","volume-title":"Retrieved","author":"Transaction Processing Performance Council","year":"2015","unstructured":"Transaction Processing Performance Council. 2015. TPC Benchmark E-Standard Specification Version 1.14.0. Retrieved May 15, 2025 from https:\/\/www.tpc.org\/tpce\/"},{"key":"e_1_2_1_12_1","first-page":"4","article-title":"OLTP-Bench: An Extensible Testbed for Benchmarking Relational Databases","volume":"7","author":"Difallah Djellel Eddine","year":"2013","unstructured":"Djellel Eddine Difallah, Andrew Pavlo, Carlo Curino, and Philippe Cudre-Mauroux. 2013. OLTP-Bench: An Extensible Testbed for Benchmarking Relational Databases. Proc. VLDB Endow. 7, 4 (Dec. 2013), 277\u2013288.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE '19)","author":"Durner Dominik","year":"2019","unstructured":"Dominik Durner and Thomas Neumann. 2019. No False Negatives: Accepting All Useful Schedules in a Fast Serializable Many-Core System. In Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE '19). 734\u2013745."},{"key":"e_1_2_1_14_1","first-page":"11","article-title":"Ocean Vista: Gossip-Based Visibility Control for Speedy Geo-Distributed Transactions","volume":"12","author":"Fan Hua","year":"2019","unstructured":"Hua Fan and Wojciech Golab. 2019. Ocean Vista: Gossip-Based Visibility Control for Speedy Geo-Distributed Transactions. Proc. VLDB Endow. 12, 11 (July 2019), 1471\u20131484.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2021 International Conference on Management of Data (SIGMOD\/PODS '21)","author":"Guo Zhihan","year":"2021","unstructured":"Zhihan Guo, Kan Wu, Cong Yan, and Xiangyao Yu. 2021. Releasing Locks As Early As You Can: Reducing Contention of Hotspots by Violating Two-Phase Locking. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD\/PODS '21). 658\u2013670."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '88)","author":"Hadzilacos Thanasis","year":"1988","unstructured":"Thanasis Hadzilacos. 1988. Serialization Graph Algorithms for Multiversion Concurrency Control. In Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '88). 135\u2013141."},{"volume-title":"Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS '85)","author":"Hadzilacos Thanasis","key":"e_1_2_1_17_1","unstructured":"Thanasis Hadzilacos and Christos H. Papadimitriou. 1985. Algorithmic Aspects of Multiversion Concurrency Control. In Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS '85). 96\u2013104."},{"key":"e_1_2_1_18_1","first-page":"3","article-title":"Linearizability: A Correctness Condition for Concurrent Objects","volume":"12","author":"Herlihy Maurice P.","year":"1990","unstructured":"Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst. 12, 3 (July 1990), 463\u2013492.","journal-title":"ACM Trans. Program. Lang. Syst."},{"volume-title":"Precision Locks. In Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data (SIGMOD '81)","author":"Jordan J. R.","key":"e_1_2_1_19_1","unstructured":"J. R. Jordan, J. Banerjee, and R. B. Batman. 1981. Precision Locks. In Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data (SIGMOD '81). 143\u2013147."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE '22)","author":"Kang Guoxin","year":"2022","unstructured":"Guoxin Kang, Lei Wang, Wanling Gao, Fei Tang, and Jianfeng Zhan. 2022. OLxP-Bench: Real-time, Semantically Consistent, and Domain-specific are Essential in Benchmarking, Designing, and Implementing HTAP Systems. In Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE '22). 1822\u20131834."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16)","author":"Kim Kangnyeon","year":"2016","unstructured":"Kangnyeon Kim, Tianzheng Wang, Ryan Johnson, and Ippokratis Pandis. 2016. ERMIA: Fast Memory-Optimized Database System for Heterogeneous Workloads. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16). 1675\u20131687."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 4th International Workshop on Parallel and Distributed Real-Time Systems. 122\u2013125","author":"Lam Kwok-Wa","year":"1996","unstructured":"Kwok-Wa Lam, V.C.S. Lee, Kam-Yiu Lam, and Sheung-Lun Hung. 1996. Distributed real-time optimistic concurrency control protocol. In Proceedings of the 4th International Workshop on Parallel and Distributed Real-Time Systems. 122\u2013125."},{"volume-title":"Proceedings of the 14th IEEE Real-Time Systems Symposium (RTSS '93)","author":"Lee J.","key":"e_1_2_1_23_1","unstructured":"J. Lee and S.H. Son. 1993. Using dynamic adjustment of serialization order for real-time database systems. In Proceedings of the 14th IEEE Real-Time Systems Symposium (RTSS '93). 66\u201375."},{"volume-title":"Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD '17)","author":"Lim Hyeontaek","key":"e_1_2_1_24_1","unstructured":"Hyeontaek Lim, Michael Kaminsky, and David G. Andersen. 2017. Cicada: Dependably Fast Multi-Core In-Memory Transactions. In Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD '17). 21\u201335."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 19th International Conference on Very Large Data Bases (VLDB '93)","author":"Lomet David B.","year":"1993","unstructured":"David B. Lomet. 1993. Key Range Locking Strategies for Improved Concurrency. In Proceedings of the 19th International Conference on Very Large Data Bases (VLDB '93). 655\u2013664."},{"key":"e_1_2_1_26_1","first-page":"12","article-title":"Aria: A Fast and Practical Deterministic OLTP Database","volume":"13","author":"Lu Yi","year":"2020","unstructured":"Yi Lu, Xiangyao Yu, Lei Cao, and Samuel Madden. 2020. Aria: A Fast and Practical Deterministic OLTP Database. Proc. VLDB Endow. 13, 12 (July 2020), 2047\u20132060.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 17th IEEE International Enterprise Distributed Object Computing Conference (EDOC '13)","author":"M\u00fcller Stephan","year":"2013","unstructured":"Stephan M\u00fcller, Lars Butzmann, Kai H\u00f6welmeyer, Stefan Klauck, and Hasso Plattner. 2013. Efficient View Maintenance for Enterprise Applications in Columnar In-Memory Databases. In Proceedings of the 17th IEEE International Enterprise Distributed Object Computing Conference (EDOC '13). 249\u2013258."},{"key":"e_1_2_1_28_1","volume-title":"Retrieved","author":"Nemoto Jun","year":"2024","unstructured":"Jun Nemoto. 2024. BoMB on CCBench. Retrieved May 15, 2025 from https:\/\/github.com\/jnmt\/ccbench\/tree\/vldb-paper"},{"key":"e_1_2_1_29_1","volume-title":"Oze: Decentralized Graph-based Concurrency Control for Long-running Update Transactions (Extended Version). Retrieved","author":"Nemoto Jun","year":"2024","unstructured":"Jun Nemoto, Takashi Kambayashi, Takashi Hoshino, and Hideyuki Kawashima. 2024. Oze: Decentralized Graph-based Concurrency Control for Long-running Update Transactions (Extended Version). Retrieved December 1, 2024 from https:\/\/arxiv.org\/abs\/2210.04179"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data","author":"Neumann Thomas","year":"2015","unstructured":"Thomas Neumann, Tobias M\u00fchlbauer, and Alfons Kemper. 2015. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australia) (SIGMOD '15). 677\u2013689."},{"key":"e_1_2_1_31_1","volume-title":"Retrieved","author":"Cloud Newman","year":"2022","unstructured":"Newman Cloud, Inc. 2022. OpenBOM - User Stories. Retrieved May 15, 2025 from https:\/\/www.openbom.com\/user-stories"},{"volume-title":"Proceedings of the 4th IEEE International Conference on Data Engineering (ICDE '88)","author":"Orji C.U.","key":"e_1_2_1_32_1","unstructured":"C.U. Orji, L. Lilien, and J. Hyziak. 1988. A performance analysis of an optimistic and a basic timestamp-ordering concurrency control algorithms for centralized database systems. In Proceedings of the 4th IEEE International Conference on Data Engineering (ICDE '88). 64\u201371."},{"key":"e_1_2_1_33_1","first-page":"2","article-title":"System Level Concurrency Control for Distributed Database Systems","volume":"3","author":"Rosenkrantz Daniel J.","year":"1978","unstructured":"Daniel J. Rosenkrantz, Richard E. Stearns, and Philip M. Lewis. 1978. System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3, 2 (June 1978), 178\u2013198.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_2_1_34_1","first-page":"1","article-title":"Altruistic Locking","volume":"19","author":"Salem Kenneth","year":"1994","unstructured":"Kenneth Salem, H\u00e9ctor Garc\u00eda-Molina, and Jeannie Shands. 1994. Altruistic Locking. ACM Trans. Database Syst. 19, 1 (March 1994), 117\u2013165.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_2_1_35_1","first-page":"3","article-title":"Transaction chopping: algorithms and performance studies","volume":"20","author":"Shasha Dennis","year":"1995","unstructured":"Dennis Shasha, Francois Llirbat, Eric Simon, and Patrick Valduriez. 1995. Transaction chopping: algorithms and performance studies. ACM Trans. Database Syst. 20, 3 (Sept. 1995), 325\u2013363.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_2_1_36_1","first-page":"13","article-title":"An Analysis of Concurrency Control Protocols for In-Memory Databases with CCBench","volume":"13","author":"Tanabe Takayuki","year":"2020","unstructured":"Takayuki Tanabe, Takashi Hoshino, Hideyuki Kawashima, and Osamu Tatebe. 2020. An Analysis of Concurrency Control Protocols for In-Memory Databases with CCBench. Proc. VLDB Endow. 13, 13 (Sept. 2020), 3531\u20133544.","journal-title":"Proc. VLDB Endow."},{"volume-title":"Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12)","author":"Thomson Alexander","key":"e_1_2_1_37_1","unstructured":"Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J. Abadi. 2012. Calvin: Fast Distributed Transactions for Partitioned Database Systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). 1\u201312."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13)","author":"Tu Stephen","year":"2013","unstructured":"Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. 2013. Speedy Transactions in Multicore In-Memory Databases. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13). 18\u201332."},{"key":"e_1_2_1_39_1","first-page":"4","article-title":"Efficiently Making (Almost) Any Concurrency Control Mechanism Serializable","volume":"26","author":"Wang Tianzheng","year":"2017","unstructured":"Tianzheng Wang, Ryan Johnson, Alan Fekete, and Ippokratis Pandis. 2017. Efficiently Making (Almost) Any Concurrency Control Mechanism Serializable. The VLDB Journal 26, 4 (Aug. 2017), 537\u2013562.","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_40_1","first-page":"2","article-title":"Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores","volume":"10","author":"Wang Tianzheng","year":"2016","unstructured":"Tianzheng Wang and Hideaki Kimura. 2016. Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores. Proc. VLDB Endow. 10, 2 (Oct. 2016), 49\u201360.","journal-title":"Proc. VLDB Endow."},{"volume-title":"Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery","author":"Weikum Gerhard","key":"e_1_2_1_41_1","unstructured":"Gerhard Weikum and Gottfried Vossen. 2001. Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Elsevier."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 2010 Second International Conference on Computer Research and Development (ICCRD '10)","author":"Younus Muhammad","year":"2010","unstructured":"Muhammad Younus, Tao Jian, and Fan Yuqing. 2010. Module-Based Parts Management System Using Single Source of Product Data. In Proceedings of the 2010 Second International Conference on Computer Research and Development (ICCRD '10). 151\u2013155."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16)","author":"Yu Xiangyao","year":"2016","unstructured":"Xiangyao Yu, Andrew Pavlo, Daniel Sanchez, and Srinivas Devadas. 2016. TicToc: Time Traveling Optimistic Concurrency Control. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16). 1629\u20131642."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3742728.3742730","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T13:37:55Z","timestamp":1756906675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3742728.3742730"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4]]},"references-count":43,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["10.14778\/3742728.3742730"],"URL":"https:\/\/doi.org\/10.14778\/3742728.3742730","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,4]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}