Two-phase locking

This article is about concurrency control. For commit consensus within a distributed transaction, see Two-phase commit protocol.

In databases and transaction processing, two-phase locking (2PL) is a pessimistic concurrency control method that guarantees serializability. It is also the name of the resulting set of database transaction schedules (histories). The protocol uses locks, applied by a transaction to data, which may block (interpreted as signals to stop) other transactions from accessing the same data during the transaction's life.

By the 2PL protocol, locks are applied and removed in two phases:

1. Expanding phase: locks are acquired and no locks are released.
2. Shrinking phase: locks are released and no locks are acquired.

Two types of locks are used by the basic protocol: Shared and Exclusive locks. Refinements of the basic protocol may use more lock types. Using locks that block processes, 2PL may be subject to deadlocks that result from the mutual blocking of two or more transactions.

Read and write locks

Locks are used to guarantee serializability. A transaction is holding a lock on an object if it that transaction has acquired a lock on that object which has not yet been released.

For 2PL, the only used data-access locks are read-locks (shared locks) and write-locks (exclusive locks). Below are the rules for read-locks and write-locks:

• A transaction is allowed to read an object if and only if it is holding a read-lock or write-lock on that object.
• A transaction is allowed to write an object if and only if it is holding a write-lock on that object.
• A schedule (i.e., a set of transactions) is allowed to hold multiple locks on the same object simultaneously if and only if none of those locks are write-locks. If a disallowed lock attempts on being held simultaneously, it will be blocked.

Lock compatibility table

Lock type	read-lock	write-lock
read-lock	✔	X
write-lock	X	X

Two-phase locking and its special cases

Two-phase locking

According to the two-phase locking protocol, each transaction handles its locks in two distinct, consecutive phases during the transaction's execution:

1. Expanding phase (aka Growing phase): locks are acquired and no locks are released (the number of locks can only increase).
2. Shrinking phase (aka Contracting phase): locks are released and no locks are acquired.

The two phase locking rules can be summarized as: each transaction must never acquire a lock after it has released a lock. The serializability property is guaranteed for a schedule with transactions that obey this rule.

Typically, without explicit knowledge in a transaction on end of phase 1, the rule is safely determined only when a transaction has completed processing and requested commit. In this case, all the locks can be released at once (phase 2).

Conservative two-phase locking

The difference between 2PL and C2PL is that C2PL's transactions obtain all the locks they need before the transactions begin. This is to ensure that a transaction that already holds some locks will not block waiting for other locks. Conservative 2PL prevents deadlocks.

Strict two-phase locking

To comply with the strict two-phase locking (S2PL) protocol, a transaction needs to comply with 2PL, and release its write (exclusive) locks only after the transaction has ended (i.e., either committed or aborted). On the other hand, read (shared) locks are released regularly during the shrinking phase.

Unlike 2PL, S2PL provides strictness (a special case of cascade-less recoverability). This protocol is not appropriate in B-trees because it causes Bottleneck (while B-trees always starts searching from the parent root).

Strong strict two-phase locking

or Rigorousness, or Rigorous scheduling, or Rigorous two-phase locking

To comply with strong strict two-phase locking (SS2PL), a transaction's read and write locks are released only after that transaction has ended (i.e., either committed or aborted). A transaction obeying SS2PL has only a phase 1 and lacks a phase 2 until the transaction has completed. Every SS2PL schedule is also an S2PL schedule, but not vice versa.

SS2PL is the concurrency control protocol utilized in most database systems (in various variants) since the early 1970s. Like S2PL, SS2PL provides both serializability and strictness. Unlike S2PL, SS2PL provides commitment ordering (i.e., it preserves the order in which transactions commit). SS2PL has an efficient implementation of distributed serializability and global serializability without using a distributed lock manager.

SS2PL, while not offering significant concurrency advantages over S2PL, is easier to implement.

Variants of SS2PL use various lock-types (such as Multiple granularity locking) in different situations, and may even change these lock-types during a transaction.

Especially before 1990, but also after, in many articles and books, e.g., (Bernstein et al. 1987, p. 59), the term "Strict 2PL" (S2PL) has been frequently defined by the locking protocol "Release all locks only after transaction end," which is the protocol of SS2PL. To make the naming convention more accurate, Breitbart and Raz re-defined S2PL as the intersection of Strictness and 2PL, and defined the protocol for releasing locks only post-transaction as "rigorousness" and "SS2PL" respectively.

Summary - Relationships among classes

Schedule classes containment: An arrow from class A to class B indicates that class A strictly contains B; a lack of a directed path between classes means that the classes are incomparable. A property is inherently blocking, if it can be enforced only by blocking transaction's data access operations until certain events occur in other transactions. (Raz 1992)

Between any two schedule classes (define by their schedules' respective properties) that have common schedules, either one contains the other (strictly contains if they are not equal), or they are incomparable. The containment relationships among the 2PL classes and other major schedule classes are summarized in the following diagram. 2PL and its subclasses are inherently blocking, which means that no optimistic implementations for them exist (and whenever "Optimistic 2PL" is mentioned it refers to a different mechanism with a class that includes also schedules not in the 2PL class).

Deadlocks in 2PL

Locks block data-access operations. Mutual blocking between transactions results in a deadlock, where execution of these transactions is stalled, and no completion can be reached. Thus deadlocks need to be resolved to complete these transactions' executions and release related computing resources. A deadlock is a reflection of a potential cycle in the precedence graph, that would occur without the blocking. A deadlock is resolved by aborting a transaction involved with such potential cycle, and breaking the cycle. It is often detected using a wait-for graph (a graph of conflicts blocked by locks from being materialized; conflicts not materialized in the database due to blocked operations are not reflected in the precedence graph and do not affect serializability), which indicates which transaction is "waiting for" lock release by which transaction, and a cycle means a deadlock. Aborting one transaction per cycle is sufficient to break the cycle. If a transaction has been aborted due to deadlock resolution, it is up to the application to decide what to do next. Usually, an application will restart the transaction from the beginning but may delay this action to give other transactions sufficient time to finish in order to avoid causing another deadlock.

In a distributed environment an atomic commitment protocol, typically the Two-phase commit (2PC) protocol, is used for atomicity. When recoverable data (data under transaction control) partitioned among 2PC participants (i.e., each data object is controlled by a single 2PC participant), then distributed (global) deadlocks, deadlocks involving two or more participants in 2PC, are resolved automatically as follows:

When SS2PL is effectively used in a distributed environment, then global deadlocks due to locking generate voting-deadlocks in 2PC, and are resolved automatically by 2PC (see Commitment ordering (CO), in Exact characterization of voting-deadlocks by global cycles; No reference except the CO articles is known to notice this). For the general case of 2PL, global deadlocks are similarly resolved automatically by the synchronization point protocol of phase-1 end in a distributed transaction (synchronization point is achieved by "voting" (notifying local phase-1 end), and being propagated to the participants in a distributed transaction the same way as a decision point in atomic commitment; in analogy to decision point in CO, a conflicting operation in 2PL cannot happen before phase-1 end synchronization point, with the same resulting voting-deadlock in the case of a global data-access deadlock; the voting-deadlock (which is also a locking based global deadlock) is automatically resolved by the protocol aborting some transaction involved, with a missing vote, typically using a timeout).

Comment:

When data are partitioned among the atomic commitment protocol (e.g., 2PC) participants, automatic global deadlock resolution has been overlooked in the database research literature, though deadlocks in such systems has been a quite intensive research area:

• For CO and its special case SS2PL, the automatic resolution by the atomic commitment protocol has been noticed only in the CO articles. However, it has been noticed in practice that in many cases global deadlocks are very infrequently detected by the dedicated resolution mechanisms, less than could be expected ("Why do we see so few global deadlocks?"). The reason is probably the deadlocks that are automatically resolved and thus not handled and uncounted by the mechanisms;
• For 2PL in general, the automatic resolution by the (mandatory) end-of-phase-one synchronization point protocol (which has same voting mechanism as atomic commitment protocol, and same missing vote handling upon voting deadlock, resulting in global deadlock resolution) has not been mentioned until today (2009). Practically only the special case SS2PL is used, where no end-of-phase-one synchronization is needed in addition to atomic commit protocol.

In a distributed environment where recoverable data are not partitioned among atomic commitment protocol participants, no such automatic resolution exists, and distributed deadlocks need to be resolved by dedicated techniques.

See also

• Serializability
• Lock (computer science)