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

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

RIGHTS & PERMISSIONS

Higher Education Press