11.1. Synchronization captures

The most common in centralized DBMS (including systems based on the client-server architecture) is an approach based on the observance of a two-phase synchronization capture protocol of database objects. In general terms, the protocol is that, before performing any operation in transaction T, a synchronization capture of an object r is requested on behalf of transaction T on the database object r in the appropriate mode (depending on the type of operation).

The main modes of synchronization captures are:

• joint mode - S (Shared), meaning a shared object capture and required to perform an object read operation;
• exclusive mode - X (eXclusive), meaning exclusive seizure of an object and required to perform entry, deletion and modification operations.

Object captures are readable in several read transactions; several transactions are allowed to read the same object, object capture by one read transaction is incompatible with another transaction capture by the same object by record, and captures of the same object by different write transactions are not compatible. Compatibility rules for capturing one object by different transactions are depicted in the following table:

The first column shows the possible states of the object in terms of synchronization captures. At the same time, "-" corresponds to the state of the object for which no capture is set. A transaction that has requested a synchronization capture of a database object already captured by another transaction in incompatible mode is blocked until the capture from this object is removed.

Note that the word "no" in our table corresponds to the previously described possible cases of conflict of transactions on access to database objects (WW, RW, WR). The compatibility of S-captures corresponds to the fact that the RR conflict does not exist.

To ensure transaction serialization (the third isolation level), synchronization captures of objects, initiated by a transaction, can be removed only at the end of the transaction. This requirement generates a two-phase synchronization capture protocol - 2PL. In accordance with this protocol, the execution of a transaction is divided into two phases:

• The first phase of the transaction is the accumulation of captures;
• the second phase (fixation or rollback) - release of captures.

It is easy enough to make sure that while observing the two-phase synchronization capture protocol, transactionalization at the third isolation level is indeed provided. The main problem is what should be considered an object for synchronization capture?

In the context of relational databases, the following alternatives are possible:

• a file is a physical (from a database point of view) object, a storage area for several relations and, possibly, indexes;
• relation - a logical object corresponding to the set of tuples of a given relation;
• data page - a physical object that stores tuples of one or more relations, index or service information;
• a tuple is an elementary physical database object.

In fact, when we talk about operations on database objects, any operation on a tuple is, in fact, an operation on the page in which this tuple is stored, and on the corresponding relation, and on the file containing the relation. Therefore, there really is a choice of the level of the capture object.

It is clear that the larger the synchronization capture object (no matter what nature this object is logical or physical), the less synchronization captures will be maintained in the system, and, accordingly, less overhead will be spent on this. Moreover, if you select a file or attitude as the level of objects for captures, then even the problem of phantoms will be solved (if it is not immediately clear, look again at the phantoms problem definition and definition of a two-phase capture protocol).

But the trouble is that when using large objects for capturing, the likelihood of transaction conflicts increases and thus decreases the allowable degree of their parallel execution. In fact, when enlarging the object of synchronization capture, we deliberately roughen the situation and see conflicts in those situations when in reality there are no conflicts.

The developers of many systems began with the use of page captures, believing this to be a compromise between the desire to reduce overhead and maintain a fairly high level of parallelism of transactions. But this is not a good choice. We will not dwell on the details, but note that the use of page captures in a two-phase protocol sometimes causes very unpleasant synchronization problems that complicate the organization of the DBMS. Most modern systems use per-pair synchronization captures.

But this raises another question. If the unit of capture is a tuple, then what synchronization captures will be required when performing such operations as destroying the relationship? It would be rather ridiculous to carry out such an operation to require the capture of all existing tuples of a relation. In addition, this would not prevent the possibility of concurrent insertion of a new tuple into a destroyed relation in another transaction.

11.1.1. Granular Synchronization Hooks

Similar reasoning led to the development of a granular synchronization capture apparatus. Using this approach, synchronization captures can be queried with respect to objects of different levels: files, relations, and tuples. The required object level is determined by what operation is being performed (for example, to perform a relationship destruction operation, the entire relationship must be the object of synchronization capture, and this tuple should be used to perform a tuple deletion operation). An object of any level can be captured in S or X mode.

Now the most important difference, which, in fact, keeps the correspondence of the grips of different levels. A special protocol of granular captures and new types of captures are introduced: before capturing an object in mode S or X, the corresponding object at a higher level must be captured in mode IS, IX or SIX. What are these modes of captures?

IS (Intented for Shared lock) with respect to some composite object O means the intention to capture some object entering O in a shared mode. For example, if you intend to read tuples from an R relationship, this relationship must be captured in IS mode (and before that, the file must be captured in the same mode).

IX (Intented for eXclusive lock) with respect to some composite object O means the intention to capture some object entering O in exclusive mode. For example, if you intend to delete tuples from an R relationship, this relationship should be captured in mode IX (and before that, the file should be captured in the same mode).

SIX (Shared, Intented for eXclusive lock) in relation to some composite object O means joint seizure of this whole object with the intention to subsequently capture any objects entering into it in exclusive mode. For example, if a long operation of viewing a relationship is performed with the possibility of deleting some of the tuples that are viewed, it is most economical to capture this relationship in SIX mode (and before that, to capture the file in IS mode).

It is rather difficult to describe in words all possible situations. We confine ourselves to providing a complete table of compatibility of captures, analyzing which it is possible to identify all cases:

11.1.2. Predicative Synchronization Captures

Despite the attractiveness of the method of granular synchronization captures, it should be noted that it does not solve the problem of phantoms (unless, of course, you limit yourself to using relationship captures in modes S and X). It has long been known that in order to solve this problem, it is necessary to move from capturing individual database objects to capturing the conditions (predicates) that these objects satisfy. The problem of phantoms does not arise when using the level of relations for synchronization precisely because a relation as a logical object is an implicit condition for its tuples. Relationship capture is a simple and special case of predicate capture.

Since any operation on a relational database is defined by some condition (that is, it does not indicate a specific set of database objects over which the operation needs to be performed, but a condition that the objects of this set must satisfy), an ideal choice would be to require synchronization capture in mode S or X is exactly this condition. But if you look at the general view of the conditions allowed, for example, in the SQL language, it becomes absolutely incomprehensible how to determine the compatibility of the two predicate hooks. It is clear that without this, it is impossible to use predicate hooks to synchronize transactions, and the problem in general form is unsolvable.

Fortunately, this problem is relatively easily solved for simple conditions. By a simple condition, we call a conjunction of simple predicates of the form

attribute-name {=> <} value

In typical DBMSs that support two-tier organization (language level and external memory management level), only simple conditions are allowed in the interface of memory management subsystems (which usually manages transaction serialization). The language level subsystem compiles the source statement with a complex condition into a sequence of calls to the database engine, each of which contains only simple conditions. Therefore, in the case of a typical organization of a relational DBMS, simple conditions can be used as the basis of predicate hooks.

For simple conditions, the compatibility of predicate hooks is easily determined based on the following geometric interpretation. Let R be a relation with attributes a ₁ , a ₂ , ..., a _n , and m ₁ , m ₂ , ..., m _n be the sets of admissible values ​​a ₁ , a ₂ , ..., a _n, respectively (all these sets are finite). Then we can associate R with a finite n-dimensional space of possible values ​​of the tuples R. Any simple condition “cuts out” an m-dimensional rectangle in this space (m <= n).

Then SX, XS, XX predicate hooks from different transactions are compatible if the corresponding rectangles do not intersect.

This is illustrated by the following example, which shows that in whatever modes transaction 1 captures conditions (1 <= a <= 4) & (b = 5) and transaction 2 requires conditions (1 <= a <= 5) & ( 1 <= b <= 3), these captures are always compatible.

Example: (n = 2)

Note that predicate hooks of simple conditions are described by tables, which are slightly different from the tables of traditional synchronizers.

11.1.3. Dead ends, recognition and destruction

One of the most sensitive shortcomings of the transaction serialization method based on synchronization captures is the possibility of deadlocks between transactions. Dead ends are possible when applying any of the options considered by us.

Here is a simple example of a deadlock between transactions T1 and T2:

• transactions T1 and T2 set monopoly captures of r1 and r2 objects, respectively;
• after that, T1 requires a joint capture of r2, and T2 requires a joint capture of r1;
• None of the transactions can continue, therefore, exclusive holdings will not be removed, and joint - will not be satisfied.

Since dead ends are possible, and there is no natural way out of the deadlock, these situations need to be detected and artificially eliminated.

The basis for the detection of deadlocks is the construction (or constant maintenance) of the transaction wait graph. A transaction waiting graph is a directed bipartite graph in which there are two types of vertices — the vertices corresponding to the transactions, and the vertices corresponding to the capture objects. In this graph, there is an arc leading from a vertex-transaction to a vertex-object, if there is a satisfied object capture for this transaction. In the graph, there is an arc from the vertex-object to the vertex-transaction if the transaction is waiting to meet the capture object.

It is easy to show that there is a deadlock situation in the system if there is at least one cycle in the transaction waiting column.

To recognize the deadlock, a transaction wait graph is periodically built (as already noted, sometimes the wait graph is maintained constantly), and cycles are searched for in this graph. The traditional technique (for which there are many varieties) finding cycles in a directed graph is the reduction of the graph.

Without going into details, the reduction is that, first of all, all arcs emanating from transaction vertices that do not include arcs from object vertices are deleted from the waiting graph. (This seems to correspond to the situation that transactions that did not await the satisfaction of the captures were successfully completed and the captures were released). For those vertex objects for which there are no incoming arcs left but outgoing ones, the orientation of the outgoing arcs is reversed (this simulates grab satisfaction). After that, the first step is triggered again and so on until the removal of arcs stops at the first step. If there are arcs in the graph, they will necessarily form a cycle.

Suppose we managed to find a cycle in the transaction waiting column. What to do now? It is necessary to somehow ensure the possibility of continuing work at least for a part of transactions that have reached a dead end. The destruction of the impasse begins with the selection in the cycle of transactions of the so-called transaction-victim, i.e. transaction, which decided to donate, to ensure the continuation of other transactions.

Roughly speaking, the criterion of choice is the cost of the transaction; the victim is the cheapest transaction. The cost of a transaction is determined on the basis of a multi-factor estimate, which, with different weights, includes execution time, number of accumulated captures, and priority.

After selecting the victim transaction, the transaction is rolled back, which can be full or partial. In this case, of course, captures are released and the execution of other transactions can be continued.

Naturally, such a violent elimination of deadlock situations is a violation of the principle of user isolation, which cannot be avoided.

Note that in centralized systems, the cost of building an expectation graph is relatively small, but it becomes too large in truly distributed DBMS, in which transactions can be performed in different nodes of the network. Therefore, other transaction serialization methods are commonly used in such systems.

One more note. To minimize the number of conflicts between transactions, in some DBMS (for example, in Oracle) the following development of the approach is used. Monopoly object capture blocks only changing transactions. After the modification operation is completed, the previous version of the object remains available for reading in other transactions. A short-term read lock is required only for the period of committing the modifying transaction when the updated objects become current.