Blocking procedure

Locking procedures are used in database systems to meet the isolation requirement of the ACID principle in transactions . All locking procedures, also called locking protocols, fall into the category of pessimistic synchronization procedures ("pessimistic locking"), i. In other words, when a transaction is started it is assumed that there is a high probability of a conflict with a parallel transaction. On the contrary, there are optimistic procedures that examine schedules for conflicts and, if necessary, reset one of the transactions involved (“ rollback ”).

introduction

In order to be able to represent a transaction formally, for the sake of simplicity it is assumed that either a read or a write operation can take place on a database object. In contrast to writing, the object is not changed when reading. ${\displaystyle a}$

In order to synchronize several transactions that want to access the same database object at the same time, each transaction can request a read lock (shared lock) or an write lock (exclusive lock) on an object.

Before a transaction can use the object , it must request a lock for ( ). However, if another transaction has exclusively locked the desired object, you have to wait until the object has been released again and receives the read lock. During this waiting time it is said that it is blocked. A blockage can always occur if another transaction has already set a lock on the desired object . ${\displaystyle T}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle R(a)}$ ${\displaystyle P}$ ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle a}$

In the event that several transactions are waiting for locks to be released, that is, they block each other, this is called a “ deadlock ”.

The situations in which a blockage occurs depends on the blocking procedure used and can be read from the associated compatibility matrix (see below).

Formal spellings

Transaction reads object : ${\displaystyle T_{i}}$ ${\displaystyle a}$ ${\displaystyle r_{i}(a)}$

Transaction writes object : ${\displaystyle T_{i}}$ ${\displaystyle a}$ ${\displaystyle w_{i}(a)}$

Transaction requests a read lock on the object : ${\displaystyle T_{i}}$ ${\displaystyle a}$ ${\displaystyle R_{i}(a)}$

Transaction requests a write lock on the object : ${\displaystyle T_{i}}$ ${\displaystyle a}$ ${\displaystyle X_{i}(a)}$

Compatibility matrix

The compatibility matrix indicates whether a transaction can obtain a particular lock on an object when another transaction has already obtained a lock on the same object.

	R.	X
R.	+	-
X	-	-

Reading type:

• The type of lock already set is specified in the top line.
• The first column shows the type of lock requested by another transaction.
• The "+" indicates that the requested lock is compatible with the one that has already been set and that the lock can therefore be set. As a result, the requesting transaction is not blocked
• The "-" indicates that the locks are incompatible and the requesting transaction is blocked.

Fundamental theorem of locking

Every transaction that uses locks must comply with the following lock conditions:

1. For each object that is to be used by the transaction, a lock must be requested before use.
2. A transaction may not request a lock it has already set on the same object again.
3. At the latest at the end of the transaction ( end-of-transmission , EOT ), all locks set by the transaction must be released again.
4. Each transaction must respect the locks set by other transactions.
5. Each transaction goes through the stages of lock growth and shrinkage (see below).

Two-phase locking protocol

Variants of 2PL

The 2PL procedure (two-phase locking) assumes that every transaction goes through two phases:

1. The growth phase in which locks can only be set but not released .
2. The shrinkage phase , in which locks can only be released but not requested .

A distinction is made between two locks:

1. Read-Lock (also shared ): several processes can read the locked object.
2. Write-Lock (also exclusive ): only the locking process can access the object and also write it.

There are two special cases of 2PL:

1. The conservative 2-phase locking protocol (preclaiming), in which all required locks are set at once at the beginning of the transaction. In any case, this prevents deadlocks, but also leads to a high loss of parallelism, since a transaction cannot carry out its first operation until it has received all locks. Furthermore, it must be known in advance which locks are required by the transaction, which is not trivial to solve, at least with a conditional if-then-else statement. For this reason, this variant is rarely used in practice. With this variant, you can start releasing locked objects before the end of the transaction.
2. The strict 2-phase locking protocol in which all write locks are only released at the end of the transaction (after the last operation). This approach prevents the snowball effect, i.e. the cascading resetting of mutually influencing transactions. The disadvantage is that locks are often held for much longer than necessary, thus increasing the waiting time for blocked transactions. The read locks are removed according to the standard 2PL procedure.

If both methods are used in combination, this automatically means that all transactions that access the same object are executed sequentially one after the other. This contradicts the idea of ​​the transaction concept.

More locks

Basically, there are two types of classic locks: X (from English eXclusive = exclusively) as a lock for modifications, mostly writing, and the S lock (from English share = to share), in which the object remains unchanged and the simultaneous ones Allows access. Since this applies to reading, the S lock is often also referred to as the R lock (from English read = read). A transaction that requests a write lock must wait until all locks from other transactions have been released.

While the write lock is set, no other transaction can obtain another read or write lock for the object. This means that a writing transaction blocks all other transactions that require the same object.

SX compatibility matrix

	S.	X
S.	+	-
X	-	-

SAX compatibility matrix

Enlargement for reading by design (A). This form of lock offers high throughput, and writers can starve to death as new readers keep arriving.

	S.	A.	X
S.	+	+	-
A.	+	-	-
X	-	-	-

SUX compatibility matrix

Extension for reading with exclusive intention to change (U). Intentional writing changes U to X after S locks are released. If it is not changed, the U-lock is changed to an S-lock. Only one transaction can hold a U lock. Writers can no longer starve to death. Less throughput than with SAX.

	S.	U	X
S.	+	-	-
U	+	-	-
X	-	-	-

SAC compatibility matrix

Extension of parallelism by better supporting read operations. An A lock if the object is to be modified. Using the C lock, the two versions of the copy are made consistent. If the C lock is set, there are two object versions, one before the completed transaction with an A lock and one after the transaction. The appropriate version is selected depending on the start of the reading process.

	S.	A.	C.
S.	+	+	+
A.	+	-	-
C.	+	-	-

Hierarchical barrier granules

The previous locks only considered those of the same granularity, the objects to be locked were hierarchically at the same level. This can be refined to the following hierarchical locking granulates ( called multiple granularity locking ) (in descending hierarchy, the further down the finer):

1. Database
2. Segments
3. pages
4. Records

IX compatibility matrix

In this process, a distinction is made between different granulates. Coarse granules define entire relations as a locked object, while fine granules only affect individual records of a relation. Intention Share (IS) sets a lock on a coarser granularity level. Intention eXclusive (IX) is the appropriate lock on a coarser granularity level for writing on a finer granularity level.

	IS	IX	S.	X
IS	+	+	+	-
IX	+	+	-	-
S.	+	-	+	-
X	-	-	-	-

SIX compatibility matrix

This procedure is a further refinement of the IX lock. SIX is made up of S (Shared) + IX (Intention eXclusive). SIX can be used in the event that all records of a record type are to be read, but only some are to be changed. In this case, an X lock would be too restrictive on the record type and an IX lock would require that every record be locked. SIX locks the object in S mode and only requests X locks on lower hierarchical levels for objects to be changed.

	IS	IX	S.	SIX	U	X
IS	+	+	+	+	-	-
IX	+	+	-	-	-	-
S.	+	-	+	-	-	-
SIX	+	-	-	-	-	-
U	-	-	+	-	-	-
X	-	-	-	-	-	-

Blocking of nodes

If a data object is to be provided with a lock, the higher-level nodes must be checked, the lock starting from the top node (the database, top-down ), the release from below ( bottom-up ):

1. Locking a node with S or IS : Locking all over it in IS or holding in IX
2. Locking a node with X or IX : Locking everything above it in IX
3. Release from bottom to top

Multiversion Concurrency Control (MVCC)

→ Main article : Multiversion Concurrency Control

See also

• Lock
• Lock rescalation
• Optimistic locking

literature

• R. Elmasri et al .: Basics of database systems. Pearson Studium, 2002, 3ed, ISBN 3-8273-7021-3 , p. 714 ff.
• Alfons Kemper, André Eickler: Database Systems - An Introduction. 11 edition. Oldenburg, Munich 2011, ISBN 978-3-486-59834-6 , p. 329 ff.
• Granularity of Locks and Degrees of Consistency in a Shared Database , J. Gray, R. Lorie, GF Putzolu and IL Traiger, Modeling in Data Base Management Systems, GM Nijssen ed., North Holland Pub., 1976, pp. 364-394 .
• Script for the lecture Database Systems II , LMU Munich
• [1] , University of Berkeley

Web links

• Scripts for the automatic solving of schedules using 2PL

Individual evidence

1. ^ ^{A b} Alfons Kemper, André Eickler: Database systems - An introduction . 11th edition. Oldenburg, Munich 2011, ISBN 978-3-486-59834-6 .