Concurrency control
In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.
Computer systems, both software and 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, a certain component's consistency may be violated by another component. The general area of concurrency control provides rules, methods, design methodologies, and 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 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 transactions, not only general-purpose database management systems.
- DBMSs need to deal also with concurrency control issues not typical just to database transactions but rather to operating systems in general. These issues are out of the scope of this section.
To ensure correctness, a DBMS usually guarantees that only serializable transaction schedules are generated, unless serializability is intentionally relaxed to increase performance, but only in cases where application correctness is not harmed. For maintaining correctness in cases of failed transactions schedules also need to have the recoverability property. A DBMS also guarantees that no effect of committed transactions is lost, and no effect of aborted transactions remains in the related database. Overall transaction characterization is usually summarized by the ACID rules below. As databases have become distributed, or needed to cooperate in distributed environments, the effective distribution of concurrency control mechanisms has received special attention.
Database transaction and the ACID rules
The concept of a database 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, 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. Every database transaction obeys the following rules :- Atomicity - Either the effects of all or none of its operations remain when a transaction is completed. In other words, to the outside world a committed transaction appears to be indivisible, and an aborted transaction does not affect the database at all. Either all the operations are done or none of them are.
- Consistency - Every transaction must leave the database in a consistent state, i.e., maintain the predetermined integrity rules of the database. A transaction must transform a database from one consistent state to another consistent state. Thus since a database can be normally changed only by transactions, all the database's states are consistent.
- Isolation - Transactions cannot interfere with each other. Moreover, usually the effects of an incomplete transaction are not even visible to another transaction. Providing isolation is the main goal of concurrency control.
- Durability - Effects of successful transactions must persist through crashes.
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 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 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. 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 precedence order between the two transactions, 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.
Concurrency control mechanisms
Categories
The main categories of concurrency control mechanisms are:- Optimistic - Delay the checking of whether a transaction meets the isolation and other integrity rules until its end, without blocking any of its operations, and then abort a transaction to prevent the violation, if the desired rules are to be violated upon its commit. An aborted transaction is immediately restarted and re-executed, which incurs an obvious overhead. If not too many transactions are aborted, then being optimistic is usually a good strategy.
- Pessimistic - Block an operation of a transaction, if it may cause violation of the rules, until the possibility of violation disappears. Blocking operations is typically involved with performance reduction.
- Semi-optimistic - Block operations in some situations, if they may cause violation of some rules, and do not block in other situations while delaying rules checking to transaction's end, as done with optimistic.
The mutual blocking between two transactions or more results in a deadlock, where the transactions involved are stalled and cannot reach completion. Most non-optimistic mechanisms are prone to deadlocks which are resolved by an intentional abort of a stalled transaction, 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, which have each many variants, and in some cases may overlap or be combined, are:- Locking - Controlling access to data by locks assigned to the data. Access of a transaction to a data item locked by another transaction may be blocked until lock release.
- Serialization graph checking - Checking for cycles in the schedule's graph and breaking them by aborts.
- Timestamp ordering - Assigning timestamps to transactions, and controlling or checking access to data by timestamp order.
- Commitment ordering - Controlling or checking transactions' chronological order of commit events to be compatible with their respective precedence order.
- Multiversion concurrency control - 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 depending on scheduling method.
- Index concurrency control - Synchronizing access operations to indexes, rather than to user data. Specialized methods provide substantial performance gains.
- Private workspace model - Each transaction maintains a private workspace for its accessed data, and its changed data become visible outside the transaction only upon its commit. This model provides a different concurrency control behavior with benefits in many cases.
Major goals of concurrency control mechanisms
Concurrency control mechanisms firstly need to operate correctly, i.e., to maintain each transaction's integrity rules 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 over processes, computers, and computer networks. Other subjects that may affect concurrency control are recovery and replication.Correctness
Serializability
For correctness, a common major goal of most concurrency control mechanisms is generating schedules 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 to some serial schedule with the same transactions. Serializability is considered the highest level of isolation among database transactions, and the major correctness criterion for concurrent transactions. In some cases compromised, relaxed forms of serializability are allowed for better performance or to meet availability requirements in highly distributed systems, but only if application's correctness is not violated by the relaxation.Almost all implemented concurrency control mechanisms achieve serializability by providing Conflict serializablity, a broad special case of serializability which can be implemented efficiently.
Recoverability
Comment: While in the general area of systems the term "recoverability" may refer to the ability of a system to recover from failure or from an incorrect/forbidden state, within concurrency control of database systems this term has received a specific meaning.Concurrency control typically also ensures the Recoverability property of schedules for maintaining correctness in cases of aborted transactions. Recoverability means that no committed transaction in a schedule has read data written by an aborted transaction. Such data disappear from the database 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 Strictness, which allows efficient database recovery from failure.
Comment: Note that the Recoverability property is needed even if no database failure occurs and no database recovery from failure is needed. It is rather needed to correctly automatically handle transaction aborts, which may be unrelated to database failure and recovery from it.
Distribution
With the fast technological development of computing the difference between local and distributed computing over low latency networks or buses is blurring. Thus the quite effective utilization of local techniques in such distributed environments is common, e.g., in computer clusters and multi-core processors. However the local techniques have their limitations and use multi-processes supported by multi-processors 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.Distributed serializability and commitment ordering
As database systems have become distributed, or started to cooperate in distributed environments, some transactions have become distributed. A distributed transaction means that the transaction spans processes, and may span computers and geographical sites. This generates a need in effective distributed concurrency control mechanisms. Achieving the Serializability property of a distributed system's schedule effectively poses special challenges typically not met by most of the regular serializability mechanisms, originally designed to operate locally. This is especially due to a need in costly distribution of concurrency control information amid communication and computer latency. The only known general effective technique for distribution is Commitment ordering, which was disclosed publicly in 1991. Commitment ordering means that transactions' chronological order of commit events is kept compatible with their respective precedence order. CO does not require the distribution of concurrency control information and provides a general effective solution for both distributed and global serializability, also in a heterogeneous environment with database systems with different concurrency control mechanisms. CO is indifferent to which mechanism is utilized, since it does not interfere with any transaction operation scheduling, and only determines the order of commit events. Thus, CO enables the efficient distribution of all other mechanisms, and also the distribution of a mix of different local mechanisms, for achieving distributed and global serializability. The existence of such a solution has been considered "unlikely" until 1991, and by many experts also later, due to misunderstanding of the CO solution. An important side-benefit of CO is automatic distributed deadlock resolution. Contrary to CO, virtually all other techniques are prone to distributed deadlocks which need special handling. CO is also the name of the resulting schedule property: A schedule has the CO property if the chronological order of its transactions' commit events is compatible with the respective transactions' precedence order.SS2PL mentioned above is a variant of CO and thus also effective to achieve distributed and global serializability. It also provides automatic distributed deadlock resolution, as well as Strictness and thus Recoverability. Possessing these desired properties together with known efficient locking based implementations explains SS2PL's popularity. SS2PL has been utilized to efficiently achieve Distributed and Global serializability since the 1980, and has become the de facto standard for it. However, SS2PL is blocking and constraining, and with the proliferation of distribution and utilization of systems different from traditional database systems, less constraining types of CO may be needed for better performance.
Comments:
- The Distributed conflict serializability property in its general form is difficult to achieve efficiently, but it is achieved efficiently via its special case Distributed CO: Each local component needs both to provide some form of CO, and enforce a special vote ordering strategy for the Two-phase commit protocol. Differently from the general Distributed CO, Distributed SS2PL exists automatically when all local components are SS2PL based. This fact has been known and utilized since the 1980s for efficient Distributed SS2PL, which implies Distributed serializability and strictness. Less constrained Distributed serializability and strictness can be efficiently achieved by Distributed Strict CO, or by a mix of SS2PL based and SCO based local components.
- About the references and Commitment ordering: was published before the discovery of CO in 1990. The CO schedule property is called Dynamic atomicity in. CO is described in, but the description is partial and misses CO's essence. was the first refereed and accepted for publication article about CO algorithms. Other CO articles followed. note CO as one of the four major concurrency control methods, and CO's ability to provide interoperability among other methods.
Distributed recoverability
As has been mentioned above, Distributed SS2PL, including Distributed strictness and Distributed commitment ordering, automatically employs the needed vote ordering strategy, and is achieved when employed locally in each database system.