Document Open Access Logo

Using Nesting to Push the Limits of Transactional Data Structure Libraries

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.OPODIS.2021.30.pdf
  • Filesize: 0.8 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

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

Metrics

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.

Cite As Get BibTex

Gal Assa, Hagar Meir, Guy Golan-Gueta, Idit Keidar, and Alexander Spiegelman. Using Nesting to Push the Limits of Transactional Data Structure Libraries. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.30

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
  • Novi Research, USA

Funding

  • Assa, Gal: Funded in part by the Hasso Plattner Institute.

Supplementary Materials

References

  1. David J Angel, James R Kumorek, Farokh Morshed, and David A Seidel. Byte code instrumentation, November 6 2001. US Patent 6,314,558. Google Scholar
  2. 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 arXiv:2001.00363, 2021. Google Scholar
  3. Joao Barreto, Aleksandar Dragojević, Paulo Ferreira, Rachid Guerraoui, and Michal Kapalka. Leveraging parallel nesting in transactional memory. In ACM Sigplan Notices, volume 45 (5), 2010. Google Scholar
  4. Martin Bättig and Thomas R Gross. Encapsulated open nesting for STM: fine-grained higher-level conflict detection. In PPoPP, 2019. Google Scholar
  5. Nathan G Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. A practical concurrent binary search tree. In ACM Sigplan Notices, volume 45 (5). ACM, 2010. Google Scholar
  6. Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking II. In DISC. Springer, 2006. Google Scholar
  7. Dave Dice and Nir Shavit. Understanding tradeoffs in software transactional memory. In CGO. IEEE, 2007. Google Scholar
  8. Aleksandar Dragojević, Rachid Guerraoui, and Michal Kapalka. Stretching transactional memory. ACM sigplan notices, 44, 2009. Google Scholar
  9. Avner Elizarov and Erez Petrank. Loft: lock-free transactional data structures. Master’s thesis, Computer Science Department, Technion, 2019. Google Scholar
  10. Robert Ennals. Software transactional memory should not be obstruction-free. Technical report, IRC-TR-06-052, Intel Research Cambridge, 2006. Google Scholar
  11. Jose M Faleiro, Daniel J Abadi, and Joseph M Hellerstein. High performance transactions via early write visibility. VLDB, 10(5), 2017. Google Scholar
  12. Pascal Felber, Christof Fetzer, and Torvald Riegel. Dynamic performance tuning of word-based software transactional memory. In PPoPP, 2008. Google Scholar
  13. Pascal Felber, Vincent Gramoli, and Rachid Guerraoui. Elastic transactions. In Idit Keidar, editor, Distributed Computing, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
  14. OIS Foundation. Suricata. URL: https://suricata-ids.org/.
  15. Vincent Gramoli. More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithms. In PPoPP, 2015. Google Scholar
  16. Vincent Gramoli and Rachid Guerraoui. Democratizing transactional programming. Commun. ACM, 57(1), January 2014. Google Scholar
  17. Vincent Gramoli and Rachid Guerraoui. Reusable concurrent data types. In ECOOP 2014 - Object-Oriented Programming. Springer, 2014. Google Scholar
  18. Rachid Guerraoui and Michal Kapalka. On the correctness of transactional memory. In PPoPP. ACM, 2008. Google Scholar
  19. 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
  20. Ahmed Hassan, Roberto Palmieri, and Binoy Ravindran. Optimistic transactional boosting. In PPoPP, 2014. Google Scholar
  21. 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
  22. Maurice Herlihy. The transactional manifesto: software engineering and non-blocking synchronization. In PLDI 2005. ACM, 2005. Google Scholar
  23. Maurice Herlihy and Eric Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP, 2008. Google Scholar
  24. 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
  25. Maurice Herlihy and J Eliot B Moss. Transactional memory: Architectural support for lock-free data structures, volume 21 (2). ACM, 1993. Google Scholar
  26. 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
  27. Guy Korland. Jstamp, 2014. URL: https://github.com/DeuceSTM/DeuceSTM/tree/master/src/test/jstamp.
  28. Guy Korland, Nir Shavit, and Pascal Felber. Noninvasive concurrency with java STM. In MULTIPROG, 2010. Google Scholar
  29. Pierre LaBorde, Lance Lebanoff, Christina Peterson, Deli Zhang, and Damian Dechev. Wait-free dynamic transactions for linked data structures. In PMAM, 2019. Google Scholar
  30. Douglas Lea. Concurrent programming in Java: design principles and patterns. Addison-Wesley Professional, 2000. Google Scholar
  31. 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
  32. 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
  33. John Eliot Blakeslee Moss. Nested transactions: An approach to reliable distributed computing. Technical report, MIT Cambridge lab, 1981. Google Scholar
  34. Shuai Mu, Sebastian Angel, and Dennis Shasha. Deferred runtime pipelining for contentious multicore software transactions. In EuroSys. ACM, 2019. Google Scholar
  35. 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
  36. Vern Paxson. Bro: a System for Detecting Network Intruders in Real-Time. Computer Networks, 31(23-24):2435-2463, 1999. URL: http://www.icir.org/vern/papers/bro-CN99.pdf.
  37. Dmitri Perelman, Anton Byshevsky, Oleg Litmanovich, and Idit Keidar. Smv: selective multi-versioning stm. In DISC. Springer, 2011. Google Scholar
  38. Martin Roesch et al. Snort: Lightweight intrusion detection for networks. In Lisa, volume 99, 1999. Google Scholar
  39. Michael Scott. Transactional memory today. SIGACT News, 46(2), June 2015. Google Scholar
  40. Nir Shavit and Itay Lotan. Skiplist-based concurrent priority queues. In IPDPS 2000. IEEE, 2000. Google Scholar
  41. Alexander Spiegelman, Guy Golan-Gueta, and Idit Keidar. Transactional data structure libraries. In PLDI 2016. ACM, 2016. Google Scholar
  42. 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
  43. Zhaoguo Wang, Shuai Mu, Yang Cui, Han Yi, Haibo Chen, and Jinyang Li. Scaling multicore databases via constrained parallel execution. In SIGMOD, 2016. Google Scholar
  44. Xingda Wei, Jiaxin Shi, Yanzhe Chen, Rong Chen, and Haibo Chen. Fast in-memory transaction processing using RDMA and HTM. In SOSP, 2015. Google Scholar
  45. Chao Xie, Chunzhi Su, Cody Littley, Lorenzo Alvisi, Manos Kapritsos, and Yang Wang. High-performance ACID via modular concurrency control. In SOSP, 2015. Google Scholar
  46. Deli Zhang, Pierre Laborde, Lance Lebanoff, and Damian Dechev. Lock-free transactional transformation for linked data structures. TOPC, 5(1), 2018. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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