BishtRef
Articles Journals Publishers Authors Subjects Most Cited New Papers Year Stats Open Access
journal article Dec 04, 2025

Brook-2PL: Tolerating High Contention Workloads with A Deadlock-Free Two-Phase Locking Protocol

Farzad Habibi ORCID Juncheng Fang ORCID Tania Lorido-Botran ORCID Faisal Nawab ORCID
Proceedings of the ACM on Management of Data Vol. 3 No. 6 pp. 1-27 · Association for Computing Machinery (ACM)
View at Publisher Save 10.1145/3769767
Abstract
The problem of hotspots remains a critical challenge in high-contention workloads for concurrency control (CC) protocols. Traditional concurrency control approaches encounter significant difficulties under high contention, resulting in excessive transaction aborts and deadlocks. In this paper, we propose
Brook-2PL
, a novel two-phase locking (2PL) protocol that (1) introduces
SLW-Graph
for deadlock-free transaction execution, and (2) proposes
partial transaction chopping
for early lock release. Previous methods suffer from transaction aborts that lead to wasted work and can further burden the system due to their cascading effects. Brook-2PL addresses this limitation by statically analyzing a new graph-based dependency structure called
SLW-Graph
, enabling deadlock-free two-phase locking through predetermined lock acquisition.
Brook-2PL
also reduces contention by enabling early lock release using partial transaction chopping and static transaction analysis. We overcome the inherent limitations of traditional transaction chopping by providing a more flexible chopping method. Evaluation using both our synthetic online game store workload and the TPC-C benchmark shows that
Brook-2PL
significantly outperforms state-of-the-art CC protocols.
Brook-2PL
achieves an average speed-up of (2.86x) while reducing tail latency (p95) by (48%) in the TPC-C benchmark.
Topics

No keywords indexed for this article. Browse by subject →

References
68
[4]
Jason Baker, Chris Bond, James C Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. 2011. Megastore: Providing scalable, highly available storage for interactive services.. In CIDR, Vol. 11. 223-234.
[6]
Philip A Bernstein Vassos Hadzilacos Nathan Goodman et al. 1987. Concurrency control and recovery in database systems. Vol. 370. Addison-wesley Reading.
[8]
Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, et al., 2013. {TAO}:{Facebook's} distributed data store for the social graph. In 2013 USENIX Annual Technical Conference (USENIX ATC 13). 49-60.
[13]
James Cowling and Barbara Liskov. 2012. Granola:{Low-Overhead} distributed transaction coordination. In 2012 USENIX Annual Technical Conference (USENIX ATC 12). 223-235.
[18]
Tamer Eldeeb and Philip A Bernstein. 2016. Transactions for Distributed Actors in the Cloud. Transactions for Distributed Actors in the Cloud (2016).
[19]
Jose M Faleiro and Daniel J Abadi. 2014. Rethinking serializable multiversion concurrency control. arXiv preprint arXiv:1412.2324 (2014).
[25]
Farzad Habibi. 2024. PhD Forum: Towards Metastable-Failure-Free Distributed Transaction Systems. In 2024 43rd International Symposium on Reliable Distributed Systems (SRDS). IEEE, 318-321.
[27]
Lexiang Huang, Matthew Magnusson, Abishek Bangalore Muralikrishna, Salman Estyak, Rebecca Isaacs, Abutalib Aghayev, Timothy Zhu, and Aleksey Charapko. 2022. Metastable Failures in the Wild. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 73-90.
[28]
Dean Jacobs and Stefan Aulbach. 2007. Ruminations on multi-tenant databases. (2007).
[30]
Kate Keahey, Jason Anderson, Zhuo Zhen, Pierre Riteau, Paul Ruth, Dan Stanzione, Mert Cevik, Jacob Colleran, Haryadi S. Gunawi, Cody Hammock, Joe Mambretti, Alexander Barnes, François Halbach, Alex Rocha, and Joe Stubbs. 2020. Lessons Learned from the Chameleon Testbed. In Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC '20). USENIX Association.
[31]
Ankur Khetrapal and Vinay Ganesh. 2006. HBase and Hypertable for large scale distributed storage systems. Dept. of Computer Science, Purdue University, Vol. 10, 1376616.1376726 (2006).
[32]
Hideaki Kimura, Goetz Graefe, and Harumi A Kuno. 2012. Efficient locking techniques for databases on modern hardware.. In ADMS@ VLDB. Citeseer, 1-12.
[34]
Avinash Lakshman and Prashant Malik. 2010. Cassandra: a decentralized structured storage system. ACM SIGOPS operating systems review, Vol. 44, 2 (2010), 35-40.
[35]
Per-Åke Larson, Spyros Blanas, Cristian Diaconu, Craig Freedman, Jignesh M Patel, and Mike Zwilling. 2011. High-performance concurrency control mechanisms for main-memory databases. arXiv preprint arXiv:1201.0228 (2011).
[38]
Haonan Lu, Siddhartha Sen, and Wyatt Lloyd. 2020a. {Performance-Optimal}{Read-Only} Transactions. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 333-349.
[39]
Yi Lu Xiangyao Yu Lei Cao and Samuel Madden. 2020b. Aria: a fast and practical deterministic OLTP database. (2020). 10.14778/3407790.3407808
[42]
Neha Narula, Cody Cutler, Eddie Kohler, and Robert Morris. 2014. Phase Reconciliation for Contended {In-Memory} Transactions. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14). 511-524.
[43]
Are Database System Researchers Making Correct Assumptions about Transaction Workloads?

Cuong D. T. Nguyen, Kevin Chen, Christopher DeCarolis et al.

Proceedings of the ACM on Management of Data 10.1145/3725268
[44]
Oracle. [n.d.]. ConcurrentHashMap (Java SE 11 and JDK 11). https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/ConcurrentHashMap.html. Accessed April 4, 2025.
[45]
Hexiang Pan, Shaofeng Cai, Tien Tuan Anh Dinh, Yuncheng Wu, Yeow Meng Chee, Gang Chen, and Beng Chin Ooi. 2025. CCaaLF: Concurrency Control as a Learnable Function. arXiv preprint arXiv:2503.10036 (2025).

Showing 50 of 68 references

Metrics
0
Citations
68
References
Details
Published
Dec 04, 2025
Vol/Issue
3(6)
Pages
1-27
Authors
F
Farzad Habibi

University of California, Irvine, Irvine, CA, USA

J
Juncheng Fang

University of California, Irvine, Irvine, CA, USA

T
Tania Lorido-Botran

Roblox, San Jose, USA and Northeastern University, Boston, USA

F
Faisal Nawab

University of California, Irvine, Irvine, CA, USA

Funding
NSF Award: 2321121, CNS1815212, SaTC-2245372
Roblox Award: Gift
Cite This Article
Farzad Habibi, Juncheng Fang, Tania Lorido-Botran, et al. (2025). Brook-2PL: Tolerating High Contention Workloads with A Deadlock-Free Two-Phase Locking Protocol. Proceedings of the ACM on Management of Data, 3(6), 1-27. https://doi.org/10.1145/3769767
Related

You May Also Like

A Universal Question-Answering Platform for Knowledge Graphs

Reham Omar, Ishika Dhall · 2023

43 citations

FactorJoin: A New Cardinality Estimation Framework for Join Queries

Ziniu Wu, Parimarjan Negi · 2023

39 citations

RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search

Jianyang Gao, Cheng Long · 2024

39 citations

ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data

Liana Patel, Peter Kraft · 2024

37 citations

Efficient Sampling Approaches to Shapley Value Approximation

Jiayao Zhang, Qiheng Sun · 2023

34 citations