Flexible time management in data stream systems

ABSTRACT

Continuous queries in a Data Stream Management System (DSMS) rely on time as a basis for windows on streams and for defining a consistent semantics for multiple streams and updatable relations. The system clock in a centralized DSMS provides a convenient and well-behaved notion of time, but often it is more appropriate for a DSMS application to define its own notion of time---its own clock(s), sequence numbers, or other forms of ordering and times-tamping. Flexible application-defined time poses challenges to the DSMS, since streams may be out of order and uncoordinated with each other, they may incur latency reaching the DSMS, and they may pause or stop. We formalize these challenges and specify how to generate heartbeats so that queries can be evaluated correctly and continuously in an application-defined time domain. Our heartbeat generation algorithm is based on parameters capturing skew between streams, unordering within streams, and latency in streams reaching the DSMS. We also describe how to estimate these parameters at run-time, and we discuss how heartbeats can be used for processing continuous queries.

REFERENCES

• 1: A. Arasu, S. Babu, and J. Widom. CQL: A Language for Continuous Queries over Streams and Relations. In Proc. of the Ninth Intl. Conf. on Database Programming Languages, September 2003.
• 2: Brian Babcock , Shivnath Babu , Rajeev Motwani , Mayur Datar, Chain: operator scheduling for memory minimization in data stream systems, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872789]
• 3: S. Babu, U. Srivastava, and J. Widom. Exploiting k-constraints to reduce memory overhead in continuous queries over data streams. Technical report, Stanford University Database Group, November 2002. Available at http://dbpubs.stanford.edu/pub/2002--52.
• 4: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 5: Jean-Chrysotome Bolot, End-to-end packet delay and loss behavior in the internet, Conference proceedings on Communications architectures, protocols and applications, p.289-298, September 13-17, 1993, San Francisco, California, United States
• 6: S. Chandrasekaran, S. Krishnamurthy, et al. Windows Explained, Windows Expressed. Available at http://www.cs.berkeley.edu/~sirish/research/ streaquel.pdf.
• 7: 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
• 8: C. Cranor, T. Johnson, O. Spatscheck, and V. Shkapenyuk. The Gigascope Stream Database. IEEE Data Engineering Bulletin, 26(1):27--32, March 2003.
• 9: M. Garey, R. Graham, and D. Johnson. Performance guarantees for scheduling algorithms. Operations Research, 26(1):3--21, January 1978.
• 10: J. Gehrke. Special issue on data stream processing. IEEE Data Engineering Bulletin, 26(1), March 2003.
• 11: Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003 [doi>10.1145/776985.776986]
• 12: S. Krishnamurthy, S. Chandrasekaran, et al. TelegraphCQ: An Architectural Status Report. IEEE Data Engineering Bulletin, 26(1):11--18, March 2003.
• 13: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 14: A. Mukherjee. On the dynamics and significance of low-frequency components of internet load. Internetworking: Research and Experience, 5(4):163--205, December 1994.
• 15: Krithi Ramamritham, Real-time databases, Distributed and Parallel Databases, v.1 n.2, p.199-226, April 1993 [doi>10.1007/BF01264051]
• 16: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, Sequence query processing, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.430-441, May 24-27, 1994, Minneapolis, Minnesota, United States
• 17: Richard Snodgrass , Ilsoo Ahn, A taxonomy of time databases, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.236-246, May 1985, Austin, Texas, United States
• 18: SQR A Stream Query Repository. http://www-db.stanford.edu/stream/sqr.
• 19: The STREAM Group. STREAM: The Stanford Stream Data Manager. IEEE Data Engineering Bulletin, 26(1):19--26, March 2003.
• 20: Peter A. Tucker , David Maier , Tim Sheard , Leonidas Fegaras, Exploiting Punctuation Semantics in Continuous Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.555-568, March 2003 [doi>10.1109/TKDE.2003.1198390]
• 21: S. Zdonik, M. Stonebraker, et al. The Aurora and Medusa Projects. IEEE Data Engineering Bulletin, 26(1):3--10, March 2003.