TicToc: Time Traveling Optimistic Concurrency Control
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 a...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115329 https://orcid.org/0000-0003-4317-3457 https://orcid.org/0000-0001-8253-7714 |
| _version_ | 1811094610577981440 |
|---|---|
| author | Yu, Xiangyao Pavlo, Andrew Sanchez, Daniel Devadas, Srinivas |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Yu, Xiangyao Pavlo, Andrew Sanchez, Daniel Devadas, Srinivas |
| author_sort | Yu, Xiangyao |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:02:51Z |
| format | Article |
| id | mit-1721.1/115329 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:02:51Z |
| publishDate | 2018 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1153292022-10-02T05:59:43Z TicToc: Time Traveling Optimistic Concurrency Control Yu, Xiangyao Pavlo, Andrew Sanchez, Daniel Devadas, Srinivas Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Yu, Xiangyao Sanchez, Daniel Devadas, Srinivas 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. Intel Science and Technology Center for Big Data National Science Foundation (U.S.) (CCF-1438955) National Science Foundation (U.S.) (CCF-1438967) 2018-05-11T17:24:26Z 2018-05-11T17:24:26Z 2016-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-3531-7 http://hdl.handle.net/1721.1/115329 Yu, Xiangyao, Andrew Pavlo, Daniel Sanchez, and Srinivas Devadas. “TicToc: Time Traveling Optimistic Concurrency Control.” Proceedings of the 2016 International Conference on Management of Data - SIGMOD ’16 (2016), 26 June - 1 July, 2016, San Francisco, California, Association for Computing Machinery, 2016. https://orcid.org/0000-0003-4317-3457 https://orcid.org/0000-0001-8253-7714 en_US http://dx.doi.org/10.1145/2882903.2882935 Proceedings of the 2016 International Conference on Management of Data - SIGMOD '16 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT Web Domain |
| spellingShingle | Yu, Xiangyao Pavlo, Andrew Sanchez, Daniel Devadas, Srinivas TicToc: Time Traveling Optimistic Concurrency Control |
| title | TicToc: Time Traveling Optimistic Concurrency Control |
| title_full | TicToc: Time Traveling Optimistic Concurrency Control |
| title_fullStr | TicToc: Time Traveling Optimistic Concurrency Control |
| title_full_unstemmed | TicToc: Time Traveling Optimistic Concurrency Control |
| title_short | TicToc: Time Traveling Optimistic Concurrency Control |
| title_sort | tictoc time traveling optimistic concurrency control |
| url | http://hdl.handle.net/1721.1/115329 https://orcid.org/0000-0003-4317-3457 https://orcid.org/0000-0001-8253-7714 |
| work_keys_str_mv | AT yuxiangyao tictoctimetravelingoptimisticconcurrencycontrol AT pavloandrew tictoctimetravelingoptimisticconcurrencycontrol AT sanchezdaniel tictoctimetravelingoptimisticconcurrencycontrol AT devadassrinivas tictoctimetravelingoptimisticconcurrencycontrol |