View source for Two-phase locking

{{Short description|Concurrency control method}}
In [[Database|database]]s and [[Transaction processing|transaction processing]], '''two-phase locking''' ('''2PL''') is a pessimistic [[Concurrency control|concurrency control]] method that guarantees [[Serializability|serializability]].<ref name=Bern1987>[[Biography:Phil Bernstein|Philip A. Bernstein]], Vassos Hadzilacos, Nathan Goodman (1987): [http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx  ''Concurrency Control and Recovery in Database Systems''], Addison Wesley Publishing Company, {{ISBN|0-201-10715-5}}</ref><ref name=Weikum2001>Gerhard Weikum, Gottfried Vossen (2001): [http://www.elsevier.com/wps/find/bookdescription.cws_home/677937/description#description  ''Transactional Information Systems''], Elsevier, {{ISBN|1-55860-508-8}}</ref>
It is also the name of the resulting set of [[Database transaction|database transaction]] [[Database transaction schedule|schedule]]s (histories). The protocol uses [[Lock (computer science)|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:
# Expanding phase: locks are acquired and no locks are released.
# 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 [[Deadlock|deadlock]]s that result from the mutual blocking of two or more transactions.

==Read and write locks==
Locks are used to guarantee [[Serializability|serializability]]. A transaction is ''holding'' a [[Lock (computer science)|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 [[Database transaction schedule|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.

{| class="wikitable" style="text-align:center;"
|+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:

# '''Expanding phase''' (aka Growing phase): locks are acquired and no locks are released (the number of locks can only increase).
# '''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|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 [[Conservative two-phase locking|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'' [[Deadlock|deadlock]]s.

===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. This protocol is not appropriate in B-trees because it causes Bottleneck (while B-trees always starts searching from the parent root). {{Citation needed|reason=This claim that S2PL is not appropriate for B-tree is not supported with citation in the edit. From knowledge, S2PL does not affect how storage / B-tree is being handled. |date=November 2016}}

===Strong strict two-phase locking===
or '''Rigorousness''', or '''Rigorous scheduling''', or '''Rigorous two-phase locking'''

To comply with '''strong strict two-phase locking''' (SS2PL) the locking protocol releases both ''write (exclusive)'' and ''read (shared)'' locks applied by a transaction only after the transaction has ended, i.e., only after both completing executing (being ''ready'') and becoming either ''committed'' or ''aborted''. This protocol also complies with the S2PL rules. A transaction obeying SS2PL can be viewed as having phase 1 that lasts the transaction's entire execution duration, and no phase 2 (or a degenerate phase 2). Thus, only one phase is actually left, and "two-phase" in the name seems to be still used due to the historical development of the concept from 2PL, and 2PL being a super-class. The SS2PL property of a schedule is also called '''Rigorousness'''. It is also the name of the class of schedules having this property, and an SS2PL schedule is also called a "rigorous schedule". The term "Rigorousness" is free of the unnecessary legacy of "two-phase," as well as being independent of any (locking) mechanism (in principle other blocking mechanisms can be used). The property's respective locking mechanism is sometimes referred to as '''Rigorous 2PL'''.

''Strong strict two-phase locking'' (SS2PL) is a popular serializability mechanism utilized in most of the database systems (in various variants) since their early days in the 1970s.

SS2PL is a special case of S2PL, i.e., the SS2PL class of schedules is a proper subclass of S2PL (every SS2PL schedule is also an S2PL schedule, but S2PL schedules exist that are not SS2PL).

SS2PL has been the concurrency control protocol of choice for most database systems and used since their early days in the 1970s. It is proven to be an effective mechanism in many situations, and provides besides [[Serializability]] also [[Database transaction schedule#Strict|Strictness]] (a special case of cascadeless Recoverability), which is instrumental for efficient [[Database|database]] [[Data recovery|recovery]], and also [[Commitment ordering]] (CO) for participating in distributed environments where a CO based [[Serializability#Distributed serializability|distributed serializability]] and [[Global serializability|global serializability]] solutions are employed. Being a subset of CO, an efficient implementation of ''[[Commitment ordering#Distributed serializability and CO|distributed SS2PL]]'' exists without a [[Distributed lock manager|distributed lock manager]] (DLM), while distributed deadlocks (see below) are resolved automatically. The fact that SS2PL employed in multi database systems ensures global serializability has been known for years before the discovery of CO, but only with CO came the understanding of the role of an [[Physics:Atomic commit|atomic commitment]] protocol in maintaining global serializability, as well as the observation of automatic distributed deadlock resolution (see [[Commitment ordering#Distributed SS2PL|a detailed example of Distributed SS2PL]]). As a matter of fact, SS2PL inheriting properties of Recoverability and CO is more significant than being a subset of 2PL, which by itself in its general form, besides comprising a simple serializability mechanism (however serializability is also implied by CO), is not known to provide SS2PL with any other significant qualities. 2PL in its general form, as well as when combined with Strictness, i.e., Strict 2PL (S2PL), are not known to be used in practice. The popular SS2PL does not require marking "end of phase 1" as 2PL and S2PL do, and thus is simpler to implement. Also, unlike the general 2PL, SS2PL provides, as mentioned above, the useful [[Database transaction schedule#Strict|Strictness]] and [[Commitment ordering]] properties.

Many variants of SS2PL exist that use various lock types with various semantics in different situations, including cases of lock-type change during a transaction. Notable are variants that use [[Multiple granularity locking]].

'''Comments:'''
#SS2PL vs. S2PL: Both provide Serializability and Strictness. Since S2PL is a superclass of SS2PL it may, in principle, provide more concurrency. However, no concurrency advantage is typically practically noticed (exactly same locking exists for both, with practically not much earlier lock release for S2PL), and the overhead of dealing with an end-of-phase-1 mechanism in S2PL, separate from transaction end, is not justified. Also, while SS2PL provides [[Commitment ordering]], S2PL does not. This explains the preference of SS2PL over S2PL.
# Especially before 1990, but also after, in many articles and books, e.g., (Bernstein et al. 1987, p.&nbsp;59),<ref name=Bern1987/> 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. Thus, "Strict 2PL" could not be the name of the intersection of Strictness and 2PL, which is larger than the class generated by the SS2PL protocol. This has caused confusion. With an explicit definition of S2PL as the intersection of Strictness and 2PL, a new name for SS2PL, and an explicit distinction between the classes S2PL and SS2PL, the articles (Breitbart et al. 1991)<ref name=Breit1991>Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, [[Biography:Abraham Silberschatz|Abraham Silberschatz]] (1991): [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=92915 "On Rigorous Transaction Scheduling"], ''IEEE Transactions on Software Engineering'' (TSE), September 1991, Volume 17, Issue 9, pp. 954-960, {{ISSN|0098-5589}}</ref> and (Raz 1992)<ref name="Raz1992">Yoav Raz (1992): [http://www.informatik.uni-trier.de/~ley/db/conf/vldb/Raz92.html "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment"] {{Webarchive|url=https://web.archive.org/web/20070523182950/http://www.informatik.uni-trier.de/~ley/db/conf/vldb/Raz92.html|date=2007-05-23}} ([http://www.vldb.org/conf/1992/P292.PDF PDF]), ''Proceedings of the Eighteenth International Conference on Very Large Data Bases'' (VLDB), pp. 292-312, Vancouver, Canada, August 1992, {{ISBN|1-55860-151-1}} (also DEC-TR 841, [[Company:Digital Equipment Corporation|Digital Equipment Corporation]], November 1990)</ref> have intended to clear the confusion: the first using the name "rigorousness," and the second "SS2PL."
# A more general property than SS2PL exists (a schedule super-class), '''[[Commitment ordering#Strict CO (SCO)|Strict commitment ordering]]''' (Strict CO, or SCO), which as well provides both serializability, strictness, and CO, and has similar locking overhead. Unlike SS2PL, SCO does not block upon a [[Read–write conflict|read-write conflict]] (a read lock does not block acquiring a write lock; both SCO and SS2PL have the same behavior for [[Write–read conflict|write-read]] and [[Write–write conflict|write-write conflicts]]) at the cost of a possible delayed commit, and upon such conflict type SCO has shorter average transaction completion time and better performance than SS2PL.<ref name=Raz1991c>Yoav Raz (1991): "Locking Based Strict Commitment Ordering, or How to improve Concurrency in Locking Based Resource Managers", DEC-TR 844, December 1991.</ref> While SS2PL obeys the ''lock compatibility table'' above, SCO has the following table:
::{| class="wikitable" style="text-align:center;"
|+Lock compatibility for SCO
|-
! Lock type !! read-lock  !! write-lock
|-
! read-lock
|   ||'''X'''
|-
! write-lock
| '''X''' || '''X'''
|}

::Note that though SCO releases all locks at transaction end and complies with the 2PL locking rules, SCO is not a subset of 2PL because of its different lock compatibility table. SCO allows materialized read-write conflicts between two transactions in their phases 1, which 2PL does not allow in phase 1 (see about materialized conflicts in [[Serializability]]).  On the other hand 2PL allows other materialized conflict types in phase 2 that SCO does not allow at all. Together this implies  that the schedule classes 2PL and SCO are incomparable (i.e., no class contains the other class).

===Summary - Relationships among classes===

[[File:CO-ScheduleClasses.jpg|thumb|350px| '''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|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 ''[[Serializability#Testing conflict serializability|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|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|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.<ref>Principles of transaction processing; {{ISBN|9780080948416}}; Chapter 6 Page 152</ref>

In a distributed environment an atomic commitment protocol, typically the Two-phase commit (2PC) protocol, is used for [[Physics:Atomicity (database systems)|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 [[Commitment ordering#Exact characterization of voting-deadlocks by global cycles|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 (computer science)#Thread or process synchronization|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 [[Deadlock#Distributed deadlock|distributed deadlocks]] need to be resolved by dedicated techniques.

==See also==
*[[Serializability]]
*[[Lock (computer science)]]

==References==
{{reflist}}

[[Category:Databases]]
[[Category:Transaction processing]]
[[Category:Concurrency control]]

de:Sperrverfahren#Zwei-Phasen-Sperrprotokoll

{{Sourceattribution|Two-phase locking}}