Interview Essentials: talk about the various implementations of distributed locks!

Preface

Today, let's talk about the design and implementation of distributed lock . Hopefully that helped , If there's something wrong , Welcome to point out , Learning together , Make progress together ~

• Distributed lock Overview

• Database distributed lock

• Redis Distributed lock

• Zookeeper Distributed lock

• Comparison of three kinds of distributed locks

1. Distributed lock Overview

Our systems are all distributed , Daily development , Order in seconds 、 Rush to buy goods And so on , In case of ⽌ Inventory oversold , All need to use Distributed lock .

Distributed lock is actually , An implementation of a lock that controls different processes in a distributed system to access shared resources together . If different systems or different hosts of the same system share a critical resource , We often need mutual exclusion to prevent interference , To ensure consistency .

The industry's popular distributed lock implementation , It's common 3 Ways of planting ：

• Distributed lock based on database

• be based on Redis Implementation of distributed lock

• be based on Zookeeper Implementation of distributed lock

2. Distributed lock based on Database

2.1 Distributed lock implemented by database pessimistic lock

have access to select ... for update  To implement distributed locking . Our own projects , Distributed timed tasks , Similar solutions are used , Let me show you Simple version, huh

The table structure is as follows ：

CREATE TABLE `t_resource_lock` (
  `key_resource` varchar(45) COLLATE utf8_bin NOT NULL DEFAULT ' Resource primary key ',
  `status` char(1) COLLATE utf8_bin NOT NULL DEFAULT '' COMMENT 'S,F,P',
  `lock_flag` int(10) unsigned NOT NULL DEFAULT '0' COMMENT '1 It's locked  0 Is unlocked ',
  `begin_time` datetime DEFAULT NULL COMMENT ' Starting time ',
  `end_time` datetime DEFAULT NULL COMMENT ' End time ',
  `client_ip` varchar(45) COLLATE utf8_bin NOT NULL DEFAULT ' Grab the lock IP',
  `time` int(10) unsigned NOT NULL DEFAULT '60' COMMENT ' Only one node is allowed to obtain a lock once in the method life cycle , Company ： minute ',
  PRIMARY KEY (`key_resource`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin

Lock lock The pseudo code of the method is as follows ：

@Transcational // Be sure to add business 
public boolean lock(String keyResource,int time){
   resourceLock = 'select * from t_resource_lock where key_resource ='#{keySource}' for update';
   
   try{
    if(resourceLock==null){
      // Insert lock data 
      resourceLock = new ResourceLock();
      resourceLock.setTime(time);
      resourceLock.setLockFlag(1);  // locked 
      resourceLock.setStatus(P); // In processing 
      resourceLock.setBeginTime(new Date());
      int count = "insert into resourceLock"; 
      if(count==1){
         // Lock acquired successfully 
         return true;
      }
      return false;
   }
   }catch(Exception x){
      return false;
   }
   
   // It's unlocked and the lock has timed out , That is, the lock can be obtained successfully 
   if(resourceLock.getLockFlag=='0'&&'S'.equals(resourceLock.getstatus)
    && new Date()>=resourceLock.addDateTime(resourceLock.getBeginTime(,time)){
      resourceLock.setLockFlag(1);  // locked 
      resourceLock.setStatus(P); // In processing 
      resourceLock.setBeginTime(new Date());
      //update resourceLock;
      return true;
   }else if(new Date()>=resourceLock.addDateTime(resourceLock.getBeginTime(,time)){
     // The timeout is not completed normally , Lock acquisition failed 
     return false;
   }else{
     return false;
   } 
}

Unlock unlock The pseudo code of the method is as follows ：

public void unlock(String v,status){
      resourceLock.setLockFlag(0);  // Unlock 
      resourceLock.setStatus(status); S: It means success ,F It means failure 
      //update resourceLock;
      return ;
}

Overall process ：

try{
if(lock(keyResource,time)){ // Lock 
   status = process();// Your business logic handles .
 }
} finally{
    unlock(keyResource,status); // Release the lock 
}

In fact, this pessimistic lock implements distributed locks , The overall process is quite clear . First select ... for update  Lock the key key_resource That record , If it is empty , You can insert a record , If there are records, judge Status and time , Has it timed out . We need to pay attention here , Must add Business Ha .

2.2 Distributed lock implemented by database optimistic lock

Except for the pessimistic lock , You can also use Optimistic locks implement distributed locks . Optimism lock , seeing the name of a thing one thinks of its function , Is very optimistic , Every update operation , Think there will be no concurrency conflict , Only after the update fails , Just try again . It is based on CAS The realization of thought . My former company , Deduction balance That's the plan .

Create a version Field , Every time you update and modify , Will increase by one , Then when you update the balance , Put the version number found out , Bring conditions to update , If it's the last version number , Just update , If not , It means that others have modified it concurrently , Just keep trying again .

The general process is as follows ：

1. Query version number and balance

select version,balance from account where user_id ='666';

Suppose the version number is oldVersion=1.

1. Logical processing , Judge the balance

if(balance< Deduction amount ){
   return;
}

left_balance = balance -  Deduction amount ;

1. Deduct the balance

update account set balance = #{left_balance} ,version = version+1 where version 
= #{oldVersion} and balance>= #{left_balance} and user_id ='666';

You can take a look at this flow chart ：

This way suits Low concurrency Scene , Generally, you need to set the number of retries

3. be based on Redis Implementation of distributed lock

Redis Distributed locks are generally implemented in the following ways ：

• setnx + expire

• setnx + value The expiration value is

• set The extended command for （set ex px nx）

• set ex px nx + Verify unique random values , And then delete

• Redisson

• Redisson + RedLock

3.1 setnx + expire

Talk about Redis Distributed lock , Many small partners backhand is setnx + expire, as follows ：

if（jedis.setnx(key,lock_value) == 1）{ //setnx Lock 
    expire（key,100）; // Set expiration time 
    try {
        do something  // Business processing 
    }catch(){
    }
  finally {
       jedis.del(key); // Release the lock 
    }
}

This code can lock successfully , But do you see the problem , Locking operation and setting timeout are separated . Suppose after execution setnx After the lock , About to execute expire When setting expiration time , process crash Down or to restart maintenance , Then this lock is ever-young 了 , Other threads will never get the lock , therefore Distributed locks cannot be implemented this way ！

3.2 setnx + value The expiration value is

long expires = System.currentTimeMillis() + expireTime; // system time + Set expiration time 
String expiresStr = String.valueOf(expires);

//  If the current lock does not exist , Returns lock successfully 
if (jedis.setnx(key, expiresStr) == 1) {
        return true;
} 
//  If the lock already exists , The expiration time of the lock acquired 
String currentValueStr = jedis.get(key);

//  If you get the expiration time , Less than the current system time , Indicates that it has expired 
if (currentValueStr != null && Long.parseLong(currentValueStr) < System.currentTimeMillis()) {

     //  Lock expired , Gets the expiration time of the last lock , And set the expiration time of the current lock （ Don't understand redis Of getSet Little friend of command , You can go to the official website ）
    String oldValueStr = jedis.getSet(key, expiresStr);
    
    if (oldValueStr != null && oldValueStr.equals(currentValueStr)) {
         //  Consider the case of multi-threaded concurrency , Only one thread has the same set value as the current value , It can be locked 
         return true;
    }
}
        
// Other situations , All return to lock failure 
return false;
}

Daily development , This is how some small partners implement distributed locks , But there will be these shortcoming ：

• The expiration time is generated by the client itself , Distributed environment , The time of each client must be synchronized .

• There is no unique identity of the holder of the preservation , May be released by other clients / Unlock .

• When the lock expires , Concurrent requests from multiple clients at the same time , Both have been implemented. jedis.getSet(), In the end, only one client can lock successfully , But the expiration time of the client lock , May be covered by other clients .

3.3  set The extended command for (set ex px nx)

What do the parameters of this command mean ？ Review with you ：

SET key value [EX seconds] [PX milliseconds] [NX|XX]

• EX second ： Set the expiration time of the key to second second .

• PX millisecond ： Set the expiration time of the key to millisecond millisecond .

• NX ： Only if the bond doesn't exist , To set the key .

• XX ： Only if the bond already exists , To set the key .

if（jedis.set(key, lock_value, "NX", "EX", 100s) == 1）{ // Lock 
    try {
        do something  // Business processing 
    }catch(){
  }
  finally {
       jedis.del(key); // Release the lock 
    }
}

This scheme may have such problems ：

• The lock expired and released , The business is not finished .

• The lock was mistakenly deleted by another thread .

Some partners may have a question , Namely Why are locks accidentally deleted by other threads Well ？ Suppose that in the scenario of concurrent multithreading , Threads A For the lock , But if it doesn't release the lock , Threads B You can't get the lock , So it can't execute the code under locking , How can it cause the lock to be deleted by other threads ？

Assuming that thread A and B, I want to use it key Lock , Last A Grab the lock and lock it successfully , But because it takes a long time to execute business logic , The set timeout has been exceeded 100s. Now ,Redis It's automatically released key lock . At this point, the thread B You can lock it successfully , Take it , It also performs business logic processing . Suppose it happens at this time ,A Execute your own business logic , It releases the lock , But it just B My lock has been released .

3.4 set ex px nx + Verify unique random values , And then delete

In order to solve The lock was mistakenly deleted by another thread problem . Can be in set ex px nx On the basis of , Add the unique random value of a check , as follows ：

if（jedis.set(key, uni_request_id, "NX", "EX", 100s) == 1）{ // Lock 
    try {
        do something  // Business processing 
    }catch(){
  }
  finally {
       // Judge whether it is the lock added by the current thread , Just released 
       if (uni_request_id.equals(jedis.get(key))) {
          jedis.del(key); // Release the lock 
        }
    }
}

ad locum , Judge the lock added and released by the current thread It's not an atomic operation . If the jedis.del() When you release the lock , Probably This lock no longer belongs to the current client , Will unlock others .

It can be used in general lua Script to package .lua The script is as follows ：

if redis.call('get',KEYS[1]) == ARGV[1] then 
   return redis.call('del',KEYS[1]) 
else
   return 0
end;

This way is better , In general , You can already use this implementation . But it still exists ： The lock expired and released , The problem that the business has not been completed .

3.5 Redisson

For possible existence Lock expired release , The business is not finished The problem of . We can set the lock expiration time a little longer , It would be better if it took longer than normal business processing time . If you don't feel very stable , You can also give the thread that obtains the lock , Turn on a timed guard thread , Check every once in a while if the lock still exists , If it exists, the expiration time of the lock will be extended , Prevent lock expiration and early release .

The current open source framework Redisson That solved the problem . May have a look Redisson The underlying schematic ：

As long as the thread is locked successfully , Will start a watch dog watchdog , It's a background thread , Every time 10 Second check , If the thread 1 And hold the lock , Then it will keep extending the lock key Survival time . therefore ,Redisson Is the use of watch dog It's solved Lock expired release , The business is not finished .

3.6 Redisson + RedLock

The first six schemes are based on Redis Stand-alone version Discussion of distributed locks , Not perfect yet . because Redis It's usually deployed in a cluster ：

If a thread is in Redis Of master The lock is held on the node , But locked key It's not synced to slave node . Just then ,master Node failure , One slave The node will be upgraded to master node . Thread 2 can naturally obtain the same key It's my lock , But thread one has got the lock , The security of the lock is gone .

To solve this problem ,Redis author antirez An advanced distributed lock algorithm is proposed ：Redlock. Its core idea is ：

Deploy multiple Redis master, To make sure they don't go down at the same time . And these master Nodes are completely independent of each other , There is no data synchronization between them . meanwhile , We need to make sure that in many of these master For instance , Is with in Redis Single instance , Use the same method to get and release locks .

Let's assume that there are 5 individual Redis master node , stay 5 Run these on servers Redis example .

RedLock Implementation steps of :

1. Get the current time , In Milliseconds .

2. In order to 5 individual master Node request lock . The client sets the network connection and response timeout , And the timeout time should be less than the lock expiration time .（ Suppose that the automatic lock failure time is 10 second , The time-out time is usually 5-50 Between milliseconds , Let's assume that the timeout is 50ms Well ）. If the timeout , Skip this master node , Try the next one as soon as possible master node .

3. The client subtracts the lock acquisition start time from the current time （ That's the step 1 Recorded time ）, Get time to acquire lock usage . If and only if more than half （N/2+1, Here is 5/2+1=3 Nodes ） Of Redis master All nodes get locks , When the time used is less than the lock failure time , Lock is success .（ Pictured above ,10s> 30ms+40ms+50ms+4m0s+50ms）

4. If you get the lock ,key The real effective time of the system will change , You need to subtract the time taken to acquire the lock .

5. If the lock acquisition fails （ Not at least N/2+1 individual master Instance to lock , The time to have or acquire the lock has exceeded the valid time ）, The client should be in all master Unlock on node （ Even if some master The node is not locked successfully at all , Also need to unlock , To prevent some fish from missing the net ）.

The next step to simplify is ：

• In order to 5 individual master Node request lock

• Judge according to the set timeout , Do you want to skip the master node .

• If greater than or equal to 3 Nodes locked successfully , And the use time is less than the validity period of the lock , You can confirm that the locking is successful .

• If the lock acquisition fails , Unlock ！

Redisson Realized redLock Version of the lock , Interested partners , You can learn about it ~

4. Zookeeper Distributed lock

I'm learning Zookeeper Before distributed locks , Let's review Zookeeper The node of .

Zookeeper The node of Znode There are four types ：

• Persistent node ： The default node type . Create the client and zookeeper After disconnection , The node still exists .

• Persistent node order node ： So called sequential nodes , When you create a node ,Zookeeper Number the node name according to the created time sequence , A persistent node is a sequential persistent node .

• Temporary node ： Contrary to persistent nodes , When creating a node's client with zookeeper After disconnection , Temporary nodes will be deleted .

• Temporary order node ： Sequential temporary nodes .

Zookeeper Distributed lock realizes the application of Temporary order node . No code is posted here , Let's talk about it zk The implementation principle of distributed lock .

4.1 zk Acquire lock process

When the first client requests it ,Zookeeper The client creates a persistent node locks. If it （Client1） Want to get a lock , Need to be in locks Create a sequential node under the node lock1. Pictured

next , client Client1 I'll look for locks All temporary sequential child nodes below , Judge your own node lock1 Is it the smallest one , If it is , The lock is obtained successfully .

At this time, if there is another client client2 Come and try to get the lock , It will be locks Next, create a temporary node lock2

client client2 Will also find locks All temporary sequential child nodes below , Judge your own node lock2 Is it the smallest , here , Find out lock1 Is the smallest , So the lock acquisition failed . Lock acquisition failed , It will not be reconciled ,client2 Sort the top nodes lock1 register Watcher event , Used to monitor lock1 Whether there is , in other words client2 Lock grabbing failed and entered the waiting state .

here , If there's another client Client3 To try to get the lock , It will be locks Next, create a temporary node lock3

alike ,client3 Will also find locks All temporary sequential child nodes below , Judge your own node lock3 Is it the smallest , Find yourself not the smallest , Failed to acquire the lock . It will not be reconciled , It will send a message to the node in front of it lock2 register Watcher event , To monitor lock2 Whether the node exists .

4.2 Release the lock

Let's take a look at the process of releasing the lock ,Zookeeper The client service is completed or fails , Will delete the temporary node , Release the lock . If the task is completed ,Client1 Will explicitly call delete lock1 Instructions

If the client fails , According to the characteristics of temporary nodes ,lock1 It will be deleted automatically

lock1 After the node is deleted ,Client2 I'm so happy , Because it keeps listening lock1.lock1 The node to delete ,Client2 Receive notice immediately , You'll find it, too locks All temporary sequential child nodes below , Hair down lock2 Is the smallest , Get the lock .

Empathy ,Client2 After getting the lock ,Client3 Also eyeing it , Ah ha ha ~

• Zookeeper Design orientation is distributed coordination , Simple and easy to use . If the lock cannot be acquired , Just add a listener , Very suitable for distributed locks .

• Zookeeper As a distributed lock, there are also disadvantages ： If many clients frequently apply for locking 、 Release the lock , about Zookeeper There will be more pressure on the cluster .

5. Comparison of three kinds of distributed locks

5.1 Database distributed lock implementation

advantage ：

• Simple , Easy to use , No need to introduce Redis、zookeeper Such as middleware .

shortcoming ：

• Not suitable for high concurrency scenarios

• db Poor operational performance ;

5.2 Redis Distributed lock implementation

advantage ：

• Good performance , Suitable for high concurrency scenarios

• Lighter weight

• Better framework support , Such as Redisson

shortcoming ：

• Expiration time is not easy to control

• Consider the scenario where the lock is accidentally deleted by another thread

5.3 Zookeeper Distributed lock implementation

shortcoming ：

• Performance is not as good as redis Implementation of distributed lock

• Heavier distributed locks .

advantage ：

• It has good performance and reliability

• There is a well encapsulated framework , Such as Curator

5.4 Comparison summary

• From a performance perspective （ From high to low ）Redis > Zookeeper >= database ;

• From the point of view of ease of understanding （ From low to high ） database > Redis > Zookeeper;

• From an implementation complexity perspective （ From low to high ）Zookeeper > Redis > database ;

• From a reliability perspective （ From high to low ）Zookeeper > Redis > database .

If this article helps you , Don't forget to give me a 3 even , give the thumbs-up , forward , Comment on ,

I'll see you next time ！ How to get answers ： Liked Commented Closed ~

Learn more knowledge and skills , Follow up with private bloggers （03）