7.5. Synchronization in System R

From the very beginning System R was conceived as a multi-user system providing multi-access mode to databases. Therefore, very much attention has always been paid to the issues of access synchronization. The System R developers have formulated and partially solved many synchronization problems, the corresponding publications have long become classics, and they are referred to in almost all works related to synchronization in database management systems. We will try to provide a historical retrospective of synchronization solutions in System R. We note first that synchronization issues are in close connection with issues of change logging and restoration of the state of the database.

We begin by looking at the goals that System R developers were guided in developing their approach to synchronization. The fact is that the initial goal of synchronization of operations was not to ensure user isolation, but to support the means of ensuring the logical integrity of the databases. As we noted in the introduction, the logical integrity of the System R databases is maintained based on the presence of integrity constraints previously formulated and stored in database directories. At the end of each transaction, or when an explicit SQL statement is executed, the integrity constraints are not modified by the changes made in the transaction. If a violation of integrity constraints is detected, then a transaction that violates the constraints is rolled back using the RSS RESTORE operation.

In order to be able to correctly perform such a rollback, it is necessary that until the end of the transaction, database objects that have been modified by a transaction cannot be changed by other transactions. Otherwise, there is the so-called problem of lost changes. Indeed, let transaction 1 change some database object A. Then another transaction 2 also changes object A, after which transaction 1 is rolled back (due to, for example, a violation of integrity constraints). Then when you next read object A, transaction 2 will see its state different from the one it went to as a result of its change by transaction 2.

The initial postulate of System R was that the lost changes should not be allowed, and ensuring this was the minimum requirement for the synchronization system. The corresponding transaction execution mode is referred to in System R as the first transaction compatibility level. This is the lowest level of synchronization, causing minimal overhead in the system. Technically, synchronization at the first compatibility level implies long-term (until the end of the transaction) synchronization captures of variable database objects and the absence of any captures for readable objects.

From the point of view of ensuring the logical integrity of databases, the first level of compatibility is quite satisfactory, but it causes some problems within transactions. The main problem is the ability to read dirty data. Indeed, the reading transaction is absolutely not synchronized with the changing transactions, and therefore it can be read some intermediate from a logical point of view the state of the object (we emphasize that a dirty object can only be at the logical level; physical consistency in the database supports another the “physical” level of RSS sync, which we will focus on later). The next, second level of transactional compatibility is System R to ensure that no dirty data is available. Technically, synchronization at the second compatibility level implies long-term synchronization captures (until the end of the transaction) of the objects being modified and short-term (for the duration of the operation) captures of the objects being read.

The second level of compatibility of transactions System R ensures the absence of dirty data, but not free from another problem - non-repeatable reads. If a transaction reads one and the same database object twice (in a row or with a certain time interval), then the state of this object may be different for different readings, since it is between them (and it can occur even if the reads go into a transaction in a row ) another transaction may modify the object. This problem is solved by the third level of compatibility of transactions System R, which is the level of maximum user isolation, which we talked about earlier. Technically, synchronization at the third compatibility level implies long-term (until the end of the transaction) synchronization captures of all objects read and modified in this transaction.

The initial versions of System R provided all of the listed levels of transaction compatibility. Accordingly, there were parameters for the RSS operation BEGIN TRANSACTION, which determined the compatibility level of this transaction. However, already the first experience of using System R has shown that the third compatibility level is the most applicable. At the same time, there were applications that were organized by the first level (mainly, applications related to statistical processing, in which the errors of the dirty data were corrected due to the large number of readings). The second compatibility level turned out to be practically inapplicable. As a result, in recent versions, the developers have left only the third compatibility level, and we will keep in mind only that.

Since the RSS interface is a tuple-based one, it is logical to synchronize in RSS at the level of tuples, or rather, their unique identifiers — tids. Note, however, that if two or more transactions read one tuple, then from a synchronization point of view, this is perfectly acceptable, and if at least one transaction changes a tuple, then it should block all other transactions that perform reading operations or changes to this tuple. This implies the need for two different modes of tuple captures — the joint mode (for reading) and the exclusive mode (for changes). Following the terminology of System R, below we will call these modes S mode (joint) and X mode (exclusive). The rules of compatibility of captures of one object in modes S and X are naturally formulated: capture mode S is compatible with capture mode S and incompatible with capture mode X; Capture Mode X is incompatible with Capture Any Mode.

Accordingly, when reading a tuple, the RSS first sets the capture of this tuple in S mode; when inserting, deleting, or modifying a tuple — in X mode. If, at this point, the tuple is captured on behalf of another transaction in a mode incompatible with the required one, the transaction that applied to RSS is blocked, and the capture requirement of the tuple is queued until conditions will be met to satisfy the required grip, i.e. conflicting captures from a tuple will not be removed.

In principle, the mode of tandem captures sufficient to meet the requirements previously formulated in this subsection. It should be noted that most of the relational database systems are limited to flip-flop (or even more coarse page-by-page) captures. However, in the context of System R, this type of synchronization is insufficient.

The main problem is the possibility of phantom tuples appearing during repeated scans of relations in one transaction (even at the third compatibility level). Indeed, after the first scan, all the tuples read will be captured in S mode, because of which no other transaction can remove or modify such tuples. But nothing prevents you from inserting a new tuple into a different transaction in a different transaction, the field values ​​of which satisfy the scanning conditions of the first transaction. Then, when re-scanning the same relationship with the same scanning conditions, a tuple that was not in the first scan will be read, i.e. a phantom tuple will appear.

An approach was proposed to solve the problem of phantoms based on the so-called predicate captures. The idea of ​​the approach is that when scanning, one should not actually capture individual read tuples, but the entire virtual set of tuples that could be read with this scan. To do this, it is enough to “capture” the condition (predicate), which all tuples must satisfy for a given scan. For example, if tuples of a relation with a value of a> 5 are to be read, then predicate a> 5 is captured. If some other transaction performs an operation, for example, inserting a tuple with a value of a> 5 into the same relation, then the predicate hook preceding the real one performance of this operation, should conflict with the capture of the first transaction, etc.

Naturally, the more accurately the predicate is formulated, the greater is the real parallelism in the execution of transactions in the system with predicate hooks. From this point of view, the highest level of asynchrony could be achieved if one assumes using the conditions of sampling, deletion or modification of the SQL language (or another high-level query language) as synchronization predicates. But on the other hand, the more general the form of predicates allowed, the more difficult it becomes to detect the compatibility of the corresponding hooks. It is quite easy to implement a system of predicate hooks, in which predicates are logical expressions consisting of simple predicates of comparison of relationship fields with constant values. The System R developers didn’t go for such a system, but some ideas of predicate hooks were used.

In the presence of only tandem captures, it is unclear the issue of synchronization in the RSS of tandem operations and operations of creating and destroying relations and indexes, and adding fields to the existing relationship. It is not clear how to combine the sorting-up grippers with the possibility of explicitly grabbing a relationship, etc. Obviously, the general system of predicate hooks removes such problems, but as we have already noted, System R developers did not go for its implementation. Instead, a hierarchical granular capture protocol was developed (with some elements of predicate hooks).

The basic idea is that there is some hierarchy of storage memory for tuples: segment-relation-tuple. Objects at each level of the hierarchy can be captured. In addition, you can capture a specified range of values ​​of any index. The set of possible capture modes is extended by so-called targeted (intented) captures. Semantically, the target capture of a “complex” object (segment or relationship) means the intention of this transaction to set target or regular captures at a lower level of the hierarchy. The following types of target captures are introduced: IX (intented to X), IS (intented to S) and SIX (shared, intented to X).

Capturing an object in mode IX corresponds to the intention of a transaction to capture objects down the hierarchy in modes IX or X. Capturing an object in IS mode corresponds to the intention of a transaction to capture objects down the hierarchy in modes IS or S. Finally, capturing an object in SIX mode corresponds to capturing an object in mode S and the intention of the transaction to capture objects down the hierarchy in mode X. From this follow the following compatibility rules for capturing different modes:

The synchronization protocol using the above capture modes is as follows: to capture an object (for example, a relation tuple) in mode S (X), you must first set captures in IS (IX) mode of the corresponding objects up the hierarchy (in the case of a tuple capture — segment and relationship) ; at the same time, captures must be established, starting from the root of the hierarchy (in our case, first for the segment, then for the relationship, and only then for the tuple).

It is obvious that the protocol of hierarchical captures solves the problem of the compatibility of global captures of a complex object (for example, relationship captures in mode S) with the captures of subobjects of this object (tuples). But it is also obvious that the protocol, generally speaking, does not solve the problem of phantoms. If a relation is scanned without using an index, then the absence of phantoms can be guaranteed if the entire relation is pre-captured in mode S. Then, in accordance with the hierarchical protocol, no other transaction can bring a new tuple into this relation, because it will be blocked when attempting to capture relationship in mode IX (captures relations in modes S and IX are incompatible). You can, of course, capture the entire relationship when scanning using the index. In this way, the problem of phantoms can be solved, but this is a very inefficient solution, because it sharply limits the possibilities for parallel execution of transactions. Any transaction that reads a relationship conflicts with any transaction that changes this relationship. On the other hand, in RSS, when scanning an index relationship, there is additional information (scanning range), which limits many tuples, among which phantoms should not occur.

Based on these considerations, it was proposed to introduce elements of predicate hooks into the synchronization system. Note first that technically seizures of segments, relations, and tuples are interpreted uniformly, as seizures of tids. When a tuple is captured, its tid is actually captured. When a segment or relationship is captured, the tid of the descriptor of the corresponding object in the internal relations of the descriptors of such objects (segments and relations) is actually captured. It was proposed to expand the synchronization system, allowing the use of captures to a pair of index identifiers - the interval of key values ​​of the index. It is allowed to apply captures to such a pair in any of the allowed modes, and the two captures are compatible if and only if they are compatible according to the table above, or the specified ranges of key values ​​do not overlap.

With this possibility, if the ratio scan is opened by index, the ratio is captured in IS mode, and in this mode a pair of index identifier is captured - scan range. When a tuple is inserted (deleted), the relation is captured in IX mode, and in this mode, for each index defined on this relation, a pair of index identifier is captured - the key value from the tuple affected by the operation. Then the reading transactions really conflict only with those changing transactions that affect the scan range. In this case, the problem of phantoms is solved, and the asynchrony of transactions is limited to "essentially", i.e. only when their parallel execution creates problems.

We note immediately that the described solution of synchronization problems is far from ideal. First, still when scanning a relationship without using indexes, the absence of phantoms can be guaranteed only with full capture of the entire relationship in mode S. Secondly, even when scanning by index, the condition of a real tuple sample can often be stricter than simply specifying the scan range, and This means that the required grip is too strong, i.e. encompasses a wider array of tuples than the one that will be the actual scan result.

Apparently, for these reasons, as well as for the reasons for the required complexity of the synchronization system, the described means of dealing with phantoms were not implemented in System R (at least this follows from the final publications). Moreover, due to the halfness of this solution and too much restriction of the degree of asynchrony, the developers refused to take the implicit relationship grips in mode S when scanning without using indexes. (Recall that the possibility of explicitly capturing the entire relationship remained). Thus, System R does not guarantee the absence of phantoms when re-scanning the relationship.

System R's experience in synchronization has had a very large impact on relational database developers worldwide. This is especially true of proposals for predicate seizures. In a number of existing or designed DBMS, predicate hooks form the basis of the synchronization system, which, of course, becomes significantly more complex than in System R.

To conclude this subsection, we briefly mention one more level of synchronization present in RSS, the level of physical synchronization. We have already noted that after performing any operation, RSS leaves the database in a physically consistent form. This means, in particular, the correctness of all interstitial links. Examples of such links may be links between the pages of B-tree indexes, etc. While performing change operations (adding, modifying, or deleting a tuple), temporary status of the data pages may occur. In order for each operation at the beginning of its execution to have correct information, additional short-term synchronization at the page level is necessary. At the time of the operation, all necessary pages are captured in read or change mode. The captures are removed at the end of the operation.

And the last remark. При синхронизации транзакций могут возникнуть тупиковые ситуации, когда две или более транзакции не могут продолжать свое выполнение по причине взаимных блокировок. RSS не предпринимает каких-либо действий по предотвращению тупиков. Вместо этого периодически проверяется состояние системы захватов на предмет обнаружения тупика, и если тупик обнаруживается, выбираются одна или несколько транзакций - жертв, для которых инициируется откат к началу или к ближайшей точке сохранения транзакции, гарантирующий разрушение тупика (при откате транзакции ее синхрозахваты снимаются). Выбор жертвы производится в соответствии с критериями минимальной стоимости проделанной транзакцией работы, которую придется повторить после отката. Мы не будем более подробно рассматривать схемы обнаружения и разрушения тупиков. Заметим лишь, что при обнаружении тупика применяется широко распространенная техника редукции графа ожидания с целью обнаружения в нем циклов, наличие которых и свидетельствует о наличии тупика.