Junhua Fang
ABSTRACT
Key-based workload partitioning is a common strategy used in parallel stream processing engines, enabling effective key-value tuple distribution over worker threads in a logical operator. It is likely to generate poor balancing performance when workload variance occurs on the incoming data stream. This paper presents a new key-based workload partitioning framework, with practical algorithms to support dynamic workload assignment for stateful operators. The framework combines hash-based and explicit key-based routing strategies for workload distribution, which specifies the destination worker threads for a handful of keys and assigns the other keys with the hash function. When short-term distribution fluctuations occur to the incoming data stream, the system adaptively updates the routing table containing the chosen keys, in order to rebalance the workload with minimal migration overhead within the stateful operator. We formulate the rebalance operation as an optimization problem, with multiple objectives on minimizing state migration costs, controlling the size of the routing table and breaking workload imbalance among worker threads. Despite of the NP-hardness nature behind the optimization formulation, we carefully investigate and justify the heuristics behind key (re)routing and state migration, to facilitate fast response to workload variance with ignorable cost to the normal processing in the distributed system. Empirical studies on synthetic data and real-world stream applications validate the usefulness of our proposals.
- Apache Storm. In http://storm.apache.org/.Google Scholar
- D. Abadi, Y. Ahmad, M. Balazinska, and et al. 2005. The Design of the Borealis Stream Processing Engine. In CIDR. pages 277--289.Google Scholar
- Y. Ahmad and U. Cetintemel. 2004. Network-aware Query Processing for Stream-based Applications. In VLDB. pages 456--467. Google ScholarDigital Library
- L. Aniello, R. Baldoni, and L. Querzoni. 2013. Adaptive Online Scheduling in Storm. In DEBS. pages 207--218. Google ScholarDigital Library
- T. P. Chen, H. Haussecker, A. Bovyrin, and et al. 2005. Computer Vision Workload Analysis: Case Study of Video Surveillance Systems. Intel Technology Journal 9, 2 (2005).Google Scholar
- D. Dewitt and J. Gray. 1992. Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35, 6 (1992), pages 85--98. Google ScholarDigital Library
- Jianbing Ding, Tom Z. J. Fu, Richard T. B. Ma, Marianne Winslett, Yin Yang, Zhenjie Zhang, and Hongyang Chao. 2015. Optimal Operator State Migration for Elastic Data Stream Processing. CoRR abs/1501.03619 (2015).Google Scholar
- M. Elseidy, A. Elguindy, A. Vitorovic, and C. Koch. 2014. Scalable and Adaptive Online Joins. VLDB 7, 6 (2014), pages 441--452. Google ScholarDigital Library
- Tom Z. J. Fu, Jianbing Ding, Richard T. B. Ma, Marianne Winslett, Yin Yang, and Zhenjie Zhang. 2015a. DRS: dynamic resource scheduling for real-time analytics over fast streams. In Proceedings of the IEEE 35th International Conference on Distributed Computing Systems (ICDCS). pages 411--420.Google ScholarCross Ref
- Tom Z. J. Fu, Jianbing Ding, Richard T. B. Ma, Marianne Winslett, Yin Yang, Zhenjie Zhang, Yong Pei, and Bingbing Ni. 2015b. LiveTraj: Real-Time Trajectory Tracking over Live Video Streams. In Proc. of ACM Multimedia, Demo. pages 777--780. Google ScholarDigital Library
- B. Gedik. 2014. Partitioning Functions for Stateful Data Parallelism in Stream Processing. VLDBJ 23, 4 (2014), pages 517--539. Google ScholarDigital Library
- B. Gedik, S. Schneider, M. Hirzel, and K. Wu. 2014. Elastic Scaling for Data Stream Processing. IEEE Trans. Parallel Distrib. Syst. 25, 6 (2014), pages 1447--1463. Google ScholarDigital Library
- David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. 1997. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In STOC. pages 654--663. Google ScholarDigital Library
- Narendra Karmarkar and Richard M Karp. 1982. An efficient approximation scheme for the one-dimensional bin-packing problem. In Foundations of Computer Science. pages 312--320. Google ScholarDigital Library
- R. Khandekar, K. Hildrum, S. Parekh, D. Rajan, J. Wolf, K. Wu, H. Andrade, and B. Gedik. 2009. COLA: Optimizing Stream Processing Applications via Graph Partitioning. In Middleware. pages 308--327. Google ScholarDigital Library
- S. Kulkarni, N. Bhagat, M. Fu, and et al. 2015. Twitter Heron: Stream Processing at Scale. In SIGMOD. pages 239--250. Google ScholarDigital Library
- Mahendra Kutare, Greg Eisenhauer, Chengwei Wang, Karsten Schwan, Vanish Talwar, and Matthew. Wolf. 2010. Monalytics: Online Monitoring and Analytics for Managing Large Scale Data Centers. In ICAC. pages 141--150. Google ScholarDigital Library
- Y. Kwon, M. Balazinska, B. Howe, and J. Rolia. 2012. Skewtune: Mitigating Skew in Mapreduce Applications. In SIGMOD. pages 25--36. Google ScholarDigital Library
- Q. Lin, B. C. Ooi, Z. Wang, and C. Yu. 2015. Scalable Distributed Stream Join Processing. In SIGMOD. pages 811--825. Google ScholarDigital Library
- M. Nasir, G. Morales, D. Garciasoriano, N. Kourtellis, and M. Serafini. 2015. The Power of Both Choices: Practical Load Balancing for Distributed Stream Processing Engines. In ICDE. pages 137--148.Google Scholar
- 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 ICDE. pages 589--600.Google Scholar
- M. Shah, J. Hellerstein, S. Chandrasekaran, and M. Franklin. 2003. Flux: An Adaptive Partitioning Operator for Continuous Query Systems. In ICDE. pages 25--36.Google Scholar
- A. Toshniwal, S. Taneja, A. Shukla, K. Ramasamy, J.M. Patel, S. Kulkarni, J. Jackson, K. Gade, M. Fu, J. Donham, and et al. 2014. Storm@ twitter. In SIGMOD. pages 147--156. Google ScholarDigital Library
- B. Ufler, N. Augsten, A. Reiser, and A. Kemper. 2012. Load Balancing in MapReduce Based on Scalable Cardinality Estimates. In ICDE. pages 522--533. Google ScholarDigital Library
- C. Walton, A. Dale, and R. Jenevein. 1991. A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins. In VLDB. pages 537--548. Google ScholarDigital Library
- J. Wolf, N. Bansal, K. Hildrum, S. Parekh, D. Rajan, R. Wagle, K. Wu, and L. Fleischer. 2008. SODA: An Optimizing Scheduler for Large-scale Stream-based Distributed Computer Systems. In Middleware. pages 306--325. Google ScholarDigital Library
- Y. Wu and K. Tan. 2015. ChronoStream: Elastic Stateful Stream Computation in the Cloud. In ICDE. pages 723--734.Google Scholar
- Y. Xing, J. Hwang, U. Cetintemel, and S. Zdonik. 2006. Providing Resiliency to Load Variations in Distributed Stream Processing. In VLDB. pages 775--786. Google ScholarDigital Library
- Y. Xing, S. Zdonik, and J. Hwang. 2005. Dynamic Load Distribution in the Borealis Stream Processor. In ICDE. pages 791--802. Google ScholarDigital Library
- Y. Xu, P. Kostamaa, X. Zhou, and L. Chen. 2008. Handling Data Skew in Parallel Joins in Shared-nothing Systems. In SIGMOD. pages 1043--1052. Google ScholarDigital Library
- M. Zaharia, T. Das, H. Li, T. Hunter, S. Shenker, and I. Stoica. 2013. Discretized Streams: Fault-tolerant Streaming Computation at Scale. In SOSP. pages 423--438. Google ScholarDigital Library
- Y. Zhou, B. Ooi, and K. Tan. 2005. Dynamic Load Management for Distributed Continuous Query Systems. In ICDE. pages 322--323. Google ScholarDigital Library
Index Terms
- Parallel Stream Processing Against Workload Skewness and Variance
Recommendations
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 ...
Distributed stream join under workload variance
Flexible and self-adaptive stream join processing plays an important role in a parallel shared-nothing environments. Join-Matrix model is a high-performance model which is resilient to data skew and supports arbitrary join predicates for taking random ...
Priority-Based Resource Scheduling in Distributed Stream Processing Systems for Big Data Applications
UCC '14: Proceedings of the 2014 IEEE/ACM 7th International Conference on Utility and Cloud ComputingDistributed Stream Processing Systems (DSPSs) are attracting increasing industrial and academic interest as flexible tools to implement scalable and cost-effective on-line analytics applications over Big Data streams. Often hosted in private/public ...
Comments