Document Open Access Logo

Brief Announcement: Using Nesting to Push the Limits of Transactional Data Structure Libraries

Authors Gal Assa, Hagar Meir, Guy Golan-Gueta, Idit Keidar, Alexander Spiegelman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.45.pdf
  • Filesize: 392 kB
  • 4 pages

Document Identifiers

Author Details

Gal Assa
  • Technion - Israel Institute of Technology, Haifa, Israel
Hagar Meir
  • IBM Research, Haifa, Israel
Guy Golan-Gueta
  • Independent researcher, Israel
Idit Keidar
  • Technion - Israel Institute of Technology, Haifa, Israel
Alexander Spiegelman
  • Independent researcher, CA, USA

Cite As Get BibTex

Gal Assa, Hagar Meir, Guy Golan-Gueta, Idit Keidar, and Alexander Spiegelman. Brief Announcement: Using Nesting to Push the Limits of Transactional Data Structure Libraries. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 45:1-45:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.45

Abstract

Transactional data structure libraries (TDSL) combine the ease-of-programming of transactions with the high performance and scalability of custom-tailored concurrent data structures. They can be very efficient thanks to their ability to exploit data structure semantics in order to reduce overhead, aborts, and wasted work compared to general-purpose software transactional memory. However, TDSLs were not previously used for complex use-cases involving long transactions and a variety of data structures.
In this paper, we boost the performance and usability of a TDSL, towards allowing it to support complex applications. A key idea is nesting. Nested transactions create checkpoints within a longer transaction, so as to limit the scope of abort, without changing the semantics of the original transaction. We build a Java TDSL with built-in support for nested transactions over a number of data structures. We conduct a case study of a complex network intrusion detection system that invests a significant amount of work to process each packet. Our study shows that our library outperforms publicly available STMs twofold without nesting, and by up to 16x when nesting is used.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Concurrent algorithms
Keywords
  • Transactional Libraries

Metrics

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

Related Versions

References

  1. Gal Assa, Hagar Meir, Guy Golan-Gueta, Idit Keidar, and Alexander Spiegelman. Using nesting to push the limits of transactional data structure libraries. arXiv preprint, 2021. URL: http://arxiv.org/abs/2001.00363.
  2. Nathan G Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. A practical concurrent binary search tree. In ACM Sigplan Notices, volume 45. ACM, 2010. Google Scholar
  3. Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking II. In DISC. Springer, 2006. Google Scholar
  4. Bart Haagdorens, Tim Vermeiren, and Marnix Goossens. Improving the performance of signature-based network intrusion detection sensors by multi-threading. In WISA. Springer, 2004. Google Scholar
  5. Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N Scherer, and Nir Shavit. A lazy concurrent list-based set algorithm. In OPODIS. Springer, 2005. Google Scholar
  6. Maurice Herlihy. The transactional manifesto: software engineering and non-blocking synchronization. In PLDI 2005. ACM, 2005. Google Scholar
  7. Maurice Herlihy and Eric Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP, 2008. Google Scholar
  8. Maurice Herlihy, Victor Luchangco, Mark Moir, and William N Scherer III. Software transactional memory for dynamic-sized data structures. In PODC. ACM, 2003. Google Scholar
  9. Maurice Herlihy and J Eliot B Moss. Transactional memory: Architectural support for lock-free data structures, volume 21. ACM, 1993. Google Scholar
  10. Nathaniel Herman, Jeevana Priya Inala, Yihe Huang, Lillian Tsai, Eddie Kohler, Barbara Liskov, and Liuba Shrira. Type-aware transactions for faster concurrent code. In Eurosys, 2016. Google Scholar
  11. Guy Korland. Jstamp, 2014. URL: https://github.com/DeuceSTM/DeuceSTM/tree/master/src/test/jstamp.
  12. Guy Korland, Nir Shavit, and Pascal Felber. Noninvasive concurrency with java STM. In MULTIPROG, 2010. Google Scholar
  13. Pierre LaBorde, Lance Lebanoff, Christina Peterson, Deli Zhang, and Damian Dechev. Wait-free dynamic transactions for linked data structures. In PMAM, 2019. Google Scholar
  14. Douglas Lea. Concurrent programming in Java: design principles and patterns. Addison-Wesley Professional, 2000. Google Scholar
  15. Lance Lebanoff, Christina Peterson, and Damian Dechev. Check-wait-pounce: Increasing transactional data structure throughput by delaying transactions. In IFIP International Conference on Distributed Applications and Interoperable Systems. Springer, 2019. Google Scholar
  16. Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, and Kunle Olukotun. STAMP: Stanford transactional applications for multi-processing. In 2008 IEEE International Symposium on Workload Characterization, 2008. Google Scholar
  17. John Eliot Blakeslee Moss. Nested transactions: An approach to reliable distributed computing. Technical report, MIT Cambridge lab, 1981. Google Scholar
  18. Yang Ni, Vijay S Menon, Ali-Reza Adl-Tabatabai, Antony L Hosking, Richard L Hudson, J Eliot B Moss, Bratin Saha, and Tatiana Shpeisman. Open nesting in software transactional memory. In PPoPP, 2007. Google Scholar
  19. Michael Scott. Transactional memory today. SIGACT News, 46(2), 2015. Google Scholar
  20. Nir Shavit and Itay Lotan. Skiplist-based concurrent priority queues. In IPDPS 2000. IEEE, 2000. Google Scholar
  21. Alexander Spiegelman, Guy Golan-Gueta, and Idit Keidar. Transactional data structure libraries. In PLDI 2016. ACM, 2016. Google Scholar
  22. Alexandru Turcu, Binoy Ravindran, and Mohamed M Saad. On closed nesting in distributed transactional memory. In Seventh ACM SIGPLAN workshop on Transactional Computing, 2012. Google Scholar
  23. Deli Zhang, Pierre Laborde, Lance Lebanoff, and Damian Dechev. Lock-free transactional transformation for linked data structures. TOPC, 5(1), 2018. 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