Query-aware partitioning for monitoring massive network data streams

ABSTRACT

Data Stream Management Systems (DSMS) are gaining acceptance for applications that need to process very large volumes of data in real time. The load generated by such applications frequently exceeds by far the computation capabilities of a single centralized server. In particular, a single-server instance of our DSMS, Gigascope, cannot keep up with the processing demands of the new OC-786 networks, which can generate more than 100 million packets per second. In this paper, we explore a mechanism for the distributed processing of very high speed data streams.

Existing distributed DSMSs employ two mechanisms for distributing the load across the participating machines: partitioning of the query execution plans and partitioning of the input data stream in a query-independent fashion. However, for a large class of queries, both approaches fail to reduce the load as compared to centralized system, and can even lead to an increase in the load. In this paper we present an alternative approach - query-aware data stream partitioning that allows for more efficient scaling. We present methods for analyzing any given query set and choose the optimal partitioning scheme, and show how to reconcile potentially conflicting requirements that different queries might place on partitioning. We conclude with experiments on a small cluster of processing nodes on high-rate network traffic feed that demonstrates with different query sets that our methods effectively distribute the load across all processing nodes and facilitate efficient scaling whenever more processing nodes becomes available.

REFERENCES

• 1: D. J. Abadi et al. The Design of the Borealis Stream Processing Engine, CIDR 2005.
• 2: 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]
• 3: Daniel J. Abadi , Wolfgang Lindner , Samuel Madden , Jörg Schuler, An integration framework for sensor networks and data stream management systems, Proceedings of the Thirtieth international conference on Very large data bases, p.1361-1364, August 31-September 03, 2004, Toronto, Canada
• 4: A. Arasu et al. STREAM: The Stanford stream data manager. IEEE Data Engineering Bulletin, 26(1):19--26, 2003.
• 5: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 6: Magdalena Balazinska , Hari Balakrishnan , Mike Stonebraker, Contract-based load management in federated distributed systems, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.15-15, March 29-31, 2004, San Francisco, California
• 7: S. Chandrasekaran et al. TelegraphCQ: Continuous dataflow processing for an uncertain world. CIDR 2003.
• 8: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 9: M. Cherniack, H. Balakrishnan, M. Balazinska, D. Carney, U. Cetintemel, Y. Xing, and S. Zdonik. Scalable Distributed Stream Processing. CIDR 2003.
• 10: Graham Cormode , Theodore Johnson , Flip Korn , S. Muthukrishnan , Oliver Spatscheck , Divesh Srivastava, Holistic UDAFs at streaming speeds, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007575]
• 11: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 12: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 13: Milena Ivanova , Tore Risch, Customizable parallel execution of scientific stream queries, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 14: Ramana Rao Kompella , Sumeet Singh , George Varghese, On scalable attack detection in the network, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028812]
• 15: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 16: Data Reduction by Partial Preaggregation, Proceedings of the 18th International Conference on Data Engineering, p.706, February 26-March 01, 2002
• 17: Jin Li , David Maier , Kristin Tufte , Vassilis Papadimos , Peter A. Tucker, No pane, no gain: efficient evaluation of sliding-window aggregates over data streams, ACM SIGMOD Record, v.34 n.1, March 2005 [doi>10.1145/1058150.1058158]
• 18: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 19: Jun Rao , Chun Zhang , Nimrod Megiddo , Guy Lohman, Automating physical database design in a parallel database, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564757]
• 20: M. A. Shah, J. M. Hellerstein, S. Chandrasekaran, M. J. Franklin. Flux: An Adaptive Partitioning Operator for Continuous Query Systems. ICDE 2003
• 21: Mark Sullivan , Andrew Heybey, Tribeca: a system for managing large databases of network traffic, Proceedings of the annual conference on USENIX Annual Technical Conference, p.2-2, June 15-19, 1998, New Orleans, Louisiana

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
data streams, partitioning, query optimization