[introduction to database system (Wang Shan)] Chapter 11 concurrency control

Multi transaction execution mode

        Serial execution 、 Cross concurrency 、 Concurrent mode

Why concurrency control ？

        When multiple users access the database concurrently, multiple transactions will access the same data at the same time . If there is no control over concurrent operations, incorrect data may be accessed and stored , Destruction is the consistency of transactions and databases . Therefore, the database management system must provide concurrency control mechanism .

Responsibility of concurrency control mechanism in database management system ：

        Ensure the isolation and consistency of transactions ,DBMS Concurrent operations need to be properly scheduled .

Data inconsistencies caused by concurrent operations mainly include ：

        Missing changes 、 It can't be read repeatedly 、 read “ dirty ” data .

Concurrency control technology ：

        The blockade .

There are two basic types of blockade ：

        Exclusive lock （ Write lock 、X lock ）, Shared lock （ Read the lock 、S lock ）.

Block the compatibility matrix of type ：

Three level blockade agreement ：

1 Level blockade protocol ：

        Business T Modifying data R It must be added before X lock , Not released until the end of the transaction .
        Normal end （COMMIT） Abnormal end （ROLLBACK）
       1 The level-1 blocking protocol can prevent the loss of modifications
        stay 1 In the level-1 blockade agreement , If it's reading data , It doesn't need to be locked , So it cannot be guaranteed to be heavy Reread and unread “ dirty ” data .

2 Level blockade protocol ：

       1 Level blockade protocol + Business T Reading data R Must be preceded by S lock , After reading, you can release S lock .
        2 Level blocking protocol can prevent losing modification and reading “ dirty ” data .
        stay 2 In the level-1 blockade agreement , Because the data can be released after reading S lock , So it's not guaranteed to be repeatable .

3 Level blockade protocol ：

       1 Level blockade protocol + Business T Reading data R It must be added before S lock , Not released until the end of the transaction .
       3 The level-1 blocking protocol can prevent the loss of modifications 、 Read dirty data and non repeatable data .

Summary of the three-level blockade agreement ：

Live lock ：

        A transaction is always waiting .
        The simple way to avoid live locks is to adopt a first come, first served strategy .

Deadlock ：

        Multiple transactions are waiting at the same time . Each transaction is waiting for other transactions to release the lock so that it can continue to execute , Thus, there is a deadlock in which multiple transactions wait for each other , Every transaction can never end .

Deadlock prevention ：

        It's not easy to achieve , so DBMS The method of diagnosing and releasing deadlock is widely used in solving deadlock problem

One time blockade ：

        Each transaction is required to lock all data to be used at one time , Otherwise, we can't carry on .
        The problems of the first blockade law ： Reduce concurrency 、 Expand the scope of the blockade .

Sequential blockade ：

        Sequential blocking method is to specify a blocking order for data objects in advance , Everything is blocked in this order .

Problems of sequential blockade method ：

        Maintenance costs are high .
        There are many data objects that can be blocked in the database system , And with the insertion of data 、 Delete, etc. and change constantly , It is very difficult to maintain the blocking order of such a large and changing resource , Cost is very high .

Deadlock diagnosis and release

Deadlock diagnosis method ：

Overtime method ： If the waiting time of a transaction exceeds the specified time limit , Think of a deadlock .

        advantage ： Implement a simple
        shortcoming ：1） May misjudge deadlock ;2） If the time limit is set too long , It can't be found in time after deadlock .

Waiting graph ： The transaction waiting graph is used to dynamically reflect the waiting situation of all transactions .

        The transaction waiting graph is a directed graph G=(T,U),T For the set of nodes , Each node represents a running transaction , U A collection of sides , Each side represents the transaction waiting , if T1 wait for T2, be T1,T2 Draw a directed edge between , from T1 Point to T2, The concurrency control subsystem periodically （ Like every other 1 min） Detect transaction wait graph , If a circuit is found in the diagram , It means there is a deadlock in the system .

Deadlock Relieving ：

        Choose a transaction with the least deadlock cost , Undo it , Release all locks held by this transaction , Enable other transactions to continue .

Serial scheduling is correct , It is also true that the execution result is equivalent to serial scheduling .

Serializable scheduling ：

        If and only if the result is the same as when these transactions are executed serially in a certain order , Call this scheduling strategy serializable scheduling .

Serializability ：

        It is the criterion for the correct scheduling of concurrent transactions . According to this rule , A given concurrent schedule , If and only if it is serializable , I think it's the right scheduling .

at present DBMS The method of two-stage lock protocol is widely used to realize the serialization of concurrent scheduling , To ensure the correctness of scheduling .

Contents of the two-stage lock agreement ：

       1） Reading any data 、 Before writing operations , The first thing a transaction needs to do is get a block on that data .
       2） After releasing a blockade , Transactions are no longer subject to any other blockade .

“ Two paragraphs ” The meaning of lock ： The transaction is divided into two stages

        The first stage is to get the blockade , Also known as the extension phase ;
        The second stage is to release the blockade , Also known as the contraction phase .

Two stage locking protocol and three-level blocking Protocol

        Two kinds of agreements with different purposes ： Two stage lock protocol Ensure the correctness of concurrent scheduling .
        Three level blockade agreement ： Ensure data consistency to varying degrees .
        Compliance with the third level blockade agreement must comply with the two-stage agreement .

The size of the blocking object is called blocking granularity . The blocking object can be a logical unit 、 Physical unit .

        example ： In a relational database , Block the object ：
        Logical unit : Property value 、 Property value set 、 Tuples 、 Relationship 、 Index entry 、 The whole index 、 The whole database, etc .
        Physical unit ： page （ Data page or index page ）、 Physical records, etc .

The relationship between blocking granularity and concurrency ：

        The greater the granularity of the block Big , Small ,
        Objects whose system is blocked Less , many ,
        Concurrency Small , high ,
        overhead Small , Big ,
        Select block granularity ： Consider the blocking mechanism and concurrency ; Weigh the system overhead and concurrency

Choose the principle of blocking granularity ：

        User transactions that need to handle a large number of tuples of multiple relationships ： Take the database as the blocking unit ;
        User transactions that need to handle a large number of tuples ： Take the relationship as the blocking unit ;
        Handle user transactions with only a small number of tuples ： In tuples .

Multi granularity blocking ： Multiple blocking granularity are supported in one system for different transaction choices .

Multi granularity tree ：

       1） Multi level blocking granularity is represented by tree structure .
        2） The root node is the entire database , Represents the maximum data granularity .
       3） Leaf nodes represent the smallest data granularity .

Multi granularity blocking protocol ：

        Allow each node in the multi granularity tree to be locked independently ;
        Locking a node means that all descendant nodes of the node are also locked of the same type ;
        In multi granularity blocking, a data object may be blocked in two ways ： Explicit blocking and implicit blocking .

Explicit blocking :

        A block directly added to a data object .

Implicitly block :

        The data object is locked because its parent node is locked .
Explicit blocking has the same effect as implicit blocking .

Introduction of intention lock （intention lock） Purpose ：

        Improve the efficiency of system checking when a data object is locked .

Three kinds of common intention locks ：

        Intention sharing lock ( abbreviation IS lock )、 Intention exclusive lock (, abbreviation IX lock )、 Sharing intention exclusive lock ( abbreviation SIX lock )

IS lock ：

        If you add... To a data object IS lock , Represents its descendant node （ Intention ） Add S lock .

IX lock ：

        If you add... To a data object IX lock , Represents its descendant node （ Intention ） Add X lock .

SIX lock ：

        If you add... To a data object SIX lock , To add to it S lock , add IX lock , namely SIX = S + IX.