Outline
Interlock MultiLock Overview
Interlocking and releasing locks for MultiLock
The algorithm principle of RedLock RedLock
Source code analysis of RedLock RedLock
Interlock MultiLock Overview
(1) Introduction to MultiLock
(2) Use of MultiLock
(3) Initialization of MultiLock
(1) Introduction to MultiLock
1. Scenario where multiple resources need to be locked at one time
For example, locking an inventory + locking an order + locking a point, locking multiple resources at once. None of these locked resources can be modified by other threads at will. Then, after the current thread updates these resources at once, releases multiple locks one by one.
2. Redisson distributed lock supports the MultiLock mechanism
Multiple locks can be combined into one large lock, and a unified lock application and lock release can be made for the large lock. That is, lock multiple resources at once, then deal with some things, and then release the locks corresponding to all resources at once after processing.
3. Redisson's Redisson MultiLock
Redisson's RedissonMultiLock can associate multiple RLocks into one interlock, and each RLock object instance can come from a different Redisson instance.
(2) Use of MultiLock
//Interlock
RedissonClient redissonInstance1 = (config);
RedissonClient redissonInstance2 = (config);
RedissonClient redissonInstance3 = (config);
RLock lock1 = ("lock1");
RLock lock2 = ("lock2");
RLock lock3 = ("lock3");
RedissonMultiLock lock = new RedissonMultiLock(lock1, lock2, lock3);
//Lock at the same time: lock1 lock2 lock3, all locks are locked successfully to be considered successful
();
//Release the lock at the same time
();
------------------------------------------------------------------
//Lock lock1, lock2, lock3; if the lock is not released actively, the lock will be automatically released in 10 seconds.
(10, );
//Waiting for locking is up to 100 seconds; if the lock is not released actively after locking is successfully completed, the lock will be automatically released after 10 seconds.
boolean res = (100, 10, );
();(3) Initialization of MultiLock
public class RedissonMultiLock implements RLock {
final List<RLock> locks = new ArrayList<>();
...
public RedissonMultiLock(RLock... locks) {
if ( == 0) {
throw new IllegalArgumentException("Lock objects are not defined");
}
((locks));
}
...
}
Interlocking and releasing locks for MultiLock
(1) Access to interlock (timeout time limit + lock failure limit)
(2) Release of interlock (release the lock in sequence + wait for the lock to be released synchronously)
(1) Access to interlock (timeout time limit + lock failure limit)
1. RedissonMultiLock's lockInterruptible() method acquires all locks every time while loop
When adding a lock, the lock() method of RedissonMultiLock will be called first, and then the lockInterruptibly() method of RedissonMultiLock will be called.
In the lockInterruptibly() method of RedissonMultiLock, the waiting time when acquiring the lock will be calculated based on the number of interlocks, and then the while loop will keep trying to call the tryLock() method to acquire all locks. Only when all locks are acquired will the while loop exit.
2. The tryLock() method of RedissonMultiLock has a timeout limit + the number of lock failures limit
In the tryLock() method of RedissonMultiLock, the locks that need to be acquired will be traversed in turn, and then the tryLock() method of RLock will be called to try to acquire each lock. For example, call the reentrant lock() method to try to acquire each lock.
Assume that the incoming leaseTime = -1, waitTime = 4500, it is calculated that remainsTime = 4500. Then the waitTime in the tryLock() method passed into RedissonLock, which specifies that the wait timeout time when acquiring each lock is 4500 milliseconds. If the lock cannot be acquired within 4500 milliseconds, it will be exited and marked as failed to acquire the lock. In addition, the parameter newLeaseTime in the tryLock() method passed into RedissonLock is -1. It indicates how long the lock will be automatically released after it is acquired. Since leaseTime is -1, newLeaseTime is also -1. So if the lock is obtained, a WatchDog will be activated and then 10 seconds later to check the lock's holding status.
There are two limitations in the for loop that acquires the lock by traversing the tryLock() method of RedissonMultiLock.
Limit one: Timeout limit
When the lock is acquired successfully, the lock instance is added to a list. But no matter whether the lock is successful or failed, the remainingTime will be reduced. In fact, remainsTime is to get the timeout time of MultiLock, and each lock is 1500 milliseconds by default. When it is found that the remainingTime is less than 0, it means that the interlock has failed and the acquired lock needs to be released. At this time, the tryLock() method of RedissonMultiLock will return false and continue with the next round of attempts.
Limit 2: Lock failure limit
When the lock acquisition fails, first determine whether the minimum number of locking is successfully reached. If it is reached, the loop can be exited and the return will be performed. If it has not been reached, the failedLocksLimit is decreasing. When failedLocksLimit is found to be 0, it means that the interlock failed this time, and the acquired lock needs to be released. At the same time, reset the value of failedLocksLimit + clear the acquiredLocks + reset the iterator of the lock list to prepare for the next attempt to acquire all locks. That is, the() method will return false and continue to the next round of attempts.
3. RedissonMultiLock's tryLock() method fails to acquire all locks and continue to try again
When the tryLock() method of RedissonMultiLock returns false, in the while loop of the lockInterruptibly() method of RedissonMultiLock, the tryLock() method of RedissonMultiLock will be called again to try to acquire the interlock.
4. Summary
Assuming there are n locks in the interlock to be acquired, then it may cycle many times to try to acquire the n locks. By default, each time you acquire this n lock, there will be a timeout of 1500*n milliseconds. That is to say, if the n lock is acquired for the first time, the n lock cannot be acquired within 1500*n milliseconds. Then you will continue to call the tryLock method for the next attempt and get the n lock again. Until one successful acquisition of this n lock within 1500*n milliseconds, the loop will be exited.
public class RedissonMultiLock implements RLock {
final List<RLock> locks = new ArrayList<>();
public RedissonMultiLock(RLock... locks) {
...
((locks));
}
@Override
public void lock() {
...
lockInterruptibly();
...
}
@Override
public void lockInterruptibly() throws InterruptedException {
lockInterruptibly(-1, null);
}
@Override
public void lockInterruptibly(long leaseTime, TimeUnit unit) throws InterruptedException {
// Calculate the waiting time when acquiring the lock based on the number of interlocks. WaitTime
//At this time, there are 3 locks in MutiLock, leaseTime=-1, baseWaitTime=4500, waitTime=4500
long baseWaitTime = () * 1500;
long waitTime = -1;
if (leaseTime == -1) {
//The incoming leaseTime is -1, assign baseWaitTime to waitTime
waitTime = baseWaitTime;
} else {
...
}
// Keep trying to get all locks
while (true) {
//Only when all locks are obtained, the while loop will exit
if (tryLock(waitTime, leaseTime, )) {
return;
}
}
}
@Override
public boolean tryLock(long waitTime, long leaseTime, TimeUnit unit) throws InterruptedException {
//The incoming leaseTime=-1, waitTime=4500 is calculated, and the remainingTime=4500 is calculated.
long newLeaseTime = -1;
...
//time=current time
long time = ();
long remainTime = -1;
if (waitTime != -1) {
//remainTime=4500
remainTime = (waitTime);
}
//RedissonRedLock will overload the calcLockWaitTime() method, shortening the timeout time for obtaining each small lock
//For example, the () method returns 1500
//() method returns 4500
long lockWaitTime = calcLockWaitTime(remainTime);
//RedissonRedLock will overload the failedLocksLimit() method, returning the maximum number of locks that can be allowed to fail to obtain.
//For example, if the () method returns 0, it means that a certain lock is not allowed to fail to obtain.
int failedLocksLimit = failedLocksLimit();
//acquiredLocks is used to save the acquired lock
List<RLock> acquiredLocks = new ArrayList<>(());
//Trace through the locks to be acquired in turn
for (ListIterator<RLock> iterator = (); ();) {
RLock lock = ();
boolean lockAcquired;
...
if (waitTime == -1 && leaseTime == -1) {
lockAcquired = ();
} else {
//awaitTime=4500
long awaitTime = (lockWaitTime, remainTime);
//The core method of obtaining locks (), such as () method
//If this lock cannot be acquired within awaitTime=4500 milliseconds, exit and mark it as failed to acquire the lock
lockAcquired = (awaitTime, newLeaseTime, );
}
...
if (lockAcquired) {
//After successfully obtaining the lock, add the lock instance to acquiredLocks
(lock);
} else {
if (() - () == failedLocksLimit()) {
break;
}
//Failed to obtain the lock, decrement the failedLocksLimit, and return false until the failedLocksLimit is 0.
if (failedLocksLimit == 0) {
//This time the interlock is acquired, the acquired lock needs to be released.
unlockInner(acquiredLocks);
if (waitTime == -1) {
return false;
}
//Reset the value of failedLocksLimit to prepare for the next attempt to acquire all locks
failedLocksLimit = failedLocksLimit();
//Clear acquiredLocks and prepare for the next attempt to acquire all locks
();
//Reset the iterator of the lock list
while (()) {
();
}
} else {
//Decrement failedLocksLimit
failedLocksLimit--;
}
}
//Decrement the remainingTime. If the remainingTime is less than 0, it means that the interlocking failed to be acquired.
if (remainTime != -1) {
remainTime -= () - time;
time = ();
//If the remainingTime is found to be less than 0, it means that the interlocking failed to be acquired.
if (remainTime <= 0) {
unlockInner(acquiredLocks);
return false;
}
}
}
if (leaseTime != -1) {
()
.map(l -> (RedissonLock) l)
.map(l -> ((leaseTime), ))
.forEach(f -> ().join());
}
return true;
}
...
}(2) Release of interlock (release the lock in sequence + wait for the lock to be released synchronously)
Release locks means calling the release logic of each lock in sequence, and waiting for each lock to be released before returning.
public class RedissonMultiLock implements RLock {
...
@Override
public void unlock() {
List<RFuture<Void>> futures = new ArrayList<>(());
//Call the release logic of each lock in turn
for (RLock lock : locks) {
(());
}
for (RFuture<Void> future : futures) {
//Synchronously wait for each lock to be released
().join();
}
}
...
}
The algorithm principle of RedLock RedLock
(1) Specific process of RedLock algorithm
(2) Summary of four key points of RedLock algorithm
(1) Specific process of RedLock algorithm
Step 1:The client first gets the current timestamp T1.
Step 2:The client initiates lock requests to these 5 nodes in turn, and each request will set a timeout time. The timeout time is in milliseconds, which is much smaller than the valid time of the lock, and is generally several dozen milliseconds. If a node fails to lock, including network timeout and locks held by other threads, then apply for locks to the next Redis node immediately.
Step 3:If the client successfully locks from more than 3 (more than half) nodes, the current timestamp T2 is obtained again. If T2 - T1 < the expiration time of the lock, the client lock is considered to be successful, otherwise the lock fails.
Step 4:If the locking fails, a request to release the lock must be initiated to all nodes. If the lock is successful, go to operate the shared resource.
(2) Summary of four key points of RedLock algorithm
1. The client applies for locking on multiple Redis nodes
2. It is necessary to ensure that most nodes are locked successfully
3. Total time spent on locking for most nodes < expiration time of lock settings
4. When releasing the lock, you must initiate a request to all nodes to release the lock.
Source code analysis of RedLock RedLock
(1) Introduction to RedLock
(2) Implementation of RedLock
(3) RedissonRedLock's source code summary
(1) Introduction to RedLock
//Red Lock
RedissonClient redissonInstance1 = (config);
RedissonClient redissonInstance2 = (config);
RedissonClient redissonInstance3 = (config);
RLock lock1 = ("lock1");
RLock lock2 = ("lock2");
RLock lock3 = ("lock3");
RedissonRedLock lock = new RedissonRedLock(lock1, lock2, lock3);
//Lock at the same time: lock1 lock2 lock3
//A successful lock on most nodes is considered successful
();
();
---------------------------------------------------------------
//Lock lock1, lock2, lock3; if the lock is not released actively, the lock will be automatically released in 10 seconds.
(10, );
//Waiting for locking is up to 100 seconds; if the lock is not released actively after locking is successfully completed, the lock will be automatically released after 10 seconds.
boolean res = (100, 10, );
();(2) Implementation of RedLock
The implementation of RedissonRedLock is very simple, because RedissonRedLock is a subclass of RedissonMultiLock, so the RedLock algorithm relies on the MultiLock mechanism to implement it.
RedissonRedLock mainly changes several special behaviors in RedissonMultiLock through method overloading.
1. RedissonRedLock overloads failedLocksLimit() method of RedissonMultiLock
The failedLocksLimit() method will return up to how many locks are allowed to be retrieved. The failedLocksLimit() method will call the minLocksAmount() method, and the minLocksAmount() method will return the minimum number of successful locking, that is, more than half. The total number of locks minus the minimum number of locks successful is the maximum number of locks allowed to fail to acquire.
RedissonMultiLock failedLocksLimit() method returns 0, that is, RedissonMultiLock does not allow a certain lock to fail to obtain.
The specific processing is to use the tryLock() method of RedissonMultiLock. When the lock acquisition fails, first determine whether the minimum number of successful locking is reached. If it is reached, the loop can be exited and the return will be performed. If it has not been reached, the failedLocksLimit is decreasing. When failedLocksLimit is found to be 0, it means that the interlock failed this time, and the acquired lock needs to be released. At the same time, the value of failedLocksLimit is reset + clear acquiredLocks + reset the iterator of the lock list to prepare for the next attempt to acquire all locks. That is, the tryLock() method of RedissonMultiLock will return false and continue to the next round of attempts.
2. RedissonRedLock overloads RedissonMultiLock's calcLockWaitTime() method
The calcLockWaitTime() method returns the timeout when each lock is locked. For example, when waitTime = 4500ms and remainTime = 4500ms: RedissonMultiLock's calcLockWaitTime() method will return 4500, and RedissonRedLock's calcLockWaitTime() method will return 1500.
The timeout time of each lock attempt in RedissonMultiLock is 4500 milliseconds, and the timeout time of each lock attempt in RedissonRedLock is 1500 milliseconds. If the lock is not acquired within the timeout time, it is considered that the locking of the lock failed.
public class RedissonRedLock extends RedissonMultiLock {
public RedissonRedLock(RLock... locks) {
super(locks);
}
//How many locks can be allowed to fail to acquire
@Override
protected int failedLocksLimit() {
return () - minLocksAmount(locks);
}
//How many times are the minimum number of successful locks required: more than half
protected int minLocksAmount(final List<RLock> locks) {
return ()/2 + 1;
}
@Override
protected long calcLockWaitTime(long remainTime) {
return (remainTime / (), 1);
}
@Override
public void unlock() {
unlockInner(locks);
}
}
public class RedissonMultiLock implements RLock {
...
@Override
public void lockInterruptibly(long leaseTime, TimeUnit unit) throws InterruptedException {
// Calculate the waiting time when acquiring the lock based on the number of interlocks. WaitTime
//At this time, there are 3 locks in MutiLock, leaseTime=-1, baseWaitTime=4500, waitTime=4500
long baseWaitTime = () * 1500;
long waitTime = -1;
if (leaseTime == -1) {
//The incoming leaseTime is -1, assign baseWaitTime to waitTime
waitTime = baseWaitTime;
} else {
...
}
// Keep trying to get all locks
while (true) {
//Only when all locks are obtained, the while loop will exit
if (tryLock(waitTime, leaseTime, )) {
return;
}
}
}
@Override
public boolean tryLock(long waitTime, long leaseTime, TimeUnit unit) throws InterruptedException {
//The incoming leaseTime=-1, waitTime=4500 is calculated, and the remainingTime=4500 is calculated.
long newLeaseTime = -1;
...
//time=current time
long time = ();
long remainTime = -1;
if (waitTime != -1) {
//remainTime=4500
remainTime = (waitTime);
}
//RedissonRedLock will overload the calcLockWaitTime() method, shortening the timeout time for obtaining each small lock
//For example, the () method returns 1500
//() method returns 4500
long lockWaitTime = calcLockWaitTime(remainTime);
//RedissonRedLock will overload the failedLocksLimit() method, returning the maximum number of locks that can be allowed to fail to obtain.
//For example, if the () method returns 0, it means that a certain lock is not allowed to fail to obtain.
int failedLocksLimit = failedLocksLimit();
//acquiredLocks is used to save the acquired lock
List<RLock> acquiredLocks = new ArrayList<>(());
//Trace through the locks to be acquired in turn
for (ListIterator<RLock> iterator = (); ();) {
RLock lock = ();
boolean lockAcquired;
...
if (waitTime == -1 && leaseTime == -1) {
lockAcquired = ();
} else {
//awaitTime=4500
long awaitTime = (lockWaitTime, remainTime);
//The core method of obtaining locks (), such as () method
//If this lock cannot be acquired within awaitTime=4500 milliseconds, exit and mark it as failed to acquire the lock
lockAcquired = (awaitTime, newLeaseTime, );
}
...
if (lockAcquired) {
//After successfully obtaining the lock, add the lock instance to acquiredLocks
(lock);
} else {
//If the minimum number of successful locking is reached, you can exit the loop and return it
if (() - () == failedLocksLimit()) {
break;
}
//Failed to obtain the lock, decrement the failedLocksLimit, and return false until the failedLocksLimit is 0.
if (failedLocksLimit == 0) {
//This time the interlock is acquired, the acquired lock needs to be released.
unlockInner(acquiredLocks);
if (waitTime == -1) {
return false;
}
//Reset the value of failedLocksLimit to prepare for the next attempt to acquire all locks
failedLocksLimit = failedLocksLimit();
//Clear acquiredLocks and prepare for the next attempt to acquire all locks
();
//Reset the iterator of the lock list
while (()) {
();
}
} else {
//Decrement failedLocksLimit
failedLocksLimit--;
}
}
//Decrement the remainingTime. If the remainingTime is less than 0, it means that the interlocking failed to be acquired.
if (remainTime != -1) {
remainTime -= () - time;
time = ();
//If the remainingTime is found to be less than 0, it means that the interlocking failed to be acquired.
if (remainTime <= 0) {
unlockInner(acquiredLocks);
return false;
}
}
}
if (leaseTime != -1) {
()
.map(l -> (RedissonLock) l)
.map(l -> ((leaseTime), ))
.forEach(f -> ().join());
}
return true;
}
...
}
public class RedissonMultiLock implements RLock {
...
protected int failedLocksLimit() {
return 0;
}
protected long calcLockWaitTime(long remainTime) {
return remainsTime;
}
@Override
public void unlock() {
List<RFuture<Void>> futures = new ArrayList<>(());
for (RLock lock : locks) {
(());
}
for (RFuture<Void> future : futures) {
().join();
}
}
protected void unlockInner(Collection<RLock> locks) {
().map(RLockAsync::unlockAsync)
.forEach(f -> {
().join();
}
);
}
...
}(3) RedissonRedLock's source code summary
Locking is performed for multiple locks, each lock has a 1500 millisecond lock timeout time.
If within 1500*n milliseconds, the n/2+1 lock is successfully locked successfully. Then you can think that the RedLock is locked successfully, and it does not require that all locks be locked successfully.
Problem: RedLock should have been a lock, but it is just locked on different Master nodes. However, Redisson's RedLock implementation is implemented by merging multiple small locks. Is this inconsistent with the design of RedLock?
When using Redis Cluster, it is actually the same. Assume there are 3 Master instances, then use lock1, lock2, and lock3 keys to add lock. These three lock keys will obtain the Hash value according to CRC16 and then modulo distribution to these three master nodes. The effect is equivalent to letting each master node use a key named lock to lock.