Optimistic lock resolution

One 、 Theoretical basis of optimistic lock

The so-called optimistic lock , In fact, it is mainly a kind of thought , Because there is no lock involved in the operation of optimistic lock , Optimistic lock is only opposite to pessimistic lock , Strictly speaking, optimistic lock cannot be called lock . So understand the concept of optimistic lock , Usually compared with pessimistic lock, it is better understood , Now let's better understand optimistic lock by comparing optimistic lock with pessimistic lock .

1.1 The concepts of optimistic lock and pessimistic lock

• Optimism lock ： Always assume the best , Every time I go to get the data, I think other people won't modify it , So it won't lock , Only when updating, we will judge whether others have updated this data during this period .

Be careful “ in the meantime ” It means the time from getting the data to updating the data . Because there is no lock , So other threads may change . Another point is that optimistic locking is actually an unlocked method to ensure the atomicity of a series of operations on a variable .

• Pessimistic locking ： Always assume the worst , Every time I go to get the data, I think others will modify it , So every time I get the data, I lock it , That way, people who want to take this data will block it , Until it gets the lock （ Shared resources are used by only one thread at a time , Other threads are blocking , Transfer resources to other threads after use ）. There are many lock mechanisms used in traditional relational databases , For example, line locks. , Table lock, etc. , Read the lock , Write locks, etc. , It's all locked before the operation .Java in synchronized and ReentrantLock Waiting for exclusive lock is the realization of pessimistic lock thought .

1.2 Two kinds of lock use scenarios

The introduction of two kinds of locks from above , We know that the two locks have their own advantages and disadvantages , Don't think one is better than the other , image Optimistic lock is suitable for writing less （ Read more scenes ）, That is, when conflicts really rarely happen , This can save the cost of locking , It enlarges the whole of the system throughput . But if it's more writing , There are often conflicts , This will lead to the continuous application of the upper layer retry, This, in turn, reduces performance , therefore In general, it is more suitable to use pessimistic lock in the scenario of writing more .

1.3 There are two common ways to implement optimistic locks

Optimistic locking can be achieved through version number mechanism or CAS Algorithm implementation .

1.3.1 Version number mechanism

There are also two common ways to implement the version number mechanism ：

• Use data version （Version） Recording mechanism Realization , This is the most common implementation of optimistic locking . What is a data version ？ Add a version identity to the data , This is generally done by adding a number type to a database table “version” Field to implement . When the data is read , take version The values of the fields are read together , The data is updated every time , Regarding this version Add the values of a .
  When we submit the update , Judge the records corresponding to the database table The current version information of is the same as that of the first time version Value comparison , If the current version number of the database table is fetched for the first time version The values are equal , Is updated , Otherwise, it is considered to be overdue According to the . Use the following picture to illustrate ：

  

  
  As shown in the figure above , If the update operations are executed in sequence , The version of the data （version） In turn, increasing , There is no conflict . However, if there are different business operations to repair the same version of data Change , that , Commit first （ In the figure B） The data version Updated to 2, When A stay B The data is found when the update is submitted later version It has been modified , that A The update operation will fail .

• Use time stamps （timestamp）. This implementation is similar to the first one , Also in need of optimistic lock control table Add a field to , Name doesn't matter , Field types use timestamps （timestamp）, And the above version similar , Also check the timestamp of the data in the current database when the update is submitted and compare it with the timestamp obtained before the update , If consistent OK, Otherwise it's a version conflict .

1.3.2 CAS Algorithm

namely Compare And Swap（ Comparison and exchange ）, It's a well-known unlocked algorithm . No lock programming , That is, to achieve variable synchronization between multiple threads without using locks , In other words, the synchronization of variables can be realized without thread blocking , So it's also called nonblocking synchronization （Non-blocking Synchronization）.CAS An operation contains three operands —— Value of memory location （V）、 The original value of the expected （A） And the new value （B）. perform CAS During operation , Compare the value of the memory location with the expected original value , If they match , The processor will automatically update the location value to the new value , otherwise , The processor does nothing .
Let's use an example to explain, I believe you will be more clear .
1. In memory address V among , The stored value is 10 The variable of .

 

2. The thread 1 Want to increase the value of the variable 1. For threads 1 Come on , Old expectations A=10, New value to modify B=11.

 

3. In a thread 1 Before you submit an update , Another thread 2 Take the lead , Put the memory address V The value of the variable in is first updated to 11.

 

4. Threads 1 Start submitting updates , First of all to A And address V The actual value of （Compare）, Find out A It's not equal to V The real value of , Submit failed .

5. Threads 1 Get the memory address again V The current value of the , And recalculate the new value you want to modify . Now for threads 1 Come on ,A=11,B=12. This process of retrying is called spin .

 

6. I'm lucky this time , No other thread changes the address V Value . Threads 1 Conduct Compare, Find out A And address V The actual value of is equal .

 

7. Threads 1 Conduct SWAP, Put the address V Replace the value of with B, That is to say 12.

 

notes ：CAS Disadvantages of the algorithm
【1】 The cycle time is long and the cost is high ： The spin CAS If it doesn't work for a long time , Will give CPU It's very expensive to execute .
【2】 Only one atomic operation of shared variables can be guaranteed ： Only one atomic operation of shared variables can be guaranteed . When operating on a shared variable , We can use cycles CAS The way to guarantee atomic operation , But when operating on multiple shared variables , loop CAS There is no guarantee of atomicity of operation , You can use the lock at this time , Or there's a clever way , It is to combine multiple shared variables into a shared variable to operate . For example, there are two shared variables i＝2,j=a, Merge ij=2a, And then use CAS To operate ij. from Java1.5 Start JDK Provides AtomicReference Class to ensure atomicity between reference objects , You can put multiple variables in one object CAS operation .
【3】ABA problem ： because CAS It is necessary to check whether there is any change in the lower value when operating the value , Update if nothing changes , But if a value turns out to be A, Turned into B, It's changed again. A, So use CAS Check that its value has not changed , But it actually changed .ABA The solution to the problem is to use version number . Append the version number to the variable , Add the version number to each variable update 1, that A－B－A Will become 1A-2B-3A.

Two 、 Implementation examples of optimistic locking in two ways

2.1 Use the version number mechanism to solve practical problems

2.1.1 Practical problems

Use MySQL 5.7 Do a test , The database engine is InnoDB, The database isolation level is repeatable （REPEATABLE-READ）, Read read share , Reading and writing are mutually exclusive . At this isolation level , In the case of multi transaction concurrency , There will still be data update conflicts .
First, let's analyze how the problem of update conflict arises .
Suppose we have a list of goods goods, The table structure is as follows ：

Field	data type	explain
goods_id	varchar(32)	goods id
count	int(11)	sales

For example, at a certain time A And transaction B, Operate the table at the same time goods_id = 213214324 The data of , The current sales volume is 100.

goods_id	count
213214324	100

The contents of the two transactions are the same , Are the data read first ,count +100 Post update .

We only discuss the implementation of optimistic lock , For the sake of description , Assume that the project has been integrated Spring frame , Use MyBatis do ORM,Service All methods of the class use transactions , The transaction propagation level uses PROPAGATION_REQUIRED , When the transaction fails, it will be rolled back automatically .
Service by GoodsService , The method to update the quantity is addCount() .

@Service
@Transaction
pubic class GoodsService{
    
    @Autowire
    private GoodsDao dao;
    
    public void addCount(String goodsId, Integer count) {
        Goods goods = dao.selectByGoodsId(goodsId);
        if (goodsSale == null) {
            throw new Execption(" The data doesn't exist ");
        }
        int count = goods.getCount() + count;
        goods.setCount(count);
        int count = dao.updateCount(goods);
        if (count == 0) {
            throw new Exception(" Failed to add quantity ");
        }
    }
}

The use of Dao by GoodsDao , There are two ways :

public interface GoodsSaleDao {
    Goods selectByGoodsId(@Param("goodsId") String goodsId);

    int updateCount(@Param("record") Goods goods);
}

mapper File corresponding sql Operation for ：

<!--  Inquire about  -->
<select id="selectByGoodsId" resultMap="BaseResultMap">
    select
    <include refid="Base_Column_List"/>
    from goods
    where goods_id = #{goodsId}
</select>

<!--  to update  -->
<update id="updateCount">
    update
    goods
    set count = #{record.count},
    where goods_id = #{record.goodsId}
</update>

Okay , Suppose there are two threads calling at the same time GoodsService Of addCount() , Operate on the same row of data , What's the problem ？
Whether there may be a conflict between two threads when updating ！ two addCount(100) , The result should be 300, But the result is 200. Because the above series of operations of querying and updating a variable are not atomic , There may be concurrency problems .

 

 

2.1.2 How to solve the problem

How to deal with the above problems , There is a simple and crude way , Since there will be thread safety problems in multithreaded access , Then lock it , Methods combined with synchronized Mutually exclusive .

public synchronized void addCount(String goodsId, Integer count) {
     Goods goods = dao.selectByGoodsId(goodsId);
        if (goodsSale == null) {
            throw new Execption(" The data doesn't exist ");
        }
        int count = goods.getCount() + count;
        goods.setCount(count);
        int count = dao.updateCount(goods);
        if (count == 0) {
            throw new Exception(" Failed to add quantity ");
        }
}

This solution can also solve the problem , But this simple and mutually exclusive approach , The granularity of the lock is too high , Transaction queuing , Low concurrency , Low performance . But if it's a distributed application , Also consider applying distributed locks , Performance is lower .
Considering that the probability of these update conflicts is not high . Here is another solution , Add a version number field in the database table to realize optimistic locking, so as to ensure the atomicity of the variable operation .
Next, let's discuss how to implement it .
First step ： Database table goods Add a new line data_version To record the version number of the data update . The new table structure is as follows ：

Field	data type	explain
goods_id	varchar(32)	goods id
count	int(11)	sales
data_version	int(11)	Version number

The second step ：GoodsDao Of updateCount() Corresponding mapper Of SQL Statement , The data is updated at the same time data_version = data_version + 1 , Execute this sql It's time to lock the data up , So this data_version Add 1 The operation of is atomic operation .

<!--  Optimistic lock update  -->
<update id="updateCount">
    update
    goods_sale
    set count = #{record.count}, data_version = data_version + 1
    where goods_sale_id = #{record.goodsSaleId}
    and data_version = #{record.dataVersion}
</update>

Dao After adjustment , Business A And transaction B The changes are as follows ：

 

There is a scheme to find conflicts and quickly fail , To make the update successful , Can be in GoodsService Add spin , Restart the execution of transaction business logic , Until there is no conflict , The update is successful . There are two ways to achieve spin , One is to use cycles , One is to use recursion .

• Cycle to achieve ：

public void addCount(String goodsId, Integer count) {
    while(true) {
        Goods goods = dao.selectByGoodsId(goodsId);
        if (goods == null) {
            throw new Execption(" The data doesn't exist ");
        }
        int count = goods.getCount() + count;
        goods.setCount(count);
        int count = dao.updateCount(goods);
        if (count > 0) {
            return;
        }   
    }
}

• Recursive implementation ：

public void addCount(String goodsId, Integer count) {
     Goods goods = dao.selectByGoodsId(goodsId);
        if (goods == null) {
            throw new Execption(" The data doesn't exist ");
        }
        int count = goods.getCount() + count;
        goods.setCount(count);
        int count = dao.updateCount(goods);
         if (count == 0) {
        addCount(goodsId, count)
    }
}

Through optimistic lock + The way you spin , Solve the thread safety problem of data update , And the lock granularity is lower than that of mutex , Good concurrency performance .
Use time stamps （timestamp）, This solution is similar to the above , I will not introduce it here .

2.2 utilize CAS Algorithms solve practical problems

Java in java.util.concurrent.atomic And all the atomic classes under the contract are based on CAS To achieve .
This involves java Source code analysis , It's not going to unfold here .

About CAS Relevant connection recommendations ：