SPECTRE: supporting consumption policies in window-based parallel complex event processing

ABSTRACT

Distributed Complex Event Processing (DCEP) is a paradigm to infer the occurrence of complex situations in the surrounding world from basic events like sensor readings. In doing so, DCEP operators detect event patterns on their incoming event streams. To yield high operator throughput, data parallelization frameworks divide the incoming event streams of an operator into overlapping windows that are processed in parallel by a number of operator instances. In doing so, the basic assumption is that the different windows can be processed independently from each other. However, consumption policies enforce that events can only be part of one pattern instance; then, they are consumed, i.e., removed from further pattern detection. That implies that the constituent events of a pattern instance detected in one window are excluded from all other windows as well, which breaks the data parallelism between different windows. In this paper, we tackle this problem by means of speculation: Based on the likelihood of an event's consumption in a window, subsequent windows may speculatively suppress that event. We propose the SPECTRE framework for speculative processing of multiple dependent windows in parallel. Our evaluations show an up to linear scalability of SPECTRE with the number of CPU cores.

References

1. Asaf Adi and Opher Etzion. 2004. Amit - the Situation Manager. The VLDB Journal 13, 2 (May 2004), 177--203.
2. Tyler Akidau, Alex Balikov, Kaya Bekiroglu, Slava Chernyak, Josh Haberman, Reuven Lax, Sam McVeety, Daniel Mills, Paul Nordstrom, and Sam Whittle. 2013. MillWheel: Fault-tolerant Stream Processing at Internet Scale. Proc. VLDB Endow. 6, 11 (Aug. 2013), 1033--1044.
3. Arvind Arasu, Shivnath Babu, and Jennifer Widom. 2006. The CQL Continuous Query Language: Semantic Foundations and Query Execution. The VLDB Journal 15, 2 (June 2006), 121--142.
4. Magdalena Balazinska, YongChul Kwon, Nathan Kuchta, and Dennis Lee. 2007. Moirae: History-Enhanced Monitoring. In CIDR. Citeseer, 375--386.
5. Cagri Balkesen, Nihal Dindar, Matthias Wetter, and Nesime Tatbul. 2013. RIP:Run-based intra-query parallelism for scalable complex event processing (DEBS'13). ACM, 3--14.
6. Cagri Balkesen and Nesime Tatbul. 2011. Scalable data partitioning techniques for parallel sliding window processing over data streams. In International Workshop on Data Management for Sensor Networks (DMSN).
7. Andrey Brito, Christof Fetzer, and Pascal Felber. 2009. Minimizing Latency in Fault-Tolerant Distributed Stream Processing Systems. In 2009 29th IEEE International Conference on Distributed Computing Systems. 173-182.
8. Andrey Brito, Christof Fetzer, Heiko Sturzrehm, and Pascal Felber. 2008. Speculative Out-of-order Event Processing with Software Transaction Memory. In Proceedings of the Second International Conference on Distributed Event-based Systems (DEBS '08). ACM, New York, NY, USA, 265--275.
9. Raul Castro Fernandez, Matteo Migliavacca, Evangelia Kalyvianaki, and Peter Pietzuch. 2013. Integrating Scale out and Fault Tolerance in Stream Processing Using Operator State Management (SIGMOD '13). ACM, 725--736.
10. Sharma Chakravarthy and Deepak Mishra. 1994. Snoop: An expressive event specification language for active databases. Data Knowl. Eng. 14, 1 (1994), 1--26.
11. Gianpaolo Cugola and Alessandro Margara. 2010. TESLA: A Formally Defined Event Specification Language. In Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems (DEBS '10). ACM, New York, NY, USA, 50--61.
12. Gianpaolo Cugola and Alessandro Margara. 2012. Complex Event Processing with T-REX. J. Syst. Softw. 85, 8 (Aug. 2012), 1709--1728.
13. Gianpaolo Cugola and Alessandro Margara. 2012. Low latency complex event processing on parallel hardware. J. Parallel and Distrib. Comput. 72, 2 (2012), 205 -- 218.
14. Tiziano De Matteis and Gabriele Mencagli. 2016. Keep Calm and React with Foresight: Strategies for Low-latency and Energy-efficient Elastic Data Stream Processing. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '16). ACM, New York, NY, USA, Article 13, 12 pages.
15. Tiziano De Matteis and Gabriele Mencagli. 2017. Parallel Patterns for Window-Based Stateful Operators on Data Streams: An Algorithmic Skeleton Approach. International Journal of Parallel Programming 45, 2 (01 Apr 2017), 382--401.
16. Buĝra Gedik. 2014. Partitioning functions for stateful data parallelism in stream processing. The VLDB Journal 23, 4 (2014), 517--539.
17. Martin Hirzel. 2012. Partition and Compose: Parallel Complex Event Processing. In Proceedings of the 6th ACM International Conference on Distributed Event-Based Systems (DEBS '12). ACM, New York, NY, USA, 191--200.
18. Martin Hirzel, Robert Soulé, Scott Schneider, Buĝra Gedik, and Robert Grimm. 2014. A Catalog of Stream Processing Optimizations. ACM Comput. Surv. 46, 4, Article 46 (March 2014), 34 pages.
19. Navendu Jain, Lisa Amini, Henrique Andrade, Richard King, Yoonho Park, Philippe Selo, and Chitra Venkatramani. 2006. Design, Implementation, and Evaluation of the Linear Road Benchmark on the Stream Processing Core (SIGMOD '06). ACM, 431--442.
20. Ilya Kolchinsky, Izchak Sharfman, and Assaf Schuster. 2015. Lazy Evaluation Methods for Detecting Complex Events. In Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems (DEBS '15). ACM, New York, NY, USA, 34-45.
21. Boris Koldehofe, Ruben Mayer, Umakishore Ramachandran, Kurt Rothermel, and Marco Völz. 2013. Rollback-recovery Without Checkpoints in Distributed Event Processing Systems. In Proceedings of the 7th ACM International Conference on Distributed Event-based Systems (DEBS '13). ACM, New York, NY, USA, 27--38.
22. Alexandros Koliousis, Matthias Weidlich, Raul Castro Fernandez, Alexander L. Wolf, Paolo Costa, and Peter Pietzuch. 2016. SABER: Window-Based Hybrid Stream Processing for Heterogeneous Architectures (SIGMOD '16). ACM, 555--569.
23. Jin Li, David Maier, Kristin Tufte, Vassilis Papadimos, and Peter A. Tucker. 2005. No Pane, No Gain: Efficient Evaluation of Sliding-window Aggregates over Data Streams. SIGMOD Rec. 34, 1 (March 2005), 39-44.
24. Björn Lohrmann, Peter Janacik, and Odej Kao. 2015. Elastic Stream Processing with Latency Guarantees. In 2015 IEEE 35th International Conference on Distributed Computing Systems (ICDCS '15). 399--410.
25. Ruben Mayer, Boris Koldehofe, and Kurt Rothermel. 2015. Predictable Low-Latency Event Detection with Parallel Complex Event Processing. Internet of Things Journal, IEEE 2, 4 (Aug 2015), 274--286.
26. Ruben Mayer, Christian Mayer, Muhammad Adnan Tariq, and Kurt Rothermel. 2016. GraphCEP: Real-time Data Analytics Using Parallel Complex Event and Graph Processing. In Proceedings of the 10th ACM International Conference on Distributed and Event-based Systems (DEBS '16). ACM, New York, NY, USA, 309316.
27. Ruben Mayer, Muhammad Adnan Tariq, and Kurt Rothermel. 2017. Minimizing Communication Overhead in Window-Based Parallel Complex Event Processing. In Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems (DEBS '17). ACM, New York, NY, USA, 54--65.
28. Christopher Mutschler and Michael Philippsen. 2014. Adaptive Speculative Processing of Out-of-Order Event Streams. ACM Trans. Internet Technol. 14, 1, Article 4 (Aug. 2014), 24 pages.
29. Nicholas Poul Schultz-Møller, Matteo Migliavacca, and Peter Pietzuch. 2009. Distributed Complex Event Processing with Query Rewriting (DEBS '09). ACM, Article 4, 12 pages.
30. Benjamin Wester, James Cowling, Edmund B. Nightingale, Peter M. Chen, Jason Flinn, and Barbara Liskov. 2009. Tolerating Latency in Replicated State Machines Through Client Speculation. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09). USENIX Association, Berkeley, CA, USA, 245--260.
31. Eugene Wu, Yanlei Diao, and Shariq Rizvi. 2006. High-performance Complex Event Processing over Streams (SIGMOD '06). ACM, 407--418.
32. Erik Zeitler and Tore Risch. 2011. Massive scale-out of expensive continuous queries. VLDB Endowment 4, 11 (2011), 1181-1188.
33. Fred Zemke, Andrew Witkowski, and Mitch Cherniak. 2007. Pattern matching in sequences of rows. (2007).
34. D. Zimmer and R. Unland. 1999. On the semantics of complex events in active database management systems. In Data Engineering, 1999. Proceedings., 15th International Conference on. 392--399.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Stream management