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

skip to main content
10.1145/3464298.3493407acmconferencesArticle/Chapter ViewAbstractPublication PagesmiddlewareConference Proceedingsconference-collections
research-article

Lachesis: a middleware for customizing OS scheduling of stream processing queries

Published: 02 December 2021 Publication History

Abstract

Data streaming applications in Cyber-Physical Systems enable high-throughput, low-latency transformations of raw data into value. The performance of such applications, run by Stream Processing Engines (SPEs), can be boosted through custom CPU scheduling. Previous schedulers in the literature require alterations to SPEs to control the scheduling through user-level threads. While such alterations allow for fine-grained control, they hinder the adoption of such schedulers due to the high implementation cost and potential limitations in application semantics (e.g., blocking I/O).
Motivated by the above, we explore the feasibility and benefits of custom scheduling without alterations to SPEs but, instead, by orchestrating the OS scheduler (e.g., using nice and cgroup) to enforce the scheduling goals. We propose Lachesis, a standalone scheduling middleware, decoupled from any specific SPE, that can schedule multiple streaming applications, run in one or many nodes, and possibly multiple SPEs. Our evaluation with real-world and synthetic workloads, several SPEs and hardware setups, shows its benefits over default OS scheduling and other state-of-the-art schedulers: up to 75% higher throughput, and 1130x lower average latency once such SPEs reach their peak processing capacity.

References

[1]
Swarup Acharya and S. Muthukrishnan. 1998. Scheduling On-Demand Broadcasts: New Metrics and Algorithms. In Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '98). ACM, New York, NY, USA, 43--54.
[2]
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 (Arlington, Texas, USA) (DEBS '13). ACM, New York, NY, USA, 207--218.
[3]
Apache. 2020. Storm. Retrieved March 11, 2021 from https://storm.apache.org/
[4]
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 Thirtieth International Conference on Very Large Data Bases - Volume 30 (Toronto, Canada) (VLDB '04). VLDB Endowment, Toronto, Canada, 480--491. http://dl.acm.org/citation.cfm?id=1316689.1316732
[5]
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Dilys Thomas. 2004. Operator Scheduling in Data Stream Systems. The VLDB Journal 13, 4 (Dec. 2004), 333--353.
[6]
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 (SIGMOD '03). ACM, New York, NY, USA, 253--264.
[7]
Michael A. Bender, Soumen Chakrabarti, and S. Muthukrishnan. 1998. Flow and Stretch Metrics for Scheduling Continuous Job Streams. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '98). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 270--279.
[8]
Maycon V. Bordin, Dalvan Griebler, Gabriele Mencagli, Cläudio F. R. Geyer, and Luiz Gustavo L. Fernandes. 2020. DSPBench: A Suite of Benchmark Applications for Distributed Data Stream Processing Systems. IEEE Access 8 (2020), 222900--222917.
[9]
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), 28--38.
[10]
Valeria Cardellini, Vincenzo Grassi, Francesco Lo Presti, and Matteo Nardelli. 2015. On QoS-Aware Scheduling of Data Stream Applications over Fog Computing Infrastructures. In 2015 IEEE Symposium on Computers and Communication (ISCC). IEEE, Larnaca, 271--276.
[11]
Don Carney, Ûgur Çetintemel, Mitch Cherniack, Christian Convey, Sangdon Lee, Greg Seidman, Michael Stonebraker, Nesime Tatbul, and Stan Zdonik. 2002. Monitoring Streams: A New Class of Data Management Applications. In Proceedings ofthe 28th International Conference on Very Large Data Bases (Hong Kong, China) (VLDB '02). VLDB Endowment, New York, NY, USA, 215--226.
[12]
Don Carney, Uğur Çetintemel, Alex Rasin, Stan Zdonik, Mitch Cherniack, and Mike Stonebraker. 2003. Operator Scheduling in a Data Stream Manager. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB '03, Vol. 29). VLDB Endowment, Berlin, Germany, 838--849.
[13]
Chris Davis et al. 2021. Graphite. Retrieved March 8, 2021 from https://graphiteapp.org/
[14]
Jeffrey Dean and Luiz André Barroso. 2013. The Tail at Scale. Commun. ACM 56, 2 (Feb. 2013), 74--80.
[15]
Marcos Dias de Assunção, Alexandre da Silva Veith, and Rajkumar Buyya. 2018. Distributed data stream processing and edge computing: A survey on resource elasticity and future directions. Journal of Network and Computer Applications 103 (2018), 1--17.
[16]
Philippe Dobbelaere and Kyumars Sheykh Esmaili. 2017. Kafka versus RabbitMQ: A Comparative Study of Two Industry Reference Publish/Subscribe Implementations: Industry Paper. In Proceedings ofthe 11th ACM International Conference on Distributed and Event-Based Systems (Barcelona, Spain) (DEBS '17). Association for Computing Machinery, New York, NY, USA, 227--238.
[17]
John C Eidson, Mike Fischer, and Joe White. 2002. IEEE-1588 Standard for a precision clock synchronization protocol for networked measurement and control systems. In Proceedings ofthe 34th Annual Precise Time and Time Interval Systems and Applications Meeting. 243--254.
[18]
Xinwei Fu, Talha Ghaffar, James C Davis, and Dongyoon Lee. 2019. Edgewise: A Better Stream Processing Engine for the Edge. In USENIX Annual Technical Conference (ATC) 19. USENIX, WA, USA, 929--946.
[19]
Panagiotis Garefalakis, Konstantinos Karanasos, and Peter Pietzuch. 2019. Neptune: Scheduling Suspendable Tasks for Unified Stream/Batch Applications. In Proceedings of the ACM Symposium on Cloud Computing (Santa Cruz, CA, USA) (SoCC '19). Association for Computing Machinery, New York, NY, USA, 233--245.
[20]
Prajith Ramakrishnan Geethakumari, Vincenzo Gulisano, Bo Joel Svensson, Pedro Trancoso, and Ioannis Sourdis. 2017. Single window stream aggregation using reconfigurable hardware. In 2017 International Conference on Field Programmable Technology (ICFPT). IEEE, 112--119.
[21]
Philipp M. Grulich, Breß Sebastian, Steffen Zeuch, Jonas Traub, Janis von Bleichert, Zongxiong Chen, Tilmann Rabl, and Volker Markl. 2020. Grizzly: Efficient Stream Processing Through Adaptive Query Compilation. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (Portland, OR, USA) (SIGMOD '20). Association for Computing Machinery, New York, NY, USA, 2487--2503.
[22]
Serge Hallyn and Michael Kerrisk. 2020. cgroups(7) Linux Programmers's Manual (5.10 ed.).
[23]
Serge Hallyn, Peter Zijlstra, Juri Lelli, Michael Kerrisk, Carsten Emde, Tom Bjorkholm, Markus Kuhn, and David Wheeler. 2020. sched(7)Linux Programmers's Manual (5.10 ed.).
[24]
HardKernel. 2020. Odroid-XU4. Retrieved November 12, 2020 from http://www.hardkernel.com
[25]
Martin Hirzel, Robert Soulé, Scott Schneider, Buğra Gedik, and Robert Grimm. 2014. A Catalog of Stream Processing Optimizations. ACM Computing Surveys (CSUR) 46,4(2014), 1--34.
[26]
Heike Hofmann, Hadley Wickham, and Karen Kafadar. 2017. Letter-Value Plots: Boxplots for Large Data. Journal of Computational and Graphical Statistics 26, 3 (2017), 469--477. arXiv:https://doi.org/10.1080/10618600.2017.1305277
[27]
M. Reza Hoseiny Farahabady, Ali Jannesari, Javid Taheri, Wei Bao, Albert Y. Zomaya, and Zahir Tari. 2020. Q-Flink: A QoS-Aware Controller for Apache Flink. In 2020 20th IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGRID). IEEE, Melbourne, VIC, Australia, 629--638.
[28]
M. Reza Hoseiny Farahabady, Javid Taheri, Albert Y. Zomaya, and Zahir Tari. 2020. A Dynamic Resource Controller for Resolving Quality of Service Issues in Modern Streaming Processing Engines. In 2020 IEEE 19th International Symposium on Network Computing and Applications (NCA). IEEE, Cambridge, MA, USA, 1--8.
[29]
Docker Inc. 2021. Docker. Retrieved March 23, 2021 from https://www.docker.com/
[30]
Henning Kagermann. 2015. Change through Digitization---Value Creation in the Age of Industry 4.0. In Management of Permanent Change, Horst Albach, Heribert Meffert, Andreas Pinkwart, and Ralf Reichwald (Eds.). Springer Fachmedien Wiesbaden, Wiesbaden, 23--45.
[31]
Linux Kernel. 2021. Pressure Stall Information. Retrieved September 6, 2021 from https://www.kernel.org/doc/html/latest/accounting/psi.html
[32]
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 (Melbourne, Victoria, Australia) (SIGMOD '15). ACM, New York, NY, USA, 239--250.
[33]
Jialin Li, Naveen Kr. Sharma, Dan R. K. Ports, and Steven D. Gribble. 2014. Tales of the Tail: Hardware, OS, and Application-Level Sources of Tail Latency. In Proceedings of the ACM Symposium on Cloud Computing (SOCC '14). Association for Computing Machinery, New York, NY, USA, 1--14.
[34]
Teng Li, Zhiyuan Xu, Jian Tang, and Yanzhi Wang. 2018. Model-Free Control for Distributed Stream Data Processing Using Deep Reinforcement Learning. Proc. VLDB Endow. 11,6 (Feb. 2018), 705--718.
[35]
Robert Love. 2010. Linux Kernel Development (3rd ed.). Addison-Wesley Professional, Boston, MA, United States.
[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 Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference (Santa Clara, CA, USA) (USENIX ATC '17). USENIX Association, USA, 617--629.
[37]
D. L. Mills, Martin J., Burbank J., and Kasc W. others. 1985. RFC0958: Network Time Protocol (NTP). Technical Report. Internet Engineering Task Force (IETF), USA.
[38]
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 (DMSN '09). ACM, Arlington, VA, USA, Article 9, 6 pages.
[39]
S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, and Johannes E. Gehrke. 1999. Online Scheduling to Minimize Average Stretch. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS '99). IEEE Computer Society, Washington, DC, USA, 433--. http://dl.acm.org/citation.cfm?id=795665.796508
[40]
Online. 2021. Lachesis' evaluation artifacts. Retrieved October 4, 2021 from https://github.com/dmpalyvos/lachesis-evaluation
[41]
Online. 2021. Lachesis' implementation. Retrieved October 4, 2021 from https://github.com/dmpalyvos/lachesis
[42]
Dimitris Palyvos-Giannas, Vincenzo Gulisano, and Marina Papatriantafilou. 2019. GeneaLog: Fine-grained data streaming provenance in cyber-physical systems. Parallel Comput. 89 (2019), 102552.
[43]
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 '19). ACM, Darmstadt, Germany, 19--30.
[44]
Dimitris Palyvos-Giannas, Vincenzo Gulisano, and Marina Papatriantafilou. 2019. Haren: A Middleware for Ad-Hoc Thread Scheduling Policies in Data Streaming. In Proceedings of the 20th International Middleware Conference Demos and Posters. 19--20.
[45]
Dimitris Palyvos-Giannas, Bastian Havers, Marina Papatriantafilou, and Vincenzo Gulisano. 2020. Ananke: A Streaming Framework for Live Forward Provenance. Proceedings of the VLDB Endowment 14, 3 (2020), 391--403.
[46]
Thao N. Pham, Panos K. Chrysanthis, and Alexandros Labrinidis. 2016. Avoiding Class Warfare: Managing Continuous Queries with Differentiated Classes of Service. The VLDB Journal 25, 2 (April 2016), 197--221.
[47]
Thao N. Pham, Lory A. Moakar, Panos K. Chrysanthis, and Alexandros Labrinidis. 2011. DILoS: A Dynamic Integrated Load Manager and Scheduler for Continuous Queries. In 2011 IEEE 27th International Conference on Data Engineering Workshops. IEEE, USA, 10--15.
[48]
Mohamed A. Sharaf, Panos K. Chrysanthis, and Alexandros Labrinidis. 2005. Preemptive Rate-Based Operator Scheduling in a Data Stream Management System. In Proceedings of the ACS/IEEE 2005 International Conference on Computer Systems and Applications (AICCSA '05). IEEE Computer Society, USA, 46-I.
[49]
Mohamed A. Sharaf, Panos K. Chrysanthis, Alexandros Labrinidis, and Kirk Pruhs. 2006. Efficient Scheduling of Heterogeneous Continuous Queries. In Proceedings of the 32Nd International Conference on Very Large Data Bases (VLDB '06). VLDB Endowment, Seoul, Korea, 511--522. http://dl.acm.org/citation.cfm?id=1182635.1164172
[50]
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 33, 1 (March 2008), 1--44.
[51]
Anshu Shukla, Shilpa Chaturvedi, and Yogesh Simmhan. 2017. RIoTBench: An IoT Benchmark for Distributed Stream Processing Systems. Concurrency and Computation: Practice and Experience 29, 21 (2017), e4257. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/cpe.4257
[52]
Open Source. 2021. Liebre SPE. Retrieved March 11, 2021 from https://github.com/vincenzo-gulisano/Liebre
[53]
Andrew S Tanenbaum and Herbert Bos. 2015. Modern Operating Systems. Pearson.
[54]
Georgios Theodorakis, Alexandros Koliousis, Peter R. Pietzuch, and Holger Pirk. 2020. LightSaber: Efficient Window Aggregation on Multi-core Processors. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD '20). ACM, Portland, OR, USA.
[55]
Tolga Urhan and Michael J. Franklin. 2001. Dynamic Pipeline Scheduling for Improving Interactive Query Performance. In Proceedings ofthe 27th International Conference on Very Large Data Bases (VLDB '01). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 501--510. http://dl.acm.org/citation.cfm?id=645927.672188
[56]
Ivan Walulya, Dimitris Palyvos-Giannas, Yiannis Nikolakopoulos, Vincenzo Gulisano, Marina Papatriantafilou, and Philippas Tsigas. 2018. Viper: A Module for Communication-Layer Determinism and Scaling in Low-Latency Stream Processing. Future Generation Computer Systems 88 (2018), 297--308.
[57]
Joel Wolf, Nikhil Bansal, Kirsten Hildrum, Sujay Parekh, Deepak Rajan, Rohit Wagle, Kun-Lung Wu, and Lisa Fleischer. 2008. SODA: An Optimizing Scheduler for Large-Scale Stream-Based Distributed Computer Systems. In Middleware 2008, Valérie Issarny and Richard Schantz (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 306--325.
[58]
Y. Xing, S. Zdonik, and J. -. Hwang. 2005. Dynamic Load Distribution in the Borealis Stream Processor. In 21st International Conference on Data Engineering (ICDE'05). IEEE, Tokyo, Japan, 791--802.
[59]
J. Xu, Z. Chen, J. Tang, and S. Su. 2014. T-Storm: Traffic-Aware Online Scheduling in Storm. In 2014 IEEE 34th International Conference on Distributed Computing Systems. IEEE, USA, 535--544.
[60]
Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J. Franklin, Ali Ghodsi, Joseph Gonzalez, Scott Shenker, and Ion Stoica. 2016. Apache Spark: A Unified Engine for Big Data Processing. Commun. ACM 59, 11 (Oct. 2016), 56--65.
[61]
Shuhao Zhang, Jiong He, Chi (Amelie) Zhou, and Bingsheng He. 2019. BriskStream: Scaling Stream Processing on Multicore Architectures. In Proceedings ofthe 2019 International Conference on Management of Data (SIGMOD '19). Association for Computing Machinery, New York, NY, USA, 705--722.
[62]
Shuhao Zhang, Yingjun Wu, Feng Zhang, and Bingsheng He. 2020. Towards Concurrent Stateful Stream Processing on Multicore Processors. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, Dallas, TX, USA, 1537--1548.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
Middleware '21: Proceedings of the 22nd International Middleware Conference
December 2021
398 pages
ISBN:9781450385343
DOI:10.1145/3464298
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

In-Cooperation

  • USENIX Assoc: USENIX Assoc
  • IFIP

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 December 2021

Permissions

Request permissions for this article.

Check for updates

Badges

Author Tags

  1. middleware
  2. scheduling
  3. stream processing

Qualifiers

  • Research-article

Funding Sources

Conference

Middleware '21
Sponsor:
Middleware '21: 22nd International Middleware Conference
December 6 - 10, 2021
Québec city, Canada

Acceptance Rates

Overall Acceptance Rate 203 of 948 submissions, 21%

Upcoming Conference

MIDDLEWARE '24
25th International Middleware Conference
December 2 - 6, 2024
Hong Kong , Hong Kong

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)129
  • Downloads (Last 6 weeks)4
Reflects downloads up to 21 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Developing Process Scheduling Policies in User Space with Common OS FeaturesProceedings of the 15th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/3678015.3680481(38-44)Online publication date: 4-Sep-2024
  • (2024)Evolutionary Computation Meets Stream ProcessingApplications of Evolutionary Computation10.1007/978-3-031-56852-7_24(377-393)Online publication date: 3-Mar-2024
  • (2023)Micro-batch and data frequency for stream processing on multi-coresThe Journal of Supercomputing10.1007/s11227-022-05024-y79:8(9206-9244)Online publication date: 9-Jan-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

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