Relaxed-currency serializability for middle-tier caching and replication

ABSTRACT

Many applications, such as e-commerce, routinely use copies of data that are not in sync with the database due to heuristic caching strategies used to enhance performance. We study concurrency control for a transactional model that allows update transactions to read out-of-date copies. Each read operation carries a "freshness constraint" that specifies how fresh a copy must be in order to be read. We offer a definition of correctness for this model and present algorithms to ensure several of the most interesting freshness constraints. We outline a serializability-theoretic correctness proof and present the results of a detailed performance study.

REFERENCES

• 1: Divyakant Agrawal , Amr El Abbadi , Ambuj K. Singh, Consistency and orderability: semantics-based correctness criteria for databases, ACM Transactions on Database Systems (TODS), v.18 n.3, p.460-486, Sept. 1993 [doi>10.1145/155271.155276]
• 2: Rakesh Agrawal , Michael J. Carey , Miron Livny, Concurrency control performance modeling: alternatives and implications, ACM Transactions on Database Systems (TODS), v.12 n.4, p.609-654, Dec. 1987 [doi>10.1145/32204.32220]
• 3: Fuat Akal , Can Türker , Hans-Jörg Schek , Yuri Breitbart , Torsten Grabs , Lourens Veen, Fine-grained replication and scheduling with freshness and correctness guarantees, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 4: Rafael Alonso , Daniel Barbará , Hector Garcia-Molina , Soraya Abad, Quasi-Copies: Efficient Data Sharing for Information Retrieval Systems, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.443-468, March 14-18, 1988
• 5: Daniel Barbará , Hector Garcia-Molina, The Demarcation Protocol: A Technique for Maintaining Linear Arithmetic Constraints in Distributed Database Systems, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.373-388, March 23-27, 1992
• 6: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 7: P. Bernstein, A. Fekete, H. Guo, R. Ramakrishnan, P. Tamma. Relaxed Currency Serializability for Middle-Tier Caching (extended version). Microsoft Research Technical Report, MSR-TR-2006-34, 2006.
• 8: Paul M. Bober , Michael J. Carey, On Mixing Queries and Transactions via Multiversion Locking, Proceedings of the Eighth International Conference on Data Engineering, p.535-545, February 03-07, 1992
• 9: CSIM: http://www.mesquite.com
• 10: Hector Garcia-Molina , Gio Wiederhold, Read-only transactions in a distributed database, ACM Transactions on Database Systems (TODS), v.7 n.2, p.209-234, June 1982 [doi>10.1145/319702.319704]
• 11: D. Gawlick and D. Kinkade. Varieties of Concurrency Control in IMS/VS FastPath. IEEE Database Engg., 1985.
• 12: Hongfei Guo , Per-Åke Larson , Raghu Ramakrishnan, Caching with "good enough" currency, consistency, and completeness, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: Hongfei Guo , Per-Åke Larson , Raghu Ramakrishnan , Jonathan Goldstein, Relaxed currency and consistency: how to say "good enough" in SQL, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007661]
• 14: Theo Harder, Handling hot spot data in DB-sharing systems, Information Systems, v.13 n.2, p.155-166, May 1988 [doi>10.1016/0306-4379(88)90012-9]
• 15: Yixiu Huang , Robert H. Sloan , Ouri Wolfson, Divergence caching in client-server architectures, Proceedings of the third international conference on on Parallel and distributed information systems, p.131-139, October 1994, Autin, Texas, United States
• 16: H.F. Korth, W. Kim and F. Bancilhon, A Model of CAD Transactions. VLDB, 1985.
• 17: Henry F. Korth , Greg Speegle, Formal aspects of concurrency control in long-duration transaction systems using the NT/PV model, ACM Transactions on Database Systems (TODS), v.19 n.3, p.492-535, Sept. 1994 [doi>10.1145/185827.185854]
• 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: Patrick E. O'Neil, The Escrow transactional method, ACM Transactions on Database Systems (TODS), v.11 n.4, p.405-430, Dec. 1986 [doi>10.1145/7239.7265]
• 20: 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
• 21: Calton Pu , Miu K. Tsang , Kun-Lung Wu , Philip S. Yu, Multiversion divergence control of time fuzziness, Proceedings of the third international conference on Information and knowledge management, p.195-202, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191278]
• 22: Krithi Ramamritham , Calton Pu, A Formal Characterization of Epsilon Serializability, IEEE Transactions on Knowledge and Data Engineering, v.7 n.6, p.997-1007, December 1995 [doi>10.1109/69.476504]
• 23: Krithi Ramamritham , Sang H. Son , Lisa Cingiser Dipippo, Real-Time Databases and Data Services, Real-Time Systems, v.28 n.2-3, p.179-215, November-December 2004 [doi>10.1023/B:TIME.0000045317.37980.a5]
• 24: Rajeev Rastogi , Sharad Mehrotra , Yuri Breitbart , Henry F. Korth , Avi Silberschatz, On correctness of nonserializable executions, Journal of Computer and System Sciences, v.56 n.1, p.68-82, Feb. 1998 [doi>10.1006/jcss.1997.1536]
• 25: U. Röhm, K. Böhm, H. Schek, and H. Schuldt. FAS-A Freshness Sensitive Coordination Middleware for a Cluster of OLAP Components. VLDB, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

Keywords:
caching, database, freshness constraint, replication, serializability, transaction