Best-effort cache synchronization with source cooperation

ABSTRACT

In environments where exact synchronization between source data objects and cached copies is not achievable due to bandwidth or other resource constraints, stale (out-of-date) copies are permitted. It is desirable to minimize the overall divergence between source objects and cached copies by selectively refreshing modified objects. We call the online process of selecting which objects to refresh in order to minimize divergence best-effort synchronization. In most approaches to best-effort synchronization, the cache coordinates the process and selects objects to refresh. In this paper, we propose a best-effort synchronization scheduling policy that exploits cooperation between data sources and the cache. We also propose an implementation of our policy that incurs low communication overhead even in environments with very large numbers of sources. Our algorithm is adaptive to wide fluctuations in available resources and data update rates. Through experimental simulation over synthetic and real-world data, we demonstrate the effectiveness of our algorithm, and we quantify the significant decrease in divergence achievable with source cooperation.

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: Brad Adelberg , Ben Kao , Hector Garcia-Molina, Database Support for Efficiently Maintaining Derived Data, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.223-240, March 25-29, 1996
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 4: Gerth Stølting Brodal , Jesper Larsson Träff , Christos D. Zaroliagis, A parallel priority queue with constant time operations, Journal of Parallel and Distributed Computing, v.49 n.1, p.4-21, Feb. 1998 [doi>10.1006/jpdc.1998.1425]
• 5: M. Cherniack, M. J. Franklin, and S. Zdonik. Expressing user profiles for data recharging. IEEE Personal Communications: Special Issue on Pervasive Computing, 8(4):32-38, Aug. 2001.
• 6: J. Cho and H. Garcia-Molina. Estimating frequency of change. Technical report, Stanford University Computer Science Department, 2000. http://dbpubs.stanford.edu/pub/2000-4.
• 7: 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
• 8: E. Cohen and H. Kaplan. Refreshment policies for web content caches. In Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), Anchorage, Alaska, Apr. 2001.
• 9: Pavan Deolasee , Amol Katkar , Ankur Panchbudhe , Krithi Ramamritham , Prashant Shenoy, Adaptive push-pull: disseminating dynamic web data, Proceedings of the 10th international conference on World Wide Web, p.265-274, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372066]
• 10: Lyman Do , Prabhu Ram , Pamela Drew, The need for distributed asynchronous transactions, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.534-535, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 11: T. Dorcey. CU-SeeMe desktop videoconferencing software. Connexions, 9(3), Mar. 1995.
• 12: D. Estrin, L. Girod, G. Pottie, and M. Srivastava. Instrumenting the world with wireless sensor networks. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2001), Salt Lake City, Utah, May 2001.
• 13: Avigdor Gal , Jonathan Eckstein, Managing periodically updated data in relational databases: a stochastic modeling approach, Journal of the ACM (JACM), v.48 n.6, p.1141-1183, November 2001 [doi>10.1145/504794.504797]
• 14: Richard A. Golding , Darrell D. E. Long, MODELING REPLICA DIVERGENCE IN A WEAK-CONSISTENCY PROTOCOL FOR GLOBAL-SCALE DISTRIBUTED DATA BASES, University of California at Santa Cruz, Santa Cruz, CA, 1993
• 15: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 16: 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
• 17: M. J. McPhaden. Tropical Atmosphere Ocean Project, Pacific Marine Environmental Laboratory, 2001. http://www.pmel.noaa.gov/tao/.
• 18: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.355-366, May 21-24, 2001, Santa Barbara, California, United States
• 19: Chris Olston , Jennifer Widom, Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data, Proceedings of the 26th International Conference on Very Large Data Bases, p.144-155, September 10-14, 2000
• 20: C. Olston and J. Widom. Best-effort cache synchronization with source cooperation. Technical report, Stanford University Computer Science Department, 2001. http://dbpubs.stanford.edu/pub/2001-43.
• 21: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 22: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.377-386, May 29-31, 1991, Denver, Colorado, United States
• 23: Krithi Ramamritham, Real-time databases, Distributed and Parallel Databases, v.1 n.2, p.199-226, April 1993 [doi>10.1007/BF01264051]
• 24: G. Salton and C. S. Yang. On the specification of term values in automatic indexing. Journal of Documentation, 29:351-372, 1973.
• 25: Peter Sanders, Randomized priority queues for fast parallel access, Journal of Parallel and Distributed Computing, v.49 n.1, p.86-97, Feb. 1998 [doi>10.1006/jpdc.1998.1429]
• 26: J. Stewart. Calculus: Early Transcendentals, Second Edition. Brooks/Cole, 1991.
• 27: Maintaining Mutual Consistency for Cached Web Objects, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.371, April 16-19, 2001
• 28: H. Yu and A. Vahdat. Design and evaluation of a continuous consistency model for replicated services. In Proceedings of the Fourth Symposium on Operating Systems Design and Implementation, San Diego, California, Oct. 2000.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Data sharing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Documentation, Theory