Commitment ordering


Commitment ordering is a class of interoperable serializability techniques in concurrency control of databases, transaction processing, and related applications. It allows optimistic implementations. With the proliferation of multi-core processors, CO has been also increasingly utilized in concurrent programming, transactional memory, and especially in software transactional memory for achieving serializability optimistically. CO is also the name of the resulting transaction schedule property, which was originally defined in 1988 with the name dynamic atomicity. In a CO compliant schedule the chronological order of commitment events of transactions is compatible with the precedence order of the respective transactions. CO is a broad special case of conflict serializability, and effective means to achieve global serializability across any collection of database systems that possibly use different concurrency control mechanisms.
Each not-CO-compliant database system is augmented with a CO component which orders the commitment events for CO compliance, with neither data-access nor any other transaction operation interference. As such CO provides a low overhead, general solution for global serializability, instrumental for global concurrency control of multi database systems and other transactional objects, possibly highly distributed. An atomic commitment protocol is a fundamental part of the solution, utilized to break global cycles in the conflict graph. CO is the most general property that guarantees global serializability, if the database systems involved do not share concurrency control information beyond atomic commitment protocol messages, and have no knowledge whether transactions are global or local. Thus CO is the only general technique that does not require the typically costly distribution of local concurrency control information. It generalizes the popular strong strict two-phase locking property, which in conjunction with the two-phase commit protocol is the de facto standard to achieve global serializability across database systems. As a result, CO compliant database systems can transparently join such SS2PL based solutions for global serializability.
In addition, locking based global deadlocks are resolved automatically in a CO based multi-database environment, an important side-benefit.
Furthermore, strict commitment ordering, the intersection of Strictness and CO, provides better performance than SS2PL whenever read-write conflicts are present. The advantage of SCO is especially significant during lock contention. Strictness allows both SS2PL and SCO to use the same effective database recovery mechanisms.
Two major generalizing variants of CO exist, extended CO and multi-version CO. They as well provide global serializability without local concurrency control information distribution, can be combined with any relevant concurrency control, and allow optimistic implementations. Both use additional information for relaxing CO constraints and achieving better concurrency and performance. Vote ordering is a container schedule set and technique for CO and all its variants. Local VO is a necessary condition for guaranteeing global serializability, if the atomic commitment protocol participants do not share concurrency control information. CO and its variants inter-operate transparently, guaranteeing global serializability and automatic global deadlock resolution also together in a mixed, heterogeneous environment with different variants.

Overview

The Commitment ordering schedule property has been referred to also as Dynamic atomicity, commit ordering, commit order serializability, and strong recoverability. The latter is a misleading name since CO is incomparable with recoverability, and the term "strong" implies a special case. This means that a schedule with a strong recoverability property does not necessarily have the CO property, and vice versa.
In [|2009] CO has been characterized as a major concurrency control method, together with the previously known three major methods: Locking, Time-stamp ordering, and Serialization graph testing, and as an enabler for the interoperability of systems using different concurrency control mechanisms.
In a federated database system or any other more loosely defined multidatabase system, which are typically distributed in a communication network, transactions span multiple and possibly Distributed databases. Enforcing global serializability in such system is problematic. Even if every local schedule of a single database is serializable, still, the global schedule of a whole system is not necessarily serializable. The massive communication exchanges of conflict information needed between databases to reach conflict serializability would lead to unacceptable performance, primarily due to computer and communication latency. The problem of achieving global serializability effectively had been characterized as open until the public disclosure of CO in 1991 by its inventor Yoav Raz.
Enforcing CO is an effective way to enforce conflict serializability globally in a distributed system, since enforcing CO locally in each database also enforces it globally. Each database may use any, possibly different, type of concurrency control mechanism. With a local mechanism that already provides conflict serializability, enforcing CO locally does not cause any additional aborts, since enforcing CO locally does not affect the data access scheduling strategy of the mechanism. The CO solution requires no communication overhead, since it uses atomic commitment protocol messages only, already needed by each distributed transaction to reach atomicity. An atomic commitment protocol plays a central role in the distributed CO algorithm, which enforces CO globally, by breaking global cycles in the global conflict graph.
CO, its special cases, and its generalizations are interoperable, and achieve global serializability while transparently being utilized together in a single heterogeneous distributed environment comprising objects with possibly different concurrency control mechanisms. As such, Commitment ordering, including its special cases, and together with its generalizations, provides a general, high performance, fully distributed solution for guaranteeing global serializability in heterogeneous environments of multidatabase systems and other multiple transactional objects. The CO solution scales up with network size and the number of databases without any negative impact on performance.
With the proliferation of Multi-core processors, Optimistic CO has been also increasingly utilized to achieve serializability in software transactional memory, and numerous STM articles and patents utilizing "commit order" have already been published.

The commitment ordering solution for global serializability

General characterization of CO

Commitment ordering is a special case of conflict serializability. CO can be enforced with non-blocking mechanisms. In a CO schedule the commitment events' precedence order of the transactions corresponds to the precedence order of the respective transactions in the conflict graph, as induced by their conflicting access operations.
;Definition commitment ordering: Let be two committed transactions in a schedule, such that is in a conflict with . The schedule has the Commitment ordering property, if for every two such transactions commits before commits.
The commitment decision events are generated by either a local commitment mechanism, or an atomic commitment protocol, if different processes need to reach consensus on whether to commit or abort. The protocol may be distributed or centralized. Transactions may be committed concurrently, if the commit partial order allows. If different conflicting operations induce different partial orders of same transactions, then the conflict graph has cycles, and the schedule will violate serializability when all the transactions on a cycle are committed. In this case no partial order for commitment events can be found. Thus, cycles in the conflict graph need to be broken by aborting transactions. However, any conflict serializable schedule can be made CO without aborting any transaction, by properly delaying commit events to comply with the transactions' precedence partial order.
CO enforcement by itself is not sufficient as a concurrency control mechanism, since CO lacks the recoverability property, which should be supported as well.

The distributed CO algorithm

A fully distributed Global commitment ordering enforcement algorithm exists, that uses local CO of each participating database, and needs only Atomic commitment protocol messages with no further communication. The distributed algorithm is the combination of local CO algorithm processes, and an atomic commitment protocol.
Atomic commitment protocol is essential to enforce atomicity of each distributed transaction. A common example of an atomic commitment protocol is the two-phase commit protocol, which is resilient to many types of system failure. In a reliable environment, or when processes usually fail together, a simpler protocol for atomic commitment may be used. An atomic commitment protocol reaches consensus among participants on whether to commit or abort a distributed transaction that spans these participants. An essential stage in each such protocol is the YES vote by each participant, which means an obligation of the voting participant to obey the decision of the protocol, either commit or abort. Otherwise a participant can unilaterally abort the transaction by an explicit NO vote. The protocol commits the transaction only if YES votes have been received from all participants, otherwise the protocol aborts the transaction. The various atomic commit protocols only differ in their abilities to handle different computing environment failure situations, and the amounts of work and other computing resources needed in different situations.
The entire CO solution for global serializability is based on the fact that in case of a missing vote for a distributed transaction, the atomic commitment protocol eventually aborts this transaction.

Enforcing global CO

In each database system a local CO algorithm determines the needed commitment order for that database. By the characterization of CO above, this order depends on the local precedence order of transactions, which results from the local data access scheduling mechanisms. Accordingly, YES votes in the atomic commitment protocol are scheduled for each distributed transaction. If a precedence relation exists between two transactions, then the second will not be voted on before the first is completed, to prevent possible commit order violation by the atomic commitment protocol. Such can happen since the commit order by the protocol is not necessarily the same as the voting order. If no precedence relation exists, both can be voted on concurrently. This vote ordering strategy ensures that also the atomic commitment protocol maintains commitment order, and it is a necessary condition for guaranteeing Global CO.
However, since database systems schedule their transactions independently, it is possible that the transactions' precedence orders in two databases or more are not compatible. With CO precedence orders are also the commitment orders. When participating databases in a same distributed transaction do not have compatible local precedence orders for that transaction it means that the transaction resides on a global cycle in the global conflict graph. In this case the atomic commitment protocol will fail to collect all the votes needed to commit that transaction: By the vote ordering strategy above at least one database will delay its vote for that transaction indefinitely, to comply with its own commitment order, since it will be waiting to the completion of another, preceding transaction on that global cycle, delayed indefinitely by another database with a different order. This means a voting-deadlock situation involving the databases on that cycle.
As a result, the protocol will eventually abort some deadlocked transaction on this global cycle, since each such transaction is missing at least one participant's vote. Selection of the specific transaction on the cycle to be aborted depends on the atomic commitment protocol's abort policies. Such abort will break the global cycle involving that distributed transaction. Both deadlocked transactions and possibly other in conflict with the deadlocked will be free to be voted on. It is worthwhile noting that each database involved with the voting-deadlock continues to vote regularly on transactions that are not in conflict with its deadlocked transaction, typically almost all the outstanding transactions. Thus, in case of incompatible local commitment orders, no action is needed since the atomic commitment protocol resolves it automatically by aborting a transaction that is a cause of incompatibility. This means that the above vote ordering strategy is also a sufficient condition for guaranteeing Global CO.
The following is concluded:
  1. The vote ordering strategy that enforces global CO is referred to as in.
  2. The Local CO property of a global schedule means that each database is CO compliant. From the necessity discussion part above it directly follows that the theorem is true also when replacing "Global CO" with "Local CO" when global transactions are present. Together it means that Global CO is guaranteed if and only if Local CO is guaranteed.
Global CO implies Global serializability.
The Global CO algorithm comprises enforcing CO in each participating database system by ordering commits of local transactions and enforcing the vote ordering strategy in the theorem above.

Exact characterization of voting-deadlocks by global cycles

The above global cycle elimination process by a voting deadlock can be explained in detail by the following observation:
First it is assumed, for simplicity, that every transaction reaches the ready-to-commit state and is voted on by at least one database.
Define a "wait for vote to commit" graph as a directed graph with transactions as nodes, and a directed edge from any first transaction to a second transaction if the first transaction blocks the vote to commit of the second transaction. Such blocking happens only if the second transaction is in a conflict with the first transaction. Thus this "wait for vote to commit" graph is identical to the global conflict graph. A cycle in the "wait for vote to commit" graph means a deadlock in voting. Hence there is a deadlock in voting if and only if there is a cycle in the conflict graph. Local cycles are eliminated by the local serializability mechanisms. Consequently, only global cycles are left, which are then eliminated by the atomic commitment protocol when it aborts deadlocked transactions with missing respective votes.
Secondly, also local commits are dealt with: Note that when enforcing CO also waiting for a regular local commit of a local transaction can block local commits and votes of other transactions upon conflicts, and the situation for global transactions does not change also without the simplifying assumption above: The final result is the same also with local commitment for local transactions, without voting in atomic commitment for them.
Finally, blocking by a lock needs to be considered: A lock blocks a conflicting operation and prevents a conflict from being materialized. If the lock is released only after transaction end, it may block indirectly either a vote or a local commit of another transaction, with the same effect as of a direct blocking of a vote or a local commit. In this case a cycle is generated in the conflict graph only if such a blocking by a lock is also represented by an edge. With such added edges representing events of blocking-by-a-lock, the conflict graph is becoming an augmented conflict graph.
  1. is blocked by a data-access lock applied by , and
  2. This blocking will not stop before ends
  3. Here, unlike the regular conflict graph, which has edges only for materialized conflicts, all conflicts, both materialized and non-materialized, are represented by edges.
  4. Note that all the new edges are all the edges of the wait-for graph. The wait-for graph can be defined also as the graph of non-materialized conflicts. By the common conventions edge direction in a conflict graph defines time order between conflicting operations which is opposite to the time order defined by an edge in a wait-for graph.
  5. Note that such global graph contains all the regular local wait-for graphs, and also may include locking based global cycles. For example, if all the databases on a global cycle are SS2PL based, then all the related vote blocking situations are caused by locks. This is a global deadlock case where each related database creates a portion of the cycle, but the complete cycle does not reside in any local wait-for graph.
In the presence of CO the augmented conflict graph is in fact a local-commit and voting wait-for graph: An edge exists from a first transaction, either local or global, to a second, if the second is waiting for the first to end in order to be either voted on, or locally committed. All global cycles in this graph generate voting-deadlocks. The graph's global cycles provide complete characterization for voting deadlocks and may include any combination of materialized and non-materialized conflicts. Only cycles of materialized conflicts are also cycles of the regular conflict graph and affect serializability. One or more non-materialized conflicts on a cycle prevent it from being a cycle in the regular conflict graph, and make it a locking related deadlock. All the global cycles need to be broken to both maintain global serializability and resolve global deadlocks involving data access locking, and indeed they are all broken by the atomic commitment protocol due to missing votes upon a voting deadlock.
Comment: This observation also explains the correctness of Extended CO below: Global transactions' voting order must follow the conflict graph order with vote blocking when order relation exists between two global transactions. Local transactions are not voted on, and their commits are not blocked upon conflicts. This results in same voting-deadlock situations and resulting global cycle elimination process for ECO.
The voting-deadlock situation can be summarized as follows:
Also the following locking based special case is concluded:
  1. Any blocking in the cycle that is not by a data-access lock is a direct blocking of either voting or local commit. All voting-deadlocks are resolved, including this locking-based type.
  2. Locking-based global-deadlocks can be generated also in a completely SS2PL-based distributed environment, where all the vote blocking are caused by data-access locks. Many research articles have dealt for years with resolving such global deadlocks, but none is known to notice that atomic commitment automatically resolves them. Such automatic resolutions are regularly occurring unnoticed in all existing SS2PL based multidatabase systems, often bypassing dedicated resolution mechanisms.
Voting-deadlocks are the key for the operation of distributed CO.
Global cycle elimination and resulting aborted transactions' re-executions are time consuming, regardless of concurrency control used. If databases schedule transactions independently, global cycles are unavoidable. However, in many cases their likelihood can be made very low by implementing database and transaction design guidelines that reduce the number of conflicts involving a global transaction. This, primarily by properly handling hot spots, and avoiding conflicts by using commutativity when possible.
Atomic commitment protocols are intended and designed to achieve atomicity without considering database concurrency control. They abort upon detecting or heuristically finding missing votes, and typically unaware of global cycles. These protocols can be specially enhanced for CO both to prevent unnecessary aborts, and to accelerate aborts used for breaking global cycles in the global augmented conflict graph. For example, existing locking based global deadlock detection methods, other than timeout, can be generalized to consider also local commit and vote direct blocking, besides data access blocking. A possible compromise in such mechanisms is effectively detecting and breaking the most frequent and relatively simple to handle length-2 global cycles, and using timeout for undetected, much less frequent, longer cycles.

Enforcing CO locally

Commitment ordering can be enforced locally by a dedicated CO algorithm, or by any algorithm/protocol that provides any special case of CO. An important such protocol, being utilized extensively in database systems, which generates a CO schedule, is the strong strict two phase locking protocol. SS2PL is a proper subset of the intersection of 2PL and strictness.

A generic local CO algorithm

A generic local CO algorithm is an algorithm independent of implementation details, that enforces exactly the CO property. It does not block data access, and consists of aborting a certain set of transactions upon committing a transaction. It aborts a minimal set of other undecided transactions that run locally and can cause serializability violation in the future. This set consists of all undecided transactions with directed edges in the conflict graph to the committed transaction. The size of this set cannot increase when that transaction is waiting to be committed, and typically decreases in time as its transactions are being decided. Thus, unless real-time constraints exist to complete that transaction, it is preferred to wait with committing that transaction and let this set decrease in size. If another serializability mechanism exists locally, or if no cycle involving that transaction exists, the set will be empty eventually, and no abort of set member is needed. Otherwise the set will stabilize with transactions on local cycles, and aborting set members will have to occur to break the cycles. Since in the case of CO conflicts generate blocking on commit, local cycles in the augments conflict graph indicate local commit-deadlocks, and deadlock resolution techniques as in SS2PL can be used. A local cycle in the augmented conflict graph with at least one non-materialized conflict reflects a locking-based deadlock. The local algorithm above, applied to the local augmented conflict graph rather than the regular local conflict graph, comprises the generic enhanced local CO algorithm, a single local cycle elimination mechanism, for both guaranteeing local serializability and handling locking based local deadlocks. Practically an additional concurrency control mechanism is always utilized, even solely to enforce recoverability. The generic CO algorithm does not affect local data access scheduling strategy, when it runs alongside of any other local concurrency control mechanism. It affects only the commit order, and for this reason it does not need to abort more transactions than those needed to be aborted for serializability violation prevention by any combined local concurrency control mechanism. The net effect of CO may be, at most, a delay of commit events, to comply with the needed commit order.
The following theorem is concluded:
  1. The Generic local CO algorithm guarantees CO.
  2. The Generic enhanced local CO algorithm guarantees both CO and locking based deadlock resolution.

    Example: Concurrent programming and Transactional memory

With the proliferation of Multi-core processors, variants of the Generic local CO algorithm have been also increasingly utilized in Concurrent programming, Transactional memory, and especially in Software transactional memory for achieving serializability optimistically by "commit order". Numerous related articles and patents utilizing CO have already been published.

Implementation considerations: The Commitment Order Coordinator (COCO)

A database system in a multidatabase environment is assumed. From a software architecture point of view a CO component that implements the generic CO algorithm locally, the Commitment Order Coordinator, can be designed in a straightforward way as a mediator between a database system and an atomic commitment protocol component. However, the COCO is typically an integral part of the database system. The COCO's functions are to vote to commit on ready global transactions according to the local commitment order, to vote to abort on transactions for which the database system has initiated an abort, and to pass the atomic commitment decision to the database system. For local transactions no voting is needed. For determining the commitment order the COCO maintains an updated representation of the local conflict graph of the undecided transactions as a data structure. The COCO component has an interface with its database system to receive "conflict," "ready", and "abort" notifications from the database system. It also interfaces with the atomic commitment protocol to vote and to receive the atomic commitment protocol's decision on each global transaction. The decisions are delivered from the COCO to the database system through their interface, as well as local transactions' commit notifications, at a proper commit order. The COCO, including its interfaces, can be enhanced, if it implements another variant of CO, or plays a role in the database's concurrency control mechanism beyond voting in atomic commitment.
The COCO also guarantees CO locally in a single, isolated database system with no interface with an atomic commitment protocol.

CO is a necessary condition for global serializability across autonomous database systems

If the databases that participate in distributed transactions do not use any shared concurrency control information and use unmodified atomic commitment protocol messages, then maintaining commitment ordering or one of its generalizing variants is a necessary condition for guaranteeing global serializability, and a different proof method for this in ); it is also a sufficient condition. This is a mathematical fact derived from the definitions of serializability and a transaction. It means that if not complying with CO, then global serializability cannot be guaranteed under this condition. Atomic commitment is a minimal requirement for a distributed transaction since it is always needed, which is implied by the definition of transaction.
defines database autonomy and independence as complying with this requirement without using any additional local knowledge:
Using this definition the following is concluded:
  1. CO compliance of every autonomous database system in a multidatabase environment is a necessary condition for guaranteeing Global serializability.
  2. CO compliance of every database system is a sufficient condition for guaranteeing Global serializability.
However, the definition of autonomy above implies, for example, that transactions are scheduled in a way that local transactions cannot be identified as such by an autonomous database system. This is realistic for some transactional objects, but too restrictive and less realistic for general purpose database systems. If autonomy is augmented with the ability to identify local transactions, then compliance with a more general property, Extended commitment ordering, makes ECO the necessary condition.
Only in the notion of Generalized autonomy captures the intended notion of autonomy:
This definition is probably the broadest such definition possible in the context of database concurrency control, and it makes CO together with any of its generalizing variants the necessary condition for Global serializability.

Summary

The Commitment ordering solution for global serializability can be summarized as follows:
If each database in a multidatabase environment complies with CO, i.e., arranges its local transactions' commitments and its votes on transactions to the atomic commitment protocol according to the local partial order induced by the local conflict graph for the respective transactions, then Global CO and Global serializability are guaranteed. A database's CO compliance can be achieved effectively with any local conflict serializability based concurrency control mechanism, with neither affecting any transaction's execution process or scheduling, nor aborting it. Also the database's autonomy is not violated. The only low overhead incurred is detecting conflicts, and ordering votes and local transactions' commits according to the conflicts.
In case of incompatible partial orders of two or more databases, a global cycle in the global conflict graph is generated. This, together with CO, results in a cycle of blocked votes, and a voting-deadlock occurs for the databases on that cycle. In this case the atomic commitment protocol fails to collect all the votes needed for the blocked transactions on that global cycle, and consequently the protocol aborts some transaction with a missing vote. This breaks the global cycle, the voting-deadlock is resolved, and the related blocked votes are free to be executed. Breaking the global cycle in the global conflict graph ensures that both global CO and global serializability are maintained. Thus, in case of incompatible local commitment orders no action is needed since the atomic commitment protocol resolves it automatically by aborting a transaction that is a cause for the incompatibility. Furthermore, also global deadlocks due to locking result in voting deadlocks and are resolved automatically by the same mechanism.
Local CO is a necessary condition for guaranteeing Global serializability, if the databases involved do not share any concurrency control information beyond atomic commitment protocol messages, i.e., if the databases are autonomous in the context of concurrency control. This means that every global serializability solution for autonomous databases must comply with CO. Otherwise global serializability may be violated.
The CO solution scales up with network size and the number of databases without performance penalty when it utilizes common distributed atomic commitment architecture.

Distributed serializability and CO

Distributed CO

A distinguishing characteristic of the CO solution to distributed serializability from other techniques is the fact that it requires no conflict information distributed, which makes it uniquely effective. It utilizes atomic commitment protocol messages instead.
A common way to achieve distributed serializability in a system is by a distributed lock manager. DLMs, which communicate lock information in a distributed environment, typically suffer from computer and communication latency, which reduces the performance of the system. CO allows to achieve distributed serializability under very general conditions, without a distributed lock manager, exhibiting the benefits already explored above for multidatabase environments; in particular: reliability, high performance, scalability, possibility of using optimistic concurrency control when desired, no conflict information related communications over the network, and automatic distributed deadlock resolution.
All distributed transactional systems rely on some atomic commitment protocol to coordinate atomicity among processes in a distributed transaction. Also, typically recoverable data are directly accessed by a single transactional data manager component that handles local sub-transactions, even if these data are accessed indirectly by other entities in the distributed system during a transaction. Thus recoverable data in a distributed transactional system are typically partitioned among transactional data managers. In such system these transactional data managers typically comprise the participants in the system's atomic commitment protocol. If each participant complies with CO, then the entire distributed system provides CO, and thus serializability. Furthermore: When CO is utilized together with an atomic commitment protocol also distributed deadlocks caused by data-access locking are resolved automatically. Thus the following corollary is concluded:
  1. Data partition: Recoverable data are partitioned among the data managers, i.e., each recoverable datum is controlled by a single data manager.
  2. Participants in atomic commitment protocol: These data managers are the participants in the system's atomic commitment protocol for coordinating distributed transactions' atomicity.
  3. CO compliance: Each such data manager is CO compliant.
  4. The entire distributed system guarantees serializability, and
  5. Data-access based distributed deadlocks are resolved automatically.
This theorem also means that when SS2PL is used locally in each transactional data manager, and each data manager has exclusive control of its data, no distributed lock manager is needed for distributed SS2PL and serializability. It is relevant to a wide range of distributed transactional applications, which can be easily designed to meet the theorem's conditions.

Distributed optimistic CO (DOCO)

For implementing Distributed Optimistic CO the generic local CO algorithm is utilized in all the atomic commitment protocol participants in the system with no data access blocking and thus with no local deadlocks. The previous theorem has the following corollary:

Distributed SS2PL

A distributed database system that utilizes SS2PL resides on two remote nodes, A and B. The database system has two transactional data managers, one on each node, and the database data are partitioned between the two data managers in a way that each has an exclusive control of its own portion of data: Each handles its own data and locks without any knowledge on the other manager's. For each distributed transaction such data managers need to execute the available atomic commitment protocol.
Two distributed transactions, and, are running concurrently, and both access data x and y. x is under the exclusive control of the data manager on A, and y under that on B.
The respective local sub-transactions on A and B are the following:
The database system's schedule at a certain point in time is the following:
holds a read-lock on x and holds read-locks on y. Thus and are blocked by the lock compatibility rules of SS2PL and cannot be executed. This is a distributed deadlock situation, which is also a voting-deadlock with a distributed cycle of length 2. The local sub-transactions are in the following states:
Since the atomic commitment protocol cannot receive votes for blocked sub-transactions, it will eventually abort some transaction with a missing vote by timeout, either, or,. This will resolve the global deadlock. The remaining transaction will complete running, be voted on, and committed. An aborted transaction is immediately restarted and re-executed.
Comments
  1. The data partition is important since without it, for example, x can be accessed directly from B. If a transaction is running on B concurrently with and and directly writes x, then, without a distributed lock manager the read-lock for x held by on A is not visible on B and cannot block the write of . Thus serializability can be violated.
  2. Due to data partition, x cannot be accessed directly from B. However, functionality is not limited, and a transaction running on B still can issue a write or read request of x. This request is communicated to the transaction's local sub-transaction on A which issues this request to the local data manager on A.

    Variations

In the scenario above both conflicts are non-materialized, and the global voting-deadlock is reflected as a cycle in the global wait-for graph. However the database system can utilize any CO variant with exactly the same conflicts and voting-deadlock situation, and same resolution. Conflicts can be either materialized or non-materialized, depending on CO variant used. For example, if SCO is used by the distributed database system instead of SS2PL, then the two conflicts in the example are materialized, all local sub-transactions are in ready states, and vote blocking occurs in the two transactions, one on each node, because of the CO voting rule applied independently on both A and B: due to conflicts is not voted on before ends, and is not voted on before ends, which is a voting-deadlock. Now the conflict graph has the global cycle, and again it is resolved by the atomic commitment protocol, and distributed serializability is maintained. Unlikely for a distributed database system, but possible in principle, A can employ SS2PL while B employs SCO. In this case the global cycle is neither in the wait-for graph nor in the serializability graph, but still in the augmented conflict graph. The various combinations are summarized in the following table:
CaseNode
A		Node
B		Possible scheduleMaterialized
conflicts
on cycle		Non-
materialized
conflicts
1SS2PLSS2PL02Ready
Voted		Running
Running
Ready
Voted
2SS2PLSCO11Ready
Voted		Ready
Vote blocked		Running
Ready
Voted
3SCOSS2PL11Ready
Voted		Running
Ready
Vote blocked		Ready
Voted
4SCOSCO20Ready
Voted		Ready
Vote blocked		Ready
Vote blocked		Ready
Voted

  1. Conflicts and thus cycles in the augmented conflict graph are determined by the transactions and their initial scheduling only, independently of the concurrency control utilized. With any variant of CO, any global cycle causes a voting deadlock. Different CO variants may differ on whether a certain conflict is materialized or non-materialized.
  2. Some limited operation order changes in the schedules above are possible, constrained by the orders inside the transactions, but such changes do not change the rest of the table.
  3. As noted above, only case 4 describes a cycle in the conflict graph which affects serializability. Cases 1-3 describe cycles of locking based global deadlocks. All cycle types are equally resolved by the atomic commitment protocol. Case 1 is the common Distributed SS2PL, utilized since the 1980s. However, no research article, except the CO articles, is known to notice this automatic locking global deadlock resolution as of 2009. Such global deadlocks typically have been dealt with by dedicated mechanisms.
  4. Case 4 above is also an example for a typical voting-deadlock when Distributed optimistic CO is used : No data-access blocking occurs, and only materialized conflicts exist.

    Hypothetical Multi Single-Threaded Core (MuSiC) environment

Comment: While the examples above describe real, recommended utilization of CO, this example is hypothetical, for demonstration only.
Certain experimental distributed memory-resident databases advocate multi single-threaded core transactional environments. "Single-threaded" refers to transaction threads only, and to serial execution of transactions. The purpose is possible orders of magnitude gain in performance relatively to conventional transaction execution in multiple threads on a same core. In what described below MuSiC is independent of the way the cores are distributed. They may reside in one integrated circuit, or in many chips, possibly distributed geographically in many computers. In such an environment, if recoverable data are partitioned among threads, and it is implemented in the conventional way for distributed CO, as described in previous sections, then DOCO and Strictness exist automatically. However, downsides exist with this straightforward implementation of such environment, and its practicality as a general-purpose solution is questionable. On the other hand, tremendous performance gain can be achieved in applications that can bypass these downsides in most situations.
Comment: The MuSiC straightforward implementation described here is for demonstration only, and has no connection to the implementation in H-Store or any other project.
In a MuSiC environment local schedules are serial. Thus both local Optimistic CO and the Global CO enforcement vote ordering strategy condition for the atomic commitment protocol are met automatically. This results in both distributed CO compliance and automatic global deadlock resolution.
Furthermore, also local Strictness follows automatically in a serial schedule. By Theorem 5.2 in, when the CO vote ordering strategy is applied, also Global Strictness is guaranteed. Note that serial locally is the only mode that allows strictness and "optimistic" together.
The following is concluded:
  1. Local sub-transactions of a global transaction are blocked until commit, which makes the respective cores idle. This reduces core utilization substantially, even if scheduling of the local sub-transactions attempts to execute all of them in time proximity, almost together. It can be overcome by detaching execution from commit for global transactions, at the cost of possible cascading aborts.
  2. increasing the number of cores for a given amount of recoverable data decreases the average amount of data per core. This may make some cores idle, while others very busy, depending on data utilization distribution. Also a local transaction may become global to reach its needed data, with additional incurred overhead. Thus, as the number of cores increases, the amount and type of data assigned to each core should be balanced according to data usage, so a core is neither overwhelmed to become a bottleneck, nor becoming idle too frequently and underutilized in a busy system. Another consideration is putting in a same core partition all the data that are usually accessed by a same transaction, to maximize the number of local transactions. This may be achieved by occasional data re-partition among cores based on load balancing and patterns of data usage by transactions. Another way to considerably mitigate this downside is by proper physical data replication among some core partitions in a way that read-only global transactions are possibly completely avoided, and replication changes are synchronized by a dedicated commit mechanism.

    CO variants: special cases and generalizations

Special case schedule property classes are strictly contained in the CO class. The generalizing classes strictly contain the CO class. The generalizing variants also guarantee global serializability without distributing local concurrency control information, while relaxing CO constraints and utilizing additional information for better concurrency and performance: ECO uses knowledge about transactions being local, and MVCO uses availability of data versions values. Like CO, both generalizing variants are non-blocking, do not interfere with any transaction's operation scheduling, and can be seamlessly combined with any relevant concurrency control mechanism.
The term CO variant refers in general to CO, ECO, MVCO, or a combination of each of them with any relevant concurrency control mechanism or property. No other generalizing variants are known, but may be discovered.

Strong strict two phase locking (SS2PL)

Strong Strict Two Phase Locking means that both read and write locks of a transaction are released only after the transaction has ended. The set of SS2PL schedules is a proper subset of the set of CO schedules.
This property is widely utilized in database systems, and since it implies CO, databases that use it and participate in global transactions generate together a serializable global schedule. No database modification or addition is needed in this case to participate in a CO distributed solution: The set of undecided transactions to be aborted before committing in the local generic CO algorithm above is empty because of the locks, and hence such an algorithm is unnecessary in this case. A transaction can be voted on by a database system immediately after entering a "ready" state, i.e., completing running its task locally. Its locks are released by the database system only after it is decided by the atomic commitment protocol, and thus the condition in the Global CO enforcing theorem above is kept automatically. If a local timeout mechanism is used by a database system to resolve SS2PL deadlocks, then aborting blocked transactions breaks not only potential local cycles in the global conflict graph, but also database system's potential global cycles as a side effect, if the atomic commitment protocol's abort mechanism is relatively slow. Such independent aborts by several entities typically may result in unnecessary aborts for more than one transaction per global cycle. The situation is different for a local wait-for graph based mechanisms: Such cannot identify global cycles, and the atomic commitment protocol will break the global cycle, if the resulting voting deadlock is not resolved earlier in another database.
Local SS2PL together with atomic commitment implying global serializability can also be deduced directly: All transactions, including distributed, obey the 2PL rules. The atomic commitment protocol mechanism is not needed here for consensus on commit, but rather for the end of phase-two synchronization point. Probably for this reason, without considering the atomic commitment voting mechanism, automatic global deadlock resolution has not been noticed before CO.

Strict CO (SCO)

Strict Commitment Ordering is the intersection of strictness and CO, and provides an upper bound for a schedule's concurrency when both properties exist. It can be implemented using blocking mechanisms similar to those used for the popular SS2PL with similar overheads.
Unlike SS2PL, SCO does not block on a read-write conflict but possibly blocks on commit instead. SCO and SS2PL have identical blocking behavior for the other two conflict types: write-read, and write-write. As a result, SCO has shorter average blocking periods, and more concurrency. More concurrency means that with given computing resources more transactions are completed in time unit, and the average duration of a transaction is shorter. The advantage of SCO is especially significant during lock contention.
SCO is as practical as SS2PL since as SS2PL it provides besides serializability also strictness, which is widely utilized as a basis for efficient recovery of databases from failure. An SS2PL mechanism can be converted to an SCO one for better performance in a straightforward way without changing recovery methods. A description of an SCO implementation can be found in. See also Semi-optimistic database scheduler.
SS2PL is a proper subset of SCO.

Optimistic CO (OCO)

For implementing Optimistic commitment ordering the generic local CO algorithm is utilized without data access blocking, and thus without local deadlocks. OCO without transaction or operation scheduling constraints covers the entire CO class, and is not a special case of the CO class, but rather a useful CO variant and mechanism characterization.

Extended CO (ECO)

General characterization of ECO

Extended Commitment Ordering generalizes CO. When local transactions can be distinguished from global transactions, commitment order is applied to global transactions only. Thus, for a local schedule to have the ECO property, the chronological order of commit events of global transactions only is consistent with their order on the respective local conflict graph.
A distributed algorithm to guarantee global ECO exists. As for CO, the algorithm needs only atomic commitment protocol messages. In order to guarantee global serializability, each database needs to guarantee also the conflict serializability of its own transactions by any concurrency control mechanism.
  1. ECO together with local conflict serializability, is a sufficient condition to guarantee global conflict serializability.
  2. When no concurrency control information beyond atomic commitment messages is shared outside a database, and local transactions can be identified, it is also a necessary condition.
This condition is weaker than CO, and allows more concurrency at the cost of a little more complicated local algorithm.
When all the transactions are assumed to be global, ECO reduces to CO.

The ECO algorithm

Before a global transaction is committed, a generic local ECO algorithm aborts a minimal set of undecided transactions, that can cause later a cycle in the conflict graph. This set of aborted transactions can be optimized, if each transaction is assigned with a weight. Like for CO such a set is time dependent, and becomes empty eventually. Practically, almost in all needed implementations a transaction should be committed only when the set is empty. The local concurrency control mechanism ensures that local cycles are eliminated. Local transactions can be always committed concurrently. When the overall transactions' local partial order allows, also global transactions can be voted on to be committed concurrently preceding.
The condition for guaranteeing Global ECO can be summarized similarly to CO:
Global ECO together with Local serializability imply Global serializability. This means that if each database system in a multidatabase environment provides local serializability and enforces the vote ordering strategy in the theorem above, then Global serializability is guaranteed.
Similarly to CO as well, the ECO voting-deadlock situation can be summarized as follows:
As with CO this means that also global deadlocks due to data-access locking are voting deadlocks, and are automatically resolved by atomic commitment.

Multi-version CO (MVCO)

Multi-version Commitment Ordering is a generalization of CO for databases with multi-version resources. With such resources read-only transactions do not block or being blocked for better performance. Utilizing such resources is a common way nowadays to increase 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. MVCO implies One-copy-serializability which is the generalization of serializability for multi-version resources. Like CO, MVCO is non-blocking, and can be combined with any relevant multi-version concurrency control mechanism without interfering with it. In the introduced underlying theory for MVCO conflicts are generalized for different versions of a same resource. For different versions conflict chronological order is replaced by version order, and possibly reversed, while keeping the usual definitions for conflicting operations. Results for the regular and augmented conflict graphs remain unchanged, and similarly to CO a distributed MVCO enforcing algorithm exists, now for a mixed environment with both single-version and multi-version resources. As for CO, the MVCO algorithm needs only atomic commitment protocol messages with no additional communication overhead. Locking-based global deadlocks translate to voting deadlocks and are resolved automatically. In analogy to CO the following holds:
  1. MVCO compliance of every autonomous database system in a mixed multidatabase environment of single-version and multi-version databases is a necessary condition for guaranteeing Global one-copy-serializability.
  2. MVCO compliance of every database system is a sufficient condition for guaranteeing Global 1SER.
  3. Locking-based global deadlocks are resolved automatically.
MVCO can be further generalized to employ the generalization of ECO.

Example: CO based snapshot isolation (COSI)

CO based snapshot isolation is the intersection of Snapshot isolation with MVCO. SI is a multiversion concurrency control method widely utilized due to good performance and similarity to serializability in several aspects. The theory in for MVCO described above is utilized later in and other articles on SI, e.g.,, for analyzing conflicts in SI in order to make it serializable. The method presented in, Serializable snapshot isolation, a low overhead modification of SI, provides good performance results versus SI, with only small penalty for enforcing serializability. A different method, by combining SI with MVCO, makes SI serializable as well, with a relatively low overhead, similarly to combining the generic CO algorithm with single-version mechanisms. Furthermore, the resulting combination, COSI, being MVCO compliant, allows COSI compliant database systems to inter-operate and transparently participate in a CO solution for distributed/global serializability. Besides overheads also protocols' behaviors need to be compared quantitatively. On one hand, all serializable SI schedules can be made MVCO by COSI without aborting transactions. On the other hand, SerializableSI is known to unnecessarily abort and restart certain percentages of transactions also in serializable SI schedules.

CO and its variants are transparently interoperable for global serializability

With CO and its variants global serializability is achieved via atomic commitment protocol based distributed algorithms. For CO and all its variants atomic commitment protocol is the instrument to eliminate global cycles in the global augmented conflict graph. In cases of either incompatible local commitment orders in two or more databases, or a data-access locking related voting deadlock, both implying a global cycle in the global augmented conflict graph and missing votes, the atomic commitment protocol breaks such cycle by aborting an undecided transaction on it. Differences between the various variants exist at the local level only. Each local CO instance of any variant has the same role, to determine the position of every global transaction within the local commitment order, i.e., to determine when it is the transaction's turn to be voted on locally in the atomic commitment protocol. Thus, all the CO variants exhibit the same behavior in regard to atomic commitment. This means that they are all interoperable via atomic commitment and transparently can be utilized together in any distributed environment.
In summary, any single global transaction can participate simultaneously in databases that may employ each any, possibly different, CO variant. The atomic commitment protocol is indifferent to CO, and does not distinguish between the various CO variants. Any global cycle generated in the augmented global conflict graph may span databases of different CO variants, and generate a voting deadlock that is resolved by atomic commitment exactly the same way as in a single CO variant environment. local cycles are resolved locally.
Vote ordering, the union of CO and all its above variants, is a useful concept and global serializability technique. To comply with VO, local serializability and the vote order strategy are needed.
Combining results for CO and its variants, the following is concluded:
  1. In a multi-database environment, where each database system is compliant with some CO variant property, any global transaction can participate simultaneously in databases of possibly different CO variants, and Global serializability is guaranteed.
  2. If only local concurrency control information is utilized by every database system, then compliance of each with some CO variant property is a necessary condition for guaranteeing Global serializability.
  3. Furthermore, in such environment data-access-locking related global deadlocks are resolved automatically, involving at least one data-access lock.

    Footnotes