Redis Chat (1) : Building the Knowledge Map
Redis Topics (2) : The underbelly of Redis data structures
Recently, distributed issues have been widely discussed, such as distributed transactions, distributed frameworks, ZooKeeper, SpringCloud, and so on. This article first reviews the concept of locking, then introduces distributed locking and how to implement distributed locking using Redis.
First, the basic understanding of the lock
First, let’s review the concept of locks in our work study.
Why do we talk about locks first and then distributed locks?
As we all know, the role of the lock is to solve the multi-thread access to shared resources and the thread safety problem, but in ordinary life, the use of lock is not much, may be some friends of the concept of lock and some basic use is not very clear, so we first look at the lock, and then in-depth introduction to distributed lock.
Through a small case of ticket selling, for example, if people go to grab dota2 ti9 tickets, what problems will occur 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){// Checks whether the inventory is sufficientif((ticketNum - num) >= 0){
try {
TimeUnit.MILLISECONDS.sleep(200);
}catch (InterruptedException e){
e.printStackTrace();
}
ticketNum -= num;
System.out.println(Thread.currentThread().getName() + "Successful sale"
+ num + "Zhang, surplus." + ticketNum + "Ticket");
}else {
System.err.println(Thread.currentThread().getName() + "No sale."
+ num + "Zhang, surplus." + ticketNum + "Ticket"); } } public static void main(String[] args) throws InterruptedException{ Ticket ticket = new Ticket(); // Start 10 threads to grab tickets, normally two people should not be able to grab ticketsfor(int i=0; i<10; i++){ new Thread(() -> ticket.reduce(1),"User"+ (i + 1)).start(); } Thread.sleep(1000L); }}Copy the codeCode analysis: there are 8 ti9 tickets, set up 10 threads (that is, simulate 10 people) to grab tickets concurrently, if the successful display success, grab failure display failure. There should be 8 successful robbers and 2 failed robbers. Here is the result:
We found that the running result is not consistent with the expected situation, unexpectedly 10 people bought tickets, that is to say, there is 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 that both threads read is 1, which means that thread B has successfully grabbed the ticket before thread A has changed its inventory.
How do you solve it? As you all know, the synchronized keyword can be used. When one thread performs a reduce method, other threads block in the wait queue, so that multiple threads do not compete for a shared variable.
For example
For example, when we go to the gym, if many people use a machine at the same time and run on a treadmill at the same time, there will be a big problem, and we will fight like cats and dogs. If we add a lock to the door of the gym, only those who have the key to the lock can go in and exercise while others wait outside the door, then competition for fitness equipment can be avoided. The code is as follows:
Public synchronized void reduce(int num){// Check whether the inventory is sufficientif((ticketNum - num) >= 0){
try {
TimeUnit.MILLISECONDS.sleep(200);
}catch (InterruptedException e){
e.printStackTrace();
}
ticketNum -= num;
System.out.println(Thread.currentThread().getName() + "Successful sale"
+ num + "Zhang, surplus." + ticketNum + "Ticket");
}else {
System.err.println(Thread.currentThread().getName() + "No sale."
+ num + "Zhang, surplus." + ticketNum + "Ticket"); }}Copy the codeRunning results:
Sure enough, it turned out that two people had failed to get tickets, and it seemed that our goal had been achieved.
Second, lock performance optimization
2.1 Shorten the lock holding time
In fact, according to our understanding of daily life, it’s unlikely that the entire gym will consist of just one person exercising. So we just need to lock one machine so that one person can run and the other person can do something else.
For the ticketing system, we only need to lock the code of stock modification operation, and other codes can be carried out in parallel, which will greatly reduce the lock holding time. The code modification is 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() + "Successful sale"
+ num + "Zhang, surplus." + ticketNum + "Ticket");
}
else {
System.err.println(Thread.currentThread().getName() + "No sale."
+ num + "Zhang, surplus." + ticketNum + "Ticket");
}
if(ticketNum == 0){
System.out.println("Take" + (System.currentTimeMillis() - startTime) + "毫秒"); }}Copy the codeThe purpose of this is to make full use of CPU resources and improve the efficiency of code execution.
Here we make a print of the two ways of time:
Public synchronized void reduce(int num){// Check whether the inventory is sufficientif((ticketNum - num) >= 0){
try {
TimeUnit.MILLISECONDS.sleep(200);
}catch (InterruptedException e){
e.printStackTrace();
}
ticketNum -= num;
if(ticketNum == 0){
System.out.println("Take" + (System.currentTimeMillis() - startTime) + "毫秒");
}
System.out.println(Thread.currentThread().getName() + "Successful sale"
+ num + "Zhang, surplus." + ticketNum + "Ticket");
}else {
System.err.println(Thread.currentThread().getName() + "No sale."
+ num + "Zhang, surplus." + ticketNum + "Ticket"); }}Copy the code
Sure enough, locking only parts of your code greatly improves your code’s efficiency.
So, 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, for two movies, nezha and spiderman, we simulated the process of payment and purchase, made the method wait and added an await method on CountDownLatch. The result is as follows:
package Thread; import java.util.concurrent.CountDownLatch; public class Movie { private final CountDownLatch latch = new CountDownLatch(1); Private Integer babyTickets = 20; Private Integer spiderTickets = 100; public synchronized void showBabyTickets() throws InterruptedException{ System.out.println("The remaining votes for Nezha are:"+ babyTickets); / / buy latch. Await (); } public synchronized void showSpiderTickets() throws InterruptedException{ System.out.println("Spiderman's remaining votes are:"+ spiderTickets); } 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(); }}Copy the codeExecution Result:
The remaining votes for Nezha: 20Copy the codeWe found that blocking when buying Nezha tickets would affect the purchase of spiderman tickets. 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 whole object of the movie into the lock of two global variables, and modify the code as follows:
public void showBabyTickets() throws InterruptedException{
synchronized (babyTickets) {
System.out.println("The remaining votes for Nezha are:"+ babyTickets); / / buy latch. Await (); } } public void showSpiderTickets() throws InterruptedException{ synchronized (spiderTickets) { System.out.println("Spiderman's remaining votes are:"+ spiderTickets); // purchase}}Copy the codeExecution Result:
Nezha has 20 remaining votes and Spider-Man has 100 remaining votesCopy the codeThe two movie tickets will no longer affect each other, which is the second way to optimize locks: reduce the granularity of locks. By the way, the ConcurrentHashMap in the Java concurrency package converts a large lock into 16 small locks, which are sectionally-efficient concurrency security.
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 to block, while write locks need to consider concurrency.
Three, the type of lock
- Fair lock: ReentrantLock
- Unfair lock: Synchronized, ReentrantLock, cas
- Pessimistic lock: Synchronized
- Optimistic lock: CAS
- Exclusive locks: Synchronized and ReentrantLock
- Shared lock: Semaphore
Here is not a description of each kind of lock concept, you can learn by yourself, lock can also be classified according to biased lock, lightweight lock, heavyweight lock.
Redis distributed lock
After understanding the basic concept of lock and lock optimization, focus on the concept of distributed lock.
The above figure shows the distributed environment we built. There are three ticketing items, corresponding to one inventory. Each system has multiple threads.
Of course, it cannot, because each ticket purchasing system has its own JVM process and is independent of each other, so adding synchronized can only ensure the thread safety of a system, but not the distributed thread safety.
So a middleware common to all three systems is needed to solve this problem.
Here, we choose Redis as a distributed lock. Multiple systems set the same key in Redis. Only when the key does not exist, the setting can be successful, and the key will correspond to the unique identity of one of the systems.
4.1 What Points should BE Paid attention to in Distributed Locks
1) Mutual exclusion
Only one client can acquire the lock at any time.
This is easy to understand, only one of all systems can hold the 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, resulting in a deadlock, so ensure 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) Lock holder unlock
The thread of client A must be the thread of client A to unlock the lock. The client cannot unlock the lock of 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
Redis distributed lock process:
1) First set a key-value pair in Redis using the nature of Redis cache. Key is the name of the lock. Then multiple threads of the client will compete for the lock.
2) Competing to lock clients do two things:
- Set the lock duration to prevent deadlocks (critical)
Constant stress testing is required to determine the length of the validity period based on business needs.
- Assign the unique identity of the client to ensure that the lock holder unlocks (very important)
So the value here is set to a unique identifier (such as a UUID).
3) Access shared resources
4) Release the lock. There are two ways to release the lock. The first way is to release the lock automatically after the expiration date; the second way is to judge whether you have the permission to release the lock according to the unique identifier.
4.3 Locking and Unlocking
This lock
1) Setnx command lock
Set if not exists we use the Redis command setnx. Setnx is set only if the lock does not exist.
2) Set the valid time of lock to prevent deadlock expire
Lock need two steps operation, think about what will be the problem?
What if the client suddenly hangs after we lock it? The lock then becomes a lock with no expiration date, and a deadlock can occur. It’s very rare, but it can be very serious, so we need to combine these two steps into one.
Fortunately, DIS3.0 has combined these two directives into a new one.
Take a look at the source code in jedis’ official documentation:
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();
}
Copy the codeThat’s what we want!
4.3.2 unlock
- Check if you own the lock (determine the unique identifier);
- Remove the lock.
Unlocking is also a two-step process, but it is also necessary to ensure atomicity of unlocking, and combine the two steps into one step.
This can’t be done with Redis, it can only be done with Lua scripts.
if Redis.call("get",key==argv[1])then
return Redis.call("del",key)
else return 0 end
Copy the codeThis is a Lua script that determines if it holds the lock itself and releases it.
Why are Lua scripts atomic? Because the Lua script is executed by Jedis using the eval() function, it is executed completely.
Five, Redis distributed lock code implementation
Public class RedisDistributedLock implements Lock {// context, Private ThreadLocal<String> lockContext = new ThreadLocal<String>(); Private long Time = 100; // Reentrant private Thread ownerThread; publicRedisDistributedLock() {
}
public void lock() {
while(! tryLock()){ try { Thread.sleep(100); }catch (InterruptedException e){ e.printStackTrace(); } } } public booleantryLock() {
returntryLock(time,TimeUnit.MILLISECONDS); } public boolean tryLock(long time, TimeUnit unit){ String id = UUID.randomUUID().toString(); Thread t = thread.currentThread (); Jedis jedis = new Jedis("127.0.0.1", 6379); // Lock only when the lock does not exist and set the lock durationif("OK".equals(jedis.set("lock",id, "NX"."PX", ununit.tomillis (time)))){// The id of the person holding the lock lockContext.set(id); ① // Record the current threadsetOwnerThread(t); 2.return true;
}else if(ownerThread == t){// Because the lock is reentrant, we need to determine whether the current thread already holds the lockreturn 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 lockreturn; } // delete lock ③ 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() {
returnnull; }}Copy the code- A context global variable is used to record the UUID of the person holding the lock. This UUID needs to be passed into the Lua script as a parameter to determine whether the lock can be unlocked.
- The current thread is recorded to achieve the reentrancy of the distributed lock. If the current thread holds the lock, the lock is also considered successful.
- The eval function is used to execute the Lua script to ensure atomicity when unlocking.
Comparison of distributed locks
6.1 Database based Distributed Locking
1) Implementation method
A piece of data is inserted when the lock is acquired and deleted when the lock is unlocked.
2) disadvantages
- If the database fails, the service system becomes unavailable.
- Unable to set expiration time, resulting in deadlock.
6.2 Distributed Lock Based on ZooKeeper
1) Implementation method
A new node is created in the directory of the specified node when the lock is attached. The temporary node is deleted when the lock is released. Because of heartbeat detection, deadlocks do not occur, making it more secure.
2) disadvantages
Performance is mediocre and not as efficient as Redis.
So:
- From a performance perspective: Redis > ZooKeeper > Database
- From the perspective of reliability (security) : ZooKeeper > Redis > database
Seven,
In this paper, starting from the basic concept of lock, put forward the thread safety problem when multi-threading access to shared resources, and then solve the thread safety problem by locking. This method will degrade performance, need to optimize the lock by shortening the lock holding time, reducing the lock granularity, lock separation three ways.
After that, four characteristics of distributed lock are introduced:
- Mutual exclusivity
- Deadlock prevention
- The locker unlocks
- reentrancy
Then use Redis to achieve distributed lock, lock with Redis command to lock, unlock with the help of Lua script to ensure atomicity.
Finally, the advantages, disadvantages and application scenarios of three distributed locks are compared.
I hope you have a new understanding of distributed locking, and I hope you think about performance issues as well as solving them.
Author: Yang Heng