Gria: an efficient deterministic concurrency control protocol

Abstract

Deterministic databases are able to reduce coordination costs in a replication. This property has fostered a significant interest in the design of efficient deterministic concurrency control protocols. However, the state-of-the-art deterministic concurrency control protocol Aria has three issues. First, it is impractical to configure a suitable batch size when the read-write set is unknown. Second, Aria running in low-concurrency scenarios, e.g., a single-thread scenario, suffers from the same conflicts as running in high-concurrency scenarios. Third, the single-version schema brings write-after-write conflicts.

To address these issues, we propose Gria, an efficient deterministic concurrency control protocol. Gria has the following properties. First, the batch size of Gria is auto-scaling. Second, Gria’s conflict probability in low-concurrency scenarios is lower than that in high-concurrency scenarios. Third, Gria has no write-after-write conflicts by adopting a multi-version structure. To further reduce conflicts, we propose two optimizations: a reordering mechanism as well as a rechecking strategy. The evaluation result on two popular benchmarks shows that Gria outperforms Aria by 13x.

Graphical abstract

Keywords

deterministic concurrency control / transaction processing

Xinyuan Wang currently is a PhD candidate at the School of Computer Science, Harbin Institute of Technology, China. His research interests include concurrent data structures, and multi-core and distributed transaction processing in databases

Yun Peng currently is a professor of the Institute of Artificial Intelligence and Blockchain at Guangzhou University, China. He received his PhD from Hong Kong Baptist University, China in 2013. His research interests include graph computing and concurrency control theory. He has published tens of papers in top-tier conferences and journals, including SIGMOD, VLDB, ICDE, IJCAI, TKDE, and TSC, etc. He serves as the program committee member of IJCAI and the editor of International Journal of Intelligent Systems (IJIS). He is the reviewer of TKDE, ICDE, and SIGMOD, etc

Hejiao Huang received her PhD in computer science from City University of Hong Kong, China in 2004. She is currently a professor in Harbin Institute of Technology, China, and previously was an invited professor at INRIA, France. Her research interests include cloud computing, trustworthy computing, and distributed system design

References

[1] Lu Y, Yu X, Cao L, Madden S. Aria: a fast and practical deterministic OLTP database. Proceedings of the VLDB Endowment, 2020, 13( 12): 2047–2060

[2] Zamanian E, Yu X, Stonebraker M, Kraska T. Rethinking database high availability with RDMA networks. Proceedings of the VLDB Endowment, 2019, 12( 11): 1637–1650

[3] Thomson A, Abadi D J. The case for determinism in database systems. Proceedings of the VLDB Endowment, 2010, 3( 1−2): 70–80

[4] Thomson A, Diamond T, Weng S C, Ren K, Shao P, Abadi D J. Fast distributed transactions and strongly consistent replication for OLTP database systems. ACM Transactions on Database Systems, 2014, 39( 2): 11

[5] Zhao W, Moserand L E, Melliar-Smith P M. Deterministic scheduling for multithreaded replicas. In: Proceedings of the10th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems. 2005, 74−81

[6] Cowling J, Liskov B. Granola: low-overhead distributed transaction coordination. In: Proceedings of 2012 USENIX Conference on Annual Technical Conference. 2012, 21

[7] Thomson A, Diamond T, Weng S C, Ren K, Shao P. Calvin: fast distributed transactions for partitioned database systems. In: Proceedings of 2012 ACM SIGMOD International Conference on Management of Data. 2012, 1−12

[8] Faleiro J M, Abadi D J. Rethinking serializable multiversion concurrency control. Proceedings of the VLDB Endowment, 2015, 8( 11): 1190–1201

[9] Faleiro J M, Abadi D J, Hellerstein J M. High performance transactions via early write visibility. Proceedings of the VLDB Endowment, 2017, 10( 5): 613–624

[10] Wu Y, Arulraj J, Lin J, Xian R, Pavlo A. An empirical evaluation of in-memory multi-version concurrency control. Proceedings of the VLDB Endowment, 2017, 10( 7): 781–792

[11] Tu S, Zheng W, Kohler E, Liskov B, Madden S. Speedy transactions in multicore in-memory databases. In: Proceedings of the 24th ACM Symposium on Operating Systems Principles. 2013, 18−32

[12] Yu X, Pavlo A, Sanchez D, Devadas S. TicToc: time traveling optimistic concurrency control. In: Proceedings of 2016 International Conference on Management of Data. 2016, 1629−1642

[13] Leutenegger S T, Dias D. A modeling study of the TPC-C benchmark. ACM SIGMOD Record, 1993, 22( 2): 22–31

[14] Cooper B F, Silberstein A, Tam E, Ramakrishnan R, Sears R. Benchmarking cloud serving systems with YCSB. In: Proceedings of the 1st ACM Symposium on Cloud Computing. 2010, 143−154

[15] Qin D, Brown A D, Goel A. Caracal: Contention management with deterministic concurrency control. In: Proceedings of the 28th ACM SIGOPS Symposium on Operating Systems Principles. 2021, 180−194

[16] Lim H, Kaminsky M, Andersen D G. Cicada: dependably fast multi-core in-memory transactions. In: Proceedings of 2017 ACM International Conference on Management of Data. 2017, 21−35

[17] Wei X, Chen R, Chen H, Wang Z, Gong Z, Zang B. Unifying timestamp with transaction ordering for MVCC with decentralized scalar timestamp. In: Proceedings of the 18th USENIX Symposium on Networked Systems Design and Implementation. 2021, 357−372

[18] Van Weert P, Gregoire M. C++17 Standard Library Quick Reference: A Pocket Guide to Data Structures, Algorithms, and Functions. 2nd ed. Berkeley: Apress, 2019

[19] Gray J N, Lorie R A, Putzolu G R. Granularity of locks in a shared data base. In: Proceedings of the 1st International Conference on Very Large Data Bases. 1975, 428−451

[20] Lomet D, Mokbel M F. Locking key ranges with unbundled transaction services. Proceedings of the VLDB Endowment, 2009, 2( 1): 265–276

[21] Mohan C. ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes. In: Proceedings of the 16th International Conference on Very Large Databases. 1990, 392−405

[22] Eswaran K P, Gray J N, Lorie R A, Traiger I L. The notions of consistency and predicate locks in a database system. Communications of the ACM, 1976, 19( 11): 624–633

[23] Bressoud T C, Schneider F B. Hypervisor-based fault tolerance. ACM Transactions on Computer Systems, 1996, 14( 1): 80–107

Acknowledgements

This work was supported by the Key Laboratory Ministry of Industry and Information Technology of China, Shenzhen Science and Technology Program (Nos. GXWD20220817124827001 and JCYJ20210324132406016), the National Natural Science Foundation of China (Grant No. 61732022), and the National Science Foundation of Guangdong Province (No. 2023A1515030273).

RIGHTS & PERMISSIONS

2024 Higher Education Press