Source code here: github.com/xbox1994/di…

Introduction to the

Distributed lock is very common in distributed systems. For example, when operating public resources, such as selling tickets, only one node can sell tickets for a specific seat at the same time. For example, avoid the large number of requests to access the database caused by cache invalidation

design

This is very much like an interview question: How do you implement a distributed lock? In the introduction, there are basically some requirements for this distributed tool, you can not rush to read the answers below, think for yourself how distributed lock should be implemented?

First we need a simple answer routine: requirements analysis, system design, implementation, shortcomings

Demand analysis

  1. It can be applied in highly concurrent distributed systems
  2. The basic features of locks need to be implemented: once a lock is allocated, no other node can access the resources covered by the lock. Failure mechanisms avoid infinite duration locks and deadlocks
  3. Further advanced locking features and similar JUC concurrency tools are better: reentrant, blocking vs. non-blocking, fair vs. non-fair, JUC concurrency tools (Semaphore, CountDownLatch, CyclicBarrier)

The system design

Conversion to design is the following requirements:

  1. The locking and unlocking process needs to be high-performance and atomic
  2. Lock state operations need to be performed on a common platform accessible to a distributed node

Therefore, we analyze that the system should be composed of lock state storage module, connection pool module connecting storage module, lock internal logic module

Lock status storage module

There are three common implementations of distributed lock storage, because the conditions for implementing locks can be met: high-performance lock unlocking, atomicity of operation, and a common platform accessible to different nodes in a distributed system:

  1. Database (with primary key unique rule, MySQL row lock)
  2. NX and EX parameters based on Redis
  3. Zookeeper Temporary ordered node

Because the lock is often in the case of high concurrency will use the distributed control tool, so the use of database implementation will cause a certain pressure on the database, connection pool overflow problem, so do not recommend database implementation; We also need to maintain the Zookeeper cluster, which is quite complex to implement. If not the original system depends on Zookeeper, and the pressure is not high. Zookeeper is generally not used to implement distributed locks. So cache implementation of distributed locks is relatively common, because the cache is lightweight, cache response fast, high throughput, and automatic invalidation mechanism to ensure that the lock must be released.

Connection pool module

Can use JedisPool implementation, if the late performance is not good, can consider referring to HikariCP implementation

Locks internal logic modules

  • Basic functions: lock, unlock, timeout release
  • Advanced features: reentrant, blocking and non-blocking, fair and unfair, JUC concurrency tool features

implementation

Storage module using Redis, connection pool module temporarily using JedisPool, lock internal logic will start from the basic function, gradually realize advanced functions, the following is the specific ideas and code of various functions to achieve.

Lock, timeout release

NX is an atomic operation provided by Redis. If the specified key exists, NX fails, and if it does not, the set operation returns success. We can use this to implement a distributed lock. The main idea is that set succeeds in obtaining the lock, set fails in obtaining the lock, and retry after failure. This, combined with the EX parameter, causes the key to be automatically deleted after a timeout.

The following is a blocking lock operation. Remove the loop and return the result to write a non-blocking lock:


public void lock(String key, String request, int timeout) throws InterruptedException { Jedis jedis = jedisPool.getResource(); while (timeout >= 0) { String result = jedis.set(LOCK_PREFIX + key, request, SET_IF_NOT_EXIST, SET_WITH_EXPIRE_TIME, DEFAULT_EXPIRE_TIME); if (LOCK_MSG.equals(result)) { jedis.close(); return; } Thread.sleep(DEFAULT_SLEEP_TIME); timeout -= DEFAULT_SLEEP_TIME; }}Copy the code

However, the timeout parameter can cause a problem. If the timeout is exceeded but the business is not finished, it can cause concurrency problems and other processes will execute the business code. How to improve this is described below.

unlock

The most common unlock code is to use the jedis.del() method to remove the lock. This method unlocks the lock without determining who owns it, so that any client can unlock the lock at any time, even if it doesn’t own it.

For example, client A locks client A after A period of time. Before jedis.del() is executed, the lock suddenly expires. Then client B tries to lock client B successfully, and then client A executes del() to unlock client B.

So we need an atomic way to unlock the lock and determine if the lock is our own. Since Lua scripts are atomic in Redis, they can be written as follows:


public boolean unlock(String key, String value) {
    Jedis jedis = jedisPool.getResource();

    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(LOCK_PREFIX + key), Collections.singletonList(value));

    jedis.close();
    return UNLOCK_MSG.equals(result);
}
Copy the code

Let’s use the test shuttle

SRC /test/ Java; SRC /test/ Java; SRC /test/ Java; There is no way to test the performance of a real Redis connection, and no way to experience the intense thrill of being locked, so this project will focus on integration testing. If you want to try unit testing with mocks, check out this article.

The integration test will rely on an instance of Redis. To avoid having to build a local Redis to run the test, I used an EmbeddedRedis tool and the code below to create a New instance of Redis. The code can be set to EmbeddedRedis class. Also, is it nice to use Spring for integration testing? It also provides an example of integrating Spring.


@Configuration public class EmbeddedRedis implements ApplicationRunner { private static RedisServer redisServer; @PreDestroy public void stopRedis() { redisServer.stop(); } @Override public void run(ApplicationArguments applicationArguments) { redisServer = RedisServer. Builder (). Setting (" bind "127.0.0.1). Setting (" requirepass test"). The build (); redisServer.start(); }}Copy the code

For consider concurrent code under test is more difficult and more difficult to achieve the purpose of testing code quality because of test cases using multithreading environment, can not complete by and hard to reproduce, but the objective of the distributed lock is a relatively simple concurrent scene, so I’ll try to ensure testing is meaningful.

My first test case is to test the mutual exclusion of the lock. If A can’t get the lock immediately after B can’t get it:


@Test public void shouldWaitWhenOneUsingLockAndTheOtherOneWantToUse() throws InterruptedException { Thread t = new Thread(() -> { try { redisLock.lock(lock1Key, UUID.randomUUID().toString()); } catch (InterruptedException e) { e.printStackTrace(); }}); t.start(); t.join(); long startTime = System.currentTimeMillis(); redisLock.lock(lock1Key, UUID.randomUUID().toString(), 3000); assertThat(System.currentTimeMillis() - startTime).isBetween(2500L, 3500L); }Copy the code

This tests only the mutual exclusion of the lock operation, but does not test whether the unlock succeeds or whether the original process will continue after the unlock, so you can see how the testLockAndUnlock method tests. Don’t think it’s easy to write a test. It’s not easy to think through the test scenarios, design the test scenarios and implement them. However, future tests will not be written separately, after all, this article will focus on the implementation of distributed locks.

Concurrency problems caused by timeout release

Problem: If the timeout period is set after USER A obtains the lock, but the service execution duration exceeds the timeout period, user A is still executing the service but the lock is released. In this case, other processes will acquire the lock and execute the same service. In this case, the distributed lock is meaningless because of concurrency.

If you said I could pass the key under the expiration time judgment tasks have completed, if you don’t have it automatically extend the expiration time, then can solve the problem of concurrency, but timeout value has lost its meaning, I set the timeout value is to want to automatically releases the lock timeout, avoid other processes is blocked. Therefore, I think the best solution is to notify the server to stop the timeout task when the lock times out, but combined with the message notification mechanism of Redis is inevitably too heavy; Or let the business code check for timeouts, but doesn’t the tool just make the business implementer pay more attention to the business?

So this problem, distributed lock Redis implementation is not reliable

Concurrency problems caused by a single point of failure

Set up a master/slave replication architecture, but some data will still be lost before synchronization due to the failure of the master node. Therefore, it is recommended to have a multi-master architecture, with N independent master servers, and the client will send lock operations to all servers.

Where we can continue to optimize

  • Semaphore, CountDownLatch, fair and unfair lock, and read-write lock are similar to those in JUC. For details, see Redisson
  • Provides multi-master configuration and lock unlocking
  • Use subscription unlock messages with Semaphore insteadThread.sleep()To avoid wasting time, refer to the lockInterruptibly method of RedissonLock in Redisson

reference

Redisson source www.jianshu.com/p/c2b4aa7a1… Crossoverjie. Top / 2018/03/29 /… www.jianshu.com/p/de67ae50f… www.cnblogs.com/linjiqin/p/…

okokokokok

Recently summarized some knowledge points related to Java interview, interested friends can maintain together ~ address: github.com/xbox1994/20…