Browse Prior Art Database

PROBABILISTIC TECHNIQUES FOR TWO PHASE LOCKING IN DATABASE SYSTEMS

IP.com Disclosure Number: IPCOM000128186D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 13 page(s) / 39K

Publishing Venue

Software Patent Institute

Related People

Paul SpirakisMand: AUTHOR [+4]

Abstract

Two phase locking (2PL) is one of the few important techniques used for database concurrency control. It has the feature that as soon as a transaction releases a lock, it never obtains additional locks. The two phase locking protocol guarantees serializability of transaction executions, hence it is a correct synchronization technique. One of the most common variations of 2PL is static locking (SL) where a transaction is allowed to act on the data only if all the locks it needs are granted to it. The main advantage of SL is that deadlocks are avoided. Although some investigators provided lately quantitative analyses os the performance of locking, most of the analyses use very strong assumptions about transaction arrivals and transaction behavior, in order to overcome the difficulties of modelling transaction interference. In some cases, the analytic results provide little intuition about the degradation of performance due to locking. In this paper, we propose a new implementation of 2PL. Our implementation is suited for a distributed database system, since there is no need of a central scheduler of transaction actions. The main innovation of the technique is the use of probabilistic choice within the 2PL protocol, to achieve fast transaction response time. Our proposed implementation is similar to a static 2PL in the sense that transactions are allowed to operate on the data only when all locks are obtained. Another contribution of the paper is that we give a tractable analysis for the mean response time of transactions and bounds for the distribution of the response time. Our analysis does not need oversimplifying assumptions on transaction behavior (e.g. uniform data reference or Poisson arrivals).. We apply randomization to 2PL protocols in stages of increasing sophistication (and efficiency), starting from a straight-forward use of random waits and advancing to a technique of probabilistic bidding for locks and then giving a technique which combines the above uses of random choice in order to favor transactions with readsets of small cardinality. We show our bidding technique to be optimal for distributed SL in the sense of matching lower bounds for transaction response time. We brieflv mention an extension of our techniques to get an efficient implementation of Moss's 2PL protocol for nested transactions.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

PROBABILISTIC TECHNIQUES FOR TWO PHASE LOCKING IN DATABASE SYSTEMS*

By

Paul SpirakisMand John. Reif

October 1983

Report #102 ` 1 n C 9 U 121 *This work was partially supported by the NSF Grant MCS 83- 00630 (1)Courant Institute of Mathematical Sciences, New York University (2) Aiken Computation Laboratory, Harvard University

Abstract

Two phase locking (2PL) is one of the few important techniques used for database concurrency control. It has the feature that as soon as a transaction releases a lock, it never obtains additional locks. The two phase locking protocol guarantees serializability of transaction executions, hence it is a correct synchronization technique. One of the most common variations of 2PL is static locking (SL) where a transaction is allowed to act on the data only if all the locks it needs are granted to it. The main advantage of SL is that deadlocks are avoided.

Although some investigators provided lately quantitative analyses os the performance of locking, most of the analyses use very strong assumptions about transaction arrivals and transaction behavior, in order to overcome the difficulties of modelling transaction interference. In some cases, the analytic results provide little intuition about the degradation of performance due to locking.

In this paper, we propose a new implementation of 2PL. Our implementation is suited for a distributed database system, since there is no need of a central scheduler of transaction actions. The main innovation of the technique is the use of probabilistic choice within the 2PL protocol, to achieve fast transaction response time. Our proposed implementation is similar to a static 2PL in the sense that transactions are allowed to operate on the data only when all locks are obtained.

Another contribution of the paper is that we give a tractable analysis for the mean response time of transactions and bounds for the distribution of the response time. Our analysis does not need oversimplifying assumptions on transaction behavior (e.g. uniform data reference or Poisson arrivals)..

We apply randomization to 2PL protocols in stages of increasing sophistication (and efficiency), starting from a straight-forward use of random waits and advancing to a technique of probabilistic bidding for locks and then giving a technique which combines the above uses of random choice in order to favor transactions with readsets of small cardinality. We show our bidding technique to be optimal for distributed SL in the sense of matching lower bounds for transaction response time. We brieflv mention an extension of our techniques to get an efficient implementation of Moss's 2PL protocol for nested transactions. .

New York University Page 1 Dec 31, 1983

Page 2 of 13

PROBABILISTIC TECHNIQUES FOR TWO PHASE LOCKING IN DATABASE SYSTEMS

1. Introduction

Synchronization in update processing is necessary to maintain the consistency of databases. Tw...