Shulou(Shulou.com)06/01 Report--

Extended reading: Redis chat (1): building a knowledge graph

Redis project (2): exploring the underlying layer of Redis data structure

Recently, distributed issues have been widely mentioned, such as distributed transactions, distributed frameworks, ZooKeeper, SpringCloud and so on. This article first reviews the concept of locks, then introduces distributed locks, and how to use Redis to implement distributed locks.

First, the basic understanding of locks

First of all, let's review the concept of locks in our work and study.

Why should we talk about locks first and then distributed locks?

We all know that the role of locks is to solve the thread safety problems caused by multithreaded access to shared resources, but locks are not often used in daily life. some friends may not be very clear about the concept and basic use of locks, so let's first look at locks, and then introduce distributed locks in depth.

Through a small case of ticket sales, for example, people go to grab dota2 ti9 tickets, what will happen if they are not locked? The code is as follows:

Package Thread;import java.util.concurrent.TimeUnit;public class Ticket {/ * * initial inventory * * / Integer ticketNum = 8; public void reduce (int num) {/ / determine whether the inventory is sufficient if ((ticketNum-num) > = 0) {try {TimeUnit.MILLISECONDS.sleep } catch (InterruptedException e) {e.printStackTrace ();} ticketNum-= num; System.out.println (Thread.currentThread () .getName () + "successfully sold" + num + "ticket, remaining" + ticketNum + "ticket") } else {System.err.println (Thread.currentThread (). GetName () + "not sold" + num + "ticket", remaining "+ ticketNum +" ticket ");} public static void main (String [] args) throws InterruptedException {Ticket ticket = new Ticket () / / start 10 threads to grab tickets. According to theory, there should be two people who can't get tickets for (int iTuno ticket.reduce (1), "user" + (I + 1)). Start ();} Thread.sleep (1000L);}}

Code analysis: there are 8 ti9 tickets, 10 threads are set (that is, 10 people are simulated) to concurrently grab tickets, if the grab is successful, it shows success, and if the grab fails, it shows failure. In theory, there should be 8 successful robbers and 2 failed robbers. Let's take a look at the running results:

We found that the running results were not consistent with the expected situation, and even 10 people bought tickets, that is to say, there was a thread safety problem, so what is the cause?

The reason is that there is a time difference between multiple threads.

As shown in the figure, there is only one ticket left, but the margin read by both threads is 1, which means that Thread B has successfully grabbed the ticket before Thread A changes its inventory.

How to solve it? As you all know, just add the synchronized keyword, and when one thread performs the reduce method, the other threads block in the waiting queue, so that multiple threads do not compete for shared variables.

For instance

For example, when we go to the gym, if many people use the same machine and run on the same treadmill at the same time, there will be a lot of problems and people will fight like crazy. If we add a lock at the door of the gym, only those who have the key to the lock can go in for exercise, and others can wait outside the door, so as to avoid competition for fitness equipment. The code is as follows:

Public synchronized void reduce (int num) {/ / determine whether the inventory is sufficient if ((ticketNum-num) > = 0) {try {TimeUnit.MILLISECONDS.sleep (200);} catch (InterruptedException e) {e.printStackTrace ();} ticketNum-= num System.out.println (Thread.currentThread (). GetName () + "successfully sold" + num + "ticket", remaining "+ ticketNum +" ticket);} else {System.err.println (Thread.currentThread (). GetName () + "not sold" + num + "ticket", remaining "+ ticketNum +" ticket ");}}

Running result:

Sure enough, as a result, two people failed to get the tickets, and it seems that our goal has been achieved.

Second, lock performance optimization 2.1 shortens lock holding time

In fact, according to our understanding of daily life, it is impossible for only one person to exercise in the whole gym. So we just need to lock a certain machine, for example, one person is running, the other person can do other sports.

For the ticketing system, we only need to lock the code of the inventory modification operation, and other codes can still be carried out in parallel, which will greatly reduce the holding time of the lock. The code is modified as follows:

Public void reduceByLock (int num) {boolean flag = false; synchronized (ticketNum) {if ((ticketNum-num) > = 0) {ticketNum-= num; flag = true }} if (flag) {System.out.println (Thread.currentThread (). GetName () + "successfully sold" + num + "ticket, remaining" + ticketNum + "ticket") } else {System.err.println (Thread.currentThread (). GetName () + "not sold" + num + "ticket", remaining "+ ticketNum +" ticket ");} if (ticketNum = = 0) {System.out.println (" time consuming "+ (System.currentTimeMillis ()-startTime) +" millisecond ");}}

The purpose of this is to make full use of the resources of cpu and improve the efficiency of code execution.

Here we print the time in two ways:

Public synchronized void reduce (int num) {/ / determine whether the inventory is sufficient if ((ticketNum-num) > = 0) {try {TimeUnit.MILLISECONDS.sleep (200);} catch (InterruptedException e) {e.printStackTrace ();} ticketNum-= num If (ticketNum = = 0) {System.out.println ("time consuming" + (System.currentTimeMillis ()-startTime) + "millisecond");} System.out.println (Thread.currentThread () .getName () + "successfully sold" + num + "ticket", remaining "+ ticketNum +" ticket ") } else {System.err.println (Thread.currentThread (). GetName () + "not sold" + num + "Zhang, remaining" + ticketNum + "ticket");}}

Sure enough, locking only part of the code will greatly improve the efficiency of code execution.

Therefore, after solving the problem of thread safety, we also need to consider the efficiency of code execution after locking.

2.2 reduce the granularity of locks

For example, there are two movies, the recently released magic boy Nathan and Spider-Man. We simulate a process of paying for a purchase, make the method wait, and add an await method of CountDownLatch. The result is as follows:

Package Thread;import java.util.concurrent.CountDownLatch;public class Movie {private final CountDownLatch latch = new CountDownLatch (1); / / Boy private Integer babyTickets = 20; / / Spider-Man private Integer spiderTickets = 100; public synchronized void showBabyTickets () throws InterruptedException {System.out.println ("the remaining number of votes for Marvel Boy is:" + babyTickets); / / purchase latch.await () } public synchronized void showSpiderTickets () throws InterruptedException {System.out.println ("Spider-Man's remaining votes are:" + spiderTickets); / / purchase} public static void main (String [] args) {Movie movie = new Movie (); new Thread (()-> {try {movie.showBabyTickets ()) } catch (InterruptedException e) {e.printStackTrace ();}}, "user A") .start (); new Thread (()-> {try {movie.showSpiderTickets ();} catch (InterruptedException e) {e.printStackTrace ()) }, "user B") .start ();}}

Execution result:

The remaining number of votes for the devil's boy Nezha is: 20

We found that blocking when buying movie tickets will affect the purchase of Spiderman tickets, but in fact, the two movies are independent of each other, so we need to reduce the granularity of the lock and change the lock of the entire object into a lock of two global variables. The modification code is as follows:

Public void showBabyTickets () throws InterruptedException {synchronized (babyTickets) {System.out.println ("Magic Boy's remaining votes are:" + babyTickets); / / purchase latch.await ();}} public void showSpiderTickets () throws InterruptedException {synchronized (spiderTickets) {System.out.println ("Spider-Man's remaining votes are:" + spiderTickets) / / purchase}}

Execution result:

The remaining votes of the devil's boy Nathan are: 20, Spider-Man's remaining votes are: 100.

Now the tickets for the two movies will not affect each other, which is the second way to optimize the lock: reduce the granularity of the lock. By the way, the ConcurrentHashMap in the Java concurrent package turns a large lock into 16 small locks, achieving efficient concurrency security through segmented locking.

2.3 Lock separation

Lock separation is often referred to as read-write separation. We divide locks into read locks and write locks. Read locks do not need blocking, while write locks consider concurrency.

Fair lock: ReentrantLock unfair lock: Synchronized, ReentrantLock, cas pessimistic lock: Synchronized optimistic lock: cas exclusive lock: Synchronized, ReentrantLock shared lock: Semaphore

Here will not talk about the concept of each lock, you can learn by yourself, locks can also be classified according to bias locks, lightweight locks, heavy locks.

4. Redis distributed lock

After understanding the basic concept of lock and lock optimization, this paper focuses on the concept of distributed lock.

The figure above shows the distributed environment we have built. There are three ticket purchase items corresponding to one inventory, and each system will have multiple threads. As above, can the modification operation and lock on the inventory ensure the thread safety of these six threads?

Of course not, because each ticketing system has its own JVM process, which is independent of each other, so adding synchronized can only ensure the thread safety of a system, not distributed thread safety.

So we need a common middleware for all three systems to solve this problem.

Here, we choose Redis as the distributed lock. Multiple systems set the same key in Redis. Only if the key does not exist can the key be set up successfully, and the key will correspond to the unique identity of one of the systems. When the system accesses resources, delete the key to achieve the purpose of releasing the lock.

4.1 what points should be paid attention to in distributed locks 1) Mutual exclusion

Only one client can acquire the lock at any one time.

It's easy to understand that only one of all systems holds a lock.

2) Anti-deadlock

If a client crashes while holding a lock and does not release the lock, then other clients cannot acquire the lock, which will cause a deadlock, so make sure that the client will release the lock.

In Redis, we can set the expiration time of locks to ensure that deadlocks do not occur.

3) unlock by the lock holder

Unlock the bell must also tie the bell, lock and unlock must be the same client, client A's thread must be client A's thread to unlock, the client cannot unlock other clients.

4) reentrant

When a client acquires an object lock, the client can acquire the lock on the object again.

4.2 Redis distributed Lock process

The specific process of Redis distributed lock:

1) first, use the nature of Redis cache to set a key-value pair in Redis in the form of key-value. Key is the name of the lock, and then multiple threads of the client compete for the lock. If the competition succeeds, set value as the unique identity of the client.

2) the client competing to the lock does two things:

The effective time of setting the lock is to prevent deadlock (very critical)

According to the needs of the business, continuous stress testing is needed to determine the length of validity.

Assign a unique identity of the client to ensure that the lock holder is unlocked (very important)

So the value here is set to a unique identity (such as uuid).

3) access to shared resources

4) there are two ways to release the lock, the first is to release the lock automatically after the expiration of the validity period, and the second is to determine whether you have the permission to release the lock according to the unique ID, and release the lock if the identification is correct.

4.3 locking and unlocking 4.3.1 locking

1) setnx command lock

Set if not exists We will use the Redis command setnx,setnx which means that the lock will be set successfully only if the lock does not exist.

2) set the effective time of the lock to prevent deadlock expire

Locking requires two-step operation, think about what will be the problem?

What if the client suddenly hangs after we add the lock? Then the lock will become a lock with no expiration date, and then a deadlock may occur. Although the probability of this happening is very small, once a problem occurs, it will be very serious, so we have to combine these two steps into one step.

Fortunately, Redis3.0 has combined these two instructions into a new instruction.

Take a look at the source code in the official documentation of jedis:

Public String set (String key, String value, String nxxx, String expx, long time) {this.checkIsInMultiOrPipeline (); this.client.set (key, value, nxxx, expx, time); return this.client.getStatusCodeReply ();}

That's what we want!

4.3.2 unlock check whether you hold the lock (determine the unique identification); delete the lock.

Unlocking is also two steps, and it is also necessary to ensure the atomicity of unlocking and combine the two steps into one step.

This cannot be done with the help of Redis, but can only be achieved by Lua scripts.

If Redis.call ("get", key==argv [1]) then return Redis.call ("del", key) else return 0 end

This is a Lua script that determines whether you hold the lock and releases the lock.

Why are Lua scripts atomic? Because the Lua script is executed by jedis with the eval () function, if executed, it will all be executed.

5. Redis distributed lock code implements public class RedisDistributedLock implements Lock {/ / context, which saves the holder of the current lock id private ThreadLocal lockContext = new ThreadLocal (); / / the default lock timeout private long time = 100; / / reentrant private Thread ownerThread Public RedisDistributedLock () {} public void lock () {while (! tryLock ()) {try {Thread.sleep (100);} catch (InterruptedException e) {e.printStackTrace ();} public boolean tryLock () {return tryLock (time,TimeUnit.MILLISECONDS) } public boolean tryLock (long time, TimeUnit unit) {String id = UUID.randomUUID (). ToString (); / / each lock holder is assigned a unique id Thread t = Thread.currentThread (); Jedis jedis = new Jedis ("127.0.0.1", 6379) / / if ("OK" .equals (jedis.set ("lock", id, "NX", "PX", unit.toMillis (time) {/ / the id lockContext.set (id) of the person who holds the lock; ① / / records the current thread setOwnerThread (t) only if the lock does not exist ② return true;} else if (ownerThread = = t) {/ / because the lock is reentrant, you need to determine if the current thread already holds the lock. Return true;} else {return false;}} private void setOwnerThread (Thread t) {this.ownerThread = t } public void unlock () {String script = null; try {Jedis jedis = new Jedis ("127.0.0.1", 6379); script = inputStream2String (getClass (). GetResourceAsStream ("/ Redis.Lua")); if (lockContext.get () = = null) {/ / No one holds the lock return } / / remove locks ③ jedis.eval (script, Arrays.asList ("lock"), Arrays.asList (lockContext.get ()); lockContext.remove ();} catch (Exception e) {e.printStackTrace () }} / * convert InputStream to String * @ param is * @ return * @ throws IOException * / public String inputStream2String (InputStream is) throws IOException {ByteArrayOutputStream baos = new ByteArrayOutputStream (); int I =-1; while ((I = is.read ())! = 1) {baos.write (I) } return baos.toString ();} public void lockInterruptibly () throws InterruptedException {} public Condition newCondition () {return null;}} uses a context global variable to record the uuid of the person holding the lock. When unlocking, you need to pass the uuid as a parameter into the Lua script to determine whether it can be unlocked. To record the current thread to achieve the reentrant nature of the distributed lock, if the current thread holds the lock, it is also a successful lock. Use the eval function to execute the Lua script to ensure atomicity when unlocking. VI. Comparison of distributed locks 6.1 distributed locks based on database

1) implementation method

Insert a piece of data when you acquire the lock and delete it when you unlock it.

2) shortcomings

If the database is hung up, the business system will be unavailable. Unable to set expiration time, which can cause deadlock. 6.2 distributed locks based on zookeeper

1) implementation method

Create a new node under the specified node's directory when the lock is added, and delete the temporary node when the lock is released. Because of the existence of heartbeat detection, deadlock will not occur, so it is safer.

2) shortcomings

The performance is average and not as efficient as Redis.

So:

From a performance perspective:

Redis > zookeeper > Database from the perspective of reliability (security):

Zookeeper > Redis > Database VII. Summary

Starting from the basic concept of lock, this paper puts forward the thread safety problem when multi-thread accesses shared resources, and then solves the thread safety problem by adding lock. This method will degrade the performance. It is necessary to optimize the lock through three ways: shortening lock holding time, reducing lock granularity and lock separation.

After that, four characteristics of distributed lock are introduced.

Mutually exclusive anti-deadlock plus lock human unlock reentrant

Then the distributed lock is implemented with Redis. When locking, the command of Redis is used to lock, and when unlocking, the Lua script is used to ensure atomicity.

Finally, the advantages and disadvantages and usage scenarios of three kinds of distributed locks are compared.

I hope you will have a new understanding of distributed locks, and I also hope that you will think more about performance while thinking about solving problems.

Author: Yang Heng

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.