Document Open Access Logo

The FIDS Theorems: Tensions Between Multinode and Multicore Performance in Transactional Systems

Authors Naama Ben-David, Gal Sela , Adriana Szekeres

PDF
Thumbnail PDF

File

LIPIcs.DISC.2023.9.pdf
  • Filesize: 0.79 MB
  • 24 pages

Document Identifiers

Author Details

Naama Ben-David
  • VMware Research, Palo Alto, California, USA
Gal Sela
  • Technion, Haifa, Israel
Adriana Szekeres
  • VMware Research, Bellevue, Washington, USA

Cite As Get BibTex

Naama Ben-David, Gal Sela, and Adriana Szekeres. The FIDS Theorems: Tensions Between Multinode and Multicore Performance in Transactional Systems. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.9

Abstract

Traditionally, distributed and parallel transactional systems have been studied in isolation, as they targeted different applications and experienced different bottlenecks. However, modern high-bandwidth networks have made the study of systems that are both distributed (i.e., employ multiple nodes) and parallel (i.e., employ multiple cores per node) necessary to truly make use of the available hardware. 
In this paper, we study the performance of these combined systems and show that there are inherent tradeoffs between a system’s ability to have fast and robust distributed communication and its ability to scale to multiple cores. More precisely, we formalize the notions of a fast deciding path of communication to commit transactions quickly in good executions, and seamless fault tolerance that allows systems to remain robust to server failures. We then show that there is an inherent tension between these two natural distributed properties and well-known multicore scalability properties in transactional systems. Finally, we show positive results; it is possible to construct a parallel distributed transactional system if any one of the properties we study is removed.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Concurrent computing methodologies
  • Computing methodologies → Distributed algorithms
Keywords
  • transactions
  • distributed systems
  • parallel systems
  • impossibility results

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Marcos K Aguilera, Naama Ben-David, Irina Calciu, Rachid Guerraoui, Erez Petrank, and Sam Toueg. Passing messages while sharing memory. In Proceedings of the 2018 ACM symposium on principles of distributed computing, pages 51-60, 2018. Google Scholar
  2. Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra Marathe, and Igor Zablotchi. The impact of RDMA on agreement. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 409-418, 2019. Google Scholar
  3. Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra J Marathe, Athanasios Xygkis, and Igor Zablotchi. Microsecond consensus for microsecond applications. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 599-616, 2020. Google Scholar
  4. Karolos Antoniadis, Antoine Desjardins, Vincent Gramoli, Rachid Guerraoui, and Igor Zablotchi. Leaderless consensus. In 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), pages 392-402. IEEE, 2021. Google Scholar
  5. Hagit Attiya and Panagiota Fatourou. Disjoint-access parallelism in software transactional memory. In Transactional Memory. Foundations, Algorithms, Tools, and Applications, pages 72-97. Springer, 2015. Google Scholar
  6. Hagit Attiya and Eshcar Hillel. The cost of privatization in software transactional memory. IEEE Transactions on Computers, 62(12):2531-2543, 2012. Google Scholar
  7. Hagit Attiya, Eshcar Hillel, and Alessia Milani. Inherent limitations on disjoint-access parallel implementations of transactional memory. Theory of Computing Systems, 49(4):698-719, 2011. Google Scholar
  8. Hillel Avni and Nir Shavit. Maintaining consistent transactional states without a global clock. In Colloquium on Structural Information & Communication Complexity, 2008. Google Scholar
  9. Naama Ben-David, Gal Sela, and Adriana Szekeres. The FIDS Theorems: Tensions between Multinode and Multicore Performance in Transactional Systems, 2023. URL: https://arxiv.org/abs/2308.03919.
  10. Philip A Bernstein, Vassos Hadzilacos, and Nathan Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley Longman Publishing Co., Inc., USA, 1986. Google Scholar
  11. Silas Boyd-Wickizer. Optimizing communication bottlenecks in multiprocessor operating system kernels. PhD thesis, Massachusetts Institute of Technology, 2014. Google Scholar
  12. Victor Bushkov, Dmytro Dziuma, Panagiota Fatourou, and Rachid Guerraoui. The pcl theorem: Transactions cannot be parallel, consistent and live. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, pages 178-187, 2014. Google Scholar
  13. Austin T. Clements, M. Frans Kaashoek, Nickolai Zeldovich, Robert T. Morris, and Eddie Kohler. The scalable commutativity rule: Designing scalable software for multicore processors. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP '13, pages 1-17, New York, NY, USA, 2013. Association for Computing Machinery. Google Scholar
  14. James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. Spanner: Google’s globally-distributed database. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI'12), 2012. Google Scholar
  15. James Cowling and Barbara H. Liskov. Granola: Low-Overhead Distributed Transaction Coordination. In Proceedings of 2012 USENIX Annual Technical Conference (USENIX ATC'12), pages 223-236, 2012. Google Scholar
  16. Aleksandar Dragojević, Dushyanth Narayanan, Edmund B. Nightingale, Matthew Renzelmann, Alex Shamis, Anirudh Badam, and Miguel Castro. No compromises: Distributed transactions with consistency, availability, and performance. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP '15, pages 54-70, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2815400.2815425.
  17. Partha Dutta, Rachid Guerraoui, and Leslie Lamport. How fast can eventual synchrony lead to consensus? In 2005 International Conference on Dependable Systems and Networks (DSN'05), pages 22-27. IEEE, 2005. Google Scholar
  18. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2):288-323, 1988. Google Scholar
  19. Mostafa Elhemali, Niall Gallagher, Nick Gordon, Joseph Idziorek, Richard Krog, Colin Lazier, Erben Mo, Akhilesh Mritunjai, Somasundaram Perianayagam, Tim Rath, Swami Sivasubramanian, James Christopher Sorenson III, Sroaj Sosothikul, Doug Terry, and Akshat Vig. Amazon DynamoDB: A scalable, predictably performant, and fully managed NoSQL database service. In 2022 USENIX Annual Technical Conference (USENIX ATC 22), 2022. Google Scholar
  20. Ronald Fagin, Joseph Y Halpern, Yoram Moses, and Moshe Vardi. Reasoning about knowledge. MIT press, 2004. Google Scholar
  21. Jose M. Faleiro, Alexander Thomson, and Daniel J. Abadi. Lazy evaluation of transactions in database systems. In SIGMOD '14, 2014. Google Scholar
  22. Pascal Felber, Christof Fetzer, Patrick Marlier, and Torvald Riegel. Time-based software transactional memory. IEEE Transactions on Parallel and Distributed Systems, 21(12):1793-1807, 2010. Google Scholar
  23. Rachid Guerraoui and Michal Kapalka. On obstruction-free transactions. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, pages 304-313, 2008. Google Scholar
  24. Joseph Y Halpern and Yoram Moses. Knowledge and common knowledge in a distributed environment. Journal of the ACM (JACM), 37(3):549-587, 1990. Google Scholar
  25. Maurice Herlihy, Victor Luchangco, Mark Moir, and William N Scherer III. Software transactional memory for dynamic-sized data structures. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, pages 92-101, 2003. Google Scholar
  26. Amos Israeli and Lihu Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '94, pages 151-160, New York, NY, USA, 1994. Association for Computing Machinery. URL: https://doi.org/10.1145/197917.198079.
  27. Manos Kapritsos, Yang Wang, Vivien Quema, Allen Clement, Lorenzo Alvisi, and Mike Dahlin. All about eve: Execute-verify replication for multi-core servers. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12, pages 237-250, USA, 2012. USENIX Association. Google Scholar
  28. Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults: preliminary version. ACM SIGACT News, 32(2):45-63, 2001. Google Scholar
  29. Tim Kraska, Gene Pang, Michael J. Franklin, Samuel Madden, and Alan Fekete. MDCC: Multi-Data Center Consistency. In Proceedings of the 8th ACM European Conference on Computer Systems, EuroSys '13, pages 113-126, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2465351.2465363.
  30. Avinash Lakshman and Prashant Malik. Cassandra: A decentralized structured storage system. SIGOPS Oper. Syst. Rev., 44(2):35-40, April 2010. URL: https://doi.org/10.1145/1773912.1773922.
  31. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558-565, July 1978. URL: https://doi.org/10.1145/359545.359563.
  32. Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133-169, 1998. Google Scholar
  33. Leslie Lamport. Paxos made simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001), pages 51-58, 2001. Google Scholar
  34. Leslie Lamport. Fast paxos. Distributed Comput., 19(2):79-103, 2006. URL: https://doi.org/10.1007/s00446-006-0005-x.
  35. Leslie Lamport. Lower bounds for asynchronous consensus. Distrib. Comput., 19(2):104-125, October 2006. URL: https://doi.org/10.1007/s00446-006-0155-x.
  36. Jialin Li, Ellis Michael, and Dan R. K. Ports. Eris: Coordination-free consistent transactions using in-network concurrency control. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP'17), SOSP '17, 2017. Google Scholar
  37. Iulian Moraru, David G Andersen, and Michael Kaminsky. Egalitarian paxos. In ACM Symposium on Operating Systems Principles, 2012. Google Scholar
  38. Shuai Mu, Lamont Nelson, Wyatt Lloyd, and Jinyang Li. Consolidating concurrency control and consensus for commits under conflicts. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI'16, pages 517-532, USA, 2016. USENIX Association. Google Scholar
  39. Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In 2014 USENIX Annual Technical Conference (Usenix ATC 14), pages 305-319, 2014. Google Scholar
  40. Christos H Papadimitriou. The serializability of concurrent database updates. Journal of the ACM (JACM), 26(4):631-653, 1979. Google Scholar
  41. Sebastiano Peluso, Roberto Palmieri, Paolo Romano, Binoy Ravindran, and Francesco Quaglia. Disjoint-access parallelism: Impossibility, possibility, and cost of transactional memory implementations. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 217-226, 2015. Google Scholar
  42. Amitabha Roy, Steven Hand, and Tim Harris. Exploring the limits of disjoint access parallelism. In Proceedings of the 1st USENIX Workshop on Hot Topics in Parallelism, Berkeley, CA, 2009. Google Scholar
  43. William N Scherer III and Michael L Scott. Advanced contention management for dynamic software transactional memory. In Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pages 240-248, 2005. Google Scholar
  44. Alex Shamis, Matthew Renzelmann, Stanko Novakovic, Georgios Chatzopoulos, Aleksandar Dragojević, Dushyanth Narayanan, and Miguel Castro. Fast general distributed transactions with opacity. In SIGMOD'19, 2019. Google Scholar
  45. Yee Jiun Song, Marcos K. Aguilera, Ramakrishna Kotla, and Dahlia Malkhi. Rpc chains: Efficient client-server communication in geodistributed systems. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09), 2009. Google Scholar
  46. Michael Stonebraker. The case for shared nothing. In IEEE Database Eng. Bull., 1985. Google Scholar
  47. Adriana Szekeres, Michael Whittaker, Jialin Li, Naveen Kr Sharma, Arvind Krishnamurthy, Dan RK Ports, and Irene Zhang. Meerkat: multicore-scalable replicated transactions following the zero-coordination principle. In Proceedings of the Fifteenth European Conference on Computer Systems, pages 1-14, 2020. Google Scholar
  48. Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. Speedy transactions in multicore in-memory databases. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP '13, pages 18-32, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2517349.2522713.
  49. Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. Speedy transactions in multicore in-memory databases. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 18-32, 2013. Google Scholar
  50. Robbert Van Renesse and Fred B Schneider. Chain replication for supporting high throughput and availability. In OSDI, 2004. Google Scholar
  51. Cheng Wang, Jianyu Jiang, Xusheng Chen, Ning Yi, and Heming Cui. Apus: Fast and scalable paxos on rdma. In Proceedings of the 2017 Symposium on Cloud Computing, pages 94-107, 2017. Google Scholar
  52. Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 347-356, 2019. Google Scholar
  53. Xiangyao Yu, Andrew Pavlo, Daniel Sanchez, and Srinivas Devadas. TicToc: Time Traveling Optimistic Concurrency Control. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD'16), 2016. Google Scholar
  54. Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. Building consistent transactions with inconsistent replication. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP '15, pages 263-278, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2815400.2815404.
  55. Jingyu Zhou, Meng Xu, Alexander Shraer, Bala Namasivayam, Alex Miller, Evan Tschannen, Steve Atherton, Andrew J. Beamon, Rusty Sears, John Leach, Dave Rosenthal, Xin Dong, Will Wilson, Ben Collins, David Scherer, Alec Grieser, Young Liu, Alvin Moore, Bhaskar Muppana, Xiaoge Su, and Vishesh Yadav. Foundationdb: A distributed unbundled transactional key value store. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD'21), 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact