What is distributed locking?

Today, I’m going to talk about distributed locks.

First of all, let’s talk about what distributed lock is. When we are in the business scenes of placing orders to reduce inventory, snatching tickets, choosing courses and snatching red envelopes, if there is no lock control here, it will lead to serious problems.

For those of you who have learned about multithreading, you can use the synchronized keyword or the ReentrantLock class in JUC to prevent multiple threads from executing the same code at the same time. Synchronized and ReentrantLock don’t work, so you need a global lock to replace synchronized and ReentrantLock in JAVA.

There are three popular implementation methods of distributed lock, which are based on cache Redis, zK temporary sequence node and database row lock. Let’s start by building the lock using the setnx command in Jedis.

Jedis writing

The idea of using Redis for distributed locking is to set a value in Redis to indicate that a lock is added, and then delete the key when the lock is released. The idea is very simple, but in the process of using to avoid some pits, let’s first look at the lock code:

/** * try to obtain distributed lock ** @param jedis Redis client * @param lockKey lock * @param requestId requestId * @param expireTime expiration time * @return*/ public static Boolean tryGetDistributedLock(Jedis Jedis, String lockKey, String requestId, int expireTime) { //setMultiple parameters are supported NX (not exist) XX (exist) EX (seconds) PX (million seconds) String result = jedis. Set (lockKey, requestId,"NX"."EX", expireTime);
        if (LOCK_SUCCESS.equals(result)) {
            return true;
        }
        return false;
    }
Copy the code

This code is very simple, mainly under the said here with command is SET key value [EX seconds | PX milliseconds] [NX | XX] [KEEPTTL], without using SETNX + EXPIRE command, The reason is that SETNX+EXPIRE is two commands that cannot guarantee atomicity, whereas SET is an atomic operation.

So why is the timeout set here?

The reason is that when a client acquires a lock and hangs during the execution of a task, without the ability to explicitly release the lock, the resource will be locked forever, resulting in a deadlock, so a timeout must be set.

The lock release code is as follows:

/** * release distributed lock ** @param jedis Redis client * @param lockKey lock * @param requestId requestId, the name of the current worker thread * @return*/ public static Boolean releaseDistributedLock(Jedis Jedis, String lockKey, String requestId) {String script ="if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end";
        Object result = jedis.eval(script, Collections.singletonList(lockKey), Collections.singletonList(requestId));
        if (RELEASE_SUCCESS.equals(result)) {
            return true;
        }
        return false;
    }
Copy the code

If A lock is added by A thread and B is added by A thread, then the thread will unlock the lock. If A lock is added by B thread, the thread will unlock the lock. Thread.currentthread ().getid (), and check whether it is the currentThread.

The second point is that authentication and lock release are two separate operations, not atomic. How to solve this problem? If redis.call(‘get’, KEYS[1]) == ARGV[1] then returnRedis. call(‘del’, KEYS[1]) else return 0 end.

Redisson writing

Redisson is one of Java’s Redis clients and provides apis to facilitate Redis operations. But Redisson this client can be a bit much, let’s open the website, see https://github.com/redisson/redisson/wiki/%E7%9B%AE%E5%BD%95

Redisson is different from Jedis in that it is not a pure Redis client, but a distributed service based on the Redis implementation. We can see that there is also a class name under the JUC package. Redisson helped us create a distributed version. So AtomicLong, just RedissonAtomicLong.

Locking is just the tip of the iceberg, and it supports master-slave, sentry, cluster, and of course, single-node.

Redisson provides a much simpler implementation of distributed locking. Let’s take a look at its usage. It’s quite simple, two lines of code, much simpler than Jedis, and Jedis has already encapsulated all the issues we need to consider.

Let’s see, there are several ways to get a lock, there’s a fair lock, there’s a read-write lock, and we’re using redissonClient.getLock, which is a reentrant lock.

Now LET me start the program

Open the Redis Desktop Manager tool to see exactly what it stores. Key is the lock name jackxu, field is the thread name, and value is 1.

Small partners may feel that I am in a pack of nonsense, it doesn’t matter, we go in to see its source code is specific implementation.

Click on the tryAcquire() method of the tryLock() method, go to ->tryAcquireAsync(), and go to ->tryLockInnerAsync().

Now LET me pull up this Lua script and analyze it. It’s very simple.

// KEYS[1] Lock name updateAccount // ARGV[1] Key expiration time 10000ms // ARGV[2] Thread name // Lock name does not existif (redis.call('exists', KEYS[1]) == 0) then// Create onehash, key= lock name, field= thread name, value=1 redis.call('hset', KEYS[1], ARGV[2], 1); / / sethashRedis. Call ('pexpire', KEYS[1], ARGV[1]);
returnnil; end; // Lock name exists, check whether the current thread holds the lockif (redis.call('hexists', KEYS[1], ARGV[2]) == 1) then// If yes, value+1, reentrant times +1 redis.call('hincrby', KEYS[1], ARGV[2], 1); Redis.call (redis.call('pexpire', KEYS[1], ARGV[1]);
returnnil; end; // The lock exists, but is not held by the current thread.return redis.call('pttl', KEYS[1]);
Copy the code

UnlockInnerAsync () in unlock() releases the lock, again via Lua script.

Redisson_lock__channel :{updateAccount} // ARGV[1] release lock message 0 // ARGV[2] Lock release time 10000 // ARGV[3] Thread name // Lock does not exist (expired or released)if (redis.call('exists', KEYS[1]) == 0) then// Publish a message that the lock has been released'publish', KEYS[2], ARGV[1]);
return1; end; // The lock exists, but not by the current threadif (redis.call('hexists', KEYS[1], ARGV[3]) == 0) then
returnnil; end; // Reentrant count -1local counter = redis.call('hincrby', KEYS[1], ARGV[3], -1); If -1 is greater than 0, the thread is holding the lock and has other tasks to performif (counter > 0) then// Reset the lock expiration time redis.call('pexpire', KEYS[1], ARGV[2]);
return 0;
elseRedis.call (redis.call());'del', KEYS[1]); Redis.call ()'publish', KEYS[2], ARGV[1]);
return1; end; // Otherwise return nilreturn nil;
Copy the code

After watching it in action, we found that it really works as silky as ReentrantLock in the JDK.

RedLock

RedLock is literally translated from Chinese, it is called RedLock. Redlock is not a tool, but a distributed lock algorithm officially proposed by Redis.

We know that there is a single point of problem with single machine deployment, as long as Redis fails, locking will not work. If the master-slave mode is adopted, only one node is locked during the locking process. Even if sentinel is used for high availability, if the master node fails and a master/slave switchover occurs, the lock loss may occur.

Based on the above considerations, Antirez, the author of Redis, also considered this problem and proposed an algorithm of RedLock.

I have drawn a diagram here in which these five instances are deployed independently without a master-slave relationship. They are the five master nodes.

Obtain a lock by following these steps:

  • Gets the current timestamp in milliseconds
  • Take turns trying to create locks on each master node with short expiration times, typically tens of milliseconds
  • Try to create a lock on most nodes, e.g., 3 nodes for 5 (n / 2 +1)
  • The client calculates the lock establishment time. If the lock establishment time is shorter than the timeout period, the lock establishment is successful
  • If the lock fails, then the lock is removed in turn
  • Whenever someone else sets up a distributed lock, you have to keep polling to try and get it

But this algorithm is quite controversial, there may be a lot of problems, can not guarantee the lock process must be correct. Martin Kleppmann challenged the algorithm, and Antirez responded. One is a highly qualified distributed architect, the other is the father of Redis, and this is the famous fight between the gods of red lock.

Finally, the Redisson website also provides how to use redlock, a few lines of code, still very smooth, interested friends can take a look.

They are writing

Before introducing zooKeeper’s mechanism for implementing distributed locks, let’s take a quick look at what ZK is: A centralized service that provides configuration management, distributed collaboration, and naming.

The model looks like this: it contains a series of nodes, called ZNodes, which are like file systems, each znode represents a directory, and zNodes have some features, which we can classify into four categories:

  • Persistent node (ZK disconnection node still exists)
  • Persistent sequential nodes (/lock/node-0000000000 for the first child created, /lock/ Node-0000000001 for the next, and so on)
  • Temporary node (node deleted after client disconnects)
  • Temporary sequence node

The ZooKeeper distributed lock uses temporary sequential nodes, so let’s see how it works diagramatically.

1. Obtain the lock

First, create a persistent node ParentLock in Zookeeper. When the first client wants to acquire the lock, it creates a temporary sequential node Lock1 under the ParentLock node.

Client1 then looks for all temporary order nodes under ParentLock and sorts them to determine if Lock1 is the highest order node it has created. If it is the first node, the lock is successfully acquired.

If another client comes to acquire the lock, create a temporary sequential node Lock2 under ParentLock.

Client2 finds all temporary order nodes under ParentLock and sorts them to determine if Lock2 is the first node in the order.

Client2 then registers Watcher with Lock1, the node just ahead of it, to listen for the existence of the Lock1 node. This means Client2 has failed to grab the lock and has entered a wait state.

If another client comes to acquire the lock, create a temporary sequential node Lock3 in ParentLock.

Client3 searches for all temporary order nodes under ParentLock and sorts them to determine whether Lock3 is the first node in the order.

Client3 then registers Watcher with Lock2, the node just ahead of it, to listen for the existence of the Lock2 node. This means Client3 has also failed to grab the lock and has entered a wait state.

So Client1 gets the lock, Client2 listens on Lock1, and Client3 listens on Lock2. It forms a waiting queue, like in Java already rely on AQS (AbstractQueuedSynchronizer).

2. Release the lock

There are two types of lock release:

1) When the task is completed, the client displays release

When the task completes, Client1 displays an instruction that calls the delete node Lock1.

2) The client crashes during the task execution

If the Client1 that obtains the lock crashes during the task execution, it will disconnect from the Zookeeper server. Depending on the nature of temporary nodes, the associated node Lock1 is automatically deleted accordingly.

Since Client2 is always listening for Lock1, it is notified immediately when a Lock1 node is deleted. Client2 checks all nodes under ParentLock again to see if Lock2 is currently the smallest node. If it is the smallest, Client2 naturally acquires the lock.

Similarly, if Client2 also deletes node Lock2 due to task completion or node crash, then Client3 will be notified.

Client3 finally succeeded in obtaining the lock.

3, Curator

In Apache open source framework Apache Curator includes the implementation of Zookeeper distributed lock.

Github.com/apache/cura…

It is also very simple to use, as follows:

We looked at the next still silky, I will not analyze the source.

conclusion

Zookeeper is designed for distributed coordination, strong consistency and robust locking. If you can’t get the lock, you just need to add a listener instead of polling all the time. Disadvantages: In the case of high request and high concurrency, the system frantically locks and releases locks, and finally ZK can not bear so much pressure that there may be a risk of downtime.

Here is a brief mention of the reason why ZK lock performance is lower than Redis:

Each write request can only be requested by the Leader. The leader will broadcast the write request to all the flowers. If all the flowers succeed, the write request will be submitted to the Leader. When locking, it is a write request. When there are a lot of write requests, ZK will be under a lot of pressure, resulting in slow server response.

Redis lock is simple to implement, simple to understand logic, good performance, and can support high concurrency lock acquisition and release operations.

Disadvantages: Redis is prone to single point of failure, cluster deployment, not strong consistency, locking is not robust enough; The key expiration time is not specified and can only be adjusted based on the actual situation. You need to constantly try to get the lock yourself, which costs performance.

Finally, both Redis and ZooKeeper should meet the characteristics of distributed locks:

  • Reentrant (a thread that has acquired a lock does not need to acquire it again during execution)
  • Automatically delete exceptions or timeout to avoid deadlocks
  • Mutually exclusive (can only be accessed by a single thread at a time in a distributed environment)
  • High performance, high availability and fault tolerance mechanism in distributed environment

Author: jack_xu

Links: juejin. Cn/post / 684490…

Wenyuan network, only for the use of learning, if there is infringement please contact delete.

I’ve compiled the interview questions and answers in PDF files, as well as a set of learning materials covering, but not limited to, the Java Virtual Machine, the Spring framework, Java threads, data structures, design patterns and more.

Follow the public account “Java Circle” for information, as well as quality articles delivered daily.