How does Redis deal with concurrent access without locks and how to implement distributed locks

Redis is lock-free for concurrent access

Atomic operation is a method to provide lock-free concurrent access control. Atomic operations refer to operations that maintain atomicity during the execution process, and there is no need to add locks when atomic operations are executed, achieving lock-free operations.

The operations corresponding to concurrent access control are mainlyData modification operation. When the client needs to modify data, the basic process is divided into two steps:

The client first reads the data locally and modifies it locally;

After the client finishes modifying the data, write it back to Redis.

We call this process the "Read-Modify-Write" operation (Read-Modify-Write, or RMW operation for short). When multiple clients perform RMW operations on the same piece of data, we need to make the code involved in the RMW operation execute atomically.The RMW operation code that accesses the same piece of data is called the critical section code.

In order to achieve the mutually exclusive execution of critical section code required by concurrency control, Redis uses two methods for atomic operations:

Implement multiple operations into one operation in Redis, that isSingle command operation;

Write multiple operations to oneLua script, Execute a single Lua script atomically.

If the RMW operation we perform is to increase or decrease the value of the data, Redis providesAtomic operations INCR and DECR Can directly help us with concurrency control.

However, if the operation we want to perform is not simply to increase or decrease data, but to have more complex judgment logic or other operations, then Redis's single-command operation can no longer guarantee the mutually exclusive execution of multiple operations. So, at this time, we need to use the second method, which isLua script.

Redis will execute the entire Lua script as a whole, and will not be interrupted by other commands during the execution process, thus ensuring the atomicity of operations in the Lua script. If we have multiple operations to perform, but cannot be achieved with INCR/DECR command operations, we can write these operations to be performed into a Lua script. Then, we can use Redis's EVAL command to execute the script. In this way, these operations are mutually exclusive when executed.

If many operations are executed atomically in the Lua script, it will increase the time for Redis to execute the script, and it will also reduce the concurrent performance of Redis. So: when writing Lua scripts,Avoid writing operations that do not require concurrency control into scripts.

Use Redis to implement distributed locks

In a distributed system, when multiple clients need to compete for locks, we must ensure that,This lock cannot be a local lock of a client. Otherwise, other clients will not be able to access this lock, and of course they will not be able to acquire this lock.

So when there are multiple clients that need to acquire the lock, we needDistributed lock. At this time, the lock is stored in a shared storage system and can be shared access and acquired by multiple clients.

Distributed locks are the same as locks on a single machineUse a variable to achieve. When locking, it is also necessary to judge the value of the lock variable, and judge whether the lock is successful according to the value of the lock variable; when releasing the lock, the value of the lock variable needs to be set to 0, indicating that the client no longer holds the lock.

In a distributed scenario,Lock variables need to be maintained by a shared storage systemOnly in this way, multiple clients can access the lock variable by accessing the shared storage system. corresponding,The operation of locking and releasing the lock becomes reading, judging and setting the value of the lock variable in the shared storage system.

In this way, we can draw two requirements for implementing distributed locks:

Requirement 1: The process of adding and releasing a distributed lock involves multiple operations. Therefore, when implementing distributed locks, we need to ensure theseAtomicity of lock operations;

Requirement 2: The shared storage system saves lock variables. If the shared storage system fails or goes down, the client cannot perform the lock operation. When implementing distributed locks, we need to consider ensuring the reliability of the shared storage system, and thenEnsure the reliability of the lock.

Implement distributed locks based on a single Redis node

As a shared storage system in the implementation of distributed locks, Redis canUse key-value pairs to store lock variables, And then receive and process the lock and release operation requests sent by different clients.

We need to give the lock variable a variable name, and use this variable name as the key of the key-value pair, and the value of the lock variable is the value of the key-value pair. In this way, Redis can save the lock variable and the client will also The lock operation can be realized through the command operation of Redis.

img

Because locking includes three operations (reading the lock variable, judging the value of the lock variable, and setting the value of the lock variable to 1), these three operations need to be executed atomically. and soRedis can use single command operation to achieve lock operation.

first of allSETNX command, it is used to set the value of the key-value pair. Specifically, when this command is executed, it will determine whether the key-value pair exists. If it does not exist, it will set the value of the key-value pair. If it exists, no setting will be made.

For the release of the lock operation, we can execute the business logic,Use the DEL command to delete the lock variable.

In summary, we can use the combination of SETNX and DEL commands to implement lock and release lock operations:

// 加锁
SETNX lock_key 1

// 业务逻辑
DO THINGS

// 释放锁
DEL lock_key

However, using a combination of SETNX and DEL commands to implement distributed locks has two potential risks:

The first risk is that if a client executes the SETNX command and locks, an exception occurs when operating the shared data immediately, and the result is that the final DEL command has not been executed to release the lock. Therefore, the lock is always held by this client, and other clients cannot obtain the lock, nor can they access shared data and perform subsequent operations, which will affect business applications.

solution:Set an expiration time for the lock variable. In this way, even if the client holding the lock has an exception and cannot actively release the lock, Redis will delete the lock variable after it expires according to the expiration time of the lock variable. After the lock variable expires, other clients can request the lock again, which will not cause the problem of being unable to lock.

Let's look at the second risk. If client A executes the SETNX command to lock, suppose client B executes the DEL command to release the lock. At this time, the lock of client A is released by mistake. If client C happens to be applying for a lock, it can successfully obtain the lock and start operating the shared data.

solution:Differentiate lock operations from different clients. If the lock variable value is set to 1 or 0, it is used to indicate whether the lock is successful. 1 and 0 have only two states, which cannot indicate which client performed the lock operation. Therefore, when we lock the operation, we can let each client set a unique value for the lock variable, and the unique value here can be used to identify the client currently operating. When releasing the lock operation, the client needs to determine whether the value of the current lock variable is equal to its own unique identifier, and only when it is equal, can the lock be released. In this way, there will be no problem of accidentally releasing the lock.

How to implement specific commands in Redis?

In order to achieve the same effect as the SETNX command, Redis provides the option NX to the SET command, which is used to implement "set if not present". If the NX option is used, the SET command will only be set when the key-value pair does not exist, otherwise no assignment will be performed. In addition, the SET command can also be executed with EX or PX options to set the expiration time of the key-value pair. The key survival time is determined by the seconds or milliseconds option value .

Command format: SET key value [EX seconds | PX milliseconds] [NX]

Specific code:

// 加锁, unique_value作为客户端唯一性的标识
SET lock_key unique_value NX PX 10000

// 业务逻辑
DO THINGS

//释放锁 比较unique_value是否相等,避免误释放
if redis.call("get",KEYS[1]) == ARGV[1] then

​    return redis.call("del",KEYS[1])

else

​    return 0

end
这是使用 Lua 脚本(unlock.script)实现的释放锁操作的伪代码,其中,KEYS[1]表示 lock_key,ARGV[1]是当前客户端的唯一标识,这两个值都是我们在执行 Lua 脚本时作为参数传入的。

最后,我们执行下面的命令,就可以完成锁释放操作了。
redis-cli  --eval  unlock.script lock_key , unique_value 

Realize highly reliable distributed locks based on multiple Redis nodes

If only one Redis instance is used to store the lock variable, if this Redis instance fails and goes down, then the lock variable is gone. At this time, the client can no longer perform the lock operation, which will affect the normal execution of the business. Therefore, when we implement distributed locks, we also need to ensureReliability of the lock.

In order to avoid the problem of inoperable locks caused by Redis instance failure, Redis developer Antirez proposedDistributed lock algorithm Redlock.

The basic idea of ​​the Redlock algorithm is to allow the client and multiple independent Redis instances to request locks in turn. If the client can successfully complete the lock operation with more than half of the instances, then we believe that the client has successfully obtained distributed Locked, otherwise the lock fails. In this way, even if a single Redis instance fails, because the lock variable is also saved on other instances, the client can still perform the lock operation normally, and the lock variable will not be lost.

The execution steps of the Redlock algorithm:

The first step is,The client gets the current time.

The second step is,The client executes lock operations to N Redis instances in sequence.

The lock operation here is the same as the lock operation performed on a single instance. Use the SET command, bring NX, EX/PX options, and bring the unique identifier of the client. Of course, if a Redis instance fails, in order to ensure that the Redlock algorithm can continue to run in this case, we need to set a timeout for the lock operation.

If the client does not succeed in requesting a lock with a Redis instance until the timeout, then the client will continue to request the lock with the next Redis instance. The timeout time of the lock operation needs to be far less than the effective time of the lock, which is generally set to tens of milliseconds.

The third step is that once the client has completed the lock operation with all Redis instances, the client mustCalculate the total time spent in the entire locking process.

Only when the following two conditions are met, can the client consider the lock to be successful.

Condition 1: The client successfully obtains a lock from more than half of the Redis instances (greater than or equal to N/2+1);

Condition 2: The total time it takes for the client to acquire the lock does not exceed the effective time of the lock.

After satisfying these two conditions, 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 it takes for the client to acquire the lock. If the effective time of the lock is too late to complete the operation of sharing data, we can release the lock to avoid the situation that the lock expires before the data operation is completed.

Of course, if the client fails to meet these two conditions at the same time after performing the lock operation with all instances, then the client initiates a lock release operation to all Redis nodes.

In the Redlock algorithm, the operation of releasing the lock is the same as the operation of releasing the lock on a single instance, as long as the Lua script that releases the lock is executed. In this way, as long as more than half of the N Redis instances can work normally, the normal operation of distributed locks can be guaranteed.