In
databaseA database is an integrated collection of logically related records or files consolidated into a common pool that provides data for one or more multiple uses....
s,
transaction processingIn computer science, transaction processing is information processing that is divided into individual, indivisible operations, called transactions. Each transaction must succeed or fail as a complete unit; it cannot remain in an intermediate state....
, and various
transactionalA database transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
applications, both centralized and
distributedDistributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
, a transaction
scheduleIn the fields of databases and transaction processing, a schedule of a system is a list of actions ordered by time from a set of transactions that are executed together in the system...
(history) is
serializable, has the
Serializability property, if its outcome (the resulting database state, the values of the database's data) is equal to the outcome of its transactions executed serially, i.e., sequentially without overlapping in time. Transactions are normally executed concurrently (they overlap), since this is the most efficient way. Serializability is the major correctness criterion for concurrent transactions' executions. It is considered the highest level of
isolationIn database systems, isolation is a property that defines how/when the changes made by one operation become visible to other concurrent operations. Isolation is one of the ACID properties.-Isolation levels:...
between
transactionsA database transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
, and plays an essential role in
concurrency controlIn 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.-Concurrency control in...
. As such it is supported in all general purpose database systems.
Correctness - serializability
Serializability is a property of a transaction
scheduleIn the fields of databases and transaction processing, a schedule of a system is a list of actions ordered by time from a set of transactions that are executed together in the system...
(history). It relates to the
isolation property of a
database transactionA database transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
. For this discussion a database transaction is a specific intended run (with specific parameters, e.g., with transaction identification, at least) of a computer program (or programs) that accesses a database (or databases). Such a program is written with the assumption that it is running in
isolation from other executing programs, i.e., when running, its accessed data (after the access) are not changed by other running programs. Without this assumption the transaction's results are unpredictable and can be wrong. A same transaction can be executed in different situations, e.g., in different times, in parallel with different programs. Serializability of a schedule means equivalence (in the outcome, the database state, data values) to a
serial schedule (i.e., sequential with no transaction overlap in time) with the same transactions. It is the major criterion for the correctness of concurrent transactions' schedule, and thus supported in all general purpose database systems.
The rationale behind serializability is the following:
- If each transaction is correct by itself, i.e., meets certain integrity conditions, then a schedule that comprises any serial execution of these transactions is correct (its transactions still meet their conditions): "Serial" means that transactions do not overlap in time and cannot interfere with each other, i.e, complete isolation between each other exists. Any order of the transactions is legitimate, if no dependencies among them exists, which is assumed. As a result, a schedule that comprises any execution (not necessarily serial) that is equivalent (in its outcome) to any serial execution of these transactions, is correct.
Schedules that are not serializable are likely to generate erroneous outcomes. Well known examples are with transactions that debit and credit accounts with money: If the related schedules are not serializable, then the total sum of money may not be preserved. Money could disappear, or be generated from nowhere. This and violations of possibly needed other
invariantInvariant and invariance may have several meanings, among which are:* Invariant , an expression whose value doesn't change during program execution* In computer science, a type in overriding that is neither covariant nor contravariant...
preservations are caused by one transaction writing, and "stepping on" and erasing what has been written by another transaction before it has become permanent in the database. It does not happen if serializability is maintained.
Comment: If any specific order between some transactions is requested by an application, then it is enforced independently of the underlying serializability mechanisms. These mechanisms are typically indifferent to any specific order, and generate some unpredictable partial order that is typically compatible with multiple serial orders of these transactions. This partial order results from the scheduling orders of concurrent transactions' data access operations, which depend on many factors.
Correctness - recoverability
A major characteristic of a database transaction is
atomicity, which means that it either
commits, i.e., all its operations' results take effect in the database, or
aborts (rolled-back), all its operations' results do not have any effect on the database ("all or nothing" semantics of a transaction). In all real systems transactions can abort for many reasons, and serializability by itself is not sufficient for correctness. Schedules also need to possess the
recoverability property.
Recoverability means that committed transactions have not read data written by aborted transactions (whose effects do not exist in the resulting database states). While serializability is currently compromised on purpose in many applications for better performance (only in cases when application's correctness is not harmed), compromising recoverability would quickly violate the database's integrity, as well as that of transactions' results.
Relaxing serializability
In many applications, unlike with finances, absolute correctness is not needed. For example, when retrieving a list of products according to specification, in most cases it does not matter much if a product, whose data was updated a short time ago, does not appear in the list, even if it meets the specification. It will typically appear in such a list when tried again a short time later. Commercial databases provide concurrency control with a whole range of isolation levels which are in fact (controlled) serializability violations in order to achieve higher performance. Higher performance means better transaction execution rate and shorter average transaction response time (transaction duration).
Classes of schedules defined by
relaxed serializability properties either contain the serializability class, or are incomparable with it.
View and conflict serializability
Mechanisms that enforce serializability need to execute in
real timeIn computer science, real-time computing , or "reactive computing", is the study of hardware and software systems that are subject to a "real-time constraint"—i.e., operational deadlines from event to system response. By contrast, a non-real-time system is one for which there is no deadline, even...
, or almost in real time, while transactions are running at high rates. In order to meet this requirement special cases of serializability, sufficient conditions for serializability which can be enforced effectively, are utilized.
Two major types of serializability exist:
view-serializability, and
conflict-serializability. View-serializability matches the general definition of serializability given above. Conflict-serializability is a broad special case, i.e., any schedule that is conflict-serializable is also view-serializable, but not necessarily the opposite. Conflict-serializability is widely utilized because it is easier to determine and covers a substantial portion of the view-serializable schedules. Determining view-serializability of a schedule is an
NP-completeIn computational complexity theory, the complexity class NP-complete , is a class of problems having two properties...
problem (a class of problems with only difficult-to-compute, excessively time-consuming known solutions).
- View-serializability of a schedule is defined by equivalence to a serial schedule (no overlapping transactions) with the same transactions, such that respective transactions in the two schedules read and write the same data values ("view" the same data values).
- Conflict-serializability is defined by equivalence to a serial schedule (no overlapping transactions) with the same transactions, such that both schedules have the same sets of respective chronologically-ordered pairs of conflicting operations (same precedence relations of respective conflicting operations).
Operations upon data are
read or
write (a write: either
insert or
modify or
delete). Two operations are
conflicting, if they are of different transactions, upon the same
datumA geodetic datum is a reference from which measurements are made. In surveying and geodesy,a datum is a set of reference points on the earth's surface against which position measurements are made, and an associated model of the shape of the earth to define a geographic coordinate system...
(data item), and at least one of them is
write. Each such pair of conflicting operations has a
conflict type: It is either a
read-write, or
write-read, or a
write-write conflict. The transaction of the second operation in the pair is said to be
in conflict with the transaction of the first operation. A more general definition of conflicting operations (also for complex operations, which may consist each of several "simple" read/write operations) requires that they are noncommutative (changing their order also changes their combined result). Each such operation needs to be atomic by itself (by proper system support) in order to be considered an operation for a commutativity check. For example, the operations
increment and
decrement of a
counter are both
write operations (both modify the counter), but do not need to be considered conflicting (write-write conflict type) since they are commutative (e.g., already supported in the old IBM's IMS "fast path"). Only precedence (time order) in pairs of conflicting (non-commutative) operations is important when checking equivalence to a serial schedule, since schedules consisting of the same transactions can be transformed from one to another by changing orders between different transactions' operations (different transactions' interleaving), and since changing orders of commutative operations (non-conflicting) does not change an overall operation sequence result, i.e., a schedule outcome (the outcome is preserved through order change between non-conflicting operations, but typically not when conflicting operations change order). This means that if a schedule can be transformed to any serial schedule without changing orders of conflicting operations (but changing orders of non-conflicting, while preserving operation order inside each transaction), then the outcome of both schedules is the same, and the schedule is conflict-serializable by definition.
Testing conflict serializability
Schedule compliance with conflict serializability can be tested with the
precedence graphA precedence graph, also named conflict graph and serializability graph, is used in the context of concurrency control in databases.The precedence graph for a schedule S contains:* A node for each committed transaction in S...
(
serializability graph,
conflict graph) for committed transactions of the schedule. It is the
directed graphA directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows .It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of...
representing precedence of transactions in the schedule, as reflected by precedence of conflicting operations in the transactions.
- In the precedence graph transactions are nodes and precedence relations are directed edges. There exists an edge from a first transaction to a second transaction, if the second transaction is in conflict with the first (see Conflict serializability above), and the conflict is materialized (i.e., if the requested conflicting operation is actually executed: in many cases a requested/issued conflicting operation by a transaction is delayed and even never executed, typically by a lock
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
on the operation's object, held by another transaction).
- Comment: In many text books only committed transactions are included in the precedence graph. Here all transactions are included for convenience in later discussions.
The following observation is a
key characterization of conflict serializability:
- A schedule is conflict-serializable if and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements. In that it is biconditional, the connective can be likened to the standard material conditional combined with its reverse ; hence the name...
its precedence graph of committed transactions (when only committed transactions are considered) is acyclicIn mathematics, a directed acyclic graph , is a directed graph with no . That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to...
. This means that a cycle consisting of committed transactions only is generated in the (general) precedence graph, if and only if conflict-serializability is violated.
Cycles of committed transactions can be prevented by aborting an
undecided (neither committed, nor aborted) transaction on each cycle in the precedence graph of all the transactions, which can otherwise turn into a cycle of committed transactions (and a committed transaction cannot be aborted). One transaction aborted per cycle is both required and sufficient number to break and eliminate the cycle (more aborts are possible, and can happen in some mechanisms, but unnecessary for serializability). The probability of cycle generation is typically low, but nevertheless, such a situation is carefully handled, typically with a considerable overhead, since correctness is involved. Transactions aborted due to serializability violation prevention are
restarted and executed again immediately.
Serializability enforcing mechanisms typically do not maintain a precedence graph as a data structure, but rather prevent or break cycles implicitly (e.g., SS2PL below).
Common mechanism - SS2PL
Strong strict two phase locking (SS2PL) is a common mechanism utilized in database systems since their early days in the 70ies (the "SS" in the name SS2PL is newer though) to enforce both conflict serializability and
strictness (a special case of recoverability which allows effective database recovery from failure) of a schedule. SS2PL is the name of the resulting schedule property as well, which is also called
rigorousness. In this mechanism each datum is locked by a transaction before accessing it (any read or write operation): The item is marked by, associated with a
lockIn computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
of a certain type, depending on operation (and the specific implementation; various models with different lock types exist; in some models locks may change type during the transaction's life). As a result access by another transaction may be blocked, typically upon a conflict (the lock delays or completely prevents the conflict from being materialized and be reflected in the precedence graph by blocking the conflicting operation), depending on lock type and the other transaction's access operation type. Employing an SS2PL mechanism means that all locks on data on behalf of a transaction are released only after the transaction has ended (either committed or aborted).
Mutual blocking between transactions results in a
deadlockA deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg."...
, where execution of these transactions is stalled, and no completion can be reached. Thus deadlocks need to be resolved to complete these transactions' execution and release related computing resources. A deadlock is a reflection of a potential cycle in the precedence graph, that would occur without the blocking when conflicts are materialized. A deadlocks is resolved by aborting a transaction involved with such potential cycle, and breaking the cycle. It is often detected using a
wait-for graphA Wait-For Graph in computer science is a directed graph used for deadlock detection in operating systems and relational database systems.In Computer Science, a system that allows concurrent operation of multiple processes and locking of resources and which does not provide mechanisms to avoid or...
(a graph of conflicts blocked by locks from being materialized; it can be also defined as the graph of non-materialized conflicts; conflicts not materialized 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. Transactions aborted due to deadlock resolution are
restarted and executed again immediately.
Other enforcing techniques
Other known mechanisms include:
- Precedence graph
A precedence graph, also named conflict graph and serializability graph, is used in the context of concurrency control in databases.The precedence graph for a schedule S contains:* A node for each committed transaction in S...
cycle elimination
- Two-phase locking
In databases and transaction processing, Two-phase locking, is a concurrency control locking protocol, or mechanism, which guarantees serializability . It is also the name of the resulting class of transaction schedules...
(2PL)
- Timestamp ordering
In computer science, in the field of databases, timestamp-based concurrency control is a non-lock concurrency control method, used in relational databases to safely handle transactions, using timestamps.-Assumptions:...
(TO)
- (Local) commitment ordering (CO)
- Serializable snapshot isolation (SerializableSI)
Optimistic versus pessimistic techniques
Concurrency control techniques are of two major types:
- Pessimistic: In Pessimistic concurrency control a transaction blocks data access operations of other transactions upon conflicts, and conflicts are non-materialized until blocking is removed. This to ensure that operations that may violate serializability (and in practice also recoverability) do not occur.
- Optimistic: In Optimistic concurrency control
In the field of relational database management systems, optimistic concurrency control is a concurrency control method that assumes that multiple transactions can complete without affecting each other, and that therefore transactions can proceed without locking the data resources that they affect...
data access operations of other transactions are not blocked upon conflicts, and conflicts are immediately materialized. When the transaction reaches the ready state, i.e., its running state has been completed, possible serializability (and in practice also recoverability) violation by the transaction's operations (relatively to other running transactions) is checked: If violation has ocurred, the transaction is aborted. Otherwise it is committed.
With different transactions loads (mixes of transaction types) one technique type (i.e., either optimistic or pessimistic) may provide better performance than the other.
Some mechanisms mix blocking in certain situations (and thus they are pessimistic) with not blocking in other situations, and have been referred to as
semi-optimistic. Such mechanisms employ both materialized and non-materialized conflicts (e.g., Strict CO (SCO)).
Unless schedule classes are
inherently blocking (i.e., they cannot be implemented without data-access operations blocking; e.g., 2PL, SS2PL and SCO above), they can be implemented also using optimistic techniques.
Overview
Distributed serializability is the serializability of a schedule of a transactional distributed system (e.g., a
distributed databaseA distributed database is a database that is under the control of a central database management system in which storage devices are not all attached to a common CPU. It may be stored in multiple computers located in the same physical location, or may be dispersed over a network of interconnected...
system). Such system is characterized by
distributed transactionA distributed transaction is an operations bundle, in which two or more network hosts are involved. Usually, hosts provide transactional resources, while the transaction manager is responsible for creating and managing a global transaction that encompasses all operations against such resources...
s (also called
global transactions), i.e., transactions that span computer processes that can fail independently, and possibly network nodes. Distributed serializability is a major goal of
distributed concurrency controlDistributed concurrency control relates to the concurrency control of a system distributed over a computer network.In database systems and transaction processing distributed concurrency control relates primarily to the concurrency control of a distributed database...
for correctness. With the prolifaration of the
InternetThe Internet is a global system of interconnected computer networks that use the standardized Internet Protocol Suite to serve billions of users worldwide...
,
Cloud computingCloud computing is the provision of dynamically scalable and often virtualised resources as a service over the Internet on a utility basis. Users need not have knowledge of, expertise in, or control over the technology infrastructure in the "cloud" that supports them...
, and small, portable, powerful computing devices (e.g.,
smartphoneA smartphone is a mobile phone offering advanced capabilities, often with PC-like functionality . There is no industry standard definition of a smartphone. For some, a smartphone is a phone that runs complete operating system software providing a standardized interface and platform for application...
s) the need for effective distributed serializability techniques to ensure correctness in and among distributed applications seems to increase.
Distributed serializability is achieved by implementing distributed versions of the known centralized techniques. Typically all such distributed versions require conflict information (either of materialized or non-materialized conflicts, or equivalently, transaction precedence and blocking information; conflict serializability is usually utilized) that is not generated locally. Thus information distribution is needed (e.g., lock information, timestamps, or tickets). However, due to the distribution of such information substantial performance penalty is typically incurred, primarily due to computer and communication
latencyLatency is a measure of time delay experienced in a system, the precise definition of which depends on the system and the time being measured.-Packet-switched networks:...
. A well known example is using a
distributed lock managerA distributed lock manager provides distributed applications with a means to synchronize their accesses to shared resources.DLMs have been used as the foundation for several successful clustered file systems, in which the machines in a cluster can use each other's storage via a unified file...
which distributes lock (non-materialized conflict) information across the distributed system to implement locking techniques. The only exception, which needs only local information for its distributed version is
Commitment orderingIn databases, transaction processing, and related distributed applications, Commitment ordering is a serializability technique, both centralized and distributed. It allows optimistic implementations. CO is also the name of the resulting transaction schedule property...
(including its many variants).
Distributed serializability and commitment ordering
Commitment orderingIn databases, transaction processing, and related distributed applications, Commitment ordering is a serializability technique, both centralized and distributed. It allows optimistic implementations. CO is also the name of the resulting transaction schedule property...
(CO; or commit ordering, or commit-order-serializability) is a serializability technique, both centralized and distributed. CO is also the name of the resulting schedule property. The most significant aspects of CO that make it a uniquely effective general distributed serializability solution are:
- Seamless, low overhead integration with any concurrency control mechanism, with neither changing any transaction's operation scheduling or blocking it, nor adding any new operation.
- No need of conflict or equivalent information distribution.
- Automatic distributed deadlock resolution, and
- Scalability
The concept of scalability applies to technology and business settings. Regardless of the setting, the base concept is consistent - The ability for a business or technology to accept increased volume without impacting the contribution margin...
.
All these aspects, except the first, are also possessed by the popular SS2PL (see above), since it is a special case of CO, but blocking and constrained.
Under certain general conditions distributed CO can be used effectively for guaranteeing distributed serializability without paying the penalty of distributing conflict information. This is a major distinguishing characteristic of distributed CO from other distributed serializability techniques. CO's net effect may be some commit delays (but no more added delay than that with its special cases, e.g., SS2PL, and on the average less). Instead of distributing conflict information, distributed CO utilizes (unmodified) messages of an atomic commitment protocol (e.g., the
Two-phase commit protocolIn transaction processing, databases, and computer networking, the two-phase commit protocol is a type of an atomic commitment protocol. It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort the...
(2PC)), which are used at any case, also without CO. Such protocol is used to coordinate atomicity of
distributed transactionA distributed transaction is an operations bundle, in which two or more network hosts are involved. Usually, hosts provide transactional resources, while the transaction manager is responsible for creating and managing a global transaction that encompasses all operations against such resources...
s, and is an essential component of any distributed transaction environment.
CO can be applied to many distributed transactional systems for guaranteeing distributed serializability. Three conditions should be met (which can be enforced in the design of most distributed transactional systems):
- Data partition: Recoverable data (or transactional data, i.e., data under transactions' control (not to be confused with the Recoverability property of a schedule)) are partitioned among (possibly distributed) transactional data managers (also called resource managers) that the distributed system comprises, i.e., each recoverable datum (data item) is controlled by a single data manager.
- Participants in atomic commitment protocol: These data managers are the participants of the system's atomic commitment protocol(s) (this requirement is not necessarily met in general, but is quite common and not difficult to be imposed), and
- CO compliance: Each such data manager guarantees CO locally (i.e., has a CO compliant local schedule, which can be quite easily achieved, possibly alongside with any relevant concurrency control mechanism).
These are conditions applied to the distributed system's
transactional data managers (
resource managers).
Distributed CO utilizes the (unmodified) atomic commitment protocol messages without any additional information communicated. This applies also to SS2PL (see above), which is a locking based special case of CO, typically utilized also for distributed serializability, and thus, can be implemented in a distributed transactional system without a
distributed lock managerA distributed lock manager provides distributed applications with a means to synchronize their accesses to shared resources.DLMs have been used as the foundation for several successful clustered file systems, in which the machines in a cluster can use each other's storage via a unified file...
, a fact that in many cases has been overlooked.
An important side-benefit of distributed CO is that
distributed deadlocks (deadlocks which span each two or more transactional data managers) are automatically resolved by atomic commitment (including the case of a completely SS2PL based distributed system).
See more on distributed CO in
Commitment orderingIn databases, transaction processing, and related distributed applications, Commitment ordering is a serializability technique, both centralized and distributed. It allows optimistic implementations. CO is also the name of the resulting transaction schedule property...
, especially in Distributed serializability and CO there, and below in the next sections.
Global serializability and commitment ordering
Guaranteeing distributed serializability in a heterogeneous system that comprises several transactional objects (i.e., with states controlled by atomic transactions) with different concurrency controls has been considered a difficult problem. In such system distributed serializability is usually called
global serializabilityIn databases, transaction processing, and other distributed applications, global serializability is a property of a global schedule of transactions. A global schedule is the unified schedule of all the individual database schedules in a multidatabase environment...
. For example, in a
federated database systemA federated database system is a type of meta-database management system which transparently integrates multiple autonomous database systems into a single federated database. The constituent databases are interconnected via a computer network, and may be geographically decentralized...
or any other more loosely defined multidatabase system, which are typically distributed in a communication network, transactions span multiple (and possibly
distributedA distributed database is a database that is under the control of a central database management system in which storage devices are not all attached to a common CPU. It may be stored in multiple computers located in the same physical location, or may be dispersed over a network of interconnected...
) databases. The database systems involved may utilize different concurrency control mechanism. Even if every local schedule of a single database is serializable, the global schedule of the whole system is not necessarily serializable. The massive communication exchanges of conflict information needed between database systems to reach conflict serializability would lead to unacceptable performance, primarily due to computer and communication
latencyLatency is a measure of time delay experienced in a system, the precise definition of which depends on the system and the time being measured.-Packet-switched networks:...
. The problem of achieving global serializability effectively in such heterogeneous systems had been characterized as
openIn science and mathematics, an open problem or an open question is a known problem that can be accurately stated, and has not yet been solved...
until the introduction of
Commitment orderingIn databases, transaction processing, and related distributed applications, Commitment ordering is a serializability technique, both centralized and distributed. It allows optimistic implementations. CO is also the name of the resulting transaction schedule property...
(CO) in 1991 (see
Global serializabilityIn databases, transaction processing, and other distributed applications, global serializability is a property of a global schedule of transactions. A global schedule is the unified schedule of all the individual database schedules in a multidatabase environment...
). CO provides an effective solution since when each database system in such heterogeneous multidatabase system is CO compliant, the entire system obeys the three conditions for distributed CO given in the previous section, and global serializability is guaranteed, as well as automatic global deadlock (over two or more transactional objects) resolution.
Commitment ordering and how it works in a distributed environment
A
scheduleIn the fields of databases and transaction processing, a schedule of a system is a list of actions ordered by time from a set of transactions that are executed together in the system...
has the
Commitment orderingIn databases, transaction processing, and related distributed applications, Commitment ordering is a serializability technique, both centralized and distributed. It allows optimistic implementations. CO is also the name of the resulting transaction schedule property...
(CO) property, if the order in time of its transactions' commitment events is compatible with the precedence (partial) order of the respective transactions, as determined by their local conflict graph (precedence graph, serializability graph). Any conflict serializable schedule can be made a CO compliant one, without aborting any transaction in the schedule, by delaying commitment events to comply with the needed partial order.
Enforcing the CO property in each local schedule is an effective way to enforce conflict serializability globally: CO is a broad special case of conflict serializability, and enforcing it locally in each local schedule also enforces it, and hence serializability, globally. The only needed communication between the databases for this purpose is that of the
atomic commitment protocol (such as the
Two-phase commit protocolIn transaction processing, databases, and computer networking, the two-phase commit protocol is a type of an atomic commitment protocol. It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort the...
(2PC)), which exists in most distributed environments and already must be utilized for the atomicity of each distributed transaction, independently of concurrency control and CO. Thus CO incurs no communication overhead. In each single database, local CO algorithm can run beside any local concurrency control mechanism (serializability enforcing mechanism) without interfering with its resource access scheduling strategy, and without adding any access operations to transactions, which reduces performance (like acquiring
timestampsIn computer science, in the field of databases, timestamp-based concurrency control is a non-lock concurrency control method, used in relational databases to safely handle transactions, using timestamps.-Assumptions:...
or tickets). As such CO provides a general, high performance, fully distributed solution. No central processing component or central data structure is needed. Moreover, CO works also in heterogeneous environments with different database system types and other multiple transactional objects that employ different serializability mechanisms. The CO solution scales up effectively with network size and the number of databases without any negative impact on performance (assuming the statistics of a single distributed transaction, e.g., the average number of databases involved with such transaction, are unchanged). This makes CO instrumental for
global concurrency controlGlobal concurrency control typically pertains to the concurrency control of a system comprising several components, each with its own concurrency control. Global concurrency control is the concurrency control of the system as a whole....
.
CO implementation by itself is not sufficient as a concurrency control mechanism, since it lacks the important recoverability property.
SS2PL implies CO, and any SS2PL-compliant database can participate in multidatabase systems that utilize the CO solution for global serializability without any modification or addition of a CO algorithm component. As a matter of fact global serializability has been achieved in all-SS2PL multidatabase environments with the Two-phase commit (2PC) protocol since the eighties, and SS2PL in conjunction with 2PC is the
de facto standardA de facto standard is a custom, convention, product, or system that has achieved a dominant position by public acceptance or market forces . De facto is a Latin phrase meaning "concerning the fact" or "in practice"...
to reach global serializability across (the common, SS2PL-compliant) databases. Also the following is true: any CO-compliant database system can transparently join any such existing SS2PL based solution for global serializability.
The commitment event of a distributed transaction is always generated by some
atomic commitment protocol, utilized to reach consensus among its processes on whether to commit or abort it. This procedure is always carried out for distributed transactions, independently of CO. The atomic commitment protocol plays a central role in the distributed CO algorithm. In case of incompatible local commitment orders in two or more databases (no global partial order can embed the respective local partial orders together), which implies a
global cycle (a cycle that spans two or more database) in the global conflict graph, CO generates a
voting-deadlock for the atomic commitment protocol (resulting in missing votes), and the protocol resolves that deadlock by aborting a transaction on the cycle and breaking the cycle. Furthermore: with CO, the
global augmented conflict graph provides a complete characterization of voting-deadlocks. In this graph also being blocked by a lock to prevent a conflict from being materialized is represented by an edge as a materialized conflict. It is the
unionIn set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets gives a set .- Definition :A simple example:...
of the regular
precedence graph with (reversed edge, for time-order compatibility of conflicting operations) regular
wait-for graphA Wait-For Graph in computer science is a directed graph used for deadlock detection in operating systems and relational database systems.In Computer Science, a system that allows concurrent operation of multiple processes and locking of resources and which does not provide mechanisms to avoid or...
, and reflects both materialized and non-materialized conflicts. This graph is a (reversed edge)
wait-for graph for voting (an edge from a first transaction to a second transaction indicates that either the voting or local commit of the first is waiting to the second to end), and a global cycle means a voting-deadlock. Thus also global deadlocks due to locking (when at least one edge for lock blocking exists on a global cycle) generate voting-deadlocks and are resolved automatically by the same mechanism (such locking based global deadlocks are resolved automatically also in the common, completely SS2PL based environments, but no research article besides the CO articles is known to notice this fact). No implementation of such global graph is needed, and it is used only to explain the behavior of CO and its effectiveness in both guaranteeing global serializability and resolving locking-based global deadlocks.