Highly concurrent cache consistency for indices in client-server database systems

ABSTRACT

In this paper, we present four approaches to providing highly concurrent B+-tree indices in the context of a data-shipping, client-server OODBMS architecture. The first performs all index operations at the server, while the other approaches support varying degrees of client caching and usage of index pages. We have implemented the four approaches, as well as the 2PL approach, in the context of the SHORE OODB system at Wisconsin, and we present experimental results from a performance study based on running SHORE on an IBM SP2 multicomputer. Our results emphasize the need for non-2PL approaches and demonstrate the tradeoffs between 2PL, no-caching, and the three caching alternatives.

REFERENCES

• Basu95: J. Basu, A. Keller, "Centralized Versus Distributed Index Management in a Page Server OODBMS", Unpublished Manuscript, October 1995.
• Baye77: R. Bayer, M. Schkolnick, "Concurrency of Operations on B-Trees", A cta Informatica, Vo}. 9, No. 1, 1977.
• Care91: 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
• Care94: 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
• Fran92: M. Franklin, M. Carey, "Client-Server Caching Revisited", Proc. Int'l Workshop on Distributed Object Mgmt., Edmonton, Canada, Aug. 1992.
• Gott96: Vibby Gottemukkala , Edward Omiecinski , Umakishore Ramachandran, Relaxed Index Consistency for a Client-Server Database, Proceedings of the Twelfth International Conference on Data Engineering, p.352-361, February 26-March 01, 1996
• Howa88: 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]
• Lamb91: 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]
• Lehm81: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• Lome93: D. Lomet, "Key Range Locking Strategies for Improved Concurrency", Digital Equipment Corporation, Feb. 1993.
• Moha89: C. Mohan, F. Levine, UARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging", IBM Research Report RJ 6846, IBM Almaden, 1989.
• Moha90: C. Mohan, ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes, Proceedings of the sixteenth international conference on Very large databases, p.392-405, September 1990, Brisbane, Australia
• Moha91: 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
• Moha95: C. Mohan, I. Narang, "Locking and Latching Techniques for Transaction Processing Systems Supporting the Shared Disks Architecture" Unpublished Manuscript, February 1995.
• Sagi86: Yehoshua Sagiv, Concurrent operations on B*-trees with overtaking, Journal of Computer and System Sciences, v.33 n.2, p.275-296, Oct. 1986 [doi>10.1016/0022-0000(86)90021-8]
• Shas88: Dennis Shasha , Nathan Goodman, Concurrent search structure algorithms, ACM Transactions on Database Systems (TODS), v.13 n.1, p.53-90, March 1988 [doi>10.1145/42201.42204]
• Wang91: 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
• Wilk90: 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
• Zaha96: Markos Zaharioudakis , Michael J. Carey , Michael J. Franklin, Adaptive, fine-grained sharing in a client-server OODBMS: a callback-based approach, ACM Transactions on Database Systems (TODS), v.22 n.4, p.570-627, Dec. 1997 [doi>10.1145/278245.278249]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory