Thomas Heinze
Zbigniew Jerzak
ABSTRACT
Elastic scaling allows a data stream processing system to react to a dynamically changing query or event workload by automatically scaling in or out. Thereby, both unpredictable load peaks as well as underload situations can be handled. However, each scaling decision comes with a latency penalty due to the required operator movements. Therefore, in practice an elastic system might be able to improve the system utilization, however it is not able to provide latency guarantees defined by a service level agreement (SLA).
In this paper we introduce an elastic scaling system, which optimizes the utilization under certain latency constraints defined by a SLA. Specifically, we present a model, which estimates the latency spike created by a set of operator movements. We use this model to built a latency-aware elastic operator placement algorithm, which minimizes the number of latency violations. We show that our solution is able to reduce the 90th percentile of the end to end latency by up to 30% and reduce the number of latency violations by 50%. The achieved system utilization for our approach is comparable to a scaling strategy, which does not use latency as optimization target.
- 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 CIDR, pages 277--289, 2005.Google Scholar
- Y. Ahmad and U. Çetintemel. Network-aware query processing for stream-based applications. In VLDB, pages 456--467, 2004. Google ScholarDigital Library
- M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia. A view of cloud computing. Communications of the ACM, pages 50--58, 2010. Google ScholarDigital Library
- M. Arrington. AOL proudly releases massive amounts of private data. TechCrunch: http://www.techcrunch.com/2006/08/06/aol-proudly-releasesmassive-amounts-of-user-search-data, 2006.Google Scholar
- B. Chandramouli, J. Goldstein, R. Barga, M. Riedewald, and I. Santos. Accurate latency estimation in a distributed event processing system. In ICDE, pages 255--266, 2011. Google ScholarDigital Library
- E. Coffman Jr, M. Garey, and D. Johnson. Approximation algorithms for bin packing: A survey. In Approximation algorithms for NP-hard problems, pages 46--93, 1996. Google ScholarDigital Library
- S. Das, D. Agrawal, and A. El Abbadi. Elastras: An elastic transactional data store in the cloud. In USENIX HotCloud, 2009. Google ScholarDigital Library
- A. J. Elmore, S. Das, D. Agrawal, and A. El Abbadi. Zephyr: live migration in shared nothing databases for elastic cloud platforms. In SIGMOD, pages 301--312, 2011. Google ScholarDigital Library
- R. C. Fernandez, M. Migliavacca, E. Kalyvianaki, and P. Pietzuch. Integrating scale out and fault tolerance in stream processing using operator state management. In SIGMOD, pages 725--736, 2013. Google ScholarDigital Library
- B. Gedik, S. Schneider, M. Hirzel, and K. Wu. Elastic scaling for data stream processing. IEEE TPDS, 2013.Google Scholar
- V. Gulisano, R. Jimenez-Peris, M. Patino-Martinez, C. Soriente, and P. Valduriez. Streamcloud: An elastic and scalable data streaming system. IEEE TPDS, pages 2351--2365, 2012. Google ScholarDigital Library
- T. Heinze, V. Pappalardo, Z. Jerzak, and C. Fetzer. Auto-scaling techniques for elastic data stream processing. In ICDEW, 2014. Google ScholarDigital Library
- T. Lorido-Botrán, J. Miguel-Alonso, and J. A. Lozano. Auto-scaling techniques for elastic applications in cloud environments. Department of Computer Architecture and Technology, University of Basque Country, Tech. Rep. EHU-KAT-IK-09-12, 2012.Google Scholar
- S. Martello and P. Toth. Algorithms for knapsack problems. Surveys in combinatorial optimization, pages 213--258, 1987.Google Scholar
- P. Mell and T. Grance. The NIST definition of cloud computing. NIST Special Publication 800--145, 2011.Google Scholar
- P. Pietzuch, J. Ledlie, J. Shneidman, M. Roussopoulos, M. Welsh, and M. Seltzer. Network-aware operator placement for stream-processing systems. In ICDE, pages 49--49, 2006. Google ScholarDigital Library
- E. A. Rundensteiner, L. Ding, T. Sutherland, Y. Zhu, B. Pielech, and N. Mehta. CAPE: Continuous query engine with heterogeneous-grained adaptivity. In VLDB, pages 1353--1356, 2004. Google ScholarDigital Library
- T. K. Sellis. Multiple-query optimization. ACM TODS, pages 23--52, 1988. Google ScholarDigital Library
- M. A. Shah, J. M. Hellerstein, S. Chandrasekaran, and M. J. Franklin. Flux: An adaptive partitioning operator for continuous query systems. In ICDE, pages 25--36, 2003.Google ScholarCross Ref
- M. Stonebraker, U. Çetintemel, and S. Zdonik. The 8 requirements of real-time stream processing. ACM SIGMOD Record, pages 42--47, 2005. Google ScholarDigital Library
- E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In SIGMOD, pages 407--418, 2006. Google ScholarDigital Library
- Y. Yang, J. Kramer, D. Papadias, and B. Seeger. Hybmig: A hybrid approach to dynamic plan migration for continuous queries. IEEE TKDE, pages 398--411, 2007. Google ScholarDigital Library
- Y. Zhu, E. A. Rundensteiner, and G. T. Heineman. Dynamic plan migration for continuous queries over data streams. In SIGMOD, pages 431--442, 2004. Google ScholarDigital Library
Index Terms
- Latency-aware elastic scaling for distributed data stream processing systems
Recommendations
Online parameter optimization for elastic data stream processing
SoCC '15: Proceedings of the Sixth ACM Symposium on Cloud ComputingElastic scaling allows data stream processing systems to dynamically scale in and out to react to workload changes. As a consequence, unexpected load peaks can be handled and the extent of the overprovisioning can be reduced. However, the strategies ...
Topology-Aware Task Allocation for Distributed Stream Processing with Latency Guarantee
ICAIP '18: Proceedings of the 2nd International Conference on Advances in Image ProcessingNowadays it becomes more and more critical to process the increasingly large amounts of data in timely manner. In order to meet this requirement and ensure the reliable processing of streaming data, a variety of distributed stream processing ...
A distributed backoff-channel deflection algorithm with load balancing for optical burst switching networks
Optical burst contention is one of the major factors that cause the burst loss in the optical burst switching (OBS) networks. So far, various contention resolution schemes have been proposed. Among them, the deflection path is more attractive due to its ...
Comments