Performance evaluation of semantics-based multilevel concurrency control protocols

ABSTRACT

For next generation information systems, concurrency control mechanisms are required to handle high level abstract operations and to meet high throughput demands. The currently available single level concurrency control mechanisms for reads and writes are inadequate for future complex information systems. In this paper, we will present a new multilevel concurrency protocol that uses a semantics-based notion of conflict, which is weaker than commutativity, called recoverability. Further, operations are scheduled according to relative conflict, a conflict notion based on the structure of operations. Performance evaluation via extensive simulation studies show that with our multilevel concurrency control protocol, the performance improvement is significant when compared to that of a single level two-phase locking based concurrency control scheme or to that of a multilevel concurrency control scheme based on commutativity alone. Further, simulation studies show that our new multilevel concurrency control protocol performs better even with resource contention.

REFERENCES

• 1: 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]
• 2: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 3: B. R. Badrinath , Krithi Ramamritham, Semantics-Based Concurrency Control: Beyond Commutativity, Proceedings of the Third International Conference on Data Engineering, p.304-311, February 03-05, 1987
• 4: Badnnath, B It. and Ramamrltham, K Performance evaluat,on of semant,cs-based multilevel concurrency control protocols Techmcal Report DCS-TR-261, Rutgets Umvermty, Department of Computer Sc,ence, December 1989
• 5: B. R. Badrinath , Krithi Ramamritham, Semantics-based concurrency control: beyond commutativity, ACM Transactions on Database Systems (TODS), v.17 n.1, p.163-199, March 1992 [doi>10.1145/128765.128771]
• 6: Been, C , Bernstem, P A, and Goodman, N A Model for Concurrency m Nested T~ansactlon Systems Techmeal Iteport CS-86-1, Hebrew Umvers, ty, Jerusalem, Israel, January 1986
• 7: C. Beeri , P. A. Bernstein , N. Goodman , M. Y. Lai , D. E. Shasha, A concurrency control theory for nested transactions (Preliminary Report), Proceedings of the second annual ACM symposium on Principles of distributed computing, p.45-62, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806709]
• 8: Catriel Beeri , Hans-Jörg Schek , Gerhard Weikum, Multi-Level Transaction Management, Theoretical Art or Practical Need ?, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.134-154, March 14-18, 1988
• 9: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 10: Thanasis Hadzilacos , Vassos Hadzilacos, Transaction synchronisation in object bases, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.193-200, March 1988, Austin, Texas, United States [doi>10.1145/308386.308438]
• 11: Hadz,lacos, V Issues of fault tolerance ,n concurrent computatmns Techmcal Iteport 11-84, Harvard Umversity, Axken Computatmn laboratory, Cambridge, MA 02138, June 1984
• 12: Maurice Herlihy, Optimistic concurrency control for abstract data types, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.206-217, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10608]
• 13: M. Herlihy, Extending multiversion time-spaning protocols to exploit type information, IEEE Transactions on Computers, v.36 n.4, p.443-448, April 1987 [doi>10.1109/TC.1987.1676926]
• 14: 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]
• 15: Martin, B E Modehng concurrent act,wt,es wlth nested objects In Proceedings of the 7th raternarwhal conference on d,str~buted computing systems, pages 432-439, Berhn, Germany, September 1987
• 16: Mart,n, B E Scheduhng protocols for nested objects Techmcal Iteport CS-094, Department of Computer Sczence and Engmeenng, Umverslty of Cahforma, San Dxego, Calfforma, 1988
• 17: J. Eliot B Moss , Nancy D. Griffeth , Marc H. Graham, Abstraction in recovery management, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.72-83, May 28-30, 1986, Washington, D.C., United States
• 18: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 19: Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
• 20: Peter Peinl , Andreas Reuter , Harald Sammer, High contention in a stock trading database: a case study, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.260-268, June 01-03, 1988, Chicago, Illinois, United States
• 21: Steve Rozen , Dennis Shasha, Using a relational system on Wall Street: the good, the bad, the ugly, and the ideal, Communications of the ACM, v.32 n.8, p.988-994, Aug. 1989 [doi>10.1145/65971.65977]
• 22: Sehnger, P, Gawhck, D , Gray, J , Krause, 3 , and Schrager, P Panel Discussion Issues m bmldmg large database systems In Proceedings of the A GM SIG- MOD international con/erence on management o} data, page 6, Chicago, Ilhnom, June 1988.
• 23: Michael Stonebraker , Randy H. Katz , David A. Patterson , John K. Ousterhout, The Design of XPRS, Proceedings of the 14th International Conference on Very Large Data Bases, p.318-330, August 29-September 01, 1988
• 24: Y. C. Tay , Nathan Goodman , R. Suri, Locking performance in centralized databases, ACM Transactions on Database Systems (TODS), v.10 n.4, p.415-462, Dec. 1985 [doi>10.1145/4879.4880]
• 25: Gerhard Weikum, A theoretical foundation of multi-level concurrency control, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.31-43, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15401]

INDEX TERMS

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

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Military

General Terms:
Design, Performance