Обязательный заказ

Упорядочение обязательств ( CO ) — это класс совместимых методов сериализации в параллельном управлении базами данных , обработке транзакций и связанных приложениях. Это позволяет реализовать оптимистичные (неблокирующие) реализации. С распространением многоядерных процессоров CO также все чаще используется в параллельном программировании , транзакционной памяти и программной транзакционной памяти (STM) для достижения оптимистической сериализуемости . CO — это также имя результирующего свойства расписания (истории) транзакций , определенного в 1988 году с именем динамическая атомарность . В расписании, совместимом с CO, хронологический порядок событий фиксации транзакций совместим с порядком приоритета соответствующих транзакций. CO — это широкий частный случай сериализуемости конфликтов и эффективных средств ( надежных , высокопроизводительных, распределенных и масштабируемых ) для достижения глобальной сериализуемости (модульной сериализуемости) в любом наборе систем баз данных, которые могут использовать различные механизмы управления параллелизмом (CO также делает каждый совместимость с сериализуемостью системы, если это еще не сделано).

Each not-CO-compliant database system is augmented with a CO component (the commitment order coordinator—COCO) 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 (and distributed serializability), instrumental for global concurrency control (and distributed concurrency control) of multi-database systems and other transactional objects, possibly highly distributed (e.g., within cloud computing, grid computing, and networks of smartphones). An atomic commitment protocol (ACP; of any type) is a fundamental part of the solution, utilized to break global cycles in the conflict (precedence, serializability) graph. CO is the most general property (a necessary condition) that guarantees global serializability, if the database systems involved do not share concurrency control information beyond atomic commitment protocol (unmodified) messages and have no knowledge of whether transactions are global or local (the database systems are autonomous). Thus CO (with its variants) is the only general technique that does not require the typically costly distribution of local concurrency control information (e.g., local precedence relations, locks, timestamps, or tickets). It generalizes the popular strong strict two-phase locking (SS2PL) property, which in conjunction with the two-phase commit protocol (2PC), is the de facto standard to achieve global serializability across (SS2PL based) database systems. As a result, CO compliant database systems (with any different concurrency control types) 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, a vital side-benefit (including the special case of a completely SS2PL based environment; a previously unnoticed fact for SS2PL).

Furthermore, strict commitment ordering (SCO; Raz 1991c), the intersection of Strictness and CO, provides better performance (shorter average transaction completion time and resulting in better transaction throughput) than SS2PL whenever read-write conflicts are present (identical blocking behavior for write-read and write-write conflicts; comparable locking overhead). The advantage of SCO is especially 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 (ECO; Raz 1993a) and multi-version CO (MVCO; Raz 1993b). They also provide global serializability without local concurrency control information distribution, can be combined with any relevant concurrency control, and allow optimistic (non-blocking) implementations. Both use additional information for relaxing CO constraints and achieving better concurrency and performance. Vote ordering (VO or Generalized CO (GCO); Raz 2009) is a container schedule set (property) and technique for CO and all its variants. Local VO is necessary for guaranteeing global serializability if the atomic commitment protocol (ACP) participants do not share concurrency control information (have the generalized autonomy property). CO and its variants inter-operate transparently, guaranteeing global serializability and automatic global deadlock resolution together in a mixed, heterogeneous environment with different variants.

Overview

The Commitment ordering (CO; Raz 1990, 1992, 1994, 2009) schedule property has been referred to also as Dynamic atomicity (since 1988), commit ordering, commit order serializability, and strong recoverability (since 1991). The latter is a misleading name since CO is incomparable with recoverability, and the term "strong" implies a special case. This means that a substantial 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 (since the 1980s) 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 still serializable, 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 (Raz 1991a; see also Global serializability).

Enforcing CO is an effective way to enforce conflict serializability globally in a distributed system since enforcing CO locally in each database (or other transactional objects) 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 other aborts, since enforcing CO locally does not affect the data access scheduling strategy of the mechanism (this scheduling determines the serializability related aborts; such a mechanism typically does not consider the commitment events or their order). The CO solution requires no communication overhead since it uses (unmodified) 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 (cycles that span two or more databases) 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 (see CO variants below), provides a general, high performance, fully distributed solution (no central processing component or central data structure are needed) for guaranteeing global serializability in heterogeneous environments of multidatabase systems and other multiple transactional objects (objects with states accessed and modified only by transactions; e.g., in the framework of transactional processes, and within Cloud computing and Grid computing). The CO solution scales up 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 a single transaction, are unchanged).

With the proliferation of Multi-core processors, Optimistic CO (OCO) has also been increasingly utilized to achieve serializability in software transactional memory, and numerous STM articles and patents utilizing "commit order" have already been published (e.g., Zhang et al. 2006).

The commitment ordering solution for global serializability

General characterization of CO

Commitment ordering (CO) is a special case of conflict serializability. CO can be enforced with non-blocking mechanisms (each transaction can complete its task without having its data-access blocked, which allows optimistic concurrency control; however, commitment could be blocked). In a CO schedule, the commitment events' (partial) precedence order of the transactions correspond to the precedence (partial) order of the respective transactions in the (directed) conflict graph (precedence graph, serializability graph), as induced by their conflicting access operations (usually read and write (insert/modify/delete) operations; CO also applies to higher-level operations, where they are conflicting if noncommutative, as well as to conflicts between operations upon multi-version data).

Definition: commitment ordering

Let $T_{1},T_{2}$ be two committed transactions in a schedule, such that $T_{2}$ is in a conflict with $T_{1}$ ($T_{1}$ precedes $T_{2}$). The schedule has the Commitment ordering (CO) property, if for every two such transactions $T_{1}$ commits before $T_{2}$ commits.

The commitment decision events are generated by either a local commitment mechanism or an atomic commitment protocol if different processes need to reach a 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 they do not have conflicting operations). Suppose different conflicting operations induce different partial orders of the same transactions. In that case, 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 (unmodified) Atomic commitment protocol messages with no further communication. The distributed algorithm is the combination of local (to each database) CO algorithm processes and an atomic commitment protocol (which can be fully distributed). Atomic commitment protocol is essential to enforce atomicity of each distributed transaction (to decide whether to commit or abort it; this procedure is always carried out for distributed transactions, independently of concurrency control and CO). 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 (e.g., in the same integrated circuit), a simpler protocol for atomic commitment may be used (e.g., a simple handshake of distributed transaction's participating processes with some arbitrary but known special participant, the transaction's coordinator, i.e., a type of one-phase commit protocol). An atomic commitment protocol reaches consensus among participants on whether to commit or abort a distributed (global) transaction that spans these participants. An essential stage in each such protocol is the YES vote (either explicit or implicit) 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 (thus, a missing vote is typically considered a NO). 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 the atomic commitment protocol eventually aborts this transaction in case of a missing vote for a distributed 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 (unaborted) distributed transaction (in what follows, "a vote" means a YES vote). Suppose a precedence relation (conflict) exists between two transactions. In that case, the second will not be voted on before the first is completed (either committed or aborted), 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 (and the local CO of a database; without it both Global CO and Local CO (a property meaning that each database is CO compliant) may be violated).

However, since database systems schedule their transactions independently, it is possible that the transactions' precedence orders in two databases or more are not compatible (no global partial order exists that can embed the respective local partial orders together). With CO, precedence orders are also the commitment orders. When participating databases in the same distributed transaction do not have compatible local precedence orders for that transaction (without "knowing" it; typically no coordination between database systems exists on conflicts, since the needed communication is massive and unacceptably degrades performance) it means that the transaction resides on a global cycle (involving two or more databases) 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 (precedence) order, since it will be waiting to the completion of another, preceding transactions 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 (a timeout mechanism is common, but it may result in more than one needed abort per cycle; both preventing unnecessary aborts and abort time shortening can be achieved by a dedicated abort mechanism for CO). Such abort will break the global cycle involving that distributed transaction. Both deadlocked transactions and possibly others in conflict with the deadlocked (and thus blocked) 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 the case of incompatible local (partial) 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:

• The Vote ordering strategy for Global CO Enforcing Theorem

Let $T_{1},T_{2}$ be undecided (neither committed nor aborted) transactions in a database system that enforces CO for local transactions, such that $T_{2}$ is global and in conflict with $T_{1}$ ($T_{1}$ precedes $T_{2}$). Then, having $T_{1}$ ended (either committed or aborted) before $T_{2}$ is voted on to be committed (the vote ordering strategy), in each such database system in a multidatabase environment, is a necessary and sufficient condition for guaranteeing Global CO (the condition guarantees Global CO, which may be violated without it).

Comments:

1. The vote ordering strategy that enforces global CO is referred to as $CD^{3}C$ in (Raz 1992).
2. The Local CO property of a global schedule means that each database is CO compliant. From the necessity discussion, the part above directly follows that the theorem is also true 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 (which is untrue for Global conflict serializability and Local conflict serializability: Global implies Local, but not the opposite).

Global CO implies Global serializability.

The Global CO algorithm comprises enforcing (local) CO in each participating database system by ordering commits of local transactions (see Enforcing CO locally below) and enforcing the vote ordering strategy in the theorem above (for global transactions).

The 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 (this implies that no blocking by locks occurs). 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 (opposite to conventional edge direction in a wait-for graph). Such blocking happens only if the second transaction conflicts with the first transaction (see above). 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 there is a cycle in the conflict graph. The local serializability mechanisms eliminate local cycles (confined to a single database). Consequently, only global cycles are left, which are then eliminated by the atomic commitment protocol when it aborts deadlocked transactions with missing (blocked) 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 also change without the simplifying assumption above: The final result is the same also with a local commitment for local transactions, without voting in atomic commitment for them.

Finally, blocking by a lock (which has been excluded so far) needs to be considered: A lock blocks a conflicting operation and prevents a conflict from being materialized. Suppose the lock is released only after the transaction end. In that case, it may block indirectly either a vote or a local commit of another transaction (which now cannot get to ready state), with the same effect as a direct blocking of a vote or a local commit. A cycle is generated in the conflict graph only if such 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.

• Definition: augmented conflict graph

An augmented conflict graph is a conflict graph with added edges: In addition to the original edges a directed edge exists from transaction $T_{1}$ to transaction $T_{2}$ if two conditions are met:

1. $T_{2}$ is blocked by a data-access lock applied by $T_{1}$ (the blocking prevents the conflict of $T_{2}$ with $T_{1}$ from being materialized and have an edge in the regular conflict graph), and
2. This blocking will not stop before $T_{1}$ ends (commits or aborts; true for any locking-based CO)

The graph can also be defined as the union of the (regular) conflict graph with the (reversed edge, regular) wait-for graph

Comments:

1. Here, unlike the regular conflict graph, which has edges only for materialized conflicts, all materialized, and non-materialized conflicts are represented by edges.
2. Note that all the new edges are all the (reversed to the conventional) edges of the wait-for graph. The wait-for graph can also be defined 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.
3. Note that such a global graph contains (has embedded) all the (reversed edge) regular local wait-for graphs and also may include locking based global cycles (which cannot exist in the local graphs). 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 the classical and probably the only global deadlock situation dealt with in the database research literature). 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 (reversed edge) 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 (if global) or locally committed (if local). All global cycles (across two or more databases) 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 (only) materialized conflicts are also cycles of the regular conflict graph and affect serializability. One or more (lock related) 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 (voting-deadlocks) need to be broken (resolved) to both maintain global serializability and resolve global deadlocks involving data access locking. 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 (ECO) below: Global transactions' voting order must follow the conflict graph order with vote blocking when order relation (graph path) exists between two global transactions. Local transactions are not voted on, and their (local) commits are not blocked upon conflicts. This results in the same voting-deadlock situations and resulting global cycle elimination process for ECO.

The voting-deadlock situation can be summarized as follows:

• The CO Voting-Deadlock Theorem

Let a multidatabase environment comprise CO compliant (which eliminates local cycles) database systems that enforce each Global CO (using the condition in the theorem above). A voting-deadlock occurs if and only if a global cycle (spans two or more databases) exists in the Global augmented conflict graph (also blocking by a data-access lock is represented by an edge). Suppose the cycle does not break by any abort. In that case, all the global transactions on it are involved with the respective voting-deadlock. Eventually, each has its vote blocked (either directly or indirectly by a data-access lock); if a local transaction resides on the cycle, eventually, it has its (local) commit blocked.

Comment: A rare situation of a voting deadlock (by missing blocked votes) can happen, with no voting for any transaction on the related cycle by any of the database systems involved with these transactions. This can occur when local sub-transactions are multi-threaded. The highest probability instance of such a rare event involves two transactions on two simultaneous opposite cycles. Such global cycles (deadlocks) overlap with local cycles that are resolved locally and are typically resolved by local mechanisms without involving atomic commitment. Formally it is also a global cycle, but practically it is local (portions of local cycles generate a global one; to see this, split each global transaction (node) to local sub-transactions (its portions confined each to a single database); a directed edge exists between transactions if an edge exists between any respective local sub-transactions; a cycle is local if all its edges originate from a cycle among sub-transactions of the same database, and global if not; global and local can overlap: the same cycle among transactions can result from several different cycles among sub-transactions, and be both local and global).

Also, the following locking based special case is concluded:

• The CO Locking-based Global-Deadlock Theorem

In a CO compliant multidatabase system, a locking-based global-deadlock, involving at least one data-access lock (non-materialized conflict), and two or more database systems, is a reflection of a global cycle in the Global augmented conflict graph, which results in a voting-deadlock. Such a cycle is not a cycle in the (regular) Global conflict graph (which reflects only materialized conflicts, so such a cycle does not affect serializability).

Comments:

1. Any blocking (edge) in the cycle that is not by a data-access lock directly blocks either voting or local commit. All voting-deadlocks are resolved (almost all by Atomic commitment; see comment above), including this locking-based type.
2. Locking-based global-deadlocks can also be generated in a completely SS2PL-based distributed environment (special case of CO based). All the vote blocking (and voting-deadlocks) are caused by data-access locks. Many research articles have dealt for years with resolving such global deadlocks, but none (except the CO articles) is known (as of 2009) 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 to the operation of distributed CO.

Global cycle elimination (here voting-deadlock resolution by atomic commitment) and resulting aborted transactions' re-executions are time-consuming, regardless of concurrency control used. If databases schedule transactions independently, global cycles are unavoidable (in a complete analogy to cycles/deadlocks generated in local SS2PL; with distribution, any transaction or operation scheduling coordination results in autonomy violation and is typically in substantial performance penalty). However, their likelihood can be made very low in many cases by implementing database and transaction design guidelines that reduce the number of conflicts involving a global transaction. This, primarily by properly handling hot spots (database objects with frequent access,) and avoiding conflicts by using commutativity when possible (e.g., when extensively using counters, as in finances, and especially multi-transaction accumulation counters, which are typically hot spots).

Atomic commitment protocols are intended and designed to achieve atomicity without considering database concurrency control. They abort upon detecting or heuristically finding (e.g., by a timeout; sometimes mistakenly, unnecessarily) missing votes and typically unaware of global cycles. These protocols can be especially enhanced for CO (including CO's variants below) to prevent unnecessary aborts and accelerate aborts used for breaking global cycles in the global augmented conflict graph (for better performance by earlier release upon transaction-end of computing resources and typically locked data). For example, existing locking based global deadlock detection methods, other than the timeout, can be generalized also to consider 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 (in a single database) 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: "release transaction's locks only after the transaction has been either committed or aborted"; see below). SS2PL is a proper subset of the intersection of 2PL and strictness.

A generic local CO algorithm

A generic local CO algorithm (Raz 1992; Algorithm 4.1) is an algorithm independent of implementation details that enforces exactly the CO property. It does not block data access (nonblocking) and consists of aborting a certain set of transactions (only if needed) upon committing a transaction. It aborts a (uniquely determined at any given time) minimal set of other undecided (neither committed, nor aborted) transactions that run locally and can cause serializability violation in the future (can later generate cycles of committed transactions in the conflict graph; this is the ABORT set of a committed transaction T; after committing T no transaction in ABORT at commit time can be committed, and all of them are doomed to be aborted). 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 (in the ready state: processing has ended,) 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 (which eliminates cycles in the local conflict graph), or if no cycle involving that transaction exists, the set will be empty eventually, and no abort of a 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 (see above) indicate local commit-deadlocks, and deadlock resolution techniques as in SS2PL can be used (e.g., like timeout and wait-for graph). 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 the local data access scheduling strategy when it runs alongside 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. At most, the net effect of CO may be a delay of commit events (or voting in a distributed environment), to comply with the needed commit order (but not more delay than its special cases, for example, SS2PL, and on average significantly less).

The following theorem is concluded:

• The Generic Local CO Algorithm Theorem

When running alone or alongside any concurrency control mechanism in a database system, then

1. The Generic local CO algorithm guarantees (local) CO (a CO compliant schedule).
2. The Generic enhanced local CO algorithm guarantees both (local) CO and (local) locking based deadlock resolution. And (when not using a timeout, and no real-time transaction completion constraints are applied) neither algorithm aborts more transactions than the minimum needed (which is determined by the transactions' operations scheduling, out of the scope of the algorithms).

Example: Concurrent programming and Transactional memory

See also Concurrent programming and Transactional memory.

With the proliferation of Multi-core processors, variants of the Generic local CO algorithm have also been increasingly utilized in Concurrent programming, Transactional memory, and especially in Software transactional memory for achieving serializability optimistically by "commit order" (e.g., Ramadan et al. 2009, Zhang et al. 2006, von Parun et al. 2007). Numerous related articles and patents utilizing CO have already been published.

Implementation considerations: The Commitment Order Coordinator (COCO)

Предполагается, что система баз данных находится в среде с несколькими базами данных. С архитектуры программного обеспечения точки зрения , компонент CO, который локально реализует общий алгоритм CO, Координатор заказов на обязательство (COCO), может быть спроектирован непосредственно как посредник между (единой) системой базы данных и компонентом протокола атомарного принятия ( Raz 1991b). ). Однако COCO обычно является неотъемлемой частью системы базы данных. Функции COCO заключаются в голосовании за фиксацию готовых глобальных транзакций (обработка завершена) в соответствии с локальным порядком фиксации, в голосовании за отмену транзакций, для которых система базы данных инициировала отмену (система базы данных может инициировать отмену любой транзакции). , по многим причинам), а также передать решение об атомарной фиксации в систему базы данных. Для локальных транзакций (если они могут быть идентифицированы) голосование не требуется. Для определения порядка фиксации COCO поддерживает обновленное представление локального графа конфликтов (или локального расширенного графа конфликтов для регистрации также взаимоблокировок) нерешенных (ни зафиксированных, ни прерванных) транзакций в виде структуры данных (например, используя механизмы, аналогичные locking for capturing conflicts, but with no data-access blocking). The COCO component has an interface with its database system to receive "conflict," "ready" (the processing has ended; readiness to vote on a global transaction or commit a local one), and "abort" notifications from the database system. It also interfaces with the atomic commitment protocol to vote and 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 (see below) or plays a role in the database's concurrency control mechanism beyond voting in atomic commitment.

COCO также гарантирует CO локально в единой изолированной системе баз данных без интерфейса с протоколом атомарной фиксации.

CO является необходимым условием глобальной сериализуемости в автономных системах баз данных.

Предположим, что базы данных, которые участвуют в распределенных транзакциях (т. е. транзакциях, которые охватывают более чем одну базу данных), не используют какую-либо общую информацию управления параллелизмом и используют немодифицированные сообщения протокола атомарной фиксации (для достижения атомарности). В этом случае поддержание (локального) обязательного порядка или одного из его обобщающих вариантов (см. ниже) является необходимым условием для обеспечения глобальной сериализуемости (метод доказательства можно найти в ( Raz 1992 ), а другой метод доказательства для этого — в ( Раз 1993а )); это также является достаточным условием . Это математический факт, вытекающий из определений сериализуемости и транзакции . Это означает, что в случае несоблюдения CO глобальная сериализуемость не может быть гарантирована при этом условии (условие отсутствия совместного использования информации управления локальным параллелизмом между базами данных за пределами сообщений протокола атомарной фиксации). Атомарное обязательство — минимальное требование для распределенной транзакции, поскольку оно необходимо всегда, что подразумевается в определении транзакции.

( Раз 1992 ) определяет автономию и независимость базы данных как соответствие этому требованию без использования каких-либо дополнительных местных знаний:

• Определение: (основанная на управлении параллелизмом) автономная система баз данных .

Система базы данных является автономной , если она не передает никакой информации управления параллелизмом, кроме немодифицированных сообщений протокола атомарной фиксации, ни одному другому объекту. Кроме того, он не использует для управления параллелизмом никакой дополнительной локальной информации, помимо конфликтов (последнее предложение не появляется явно, а скорее подразумевается в дальнейшем обсуждении в Raz 1992 ).

Используя это определение, можно сделать следующий вывод:

• Теорема CO и глобальной сериализуемости

1. Соответствие CO каждой автономной системы баз данных (или транзакционного объекта) в среде с несколькими базами данных является необходимым условием для гарантии глобальной сериализуемости (без CO глобальная сериализуемость может быть нарушена).
2. Соответствие CO каждой системе баз данных является достаточным условием для гарантии глобальной сериализуемости.

Однако приведенное выше определение автономии подразумевает, например, что транзакции планируются таким образом, что локальные транзакции (ограниченные одной базой данных) не могут быть идентифицированы как таковые автономной системой баз данных. Это реалистично для некоторых транзакционных объектов, но слишком ограничительно и менее реалистично для систем баз данных общего назначения. Если автономия дополняется возможностью идентифицировать локальные транзакции, то соответствие более общему свойству — порядку с расширенными обязательствами (ECO, см. ниже) — делает ECO необходимым условием.

Только в ( Raz 2009 ) понятие всеобщей автономии отражает предполагаемое понятие автономии:

• Определение: обобщенная автономия

Система базы данных обладает свойством обобщенной автономии, если она не разделяет ни с одной другой системой баз данных никакой информации о локальном параллелизме, кроме (немодифицированных) сообщений протокола атомарной фиксации (однако можно использовать любую локальную информацию).

Это определение, вероятно, является самым широким из возможных определений в контексте управления параллелизмом баз данных, и оно делает CO вместе с любым из его (полезных: нет распределения информации управления параллелизмом) обобщающими вариантами (порядок голосования (VO); см. варианты CO ниже) необходимым условием Глобальной сериализуемости (т. е. объединением СО и его обобщающих вариантов является необходимое множество ВО, в которое также могут входить новые неизвестные полезные обобщающие варианты).

Краткое содержание

Решение (метод) упорядочивания обязательств (CO) для глобальной сериализуемости можно резюмировать следующим образом:

Если каждая база данных (или любой другой транзакционный объект ) в среде с несколькими базами данных соответствует CO, т. е. организует свои обязательства по локальным транзакциям и свои голоса по (глобальным, распределенным) транзакциям в соответствии с протоколом атомарных обязательств в соответствии с локальным (для базы данных) частичный порядок, индуцированный локальным графом конфликтов (графом сериализуемости) для соответствующих транзакций, тогда глобальный CO и глобальная сериализуемость гарантируется . Соответствие базы данных CO может быть эффективно достигнуто с помощью любого механизма управления параллелизмом на основе сериализуемости локальных конфликтов , который не влияет на процесс выполнения или планирование каких-либо транзакций и не прерывает их. Также не нарушается автономность базы данных. Единственные небольшие накладные расходы — это обнаружение конфликтов (например, с блокировкой, но без блокировки доступа к данным; если это еще не обнаружено для других целей) и упорядочивание голосов и фиксаций локальных транзакций в соответствии с конфликтами.

Включение классов расписания: стрелка от класса A к классу B указывает, что класс A строго содержит класс B; отсутствие направленного пути между классами означает, что классы несравнимы. Свойство по своей сути является блокирующим , если его можно реализовать только путем блокировки операций доступа к данным транзакции до тех пор, пока в других транзакциях не произойдут определенные события. ( Раз 1992 )

В случае несовместимых частичных порядков двух или более баз данных (ни один глобальный частичный порядок не может объединить соответствующие локальные частичные порядки вместе), в графе глобальных конфликтов генерируется глобальный цикл (охватывающий две или более базы данных). Это вместе с CO приводит к циклу заблокированных голосов. голосования ( В этом цикле для баз данных происходит тупик однако разрешенное одновременное голосование в каждой базе данных, обычно почти для всех оставшихся голосов, продолжает выполняться). В этом случае протокол атомарной фиксации не может собрать все голоса, необходимые для заблокированных транзакций в этом глобальном цикле. Следовательно, протокол прерывает некоторые транзакции из-за отсутствия голоса. Это разрывает глобальный цикл, тупик голосования разрешается, и соответствующие заблокированные голоса могут быть выполнены свободно. Разрыв глобального цикла в графе глобальных конфликтов гарантирует сохранение глобального CO и глобальной сериализуемости. Таким образом, в случае несовместимых локальных (частичных) ордеров на фиксацию никаких действий не требуется, поскольку протокол атомарной фиксации разрешает ее автоматически, прерывая транзакцию, которая является причиной несовместимости. Кроме того, глобальные взаимоблокировки из-за блокировок (глобальные циклы в расширенный граф конфликтов , по крайней мере, с одной блокировкой доступа к данным) приводят к взаимоблокировкам при голосовании и разрешаются автоматически с помощью того же механизма.

Локальный CO является необходимым условием для гарантии глобальной сериализуемости , если задействованные базы данных не совместно используют какую-либо информацию управления параллелизмом, кроме (немодифицированных) сообщений протокола атомарных обязательств, т. е. если базы данных автономны в контексте управления параллелизмом. Это означает, что каждое решение глобальной сериализуемости для автономных баз данных должно соответствовать CO. В противном случае глобальная сериализуемость может быть нарушена (и, следовательно, она, скорее всего, будет нарушена очень быстро в высокопроизводительной среде).

Решение CO масштабируется в зависимости от размера сети и количества баз данных без снижения производительности, если оно использует общую архитектуру распределенных атомарных обязательств .

Распределенная сериализуемость и CO

Распределенная СО

Отличительной характеристикой решения CO для распределенной сериализации от других методов является тот факт, что оно не требует распространения конфликтной информации (например, отношений локального приоритета, блокировок, временных меток , билетов), что делает его уникально эффективным. Вместо этого он использует (немодифицированные) сообщения протокола атомарной фиксации (которые уже используются).

Распространенным способом достижения распределенной сериализуемости в (распределенной) системе является использование диспетчера распределенных блокировок (DLM). DLM, которые передают информацию о блокировках (нематериализованном конфликте) в распределенной среде, обычно страдают от задержек компьютера и связи , что снижает производительность системы. CO позволяет достичь распределенной сериализуемости в очень общих условиях без диспетчера распределенных блокировок, демонстрируя преимущества, уже рассмотренные выше для сред с несколькими базами данных; в частности: надежность, высокая производительность, масштабируемость, возможность использования оптимистического управления параллелизмом при желании, отсутствие конфликтной информации, связанной с передачей информации по сети (которая приводит к накладным расходам и задержкам), и автоматическое распределенное разрешение взаимоблокировок.

Все распределенные транзакционные системы полагаются на некоторый протокол атомарной фиксации для координации атомарности (фиксации или прерывания) между процессами в распределенной транзакции . Кроме того, обычно восстанавливаемые данные (т. е. данные, находящиеся под контролем транзакций, например, данные базы данных; не путать со свойством восстанавливаемости расписания) напрямую доступны одному компоненту менеджера транзакционных данных (также называемому менеджером ресурсов ). который обрабатывает локальные субтранзакции (часть распределенной транзакции в одном месте, например, сетевой узел), даже если к этим данным косвенно обращаются другие объекты в распределенной системе во время транзакции (т. е. косвенный доступ требует прямого доступа через локальная субтранзакция). Таким образом, восстанавливаемые данные в распределенной транзакционной системе обычно распределяются между менеджерами транзакционных данных. В такой системе эти менеджеры транзакционных данных обычно включают участников системного протокола атомарных обязательств. Если каждый участник соблюдает CO (например, используя SS2PL, или COCO, или их комбинацию; см. выше), то вся распределенная система обеспечивает CO (согласно приведенным выше теоремам; каждый участник может рассматриваться как отдельный транзакционный объект), и, таким образом, (распределенная) сериализуемость. Более того: когда CO используется вместе с протоколом атомного обязательства, также распределенные взаимоблокировки (т. е. взаимоблокировки, охватывающие два или более диспетчера данных), вызванные блокировкой доступа к данным, разрешаются автоматически. Таким образом, делается вывод о следующем следствии:

• Теорема о распределенной сериализуемости на основе CO

Пусть распределенная транзакционная система (например, распределенная система баз данных ) содержит менеджеры транзакционных данных (также называемые менеджерами ресурсов системы ), которые управляют всеми восстанавливаемыми данными . Менеджеры данных отвечают трем условиям:

1. Раздел данных: восстанавливаемые данные разделены между менеджерами данных, т. е. каждый восстанавливаемый элемент данных (элемент данных) контролируется одним менеджером данных (например, как это обычно бывает в архитектуре без общего доступа ; даже копии одних и тех же данных под разными менеджерами данных не физически отличимы, реплицированы ).
2. Участники протокола атомарной фиксации: эти менеджеры данных являются участниками системного протокола атомарной фиксации для координации атомарности распределенных транзакций.
3. Соответствие CO: каждый такой менеджер данных соответствует требованиям CO (или соответствует некоторым вариантам CO; см. ниже).

Затем

1. Вся распределенная система гарантирует (распределенную CO и) сериализуемость , и
2. на основе доступа к данным Распределенные взаимоблокировки (взаимоблокировки с участием двух или более менеджеров данных, по крайней мере, с одним нематериализованным конфликтом) разрешаются автоматически.

Более того: соответствие менеджеров данных CO является необходимым условием для (распределенной) сериализации в системе, соответствующей условиям 1, 2 выше, когда менеджеры данных автономны , т. е. не делятся информацией управления параллелизмом за пределами немодифицированных сообщений протокола атомарной фиксации.

Эта теорема также означает, что когда SS2PL (или любой другой вариант CO) используется локально в каждом диспетчере транзакционных данных и каждый менеджер данных имеет исключительный контроль над своими данными, никакой распределенный менеджер блокировок (который часто используется для обеспечения распределенного SS2PL) не требуется. для распределенного SS2PL и сериализуемости. Это актуально для широкого спектра распределенных транзакционных приложений, которые можно легко спроектировать с учетом условий теоремы.

Распределенная оптимистичная CO (DOCO)

Для реализации распределенного оптимистического CO (DOCO) общий локальный алгоритм CO используется во всех участниках протокола атомарной фиксации в системе без блокировки доступа к данным и, следовательно, без локальных взаимоблокировок. Из предыдущей теоремы следует следующее следствие:

• Теорема о распределенном оптимистическом CO (DOCO)

Если используется DOCO, то:

1. Никаких локальных взаимоблокировок не происходит, и
2. Глобальные взаимоблокировки (голосование) разрешаются автоматически (и все они связаны с сериализуемостью (с неблокирующими конфликтами), а не с блокировкой (с блокирующими и, возможно, неблокирующими конфликтами)).

Таким образом, обработка взаимоблокировок не требуется.

Примеры

Распределенный SS2PL

Система распределенной базы данных, использующая SS2PL , расположена на двух удаленных узлах, A и B. Система базы данных имеет два менеджера транзакционных данных ( менеджеров ресурсов ), по одному на каждом узле, и данные базы данных разделены между двумя менеджерами данных таким образом, что каждый имеет эксклюзивный контроль над своей собственной (локальной по отношению к узлу) частью данных: каждый обрабатывает свои собственные данные и блокирует их без каких-либо знаний о других менеджерах. Для каждой распределенной транзакции такие менеджеры данных должны выполнять доступный протокол атомарной фиксации.

Две распределенные транзакции, $T_{1}$ и $T_{2}$, работают одновременно и оба получают доступ к данным x и y. x находится под исключительным контролем менеджера данных на A (менеджер B не имеет доступа к x), а y — под контролем на B.

$T_{1}$ читает x на A и записывает y на B, т. е. $T_{1}=R_{\text{1A}}(x)$ $W_{\text{1B}}(y)$ при использовании обозначений, общих для управления параллелизмом.

$T_{2}$ читает y на B и записывает x на A, т. е. $T_{2}=R_{\text{2B}}(y)$ $W_{\text{2A}}(x)$

Соответствующие локальные субтранзакции по A и B (части $T_{1}$ и $T_{2}$ на каждом из узлов) следующие:

Локальные субтранзакции

Узел Сделка	А	Б
$T_{1}$	$T_{\text{1A}}=R_{\text{1A}}(x)$	$T_{\text{1B}}=W_{\text{1B}}(y)$
$T_{2}$	$T_{\text{2A}}=W_{\text{2A}}(x)$	$T_{\text{2B}}=R_{\text{2B}}(y)$

системы базы данных Расписание в определенный момент времени следующее:

$R_{\text{1A}}(x)$ $R_{\text{2B}}(y)$

(также $R_{\text{2B}}(y)$ $R_{\text{1A}}(x)$ возможно)

$T_{1}$ удерживает блокировку чтения на x и $T_{2}$ удерживает блокировки чтения на y. Таким образом $W_{\text{1B}}(y)$ и $W_{\text{2A}}(x)$ блокируются правилами совместимости блокировок SS2PL и не могут быть выполнены. Это ситуация распределенного тупика, который также является тупиком голосования (см. ниже) с распределенным (глобальным) циклом длины 2 (количество ребер, конфликтов; 2 — наиболее частая длина). Локальные субтранзакции находятся в следующих состояниях:

$T_{\text{1A}}$ готов ) (выполнение завершено) и проголосовано (в атомарном обязательстве

$T_{\text{1B}}$ запущен ) и заблокирован (нематериализованная конфликтная ситуация, голосование по ней произойти не может

$T_{\text{2B}}$ готов ​ и проголосовал

$T_{\text{2A}}$ запущен . и заблокирован (нематериализованный конфликт; нет голосования)

Поскольку протокол атомарных обязательств не может получать голоса за заблокированные субтранзакции (тупик голосования), он в конечном итоге прервет некоторую транзакцию с отсутствующими голосами по таймауту , либо $T_{1}$, или $T_{2}$, (или и то и другое, если таймауты очень близки). Это позволит разрешить глобальный тупик. Оставшаяся транзакция завершится, будет проголосована и зафиксирована. Прерванная транзакция немедленно перезапускается и выполняется повторно.

Комментарии

1. Раздел данных (x на A; y на B) важен, поскольку без него, например, к x можно получить прямой доступ из B. Если транзакция $T_{3}$ работает на B одновременно с $T_{1}$ и $T_{2}$ и напрямую записывает x, затем, без диспетчера распределенных блокировок, блокировка чтения для x удерживается $T_{1}$ на A не виден на B и не может блокировать запись $T_{3}$ (или сигнализировать о материализовавшемся конфликте для неблокирующего варианта CO; см. ниже). Таким образом, сериализуемость может быть нарушена.
2. Из-за раздела данных к x нельзя получить доступ непосредственно из B. Однако функциональность не ограничена, и транзакция, выполняемая на B, все равно может выдать запрос на запись или чтение x (не часто). Этот запрос передается локальной субтранзакции транзакции на A (которая генерируется, если еще не существует), которая отправляет этот запрос локальному менеджеру данных на A.

Вариации

В приведенном выше сценарии оба конфликта не материализуются , а глобальный тупик голосования отражается как цикл в глобальном графе ожидания (но не в глобальном графе конфликтов ; см. Точную характеристику тупиков голосования с помощью глобальных циклов выше) . Однако система базы данных может использовать любой вариант CO с точно такими же конфликтами и тупиковой ситуацией голосования, а также с тем же разрешением. Конфликты могут быть как материализованными , так и нематериализованными , в зависимости от используемого варианта СО. Например, если SCO система распределенной базы данных использует (ниже) вместо SS2PL, то два конфликта в примере материализуются , все локальные субтранзакции находятся в состоянии готовности , и блокировка голосования происходит в двух транзакциях, одна из которых на каждом узле, поскольку правило голосования CO применяется независимо как к A, так и к B: из-за конфликтов $T_{\text{2A}}=W_{\text{2A}}(x)$ не голосуется раньше $T_{\text{1A}}=R_{\text{1A}}(x)$ заканчивается, и $T_{\text{1B}}=W_{\text{1B}}(y)$ не голосуется раньше $T_{\text{2B}}=R_{\text{2B}}(y)$ заканчивается, что представляет собой тупик голосования. Теперь граф конфликтов имеет глобальный цикл (все конфликты материализуются), и он снова разрешается протоколом атомарной фиксации, при этом сохраняется распределенная сериализуемость. Маловероятно для системы распределенных баз данных, но в принципе возможно (и встречается в системах с несколькими базами данных), что A может использовать SS2PL, а B — SCO. В этом случае глобальный цикл находится не в графе ожидания и не в графе сериализуемости, а все еще в расширенном графе конфликтов (объединении двух). Различные комбинации сведены в следующую таблицу:

Тупиковые ситуации голосования

Случай	Узел А	Узел Б	Возможный график	Материализованный конфликты на цикле	Не- материализованный конфликты	$T_{\text{1A}}=R_{\text{1A}}(x)$	$T_{\text{1B}}=W_{\text{1B}}(y)$	$T_{\text{2A}}=W_{\text{2A}}(x)$	$T_{\text{2B}}=R_{\text{2B}}(y)$
1	СС2ПЛ	СС2ПЛ	$R_{\text{1A}}(x)R_{\text{2B}}(y)$	0	2	Готовый Проголосовали	Бег (Заблокировано)	Бег (Заблокировано)	Готовый Проголосовали
2	СС2ПЛ	ШОС	$R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)$	1	1	Готовый Проголосовали	Готовый Голосование заблокировано	Бег (Заблокировано)	Готовый Проголосовали
3	ШОС	СС2ПЛ	$R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{2A}}(x)$	1	1	Готовый Проголосовали	Бег (Заблокировано)	Готовый Голосование заблокировано	Готовый Проголосовали
4	ШОС	ШОС	$R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)W_{\text{2A}}(x)$	2	0	Готовый Проголосовали	Готовый Голосование заблокировано	Готовый Голосование заблокировано	Готовый Проголосовали

Комментарии:

1. Конфликты и, следовательно, циклы в расширенном графе конфликтов определяются только транзакциями и их первоначальным планированием, независимо от используемого управления параллелизмом. При любом варианте CO любой глобальный цикл (т. е. охватывающий две или более базы данных) приводит к тупику голосования . определенный конфликт Различные варианты СО могут различаться в зависимости от того, материализован или нематериализован .
2. Возможны некоторые ограниченные изменения порядка операций в приведенных выше графиках, ограниченные заказами внутри транзакций, но такие изменения не меняют остальную часть таблицы.
3. Как отмечалось выше, только случай 4 описывает цикл в (обычном) графе конфликтов, который влияет на сериализуемость. Случаи 1-3 описывают циклы глобальных взаимоблокировок на основе блокировок (существует хотя бы одна блокировка блокировки). Все типы циклов одинаково разрешаются протоколом атомарных обязательств. Случай 1 — это обычный распределенный SS2PL, используемый с 1980-х годов. Однако по состоянию на 2009 год ни в одной исследовательской статье, за исключением статей CO, не упоминается об этой автоматической блокировке разрешения глобальных взаимоблокировок. Такие глобальные взаимоблокировки обычно решаются с помощью специальных механизмов.
4. Случай 4, приведенный выше, также является примером типичного тупика голосования, когда используется распределенный оптимистический CO (DOCO) (т. е. случай 4 не изменяется, когда оптимистический CO (OCO; см. ниже) заменяет SCO как на A, так и на B): Нет данных. происходит блокировка доступа и существуют только материализованные конфликты.

Гипотетическая многопоточная среда с однопоточным ядром (MuSiC)

Комментарий: Хотя приведенные выше примеры описывают реальное рекомендуемое использование CO, этот пример является гипотетическим и предназначен только для демонстрации.

Некоторые экспериментальные распределенные резидентные базы данных поддерживают многопоточные транзакционные среды (MuSiC). «Однопоточный» относится только к потокам транзакций и последовательному выполнению транзакций. Целью является возможное повышение производительности на порядки (например, H-Store и VoltDB ) по сравнению с обычным выполнением транзакций в нескольких потоках на одном ядре. То, что описано ниже, MuSiC не зависит от способа распределения ядер. Они могут находиться в одной интегральной схеме (чипе) или во многих чипах, возможно, географически распределенных по многим компьютерам. В такой среде, если восстанавливаемые (транзакционные) данные разделены между потоками (ядрами) и реализованы обычным способом для распределенной CO, как описано в предыдущих разделах, то DOCO и Strictness существуют автоматически. Однако такая простая реализация такой среды имеет свои недостатки, и ее практичность как решения общего назначения сомнительна. С другой стороны, огромный прирост производительности может быть достигнут в приложениях, которые в большинстве ситуаций могут обойти эти недостатки.

Комментарий: Описанная здесь простая реализация MuSiC (которая использует, например, как обычно в распределенном CO, блокировку голосования (и потока транзакций) в протоколе атомарной фиксации, когда это необходимо) предназначена только для демонстрации и не имеет никакого отношения к реализации в H- Магазин или любой другой проект.

В среде MuSiC локальные расписания являются последовательными . Таким образом, как локальное оптимистическое CO (OCO; см. ниже), так и условие глобальной стратегии порядка голосования CO для протокола атомарных обязательств выполняются автоматически. Это приводит как к соблюдению требований распределенного CO (и, следовательно, к распределенной сериализуемости), так и к автоматическому разрешению глобальных тупиковых ситуаций (голосованием).

Кроме того, локальная строгость в последовательном расписании автоматически следует . По теореме 5.2 из ( Raz 1992 ; стр. 307), когда применяется стратегия упорядочения голосов CO, также гарантируется глобальная строгость. Обратите внимание, что локальный последовательный режим — единственный режим, который позволяет сочетать строгость и «оптимизм» (без блокировки доступа к данным).

Делается следующий вывод:

• Теорема MuSiC

В средах MuSiC, если восстанавливаемые (транзакционные) данные разделены между ядрами (потоками), то оба

1. OCO (и подразумеваемая сериализуемость ; т. е. DOCO и распределенная сериализуемость)
2. Строгость (позволяющая эффективное восстановление; 1 и 2 подразумевают строгий CO — см. SCO ниже) и
3. (голосование) разрешение тупиковой ситуации

автоматически существуют глобально с неограниченной масштабируемостью по количеству используемых ядер.

Комментарий: Однако могут существовать два основных недостатка, которые требуют особого подхода:

1. Локальные субтранзакции глобальной транзакции блокируются до момента фиксации, в результате чего соответствующие ядра простаивают. Это существенно снижает загрузку ядра, даже если планирование локальных субтранзакций пытается выполнить их все одновременно, почти одновременно. Эту проблему можно преодолеть, отделив выполнение от фиксации (с помощью некоторого протокола атомарной фиксации) для глобальных транзакций за счет возможных каскадных прерываний.
2. Увеличение количества ядер для заданного объема восстанавливаемых данных (размера базы данных) уменьшает средний объем (разделенных) данных на ядро. Это может привести к тому, что некоторые ядра будут простаивать, а другие — очень заняты, в зависимости от распределения использования данных. Кроме того, локальная (по отношению к ядру) транзакция может стать глобальной (многоядерной) для достижения необходимых данных, что приведет к дополнительным накладным расходам. Таким образом, по мере увеличения количества ядер объем и тип данных, назначаемых каждому ядру, должны быть сбалансированы в соответствии с использованием данных, чтобы ядро ​​не было перегружено и не становилось узким местом, а также не слишком часто простаивало и недостаточно использовалось в загруженной системе. Еще одним соображением является размещение в одном основном разделе всех данных, к которым обычно обращается одна и та же транзакция (если это возможно), чтобы максимизировать количество локальных транзакций (и минимизировать количество глобальных распределенных транзакций). Этого можно достичь путем периодического перераспределения данных между ядрами на основе балансировки нагрузки (балансировки доступа к данным) и шаблонов использования данных транзакциями. Другой способ значительно смягчить этот недостаток — правильная физическая репликация данных между некоторыми основными разделами таким образом, чтобы (в зависимости от шаблонов использования) полностью исключались глобальные транзакции только для чтения, а изменения репликации синхронизировались с помощью специального механизма фиксации.

Варианты СО: частные случаи и обобщения

Классы свойств расписания особых случаев (например, SS2PL и SCO ниже) строго содержатся в классе CO. Обобщающие классы (ECO и MVCO) строго содержат класс CO (т. е. включают также расписания, не соответствующие CO). Обобщающие варианты также гарантируют глобальную сериализуемость без распространения локальной информации управления параллелизмом (каждая база данных обладает свойством обобщенной автономии : она использует только локальную информацию), одновременно ослабляя ограничения CO и используя дополнительную (локальную) информацию для лучшего параллелизма и производительности: ECO использует знания о транзакции являются локальными (т. е. ограничены одной базой данных), а MVCO использует значения доступности версий данных. Как и CO, оба обобщающих варианта являются неблокирующими , не мешают планированию операций каких-либо транзакций и могут легко сочетаться с любым соответствующим механизмом управления параллелизмом.

Термин «вариант CO» в целом относится к CO, ECO, MVCO или комбинации каждого из них с любым соответствующим механизмом или свойством управления параллелизмом (включая ECO на основе нескольких версий, MVECO). Никакие другие обобщающие варианты (которые гарантируют глобальную сериализуемость без локального распределения информации управления параллелизмом) неизвестны, но могут быть обнаружены.

Сильная строгая двухфазная блокировка (SS2PL)

Основная статья: Двухфазная блокировка

Строгая строгая двухфазная блокировка (SS2PL; также называемая строгостью или строгим планированием ) означает, что блокировки чтения и записи транзакции снимаются только после завершения транзакции (либо фиксации, либо прерывания). Набор расписаний SS2PL является подмножеством набора расписаний CO. Это свойство широко используется в системах баз данных, и, поскольку оно подразумевает CO, базы данных, которые его используют и участвуют в глобальных транзакциях, вместе генерируют сериализуемый глобальный график (при использовании любого протокола атомарной фиксации, который необходим для атомарности в среде с несколькими базами данных). . В этом случае для участия в распределенном решении CO не требуется никаких изменений или дополнений базы данных: набор нерешенных транзакций, которые должны быть прерваны перед фиксацией в приведенном выше локальном общем алгоритме CO, пуст из-за блокировок, и, следовательно, такой алгоритм не нужен в этот случай. Система баз данных может проголосовать за транзакцию сразу после перехода в состояние «готовности», т. е. завершения локального выполнения своей задачи. Его блокировки снимаются системой базы данных только после того, как это будет решено протоколом атомарной фиксации, и, таким образом, условие в Приведенная выше теорема о глобальном соблюдении CO сохраняется автоматически. Если механизм локального тайм-аута используется системой баз данных для разрешения (локальных) взаимоблокировок SS2PL, то прерывание заблокированных транзакций нарушает не только потенциальные локальные циклы в глобальном графе конфликтов (реальные циклы в расширенном графе конфликтов), но и потенциальные глобальные циклы системы базы данных. циклов как побочный эффект, если механизм прерывания протокола атомарной фиксации относительно медленный. Такие независимые прерывания несколькими объектами обычно могут привести к ненужным прерываниям более чем одной транзакции за глобальный цикл. Ситуация иная для механизмов, основанных на локальных графах ожидания : они не могут идентифицировать глобальные циклы, и протокол атомарной фиксации разорвет глобальный цикл, если возникший в результате тупик голосования не будет разрешен ранее в другой базе данных.

Локальный SS2PL вместе с атомарным обязательством, подразумевающим глобальную сериализуемость, также может быть выведен напрямую: все транзакции, включая распределенные, подчиняются правилам 2PL (SS2PL). Механизм протокола атомарной фиксации здесь необходим не для достижения консенсуса по фиксации, а скорее для завершения точки синхронизации второй фазы. Вероятно, по этой причине, без учета механизма голосования по атомарным обязательствам, автоматическое разрешение глобальных тупиков не было замечено до CO.

Строгий CO (SCO)

Конфликт чтения и записи: SCO Vs. СС2ПЛ . Продолжительность транзакции T2 у SS2PL больше, чем у SCO. SS2PL задерживает операцию записи w2[x] из T2 до тех пор, пока T1 не зафиксирует из-за блокировки x с помощью T1 после операции чтения r1[x]. Если для транзакции T2 требуется t единиц времени после запуска операции записи w2[x] для достижения состояния готовности, то T2 фиксирует t единиц времени после фиксации T1. Однако SCO не блокирует w2[x], и T2 может зафиксировать сразу после фиксации T1. ( Раз 1991с )

Порядок строгих обязательств (SCO; ( Raz 1991c )) представляет собой пересечение строгости (особого случая восстанавливаемости) и CO и обеспечивает верхнюю границу параллелизма расписания, когда оба свойства существуют. Его можно реализовать с помощью механизмов блокировки (блокировки), аналогичных тем, которые используются для популярного SS2PL, с аналогичными накладными расходами.

В отличие от SS2PL, SCO не блокирует конфликт чтения-записи, но, возможно, вместо этого блокирует фиксацию. SCO и SS2PL имеют идентичное поведение блокировки для двух других типов конфликтов: запись-чтение и запись-запись. В результате SCO имеет более короткие средние периоды блокировки и больший параллелизм (например, моделирование производительности одной базы данных для наиболее значимого варианта блокировок с упорядоченным разделением , который идентичен SCO, ясно это показывает, с примерно 100% выигрышем для некоторые транзакционные нагрузки также для идентичных транзакционных нагрузок SCO могут достигать более высоких скоростей транзакций, чем SS2PL, прежде чем блокировка произойдет ). Увеличение параллелизма означает, что при данных вычислительных ресурсах за единицу времени выполняется больше транзакций (более высокая скорость транзакций, пропускная способность ), а средняя продолжительность транзакции короче (более быстрое завершение; см. диаграмму). Преимущество SCO особенно важно во время конфликта блокировок.

• ШОС против. Теорема о производительности SS2PL

SCO обеспечивает более короткое среднее время завершения транзакции, чем SS2PL, если существуют конфликты чтения и записи. В остальном SCO и SS2PL идентичны (имеют идентичное поведение блокировки при конфликтах записи-чтения и записи-записи).

SCO так же практичен, как и SS2PL, поскольку, как и SS2PL, он обеспечивает помимо сериализуемости еще и строгость, которая широко используется в качестве основы для эффективного восстановления баз данных после сбоя. Механизм SS2PL можно преобразовать в механизм SCO для повышения производительности простым способом без изменения методов восстановления. Описание реализации ШОС можно найти в (Перризо и Татаринов, 1998). См. также Полуоптимичный планировщик базы данных .

SS2PL — это правильное подмножество SCO (что является еще одним объяснением того, почему SCO менее ограничивает и обеспечивает больший параллелизм, чем SS2PL).

Оптимистичный СО (ОСО)

Для реализации оптимистического порядка фиксации (OCO) используется общий локальный алгоритм CO без блокировки доступа к данным и, следовательно, без локальных взаимоблокировок. OCO без ограничений планирования транзакций или операций охватывает весь класс CO и не является частным случаем класса CO, а скорее полезным вариантом CO и характеристикой механизма.

Расширенный CO (ECO)

Общая характеристика ЭКО

Порядок расширенных обязательств (ECO; ( Raz 1993a )) обобщает CO. Когда локальные транзакции (транзакции, ограниченные одной базой данных) можно отличить от глобальных (распределенных) транзакций (транзакций, которые охватывают две или более базы данных), порядок обязательств применяется к глобальным. только транзакции. Таким образом, чтобы локальное (для базы данных) расписание имело свойство ECO, хронологический (частичный) порядок событий фиксации только глобальных транзакций (неважен для локальных транзакций) соответствует их порядку на соответствующем графе локальных конфликтов.

• Определение: заказ с расширенными обязательствами

Позволять $T_{1},T_{2}$ быть двумя зафиксированными глобальными транзакциями в расписании, так что ) существует направленный путь непрерванных транзакций в графе конфликтов ( графе приоритетов из $T_{1}$ к $T_{2}$ ( $T_{1}$ предшествует $T_{2}$возможно, транзитивно , косвенно). График имеет свойство «Заказ с расширенным обязательством» (ECO), если для каждых двух таких транзакций $T_{1}$ фиксирует раньше $T_{2}$ совершает.

Существует распределенный алгоритм, гарантирующий глобальную ЭКО. Что касается CO, алгоритму нужны только (немодифицированные) сообщения протокола атомарной фиксации. Чтобы гарантировать глобальную сериализуемость, каждая база данных должна также гарантировать сериализуемость конфликтов своих собственных транзакций с помощью любого (локального) механизма управления параллелизмом.

• ECO и теорема глобальной сериализуемости

1. (Локальный, что подразумевает глобальный) ECO вместе с сериализуемостью локальных конфликтов является достаточным условием, чтобы гарантировать сериализуемость глобального конфликта.
2. Когда никакая информация управления параллелизмом, кроме сообщений об атомарных обязательствах, не передается за пределы базы данных (автономия) и могут быть идентифицированы локальные транзакции, это также является необходимым условием.

См. доказательство необходимости в ( Raz 1993a ).

Это условие (ECO с локальной сериализуемостью) слабее, чем CO, и обеспечивает больший параллелизм за счет немного более сложного локального алгоритма (однако практической разницы в накладных расходах с CO не существует).

Когда предполагается, что все транзакции являются глобальными (например, если нет информации о локальных транзакциях), ECO сводится к CO.

Алгоритм ЭКО

Прежде чем глобальная транзакция будет зафиксирована, общий локальный (по отношению к базе данных) алгоритм ECO прерывает минимальный набор нерешенных транзакций (ни зафиксированных, ни прерванных; либо локальных транзакций, либо глобальных, которые выполняются локально), что может впоследствии вызвать цикл в граф конфликта. Этот набор прерванных транзакций (не уникальный, в отличие от CO) можно оптимизировать, если каждой транзакции присвоен вес (который может определяться важностью транзакции и вычислительными ресурсами, уже вложенными в выполняющуюся транзакцию; оптимизация может быть выполнена). например, путем сокращения задачи о максимальном потоке в сетях ( Raz 1993a )). Как и в случае с CO, такое множество зависит от времени и со временем становится пустым. Практически, почти во всех необходимых реализациях транзакция должна фиксироваться только тогда, когда набор пуст (и оптимизация набора не применима). Локальный (по отношению к базе данных) механизм управления параллелизмом (отдельный от алгоритма ECO) обеспечивает исключение локальных циклов (в отличие от CO, который сам по себе подразумевает сериализуемость; однако практически также и для CO используется механизм локального параллелизма, по крайней мере, для обеспечить возможность восстановления). Локальные транзакции всегда могут фиксироваться одновременно (даже если существует отношение приоритета, в отличие от CO). Когда позволяет локальный частичный порядок общих транзакций (который определяется графом локальных конфликтов, теперь только с возможными временными локальными циклами, поскольку циклы устраняются механизмом локальной сериализуемости), также можно проголосовать за одновременное выполнение глобальных транзакций ( когда все их транзитивно (косвенно) предшествующие (через конфликт) глобальные транзакции фиксируются, тогда как транзитивно предшествующие локальные транзакции могут находиться в любом состоянии. Это аналогично более строгому условию одновременного голосования в распределенном алгоритме CO, при котором все транзитивно предшествующие транзакции должны быть зафиксированы).

Условие гарантии Global ECO можно резюмировать аналогично CO:

• Теорема о глобальной стратегии очередности голосов ОЭС

Позволять $T_{1},T_{2}$ быть нерешенными (ни зафиксированными, ни прерванными) глобальными транзакциями в системе базы данных, которая обеспечивает сериализуемость локально, так что существует направленный путь непрерванных транзакций из в локальном графе конфликтов (в графе самой базы данных) $T_{1}$ к $T_{2}$. Затем, имея $T_{1}$ закончилось (либо совершено, либо прервано) до $T_{2}$ голосование за принятие в каждой такой системе баз данных в среде с несколькими базами данных является необходимым и достаточным условием для гарантии Global ECO (условие гарантирует Global ECO, которое может быть нарушено без него).

Глобальное ECO (все глобальные циклы в графе глобальных конфликтов устраняются атомарным обязательством) вместе с локальной сериализуемостью (т. е. каждая система базы данных поддерживает сериализуемость локально; все локальные циклы исключаются) подразумевают глобальную сериализуемость (все циклы исключаются). Это означает, что если каждая система баз данных в среде с несколькими базами данных обеспечивает локальную сериализуемость (с помощью любого механизма) и применяет стратегию упорядочивания голосов, указанную в приведенной выше теореме (обобщение стратегии упорядочивания голосов CO), то глобальная сериализуемость гарантирована (локальный CO не требуется). больше).

Как и в случае с CO, ситуацию с тупиком в голосовании ОЭС можно резюмировать следующим образом:

• Теорема ОЭС о тупике голосования

Пусть среда с несколькими базами данных включает в себя системы баз данных, каждая из которых обеспечивает как Global ECO (используя условие в приведенной выше теореме), так и сериализуемость локальных конфликтов (которая устраняет локальные циклы в графе глобальных конфликтов). Тогда тупик голосования возникает тогда и только тогда, когда глобальный цикл (охватывает две или более базы данных) существует в графе глобальных расширенных конфликтов (также блокировка блокировкой доступа к данным представлена ​​ребром). Если цикл не прерывается каким-либо прерыванием, то все глобальные транзакции в нем участвуют в соответствующем тупике голосования, и в конечном итоге голос каждого блокируется (прямо или косвенно блокировкой доступа к данным). Если локальная транзакция находится в цикле, она может находиться в любом непрерванном состоянии (выполняется, готова или зафиксирована; в отличие от CO, блокировка локальной фиксации не требуется).

Как и в случае с CO, это означает, что глобальные взаимоблокировки из-за блокировки доступа к данным (с хотя бы одной блокировкой блокировки) являются взаимоблокировками голосования и автоматически разрешаются посредством атомарной фиксации.

Многоверсионный CO (MVCO)

Multi-version Commitment Order (MVCO; ( Raz 1993b )) — это обобщение CO для баз данных с многоверсионными ресурсами . С такими ресурсами транзакции только для чтения не блокируются или блокируются для повышения производительности. Использование таких ресурсов в настоящее время является распространенным способом повышения параллелизма и производительности за счет создания новой версии объекта базы данных каждый раз, когда объект записывается, и разрешения транзакциям операций чтения нескольких последних соответствующих версий (каждого объекта). MVCO подразумевает сериализуемость одной копии (1SER или 1SR), которая является обобщением сериализуемости для многоверсионных ресурсов. Как и CO, MVCO не является блокирующим и может быть объединен с любым подходящим механизмом управления многоверсионным параллелизмом, не мешая ему. В представленной базовой теории конфликтов MVCO обобщаются для разных версий одного и того же ресурса (в отличие от более ранних теорий нескольких версий). Для разных версий хронологический порядок конфликтов заменяется порядком версий и, возможно, меняется на обратный, сохраняя при этом обычные определения конфликтующих операций. Результаты для обычных и расширенных графов конфликтов остаются неизменными, и, как и в случае с CO, существует распределенный алгоритм применения MVCO, теперь для смешанной среды как с одноверсионными, так и с многоверсионными ресурсами (теперь одна версия является особым случаем многоверсионности). ). Что касается CO, то алгоритму MVCO нужны только (немодифицированные) сообщения протокола атомарной фиксации без каких-либо дополнительных затрат на связь. Глобальные взаимоблокировки на основе блокировки преобразуются в взаимоблокировки голосования и разрешаются автоматически. По аналогии с CO справедливо следующее:

• MVCO и глобальная теорема о сериализуемости с одной копией

1. Соответствие MVCO каждой автономной системы баз данных (или транзакционного объекта) в смешанной среде с несколькими базами данных, состоящей из одноверсионных и многоверсионных баз данных, является необходимым условием для гарантии глобальной сериализуемости одной копии (1SER).
2. Соответствие MVCO каждой системы баз данных является достаточным условием для гарантии Global 1SER.
3. Глобальные взаимоблокировки на основе блокировок разрешаются автоматически.

Комментарий : Теперь одноверсионная система баз данных, совместимая с CO, автоматически также совместима с MVCO.

MVCO можно дополнительно обобщить, используя обобщение ECO (MVECO).

Пример: изоляция моментальных снимков на основе CO (COSI)

Изоляция моментальных снимков на основе CO (COSI) — это пересечение изоляции моментальных снимков (SI) с MVCO. SI — это метод управления многоверсионным параллелизмом, широко используемый благодаря хорошей производительности и сходству с сериализуемостью (1SER) в нескольких аспектах. Теория (Raz 1993b) для MVCO, описанная выше, используется позже в (Fekete et al. 2005) и других статьях по SI, например (Cahill et al. 2008); см. также Создание сериализуемой изоляции моментальных снимков и ссылки там), для анализа конфликтов в SI, чтобы сделать его сериализуемым. Метод, представленный в (Cahill et al. 2008), Изоляция моментальных снимков Serializable (SerializableSI), модификация SI с низкими накладными расходами, обеспечивает хорошие результаты производительности по сравнению с SI, с лишь небольшими потерями для обеспечения сериализуемости. Другой метод, сочетающий SI с MVCO (COSI), также делает SI сериализуемым с относительно низкими накладными расходами, аналогично комбинированию общего алгоритма CO с механизмами одной версии. Более того, полученная комбинация COSI, совместимая с MVCO, позволяет совместимым с COSI системам баз данных взаимодействовать и прозрачно участвовать в решении CO для распределенной/глобальной сериализуемости (см. ниже). Помимо накладных расходов, необходимо количественно сравнивать поведение протоколов. С одной стороны, все сериализуемые расписания SI могут быть преобразованы в MVCO с помощью COSI (путем возможных задержек фиксации, когда это необходимо) без прерывания транзакций. С другой стороны, известно, что SerializableSI без необходимости прерывает и перезапускает определенный процент транзакций даже в сериализуемых расписаниях SI.

CO и его варианты прозрачно совместимы для глобальной сериализации.

При использовании CO и его вариантов (например, SS2PL, SCO, OCO, ECO и MVCO, описанных выше) глобальная сериализуемость достигается с помощью распределенных алгоритмов на основе протокола атомарной фиксации . Для CO и всех его вариантов протокол атомарного принятия является инструментом устранения глобальных циклов (циклов, охватывающих две или более базы данных) в глобальном расширенном (и, следовательно, регулярном) графе конфликтов (неявно; реализация глобальной структуры данных не требуется). В случаях либо несовместимости локальных заказов на принятие обязательств в двух или более базах данных (когда ни один глобальный частичный заказ не может объединить соответствующие локальные частичные заказы вместе), либо тупика голосования, связанного с блокировкой доступа к данным, оба из которых подразумевают глобальный цикл в глобальном расширенном графе конфликтов. и недостающих голосов, протокол атомарной фиксации разрывает такой цикл, прерывая нерешенную транзакцию (см. Алгоритм распределенного CO выше). Различия между различными вариантами существуют только на местном уровне (внутри участвующих систем баз данных). Каждый локальный экземпляр CO любого варианта выполняет одну и ту же роль: определять положение каждой глобальной транзакции (транзакции, охватывающей две или более базы данных) в локальном заказе фиксации, т. е. определять, когда наступит очередь голосования по транзакции. локально в протоколе атомных обязательств. Таким образом, все варианты CO демонстрируют одинаковое поведение в отношении атомного связывания. Это означает, что все они совместимы посредством атомарной фиксации (с использованием одних и тех же программных интерфейсов, обычно предоставляемых как сервисы , некоторые из которых уже стандартизированы для атомарной фиксации, в первую очередь для протокола двухфазной фиксации , например, X/Open XA ) и прозрачно могут использоваться вместе в любой распределенной среде (в то время как каждый экземпляр варианта CO может быть связан с любым соответствующим локальным механизмом управления параллелизмом). тип).

Таким образом, любая отдельная глобальная транзакция может одновременно участвовать в базах данных, которые могут использовать любой, возможно, другой вариант CO (при одновременном запуске процессов в каждой такой базе данных и одновременном выполнении локальных и других глобальных транзакций в каждой такой базе данных). Протокол атомарного обязательства безразличен к CO и не делает различий между различными вариантами CO. Любой глобальный цикл , сгенерированный в расширенном глобальном графе конфликтов, может охватывать базы данных различных вариантов CO и генерировать (если не прерывается каким-либо локальным прерыванием) тупик голосования, который разрешается атомарным обязательством точно так же, как и в среде с одним вариантом CO. локальные циклы (теперь возможно со смешанными материализованными и нематериализованными конфликтами, связанными как с сериализуемостью, так и с блокировкой доступа к данным, например, SCO) разрешаются локально (каждый с помощью собственных локальных механизмов соответствующего экземпляра варианта).

Порядок голосования (VO или Generalized CO (GCO); Raz 2009 ), объединение CO и всех его вышеперечисленных вариантов, является полезной концепцией и методом глобальной сериализации. локальная сериализуемость (в ее наиболее общей форме, основанная на коммутативности и включая многоверсионность) и стратегия порядка голосования Для соответствия ВО необходимы (голосование по локальному порядку приоритета).

Объединив результаты для CO и его вариантов, можно сделать следующий вывод:

• Теорема о совместимости вариантов CO

1. В среде с несколькими базами данных, где каждая система базы данных (транзакционный объект) совместима с некоторым свойством варианта CO (совместима с VO), любая глобальная транзакция может одновременно участвовать в базах данных, возможно, разных вариантов CO, и гарантируется глобальная сериализуемость ( достаточное условие для Глобальная сериализуемость и глобальная сериализуемость одной копии (1SER) для случая, когда существует многоверсионная база данных).
2. Если в каждой системе базы данных используется только локальная (для системы базы данных) информация управления параллелизмом (каждая из них имеет свойство обобщенной автономии , обобщение автономии ), то соответствие каждой из них некоторому (любому) свойству варианта CO (соответствие VO) является необходимое условие для гарантии глобальной сериализуемости (и Global 1SER; в противном случае они могут быть нарушены).
3. Более того, в такой среде глобальные тупики, связанные с блокировкой доступа к данным, разрешаются автоматически (каждый такой тупик генерируется глобальным циклом в расширенном графе конфликтов (т. е. тупик голосования ; см. выше), включая по крайней мере одну блокировку доступа к данным (нематериализованный конфликт) и две системы баз данных, таким образом, не возникает цикла в обычном графе конфликтов и не влияет на сериализуемость).

Ссылки

• Раз, Йоав (август 1992 г.), «Принцип упорядочивания обязательств или гарантия сериализуемости в гетерогенной среде нескольких автономных менеджеров ресурсов, использующих атомарные обязательства» (PDF) , Материалы восемнадцатой международной конференции по очень большим базам данных , Ванкувер, Канада , стр. 292–312 (также DEC-TR 841, Digital Equipment Corporation , ноябрь 1990 г.)
• Раз, Йоав (сентябрь 1994 г.), «Сериализуемость посредством заказа с обязательствами», Information Processing Letters , 51 (5): 257–264, doi : 10.1016/0020-0190(94)90005-1
• Раз, Йоав (июнь 2009 г.), Теория упорядочения обязательств: Краткое изложение , получено 11 ноября 2011 г.
• Раз, Йоав (ноябрь 1990 г.), О значении обязательного заказа (PDF) , Digital Equipment Corporation
• Yoav Raz (1991a): US patents 5,504,899 (ECO) 5,504,900 (CO) 5,701,480 (MVCO)
• Йоав Раз (1991b): «Координатор заказов на обязательства (COCO) менеджера ресурсов, или архитектура для управления параллелизмом на основе упорядочения распределенных обязательств», DEC-TR 843, Digital Equipment Corporation, декабрь 1991 г.
• Йоав Раз (1991c): «Упорядочение строгих обязательств на основе блокировки или как улучшить параллелизм в менеджерах ресурсов на основе блокировки», DEC-TR 844, декабрь 1991 г.
• Йоав Раз (1993a): «Расширенное упорядочение с обязательствами или гарантия глобальной сериализуемости путем применения избирательности заказов с обязательствами к глобальным транзакциям». Материалы двенадцатого симпозиума ACM по принципам систем баз данных (PODS), Вашингтон, округ Колумбия, стр. 83–96, май 1993 г. (также DEC-TR 842, ноябрь 1991 г.)
• Йоав Раз (1993b): «Управление распределенным параллелизмом на основе упорядочивания обязательств для соединения одно- и многоверсионных ресурсов». Материалы Третьего международного семинара IEEE по проблемам исследования инженерии данных: совместимость в системах с несколькими базами данных (RIDE-IMS), Вена, Австрия, стр. 189–198, апрель 1993 г. (также DEC-TR 853, июль 1992 г.)

Внешние ссылки

• Yoav Raz's Commitment ordering page