Optimistic parallelization support for event stream processing systems

ABSTRACT

Event stream applications consist of an acyclic graph of components that are traversed by streams of events. Examples of operations in such components are filtering, aggregation, enrichment, and transformation of events and, commonly, applications include a mix of common-use library functions and user-defined functions. When the operation only depends on the current input events, the component can be trivially parallelized by replication. However, if the component keeps state that is used for the computation of the results, the trivial parallelization approach does not work. Parallel versions for common components have being designed, but complex or user-defined components are normally limited by single thread performance. In this work, we use optimistic parallelization approaches to harness the potential of multi-core processors to scale the performance of stateful operators in event stream applications. In addition, we investigate indulgent ways to allow the user to provide application knowledge that can improve the amount of useful speculative work. The current prototype shows considerable gain in throughput even though some speculative executions must be disregarded.

REFERENCES

• 1: D. J. Abadi, Y. Ahmad, M. Balazinska, U. Cetintemel, M. Cherniack, J.-H. Hwang, W. Lindner, A. S. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. Zdonik. The design of the borealis stream processing engine. In Proceedings of the 2nd Biennial Conference on Innovative Data Systems Research (CIDR'05), Asilomar, CA, January 2005.
• 2: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 3: R. Barga, J. Goldstein, M. Ali, and M. Hong. Consistent streaming through time: a vision for event stream processing. In Proceedings of the third biennial conference on Innovative data systems research (CIDR'07), Asilomar, USA, January 2007.
• 4: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004 [doi>10.1016/S0304-3975(03)00400-6]
• 5: S. Diestelhorst and M. Hohmuth. Hardware acceleration for lock-free data structures and software-transactional memory. In Proceedings of the 2008 Workshop on Exploiting Parallelism with Transactional Memory and other Hardware Assisted Methods, April 2008.
• 6: Pascal Felber , Christof Fetzer , Torvald Riegel, Dynamic performance tuning of word-based software transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345241]
• 7: Maurice Herlihy , Eric Koskinen, Transactional boosting: a methodology for highly-concurrent transactional objects, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345237]
• 8: Milena Ivanova , Tore Risch, Customizable parallel execution of scientific stream queries, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 9: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 10: Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 11: Mark Moir , Kevin Moore , Dan Nussbaum, The adaptive transactional memory test platform: a tool for experimenting with transactional code for rock (poster), Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378595]
• 12: M. A. Shah, J. M. Hellerstein, S. Chandrasekaran, and M. J. Franklin. Flux: An adaptive partitioning operator for continuous query systems. In Proceeding of the 19th Internationsal Conference on Data Engineering, pages 25--36, 2003.
• 13: Ori Shalev , Nir Shavit, Predictive log-synchronization, ACM SIGOPS Operating Systems Review, v.40 n.4, October 2006
• 14: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 15: Jesper H. Spring , Jean Privat , Rachid Guerraoui , Jan Vitek, Streamflex: high-throughput stream programming in java, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 16: J. Steffan , T Mowry, The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.2, January 31-February 04, 1998
• 17: Christoph von Praun , Luis Ceze , Calin Caşcaval, Implicit parallelism with ordered transactions, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229443]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming; Parallel programming

General Terms:
Algorithms, Design, Performance

Keywords:
event stream processing, optimistic parallelization, software transactional memory