428 GRANULARITY OF LOCKS IN A SHARED DATA BASE bY J.N. Gray R.A. Lorie G.R. Putzolu IBM Research Laboratory San Jose, California 95193 Abstract: This paper proposes a locking protocol which associates locks with sets of resources. This protocol allows simultaneous locking at various granularities by different transactions. It is based on the introduction of additional lock modes besides the conventional share mode and exclusive mode. The protocol is generalized from simple hierarchies of locks to directed acyclic graphs of locks and to dynamic graphs of locks. The issues of scheduling and granting conflicting requests for the same resource are then discussed. Lastly, these ideas are compared with the lock mechanisms provided by existing data management systems. This work was supported by IBM. Author's address: K55-282, IBM, Monterey and Cottle Rds., San Jose, California 95193.429 1. INTRODUCTION We assume %he data base consists of a collection of records and constraints defined on these records. There are physical constraints (ex: in a list of records, if record B then record B must a record A points to exist) as well as logical constraints (ex: conservation of money in a bank checking account application). When all such constraints are satisfied the data base is said to be consistent. A transaction is a series of accesses (fcr read or write operations) to the data base which, applied to a consistent data base, will produce a consistent data base. During the execution of a transaction, the data base may be temporarily inconsistent. The programs used to Ferform the transacticns assume that they trsee'q a consistent data base. So if several transactions are run concurrently, a locking mechanism must be used to insure that one transaction does not see temporarily inconsistent data caused by another transaction. Also, even if there are no consistency constraints, locks must be used so that the updates of one transaction are not made available to others before the transaction completes. Otherwise, transaction backup might cascade to other transactions which read or updated the "backed upI1 updates. Section 2 of the paper gives a brief description of a possible locking mechanism. It introduces the notion of granularity of lockable objects. Very informally, granularity refers to the size of a lockable object. The following and main Section 3 outlines a mechanism which simultaneously supports fine and gross lockable objects organized into a hierarchy. The generalization of these notions to directed acyclic graphs is then presented. Section 4 discusses the problems of scheduling lock requests. Section 5 relates these ideas to existing data base systems and briefly describes our use of this protocol in an experimental data base system. Note that the terms hierarchy and graph refer to the lock protocol and have nothing to do with the data model of the system. In fact the last section shows applications of the protocol to hierarchical, network and relational systems.430 2. GRAP'ULARITY OF LOCKS The description of a lock mechanism must cover the definition of the lockable objects, the operations which can be performed on the objects, how and when objects are allocated to particular transactions, and the duration of an allocation. A previous paper [1] discussed in some detail a lock protocol which would insure that the data base state obtained after running the same transactions concurrently is equivalent to.the state obtained by running the same transactions sequentially in some arbitrary order determined by the system. This defines the consistency provided by +he system. Suppose the lockable object is a single record in a file. The proposed protocol can be stated as: (a) Recognize the classical notion of shared locks for read oper- ations and exclusive locks for write operations on objects. (b) Any record must be appropriately locked before being accessed. (c) Any lock is kept to the end of transaction. Note that in order to work correctly the notion of locking a record must be extended to include the ability to lock the non-existence of a record (i.e. to prevent the insertion of "phantom" records by other transactions). This notion has been extensively discussed in Cl]. A forthcomming paper generalizes this notion of consistency to include protocols which release locks before the end of the transaction. The present paper also applies those more general protocols. It is a general problem in large integrated data bases that a transaction does not know which records it will access. so to avoid locking entire files or areas in advance, locks are requested dynamically. This creates a scheduling problem and the chosen scheduler must be prepared to handle deadlock situations. We return to this problem in section 4. The choice of lock granularity presents a tradeoff between concurrency and overhead. On the one hand, concurrency is increased if a fine unit of locking (for example a record or field) is chosen. Such a choice is appropriate to "simplet' transactions which access a few records. If a transaction accesses many records %here are many locks. Each such access incurs the computational overhead of setting and perhaps waiting for a lock and the storage overhead of representing the lock until the end of transaction. Using a coarse unit of locking (for example a file) is probably convenient for a transaction which accesses many records. However, such a coarse unit discriminates against transactions which only want to lock one record of the file. From this discussion it follows that one needs a multiplicity of granularities of lockable objects.431 3. HIERARCHICAL LOCKS In [l] it was proposed that one locks sets of records chosen from a file by specifying a predicate expression which "selects" the set of records to be locked. For