Shulou(Shulou.com)06/01 Report--

Talking about the understanding of the isolation level of Database

When people mention a database management system (DBMS), they always mention transactions, ACID features, and transaction isolation levels. The transaction itself is a concept that ensures that the running state of the system will eventually be consistent (satisfying a set of constraints). The I (Isolation) in the ACID feature is to ensure that the database can be in a "consistent" state in the case of concurrent operations. But asking yourself raises a lot of questions: what exactly is the transaction isolation level? Why is there a transaction isolation level? How is each isolation level defined and what is the role of each isolation level as the basis of the theory? The following is mainly combined with the classic paper [1] and relevant experience to briefly talk about their own understanding.

(a) what exactly is the transaction isolation level? Why is there a transaction isolation level?

The I (Isolation) in the four characteristics of transaction ACID literally means "isolation" and essentially refers to the concurrency control of data operations. So the question, in other words, why concurrency control is needed? What problem does it solve?

In the database, if all transaction operations for the same data item are performed serialized, there is no problem with the execution process and results. If there are concurrent operations, that is, there is an intersection between the life cycles (time intervals) of multiple transactions, operational conflicts and dependencies may occur, leading to anomalies. For the same data item, the execution process of two concurrent operations must be sequential rather than physical at the same time, and the result depends on the contention and scheduling strategy. The operation sequence type can be divided into four types: read-read, read-write, write-read, write-write. The last three operation sequences including writing are conflicting, and they may cause the exception of the execution result, or called Anomaly.

For example, the following commands are executed in the following scheduling order without any concurrency control mechanism, such as locks:

time

Transaction 1

Transaction 2

T0

BEGIN; / / x = 10

BEGIN

T1

W1 [x]: update x = x + 1; / / x = 11

T2

R2 [x]: read x; / / x = 11, dependent on W1 [x]

T3

A1: abort (causing a rollback); / / x = 10

T4

Update y: = x

Table 1.

The execution sequence pattern (phenomenon) formed in this way is W1 [x]. R2 [x]. A1., which accords with the write-read conflict mode, and the above case does produce an exception, that is:

(1) according to the above execution sequence, the data read by transaction 2 is the uncommitted dirty data x = 11 of transaction 1, which is actually inconsistent data that should not be seen by transaction 2. If the data is subsequently applied by transaction 2 to update a record y: = 11, then the state of the database will be inconsistent. (this is known as "dirty reading")

(2) if transaction 1 is executed before transaction 2, then this is the serialized transaction execution mode, and the x value read by transaction 2 should be the value before transaction 1 started (rolled back), that is, x = 10, which is the correct result. The details are as follows:

time

Transaction 1

Transaction 2

T0

BEGIN; / / x = 10

T1

W1 [x]: update x = x + 1; / / x = 11

T2

A1: abort (cause rollback); / / x = 10, end

BEGIN; / / x = 10, serial with transaction 1, no problem

T3

R2 [x]: read x; / / x = 10

T4

Update y: = x

......

Table 2.

In this way, (1), (2) the results of the order-preserving execution sequences corresponding to the two scheduling modes are different, (2) the serialization execution is correct, and (1) the results (because of dirty reading) produce inconsistent data states.

The above exception is only one of many kinds of exceptions, concurrency control is to solve these exceptions, but to what extent does concurrency control need to be achieved? Because the high degree of concurrency control corresponds to the low efficiency of concurrent execution, database users do not need the strongest concurrency control mode all the time, which is the tradeoff between consistency and concurrency, and the isolation level is the control parameter of this tradeoff.

If we set the context of the transaction and transaction isolation level on the database system, we can consider:

From the point of view of database users, anomalies are possible problems in concurrent operations, concurrency control is a process or means to avoid problems caused by some abnormal phenomena, and isolation level is an abstract description of the degree of concurrency control. That is, the database consumer configures the database system by setting the transaction isolation level, so that it can avoid some abnormal phenomena in concurrent operations.

From the point of view of database developers, it is a fundamental requirement to solve the abnormal phenomena in concurrent operations, and the isolation level classifies, abstracts and summarizes these infinite phenomenal requirements, transforming the need to avoid abnormal phenomena into meeting the needs of limited types of isolation levels. That is, database developers only need to implement several defined isolation levels to provide the database system with the ability to avoid some (possibly infinite) anomalies. The definition of isolation levels in a specific DBMS may vary, but the implementation needs to be at least as good as the ANSI-SQL standard.

How to set the isolation level is closely related to the classification and induction of abnormal phenomena / behavior sequences. In order to define the isolation level strictly (mathematically), it is necessary to give a formal (but strict) definition of abnormal phenomena.

Key points of this section:

-> concurrent transactions cause execution results to break some constraints (the source of the problem)

-> cause is attributed to read-write conflict (w-w/w-r/r-w)

-> abnormal phenomena (Anomaly) (incomplete) are reduced to abnormal patterns

The broader behavior sequence (phenomenon-Phenomenon) is summed up as a behavior sequence pattern.

-> banning behavior sequences or exception sequence patterns can avoid some concurrent operation problems

-> it is defined according to the induction of behavior sequence patterns: to solve some problems is to meet a specific isolation level.

(2) how to standardize and formally describe and issue the (abnormal) phenomenon of reading and writing? How to understand them?

In the paper [1], the formal description of abnormal or common phenomena of concurrent operations has been given. That is, the behavior sequence is used to describe a series of operation processes, in which the behavior is simplified and abstracted into two types: read and write, the digital label represents the transaction to which the behavior belongs (transaction N), and the parameters in parentheses represent the operation object. It is shaped like "W1 [x]. R2 [x]." It represents a behavior sequence pattern (Table 3-P2), then the formal definition of the behavior sequence can be regarded as the behavior sequence pattern, which is the abstract expression of the behavior sequence with certain commonness (characteristics). It expresses a collection of behavior sequences of certain patterns.

The following is divided into several parts: formal definition of behavior sequence patterns, classification of operating objects, visual understanding, summary of various patterns, to explain the problems of this section. (the following is explained in the case of a single version, regardless of MVCC)

* scene classification of behavior sequence patterns: (the definitions of P0murP3Magi A5, etc., are shown in Table 3.)

Category 1. Concurrent operation of single data (one data item)

> > the formal description of the sequence of read and write operations for a single piece of data is complete, corresponding to three types of read and write conflicts: P0 (wmurw conflict), P1 (wmurr conflict) and P2 (rmurw conflict) (rmurr does not conflict).

Category 2. Concurrent operations of data sets (one data set of data items)

> > dataset operations correspond to P3 (potential illusion)

Category 3. Constrained data item manipulation phenomenon (data items with constraints)

> > data operations with associated constraints correspond to A5 (A5A (r-w-w-r), A5B (r-r-w-w),...) And other possible behavior patterns involving data association constraints

* Common behavior sequence patterns and their formal definitions (including exception sequence patterns)

Common phenomena

Abnormal phenomenon set / pattern

(covered by the original ANSI-SQL standard)

Common phenomenon set / pattern

(contains the corresponding abnormal phenomena,)

(enhanced ANSI-SQL isolation level)

E.g. Dirty writing

Record wmurw conflicts

A0 is not defined

P0: W1 [x]. W2 [x]. (c1/a1/c2/a2)

E.g. Dirty reading

Record wmurr conflicts

A1: w1[x]... R2[x]... a1

Write before you read

P1: W1 [x]... R2 [x]... (c1/a1/c2/a2)

P1 contains A1

E.g. Non-repeatable

Record the rmurw conflict

A2: r1[x]... w2[x]... c2... R1 [x]

Read before you write

P2: R1 [x]. W2 [x]. (c1/a1/c2/a2)

P2 contains A2

E.g. Illusion

Set rmurw conflict

A3: r1[P]... w2[x in P]... c2...r1[P]

Read before you write

P3: R1 [P]... W2 [x in P]... (c1/a1/c2/a2)

P3 contains A3

E.g. Write loss

Record r-w-w conflicts

-

P4: r1[x]... W2[x]... w1[x]... c1

P2 contains P4, read first and then write

E.g. Reading skew

Associated data conflict

A5A: (belongs to category A5 mode)

R1[x]... w2[x]... w2[y]... c2... R1 [y]

Read before you write

P2 contains P4

E.g. Writing skew

Associated data conflict

A5B: (belongs to category A5 mode)

R1[x]... r2[y]... W1 [y]... W2 [x]... (c1/c2)

Read before you write

P2 contains A5

... (etc.)

...

...

Table 3.

Description: (the following instructions are not the most important, but mainly lay the groundwork for the later behavior pattern diagram, which can be checked in comparison.)

(1) behavior sequence description: for example, P1: W1 [x]... R2 [x]... (c1/a1/c2/a2), transaction 1 writes data item x, after which (other data items / transaction operations may be experienced), transaction 2 writes data x, after which transaction 1 and 2 ends in any order and manner (commit / abort)

(2) semantics of behavior sequence patterns: sequences that satisfy a certain pattern P can form a set, and some specific sequences in the set may or may not produce abnormal results. For example, a sequence that conforms to the P2 pattern does not necessarily match A2 (dirty reading), and a specific sequence that matches A2 does not necessarily have a real impact. (for example, if the read operation in R2 [x] is not dependent on the operation lock of any subsequent application or person and is discarded just by looking at it, it will not have an impact.)

(3) A1-A3: these three abnormal sequence patterns are the abnormal behavior sequence patterns used by ANSI-SQL to define the isolation level, but these describe a specific kind of exception, and the description of record-level read-write conflict is not complete, so P0-P3 is proposed to extend A1-A3 in paper [1]. (for example, the A1 pattern is: "W1 [x]... R2 [x]... A1", which is a 3-tuple, while the P1 mode is: "W1 [x]... R2 [x]...", which is a 2-tuple (because any ending order and mode (c1/a1/c2/a2) is not limited by pairwise sequential patterns, it can be ignored). It is obvious that A1 is a special case of P1, and A2 to P2 and A3 to P3 is similar)

(4) serializable level: the incompleteness of the above A1-A3 also shows that the ANSI-SQL isolation level defined based on A1-A3 is not rigorous enough (see Table 4 of (3) for details).

(5) P4: write loss

A) P4 is different from P0, although they all involve wmurw conflicts, but the pattern of P0 is "W1 [x]-W2 [x] -. The conflict of P4 is" R1 [x]. W2 [x]. W1 [x] -. Compared with P0, there is a read operation of the same data item in the first place, which implies that the later W1 [x] may depend on the read result of R1 [x]. P0 does not have this.

B) P4 "R1 [x]. W2 [x]. W1 [x] -. C1" write loss is included in P2 "R1 [x]. W2 [x]." Read before you write.

(6) A5: the operation sequence of two data items with associated constraints may cause the associated constraints to be broken (which can be user-defined constraints). It should be noted that the association constraints based on any number of data items are not clearly defined in this paper, so there are other anomalies in addition to P0murP3 and A5.

A) A5A read skew: transaction 1 requires two read operations (R1 [x] .r1 [y]) to read two constrained data items, between which the write operation of transaction 2 (R1 [x]) is inserted. W1 [x]. W2 [y]. C2. R1 [y]. So that the constraint relationship has been broken on the second read operation.

B) A5B write skew: two transactions first read one data item (R1 [x]. R2 [y].), and then calculate and update the other data item (. W1 [y]. W2 [x]). If the two transactions cannot be serialized, the constraint may be broken. For example, the initial value x = 50; R1 [x = 50]. R2 [y = 50]. W1 [y: = xylene 1 =]. .........

(7) P2: unrepeatable phenomenon, which is more interesting:

A) P2 contains A2, which was mentioned earlier (3).

B) P2 contains P4, which was mentioned earlier in (4).

C) P2 contains A5A and A5B, which was mentioned earlier.

(8) END

Thus it can be seen that the A (I) sequence pattern is contained in the P (I) sequence pattern, I = 1pm 2pm 3. P0 is a sequence pattern that is not defined by class A (I). The class P (I) pattern (w words, r memory, r m w + data items / data sets) is more complete than the exception set of class A (I).

q. What is the difference and relationship between unrepeatable phenomena (A2/P2) and hallucinatory phenomena (A3/P3)?

a. Non-repeatable reading is only for a single piece of data. In fact, it can be considered that the illusion is an unrepeatable read phenomenon for the data set, so the illusion not only contains the illusion reading that can be avoided by the RR isolation level in MySQL (because the insertion of new data causes the set to be unrepeatable), but can be extended to the non-repeatable reading of the data set under the given predicate condition caused by adding / deleting / modifying data records.

For example: SELECT pk_id FROM t WHERE cond

Under the RU (read uncommitted) isolation level, the query result set can be changed by adding / deleting / modifying data records related to WHERE conditions. The data record that needs to be changed here is to cause a change in the cond decision, otherwise it will not affect the query result. For example, a key value of INSERT that satisfies cond, a key value of UPDATE (its old or target key value satisfies cond), and a key value of DELETE can change the query result set that satisfies cond.

* Visualization of abnormal phenomena

(1) the exception of A1-A2 (A3 is similar to A2) can be visualized as a "V" exception:

Figure 1.

(2) what is a type A5 anomaly? What is reading skew and writing skew?

In fact, A5 in paper [1] expresses the operation anomalies of two data items with associated constraints, in which A5A (read skew read skew) and A5B (write skew write skew) can be expressed as follows: (PS: to avoid ambiguity, skew is translated as skew rather than skew (generally easy to be understood as partial ordering). )

Figure 2.

* relationship summary of various common behavior patterns (phenomena)

In the paper [1], the relationship between the sequences mentioned in this section is implied in the analysis of the isolation level, and the author hereby summarizes it into a diagram. (the details of some set relationships in the following figure are open to discussion, but we can have a macro understanding based on this.)

Figure 3.

To sum up, a summary of abnormal phenomena has been made: formal expression and intuitive description.

Now that there are anomalies, let's look at how each isolation level is defined and what exceptions have been resolved.

(C) how the isolation level is strictly defined?

With the formal definition in (2), the isolation level can be relatively strictly defined. Here we will directly quote the descriptions in the papers and books. Here, in the understanding of (1), it is slightly modified: the definition of isolation level can be defined in many ways, but its fundamental meaning is that if a transaction system can avoid some problem set at run time, then the transaction of the system will have some corresponding isolation level, that is, the isolation level abstracts out the minimum abnormal phenomenon set to be avoided. As for the implementation of a certain isolation level of DBMS, there is no restriction on whether it is also possible to avoid exception sequences outside the minimum problem set of the corresponding level.

Let's take a look at how several definitions of isolation levels are explained progressively in paper [1].

1. Isolation level 4 defined in ANSI-SQL92 (resolve some or all exceptions in A1-A3):

Table 4.-[1]-table 1

However, due to Table 3 in (2). Tells us that A1-A3 's definition of exception is incomplete, so the above definition of ANSI-SQL isolation level is incomplete. In particular, the ANOMALY-SERIALIABLE level, which is only named for avoiding A1-A3, is not a real serializable (SR) isolation level, because concurrent transactions do not have concurrent operation anomalies when they meet the serializable isolation level (guaranteed in theory), while the ANOMALY-SERIALIABLE level can not avoid the occurrence of exceptions such as A5AMagneA5B. Therefore, the situation needs to be expanded to be more complete, as follows.

two。 Definition of isolation level based on P0-P3: (from paper [1])

After extending the ANSI exception A1-A3 to P0-P3, the enhanced ANSI-SQL isolation level definition is obtained:

Table 5.-[1]-table 3

The above definition will be strong, but how to implement it? Pops Jim Gray and others also summarized the definition of isolation level based on lock mechanism according to the data of all parties, which is a definition of realizable point of view, as follows.

3. Definition of isolation level based on lock mechanism: (from paper [1])

Table 6.-[1]-table 2

Here is a conclusion mentioned in paper [1]: the definitions of four isolation levels of Table 3 and Table 2 are equivalent, that is to say, the four isolation levels of Locking-based are equivalent to the four isolation levels defined by ANSI-SQL enhanced version.

Degree-0

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.