View source for Concurrency control

{{Short description|Measures to ensure concurrent computing operations generate correct results}}
{{pp-pc}}
In [[information technology]] and [[computer science]],  especially in the fields of [[computer programming]], [[operating systems]], [[multiprocessor]]s, and [[database]]s, '''concurrency control''' ensures that correct results for [[Concurrent computing|concurrent]] operations are generated, while getting those results as quickly as possible.

Computer systems, both [[software]] and [[computer hardware|hardware]], consist of modules, or components. Each component is designed to operate correctly, i.e., to obey or to meet certain consistency rules. When components that operate concurrently interact by messaging or by sharing accessed data (in [[Computer memory|memory]] or [[Computer data storage|storage]]), a certain component's consistency may be violated by another component. The general area of concurrency control provides rules, methods, design methodologies, and [[Scientific theory|theories]] to maintain the consistency of components operating concurrently while interacting, and thus the consistency and correctness of the whole system. Introducing concurrency control into a system means applying operation constraints which typically result in some performance reduction. Operation consistency and correctness should be achieved with as good as possible efficiency, without reducing performance below reasonable levels. Concurrency control can require significant additional complexity and overhead in a [[concurrent algorithm]] compared to the simpler [[sequential algorithm]].

For example, a failure in concurrency control can result in [[data corruption]] from [[Torn data-access operation|torn read or write operations]].

==Concurrency control in databases==
Comments:
# This section is applicable to all transactional systems, i.e., to all systems that use ''[[database transaction]]s'' (''atomic transactions''; e.g., transactional objects in [[Systems management]] and in networks of [[smartphone]]s which typically implement private, dedicated database systems), not only general-purpose [[database management system]]s (DBMSs).
# DBMSs need to deal also with concurrency control issues not typical just to database transactions but rather to operating systems in general. These issues (e.g., see ''[[Concurrency control#Concurrency control in operating systems|Concurrency control in operating systems]]'' below) are out of the scope of this section.

Concurrency control in [[Database management system]]s (DBMS; e.g., [[#Bern87|Bernstein et al. 1987]], [[#Weikum01|Weikum and Vossen 2001]]), other [[database transaction|transactional]] objects, and related distributed applications (e.g., [[Grid computing]] and [[Cloud computing]]) ensures that ''[[database transaction]]s'' are performed [[Concurrency (computer science)|concurrently]] without violating the [[data integrity]] of the respective [[database]]s. Thus concurrency control is an essential element for correctness in any system where two database transactions or more, executed with time overlap, can access the same data, e.g., virtually in any general-purpose database system. Consequently, a vast body of related research has been accumulated since database systems emerged in the early 1970s. A well established concurrency control [[Scientific theory|theory]] for database systems is outlined in the references mentioned above: [[Serializability|serializability theory]], which allows to effectively design and analyze concurrency control methods and mechanisms. An alternative theory for concurrency control of atomic transactions over [[abstract data type]]s is presented in ([[#Lynch1993|Lynch et al. 1993]]), and not utilized below. This theory is more refined, complex, with a wider scope, and has been less utilized in the Database literature than the classical theory above. Each theory has its pros and cons, emphasis and [[insight]]. To some extent they are complementary, and their merging may be useful.

To ensure correctness, a DBMS usually guarantees that only ''[[Serializability|serializable]]'' [[database transaction schedule|transaction schedules]] are generated, unless ''serializability'' is [[Serializability#Relaxing serializability|intentionally relaxed]] to increase performance, but only in cases where application correctness is not harmed. For maintaining correctness in cases of failed (aborted) transactions (which can always happen for many reasons) schedules also need to have the ''[[Serializability#Correctness - recoverability|recoverability]]'' (from abort) property. A DBMS also guarantees that no effect of ''committed'' transactions is lost, and no effect of ''aborted'' ([[Rollback (data management)|rolled back]]) transactions remains in the related database. Overall transaction characterization is usually summarized by the [[ACID]] rules below. As databases have become [[Distributed database|distributed]], or needed to cooperate in distributed environments (e.g., [[Federated database]]s in the early 1990, and [[Cloud computing]] currently), the effective distribution of concurrency control mechanisms has received special attention.

===Database transaction and the ACID rules===
{{main|Database transaction|ACID}}
The concept of a ''database transaction'' (or ''atomic transaction'') has evolved in order to enable both a well understood database system behavior in a faulty environment where crashes can happen any time, and ''recovery'' from a crash to a well understood database state. A database transaction is a unit of work, typically encapsulating a number of operations over a database (e.g., reading a [[database object]], writing, acquiring lock, etc.), an abstraction supported in database and also other systems. Each transaction has well defined boundaries in terms of which program/code executions are included in that transaction (determined by the transaction's programmer via special transaction commands). Every database transaction obeys the following rules (by support in the database system; i.e., a database system is designed to guarantee them for the transactions it runs):
*'''[[Atomicity (database systems)|Atomicity]]''' - Either the effects of all or none of its operations remain ("all or nothing" semantics) when a [[database transaction|transaction]] is completed (''committed'' or ''aborted'' respectively). In other words, to the outside world a committed transaction appears (by its effects on the database) to be indivisible (atomic), and an aborted transaction does not affect the database at all. Either all the operations are done or none of them are.
*'''[[Consistency (database systems)|Consistency]]''' - Every transaction must leave the database in a consistent (correct) state, i.e., maintain the predetermined integrity rules of the database (constraints upon and among the database's objects). A transaction must transform a database from one consistent state to another consistent state (however, it is the responsibility of the transaction's programmer to make sure that the transaction itself is correct, i.e., performs correctly what it intends to perform (from the application's point of view) while the predefined integrity rules are enforced by the DBMS). Thus since a database can be normally changed only by transactions, all the database's states are consistent.
*'''[[Isolation (database systems)|Isolation]]''' - Transactions cannot interfere with each other (as an end result of their executions). Moreover, usually (depending on concurrency control method) the effects of an incomplete transaction are not even visible to another transaction. Providing isolation is the main goal of concurrency control.
*'''[[Durability (database systems)|Durability]]''' - Effects of successful (committed) transactions must persist through [[Crash (computing)|crash]]es (typically by recording the transaction's effects and its commit event in a [[non-volatile memory]]).

The concept of atomic transaction has been extended during the years to what has become [[Business transaction management|Business transactions]] which actually implement types of [[Workflow]] and are not atomic. However also such enhanced transactions typically utilize atomic transactions as components.

===Why is concurrency control needed?===
If transactions are executed ''serially'', i.e., sequentially with no overlap in time, no transaction concurrency exists. However, if concurrent transactions with interleaving operations are allowed in an uncontrolled manner, some unexpected, undesirable results may occur, such as:
# The [[lost update]] problem: A second transaction writes a second value of a data-item (datum) on top of a first value written by a first concurrent transaction, and the first value is lost to other transactions running concurrently which need, by their precedence, to read the first value. The transactions that have read the wrong value end with incorrect results.
# The [[Write–read conflict|dirty read]] problem: Transactions read a value written by a transaction that has been later aborted. This value disappears from the database upon abort, and should not have been read by any transaction ("dirty read"). The reading transactions end with incorrect results.
# The incorrect summary problem: While one transaction takes a summary over the values of all the instances of a repeated data-item, a second transaction updates some instances of that data-item. The resulting summary does not reflect a correct result for any (usually needed for correctness) precedence order between the two transactions (if one is executed before the other), but rather some random result, depending on the timing of the updates, and whether certain update results have been included in the summary or not.

Most high-performance transactional systems need to run transactions concurrently to meet their performance requirements. Thus, without concurrency control such systems can neither provide correct results nor maintain their databases consistently.

===Concurrency control mechanisms===

====Categories====
The main categories of concurrency control mechanisms are:
* '''[[Optimistic concurrency control|Optimistic]]''' - Allow transactions to proceed without blocking any of their (read, write) operations ("...and be optimistic about the rules being met..."), and only check for violations of the desired integrity rules (e.g., [[serializability]] and [[Serializability#Correctness - recoverability|recoverability]]) at each transaction's commit. If violations are detected upon a transaction's commit, the transaction is aborted and restarted. This approach is very efficient when few transactions are aborted.
* '''Pessimistic''' - Block an operation of a transaction, if it may cause violation of the rules (e.g., serializability and recoverability), until the possibility of violation disappears. Blocking operations is typically involved with performance reduction.
*'''Semi-optimistic''' - Responds pessimistically or optimistically depending on the type of violation and how quickly it can be detected.

Different categories provide different performance, i.e., different average transaction completion rates (''throughput''), depending on transaction types mix, computing level of parallelism, and other factors. If selection and knowledge about trade-offs are available, then category and method should be chosen to provide the highest performance.

The mutual blocking between two transactions (where each one blocks the other) or more results in a [[deadlock (computer science)|deadlock]], where the transactions involved are stalled and cannot reach completion. Most non-optimistic mechanisms (with blocking) are prone to deadlocks which are resolved by an intentional abort of a stalled transaction (which releases the other transactions in that deadlock), and its immediate restart and re-execution. The likelihood of a deadlock is typically low.

Blocking, deadlocks, and aborts all result in performance reduction, and hence the trade-offs between the categories.

====Methods====
Many methods for concurrency control exist. Most of them can be implemented within either main category above. The major methods,<ref name=Bern2009>[[Phil Bernstein|Philip A. Bernstein]], Eric Newcomer (2009): [http://www.elsevierdirect.com/product.jsp?isbn=9781558606234 ''Principles of Transaction Processing'', 2nd Edition] {{Webarchive|url=https://web.archive.org/web/20100807151625/http://www.elsevierdirect.com/product.jsp?isbn=9781558606234 |date=2010-08-07 }}, [[Morgan Kaufmann]] (Elsevier), June 2009, {{ISBN|978-1-55860-623-4}} (page 145)</ref> which have each many variants, and in some cases may overlap or be combined, are:
#Locking (e.g., '''[[Two-phase locking]]''' - 2PL) - Controlling access to data by [[Lock (computer science)|locks]] assigned to the data. Access of a transaction to a data item (database object) locked by another transaction may be blocked (depending on lock type and access operation type) until lock release.
#'''Serialization [[Serializability#Testing conflict serializability|graph checking]]''' (also called Serializability, or Conflict, or Precedence graph checking) - Checking for [[Cycle (graph theory)|cycles]] in the schedule's [[Directed graph|graph]] and breaking them by aborts.
#'''[[Timestamp-based concurrency control|Timestamp ordering]]''' (TO) - Assigning timestamps to transactions, and controlling or checking access to data by timestamp order.

Other major concurrency control types that are utilized in conjunction with the methods above include:

* '''[[Multiversion concurrency control]]''' (MVCC) - Increasing concurrency and performance by generating a new version of a database object each time the object is written, and allowing transactions' read operations of several last relevant versions (of each object) depending on scheduling method.
* '''[[Index locking|Index concurrency control]]''' - Synchronizing access operations to [[Index (database)|index]]es, rather than to user data. Specialized methods provide substantial performance gains.
* '''Private workspace model''' ('''Deferred update''') - Each transaction maintains a private workspace for its accessed data, and its changed data become visible outside the transaction only upon its commit (e.g., [[#Weikum01|Weikum and Vossen 2001]]). This model provides a different concurrency control behavior with benefits in many cases.

The most common mechanism type in database systems since their early days in the 1970s has been ''[[Two-phase locking|Strong strict Two-phase locking]]'' (SS2PL; also called ''Rigorous scheduling'' or ''Rigorous 2PL'') which is a special case (variant) of [[Two-phase locking]] (2PL). It is pessimistic. In spite of its long name (for historical reasons) the idea of the '''SS2PL''' mechanism is simple: "Release all locks applied by a transaction only after the transaction has ended." SS2PL (or Rigorousness) is also the name of the set of all schedules that can be generated by this mechanism, i.e., these SS2PL (or Rigorous) schedules have the SS2PL (or Rigorousness) property.

===Major goals of concurrency control mechanisms===
Concurrency control mechanisms firstly need to operate correctly, i.e., to maintain each transaction's integrity rules (as related to concurrency; application-specific integrity rule are out of the scope here) while transactions are running concurrently, and thus the integrity of the entire transactional system. Correctness needs to be achieved with as good performance as possible. In addition, increasingly a need exists to operate effectively while transactions are [[Distributed transaction|distributed]] over [[Process (computing)|processes]], [[computer]]s, and [[computer network]]s. Other subjects that may affect concurrency control are [[Data recovery|recovery]] and [[Replication (computer science)|replication]].

====Correctness====

=====Serializability=====
{{Main|Serializability}}

For correctness, a common major goal of most concurrency control mechanisms is generating [[database transaction schedule|schedule]]s with the ''[[Serializability]]'' property. Without serializability undesirable phenomena may occur, e.g., money may disappear from accounts, or be generated from nowhere. '''Serializability''' of a schedule means equivalence (in the resulting database values) to some ''serial'' schedule with the same transactions (i.e., in which transactions are sequential with no overlap in time, and thus completely isolated from each other: No concurrent access by any two transactions to the same data is possible). Serializability is considered the highest level of [[isolation (database systems)|isolation]] among [[database transaction]]s, and the major correctness criterion for concurrent transactions. In some cases compromised, [[serializability#Relaxing serializability|relaxed forms]] of serializability are allowed for better performance (e.g., the popular ''[[Snapshot isolation]]'' mechanism) or to meet [[availability]] requirements in highly distributed systems (see ''[[Eventual consistency]]''), but only if application's correctness is not violated by the relaxation (e.g., no relaxation is allowed for [[money]] transactions, since by relaxation money can disappear, or appear from nowhere).

Almost all implemented concurrency control mechanisms achieve serializability by providing ''[[Serializability#View and conflict serializability|Conflict serializability]]'', a broad special case of serializability (i.e., it covers, enables most serializable schedules, and does not impose significant additional delay-causing constraints) which can be implemented efficiently.

=====Recoverability=====
:See ''[[Serializability#Correctness - recoverability|Recoverability]]'' in ''[[Serializability]]''

Concurrency control typically also ensures the ''[[Serializability#Correctness - recoverability|Recoverability]]'' property of schedules for maintaining correctness in cases of aborted transactions (which can always happen for many reasons). '''Recoverability''' (from abort) means that no committed transaction in a schedule has read data written by an aborted transaction. Such data disappear from the database (upon the abort) and are parts of an incorrect database state. Reading such data violates the consistency rule of ACID. Unlike Serializability, Recoverability cannot be compromised, relaxed at any case, since any relaxation results in quick database integrity violation upon aborts. The major methods listed above provide serializability mechanisms. None of them in its general form automatically provides recoverability, and special considerations and mechanism enhancements are needed to support recoverability. A commonly utilized special case of recoverability is ''[[database transaction schedule#Strict|Strictness]]'', which allows efficient database recovery from failure (but excludes optimistic implementations.

====Distribution====
With the fast technological development of computing the difference between local and distributed computing over low latency [[Computer network|networks]] or [[Bus (computing)|buses]] is blurring. Thus the quite effective utilization of local techniques in such distributed environments is common, e.g., in [[computer cluster]]s and [[multi-core processor]]s. However the local techniques have their limitations and use multi-processes (or threads) supported by multi-processors (or multi-cores) to scale. This often turns transactions into distributed ones, if they themselves need to span multi-processes. In these cases most local concurrency control techniques do not scale well.

=====Recovery=====
{{Main|Data recovery}}
All systems are prone to failures, and handling ''[[Data recovery|recovery]]'' from failure is a must. The properties of the generated schedules, which are dictated by the concurrency control mechanism, may affect the effectiveness and efficiency of recovery. For example, the Strictness property (mentioned in the section [[Concurrency control#Recoverability|Recoverability]] above) is often desirable for an efficient recovery.

=====Replication=====
{{Main|Replication (computer science)}}
For high availability database objects are often ''[[Replication (computer science)|replicated]]''. Updates of replicas of a same database object need to be kept synchronized. This may affect the way concurrency control is done (e.g., Gray et al. 1996<ref name=Gray1996>{{cite conference
 | author = Gray, J.
 | author2 = Helland, P.
 | author3-link = Patrick O'Neil
 | author3 = O'Neil, P.
 | author4-link = Dennis Shasha
 | author4 = Shasha, D.
 | year = 1996
 | conference = The dangers of replication and a solution
 | title = Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data
 | pages = 173–182
 | conference-url = ftp://ftp.research.microsoft.com/pub/tr/tr-96-17.pdf
 | doi = 10.1145/233269.233330
 | author-link = Jim Gray (computer scientist)
 | title-link = ACM SIGMOD International Conference on Management of Data
 | doi-access = free
 }}{{Dead link|date=March 2022 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>).

== Concurrency control in operating systems ==
{{Expand section|date=December 2010}}
[[Computer multitasking|Multitasking]] operating systems, especially [[real-time operating system]]s, need to maintain the illusion that all tasks running on top of them are all running at the same time, even though only one or a few tasks really are running at any given moment due to the limitations of the hardware the operating system is running on. Such multitasking is fairly simple when all tasks are independent from each other. However, when several tasks try to use the same resource, or when tasks try to share information, it can lead to confusion and inconsistency. The task of [[concurrent computing]] is to solve that problem. Some solutions involve "locks" similar to the locks used in databases, but they risk causing problems of their own such as [[deadlock (computer science)|deadlock]]. Other solutions are [[Non-blocking algorithm]]s and [[Read-copy-update]].

== See also ==
* {{annotated link|Linearizability}}
* {{annotated link|Lock (computer science)}}
* {{annotated link|Mutual exclusion}}
* {{annotated link|Search engine indexing}}
* {{annotated link|Semaphore (programming)}}
* {{annotated link|Software transactional memory}}
* {{annotated link|Transactional Synchronization Extensions}}
* [[Database transaction schedule]]
* [[Isolation (computer science)]]
* [[Distributed concurrency control]]

== References ==
*  Andrew S. Tanenbaum, Albert S Woodhull (2006): ''Operating Systems Design and Implementation, 3rd Edition'', [[Prentice Hall]], {{ISBN|0-13-142938-8}}
* {{cite book | last = Silberschatz | first = Avi |author2=Galvin, Peter |author3=Gagne, Greg | title = Operating Systems Concepts, 8th edition | publisher = [[John Wiley & Sons]] | year = 2008 | isbn = 978-0-470-12872-5 }}
*<cite id=Bern87>[[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''] (free PDF download), Addison Wesley Publishing Company, 1987, {{ISBN|0-201-10715-5}} </cite>
*<cite id=Weikum01>[[Gerhard Weikum]], Gottfried Vossen (2001): [https://www.elsevier.com/books/transactional-information-systems/weikum/978-1-55860-508-4  ''Transactional Information Systems''], Elsevier, {{ISBN|1-55860-508-8}} </cite>
*<cite id=Lynch1993>[[Nancy Lynch]], Michael Merritt, William Weihl, Alan Fekete (1993): [https://web.archive.org/web/20120715080630/http://www.elsevier.com/wps/find/bookdescription.cws_home/680521/description#description ''Atomic Transactions in Concurrent and Distributed Systems ''], [[Morgan Kaufmann]] (Elsevier), August 1993, {{ISBN|978-1-55860-104-8}}, {{ISBN|1-55860-104-X}} </cite>
*<cite id=Raz92>[[Yoav Raz]] (1992): [https://web.archive.org/web/20070523182950/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."]  ([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. (also DEC-TR 841, [[Digital Equipment Corporation]], November 1990) </cite>

== Citations ==
{{Reflist}}{{Databases}}

{{DEFAULTSORT:Concurrency Control}}
[[Category:Concurrency control| ]]
[[Category:Data management]]
[[Category:Databases]]
[[Category:Transaction processing]]
[[Category:Database management systems]]