We know that both Redis and ZooKeeper can build distributed locks, but what are the similarities and differences between them, and how do these differences guide us in our daily production scenarios?

How to implement distributed locking

There are three phases when a process requests a distributed lock: 1. 2. The process that obtains the lock holds the lock and executes the service logic. 3. The process that obtains the lock releases the lock. The analysis follows these three stages.

Single Redis

Acquiring a lock

The lock is acquired by SETNX from the original requesting process;

127.0.0.1:6379> SETNX redis_locks 1
(integer) 1
Copy the code

– > because there is process by SETNX command to get the lock, hang up during execution of business logic, failed to release the lock, lead to a deadlock scenario, the introduction of the mechanism is used to break the deadlock timeout condition of (the process of access to the lock has been holding a lock), makes the lock even after the collapse in the process of acquiring a lock can be released through the timeout mechanism;

127.0.0.1:6379> SETNX redis_locks 1
(integer) 1
127.0.0.1:6379> EXPIRE redis_locks 60
(integer) 1
Copy the code

-> After the introduction of the timeout mechanism, there are two commands to obtain the lock, SETNX+EXPIRE, the former is used to add the lock, the latter is used to set the expiration time of the lock, that is, the lock process is no longer atomic; Therefore, there are also scenarios where the process obtains the lock through SETNX and dies without executing EXPIRE, which will also lead to deadlocks. Therefore, Redis extended the SET parameter after 2.6.12, so that SETNX+EXPIRE can be implemented with a single command SET Key Value EX 10 NX, ensuring atomicity of lock acquisition.

127.0.0.1:6379> SET redis_locks 1 EX 60 NX
OK
Copy the code

Release the lock

After executing the business logic, the process that originally acquired the lock calls DEL to release the lock.

-> The introduction of timeout mechanism makes lock release an additional channel; If access to lock in the process of the process execution of business logic because GC pause to causes such as process, and suspended because process leading to trigger lock timeout mechanism makes the lock is released, another process acquiring a lock is successful, but don’t know when the current process to run their own locks have been released, will continue to execute the business logic and releases the lock, The lock is held by another process; That is, a client releases a lock held by another client, and the solution to this problem is to add a unique identifier of the lock owner, such as UUID. When the process is ready to release the lock, it first checks the identifier of the lock to confirm whether the lock belongs to itself. Only when the lock belongs to itself will it be released.

// uuid can be obtained by using uuid.randomuuid ().tostring () 127.0.0.1:6379> SET redis_locks $uuid EX 60 NX OKCopy the code

-> After the introduction of unique identifier, lock release needs to check the lock identifier and release the lock two steps, obviously not atomic; In extreme cases, the lock still belongs to itself when the lock identifier is checked, but after the check, the lock will be released due to timeout. At this time, another process has acquired the lock, which leads to the possibility of the current process still releasing the lock of other processes. Therefore, these two steps need to be atomic, usually through Lua scripts;

Atomic script contains two steps: If redis.call("GET", KEYS[1]) == ARGV[1] then return redis.call("DEL", KEYS[1]) else return 0 endCopy the code

Optimization: automatic renewal

Although the above process has solved the problem that the current process can release the locks of other processes in the scenario that the locks are automatically released due to expiration when the process holds the lock and performs the service logic, the current process can also continue to run the service logic. However, if the current service logic has sequential causality, such as Read And Modify, Check Then Act, data consistency may occur.

Here’s an example:

  1. The service logic is used to add one to a value of the database. Then the process that obtains the lock first reads the current value of the database as1, and then the lock times out because the GC is stuck in process pause;
  2. At this point, another process acquires the lock and reads from the database the current value is1, and write after +1, the database value is2;
  3. Then the first process goes fromGCWake up and continue to execute the business logic on the previously read value1Write after +1, the database value is still2; And that causedUpdate the lostThe problem;

Therefore, it is better to provide a mechanism to renew the lock. That is, the client starts a daemon thread. If the current lock is about to expire, but the business logic is not completed, the thread will automatically renew the lock.

In the Java ecosystem, Redisson implements automatic renewal through the watchdog mechanism, which we only need to reference; There are many features implemented in Redisson’s SDK, such as reentrant locking, optimistic locking, fair locking, read/write locking, and RedLock, which will be mentioned in the cluster version below.

Redis cluster

In general, the production environment constructs redis cluster through the master-slave + sentry mechanism, and provides services externally through the writer-master/read-slave mechanism. For the write service, if the master database is successfully written, the client is returned, and the master/slave status is asynchronously synchronized through the RDB+AOF mechanism.

Therefore, in the redis cluster under the write primary read secondary policy, a process writes primary Redis through the SET x x EX x NX command and successfully obtains the lock, and the command has not been synchronized through the AOF network. If the primary Redis crashes at this time, the sentry will perform the primary/secondary switchover. Obviously, there is no key-value pair for the lock from the library, so if another process tries to acquire the lock, it may succeed, which will cause the lock mechanism to no longer meet the mutual exclusion.

The key to the above problem is that there is a lag between master and slave message synchronization. Therefore, the author of Redis proposes a RedLock mechanism to solve the above problem. There is a premise for the use of RedLock: no slave library and sentinel mechanism are deployed, but multiple master libraries should be deployed, which is officially recommended as an odd number of 5. As shown below:

Acquiring a lock

If a process wants to acquire a lock in a Redis cluster, the process must be able to obtain the lock through a consensus among the Redis cluster instances. This consensus is usually reached through the Quorum mechanism, i.e. the minority rules the majority.

Therefore, in the redLock algorithm, a process needs to send a SET lock UUID EX 60 NX request to five instances in turn, and record the response results. If more than three (5/2 +1, half +1) instances return the lock success, then the process has successfully obtained the lock. If the lock fails to be obtained, a lock release request (via Lua script) is issued to all redis instances in the cluster.

The above scheme does not consider network delay, process pause, clock drift these three will lead to data consistency problems, and then based on the partial synchronization model of the network to do further security discussion of the algorithm;

1. Consider network latency beyond the upper bound

After requesting a lock, the process synchronously waits for the response result from the REDis server. If the network delay exceeds the upper limit, when the requesting process receives a successful response from the REDis instance, the current lock expires automatically after the time specified in EX. Unbeknownst to the process, the process proceeds with the next step of the business logic and then releases the lock, which causes a similar problem to the redis standalone version – the current process releases the lock of another process; Therefore, when the current process attempts to acquire the lock, redLock first obtains the current timestamp T1. When the client receives the response from the Redis server, it obtains the current timestamp T2 again and determines that T2-T1 > EX Time. The current client considers that the lock is successful only when the inequality is true; otherwise, the lock fails.

2. Consider suspending a process beyond an upper bound

If the process has acquired the lock and GC occurs for a long time, it will cause the current client to release the lock of other clients just like the stand-alone Redis version. The solution is similar, using Lua script to release the lock.

3. Consider clock drift beyond upper bounds

If the client that requests the lock obtains the lock of 60 seconds and processes the service logic, some instances in the Redis cluster make a big jump when synchronizing NTP time, and the locks on some instances expire in advance, two clients may hold the redis lock of the cluster at the same time. Here’s an example:

  1. Client A obtains the successful response of redis cluster instance [1,2,3] when locking for the first time, while [4,5] is locked by other clients. However, according to the principle of more than half, only client A obtains the lock.
  2. At this time, the clock jump occurs in instance 3 and the lock on instance 3 expires in advance. At this time, another client B obtains the successful response of three instances [3,4,5] when requesting lock, so client B also obtains the lock.

In response to this problem, the authors of Redis say that regular operation and maintenance are needed to ensure that machines in the cluster do not have large jumps;

4. RedLock Process of obtaining the lock

In summary, RedLock acquires the lock as follows:

  1. The requesting process records the current timestamp T1.
  2. The requester process successively requests redis instance to acquire the lock, and sets the timeout time for each request (the timeout time is much less than the effective time of the lock). If the requester process receives the response or exceeds the timeout time, it will continue to apply for the lock for the next Redis instance.
  3. If the requesting process gets more than half of the redis cluster instance responses, the current timestamp T2 is obtained and judgedT2-T1 > EX TimeIf not, the lock fails to be obtained.

Release the lock

Releasing locks not only requires Lua script to release locks, but also takes into account that some Redis instances have successfully added locks during the lock process, but the response times out, which is unknown to the current lock holder, so the lock holding process needs to send requests to all Redis instances in the cluster to release locks.

Zookeeper implements distributed locks

Because ZK is based on the full-order broadcast algorithm ZAB, ZK will assign a globally unique increasing ZXID to each process’s request to obtain the lock, that is, the smaller the ZXID is, the earlier the request will reach ZK. And because ZK’s processing of each request will reach a consensus among the cluster nodes by executing ZAB algorithm, the request with the smallest ZXID will get the lock. Zk therefore does not need to rely on additional RedLock mechanisms to implement distributed consensus; This is also an advantage of ZK implementing distributed locking.

Obtain the lock: To obtain the lock, create a temporary node in zK, for example, /exclusive_lock/lock. The process that successfully creates the temporary node obtains the lock, and the process that fails to create the temporary node fails to lock. We can create nodes through open source ZK clients, such as create() method of ZkClient and Curator.

Release the lock: Due to the characteristics of the temporary node, there are two ways to release the lock: 1. The process that obtains the lock deletes the temporary node to release the lock. 2. When the process that obtains the lock hangs, the temporary node will be automatically deleted after it is disconnected from ZK, that is, the lock will be automatically released. This is the second advantage of acquiring locks through ZK – there is no worry about lock expiration; Recall that Redis introduced the timeout mechanism to solve the problem of lock acquisition node downtime, and this timeout caused a number of problematic scenarios.

Read/write lock and optimistic lock can be realized by zK sequence node and Watcher mechanism directly.

Watcher mechanism: Through the Watcher mechanism, clients can register Watcher listeners for child node changes with the following /read_write_lock directory node, so that zK will notify all registered clients of the event when the subnode of this directory is increased or decreased.

Sequential node: ZK maintains the order in which the nodes are created for the child nodes in the sequential node directory and adds the value of the order in the suffix of the node name:

With the above two mechanisms, we can implement read/write locks:

  • First, you need to define a mechanism for distinguishing read and write requests, which can be increased when a node value is writtenRead or WriteTo make a distinction; Because the sequential node suffix size identifies the sequence of requests, as shown in the figure above: indicates zKWe have receivedTwo Read lock requests and one Wrtie lock requests;
  • Then for a process to acquire a read lock request, if at this time/read_write_lockNone in the directoryWriteIs displayed, the node is directly created and the command output is displayed. If the node that acquired the read lock exists at this point, the acquisition fails, but the node is still created under the directory, but needs to beRegister on the write lock nodeWatcherListening to the, when the write lock node is deleted, the original requester process can try to acquire the read lock again.
  • For a write lock request, if at this time/read_write_lockdirectoryWriteIf the node has the smallest surviving suffix, the write lock is successfully obtained. If other nodes exist before the request, the write lock fails to be obtained. You need to register the node whose suffix is not larger than the write request in the directoryWatcherNotification so that when the node is released, the requester can try again to acquire the write lock.

Some problems in implementing distributed locks in ZooKeeper

Of course, there are still many problems in implementing distributed lock through ZK. We also analyze it from the perspective of network delay and process suspension.

  1. Process 1 creates the temporary node/exclusive_lock/lockGot it. Got the lock
  2. Process 1 paused due to machine long GC
  3. Process 1 cannot send heartbeat messages to Zookeeper, and Zookeeper deletes the temporary node
  4. Process 2 creates the temporary node/exclusive_lock/lockGot it. Got the lock
  5. Process 1 machine resumes after GC, it still thinks it holds the lock (causing a conflict)

Therefore, no matter through ZK, Redis or other lock services, there will be a similar problem. That is, after the lock is released due to the process suspension of the service that has acquired the lock, the other process acquires the reverse lock, causing both clients to think that they have the lock.

Zk temporary nodes can be maintained through a daemon thread using a Redisson-like renewal mechanism; However, zK does not release someone else’s lock, so there is no need for a lua-like mechanism to release locks.

Fencing token algorithm

The key of the above problem is that the process still thinks it holds the lock and shares resources after waking up. Because the process in the operating system switch or crash recovery, will only continue to execute in the original sequence of execution, nature can not automatically wake up after re-check whether they still hold the lock;

Therefore, the fencing algorithm proposes to make the shared resource have the ability to reject requests made by processes with expired locks:

  1. The fencing algorithm adds a sequence to the lock so that each time the requesting process successfully obtains the lock, the lock service returns an incrementally increased numbertoken;
  2. And then the request process holds thistokenTo operate shared resources;
  3. Shared resource CachetokenAnd refused totokenClient request with a smaller value.

In this algorithm, for example, the token obtained by process 1 that first obtained the lock = 1; After the process GC, process 2 obtains the token obtained by the lock. Then process 2 requests the shared resource with the token value of 2, and the shared resource caches the token value. Finally, process 1 wakes up and requests the shared resource with the token value of 1. The shared resource detects that 1 is less than 2(current cached) and rejects the request.

This algorithm can solve the above effects of process suspension after holding the lock. However, it is unnecessary to use this algorithm if the process holding the expired lock operates the shared resource without sequential causality.

conclusion

Distributed locks are generally used as mutual exclusions. The above article lists some problems in NPC scenarios and provides corresponding solutions. Consider the sensitivity of the scene itself to the absolute correctness of the data and decide whether to use a more expensive mechanism to ensure it. Of course, RedLock is still not recommended, because it is too expensive. It is recommended to use the master-slave + sentry mechanism to build a Redis cluster.