Implementation of distributed lock  

Train of thought ：SQL Optimize

In order to specifically simulate the seckill scene , Suppose the inventory table is called stock, The quantity of goods is called num, The new number calculated by the business code is new_num=num-1, Originally executed SQL by ：

update stock set num=new_num where id = id=#{id};

We can improve SQL, Let the database update the data according to its current value , For example, write as follows ：

update stock set num=num-1 where id = #{id};
 Copy code 

Although this seems to solve the problem , But suppose the quantity of inventory is 1, The two threads each subtract 1 after , You will find that the inventory has been deducted -1, It also cannot completely solve the concurrency problem .

Train of thought two ： Code locking

Since two threads take data at the same time, there is still a problem , So is there any way to make them execute in turn , So it's easy to think of locking it before checking the inventory , such as Java Of synchronized keyword .

This can guarantee the serialization well , Ensure that there is only one thread to execute the code snippet of inventory check and inventory deduction at a time , But there are also many shortcomings ：

1. Unable to achieve fine-grained control , If someone kills commodities A、 Some second kill products B, We should adopt the second kill method , They do not conflict with each other but can only be executed serially , Access will be slow .
2. because spring Inside @service Is a singleton , So you can write , If you use python Linguistic django frame , There is no way to do similar control at the code level , Not universal .
3. Only single point is supported （ stand-alone 、 Server environment ）, Unable to expand horizontally , Now they are basically deployed in clusters , Only one machine can work .

Maybe , We need a third-party mechanism , To realize such a lock .

Train of thought three ： be based on MySQL The pessimistic lock of

Because all threads are accessing the same table , You can lock the database , Typical practices include pessimistic lock and optimistic lock .

Pessimistic locks take advantage of select…for update grammar , for example ：

select * from stock where id=#{id} for update;

Be careful ： To use pessimistic locking, you need to put the business code in the transaction .

The pessimistic lock locks the data row when obtaining data , Other transactions want to obtain locks , You must wait until the original transaction is over .

Use selec…for update It locks the data ,MySQL InnoDB Default Row-Level Lock, So only 「 clear 」 Specifies the primary key ,MySQL Will execute Row lock ( Only the selected data is locked ) , otherwise MySQL Will execute Table Lock ( Lock the entire data form ).

The disadvantage of using pessimistic locks is , Because I want to lock my watch , So the concurrency is not high , If concurrency is too high , Too much pressure on the database , Will be down .

Train of thought four ： be based on MySQL Optimistic lock of

Optimistic lock is relative to pessimistic lock , The optimistic locking assumption assumes that data in general will not cause collisions , So when the data is submitted for update , The data conflict will be formally detected or not , If there is a conflict , Returns the user's error message , Let the user decide how to do it .

There are two ways to implement optimistic locking .

Using version number to implement optimistic lock

There are two ways to implement version numbers , One is the data version mechanism , One is the timestamp mechanism . As follows .

Use data version （Version） Record mechanism implementation , 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 , Determine which database table corresponds to the current version of the record and which is fetched for 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 outdated data .

If optimistic lock is used , Stock deducted SQL Change to next ：

1. Search out the product information

select num,version from stock where id=#{id};

1. Number of deductions .new_num = num -1
2. modify the database .

update stock set num=new_num, version=version+1 where id=#{id} and version=#{version};

If at this time version It has changed , Will fail to update , You can retry or report an error according to the specific business .

Use conditional constraints to achieve optimistic locking

This applies to data security verification only for updates , Suitable for inventory model , Deduct share and roll back share , Higher performance , Very convenient and practical .

SQL Change it to ：

update stock SET num = num - #{buyNum} where id = #{id} and num - #{buyNum} >= 0;

Be careful ： Update operation of optimistic lock , It's best to update... With a primary key or a unique index , This is a line lock , Otherwise, the table will be locked during update .

Optimistic lock has higher ability to carry concurrency than pessimistic lock , There will be more applications . But when concurrency gets higher and higher , The pressure on the database will also be relatively large , Because if the update fails, try again , You may keep querying the database .

Train of thought five ： be based on Redis Distributed lock

Since the lock implementation of the database can never bypass the concurrency problem , We turn to third-party middleware , such as Redis.

Just to mention here , If the concurrency is not high , be based on MySQL The pessimistic lock or optimistic lock can solve the problem , And maintenance is relatively simple , No need to introduce additional components , High system availability . The so-called architecture , It's just doing trade-off.

Let's briefly talk about the implementation principle , Threads A First in Redis Set the product's key（ such as goods_1） by 1, If the thread B Also found 1, Then not only poll , Until the thread A Release the lock , Threads B To get this lock again .

I use it here. Python Language is a simple simulation to achieve , It was used redis-py The library of , Wrote a Lock class , It contains two methods , Get the lock acquire And release the lock release：

import redis
class Lock:
    def __init__(self, name):
        self.redis_client = redis.Redis(host="127.0.0.1")
        self.name = name

    def acquire(self):
        #  If it is empty or None Getting a lock means 
        if not self.redis_client.get(self.name):
            self.redis_client.set(self.name, 1) 
            return True
        else:
            #  If you do not want to block the polling access lock , Can return directly False
            while True:
                import time
                time.sleep(1)
                if self.redis_client.get(self.name):
                    return True

    def release(self):
        self.redis_client.delete(self.name)

Train of thought six ：Redis Problems and improvements of distributed locks

Make sure the atomicity

Experienced friends will definitely find the problems in my above code , When concurrency is very high , It is possible for multiple threads to enter at the same time  if not self.redis_client.get(self.name), So I got the lock at the same time , This invalidates the distributed lock .

So we need to ensure atomicity in reading and setting values .

How to solve it ？Redis Nature provides setnx command , Atomic manipulation can be guaranteed , The order is at the designated key When there is no , by key Set the specified value .

So we can put the above Lock Upgrade the code to the following ：

import redis
class Lock:
    def __init__(self, name):
        self.redis_client = redis.Redis(host="127.0.0.1")
        self.name = name

    def acquire(self):
        if self.redis_client.setnx(self.name, 1): #  If there is no setting and 1, No return 0,  This is an atomic operation 
            return True
        else:
            #  If you do not want to block the polling access lock , Can return directly False
            while True:
                import time
                time.sleep(1)
                if self.redis_client.setnx(self.name, 1): #  Note that this place should also be changed 
                    return True

    def release(self):
        self.redis_client.delete(self.name)

Expiration time of lock

Let's move on to thinking , Suppose a thread gets the lock , But for some reason （ For example, the network is not connected redis, Code exception , A sudden power failure ） The lock was not released , As a result, other threads cannot get the lock , In the state of waiting forever , Cause a deadlock .

A good solution is to set the expiration time for the lock , We make use of redis-py Library provides the set function , And add atomic operation and expiration parameters to .

self.redis_client.set(self.name, self.id, nx=True, ex=15)

Renewal of locks

however , Expiration settings will cause new problems ：

If the current thread does not finish executing after a period of time , then key Out of date , It will cause another thread to get the lock and continue to execute , The program is unsafe .

in addition , Another thread may finish executing first , The current lock will be released , The lock of the original thread is released .

therefore , If the current thread has not finished executing , Then it should be renewed at an appropriate time , Reset the expiration time .

The more empirical approach is , For example, the expiration time is 15s, Then in 15s Of 2/3 Renew your lease when you are ready , Which is running 10s Reset the expiration time to 15s. You can start a new thread in the program to complete the lease renewal process on a regular basis .

Delete the security of the lock

There is also a point mentioned above , Other threads are at risk of releasing the lock of the current thread .

We can set the value for acquiring the lock , no need 1, While using uuid, And determine whether it belongs to the current thread when it is released uuid, Prevent being released by other threads .

So the code of distributed lock has evolved into the following ：

import uuid
import redis
class Lock:
    def __init__(self, name, id=None):
        self.id = uuid.uuid4()
        self.redis_client = redis.Redis(host="192.168.0.104")
        self.name = name

    def acquire(self):
        #  Set expiration time 15s,  If there is no setting and 1, No return 0,  This is an atomic operation 
        if self.redis_client.set(self.name, self.id, nx=True, ex=15): 
            #  Start a thread and periodically refresh the expired   This operation is also best done using lua Script to complete 
            return True
        else:
            while True:
                import time
                time.sleep(1)
                if self.redis_client.set(self.name, self.id, nx=True, ex=15):
                    return True

    def release(self):
        #  Make a judgment first , Take out the value first, and then judge the current value and your own lock Medium id Is it consistent , If deleted consistently , In case of inconsistency, an error is reported 
        #  This code is not secure ,  take get and delete Operation atomization , however Redis have access to lua The script completes this operation and atomizes it 
        id = self.redis_client.get(self.name)
        if id == self.id:
            self.redis_client.delete(self.name)
        else:
            print(" You cannot delete a lock that does not belong to you ")

The code above is not complete , Because I want to get and delete Operation atomization ,Redis There is no relevant operation instruction , There will still be security problems , There will also be such problems in the process of renewal .

however ,Redis For such a user scenario lua Script support , Users can send lua Script to perform custom actions , Get the response data of the script .Redis The server executes atomically with a single thread lua Script , Guarantee lua The script will not be interrupted by any other request during processing .

summary Redis Distributed lock

thus , Let's summarize the problems that need to be solved with distributed locks ：

• Mutual exclusivity ： Only one client can have a lock at any time , Multiple clients cannot get at the same time

• Deadlock ： The client that gets the lock is down for some reason , And failed to release the lock , Other clients can't get this lock , Organic systems are needed to avoid such problems

• • For example, code exception , As a result, it cannot run to release
  • There is a problem with the current server network , Let's say release when , Suddenly I can't visit Redis 了
  • Server power down

• Security ： The lock can only be deleted by the user holding the lock , It can't be deleted by other users
• Fault tolerance ： When some nodes are down , The client can still acquire or release the lock

Seven ideas ：Python Third party open source libraries

As mentioned above, we need to use Lua Scripts solve security problems , however lua Script writing is troublesome , Here I recommend a third-party open source library on the network , There is a very complete Python Realization Redis Method of distributed locking .

I'll post the flow chart of this library here ：

The overall implementation of this library is consistent with what we mentioned earlier , But there are some differences in detail . By reading the source code , I summarize as follows ：

• To reduce meaningless polling , Another one will be built Redis A list of , Used Redis Of blpop Instructions , Move out and get the first element of the list , If there are no elements in the list, it will block the list until the wait timeout or pop-up elements are found .
• It's difficult to read when you renew your lease , simply , It will start a thread to renew the lease , Suppose the lock time is 15s, The interval between renewal checks is 15s Of 2/3, namely 10s, Renewal of the lease , Reset the lock timeout to 15s, And in 10s Then continue the inspection .
• If the business code is blocked , Renewal may cause code to wait indefinitely , You need to be careful with , So the library provides optional parameters .
• Used __enter__,__exit__ Magic methods , Support when calling from the client with Realization .

thus ,Redis The distributed lock part of the lock has been completely introduced , Its advantage is simple to use , High performance at the same time , and Redis It is also a very common component , No extra maintenance is required .

Besides , Because of the single machine Redis There is also a risk of dying , We will use in production Redis cluster or Redis sentinel Guaranteed high availability .

Eight ideas ： be based on zookeeper Distributed locks for

Besides using Redis Realization ,zookeeper You can also implement distributed locks . But if it is not used in the project zookeeper, I don't think it's necessary to introduce additional components , In this way , I won't introduce more .

Thinking nine ：Java Medium Redission

If it is Java Code , have access to Redission Package to implement distributed locks .

The sample code is as follows ：

// 1. structure redisson It is necessary to implement distributed lock Config
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:5379").setPassword("123456").setDatabase(0);
// 2. structure RedissonClient
RedissonClient redissonClient = Redisson.create(config);
// 3. Get lock object instance （ There is no guarantee that you will get... In the order of threads ）
RLock rLock = redissonClient.getLock(lockKey);
try {
    /**
     * 4. Attempt to acquire lock 
     * waitTimeout  The maximum waiting time to try to acquire the lock , Beyond that , It is considered that the acquisition of lock failed 
     * leaseTime    Lock holding time , After this time, the lock will automatically fail （ Value should be set to be greater than the time of business processing , Ensure that the business can be processed within the lock validity period ）
     */
    boolean res = rLock.tryLock((long)waitTimeout, (long)leaseTime, TimeUnit.SECONDS);
    if (res) {
        // Successful lock acquisition , Deal with business here 
    }
} catch (Exception e) {
    throw new RuntimeException("aquire lock fail");
}finally{
    // in any case ,  Finally, we need to unlock 
    rLock.unlock();
}

Follow up planning

--------------------------------------------------

Provide a global view of the whole system 、 The only way to get the lock “ thing ”, Then every system needs to be locked , All ask this “ thing ” Get a lock , So different systems get the same lock .

It can be Redis、Zookeeper, It can also be a database .

be based on Redis Implement distributed locks

The above analysis shows why distributed locks should be used , Here, let's take a specific look at how to handle the distributed lock when it lands . Expand ：Redisson How to implement distributed lock ？

One of the most common solutions is to use Redis Do distributed locks

Use Redis The idea of distributed lock is like this ： stay redis Set a value in to indicate a lock , Then release the lock and put this key Delete .

The specific code is like this ：

?

There are several key points to this approach ：

• Be sure to use SET key value NX PX milliseconds command

  If not , Set the value first , Then set the expiration time , This is not an atomic operation , It's possible to go down before setting the expiration time , Can cause deadlock (key Forever )

• value To be unique

  This is for unlocking , Need to verify value It's the same as the lock key.

  This is to avoid a situation ： hypothesis A Acquire the lock , Expiration time 30s, here 35s after , The lock has been released automatically ,A Release lock , But it could be B Acquire the lock .A The client can't delete B It's locked .

In addition to considering how the client implements distributed locks , You need to think about redis The deployment of .

redis Yes 3 There are two ways to deploy ：

• standalone mode
• master-slave + sentinel Election model
• redis cluster Pattern

Use redis The disadvantage of distributed locking is that ： If you use the stand-alone deployment mode , There will be a single point of problem , as long as redis It's broken down . You can't lock it .

use master-slave Pattern , When locking, only one node is locked , Even through sentinel Made highly available , But if master Node failure , Master slave switch occurs , At this point, it is possible that the lock will be lost .

Based on the above considerations , Actually redis The author of this paper also considers this problem , He proposed a RedLock The algorithm of , The meaning of this algorithm is like this ：

hypothesis redis The deployment mode of is redis cluster, All in all 5 individual master node , Get a lock by following these steps ：

• Get the current timestamp , In milliseconds
• Take turns trying at each master Create lock on node , The expiration time setting is short , Usually tens of milliseconds
• Try to create a lock on most nodes , such as 5 Each node requires 3 Nodes （n / 2 +1）
• The client calculates the time when the lock is established , If the time to set up the lock is less than the timeout , Even if the establishment is successful
• If the lock establishment fails , Then delete the lock one by one
• As long as someone else establishes a distributed lock , You have to keep polling to try to get the lock

But this algorithm is still controversial , There may still be a lot of problems , There is no guarantee that the locking process will be correct .

Another way ：Redisson

Besides , Realization Redis Distributed locks for , In addition to being based on redis client Native api To achieve beyond , You can also use open source frameworks ：Redission

Redisson It's an enterprise level open source Redis Client, Also provides distributed lock support . I also highly recommend that you use , Why? ？

Think about it , If you write your own code to pass redis Set a value , It is set by the following command .

• SET anyLock unique_value NX PX 30000

The timeout set here is 30s, If I exceed 30s Without completing the business logic ,key Will expire , Other threads may get locks .

In this way , The first thread hasn't finished executing the business logic yet , When the second thread comes in, there will also be thread safety problems . So we also need to maintain the expiration time , It's too troublesome ~

Let's see redisson How did it happen ？ First feel the use of redission Cool ：

?

It's that simple , We just need to go through its api Medium lock and unlock The distributed lock can be completed , He helped us think about a lot of details ：

• redisson All instructions go through lua Script execution ,redis Support lua Script atomic execution

• redisson Set up a key The default expiration time is 30s, If a client holds a lock for more than 30s What do I do ？

  redisson There is one of them. watchdog The concept of , In translation, it's the watchdog , It will be after you get the lock , every other 10 Seconds to help you key The timeout of is set to 30s

  In this case , Even if you hold the lock all the time, it won't appear key Out of date , Other threads get locks .

• redisson Of “ watchdog ” Logic ensures that no deadlock occurs .

  ( If the machine goes down , The watchdog is gone . There will be no extension at this point key The expiration time of , here we are 30s Then it will automatically expire , Other threads can get locks )

Here's the implementation code ：

?

?

be based on zookeeper Implement distributed locks

Common distributed lock implementation scheme , Besides using redis To achieve beyond , Use zookeeper You can also implement distributed locks .

Introducing zookeeper( hereafter zk Instead of ) Before implementing the mechanism of distributed lock , Let me give you a brief introduction zk What is it? ：

Zookeeper It's about providing configuration management 、 Distributed collaboration and named centralized services .

zk This is the model of ：zk Contains a series of nodes , be called znode, It's like a file system, every znode Represents a directory , then znode There are some features ：

• Ordered node ： If there is currently a parent node /lock, We can create a child node under this parent node ;

  zookeeper Provides an optional ordered feature , For example, we can create child nodes “/lock/node-” And point to order , that zookeeper When generating a child node, an integer sequence number will be automatically added according to the current number of child nodes

  in other words , If it's the first child node created , So the generated child node is /lock/node-0000000000, The next node is /lock/node-0000000001, By analogy .

• Temporary node ： The client can create a temporary node , After the session ends or the session times out ,zookeeper The node will be deleted automatically .

• Event monitoring ： While reading the data , We can set event monitoring on nodes at the same time , When the node data or structure changes ,zookeeper The client will be notified . At present zookeeper There are four kinds of events ：

• • Node creation
  • The node to delete
  • Node data modification
  • Child node changes

Based on some of the above zk Characteristics of , We can easily come to the conclusion that zk Realize the landing scheme of distributed lock ：

1. Use zk Temporary nodes and ordered nodes of , Each thread acquires the lock in the following way zk Create a temporary, orderly node , For example /lock/ Under the table of contents .

2. After creating the node successfully , obtain /lock All temporary nodes in the directory , Then judge whether the node created by the current thread is the node with the smallest serial number of all nodes

3. If the node created by the current thread is the node with the smallest number of all nodes , The lock is obtained successfully .

4. If the node created by the current thread is not the node with the smallest sequence number of all nodes , Add an event listener to the node before the node sequence number .

   For example, the node sequence number obtained by the current thread is /lock/003, Then the list of all nodes is [/lock/001,/lock/002,/lock/003], On the other hand /lock/002 This node adds an event listener .

If the lock is released , Will wake up the next ordinal node , And then we'll do it again 3 Step , Determine whether the node number is the smallest .

such as /lock/001 The release of the ,/lock/002 Listen to the time , At this point, the node set is [/lock/002,/lock/003], be /lock/002 Is the smallest ordinal node , Get lock .

The whole process is as follows ：

This is the way to realize it , As for how to write the code , It's complicated here, so I won't post it .

Curator Introduce

Curator It's a zookeeper Open source client for , The implementation of distributed lock is also provided .

It's easy to use ：

?

Actually curator The underlying principle of implementing distributed lock is similar to that analyzed above . Here we use a diagram to describe the principle in detail ：

The advantages and disadvantages of the two schemes are compared

After learning two implementation schemes of distributed lock , What needs to be discussed in this section is redis and zk The advantages and disadvantages of each implementation scheme of .

about redis In terms of distributed locks , It has the following disadvantages ：

• It gets the lock in a simple and crude way , Try to acquire the lock without getting the lock , Compare consumption performance .
• Other foreign words ,redis Its design orientation determines that its data is not highly consistent , In some extreme cases , There may be problems . The lock model is not robust enough
• Even with redlock Algorithm to achieve , In some complex situations , There is no guarantee that it will come true 100% No problem , About redlock We can see How to do distributed locking
• redis Distributed lock , In fact, you need to keep trying to get the lock , Compare consumption performance .

But on the other hand redis Implementing distributed locks is very common in many enterprises , And most of the time, they don't meet the so-called “ Extremely complex scenes ”

So use redis As a distributed lock is also a good solution , The most important thing is redis High performance , It can support high concurrency acquisition 、 Release lock operation .

about zk For distributed locks :

• zookeeper Natural design orientation is distributed coordination , Strong consistency . The lock model is robust 、 Simple and easy to use 、 It is suitable for distributed locks .
• If the lock cannot be acquired , Just add a listener , Don't poll all the time , Less performance consumption .

however zk There are also disadvantages ： If more clients frequently apply for locking 、 Release the lock , about zk There will be more pressure on the cluster .

Summary ：

in summary ,redis and zookeeper Both have their advantages and disadvantages . When we do technology selection, we can take these problems as reference factors .

Suggest

Through the previous analysis , Two common ways to implement distributed locks ：redis and zookeeper, They have their own strengths . How to choose the model ？

Personally , I prefer zk Implemented locks ：

because redis There may be hidden dangers , The data may be wrong . however , How to choose depends on the specific situation in the company .

If the company has zk Cluster conditions , Priority selection zk Realization , But if the company only has redis colony , There are no conditions to build zk colony .

So it's practical redis It's also possible to , In addition, the system designer may have considered that the system already has redis, But I don't want to introduce some external dependence again , May choose redis.

**