AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Article Link
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

Optimistic Transaction Processing in Deterministic Database

Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai 200240, China
Show Author Information

Abstract

Deterministic databases can improve the performance of distributed workload by eliminating the distributed commit protocol and reducing the contention cost. Unfortunately, the current deterministic scheme does not consider the performance scalability within a single machine. In this paper, we describe a scalable deterministic concurrency control, Deterministic and Optimistic Concurrency Control (DOCC), which is able to scale the performance both within a single node and across multiple nodes. The performance improvement comes from enforcing the determinism lazily and avoiding read-only transaction blocking the execution. The evaluation shows that DOCC achieves 8x performance improvement than the popular deterministic database system, Calvin.

Electronic Supplementary Material

Download File(s)
jcst-35-2-382-Highlights.pdf (234.8 KB)

References

[1]
Thomson A, Diamond T, Weng S C, Ren K, Shao P, Abadi D J. Calvin: Fast distributed transactions for partitioned database systems. In Proc. the 2012 ACM SIGMOD International Conference on Management of Data, May 2012, pp.1-12.
[2]

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

[3]
Faleiro J M, Thomson A, Abadi D J. Lazy evaluation of transactions in database systems. In Proc. the 2014 ACM SIGMOD International Conference on Management of Data, June 2014, pp.15-26.
[4]

Ren K, Thomson A, Abadi D J. Lightweight locking for main memory database systems. Proceedings of the VLDB Endowment, 2012, 6(2): 145-156.

[5]

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

[6]
Fraser K. Practical lock-freedom. Technical Report, University of Cambridge, 2004. https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf, June 2019.
[7]
Tu S, Zheng W, Kohler E, Liskov B, Madden S. Speedy transactions in multicore in-memory databases. In Proc. the 24th ACM SIGOPS Symposium on Operating Systems Principles, November 2013, pp.18-32.
[8]

Hart T E, McKenney P E, Brown A D, Walpole J. Performance of memory reclamation for lockless synchronization. Journal of Parallel and Distributed Computing, 2007, 67(12): 1270-1285.

[9]
Arcangeli A, Cao M, McKenney P E, Sarma D. Using read-copy-update techniques for system V IPC in the Linux 2.5 kernel. In Proc. the 2003 USENIX Annual Technical Conference, June 2003, pp.297-309.
[10]
McKenney P E, Slingwine J D. Read-copy update: Using execution history to solve concurrency problems. In Proc. the 15th ISCA International Conference on Parallel and Distributed Computing and Systems, September 2002, pp.509-518.
[11]
Chen Y, Wei X, Shi J, Chen R, Chen H. Fast and general distributed transactions using RDMA and HTM. In Proc. the 11th European Conference on Computer Systems, April 2016, Article No. 26.
[12]
Stonebraker M, Madden S, Abadi D J, Harizopoulos S, Hachem N, Helland P. The end of an architectural era: (It’s time for a complete rewrite). In Proc. the 33rd International Conference on Very Large Data Bases, September 2007, pp.1150-1160.
[13]
Kimura H. FOEDUS: OLTP engine for a thousand cores and NVRAM. In Proc. the 2015 ACM SIGMOD International Conference on Management of Data, May 2015, pp.691-706.
[14]
Kalia A, Kaminsky M, Andersen D. G. FaSST: Fast, scalable and simple distributed transactions with two-sided (RDMA) datagram RPCs. In Proc. the 12th USENIX Symposium on Operating Systems Design and Implementation, November 2016, pp.185-201.
[15]
Wei X, Dong Z, Chen R, Chen H. Deconstructing RDMA-enabled distributed transactions: Hybrid is better! In Proc. the 13th USENIX Symposium on Operating Systems Design and Implementation, October 2018, pp.233-251.
[16]

Kung H T, Robinson J T. On optimistic methods for concurrency control. ACM Transactions on Database Systems, 1981, 6(2): 213-226.

[17]

Adya A, Gruber R, Liskov B, Maheshwari U. Efficient optimistic concurrency control using loosely synchronized clocks. ACM SIGMOD Record, 1995, 24(2): 23-34.

[18]
Liskov B, Castro M, Shrira L, Adya A. Providing persistent objects in distributed systems. In Proc. the 13th European Conference on Object-Oriented Programming, June 1999, pp.230-257.
[19]

Yuan Y, Wang K, Lee R, Ding X, Xing J, Blanas S, Zhang X. BCC: Reducing false aborts in optimistic concurrency control with low cost for in-memory databases. Proceedings of the VLDB Endowment, 2016, 9(6): 504-515.

[20]

Wang T, Kimura H. Mostly-optimistic concurrency control for highly contended dynamic workloads on a thousand cores. Proceedings of the VLDB Endowment, 2016, 10(2): 49-60.

[21]
Yu X, Pavlo A, Sánchez D, Devadas S. TicToc: Time traveling optimistic concurrency control. In Proc. the 2016 ACM SIGMOD International Conference on Management of Data, June 2016, pp.1629-1642.
[22]
Weikum G, Vossen G. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (1st edition). Morgan Kaufmann, 2001.
[23]

Agrawal D, Sengupta S. Modular synchronization in distributed, multiversion databases: Version control and concurrency control. IEEE Transactions on Knowledge and Data Engineering, 1993, 5(1): 126-137.

[24]
Bernstein P A, Hadzilacos V, Goodman N. Concurrency Control and Recovery in Database Systems (1st edition). Addison-Wesley, 1987.
[25]
Mohan C, Pirahesh H, Lorie R. Efficient and flexible methods for transient versioning of records to avoid locking by read-only transactions. In Proc. the 1992 ACM SIGMOD International Conference on Management of Data, June 1992, pp.124-133.
[26]

Färber F, Cha S K, Primsch J, Bornhövd C, Sigg S, Lehner W. SAP HANA database: Data management for modern business applications. ACM SIGMOD Record, 2012, 40(4): 45-51.

[27]
Diaconu C, Freedman C, Ismert E, Larson P Å, Mittal P, Stonecipher R, Verma N, Zwilling M. Hekaton: SQL server’s memory-optimized OLTP engine. In Proc. the 2013 ACM SIGMOD International Conference on Management of Data, June 2013, pp.1243-1254.
[28]
Levandoski J, Lomet D, Sengupta S, Stutsman R, Wang R. High performance transactions in deuteronomy. In Proc. the 7th Biennial Conference on Innovative Data Systems Research, January 2015, Article No. 44.
[29]
Neumann T, Mühlbauer T, Kemper A. Fast serializable multi-version concurrency control for main-memory database systems. In Proc. the 2015 ACM SIGMOD International Conference on Management of Data, May 2015, pp.677-689.
[30]

Larson P Å, Blanas S, Diaconu C, Freedman C, Patel J M, Zwilling M. High-performance concurrency control mechanisms for main-memory databases. Proceedings of the VLDB Endowment, 2011, 5(4): 298-309.

[31]
Li J, Michael E, Ports D R. Eris: Coordination-free consistent transactions using in-network concurrency control. In Proc. the 26th Symposium on Operating Systems Principles, October 2017, pp.104-120.
[32]
Wang Z, Qian H, Li J, Chen H. Using restricted transactional memory to build a scalable in-memory database. In Proc. the 9th European Conference on Computer Systems, April 2014, Article No. 26.
[33]
Wei X, Shi J, Chen Y, Chen R, Chen H. Fast in-memory transaction processing using RDMA and HTM. In Proc. the 25th Symposium on Operating Systems Principles, October 2015, pp.87-104.
[34]

Chen H, Chen R, Wei X, Shi J, Chen Y, Wang Z, Zang B, Guan H. Fast in-memory transaction processing using RDMA and HTM. ACM Transactions on Computer Systems, 2017, 35(1): Article No. 3.

[35]

Kallman R, Kimura H, Natkins J et al. H-store: A high performance, distributed main memory transaction processing system. Proceedings of the VLDB Endowment, 2008, 1(2): 1496-1499.

[36]

Stonebraker M, Weisberg A. The voltDB main memory DBMs. IEEE Data Eng. Bull., 2013, 36(2): 21-27.

[37]
Cowling J, Liskov B. Granola: Low-overhead distributed transaction coordination. In Proc. the 2012 USENIX Annual Technical Conference, June 2012, pp.223-235.
[38]

Bernstein P A, Shipman D W. The correctness of concurrency control mechanisms in a system for distributed databases (SDD-1). ACM Transactions on Database Systems, 1980, 5(1): 52-68.

[39]

Bernstein A J, Gerstl D S, Lewis P M. Concurrency control for step-decomposed transactions. Information Systems, 1999, 24(8): 673-698.

[40]

Shasha D, Llirbat F, Simon E, Valduriez P. Transaction chopping: Algorithms and performance studies. ACM Transactions on Database Systems, 1995, 20(3): 325-363.

[41]
Zhang Y, Power R, Zhou S, Sovran Y, Aguilera M K, Li J. Transaction chains: Achieving serializability with low latency in geo-distributed storage systems. In Proc. the 24th ACM SIGOPS Symposium on Operating Systems Principles, November 2013, pp.276-291.
[42]
Mu S, Cui Y, Zhang Y, Lloyd W, Li J. Extracting more concurrency from distributed transactions. In Proc. the 11th USENIX Symposium on Operating Systems Design and Implementation, October 2014, pp.479-494.
[43]
Xie C, Su C, Littley C, Alvisi L, Kapritsos M, Wang Y. High-performance ACID via modular concurrency control. In Proc. the 25th Symposium on Operating Systems Principles, October 2015, pp.279-294.
[44]
Wang Z, Mu S, Cui Y, Yi H, Chen H, Li J. Scaling multicore databases via constrained parallel execution. In Proc. the 2016 ACM SIGMOD International Conference on Management of Data, June 2016, pp.1643-1658.
[45]

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.

Journal of Computer Science and Technology
Pages 382-394
Cite this article:
Dong Z-Y, Tang C-Z, Wang J-C, et al. Optimistic Transaction Processing in Deterministic Database. Journal of Computer Science and Technology, 2020, 35(2): 382-394. https://doi.org/10.1007/s11390-020-9700-5

433

Views

9

Crossref

N/A

Web of Science

10

Scopus

1

CSCD

Altmetrics

Received: 08 May 2019
Revised: 02 September 2019
Published: 27 March 2020
©Institute of Computing Technology, Chinese Academy of Sciences 2020
Return