research-article

TicToc: Time Traveling Optimistic Concurrency Control

Authors:

Daniel Sanchez,

Srinivas DevadasAuthors Info & Claims

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

Pages 1629 - 1642

https://doi.org/10.1145/2882903.2882935

Published: 26 June 2016 Publication History

Abstract

Concurrency control for on-line transaction processing (OLTP) database management systems (DBMSs) is a nasty game. Achieving higher performance on emerging many-core systems is difficult. Previous research has shown that timestamp management is the key scalability bottleneck in concurrency control algorithms. This prevents the system from scaling to large numbers of cores. In this paper we present TicToc, a new optimistic concurrency control algorithm that avoids the scalability and concurrency bottlenecks of prior T/O schemes. TicToc relies on a novel and provably correct data-driven timestamp management protocol. Instead of assigning timestamps to transactions, this protocol assigns read and write timestamps to data items and uses them to lazily compute a valid commit timestamp for each transaction. TicToc removes the need for centralized timestamp allocation, and commits transactions that would be aborted by conventional T/O schemes. We implemented TicToc along with four other concurrency control algorithms in an in-memory, shared-everything OLTP DBMS and compared their performance on different workloads. Our results show that TicToc achieves up to 92% better throughput while reducing the abort rate by 3.3x over these previous algorithms.

References

[1]

DBx1000. https://github.com/yxymit/DBx1000.

[2]

Tile-gx family of multicore processors. http://www.tilera.com.

[3]

M. Aslett. How will the database incumbents respond to NoSQL and NewSQL? The 451 Group, April 2011.

[4]

R. Bayer, K. Elhardt, J. Heigert, and A. Reiser. Dynamic timestamp allocation for transactions in database systems. In 2nd Int. Symp. on Distributed Databases, pages 9--20, 1982.

[5]

P. A. Bernstein and N. Goodman. Concurrency control in distributed database systems. ACM Comput. Surv., 13(2):185--221, 1981.

Digital Library

[6]

P. A. Bernstein, D. Shipman, and W. Wong. Formal aspects of serializability in database concurrency control. IEEE Transactions on Software Engineering, 5(3):203--216, 1979.

Digital Library

[7]

C. Boksenbaum, M. Cart, J. Ferrié, and J.-F. Pons. Concurrent certifications by intervals of timestamps in distributed database systems. Software Engineering, IEEE Transactions on, (4):409--419, 1987.

Digital Library

[8]

M. J. Carey. Improving the performance of an optimistic concurrency control algorithm through timestamps and versions. Software Engineering, IEEE Transactions on, SE-13(6):746--751, June 1987.

Digital Library

[9]

B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with YCSB. In SoCC'10, pages 143--154.

Digital Library

[10]

W. J. Dally. GPU Computing: To Exascale and Beyond. In Supercomputing '10, Plenary Talk, 2010.

[11]

T. David, R. Guerraoui, and V. Trigonakis. Everything you always wanted to know about synchronization but were afraid to ask. In Symposium on Operating Systems Principles, pages 33--48, 2013.

Digital Library

[12]

B. D. de Dinechin, R. Ayrignac, P.-E. Beaucamps, P. Couvert, B. Ganne, P. G. de Massas, F. Jacquet, S. Jones, N. M. Chaisemartin, F. Riss, and T. Strudel. A clustered manycore processor architecture for embedded and accelerated applications. In Proc. of the High Performance Extreme Computing Conference, 2013.

[13]

K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. CACM, 19(11):624--633, 1976.

Digital Library

[14]

A. Gottlieb, R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph, and M. Snir. The NYU Ultracomputer: Designing an MIMD Shared Memory Parallel Computer. IEEE Trans. Comput., 100(2), 1983.

Digital Library

[15]

J. Gray. The transaction concept: Virtues and limitations. In VLDB, pages 144--154, 1981.

Digital Library

[16]

J. Gray, P. Sundaresan, S. Englert, K. Baclawski, and P. J. Weinberger. Quickly generating billion-record synthetic databases. SIGMOD, pages 243--252, 1994.

Digital Library

[17]

T. H\"arder. Observations on optimistic concurrency control schemes. Inf. Syst., 9(2):111--120, Nov. 1984.

Digital Library

[18]

H. Hoffmann, D. Wentzlaff, and A. Agarwal. Remote store programming. In High Performance Embedded Architectures and Compilers, pages 3--17. Springer, 2010.

Digital Library

[19]

Intel. Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3B, 17.14.1 Invariant TSC, 2015.

[20]

R. Johnson, I. Pandis, N. Hardavellas, A. Ailamaki, and B. Falsafi. Shore-MT: a scalable storage manager for the multicore era. EDBT, pages 24--35, 2009.

Digital Library

[21]

H. Kimura. Foedus: Oltp engine for a thousand cores and nvram. SIGMOD '15, pages 691--706, 2015.

Digital Library

[22]

H. T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM Trans. Database Syst., 6(2):213--226, June 1981.

Digital Library

[23]

K.-W. Lam, K.-Y. Lam, and S.-L. Hung. Real-time optimistic concurrency control protocol with dynamic adjustment of serialization order. In Real-Time Technology and Applications Symposium, pages 174--179. IEEE, 1995.

Digital Library

[24]

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

Digital Library

[25]

J. Lee and S. H. Son. Using dynamic adjustment of serialization order for real-time database systems. In Real-Time Systems Symposium, pages 66--75. IEEE, 1993.

[26]

D. A. MenascÈ and T. Nakanishi. Optimistic versus pessimistic concurrency control mechanisms in database management systems. Information Systems, 7(1):13--27, 1982.

[27]

C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, and P. Schwarz. Aries: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. TODS, 17(1):94--162, 1992.

Digital Library

[28]

I. Pandis, R. Johnson, N. Hardavellas, and A. Ailamaki. Data-oriented transaction execution. Proc. VLDB Endow., 3:928--939, September 2010.

Digital Library

[29]

D. Porobic, I. Pandis, M. Branco, P. Tzn, and A. Ailamaki. OLTP on Hardware Islands. Proc. VLDB Endow., 5:1447--1458, July 2012.

Digital Library

[30]

D. P. Reed. Naming and synchronization in a decentralized computer system. PhD thesis, Massachusetts Institute of Technology, 1978.

Digital Library

[31]

M. Reimer. Solving the phantom problem by predicative optimistic concurrency control. VLDB '83, pages 81--88, 1983.

Digital Library

[32]

M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era: (it's time for a complete rewrite). In VLDB, pages 1150--1160, 2007.

Digital Library

[33]

The Transaction Processing Council. TPC-C Benchmark (Revision 5.9.0), June 2007.

[34]

A. Thomasian. Concurrency control: Methods, performance, and analysis. ACM Comput. Surv., 30(1):70--119, Mar. 1998.

Digital Library

[35]

S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy transactions in multicore in-memory databases. In SOSP, 2013.

Digital Library

[36]

T. Wang and R. Johnson. Scalable logging through emerging non-volatile memory. Proceedings of the VLDB Endowment, 7(10):865--876, 2014.

Digital Library

[37]

X. Yu, G. Bezerra, A. Pavlo, S. Devadas, and M. Stonebraker. Staring into the abyss: An evaluation of concurrency control with one thousand cores. volume 8, pages 209--220. VLDB Endowment, 2014.

Digital Library

[38]

X. Yu and S. Devadas. TARDIS: timestamp based coherence algorithm for distributed shared memory. In International Conference on Parallel Architectures and Compilation Techniques, 2015.

Digital Library

[39]

W. Zheng, S. Tu, E. Kohler, and B. Liskov. Fast databases with fast durability and recovery through multicore parallelism. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, OSDI'14, pages 465--477. USENIX Association, 2014.

Digital Library

Cited By

Uchida MKawashima H(2024)CLMD: Making Lock Manager Predictable and Concurrent for Deterministic Concurrency ControlInternational Journal of Networking and Computing10.15803/ijnc.14.1_8114:1(81-92)Online publication date: 2024
https://doi.org/10.15803/ijnc.14.1_81
Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Doki KHoshino TKawashima H(2024)WoundDie: Concurrency Control Protocol with Lightweight Priority ControlProceedings of the 15th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/3678015.3680480(130-135)Online publication date: 4-Sep-2024
https://dl.acm.org/doi/10.1145/3678015.3680480
Show More Cited By

Index Terms

TicToc: Time Traveling Optimistic Concurrency Control
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database transaction processing
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Concurrency control

Recommendations

Decentralization of Two Phase Locking based Protocols
HPDC '22: Proceedings of the 31st International Symposium on High-Performance Parallel and Distributed Computing

Bamboo is a state-of-the-art concurrency control protocol based on the 2-phase locking protocol. One problem of Bamboo is that it requires transactions to fetch timestamps from a single centralized atomic counter. To replace the concentrated access to ...
Semantics-based concurrency control: beyond commutativity

The concurrency of transactions executing on atomic data types can be enhanced through the use of semantic information about operations defined on these types. Hitherto, commutativity of operations has been exploited to provide enchanced concurrency ...
Implementing Distributed Read-Only Transactions

This paper presents an efficient scheme for eliminating conflicts between distributed read-only transactions and distributed update transactions, thereby reducing synchronization delays. The scheme makes use of a multiversion mechanism in order to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

June 2016

2300 pages

ISBN:9781450335317

DOI:10.1145/2882903

General Chairs:
Fatma Özcan
IBM Research, USA
,
Georgia Koutrika
HP Labs, USA
,
Program Chair:
Sam Madden
Massachusetts Institute of Technology, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Intel Science and Technology Center at MIT
Intel Science and Technology Center at MIT.

Conference

SIGMOD/PODS'16

Sponsor:

SIGMOD

SIGMOD/PODS'16: International Conference on Management of Data

June 26 - July 1, 2016

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

111
Total Citations
View Citations
1,290
Total Downloads

Downloads (Last 12 months)146
Downloads (Last 6 weeks)4

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Uchida MKawashima H(2024)CLMD: Making Lock Manager Predictable and Concurrent for Deterministic Concurrency ControlInternational Journal of Networking and Computing10.15803/ijnc.14.1_8114:1(81-92)Online publication date: 2024
https://doi.org/10.15803/ijnc.14.1_81
Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Doki KHoshino TKawashima H(2024)WoundDie: Concurrency Control Protocol with Lightweight Priority ControlProceedings of the 15th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/3678015.3680480(130-135)Online publication date: 4-Sep-2024
https://dl.acm.org/doi/10.1145/3678015.3680480
Blelloch GWei YLee IChabbi MSteuwer M(2024)VERLIB: Concurrent Versioned PointersProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638501(200-214)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638501
Ramalhete PCorreia ALee IChabbi MSteuwer M(2024)Scaling Up Transactions with Slower ClocksProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638472(2-16)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638472
Cui ZDou WGao YWang DSong JZheng YWang TYang RXu KHu YWei JHuang TRoychoudhury APaiva AAbreu RStorey M(2024)Understanding Transaction Bugs in Database SystemsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639207(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639207
Xian DWei X(2024)SC-Chef: Turboboosting Smart Contract Concurrent Execution for High Contention Workloads via Chopping TransactionsIEEE Transactions on Reliability10.1109/TR.2023.329627873:1(216-229)Online publication date: Mar-2024
https://doi.org/10.1109/TR.2023.3296278
Pan JLi G(2024)Fast and Scalable Ridesharing SearchIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.341843336:11(6159-6170)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2024.3418433
Miyazaki YHoshino TKawashima H(2024)Optimizing Aria Concurrency Control Protocol with Early Dependency Resolution2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00062(242-249)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00062
Baccaert TKetsman B(2024)Cascade: Optimal Transaction Scheduling for High-Contention Workloads2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00452(5634-5638)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00452
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents