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

How to lock and distributed lock, I believe that many inexperienced people do not know what to do. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

Lock

In the multithreaded software world, the Data Race for shared resources is concurrency, and the most direct way to protect the access of shared resource data is to introduce locks.

Lock-free programming is also a method, but it is beyond the scope of this article. Lock-free or lock optimization can be achieved by means of concurrent multithreading to single thread (Disruptor), functional programming, lock granularity control (ConcurrentHashMap bucket), semaphore (Semaphore) and so on.

Technically, locks can also be understood as serializing a large number of concurrent requests, but please note that serialization cannot simply be equated with queuing, because queuing is no different from the real world. Queuing means that everyone receives resources on a first-come-first-served basis. However, in many cases, it is unfair for Unfair to grab resources between multiple threads for performance considerations. ReentrantLock reentrant lock in Java provides two implementations of fair lock and unfair lock

Also note that serial does not mean that there is only one queue, only one at a time. Of course there can be many teams, more than one at a time. For example, if there are a total of 10 tables in a restaurant, the waiter may let up to 10 people in at a time, and someone may come out and let the same number of people in. Semaphore semaphore in Java, which is equivalent to managing a batch of locks at the same time.

Type 1 spin lock (Spin Lock) of the lock

If the spin lock has been acquired by another thread, the caller loops around to see if the holder of the spin lock has released the lock, hence the name "spin".

A spin lock is a non-blocking lock, that is, if a thread needs to acquire a spin lock, but the lock is already occupied by another thread, the thread will not be suspended, but is constantly consuming CPU time and constantly trying to acquire the spin lock.

Java does not have a default spin lock implementation. The sample code is as follows:

Public class SpinLock {

Private AtomicReference sign = new AtomicReference ()

Public void lock () {

Thread current = Thread.currentThread ()

While (! sign .compareAndSet (null, current)) {

}

}

Public void unlock () {

Thread current = Thread.currentThread ()

Sign .compareAndSet (current, null)

}

}

Through the example, you can see that the CAS atomic operation sets sign from the desired null to the current thread, thread A can acquire the lock with the first call to lock (), and the second call will enter the loop to wait, because sign has been set to current.

Reentry can be realized by simply adding an owner comparison judgment and lock counter of the current lock.

2 Mutex (Mutex Lock)

A mutex is a blocking lock. When a thread is unable to acquire a mutex, the thread will be suspended directly and no longer consume CPU time. When other threads release the mutex, the operating system will wake up the suspended thread.

The blocking lock can be said to let the thread enter the blocking state and wait. Only when the corresponding signal (wake up, time) is obtained can the thread enter the ready state, and all threads in the ready state enter the running state through competition. Its advantage is that blocked threads do not take up CPU time and do not cause excessive CPU utilization, but the entry time and recovery time are slightly slower than spin locks. In the case of fierce competition, the performance of blocking lock is obviously higher than that of spin lock.

In JAVA, the methods that can enter / exit, block state, or contain blocking locks are:

Synchronized

ReentrantLock

Object.wait () / notify ()

LockSupport.park () / unpart () (j.u.c is often used)

Spin lock VS mutex

The two locks are suitable for different scenarios:

In the case of a multi-core processor, it is expected that the thread waits for a lock so short that it takes less than two context switches for the thread, so it is cost-effective to use a spin lock.

In the case of a multi-core processor, it is recommended to use a mutex if the thread is expected to wait longer for the lock, which is at least longer than two thread context switches.

If it is a single-core processor, it is generally recommended not to use spin locks. Because only one thread is running at a time, if the running thread finds that it cannot acquire the lock and can only wait for the lock to be unlocked, but because it is not suspended, the thread that acquired the lock has no way to enter the running state. Only when the running thread runs out of time slices allocated to it by the operating system can it have a chance to be scheduled. The cost of using a spin lock in this case is high.

If locked code is often called, but when competition rarely occurs, priority should be given to the use of spin locks, which have less overhead and higher mutexes.

3 reentrant lock (Reentrant Lock)

A reentrant lock is a special mutex that can be acquired multiple times by the same thread without causing a deadlock.

First of all, it is a mutex: there is only one thread lock at any one time. That is, assuming that thread A has acquired the lock, thread B cannot acquire the lock until thread A releases the lock, and thread B will enter the blocking state to acquire the lock.

Second, it can be held multiple times by the same thread. That is, assuming that the A thread has acquired the lock, it can be acquired successfully if the A thread requests to acquire the lock again before releasing the lock.

Both synchronized and ReentrantLock in Java are reentrant locks. 4 lightweight lock (Lightweight Lock) & bias lock (Biased Lock)

First of all, mutex is a resource-consuming operation that causes the thread to hang and needs to be rescheduled back to the original thread in a short time.

In order to reduce the performance consumption caused by acquiring and releasing locks, Java6 introduces "biased locks" and "lightweight locks", so there are four kinds of locks in Java6, namely, no lock state, partial lock state, lightweight lock state and heavyweight lock state, which will gradually upgrade with the competition. Locks can be upgraded but cannot be degraded, which means that biased locks cannot be degraded to biased locks after upgrading to lightweight locks. This lock upgrade strategy can not be degraded in order to improve the efficiency of acquiring and releasing locks.

Different locking levels in the database (Lock Hierarchy, tables / pages / rows, etc.)

There is also a concept similar to lock upgrade (Lock Escalations). 5 JUC

Doug Lea, the master of concurrency, implements a large number of concurrency tool classes in the JUC package, and the idea of concurrency is well reflected in the source code. For example, Semaphore, CountDownLatch and CyclicBarrier are all classic implementations in specific scenarios. If you are interested, you can study them by yourself, and finally sigh: locks can play with so many tricks.

Java-7-concurrent-executors-uml-class-diagram-example

Sequelae of the lock

In the concurrent world, locks play both good and evil roles, and most of the time they are villains. The sequelae of lock include: deadlock, hunger, live lock, Lock Convoying (multiple threads with the same priority repeatedly compete for the same lock, at this time, a large number of threads that are awakened but can not get the lock are forced to schedule and switch, this frequent scheduling switching affects the system performance, priority inversion, unfair and inefficient and so on. These problems are common and have to be faced in the process of realizing the lock.

Here only throw out the question for the reader to understand, the specific solution is not in the scope of this article.

The difference between a livelock and a deadlock is that the entity in the livelock is constantly changing its state, the so-called "alive", while the entity in the deadlock is waiting; the livelock may unlock itself, but the deadlock cannot.

Distributed lock

Compared with the stand-alone lock set by the stand-alone application, the lock set for the exclusive access of the nodes of the distributed application to the shared resources is the distributed lock. In distributed scenarios, there are many situations that need to achieve the ultimate consistency of multiple nodes. Such as global dispatcher, distributed transaction and so on.

The traditional solution to realize distributed lock is to use persistent database (such as InnoDB row lock, or transaction, or version optimistic lock). Of course, most of the time it can meet the needs of most people. Nowadays, the magnitude of Internet applications has exploded at the geometric level. Using more efficient distributed components such as zookeeper,redis to implement distributed locks can provide highly available and stronger locking features, and support rich usage scenarios.

There are many open source implementations, such as Redis author's Redlock,Redission based on Redis, and so on.

Interlude:

Where locks exist is controversial, and Redlock is no exception. A distributed expert once published an article questioning the correctness of Redlock, and the author of Redis responded in the. The competition is relatively exciting, and interested readers can go there on their own.

Predecessors planted trees and future generations to enjoy the cool, the current various lock implementations have provided us with a lot of elegant design templates, let's analyze how to design distributed locks in the end.

Design Essentials of distributed Lock

Let's take Redis as an example to briefly think about the implementation of this lock.

It seems that only one SETNX command is needed to add the lock. Returning 1 indicates that the lock is successful, and 0 indicates that the lock is occupied. Then unlock it with the DEL command. A return of 1 indicates that the unlock is successful, and 0 indicates that it has been unlocked.

And then the question comes:

There will be lock competition in SETNX, and if the client goes down during execution, it will cause deadlock problem, that is, lock resources cannot be released. To solve the deadlock problem, we can learn from the deadlock detection of Mysql, set a failure time, and determine whether it needs to be forcibly unlocked by the time stamp of key.

However, there are also problems with forced unlocking. One is the time difference. There may also be time differences in the local time of different machines. In high concurrency scenarios with very small transaction granularity, for example, when a lock is deleted, it is determined that the timestamp has expired, and it is possible to delete the locks of other clients that have acquired the lock.

In addition, if a timeout is set, if the execution time of the program exceeds the timeout, the lock will be automatically released before it is finished, and there will be a problem when the client holding the lock is unlocked again. and the most serious thing is that consistency is not guaranteed. How to set this timeout reasonably may be a process of observation and continuous adjustment.

So, summarize a few key points of the design:

The limitation of the lock. Avoid deadlocks caused by a single point of failure, affecting other clients to acquire locks. But also make sure that once a client holds a lock, it will not be unlocked by other clients when it is available.

The check during the lock. Try to check the state of the lock at the critical node, so it should be designed to be reentrant.

Reduce the operation of acquiring locks and minimize the pressure of redis. So you need to let the client's application lock have a waiting time, instead of all the request threads that apply for the lock keep looping to apply for the lock.

The granularity of locked transactions or operations is as small as possible, reduce the waiting time for other clients to apply for locks, and improve processing efficiency and concurrency.

After the client holding the lock is unlocked, it must be able to notify other nodes waiting for the lock, otherwise the other nodes can only wait an expected time before triggering the application for the lock. Thread-like notifyAll should be able to synchronize lock state to other clients and be distributed messages.

Consider any exceptions that may occur in the execution handle, the correct flow of state, and handling. For example, the entire waiting task queue or task pool cannot be affected because a node failed to unlock, or a lock query failed (redis timeout or other runtime exception).

If the Redis server is down or the network is abnormal, there should be other backup schemes, such as stand-alone lock current limit + persistent lock of the final database to do the final consistency control.

After reading the above, have you mastered how to lock and how to distribute locks? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

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.