Transactional client-server cache consistency: alternatives and performance

ABSTRACT

Client-server database systems based on a data shipping model can exploit client memory resources by caching copies of data items across transaction boundaries. Caching reduces the need to obtain data from servers or other sites on the network. In order to ensure that such caching does not result in the violation of transaction semantics, a transactional cache consistency maintenance algorithm is required. Many such algorithms have been proposed in the literature and, as all provide the same functionality, performance is a primary concern in choosing among them. In this article we present a taxonomy that describes the design space for transactional cache consistency maintenance algorithms and show how proposed algorithms relate to one another. We then investigate the performance of six of these algorithms, and use these results to examine the tradeoffs inherent in the design choices identified in the taxonomy. The results show that the interactions among dimensions of the design space impact performance in many ways, and that classifications of algorithms as simply “pessimistic” or “optimistic” do not accurately characterize the similarities and differences among the many possible cache consistency algorithms.

REFERENCES

• 1: ADVE, S. AND GHARACHORLOO, K. 1995. Shared memory consistency models: A tutorial. Tech. Rep. 95/7 (Sept.), Digital Western Research Laboratory.
• 2: Atul Adya , Robert Gruber , Barbara Liskov , Umesh Maheshwari, Efficient optimistic concurrency control using loosely synchronized clocks, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.23-34, May 22-25, 1995, San Jose, California, United States
• 3: A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 4: Peter A. Alsberg , John D. Day, A principle for resilient sharing of distributed resources, Proceedings of the 2nd international conference on Software engineering, p.562-570, October 13-15, 1976, San Francisco, California, United States
• 5: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 6: Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
• 7: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 8: Anupam Bhide, An Analysis of Three Transaction Processing Architectures, Proceedings of the 14th International Conference on Very Large Data Bases, p.339-350, August 29-September 01, 1988
• 9: Paul Butterworth , Allen Otis , Jacob Stein, The GemStone object database management system, Communications of the ACM, v.34 n.10, p.64-77, Oct. 1991 [doi>10.1145/125223.125254]
• 10: Michael J. Carey , David J. DeWitt , Jeffrey F. Naughton, The 007 Benchmark, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.12-21, May 25-28, 1993, Washington, D.C., United States
• 11: Michael J. Carey , Michael J. Franklin , Markos Zaharioudakis, Fine-grained sharing in a page server OODBMS, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.359-370, May 24-27, 1994, Minneapolis, Minnesota, United States
• 12: Michael J. Carey , Miron Livny, Conflict detection tradeoffs for replicated data, ACM Transactions on Database Systems (TODS), v.16 n.4, p.703-746, Dec. 1991 [doi>10.1145/115302.115289]
• 13: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 14: Michael J. Carey , Michael J. Franklin , Miron Livny , Eugene J. Shekita, Data caching tradeoffs in client-server DBMS architectures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.357-366, May 29-31, 1991, Denver, Colorado, United States
• 15: R. G. Cattell, Object Data Management: Object-Oriented and Extended, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 16: R. G. G. Cattell , J. Skeen, Object operations benchmark, ACM Transactions on Database Systems (TODS), v.17 n.1, p.1-31, March 1992 [doi>10.1145/128765.128766]
• 17: S. Iris Chu , Marianne Winslett, Minipage locking support for object-oriented page-server DBMS, Proceedings of the third international conference on Information and knowledge management, p.171-178, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191274]
• 18: Asit Dan , Daniel M. Dias , Philip S. Yu, The effect of skewed data access on buffer hits and data contention in a data sharing environment, Proceedings of the sixteenth international conference on Very large databases, p.418-431, September 1990, Brisbane, Australia
• 19: Asit Dan , Daniel M. Dias , Philip S. Yu, Analytical modelling of a hierarchical buffer for a data sharing environment, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.156-167, May 21-24, 1991, San Diego, California, United States
• 20: DAN, A. AND YU, P. S. 1991. Performance comparisons of buffer coherency policies. In Proceedings 11th International Conference on Distributed Computing Systems (Arlington, TX, May).
• 21: Asit Dan , Philip S. Yu, Performance analysis of coherency control policies through lock retention, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.114-123, June 02-05, 1992, San Diego, California, United States
• 22: Susan B. Davidson , Hector Garcia-Molina , Dale Skeen, Consistency in a partitioned network: a survey, ACM Computing Surveys (CSUR), v.17 n.3, p.341-370, Sept. 1985 [doi>10.1145/5505.5508]
• 23: David J. DeWitt , Philippe Futtersack , David Maier , Fernando Velez, A study of three alternative workstation server architectures for object-oriented database systems, Proceedings of the sixteenth international conference on Very large databases, p.107-121, September 1990, Brisbane, Australia
• 24: Daniel M. Dias , Balakrishna R. Iyer , John T. Robinson , Philip S. Yu, Design and Analysis of Integrated Concurrency-Coherence Controls, Proceedings of the 13th International Conference on Very Large Data Bases, p.463-471, September 01-04, 1987
• 25: EXODUS PROJECT GROUP. 1993. Exodus storage manager architectural overview. Computer Sciences Dept., Univ. of Wisconsin-Madison.
• 26: Michael Jay Franklin, Caching and memory management in client-server database systems, University of Wisconsin at Madison, Madison, WI, 1993
• 27: FRANKLIN, M. J. AND CAREY, M. 1992. Client-server caching revisited. In Proceedings International Workshop on Distributed Object Management (Edmonton, Canada, May), 57-78. (Published as Distributed Object Management, Ozsu, Dayal, Vaduriez, Eds., Morgan Kaufmann, San Mateo, CA, 1994.).
• 28: Michael J. Franklin , Michael J. Carey , Miron Livny, Global Memory Management in Client-Server Database Architectures, Proceedings of the 18th International Conference on Very Large Data Bases, p.596-609, August 23-27, 1992
• 29: Michael J. Franklin , Michael J. Carey , Miron Livny, Local Disk Caching for Client-Server Database Systems, Proceedings of the 19th International Conference on Very Large Data Bases, p.641-655, August 24-27, 1993
• 30: Michael J. Franklin , Michael J. Zwilling , C. K. Tan , Michael J. Carey , David J. DeWitt, Crash recovery in client-server EXODUS, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.165-174, June 02-05, 1992, San Diego, California, United States
• 31: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 32: James R. Goodman, Using cache memory to reduce processor-memory traffic, Proceedings of the 10th annual international symposium on Computer architecture, p.124-131, June 13-17, 1983, Stockholm, Sweden
• 33: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 34: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 35: Ashok M. Joshi, Adaptive Locking Strategies in a Multi-node Data Sharing Environment, Proceedings of the 17th International Conference on Very Large Data Bases, p.181-191, September 03-06, 1991
• 36: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 37: Alfons Kemper , Donald Kossmann, Dual-Buffering Strategies in Object Bases, Proceedings of the 20th International Conference on Very Large Data Bases, p.427-438, September 12-15, 1994
• 38: W. Kim , J. F. Garza , N. Ballou , D. Woelk, Architecture of the ORION Next-Generation Database System, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.109-124, March 1990 [doi>10.1109/69.50909]
• 39: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.213-225, October 13-16, 1991, Pacific Grove, California, United States
• 40: Charles Lamb , Gordon Landis , Jack Orenstein , Dan Weinreb, The ObjectStore database system, Communications of the ACM, v.34 n.10, p.50-63, Oct. 1991 [doi>10.1145/125223.125244]
• 41: LAMPORT, L. 1979. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28, 9, 690-691.
• 42: Eliezer Levy , Abraham Silberschatz, Distributed file systems: concepts and examples, ACM Computing Surveys (CSUR), v.22 n.4, p.321-374, Dec. 1990 [doi>10.1145/98163.98169]
• 43: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 44: David J. Lilja, Cache coherence in large-scale shared-memory multiprocessors: issues and comparisons, ACM Computing Surveys (CSUR), v.25 n.3, p.303-338, Sept. 1993 [doi>10.1145/158439.158907]
• 45: LISKOV, B., DAY, M., AND SHRIRA, L. 1992. Distributed object management in Thor. In Proceedings International Workshop on Distributed Object Management (Edmonton, Canada, May), 79-91. (Published as Distributed Object Management, Ozsu, Dayal, Vaduriez, Eds., Morgan Kaufmann, San Mateo, CA, 1994.).
• 46: LIVNY, M. 1990. Denet user's guide, version 1.5. Computer Sciences Dept., University of Wisconsin-Madison.
• 47: David Lomet, Private locking and distributed cache management, Proceedings of the third international conference on on Parallel and distributed information systems, p.151-159, October 1994, Autin, Texas, United States
• 48: C. Mohan , Inderpal Narang, Recovery and Coherency-Control Protocols for Fast Intersystem Page Transfer and Fine-Granularity Locking in a Shared Disks Transaction Environment, Proceedings of the 17th International Conference on Very Large Data Bases, p.193-207, September 03-06, 1991
• 49: Michael N. Nelson , Brent B. Welch , John K. Ousterhout, Caching in the Sprite network file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.134-154, Feb. 1988 [doi>10.1145/35037.42183]
• 50: Bill Nitzberg , Virginia Lo, Distributed Shared Memory: A Survey of Issues and Algorithms, Computer, v.24 n.8, p.52-60, August 1991 [doi>10.1109/2.84877]
• 51: O. Deux, The O2 system, Communications of the ACM, v.34 n.10, p.34-48, Oct. 1991 [doi>10.1145/125223.125238]
• 52: OBJECTIVITY INC. 1991. Objectivity/DB Documentation V 1.
• 53: ONTOS INC. 1992. Ontos DB 2.2 Reference Manual.
• 54: RAHM, E. 1991. Concurrency and coherency control in database sharing systems. Tech. Rep. 3/91 (Nov.), Computer Science Dept., Univ. of Kaiserslautern, Germany.
• 55: Erhard Rahm, Empirical performance evaluation of concurrency and coherency control protocols for database sharing systems, ACM Transactions on Database Systems (TODS), v.18 n.2, p.333-377, June 1993 [doi>10.1145/151634.151639]
• 56: K. K. Ramakrishnan , Prabuddha Biswas , Ramakrishna Karedla, Analysis of file I/O traces in commercial computing environments, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.78-90, June 01-05, 1992, Newport, Rhode Island, United States
• 57: Harjinder S. Sandhu , Songnian Zhou, Cluster-based file replication in large-scale distributed systems, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.91-102, June 01-05, 1992, Newport, Rhode Island, United States
• 58: Per Stenström, A Survey of Cache Coherence Schemes for Multiprocessors, Computer, v.23 n.6, p.12-24, June 1990 [doi>10.1109/2.55497]
• 59: STONEBRAKER, M. 1979. Concurrency control and consistency of multiple copies of data in distributed INGRES. IEEE Trans. Softw. Eng. 5, 3 (May), 188-194.
• 60: H. Sturgis , J. Mitchell , J. Israel, Issues in the design and use of a distributed file system, ACM SIGOPS Operating Systems Review, v.14 n.3, p.55-69, July 1980 [doi>10.1145/850697.850705]
• 61: VERSANT OBJECT TECHNOLOGY. 1991. VERSANT system reference manual, release 1.6.
• 62: Yongdong Wang , Lawrence A. Rowe, Cache consistency and concurrency control in a client/server DBMS architecture, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.367-376, May 29-31, 1991, Denver, Colorado, United States
• 63: Kevin Wilkinson , Marie-Anne Neitmat, Maintaining consistency of client-cached data, Proceedings of the sixteenth international conference on Very large databases, p.122-134, September 1990, Brisbane, Australia

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

Additional Classification:
  C. Computer Systems Organization

  D. Software
  D.4 OPERATING SYSTEMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

General Terms:
Algorithms, Design, Performance