1. The background

In Java, synchronized and ReentrantLock are commonly used to control concurrent access to resources in multi-threaded environments. However, with the rapid development of distribution, local locking is often not sufficient. In our distributed environment the above locking method will not work. So people in order to achieve the effect of local locking in a distributed environment, but also have their own ways, today let’s talk about the general distributed lock implementation routines.

2. Distributed lock

2.1 Why do you need distributed Locks

Martin Kleppmann, a distributed systems researcher at the University of Cambridge in the United Kingdom, had a heated discussion with Antirez, the father of Redis, about whether RedLock is safe. Martin argues that there are two scenarios in which distributed locking is commonly used:

• Efficiency: Using distributed locks prevents different nodes from doing the same work repeatedly, which wastes resources. For example, different nodes may send multiple messages after the user has paid.
• Correctness: Adding distributed lock can also avoid the occurrence of correctness destruction. If two nodes operate on the same data, for example, multiple node machines operate on the same order in different processes, it may cause errors in the final state of the order, resulting in losses.

2.2 Features of distributed locking

When we have identified the need for distributed locks on different nodes, we need to understand the characteristics of distributed locks:

• Mutual exclusion: Similar to local locks, mutual exclusion is essential, but distributed locks need to ensure that different threads on different nodes are mutually exclusive.
• Reentrancy: The same thread on the same node that acquired the lock can acquire the lock again.
• Lock timeout: Supports lock timeout as local lock, preventing deadlock.
• High efficiency, high availability: Locking and unlocking requires high efficiency and high availability to prevent distributed lock failure. You can increase degradation.
• Support for blocking and non-blocking: Lock and trylock and trylock (long timeOut) are supported as well as ReentrantLock.
• Support for fair and non-fair locks (optional): Fair locks are acquired in the order in which they are requested, whereas non-fair locks are unordered. This is generally less implemented.

2.3 Common Distributed Locks

After we look at some features, we generally implement distributed locking in the following ways:

• MySql
• Zk
• Redis
• Self-developed distributed locks: Google’s Chubby.

The implementation principles of these distributed locks are described below.

3Mysql distributed lock

First of all, let’s talk about the implementation principle of Mysql distributed lock, which is relatively easy to understand, after all, the database and our developers in the usual development is closely related. For distributed locks we can create a lock table:

3.1 the lock ()

We can write an infinite loop to perform the operation of the lock:

Mysqllock.lcok is an SQL file that can be used to reentrant a lock. If there is a value, then we need to compare node_info for the same value. If there is a value, we need to add the value of the count of the reentrant lock. If not, return false. If there is no value, insert the data directly. The pseudocode is as follows:

Note that this section of code needs to add transactions, must ensure that the sequence of operations atomic.

3.2 tryLock () and tryLock (long timeout)

TryLock () is a non-blocking acquisition of the lock and returns immediately if it cannot be obtained.

3.3 unlock ()

So, unlock if the count here is 1 then you can delete it, if it’s greater than 1 then you have to subtract 1.

3.4 the lock timeout

We are likely to encounter our machine nodes hang up and then the lock will not be released, we can start a timer task, by calculating the average time the general we processing tasks, such as 5 ms, then we can be a little bit to expand, when the lock more than 20 ms have not been released we can hang as node and then release it directly.

Mysql 3.5 summary

• Application scenario: Mysql distributed lock is generally applicable to resources that do not exist in the database, if the database exists such as an order, then you can directly lock the data on the row, do not need more cumbersome steps above, such as an order, Select * from order_table where id = ‘XXX’ for update select * from order_table where id = ‘XXX’ for update
• Advantages: Easy to understand, no need to maintain additional third-party middleware (such as Redis,Zk).
• Disadvantages: Although easy to understand, it is complicated to implement. You need to consider lock timeout, add transaction, etc. Performance is limited to databases and is generally low compared to caches. It is not suitable for high concurrency scenarios.

3.6 optimistic locking

In front of us are pessimistic locks, here want to mention the extra optimistic locking, often achieve optimistic locking in our actual project, because we row locking performance overhead is large, we often for some not so competitive, but the need to make sure that we are concurrent sequential use optimistic locking for processing, We can for our table to add a version number field, then after we query a version number, update or delete need to rely on when we check out the version number, whether the current database and query the version number is equal to, if you can perform equal, if it cannot be executed. Such a policy is much like our CAS(Compare And Swap), which is an atomic operation. This way we can avoid the overhead of adding a select * for update row lock.

4. ZooKeeper

ZooKeeper is also a common method to implement distributed locking. Compared with the database, if you don’t know ZooKeeper, it may be more difficult to get started. ZooKeeper is a distributed application coordination service based on the Paxos algorithm. Zk’s data nodes are similar to file directories, so we can use this feature to implement distributed locking. We take a certain resource as a directory, and the nodes under this directory are the clients that we need to acquire the lock. The clients that have not acquired the lock register need to register Watcher with the previous client, which can be shown in the following figure.

4.1 Curator

Exhibit encapsulates the underlying Api for Zookeeper, making it easier to operate Zookeeper, and it encapsulates distributed locking, so you don’t need to implement it yourself.

Curator for reentrant lock (InterProcessMutex), also has realized the non-reentrant lock (InterProcessSemaphoreMutex). Read and write locks are also implemented in reentrant locks.

4.2 InterProcessMutex

InterProcessMutex is a reentrant lock implemented by The Curator. We can implement our reentrant lock with the following code:

We use acuire to lock and release to unlock.

The lock process is as follows:

1. First reentrant determine: the reentrant lock here are recorded in the ConcurrentMap < Thread, LockData > threadData this Map, if threadData get (currentThread) is a value then proved to be reentrant lock, And then the record is going to increase by 1. Mysql can also be optimized in this way, without the need for the count field value. Maintaining this locally can improve performance.
2. Then create a node in our resource directory: for example, create a /0000000002 node here that needs to be set to EPHEMERAL_SEQUENTIAL and ordered.
3. Obtain all child nodes in the current directory and determine whether your own node is the first child node.
4. If it is the first, then the lock is acquired and can be returned.
5. If it is not the first, it proves that someone has already acquired the lock, so you need to acquire the node before your own. /0000000002 is preceded by /0000000001, which we get and register with Watcher(Watcher calls object.notifyAll() to unblock).
6. Object.wait (timeout) or object.wait(): Block to wait this corresponds to our watcher in step 5.

The specific process of unlocking:

1. First of all can reenter the lock of the judgment: if there can reenter the lock only need to reduce the number of 1, minus 1 after the number of lock is 0 to continue the following steps, not 0 direct return.
2. Example Delete the current node.
3. Delete reentrant data from threadDataMap.

4.3 read-write lock

Curator provides a read-write lock, its implementation class is InterProcessReadWriteLock, every node prefix here:

private static final String READ_LOCK_NAME  = "__READ__";
private static final String WRITE_LOCK_NAME = "__WRIT__";
Copy the code

If a read lock is preceded by a write lock, you need to register the watcher with the nearest write lock. The logic of write locking remains the same as we analyzed in 4.2.

4.4 the lock timeout

Zookeeper does not need to configure the lock timeout. Because we set the node as a temporary node, each of our machines maintains a ZK session, through which ZK can determine whether the machine breaks down. If our machine goes down, the corresponding temporary node will be deleted, so we don’t need to care about the lock timeout.

4.5 the ZK summary

• Advantage :ZK can do not need to care about the lock timeout time, implement ready-made third-party package, more convenient, and support read and write lock, ZK lock will be in accordance with the lock order, so it is fair lock. High availability of ZK clusters is guaranteed.
• Disadvantages :ZK requires additional maintenance, which increases maintenance costs, and its performance is not much different from that of Mysql. And developers need to know what ZK is.

5.Redis

We search distributed lock on the Internet, I am afraid the most implementation is Redis, Redis because of its good performance, easy to achieve so that a lot of people are very fond of it.

5.1 Simple implementation of Redis distributed lock

Those familiar with Redis must be familiar with the setNx(Set if not exist) method. If it does not exist, update it. It can be used well to implement our distributed lock. To lock a resource all we need to do is

setNx resourceName value
Copy the code

The problem here is that if the machine goes down, the lock will not be released, so the expiration time will be added. Adding the expiration time needs to be the same atomic operation as setNx. Before Reddis2.8 we need to use the Lua script to do this. After Redis 2.8, however, Redis supports nX and EX operations being the same atomic operation.

set resourceName value ex 5 nx
Copy the code

5.2 Redission

All Javaers know about Jedis. Jedis is the Java implementation of Redis, and its API provides comprehensive support for Redis commands. Redission is also a client of Redis, which is simpler than Jedis. Jedis simply uses blocking I/O to interact with Redis, and Redission supports non-blocking I/O through Netty. The latest version of Jedis 2.9.0 has not been updated in 2016 for nearly 3 years, while the latest version of Redission was updated in October 2018.

Redission encapsulates the realization of the Lock, it inherited the Java. Util. Concurrent. The locks, Lock interfaces, let’s go like our local Lock operation operation Redission Lock, the following introduce how to realize the distributed Lock.

Redission not only provides some of Java’s own methods (Lock,tryLock), but also provides asynchronous locking, which is easier for asynchronous programming. TryLock = tryLock = tryLock = tryLock = tryLock = tryLock = tryLock = tryLock = tryLock

1. Attempt to lock: The first attempt to lock is made. Since the guarantee operation is atomic, only the lua script can be used. The lua script is as follows:
   

   

   As you can see, it does not use our sexNx to operate. Instead, it uses the hash structure. Each of our resources to be locked can be regarded as a HashMap, and the node information of the locked resource is Key, and the number of locks is value. In this way, the reentrant effect can be well realized. The reentrant lock can be implemented only by adding 1 to the value. Of course, you can also optimize with the local count we talked about earlier.

2. If the attempt fails, determine whether the lock timed out. If it timed out, return false.
3. If the lock fails and there is no timeout, you need to subscribe to a channel named Redisson_LOCK__channel +lockName that will subscribe to the unlock message and then block until it times out or there is a unlock message.
4. Retry steps 1, 2, and 3 until the lock is acquired or one of the steps times out.

For us, the unlock method is simple and is also unlocked by the lua script. If it is a reentrable lock, we just subtract 1. If unlocked from a non-locking thread, the unlock fails.

Redission also has the implementation of fair lock, for fair lock it uses the list structure and hashset structure respectively to save our queued nodes, and our node expiration time, with these two data structures to help us achieve fair lock, here will not expand the introduction, interested can reference the source code.

5.3 RedLock

Let’s imagine A scenario where machine A applies for A lock, and if the Redis main machine is down and the slave machine is not synchronized to the lock, then machine B applies for the lock again. In order to solve this problem, Redis author proposed RedLock RedLock algorithm, RedLock is also implemented in Reddission.

Through the above code, we need to implement multiple Redis clusters, and then lock and unlock the red lock. The specific steps are as follows:

1. Firstly, rLocks of multiple Redis clusters are generated and constructed into RedLocks.
2. Lock the three clusters in turn, and the locking process is the same as in 5.2.
3. If the locking fails in the process of cyclic locking, it is necessary to determine whether the number of locking failures exceeds the maximum value. The maximum value here is based on the number of clusters. For example, if there are three clusters, only one failure is allowed, and if there are five clusters, only two failures are allowed.
4. In the process of locking, we need to determine whether the locking timeout. It is possible that we can only set the locking to be used for 3ms, but the first cluster has already consumed 3ms. Then it counts as a lock failure.
5. If the lock fails in step 3 or 4, the lock will be unlocked, and all clusters will be unlocked at the same time.

It can be seen that the basic principle of RedLock is to use multiple Redis clusters and use most of the clusters to lock successfully, so as to reduce the probability of distributed lock problems caused by the failure of a certain Cluster in Redis.

Redis 5.4 summary

• Advantages: Simple implementation for Redis, better performance than ZK and Mysql. If you do not need particularly complex requirements, then you can use setNx to implement, if you need complex requirements then you can use or borrow Redission. For more demanding scenarios, you can use RedLock.
• Disadvantages: Redis clusters need to be maintained, and more clusters need to be maintained to implement RedLock.

6. Security of distributed locks

We’ve talked about red locks above, but Martin Kleppmann says they’re still not safe. As for the points that Martin refuted, I think it is not limited to RedLock, and all the algorithms mentioned above have this problem. Let’s discuss these problems below:

• GC pause: If you are familiar with Java, a STW(stop-the-world) occurs during GC. For example, a CMS garbage collector has two phases of STW to prevent the reference from continuing to change. The following diagram (quoted in Martin’s rebuttal to Redlock) is possible:
  

  

  Client1 has acquired the lock and set the timeout period for the lock, but client1 has STW, which takes a long time to release the distributed lock, client2 has acquired the lock, and client1 has restored the lock, then client1 and 2 have acquired the lock at the same time. This is where distributed lock insecurity comes in. This is not limited to RedLock, we have the same problem with ZK and Mysql.

• Clock jump: For Redis server, if the time of the lock jump, then certainly affect our lock expiration time, then our lock expiration time is not what we expected, client1 and Client2 also appear to acquire the same lock, then there will be unsafe, this will also appear for Mysql. However, since ZK does not set the expiration time, the jump will not be affected.
• Long network I/O: This problem is similar to our GC STW, that is, after we acquire the lock, we make a network call, the call time may be longer than our lock expiration time, then there will be unsafe issues, Mysql also has this problem, ZK will not have this problem.

There has been a lot of discussion about these three issues, including the Redis author.

6.1 the STW GC

For this problem, you can see that almost all of them will have problems. Martin gives a solution. For ZK, he will generate an increment sequence, so when we actually operate on the resource, we need to determine whether the current sequence is the latest, similar to our optimistic locking. Of course, the Redis author argues that since you can generate an increment sequence, you don’t need to lock at all, so you can follow a solution similar to Mysql optimistic locking.

In my opinion, this solution increases the complexity. When we operate on resources, we need to add the determination of whether the serial number is up to date. No matter what method we use, it will increase the complexity.

6.2 Clock Jump Occurs

Martin thinks that the reason why RedLock is insecure is also because of clock jump, because lock expiration is strongly dependent on time, but ZK does not depend on time, it depends on the Session of each node. Redis author also gives the answer: for time jump there are artificial adjustment and NTP automatic adjustment.

• Artificial adjustment: the effect of artificial adjustment can be completely artificial adjustment, this is in the controllable.
• NTP automatic adjustment: this can be optimized to control the jump time within the controllable range, although it will jump, but it is completely acceptable.

6.3 Long-term Network I/O

This piece isn’t focus their discussion, I feel, for the problem of optimization can control network call timeout, all network call timeout, then we lock the expiration time should be greater than this time, actually, of course, also can be invoked by optimizing the network such as serial to parallel, asynchronous, etc. Refer to my two articles: Parallelization – your high concurrency killer, and asynchrony – your high concurrency killer

7. Some optimizations by Chubby

If you search for ZK, you’ll find that they all write that ZK is an open source implementation of Chubby, which works like ZK internally. But Chubby’s positioning of distributed locks is a little different than ZK’s. Chubby also uses the above self-incrementing sequence scheme to solve the problem of distributed insecurity, but he provides a variety of verification methods:

• CheckSequencer() : Call Chubby’s API to check if the sequence number is valid at this point.
• Access the resource server check to determine the current resource server’s latest serial number and the size of our serial number.
• Lock-delay: In order to prevent the logic we verify from intrudinginto our resource server, this provides a way to not release the lock immediately when a client loses contact, but to prevent other clients from taking the lock for a certain amount of time (default: 1min), thus giving a buffer until STW recovers. If our GC STW time is longer than 1min then you should check your program, not suspect your distributed locks.

Nodule 8.

This article focuses on the implementation of a variety of distributed locking methods, as well as some of their advantages and disadvantages. Finally, I also talked about the security of distributed lock. Different businesses need different security levels. We need to select the most suitable solution according to our own business scenarios and through different dimensional analysis.

Finally, this article is included in JGrowing, a comprehensive, excellent, community-built Java learning route, if you want to participate in the maintenance of open source projects, you can build together, github :github.com/javagrowing… A little star, please.

Finally, I would like to make an advertisement. If you think this article has something for you, you can follow my technical official account or join my technical communication group for more technical communication. Your attention and retweet are the greatest support for me, O(∩_∩)O.