Potential-driven load distribution for distributed data stream processing

ABSTRACT

A large class of applications require real-time processing of continuous stream data resulting in the development of data stream management systems (DSMS). Since many of these applications are distributed, distributed DSMSs are starting to receive attention. In this paper, we focus on an important issue in distributed DSMS operation, namely load distribution to minimize end-to-end latency. We identify the often conflicting requirements of load distribution, and propose a "potential-driven" load distribution approach to mimic the movements of objects in the physical world. Our approach also takes into account heterogeneous machines, different network conditions, and resource constraints. We present experimental results that investigate our algorithms from various aspects, and show that they outperform existing techniques in terms of end-to-end latency.

REFERENCES

• 1: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 2: D. J. Abadi et al. The design of the borealis stream processing engine. In CIDR, 2005.
• 3: Yanif Ahmad , Uğur Çetintemel, Network-aware query processing for stream-based applications, Proceedings of the Thirtieth international conference on Very large data bases, p.456-467, August 31-September 03, 2004, Toronto, Canada
• 4: S. Chandrasekaran et al. TelegraphCQ: Continuous dataflow processing for an uncertain world. In CIDR, 2003.
• 5: X. Gu, P. S. Yu, and H. Wang. Adaptive load diffusion for multiway windowed stream joins. In ICDE, 2007.
• 6: R. Motwani et al. Query processing, approximation, and resource management in a data stream management system. In CIDR, 2003.
• 7: Peter Pietzuch , Jonathan Ledlie , Jeffrey Shneidman , Mema Roussopoulos , Matt Welsh , Margo Seltzer, Network-Aware Operator Placement for Stream-Processing Systems, Proceedings of the 22nd International Conference on Data Engineering, p.49, April 03-07, 2006 [doi>10.1109/ICDE.2006.105]
• 8: M. A. Shah, J. M. Hellerstein, S. Chandrasekaran, and M. J. Franklin. Flux: An adaptive partitioning operator for continuous query systems. In ICDE, 2003.
• 9: Utkarsh Srivastava , Kamesh Munagala , Jennifer Widom, Operator placement for in-network stream query processing, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065199]
• 10: Y. Xing. Load distribution for distributed stream processing. In EDBT Ph.D. Workshop, 2004.
• 11: Ying Xing , Stan Zdonik , Jeong-Hyon Hwang, Dynamic Load Distribution in the Borealis Stream Processor, Proceedings of the 21st International Conference on Data Engineering, p.791-802, April 05-08, 2005 [doi>10.1109/ICDE.2005.53]
• 12: Ying Xing , Jeong-Hyon Hwang , Uǧur Çetintemel , Stan Zdonik, Providing resiliency to load variations in distributed stream processing, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 13: Yongluan Zhou , Beng Chin Ooi , Kian-Lee Tan, Dynamic Load Management for Distributed Continuous Query Systems, Proceedings of the 21st International Conference on Data Engineering, p.322-323, April 05-08, 2005 [doi>10.1109/ICDE.2005.54]
• 14: Y. Zhou, B. C. Ooi, K.-L. Tan, and J. Wu. Efficient dynamic operator placement in a locally distributed continuous query system. In LNCS 4275, OTM, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Performance

Keywords:
data streams, distributed systems, load balancing