[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3448016.3452794acmconferencesArticle/Chapter ViewAbstractPublication PagesmodConference Proceedingsconference-collections
research-article

Klink: Progress-Aware Scheduling for Streaming Data Systems

Published: 18 June 2021 Publication History

Abstract

Modern stream processing engines (SPEs) process large volumes of events propagated at high velocity through multiple queries. To improve performance, existing SPEs generally aim to minimize query output latency by minimizing, in turn, the propagation delay of events in query pipelines. However, for queries containing commonly used blocking operators such as windows, this scheduling approach can be inefficient. Watermarks are events popularly utilized by SPEs to correctly process window operators. Watermarks are injected into the stream to signify that no events preceding their timestamp should be further expected. Through the design and development of Klink, we leverage these watermarks to robustly infer stream progress based on window deadlines and network delay, and to schedule query pipeline execution that reflects stream progress. Klink aims to unblock window operators and to rapidly propagate events to output operators while performing judicious memory management. We integrate Klink into the popular open source SPE Apache Flink and demonstrate that Klink delivers significant performance gains over existing scheduling policies on benchmark workloads for both scale-up and scale-out deployments.

Supplementary Material

MP4 File (3448016.3452794.mp4)
Modern stream processing engines (SPEs) process large volumes of events propagated at high velocity through multiple queries. To improve performance, existing SPEs generally aim to minimize query output latency by minimizing, in turn, the propagation delay of events in query pipelines. However, for queries containing commonly used blocking operators such as windows, this scheduling approach can be inefficient. Watermarks are events popularly utilized by SPEs to correctly process window operators. Watermarks are injected into the stream to signify that no events preceding their timestamp should be further expected. Through the design and development of Klink, we leverage these watermarks to robustly infer stream progress based on window deadlines and network delay, and to schedule query pipeline execution that reflects stream progress. Klink aims to unblock window operators and to rapidly propagate events to output operators while performing judicious memory management. We integrate Klink into the popular open source SPE Apache Flink and demonstrate that Klink delivers significant performance gains over existing scheduling policies on benchmark workloads for both scale-up and scale-out deployments.

References

[1]
2020. Klink Codebase. https://github.com/klink-scheduler/klink.
[2]
Daniel J Abadi, Yanif Ahmad, Magdalena Balazinska, Ugur Cetintemel, Mitch Cherniack, Jeong-Hyon Hwang, Wolfgang Lindner, Anurag Maskey, Alex Rasin, Esther Ryvkina, et al. 2005. The design of the borealis stream processing engine. In Cidr, Vol. 5. 277--289.
[3]
Daniel J Abadi, Don Carney, Ugur Çetintemel, Mitch Cherniack, Christian Convey,Sangdon Lee, Michael Stonebraker, Nesime Tatbul, and Stan Zdonik. 2003. Aurora:a new model and architecture for data stream management. the VLDB Journal 12, 2 (2003), 120--139.
[4]
Tyler Akidau, Alex Balikov, Slava Chernyak, Josh Haberman, Reuven Lax, Sam McVeety, Daniel Mills, Paul Nordstrom, and Sam Whittle. 2013. MillWheel: fault-tolerant stream processing at internet scale. Proceedings of the VLDB Endowment6, 11 (2013), 1033--1044.
[5]
Tyler Akidau, Robert Bradshaw, Craig Chambers, Slava Chernyak, Rafael J Fernandez-Moctezuma, Reuven Lax, Sam McVeety, Daniel Mills, Frances Perry, Eric Schmidt, et al. 2015. The data flow model: a practical approach to balancing correctness, latency, and cost in massive-scale, unbounded, out-of-order data processing. Proceedings of the VLDB Endowment 8, 12 (2015), 1792--1803.
[6]
Leonardo Aniello, Roberto Baldoni, and Leonardo Querzoni. 2013. Adaptive online scheduling in storm. In Proceedings of the 7th ACM international conference on Distributed event-based systems (DEBS). ACM, 207--218.
[7]
Arvind Arasu, Mitch Cherniack, Eduardo Galvez, David Maier, Anurag S Maskey, Esther Ryvkina, Michael Stonebraker, and Richard Tibbetts. 2004. Linear road: a stream data management benchmark. In Proceedings of the VLDB Endowment,Vol. 30. ACM, 480--491.
[8]
Brian Babcock, Shivnath Babu, Rajeev Motwani, and Mayur Datar. 2003. Chain: Operator scheduling for memory minimization in data stream systems. In Proceedings of the 2003 ACM SIGMOD International conference on Management of Data. ACM, 253--264.
[9]
Pablo Basanta-Val, Norberto Fernández-Garcia, Andy J Wellings, and Neil C Audsley. 2015. Improving the predictability of distributed stream processors. Future Generation Computer Systems 52 (2015), 22--36.
[10]
Michael A Bender, Soumen Chakrabarti, and Sambavi Muthukrishnan. 1998. Flow and Stretch Metrics for Scheduling Continuous Job Streams. In SODA, Vol. 98.270--279.
[11]
Jean-Chrysostome Bolot. 1993. Characterizing end-to-end packet delay and loss in the internet. In Journal of High Speed Networks (JHSN). 305--323.
[12]
Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache flink: Stream and batch processing in a single engine.Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 36, 4 (2015).
[13]
Don Carney, Alex Rasin, Stan Zdonik, Mitch Cherniack, and Mike Stonebraker. 2003. Operator scheduling in a data stream manager. In Proceedings 2003 VLDB Conference. Elsevier, 838--849.
[14]
Ugur Cetintemel, Jiang Du, Tim Kraska, Samuel Madden, David Maier, John Meehan, Andrew Pavlo, Michael Stonebraker, Erik Sutherland, Nesime Tatbul, et al.2014. S-Store: a streaming NewSQL system for big velocity applications. Proceedings of the VLDB Endowment 7, 13 (2014), 1633--1636.
[15]
Badrish Chandramouli, Jonathan Goldstein, Roger Barga, Mirek Riedewald, and Ivo Santos. 2011. Accurate latency estimation in a distributed event processing system. In 2011 IEEE 27th International Conference on Data Engineering. IEEE, 255--266.
[16]
Badrish Chandramouli, Jonathan Goldstein, Mike Barnett, Robert De Line, Danyel Fisher, John C Platt, James F Terwilliger, and John Wernsing. 2014. Trill: A high-performance incremental query processor for diverse analytics. Proceedings of the VLDB Endowment 8, 4 (2014), 401--412.
[17]
Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin Levandoski, James Hunter, and Mike Barnett. 2018. FASTER: an embedded concurrent key-value store for state management. Proceedings of the VLDB Endowment11, 12(2018), 1930--1933.
[18]
Sanket Chintapalli, Derek Dagit, Bobby Evans, Reza Farivar, Thomas Graves, Mark Holderbaugh, Zhuo Liu, Kyle Nusbaum, Kishorkumar Patil, Boyang Jerry Peng, et al. 2016. Benchmarking streaming computation engines: Storm, flink and spark streaming. In 2016 IEEE international parallel and distributed processing symposium workshops (IPDPSW). IEEE, 1789--1792.
[19]
Sergio Esteves, Gianmarco De Francisci Morales, Rodrigo Rodrigues, Marco Serafini, and Luis Veiga. 2020. Aion: Better Late than Never in Event-Time Streams. arXiv preprint arXiv: 2003.03604(2020).
[20]
Omar Farhat, Harsh Bindra, and Khuzaima Daudjee. 2020. Leaving Stragglers at the Window: Low-Latency Stream Sampling with Accuracy Guarantees. In Proceedings of the 14th ACM International Conference on Distributed and Event-Based Systems(Montreal, Quebec, Canada)(DEBS '20). Association for Computing Machinery, New York, NY, USA, 15--26. https://doi.org/10.1145/3401025.3401732
[21]
B. Gedik, S. Schneider, M. Hirzel, and K. Wu. 2014. Elastic Scaling for Data Stream Processing. IEEE Transactions on Parallel and Distributed Systems 25, 6 (2014), 1447--1463.
[22]
Lukasz Golab and M Tamer Ozsu. 2003. Issues in data stream management. SIGMOD Record 32, 2 (2003), 5--14.
[23]
Michael Grossniklaus, David Maier, James Miller, Sharmadha Moorthy, and Kristin Tufte. 2016. Frames: data-driven windows. In Proceedings of the 10thACM International Conference on Distributed and Event-based Systems (DEBS). ACM, 13--24.
[24]
Martin Hirzel, Robert Soulé, Scott Schneider, Bugra Gedik, and Robert Grimm. 2014. A catalog of stream processing optimizations. ACM Computing Surveys(CSUR)46, 4 (2014), 1--34.
[25]
Gabriela Jacques-Silva, Ran Lei, Luwei Cheng, Guoqiang Jerry Chen, Kuen Ching, Tanji Hu, Yuan Mei, Kevin Wilfong, Rithin Shetty, Serhat Yilmaz, et al. 2018. Providing streaming joins as a service at facebook. Proceedings of the VLDB Endowment 11, 12 (2018), 1809--1821.
[26]
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. In Proceedings of the VLDB Endowment. ACM, 431--442.
[27]
Zbigniew Jerzak and Holger Ziekow. 2015. The DEBS 2015 Grand Challenge. In Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems (DEBS). ACM, 266--268.
[28]
Yuanzhen Ji, Hongjin Zhou, Zbigniew Jerzak, Anisoara Nica, Gregor Hackenbroich, and Christof Fetzer. 2015. Quality-driven continuous query execution over out-of-order data streams. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 889--894.
[29]
Nikos R Katsipoulakis, Alexandros Labrinidis, and Panos K Chrysanthis. 2017. A holistic view of stream partitioning costs.Proceedings of the VLDB Endowment 10, 11 (2017), 1286--1297.
[30]
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. In Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data. ACM, 555--569.
[31]
Sanjeev Kulkarni, Nikunj Bhagat, Maosong Fu, Vikas Kedigehalli, Christopher Kellogg, Sailesh Mittal, Jignesh M Patel, Karthik Ramasamy, and Siddarth Taneja. 2015. Twitter heron: Stream processing at scale. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 239--250.
[32]
Jin Li, Kristin Tufte, Vladislav Shkapenyuk, Vassilis Papadimos, Theodore John-son, and David Maier. 2008. Out-of-order processing: a new architecture for high-performance stream systems. Proceedings of the VLDB Endowment1, 1(2008), 274--288.
[33]
Teng Li, Jian Tang, and Jielong Xu. 2016. Performance modeling and predictive scheduling for distributed stream data processing. IEEE Transactions on Big Data 2, 4 (2016), 353--364.
[34]
Federico Lombardi, Leonardo Aniello, Silvia Bonomi, and Leonardo Querzoni. 2017. Elastic symbiotic scaling of operators and resources in stream processing systems. IEEE Transactions on Parallel and Distributed Systems 29, 3 (2017), 572--585.
[35]
Yuan Mei, Luwei Cheng, Vanish Talwar, Michael Y. Levin, Gabriela Jacques da Silva, Nikhil Simha, Anirban Banerjee, Brian Smith, Tim Williamson, Serhat Yilmaz, Weitao Chen, and Guoqiang Jerry Chen. 2020. Turbine: Facebook's Service Management Platform for Stream Processing. In 2016 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 589--600.
[36]
Hongyu Miao, Heejin Park, Myeongjae Jeon, Gennady Pekhimenko, Kathryn S McKinley, and Felix Xiaozhu Lin. 2017. Streambox: Modern stream processing on a multicore machine. In 2017 USENIX Annual Technical Conference(USENIX ATC '17). 617--629.
[37]
Lory Al Moakar, Thao N Pham, Panayiotis Neophytou, Panos K Chrysanthis, Alexandros Labrinidis, and Mohamed Sharaf. 2009. Class-based continuous query scheduling for data streams. In Proceedings of the Sixth International Workshop on Data Management for Sensor Networks. ACM, 9.
[38]
Shanmugavelayutham Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, and Johannes E Gehrke. 1999. Online scheduling to minimize average stretch. In 40th Symp. Foundations of Computer Science Science (FOCS). IEEE, 433--443.
[39]
Snehal Nagmote and Pallavi Phadnis. 2019. Massive Scale Data Processing at Netflix using Flink. Flink Forward Conference(2019).
[40]
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.
[41]
Dimitris Palyvos-Giannas, Vincenzo Gulisano, and Marina Papatriantafilou. 2019. Haren: A Framework for Ad-Hoc Thread Scheduling Policies for Data Streaming Applications. In Proceedings of the 13th ACM International Conference on Distributed and Event-based Systems (DEBS). ACM, 19--30.
[42]
Boyang Peng, Mohammad Hosseini, Zhihao Hong, Reza Farivar, and Roy Campbell. 2015. R-Storm: Resource-Aware Scheduling in Storm. In Proceedings of the 16th Annual Middleware Conference(Vancouver, BC, Canada)(Middle-ware '15). Association for Computing Machinery, New York, NY, USA, 149--161.https://doi.org/10.1145/2814576.2814808
[43]
Thao N Pham, Panos K Chrysanthis, and Alexandros Labrinidis. 2016. Avoiding class warfare: managing continuous queries with differentiated classes of service. Proceedings of the VLDB Endowment 25, 2 (2016), 197--221.
[44]
Nicolo Rivetti, Nikos Zacheilas, Avigdor Gal, and Vana Kalogeraki. 2018. Probabilistic Management of Late Arrival of Events. In Proceedings of the 12th ACM International Conference on Distributed and Event-based Systems (DEBS). ACM, 52--63.
[45]
Gabriele Russo Russo, Valeria Cardellini, and Francesco Lo Presti. 2019. Reinforcement Learning Based Policies for Elastic Stream Processing on Heterogeneous Resources. In Proceedings of the 13th ACM International Conference on Distributed and Event-based Systems (DEBS). ACM, 31--42.
[46]
Sven Schmidt, Thomas Legler, Daniel Schaller, and Wolfgang Lehner. 2005. Real-time scheduling for data stream management systems. In 17th Euromicro Conference on Real-Time Systems (ECRTS'05). IEEE, 167--176.
[47]
Mohamed A Sharaf, Panos K Chrysanthis, Alexandros Labrinidis, and Kirk Pruhs. 2006. Efficient scheduling of heterogeneous continuous queries. In VLDB. 511--522.
[48]
Mohamed A Sharaf, Panos K Chrysanthis, Alexandros Labrinidis, and Kirk Pruhs. 2008. Algorithms and metrics for processing multiple heterogeneous continuous queries. ACM Transactions on Database Systems (TODS)33, 1 (2008), 5.
[49]
Utkarsh Srivastava and Jennifer Widom. 2004. Flexible time management in data stream systems. In Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 263--274.
[50]
Michael Stonebraker, Ugur Çetintemel, and Stan Zdonik. 2005. The 8 requirements of real-time stream processing. SIGMOD Record 34, 4 (2005), 42--47.
[51]
Ankit Toshniwal, Siddarth Taneja, Amit Shukla, Karthik Ramasamy, Jignesh M Patel, Sanjeev Kulkarni, Jason Jackson, Krishna Gade, Maosong Fu, Jake Donham,et al. 2014. Storm@ twitter. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. ACM, 147--156.
[52]
Peter A. Tucker, David Maier, Tim Sheard, and Leonidas Fegaras. 2003. Exploiting punctuation semantics in continuous data streams. IEEE Transactions on Knowledge and Data Engineering 15, 3 (2003), 555--568.
[53]
Tolga Urhan and Michael J Franklin. 2001. Dynamic pipeline scheduling for improving interactive query performance. In PVLDB, Vol. 1. ACM, 501--510.
[54]
Shivaram Venkataraman, Aurojit Panda, Kay Ousterhout, Michael Armbrust, Ali Ghodsi, Michael J Franklin, Benjamin Recht, and Ion Stoica. 2017. Drizzle: Fast and adaptable stream processing at scale. In Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 374--389.
[55]
Matei Zaharia, Reynold S Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J Franklin, et al. 2016. Apache spark: a unified engine for big data processing. Commun. ACM 59, 11 (2016), 56--65.
[56]
Steffen Zeuch, Bonaventura Del Monte, Jeyhun Karimov, Clemens Lutz, Manuel Renz, Jonas Traub, Sebastian BreB, Tilmann Rabl, and Volker Markl. 2019. Analyzing efficient stream processing on modern hardware. PVLDB 12, 5 (2019),516--530.
[57]
Tan Zhang, Aakanksha Chowdhery, Paramvir Bahl, Kyle Jamieson, and Suman Banerjee. 2015. The design and implementation of a wireless video surveillance system. In Proceedings of the 21st Annual International Conference on Mobile Computing and Networking. 426--438.

Cited By

View all
  • (2024)Toward Stream Processing Elasticity in Realistic Geo-Distributed Environments2024 IEEE International Conference on Cloud Engineering (IC2E)10.1109/IC2E61754.2024.00020(118-125)Online publication date: 24-Sep-2024
  • (2023)PaVM: A Parallel Virtual Machine for Smart Contract Execution and ValidationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333420835:1(186-202)Online publication date: 20-Nov-2023
  • (2023)Proactive Resource Management to Optimize Distributed Workflow Executions2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386493(6305-6307)Online publication date: 15-Dec-2023
  • Show More Cited By

Index Terms

  1. Klink: Progress-Aware Scheduling for Streaming Data Systems

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGMOD '21: Proceedings of the 2021 International Conference on Management of Data
    June 2021
    2969 pages
    ISBN:9781450383431
    DOI:10.1145/3448016
    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: 18 June 2021

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. scheduling
    2. stream processing
    3. watermarks
    4. windows

    Qualifiers

    • Research-article

    Conference

    SIGMOD/PODS '21
    Sponsor:

    Acceptance Rates

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

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)49
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 19 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Toward Stream Processing Elasticity in Realistic Geo-Distributed Environments2024 IEEE International Conference on Cloud Engineering (IC2E)10.1109/IC2E61754.2024.00020(118-125)Online publication date: 24-Sep-2024
    • (2023)PaVM: A Parallel Virtual Machine for Smart Contract Execution and ValidationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333420835:1(186-202)Online publication date: 20-Nov-2023
    • (2023)Proactive Resource Management to Optimize Distributed Workflow Executions2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386493(6305-6307)Online publication date: 15-Dec-2023
    • (2023)A survey on the evolution of stream processing systemsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00819-833:2(507-541)Online publication date: 22-Nov-2023
    • (2022)A Survey on Advancements of Real-Time Analytics Architecture ComponentsComputational Methods and Data Engineering10.1007/978-981-19-3015-7_41(547-559)Online publication date: 9-Sep-2022

    View Options

    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