Efficient optimistic concurrency control using loosely synchronized clocks

ABSTRACT

This paper describes an efficient optimistic concurrency control scheme for use in distributed database systems in which objects are cached and manipulated at client machines while persistent storage and transactional support are provided by servers. The scheme provides both serializability and external consistency for committed transactions; it uses loosely synchronized clocks to achieve global serialization. It stores only a single version of each object, and avoids maintaining any concurrency control information on a per-object basis; instead, it tracks recent invalidations on a per-client basis, an approach that has low in-memory space overhead and no per-object disk overhead. In addition to its low space overheads, the scheme also performs well. The paper presents a simulation study that compares the scheme to adaptive callback locking, the best concurrency control scheme for client-server object-oriented database systems studied to date. The study shows that our scheme outperforms adaptive callback locking for low to moderate contention workloads, and scales better with the number of clients. For high contention workloads, optimism can result in a high abort rate; the scheme presented here is a first step toward a hybrid scheme that we expect to perform well across the full range of workloads.

REFERENCES

• 1: Adya, A, Transaction Management for Mobile Objects Using Optimistic Concurrency Control, Massachusetts Institute of Technology, Cambridge, MA, 1994
• 2: D. Agrawal, A. J. Bemstein, P. Gupta, and S. Sengupta. Distributed Multi-version Optimistic Concurrency Control with Reduced Rollback. Distributed Computing, 2(1), 1987.
• 3: 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]
• 4: 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
• 5: 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
• 6: S. Ceil and S. Owicki. On the Use of Optimistic Methods for Concurrency Control in Distributed Databases. In Proceedings of the 6th Berkeley Workshop, 1982.
• 7: Mark Stuart Day , Barbara Liskov, Client cache management in a distributed object database, 1995
• 8: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 9: Michael Jay Franklin, Caching and memory management in client-server database systems, University of Wisconsin at Madison, Madison, WI, 1993
• 10: M. Franklin and M. Carey. Client-Server Caching Revisited. In Proc. Int'l Workshop on Distributed Object Management, Edmonton, Canada, August 1992.
• 11: S. Ghemawat. Main-Memory Log: A Simple Solution to the Disk Bottleneck. PhD thesis, Massachusetts Institute of Technology, Forthcoming.
• 12: D. K. Gifford. Information Storage in a Decentralized Computer System. Tech. Report CSL-81-8, Xerox Parc, 1983.
• 13: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 14: R. E. Gruber, OPTIMISTIC CONCURRENCY CONTROL FOR NESTED DISTRIBUTED TRANSACTIONS, Massachusetts Institute of Technology, Cambridge, MA, 1989
• 15: R. E. Gruber. Temperature-Based Concurrency Control. in Third IWO00S, pages 230-232, Asheville, December 1993.
• 16: R. E. Gruber. Temperature-Based Concurrency Control. PhD thesis, Massachusetts Institute of Technology, Forthcoming.
• 17: Theo Härder, Observations on optimistic concurrency control schemes, Information Systems, v.9 n.2, p.111-120, 1984 [doi>10.1016/0306-4379(84)90020-6]
• 18: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 19: Ming-Yee Lai , W. Kevin Wilkinson, Distributed Transaction Management in Jasmin, Proceedings of the 10th International Conference on Very Large Data Bases, p.466-470, August 27-31, 1984
• 20: Barbara Liskov, Practical uses of synchronized clocks in distributed systems, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.1-9, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112601]
• 21: B. Liskov. Preliminary Design of the Thor Object-Oriented Database System. Programming Methodology Memo 74, MIT Lab. for Computer Science, March 1992.
• 22: B. Liskov, R. Gmber, E Johnson, and L. Shrira. A Highly- Available Object Repository for use in a Heterogeneous Distributed System. In Proc. of the 4th lnt'l Workshop on Persistent Object Systems, pages 255-266, September 1990.
• 23: Umesh Maheshwari , Barbara H. Liskov, Fault-tolerant distributed garbage collection in a client-server object-oriented database, Proceedings of the third international conference on on Parallel and distributed information systems, p.239-248, October 1994, Autin, Texas, United States
• 24: D. L. Mills. Network Time Protocol: Specification and implementation. DARPA-Intemet Report RFC 1059, DARPA, July 1988.
• 25: E. Rahm and A. Thomasian. A New Distributed Optimistic Concurrency Control Method and a Comparison of its Performance with Two-Phase Locking. In Proceedings of Tenth ICDCS, 1990.
• 26: J. W. Stamos. A Low-Cost Atomic Commit Protocol. Tech. Report RJ7185, IBM Almaden, CA, December 1989.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Recovery and restart; Deadlock avoidance
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Experimentation, Performance, Verification