Locking granularity revisited

ABSTRACT

Locking granularity refers to the size and hence the number of locks used to ensure the consistency of a database during multiple concurrent updates. In an earlier simulation study we concluded that coarse granularity, such as area or file locking, is to be preferred to fine granularity such as individual page or record locking. However, alternate assumptions than those used in the original paper can change that conclusion. First, we modified the assumptions concerning the placement of the locks on the database with respect to the accessing transactions. In the original model the locks were assumed to be well placed. Under worse case and random placement assumptions when only very small transactions access the database, fine granularity is preferable. Second, we extended the simulation to model a lock hierarchy where large transactions use large locks and small transactions use small locks. In this scenario, again under the random and worse case lock placement assumptions, fine granularity is preferable if all transactions accessing more than 1 percent of the database use large locks. Finally, the simulation was extended to model a “claim as needed” locking strategy together with the resultant possibility of deadlock. In the original study all locks were claimed in one atomic operation at the beginning of a transaction. The claim as needed strategy does not change the conclusions concerning the desired granularity.

REFERENCES

• 1: 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]
• 2: CHAMBERLIN, D., ET AL. A deadlock-free scheme for resource locking in a data base environment. Res. Rep., IBM Res. Lab., San Jose, Calif., June 1974.
• 3: CODASYL PROGRAMMING LANGUAGE COMMITTEE. CODASYL COBOL Data Base Facility- Proposal, March 1973.
• 4: E. G. Coffman , M. Elphick , A. Shoshani, System Deadlocks, ACM Computing Surveys (CSUR), v.3 n.2, p.67-78, June 1971 [doi>10.1145/356586.356588]
• 5: DIGITAL EQUIPMENT CORP. DBMS-11 Data Base Administrator's Guide. DEC-11-ODABA-A-D, Digital Equipment Corp., Maynard, Mass., 1976.
• 6: 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]
• 7: GRAY, J.N., LOR}E, R.A., AI~D PUTZOLU, G.R. GranuLarity of locks in a shared data base. Proc. Int. Conf. on Very Large Data Bases, Framingham, Mass., Sept. 1975, pp. 428-451.
• 8: GRAY, J.N., LORIE, R.A., PUTZOLU, G.R. AND TRAIGER, I.L. Granularity of locks and degrees of consistency in a shared data base. Proc. IFIP Working Conf. on Modelling of Data Base Manage. Syst., Freudenstadt, Germany, Jan. 1976, pp. 695-723.
• 9: HEWLETT-PACKARD CORP. IMAGE Reference Manuall Hewlett-Packard Corp., Pa|o Alto, Calif., 1977.
• 10: LIPSON, W., AND LAPEZAK, LSL User's Manual. Tech. Note No. 9, Comptr. Syst. Res. Group, U. of Toronto, Toronto, Ont., Canada, Aug. 1976.
• 11: Philip P. Macri, Deadlock detection and resolution in a CODASYL based data management system, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
• 12: R. Munz , G. Krenz, Concurrency in database systems: a simulation study, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509421]
• 13: Daniel R. Ries , Michael Stonebraker, Effects of locking granularity in a database management system, ACM Transactions on Database Systems (TODS), v.2 n.3, p.233-246, Sept. 1977 [doi>10.1145/320557.320566]
• 14: RODRIQUEZ-ROSELL, J. Empirical data reference behavior in data base systems. Computer 9, 11 (Nov. 1976), 9-13.
• 15: James F. Spitzer, Performance prototyping of data management applications, Proceedings of the annual conference, p.287-291, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805599]
• 16: STEARNS, R.E., ET AL. Concurrency control for data base systems. Proc. IEEE Syrup. on Foundation of Comptr. Sci., Oct. 1976, 19-32.
• 17: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Deadlock avoidance

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Design, Security

Keywords:
concurrency, database management, locking granulaity, locking hierarchies, multiple updates