Gria: an efficient deterministic concurrency control protocol
Xinyuan WANG1, Yun PENG2, Hejiao HUANG1()
1. School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China 2. Institute of Artificial Intelligence and Blockchain, Guangzhou University, Guangzhou 510006, China
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.
A version behind the versions read is visible (inter-group conflict) 2
(reordering)
write-after-write
Tab.2
Fig.9
Fig.10
Fig.11
Fig.12
Fig.13
Fig.14
Fig.15
1
Y, Lu X, Yu L, Cao S Madden . Aria: a fast and practical deterministic OLTP database. Proceedings of the VLDB Endowment, 2020, 13( 12): 2047–2060
2
E, Zamanian X, Yu M, Stonebraker T Kraska . Rethinking database high availability with RDMA networks. Proceedings of the VLDB Endowment, 2019, 12( 11): 1637–1650
3
A, Thomson D J Abadi . The case for determinism in database systems. Proceedings of the VLDB Endowment, 2010, 3( 1−2): 70–80
4
A, Thomson T, Diamond S C, Weng K, Ren P, Shao D J Abadi . Fast distributed transactions and strongly consistent replication for OLTP database systems. ACM Transactions on Database Systems, 2014, 39( 2): 11
5
W, Zhao L E, Moserand P M Melliar-Smith . Deterministic scheduling for multithreaded replicas. In: Proceedings of the10th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems. 2005, 74−81
6
J, Cowling B Liskov . Granola: low-overhead distributed transaction coordination. In: Proceedings of 2012 USENIX Conference on Annual Technical Conference. 2012, 21
7
A, Thomson T, Diamond S C, Weng K, Ren P Shao . Calvin: fast distributed transactions for partitioned database systems. In: Proceedings of 2012 ACM SIGMOD International Conference on Management of Data. 2012, 1−12
8
J M, Faleiro D J Abadi . Rethinking serializable multiversion concurrency control. Proceedings of the VLDB Endowment, 2015, 8( 11): 1190–1201
9
J M, Faleiro D J, Abadi J M Hellerstein . High performance transactions via early write visibility. Proceedings of the VLDB Endowment, 2017, 10( 5): 613–624
10
Y, Wu J, Arulraj J, Lin R, Xian A Pavlo . An empirical evaluation of in-memory multi-version concurrency control. Proceedings of the VLDB Endowment, 2017, 10( 7): 781–792
11
S, Tu W, Zheng E, Kohler B, Liskov S Madden . Speedy transactions in multicore in-memory databases. In: Proceedings of the 24th ACM Symposium on Operating Systems Principles. 2013, 18−32
12
X, Yu A, Pavlo D, Sanchez S Devadas . TicToc: time traveling optimistic concurrency control. In: Proceedings of 2016 International Conference on Management of Data. 2016, 1629−1642
13
S T, Leutenegger D Dias . A modeling study of the TPC-C benchmark. ACM SIGMOD Record, 1993, 22( 2): 22–31
14
B F, Cooper A, Silberstein E, Tam R, Ramakrishnan R Sears . Benchmarking cloud serving systems with YCSB. In: Proceedings of the 1st ACM Symposium on Cloud Computing. 2010, 143−154
15
D, Qin A D, Brown A Goel . Caracal: Contention management with deterministic concurrency control. In: Proceedings of the 28th ACM SIGOPS Symposium on Operating Systems Principles. 2021, 180−194
16
H, Lim M, Kaminsky D G Andersen . Cicada: dependably fast multi-core in-memory transactions. In: Proceedings of 2017 ACM International Conference on Management of Data. 2017, 21−35
17
X, Wei R, Chen H, Chen Z, Wang Z, Gong B Zang . 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
Weert P, Van M Gregoire . C++17 Standard Library Quick Reference: A Pocket Guide to Data Structures, Algorithms, and Functions. 2nd ed. Berkeley: Apress, 2019
19
J N, Gray R A, Lorie G R Putzolu . Granularity of locks in a shared data base. In: Proceedings of the 1st International Conference on Very Large Data Bases. 1975, 428−451
20
D, Lomet M F Mokbel . Locking key ranges with unbundled transaction services. Proceedings of the VLDB Endowment, 2009, 2( 1): 265–276
21
C Mohan . 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
K P, Eswaran J N, Gray R A, Lorie I L Traiger . The notions of consistency and predicate locks in a database system. Communications of the ACM, 1976, 19( 11): 624–633
23
T C, Bressoud F B Schneider . Hypervisor-based fault tolerance. ACM Transactions on Computer Systems, 1996, 14( 1): 80–107
