Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3514221.3517829acmconferencesArticle/Chapter ViewAbstractPublication PagesmodConference Proceedingsconference-collections
research-article

HYPERSONIC: A Hybrid Parallelization Approach for Scalable Complex Event Processing

Published: 11 June 2022 Publication History

Abstract

The ability to promptly and efficiently detect arbitrarily complex patterns in massive real-time data streams is a crucial requirement in many modern applications. The ever-growing scale of these applications and the sophistication of the patterns involved make it imperative to employ advanced solutions that can optimize pattern detection. One of the most prominent and well-established ways to achieve the above goal is to apply complex event processing (CEP) in a parallel manner, using a multi-core machine and/or a distributed environment. However, the inherent tightly coupled nature of CEP severely limits the scalability of the parallelization methods currently available. In this paper, we introduce a novel parallelization mechanism for efficient complex event processing over data streams. This mechanism is based on a hybrid two-tier model combining multiple layers of parallelism. By employing a fine-grained load balancing model, this multi-layered approach leads to a substantial increase in event detection throughput, while at the same time reducing the latency and the memory consumption. An extensive experimental evaluation on multiple real-life datasets shows that our approach consistently outperforms state-of-the-art CEP parallelization methods by a factor of two to three orders of magnitude.

References

[1]
[n.d.]. http://flink.apache.org.
[2]
[n.d.]. http://www.eoddata.com.
[3]
[n.d.]. http://www.espertech.com.
[4]
D. J. Abadi, Y. Ahmad, M. Balazinska, M. Cherniack, J. Hwang, W. Lindner, A. S. Maskey, E. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. Zdonik. 2005. The design of the Borealis stream processing engine. In CIDR. 277--289.
[5]
A. Adi and O. Etzion. 2004. Amit - the Situation Manager. The VLDB Journal 13, 2 (2004), 177--203. https://doi.org/10.1007/s00778-003-0108-y
[6]
J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. 2008. Efficient Pattern Matching over Event Streams. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (Vancouver, Canada) (SIGMOD '08). ACM, New York, NY, USA, 147--160. https://doi.org/10.1145/1376616.1376634
[7]
M. Akdere, U. Çetintemel, and N. Tatbul. 2008. Plan-based Complex Event Detection Across Distributed Sources. Proc. VLDB Endow. 1, 1 (2008), 66--77.
[8]
Alaa Aljanaby, Emad Abuelrub, and Mohammed Odeh. 2005. A Survey of Distributed Query Optimization. Int. Arab J. Inf. Technol. 2, 1 (2005), 48--57.
[9]
L. Amini, H. Andrade, R. Bhagwan, F. Eskesen, R. King, P. Selo, Y. Park, and C. Venkatramani. 2006. SPC: A Distributed, Scalable Platform for Data Mining. In Proceedings of the 4th International Workshop on Data Mining Standards, Services and Platforms (Philadelphia, Pennsylvania). ACM, New York, NY, USA, 27--37. https://doi.org/10.1145/1289612.1289615
[10]
A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, M. Datar, K. Ito, R. Motwani, U. Srivastava, and J. Widom. 2016. STREAM: The Stanford Data Stream Management System. Springer Berlin Heidelberg, Berlin, Heidelberg, 317--336. https://doi.org/10.1007/978--3--540--28608-0_16
[11]
A. Arasu, S. Babu, and J. Widom. 2006. The CQL Continuous Query Language: Semantic Foundations and Query Execution. The VLDB Journal 15, 2 (2006), 121--142. https://doi.org/10.1007/s00778-004-0147-z
[12]
C. Balkesen, N. Dindar, M. Wetter, and N. Tatbul. 2013. RIP: Run-based Intraquery Parallelism for Scalable Complex Event Processing. In Proceedings of the 7th ACM International Conference on Distributed Event-based Systems (Arlington, Texas, USA) (DEBS '13). ACM, New York, NY, USA, 3--14. https://doi.org/10.1145/2488222.2488257
[13]
R. S. Barga, J. Goldstein, M. H. Ali, and M. Hong. 2007. Consistent Streaming Through Time: A Vision for Event Stream Processing. In CIDR. 363--374.
[14]
Paul Beame, Paraschos Koutris, and Dan Suciu. 2017. Communication steps for parallel query processing. Journal of the ACM (JACM) 64, 6 (2017), 1--58.
[15]
M. Blount, M. Ebling, J. Eklund, A. James, C. Mcgregor, N. Percival, K. Smith, and D. Sow. 2010. Real-Time Analysis for Intensive Care: Development and Deployment of the Artemis Analytic System. 29 (05 2010), 110--8.
[16]
L. Brenna, A. Demers, J. Gehrke, M. Hong, J. Ossher, B. Panda, M. Riedewald, M. Thatte, and W. White. [n.d.]. Cayuga: A High-performance Event Processing Engine. In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data (Beijing, China). ACM, 1100--1102. https://doi.org/10.1145/1247480.1247620
[17]
L. Brenna, J. Gehrke, M. Hong, and D. Johansen. 2009. Distributed event stream processing with non-deterministic finite automata. In DEBS, A. S. Gokhale and D. C. Schmidt (Eds.). ACM.
[18]
P. Brown. 2013. Architecting Complex-Event Processing Solutions with TIBCO (1st ed.). Addison-Wesley Professional.
[19]
S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. A. Shah. 2003. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. In CIDR.
[20]
J. Chen, D. J. DeWitt, F. Tian, and Y. Wang. 2000. NiagaraCQ: A Scalable Continuous Query System for Internet Databases. SIGMOD Rec. 29, 2 (2000), 379--390. https://doi.org/10.1145/335191.335432
[21]
Shumo Chu, Magdalena Balazinska, and Dan Suciu. 2015. From theory to practice: Efficient join query evaluation in a parallel database system. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 63--78.
[22]
Diane J Cook. 2010. Learning setting-generalized activity models for smart spaces. IEEE intelligent systems 2010, 99 (2010), 1.
[23]
G. Cugola and A. Margara. 2010. TESLA: a formally defined event specification language. In DEBS. ACM, 50--61.
[24]
G. Cugola and A. Margara. 2012. Complex Event Processing with T-REX. J. Syst. Softw. 85, 8 (2012), 1709--1728. https://doi.org/10.1016/j.jss.2012.03.056
[25]
G. Cugola and A. Margara. 2012. Low latency complex event processing on parallel hardware. J. Parallel and Distrib. Comput. 72, 2 (2012), 205--218.
[26]
G. Cugola and A. Margara. 2012. Processing Flows of Information: From Data Stream to Complex Event Processing. ACM Comput. Surv. 44, 3, Article 15 (2012), 62 pages. https://doi.org/10.1145/2187671.2187677
[27]
M. Dayarathna and S. Perera. 2018. Recent Advancements in Event Processing. ACM Comput. Surv. 51, 2, Article 33 (Feb. 2018), 36 pages. https://doi.org/10.1145/3170432
[28]
Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified data processing on large clusters. (2004).
[29]
A. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. White. [n.d.]. Towards Expressive Publish/Subscribe Systems. In Proceedings of the 10th International Conference on Advances in Database Technology. Springer-Verlag, 627--644. https://doi.org/10.1007/11687238_38
[30]
Christos Doulkeridis and Kjetil Nørvåg. 2014. A survey of large-scale analytical query processing in MapReduce. The VLDB journal 23, 3 (2014), 355--380.
[31]
O. Etzion and P. Niblett. 2010. Event Processing in Action. Manning Publications Co.
[32]
I. Flouris, N. Giatrakos, A. Deligiannakis, M. Garofalakis, M. Kamp, and M. Mock. 2017. Issues in complex event processing: Status and prospects in the Big Data era. Journal of Systems and Software 127 (2017), 217 -- 236. https://doi.org/10.1016/j.jss.2016.06.011
[33]
Bugra Gedik, Habibe G Özsema, and Özcan Öztürk. 2016. Pipelined fission for stream programs with dynamic selectivity and partitioned state. J. Parallel and Distrib. Comput. 96 (2016), 106--120.
[34]
D. Gyllstrom, J. Agrawal, Y. Diao, and N. Immerman. 2008. On Supporting Kleene Closure over Event Streams. In ICDE. IEEE, 1391--1393.
[35]
Yeye He, Siddharth Barman, Di Wang, and Jeffrey F Naughton. 2011. On the complexity of privacy-preserving complex event processing. In Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 165--174.
[36]
M. Hill, M. Campbell, Y. C. Chang, and V. Iyengar. 2008. Event detection in sensor networks for modern oil fields. In DEBS (ACM International Conference Proceeding Series), Vol. 332. ACM, 95--102.
[37]
M. Hirzel. 2012. Partition and Compose: Parallel Complex Event Processing. In Proceedings of the 6th ACM International Conference on Distributed Event- Based Systems (Berlin, Germany) (DEBS '12). ACM, New York, NY, USA, 191--200. https://doi.org/10.1145/2335484.2335506
[38]
M. Hirzel, R. Soulé, S. Schneider, B. Gedik, and R. Grimm. 2014. A Catalog of Stream Processing Optimizations. ACM Comput. Surv. 46, 4, Article 46 (March 2014), 34 pages. https://doi.org/10.1145/2528412
[39]
M. Hirzel, R. Soulé, S. Schneider, B. Gedik, and R. Grimm. 2014. A catalog of stream processing optimizations. ACM Computing Surveys (CSUR) 46, 4 (2014), 46.
[40]
K.Chapnik, I. Kolchinsky, and A. Schuster. 2022. DARLING: Data-Aware Load Shedding in Complex Event Processing Systems. PVLDB 15, 15 (2022).
[41]
I. Kolchinsky and A. Schuster. 2018. Efficient Adaptive Detection of Complex Event Patterns. PVLDB 11, 11 (2018), 1346--1359.
[42]
I. Kolchinsky and A. Schuster. 2018. Join Query Optimization Techniques for Complex Event Processing Applications. PVLDB 11, 11 (2018), 1332--1345.
[43]
Ilya Kolchinsky and Assaf Schuster. 2019. Real-Time Multi-Pattern Detection over Event Streams. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, Peter A. Boncz, Stefan Manegold, Anastasia Ailamaki, Amol Deshpande, and Tim Kraska (Eds.). ACM, 589--606. https://doi.org/10.1145/3299869.3319869
[44]
I. Kolchinsky, A. Schuster, and D. Keren. 2016. Efficient Detection of Complex Event Patterns Using Lazy Chain Automata. CoRR abs/1612.05110 (2016). arXiv:1612.05110 http://arxiv.org/abs/1612.05110
[45]
I. Kolchinsky, I. Sharfman, and A. Schuster. 2015. Lazy Evaluation Methods for Detecting Complex Events. In DEBS (Oslo, Norway). ACM, 34--45. https://doi.org/10.1145/2675743.2771832
[46]
Donald Kossmann. 2000. The state of the art in distributed query processing. ACM Computing Surveys (CSUR) 32, 4 (2000), 422--469.
[47]
Kyong-Ha Lee, Yoon-Joon Lee, Hyunsik Choi, Yon Dohn Chung, and Bongki Moon. 2012. Parallel data processing with MapReduce: a survey. AcM sIGMoD Record 40, 4 (2012), 11--20.
[48]
Qian Lin, Beng Chin Ooi, Zhengkui Wang, and Cui Yu. 2015. Scalable distributed stream join processing. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 811--825.
[49]
Mo Liu, Elke Rundensteiner, Dan Dougherty, Chetan Gupta, Song Wang, Ismail Ari, and Abhay Mehta. 2011. High-performance nested CEP query processing over event streams. In 2011 IEEE 27th International Conference on Data Engineering. IEEE, 123--134.
[50]
M. Liu, E. Rundensteiner, K. Greenfield, C. Gupta, S. Wang, I. Ari, and A. Mehta. 2011. E-Cube: Multi-dimensional Event Sequence Analysis Using Hierarchical Pattern Query Sharing. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data (Athens, Greece) (SIGMOD '11). ACM, New York, NY, USA, 889--900. https://doi.org/10.1145/1989323.1989416
[51]
R. Mayer, B. Koldehofe, and K. Rothermel. 2015. Predictable Low-Latency Event Detection With Parallel Complex Event Processing. IEEE Internet of Things Journal 2, 4 (Aug 2015), 274--286. https://doi.org/10.1109/JIOT.2015.2397316
[52]
Ruben Mayer, Ahmad Slo, Muhammad Adnan Tariq, Kurt Rothermel, Manuel Gräber, and Umakishore Ramachandran. 2017. SPECTRE: supporting consumption policies in window-based parallel complex event processing. In Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference. 161--173.
[53]
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. 54--65. 14
[54]
Y. Mei and S. Madden. 2009. ZStream: a cost-based query processor for adaptively detecting composite events. In SIGMOD Conference. ACM, 193--206.
[55]
Gabriele Mencagli, Massimo Torquati, Marco Danelutto, and Tiziano De Matteis. 2017. Parallel continuous preference queries over out-of-order and bursty data streams. IEEE Transactions on Parallel and Distributed Systems 28, 9 (2017), 2608--2624.
[56]
Muhammad Anis Uddin Nasir, Gianmarco De Francisci Morales, Nicolas Kourtellis, and Marco Serafini. 2016. When two choices are not enough: Balancing at scale in distributed stream processing. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE). IEEE, 589--600.
[57]
M Tamer Özsu and Patrick Valduriez. 1996. Distributed and parallel database systems. ACM Computing Surveys (CSUR) 28, 1 (1996), 125--128.
[58]
Karl Pearson. 1895. VII. Note on regression and inheritance in the case of two parents. proceedings of the royal society of London 58, 347--352 (1895), 240--242.
[59]
O. Poppe, C. Lei, S. Ahmed, and E. Rundensteiner. 2017. Complete Event Trend Detection in High-Rate Event Streams. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD '17). ACM, New York, NY, USA, 109--124. https://doi.org/10.1145/3035918.3035947
[60]
E. Rabinovich, O. Etzion, and A. Gal. 2011. Pattern Rewriting Framework for Event Processing Optimization. In Proceedings of the 5th ACM International Conference on Distributed Event-based Systems (New York, New York, USA). ACM, 101--112. https://doi.org/10.1145/2002259.2002277
[61]
M. Ray, C. Lei, and E. A. Rundensteiner. 2016. Scalable Pattern Sharing on Event Streams. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD '16). ACM, New York, NY, USA, 495--510. https://doi.org/10.1145/2882903.2882947
[62]
Sasko Ristov, Radu Prodan, Marjan Gusev, and Karolj Skala. 2016. Superlinear speedup in HPC systems: Why and when?. In 2016 Federated Conference on Computer Science and Information Systems (FedCSIS). IEEE, 889--898.
[63]
Nicoló Rivetti, Emmanuelle Anceaume, Yann Busnel, Leonardo Querzoni, and Bruno Sericola. 2016. Online scheduling for shuffle grouping in distributed stream processing systems. In Proceedings of the 17th International Middleware Conference. 1--12.
[64]
Henriette Röger and Ruben Mayer. 2019. A comprehensive survey on parallelization and elasticity in stream processing. ACM Computing Surveys (CSUR) 52, 2 (2019), 1--37.
[65]
Pratanu Roy, Jens Teubner, and Rainer Gemulla. 2014. Low-latency handshake join. Proceedings of the VLDB Endowment 7, 9 (2014), 709--720.
[66]
Ravindra S. and Dayarathna M. 2015. Distributed Scaling of WSO2 Complex Event Processor. (2015). https://wso2.com/library/articles/2015/12/article-distributed-scaling-of-wso2-complex-event-processor/.
[67]
Omran Saleh, Heiko Betz, and Kai-Uwe Sattler. 2015. Partitioning for scalable complex event processing on data streams. In New Trends in Database and Information Systems II. Springer, 185--197.
[68]
N. P. Schultz-Møller, M. M., and P. R. Pietzuch. 2009. Distributed complex event processing with query rewriting. In DEBS. ACM.
[69]
S. Suhothayan, K. Gajasinghe, I. L. Narangoda, S. Chaturanga, S. Perera, and V. Nanayakkara. 2011. Siddhi: A Second Look at Complex Event Processing Architectures. In Proceedings of the 2011 ACM Workshop on Gateway Computing Environments (Seattle, Washington, USA) (GCE '11). ACM, New York, NY, USA, 43--50. https://doi.org/10.1145/2110486.2110493
[70]
Yuzhe Tang and Bugra Gedik. 2012. Autopipelining for data stream processing. IEEE Transactions on Parallel and Distributed Systems 24, 12 (2012), 2344--2354.
[71]
Jens Teubner and Rene Mueller. 2011. How soccer players would do stream joins. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. 625--636.
[72]
YH Wang, Kening Cao, and XM Zhang. 2013. Complex event processing over distributed probabilistic event streams. Computers & Mathematics with Applications 66, 10 (2013), 1808--1821.
[73]
L. Woods, J. Teubner, and G. Alonso. 2010. Complex event detection at wire speed with FPGAs. Proceedings of the VLDB Endowment 3, 1--2 (2010), 660--669.
[74]
E. Wu, Y. Diao, and S. Rizvi. 2006. High-performance complex event processing over streams. In SIGMOD Conference. ACM, 407--418.
[75]
Fuyuan Xiao, Cheng Zhan, Hong Lai, Li Tao, and Zhiguo Qu. 2017. New parallel processing strategies in complex event processing systems with data streams. International Journal of Distributed Sensor Networks 13, 8 (2017), 1550147717728626. https://doi.org/10.1177/1550147717728626 arXiv:https://doi.org/10.1177/1550147717728626
[76]
H. Zhang, Y. Diao, and N. Immerman. 2014. On Complexity and Optimization of Expensive Queries in Complex Event Processing. In SIGMOD. 217--228.
[77]
S. Zhang, H. T. Vo, D. Dahlmeier, and B. He. 2017. Multi-Query Optimization for Complex Event Processing in SAP ESP. In 33rd IEEE International Conference on Data Engineering, ICDE 2017, San Diego, CA, USA, April 19--22, 2017. 1213--1224. https://doi.org/10.1109/ICDE.2017.166
[78]
Shuhao Zhang, Feng Zhang, Yingjun Wu, Bingsheng He, and Paul Johns. 2020. Hardware-conscious stream processing: A survey. ACM SIGMOD Record 48, 4 (2020), 18--29.
[79]
Q. Zhou, Y. Simmhan, and V. K. Prasanna. 2012. Incorporating Semantic Knowledge into Dynamic Data Processing for Smart Power Grids. In International Semantic Web Conference (2) (Lecture Notes in Computer Science), Vol. 7650. Springer, 257--273.
[80]
Nikolaos Zygouras, Nikos Zacheilas, Vana Kalogeraki, Dermot Kinane, and Dimitrios Gunopulos. 2015. Insights on a scalable and dynamic traffic management system. In EDBT. 653--664.

Cited By

View all
  • (2024)DecoPa: Query Decomposition for Parallel Complex Event ProcessingProceedings of the ACM on Management of Data10.1145/36549352:3(1-26)Online publication date: 30-May-2024
  • (2024)An Efficient Algorithm for Continuous Complex Event Matching Using Bit-Parallelism2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00037(396-408)Online publication date: 13-May-2024
  • (2023)NANO: Cryptographic Enforcement of Readability and Editability Governance in Blockchain DatabasesIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.333017121:4(3439-3452)Online publication date: 6-Nov-2023

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data
June 2022
2597 pages
ISBN:9781450392495
DOI:10.1145/3514221
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2022

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. complex event processing
  2. distributed query processing
  3. parallel query processing
  4. query optimization

Qualifiers

  • Research-article

Conference

SIGMOD/PODS '22
Sponsor:

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)67
  • Downloads (Last 6 weeks)9
Reflects downloads up to 13 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)DecoPa: Query Decomposition for Parallel Complex Event ProcessingProceedings of the ACM on Management of Data10.1145/36549352:3(1-26)Online publication date: 30-May-2024
  • (2024)An Efficient Algorithm for Continuous Complex Event Matching Using Bit-Parallelism2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00037(396-408)Online publication date: 13-May-2024
  • (2023)NANO: Cryptographic Enforcement of Readability and Editability Governance in Blockchain DatabasesIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.333017121:4(3439-3452)Online publication date: 6-Nov-2023

View Options

Get Access

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media