On Optimistic Methods for Concurrency Control H.T. KUNG and JOHN T. ROBINSON Carnegie-Mellon University Most current approaches to concurrency control in database systems rely on locking of data objects as a control mechanism. In this paper, two families of nonlocking concurrency controls are presented. The methods used are “optimistic” in the sense that they rely mainly on transaction backup as a control mechanism, “hoping” that conflicts between transactions will not occur. Applications for which these methods should be more efficient than locking are discussed. Key Words and Phrases: databases, concurrency controls, transaction processing CR Categories: 4.32, 4.33 1. INTRODUCTION Consider the problem of providing shared access to a database organized as a collection of objects. We assume that certain distinguished objects, called the roots, are always present and access to any object other than a root is gained only by first accessing a root and then following pointers to that object. Any sequence of accesses to the database that preserves the integrity constraints of the data is called a transaction (see, e.g., [4]). If our goal is to maximize the throughput of accesses to the database, then there are at least two cases where highly concurrent access is desirable. (1) The amount of data is sufficiently great that at any given time only a fraction of the database can be present in primary memory, so that it is necessary to swap parts of the database from secondary memory as needed. (2) Even if the entire database can be present in primary memory, there may be multiple processors. In both cases the hardware will be underutilized if the degree of concurrency is too low. However, as is well known, unrestricted concurrent access to a shared database will, in general, cause the integrity of the database to b6 lost. Most current Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. This research was supported in part by the National Science Foundation under Grant MCS 78-236-76 and the Office of Naval Research under Contract NOOO14-76-C-0370. Authors’ address: Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA 15213. 0 1981 ACM 0362-5915/81/0600~0213 $00.75 ACM Transactions on Database Systems, Vol. 6, No. 2, June 1981, Pages 213-226. i214 . H. T. Kung and J. T. Robinson approaches to this problem involve some type of locking. That is, a mechanism is provided whereby one process can deny certain other processes access to some portion of the database. In particular, a lock may be associated with each node of the directed graph, and any given process is required to follow some locking protocol so as to guarantee that no other process can ever discover any lack of integrity in the database temporarily caused by the given process. The locking approach has the following inherent disadvantages. (1) Lock maintenance represents an overhead that is not present in the sequential case. Even read-only transactions (queries), which cannot possibly affect the integrity of the data, must, in general, use locking in order to guarantee that the data being read are not modified by other transactions at the same time. Also, if the locking protocol is not deadlock-free, deadlock detection must be considered to be part of lock maintenance overhead. (2) There are no general-purpose deadlock-free locking protocols for databases that always provide high concurrency. Because of this, some research has been directed at developing special-purpose locking protocols for various special cases. For example, in the case of B-trees [l], at least nine locking protocols have been proposed [2, 3,9, 10, 131. (3) In the case that large parts of the database are on secondary memory, concurrency is significantly lowered whenever it is necessary to leave some congested node locked (a congested node is one that is often accessed, e.g., the root of a tree) while waiting for a secondary memory access. (4) To allow a transaction to abort itself when mistakes occur, locks cannot be released until the end of the transaction. This may again significantly lower concurrency. (5) Most important for the purposes of this paper, locking may be necessary only in the worst case. Consider the following simple example: The directed graph consists solely of roots, and each transaction involves one root only, any root equally likely. Then if there are n roots and two processes executing trans- actions at the same rate, locking is really needed (if at all) every n transac- tions, on the average. In general, one may expect the argument of (5) to hold whenever (a) the number of nodes in the graph is very large compared to the total number of nodes involved in all the running transactions at a given time, and (b) the probability of modifying a congested node is small. In many applications, (a) and (b) are designed to hold (see Section 6 for the B-tree application). Research directed at finding deadlock-free locking protocols may be seen as an attempt to lower the expense of concurrency control by eliminating transaction backup as a control mechanism. In this paper we consider the converse problem, that of eliminating locking. We propose two families of concurrency controls that do not use locking. These methods are “optimistic” in the sense that they rely for efficiency on the hope that conflicts between transactions will not