Scheduling to minimize staleness and stretch in real-time data warehouses

ABSTRACT

We study scheduling algorithms for loading data feeds into real time data warehouses, which are used in applications such as IP network monitoring, online financial trading, and credit card fraud detection. In these applications, the warehouse collects a large number of streaming data feeds that are generated by external sources and arrive asynchronously. Data for each table are generated at a constant rate, different tables possibly at different rates. For each data feed, the arrival of new data triggers an update that seeks to append the new data to the corresponding table; if multiple updates are pending for the same table, they are batched together before being loaded. At time τ, if a table has been updated with information up to time r≤τ, its staleness is defined as τ--r.

Our first objective is to schedule the updates on one or more processors in a way that minimizes the total staleness. In order to ensure fairness, our second objective is to limit the maximum "stretch", which we define (roughly) as the ratio between the duration of time an update waits till it is finished being processed, and the length of the update.

In contrast to earlier work proving the nonexistence of constant-competitive algorithms for related scheduling problems, we prove that any online nonpreemptive algorithm, no processor of which is ever voluntarily idle, incurs a staleness at most a constant factor larger than an obvious lower bound on total staleness (provided that the processors are sufficiently fast). We give a constant-stretch algorithm, provided that the processors are sufficiently fast, for the quasiperiodic model, in which tables can be clustered into a few groups such that the update frequencies within each group vary by at most a constant factor. Finally, we show that our constant-stretch algorithm is also constant-competitive (subject to the same proviso on processor speed) in the quasiperiodic model with respect to total weighted staleness, where tables are assigned weights that reflect their priorities.

REFERENCES

• 1: B. Adelberg , H. Garcia-Molina , B. Kao, Applying update streams in a soft real-time database system, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.245-256, May 22-25, 1995, San Jose, California, United States
• 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: Nikhil Bansal , Avrim Blum, Algorithms for flow time scheduling, Carnegie Mellon University, Pittsburgh, PA, 2003
• 4: Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
• 5: Don Carney , Uğur Çetintemel , Alex Rasin , Stan Zdonik , Mitch Cherniack , Mike Stonebraker, Operator scheduling in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.838-849, September 09-12, 2003, Berlin, Germany
• 6: Junghoo Cho , Hector Garcia-Molina, Synchronizing a database to improve freshness, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.117-128, May 15-18, 2000, Dallas, Texas, United States
• 7: Lukasz Golab , Theodore Johnson , J. Spencer Seidel , Vladislav Shkapenyuk, Stream warehousing with DataDepot, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA [doi>10.1145/1559845.1559934]
• 8: Lukasz Golab , Theodore Johnson , Vladislav Shkapenyuk, Scheduling Updates in a Real-Time Stream Warehouse, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1207-1210, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.202]
• 9: Moustafa A. Hammad , Michael J. Franklin , Walid G. Aref , Ahmed K. Elmagarmid, Scheduling for shared window joins over data streams, Proceedings of the 29th international conference on Very large data bases, p.297-308, September 09-12, 2003, Berlin, Germany
• 10: Ben Kao , Héctor García-Molina, An overview of real-time database systems, Advances in real-time systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 11: Wilburt Juan Labio , Ramana Yerneni , Hector Garcia-Molina, Shrinking the warehouse update Window, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.383-394, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 12: Alexandros Labrinidis , Nick Roussopoulos, Update Propagation Strategies for Improving the Quality of Data on the Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.391-400, September 11-14, 2001
• 13: N. Polyzotis, S. Skiadopoulos, P. Vassiliadis, A. Simitsis, and N.-E. Frantzell, Supporting Streaming Updates in an Active Data Warehouse, ICDE 2007, 476--485.
• 14: Mohamed A. Sharaf , Panos K. Chrysanthis , Alexandros Labrinidis , Kirk Pruhs, Algorithms and metrics for processing multiple heterogeneous continuous queries, ACM Transactions on Database Systems (TODS), v.33 n.1, p.1-44, March 2008 [doi>10.1145/1331904.1331909]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

General Terms:
Algorithms, Theory

Keywords:
competitive analysis, data warehouse maintenance, on-line scheduling