Detailed explanation of redis' distributed lock principle

Distributed lock requirements

         In distributed systems , When multiple clients need to acquire locks , We need distributed locks . here , Locks are stored in a shared storage system , It can be shared and accessed by multiple clients .

          Distributed locks can be used A variable to implement . The operation logic of locking and releasing locks by the client ： When locking , First get the value of the lock variable , Then, according to whether the value of the lock variable is 0 Come on Judge whether locking is successful ; When releasing a lock, you need to set the value of the lock variable to 0, Indicates that the client no longer holds the lock . In a distributed scenario , The lock variable needs to be controlled by a Shared storage system to maintain , That's the only way , Multiple clients can access the lock variable by accessing the shared storage system . Corresponding , The operation of locking and releasing the lock becomes Read 、 Judge and set the lock variable value in the shared storage system .

         It can be seen from the above process , Distributed locks have the following two requirements ：

1. The process of locking and releasing distributed locks , Multiple operations involved . therefore , When implementing distributed locks , We need to ensure these Atomicity of lock operation ;
2. The shared storage system holds the lock variable , If the shared storage system fails or goes down , Then the client cannot perform lock operation . When implementing distributed locks , We need to consider the guarantee Reliability of shared storage system , So as to ensure the reliability of the lock

         As a shared storage system in the implementation of distributed lock ,Redis You can use key value pairs to hold lock variables , Then receive and process the operation requests for locking and releasing locks sent by different clients . We use it lock_key As key , To set the value of the lock variable .

          First, let's look at the locking operation , There are three actions ： Read lock variables , Judge the lock variable and modify the value of the lock variable to 1. These three operations need to ensure atomicity . How can we guarantee atomicity ？

Redis Atomic operation provided

         In order to achieve the critical area of concurrency control requirements, code mutually exclusive execution ,Redis There are two methods of atomic operation ：

1. Put multiple operations in Redis Implemented as an operation , That is, single command operation ;
2. Write multiple operations to one Lua Script , Perform a single... In an atomic manner Lua Script .

        Redis It's using One way to process the request operation command of the client in series , therefore , When Redis When executing a command operation , Other commands cannot be executed , This is equivalent to the command operation is Mutually exclusive . Of course ,Redis Snapshot generation for 、AOF Override these operations , You can use background threads or child processes to execute , That is, it is executed in parallel with the operation of the main thread . however , These operations just read data , Data will not be modified , therefore , We don't need to do concurrency control on them .

        You can see redis A single command operation can be performed atomically , But in practice , Data modification may require multiple operations , In this case redis Provides INCR/DECR command , It turns these three operations into an atomic operation .INCR/DECR Command can add value to the data / Impairment operations , And they are themselves a single command operation ,Redis When they are executed , It is mutually exclusive in itself .

         however , If the operation we want to perform is not to simply increase or decrease the data , But there are more complex judgment logic or other operations , that ,Redis The single command operation of cannot guarantee the mutually exclusive execution of multiple operations . therefore , This is the time , We need to use the second method , That is to say Lua Script . Redis Will The entire script is executed as a whole , The middle will not be inserted by other requests , Therefore, there is no need to worry about race conditions during script running . We can use Redis Of EVAL Command to execute the script . Suppose we write a script named lua.script, We can use Redis client , close eval Options , To execute the script . The parameters required by the script will be through... In the following command keys and args To pass .

redis-cli  --eval lua.script  keys , args

Redis Implement distributed locks

         We can use SETNX A single command sets the value of a key value pair . say concretely , It is this command that will judge whether the key value pair exists when executing , If it doesn't exist , Set the value of the key value pair , If there is , Just don't make any settings . Use redisTemplate operation SetNx Will return a Boolean value , Judge whether the lock is obtained according to the Boolean value .  For the release lock operation , We can execute the business logic , Use DEL Command to delete lock variables .SETNX It includes the process of obtaining the value of the lock variable and judging .

//  Lock 
SETNX lock_key 1
//  Business logic 
DO THINGS
//  Release the lock 
DEL lock_key

        But the use of SETNX and DEL The following problems will occur when implementing distributed locks by command combination ：

1. A client executed SETNX However, an exception occurred when processing business logic , unexecuted DEL operation , As a result, other clients cannot acquire locks .
2. A client A Yes SETNX, And the other client B When it processes business logic DEL command , And then the client C It's done again SETNX Acquire the lock , And A Operate and share data together , Cause error .

For the first question , An effective solution is , to The lock variable sets an expiration time .  For the second question , We need to be able to Distinguish lock operations from different clients . The specific operation is , During locking operation , Each client can give Lock variables Set up a The only value , The unique value here can be used to identify the client of the current operation . When releasing the lock , The client needs to judge , Whether the value of the current lock variable is equal to its own unique identifier , Only in equal cases , To release the lock . thus , There will be no problem of releasing the lock by mistake . The specific implementation is as follows ：

//  Lock , unique_value As the unique identification of the client 
SET lock_key unique_value NX PX 10000

among ,unique_value Is the unique identity of the client , It can be represented by a randomly generated string ,PX 10000 （ms amount to EX 10 s） said lock_key Will be in 10s After expired , So that the client can not release the lock due to an exception during this period . Because in the locking operation , Each client uses a unique identifier , So when releasing the lock , We need to determine the value of the lock variable , Is equal to the unique identification of the client performing the lock release operation . This is where it comes in Lua The script , because , The logic of locking operation also includes Read lock variables 、 Judgment value 、 Delete lock variable Multiple operations of .

Reliability assurance of distributed locks

for fear of Redis The lock cannot work due to instance failure ,Redis The developer of the Antirez A distributed lock algorithm is proposed Redlock.Redlock The basic idea of the algorithm , Is to let the client and multiple independent Redis Instances request locking in turn , If the client can communicate with More than half of the instances successfully completed the locking operation , So we say , The client successfully obtained the distributed lock , Otherwise, locking fails . thus , Even if there is a single Redis Instance failed , Because lock variables are also saved on other instances , therefore , The client can still lock normally , Lock variables are not lost .Redlock The algorithm can be divided into three steps ：

1. The client gets the current time
2. The clients are sent to... In order N individual Redis The instance performs a locking operation , Different from the above locking operation, a timeout will be set for the locking operation , If the lock operation times out, it will be connected with the next redis Instance to lock
3. Once the client is finished and all Redis Lock the instance , The client needs to calculate the total time of the whole locking process .

The client only if the following two conditions are met , Can be regarded as locking success .

• Conditions for a ： Clients from more than half （ Greater than or equal to N/2+1） Of Redis Successfully obtained the lock on the instance ;
• Condition 2 ： The total time taken by the client to acquire the lock does not exceed the effective time of the lock .

After these two conditions are met , We need to recalculate the effective time of this lock , The result of the calculation is the initial effective time of the lock minus the total time taken by the client to obtain the lock . If the effective time of the lock is too late to complete the operation of sharing data , We can release the lock , In order to avoid incomplete data operation , The lock expires . The operation of releasing the lock is the same as that of releasing the lock on the singleton .

Reference resources ： Geek time - Easy to learn , Efficient learning - Geek state (geekbang.org)