research-article

Public Access

Deferred Runtime Pipelining for contentious multicore software transactions

Authors:

Sebastian Angel,

Dennis ShashaAuthors Info & Claims

EuroSys '19: Proceedings of the Fourteenth EuroSys Conference 2019

Article No.: 40, Pages 1 - 16

https://doi.org/10.1145/3302424.3303966

Published: 25 March 2019 Publication History

Abstract

DRP is a new concurrency control protocol for software transactional memory that achieves high throughput, even for skewed workloads that exhibit high contention. DRP builds on prior works that chop transactions into pieces to expose more concurrency opportunities, but unlike these works, DRP performs no static analyses and supports arbitrary workloads. DRP achieves a high degree of concurrency across most workloads and guarantees deadlock freedom, strict serializability, and opacity. We incorporate DRP into the software transactional objects library STO [18] and find that DRP improves STO's throughput on several STAMP benchmarks by up to 3.6x. Additionally, an in-memory multicore database implemented with our modified variant of STO outperforms databases that use OCC or transaction chopping for concurrency control. Specifically, DRP achieves 6.6x higher throughput than OCC when contention is high. Compared to transaction chopping, our DRP achieves 3.3x higher throughput when contention is medium or low. Furthermore, our implementation achieves comparable performance to OCC and transaction chopping at other contention levels.

References

[1]

TL2-X86. https://github.com/nathanielherman/sto-stamp/tree/master/tl2, Mar. 2016.

[2]

Silo: Multicore in-memory storage engine (for STO). https://github.com/nathanielherman/silo/tree/8a63b, Apr. 2017.

[3]

Software transactional objects. https://github.com/nathanielherman/sto/tree/fd80932, Jan. 2018.

[4]

A.-R. Adl-Tabatabai, B. T. Lewis, V. Menon, B. R. Murphy, B. Saha, and T. Shpeisman. Compiler and runtime support for efficient software transactional memory. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2006.

Digital Library

[5]

R. Appuswamy, A. C. Anadiotis, D. Porobic, M. K. Iman, and A. Ailamaki. Analyzing the impact of system architecture on the scalability of oltp engines for high-contention workloads. In Proceedings of the International Conference on Very Large Data Bases (VLDB), Aug. 2018.

[6]

E. D. Berger, T. Yang, T. Liu, D. Krishnan, and G. Novark. Grace: Safe and efficient concurrent programming. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), Dec. 2008.

[7]

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

Digital Library

[8]

C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In Proceedings of the IEEE International Symposium on Workload Characterization, Sept. 2008.

[9]

A. Cheung, S. Madden, and A. Solar-Lezama. Sloth: Being lazy is a virtue (when issuing database queries). In Proceedings of the ACM International Conference on Management of Data (SIGMOD), June 2014.

Digital Library

[10]

J. Cowling and B. Liskov. Granola: low-overhead distributed transaction coordination. In Proceedings of the USENIX Annual Technical Conference (ATC), June 2012.

Digital Library

[11]

D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In Proceedings of the International Symposium on Distributed Computing (DISC), Sept. 2006.

Digital Library

[12]

J. M. Faleiro, D. J. Abadi, and J. M. Hellerstein. High performance transactions via early write visibility. In Proceedings of the International Conference on Very Large Data Bases (VLDB), Sept. 2017.

Digital Library

[13]

J. M. Faleiro, A. Thomson, and D. J. Abadi. Lazy evaluation of transactions in database systems. In Proceedings of the ACM International Conference on Management of Data (SIGMOD), June 2014.

Digital Library

[14]

R. Guerraoui and M. Kapałtka. On the correctness of transactional memory. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), Feb. 2008.

Digital Library

[15]

T. Harris and K. Fraser. Language support for lightweight transactions. In Proceedings of the ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), Oct. 2003.

Digital Library

[16]

M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), Feb. 2008.

Digital Library

[17]

M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software transactional memory for dynamic-sized data structures. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), July 2003.

Digital Library

[18]

N. Herman, J. P. Inala, Y. Huang, L. Tsai, E. Kohler, B. Liskov, and L. Shrira. Type-aware transactions for faster concurrent code. In Proceedings of the ACM European Conference on Computer Systems (EuroSys), Apr. 2016.

Digital Library

[19]

H. T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM Transactions on Database Systems, 6(2), June 1981.

Digital Library

[20]

H. Lim, M. Kaminsky, and D. G. Andersen. Cicada: Dependably fast multicore in-memory transactions. In Proceedings of the ACM International Conference on Management of Data (SIGMOD), May 2017.

Digital Library

[21]

S. Mu, S. Angel, and D. Shasha. Deferred runtime pipelining for contentious multicore software transactions (extended version). Technical report, University of Pennsylvania, Feb. 2019.

Digital Library

[22]

N. Narula, C. Cutler, E. Kohler, and R. Morris. Phase reconciliation for contended in-memory transactions. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), Oct. 2014.

Digital Library

[23]

C. H. Papadimitriou. The serializability of concurrent database updates. Journal of the ACM (JACM), 26(4), Oct. 1979.

Digital Library

[24]

D. E. Porter, O. S. Hofmann, C. J. Rossbach, A. Benn, and E. Witchel. Operating system transactions. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP), Oct. 2009.

Digital Library

[25]

T. M. Qadah and M. Sadoghi. Quecc: A queue-oriented, control-free concurrency architecture. In Proceedings of the ACM/IFIP International Middleware Conference, Dec. 2018.

Digital Library

[26]

H. E. Ramadan, I. Roy, M. Herlihy, and E. Witchel. Committing conflicting transactions in an STM. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), Feb. 2009.

Digital Library

[27]

K. Ren, A. Thomson, and D. J. Abadi. An evaluation of the advantages and disadvantages of deterministic database systems. In Proceedings of the International Conference on Very Large Data Bases (VLDB), Sept. 2014.

Digital Library

[28]

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

Digital Library

[29]

N. Shavit and D. Touitou. Software transactional memory. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Aug. 1995.

Digital Library

[30]

A. Spiegelman, G. Golan-Gueta, and I. Keidar. Transactional data structure libraries. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2016.

Digital Library

[31]

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 Proceedings of the International Conference on Very Large Data Bases (VLDB), Sept. 2007.

Digital Library

[32]

The Transaction Processing Council. TPC-C benchmark (revision 5.9.0). http://www.tpc.org/tpcc/, June 2007.

[33]

A. Thomson and D. J. Abadi. The case for determinism in database systems. In Proceedings of the International Conference on Very Large Data Bases (VLDB), Sept. 2010.

Digital Library

[34]

A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, and D. J. Abadi. Calvin: Fast distributed transactions for partitioned database systems. In Proceedings of the ACM International Conference on Management of Data (SIGMOD), May 2012.

Digital Library

[35]

S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy transactions in multicore in-memory databases. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP), Nov. 2013.

Digital Library

[36]

T. Wang and H. Kimura. Mostly-optimistic concurrency control for highly contended dynamic workloads on a thousand cores. In Proceedings of the International Conference on Very Large Data Bases (VLDB), Sept. 2017.

[37]

Z. Wang, S. Mu, Y. Cui, H. Yi, H. Chen, and J. Li. Scaling multicore databases via constrained parallel execution. In Proceedings of the ACM International Conference on Management of Data (SIGMOD), June 2016.

Digital Library

[38]

C. Xie, C. Su, C. Littley, L. Alvisi, M. Kapritsos, and Y. Wang. High-performance ACID via modular concurrency control. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP), Oct. 2015.

Digital Library

[39]

X. Yu, G. Bezerra, A. Pavlo, S. Devadas, and M. Stonebraker. Staring into the abyss: An evaluation of concurrency control with one thousand cores. In Proceedings of the International Conference on Very Large Data Bases (VLDB), Aug. 2014.

Digital Library

[40]

X. Yu, A. Pavlo, D. Sanchez, and S. Devadas. Tictoc: Time traveling optimistic concurrency control. In Proceedings of the ACM International Conference on Management of Data (SIGMOD), June 2016.

Digital Library

[41]

D. Zhang and D. Dechev. Lockfree transactions without rollbacks for linked data structures. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), July 2016.

Digital Library

[42]

I. Zhang, N. Lebeck, P. Fonseca, B. Holt, R. Cheng, A. Norberg, A. Krishnamurthy, and H. M. Levy. Diamond: Automating data management and storage for wide-area, reactive applications. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), Oct. 2016.

Digital Library

[43]

W. Zheng, S. Tu, E. Kohler, and B. Liskov. Fast databases with fault durability and recovery through multicore parallelism. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), Oct. 2014.

Digital Library

Cited By

Wei JGu YLi TQi JLi CZhang YJensen CYu G(2024)LTPG: Large-Batch Transaction Processing on GPUs with Deterministic Concurrency Control2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00296(3865-3877)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00296
Zhu BHua YLong ZLiu X(2023)CATS: A Computation-Aware Transaction Processing System with Proactive Unlocking2023 IEEE/ACM 31st International Symposium on Quality of Service (IWQoS)10.1109/IWQoS57198.2023.10188780(1-10)Online publication date: 19-Jun-2023
https://doi.org/10.1109/IWQoS57198.2023.10188780
Chen YYu XKoutris PArpaci-Dusseau AArpaci-Dusseau RShu JIves ZBonifati AEl Abbadi A(2022)Plor: General Transactions with Predictable, Low Tail LatencyProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517879(19-33)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517879
Show More Cited By

Deferred Runtime Pipelining for contentious multicore software transactions
1. Information systems
  1. Data management systems
    1. Database management system engines

Recommendations

Fast software transactions
Invalidating transactions: optimizations, theory, guarantees, and unification
Opportunities for optimism in contended main-memory multicore transactions
Abstract
Main-memory multicore transactional systems have achieved excellent performance using single-version optimistic concurrency control (OCC), especially on uncontended workloads. Nevertheless, systems based on other concurrency control protocols, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '19: Proceedings of the Fourteenth EuroSys Conference 2019

March 2019

714 pages

ISBN:9781450362818

DOI:10.1145/3302424

Copyright © 2019 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 the author(s) 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

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

EuroSys '19

Sponsor:

SIGOPS

EuroSys '19: Fourteenth EuroSys Conference 2019

March 25 - 28, 2019

Dresden, Germany

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
754
Total Downloads

Downloads (Last 12 months)197
Downloads (Last 6 weeks)9

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wei JGu YLi TQi JLi CZhang YJensen CYu G(2024)LTPG: Large-Batch Transaction Processing on GPUs with Deterministic Concurrency Control2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00296(3865-3877)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00296
Zhu BHua YLong ZLiu X(2023)CATS: A Computation-Aware Transaction Processing System with Proactive Unlocking2023 IEEE/ACM 31st International Symposium on Quality of Service (IWQoS)10.1109/IWQoS57198.2023.10188780(1-10)Online publication date: 19-Jun-2023
https://doi.org/10.1109/IWQoS57198.2023.10188780
Chen YYu XKoutris PArpaci-Dusseau AArpaci-Dusseau RShu JIves ZBonifati AEl Abbadi A(2022)Plor: General Transactions with Predictable, Low Tail LatencyProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517879(19-33)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517879
Shen WKhanna AAngel SSen SMu SBromberg YKermarrec AKozyrakis C(2022)RolisProceedings of the Seventeenth European Conference on Computer Systems10.1145/3492321.3519561(69-84)Online publication date: 28-Mar-2022
https://dl.acm.org/doi/10.1145/3492321.3519561
Huang YQian WKohler ELiskov BShrira L(2022)Opportunities for optimism in contended main-memory multicore transactionsThe VLDB Journal10.1007/s00778-021-00719-931:6(1239-1261)Online publication date: 11-Jan-2022
https://doi.org/10.1007/s00778-021-00719-9
Guo ZWu KYan CYu XLi GLi ZIdreos SSrivastava D(2021)Releasing Locks As Early As You Can: Reducing Contention of Hotspots by Violating Two-Phase LockingProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457294(658-670)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457294
Zhang HCardoza AChen PAngel SLiu VLu SHowell J(2020)Fault-tolerant and transactional stateful serverless workflowsProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488833(1187-1204)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488833
Lepers BBalmau OGupta KZwaenepoel WLu SHowell J(2020)KVell+Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488790(425-441)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488790
Huang YQian WKohler ELiskov BShrira L(2020)Opportunities for optimism in contended main-memory multicore transactionsProceedings of the VLDB Endowment10.14778/3377369.337737313:5(629-642)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.14778/3377369.3377373
Peterson CWilson APirkelbauer PDechev D(2020)Optimized Transactional Data Structure Approach to Concurrency Control for In-Memory Databases2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)10.1109/SBAC-PAD49847.2020.00025(107-115)Online publication date: Sep-2020
https://doi.org/10.1109/SBAC-PAD49847.2020.00025
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten