1, What is FairLock

In the previous chapter, we output the class diagram of Redisson distributed lock core code. We can observe that FairLock is a subclass based on RedissonLock, that is, it implements some other features based on RedissonLock

Core concept

Compared with the previous ReentrantLock and the current FairLock, as the name suggests, it is obvious that it represents a fair lock. From the previous cases, it can be found that the threads competing for locks after lock failure are not controlled sequentially, but are allowed to compete, that is, unfair, and FairLock will be controlled through a series of mechanisms, The order in which locks are acquired will be the same as the order in which locks are requested

code implementation

// Get a FairLock
RLock fairLock = redissonClient.getFairLock("lockName");
// Lock
fairLock.lock();
// Release lock
fairLock.unlock();

• The implementation code is very simple. It is almost the same as ReentrantLock, except that when initializing the lock object, a redisonfairlock is initialized instead of the previous RedissonLock

Ask questions

Lock

Since FairLock can realize the locking sequence, the whole locking process will make people curious about how to lock in order to ensure the consistency of locking

• There may be a queue in redis. Use the first in first out rule of the queue to record the locked thread information
• What to do if the lock acquisition times out? We all know that there may be a waitTime when we acquire the lock. If the waitTime has been reached, how to complete the work

• If leaseTime is set, that is, the timeout lock is automatically released, what is the difference?
• How can a reentrant lock be completed in this queue? You can imagine that since it is a reentrant lock, it must be successful. You only need to compare the element holding the lock with the thread to be locked. If it is the same, it is proved that the same thread is locked, and the reentrant lock can be realized

• Another problem is that when the lock is not obtained, there will be a loop to continuously obtain the lock. At this time, we should ensure the uniqueness of the elements in the queue
• The contract renewal work completed by watchdog should be the same as before

Release lock

There are two ways to release a lock. One is to release the lock actively. Only when the lock has been held and the task is completed, the unlock command will be actively executed to release the lock; The other is passive release. The timeout lock is automatically released, that is, the leaseTime is set, but the watchdog is not started again

2, Source code analysis

initialization

// Command actuator
this.commandExecutor = commandExecutor;
// threadWaitTime: 60000 * 5 is directly initialized in the code. This time has been 5 minutes here
this.threadWaitTime = threadWaitTime;
// Queue name: reisson_ lock_ queue:{lockName}
threadsQueueName = prefixName("redisson_lock_queue", name);
// Set set name: reisson_ lock_ timeout:{lockName}
timeoutSetName = prefixName("redisson_lock_timeout", name);

Way
It can be observed that the whole initialization process is to initialize some member variables. The key points are as follows:

• threadWaitTime: 60000*5
• Queue name: reisson_ lock_ queue:{lockName}
• Set set name: reisson_ lock_ timeout:{lockName}

Similarly, we can also guess that threadWaitTime is the waiting time for obtaining locks, and then maintain a queue and a set set in redis

By reading the source code, you can find that FairLock almost always follows RedissonLock in the whole process of lock. It is found that RedissonFairLock only overloads the RedissonLock method

• tryLockInnerAsync lock
• acquireFailedAsync cancels lock acquisition
• Unlock innerasync release lock
• forceUnlockAsync force lock release

In the following time, we will take a look at these core source code processes and introduce any different mechanisms to complete queuing and locking

Lock

Lua script analysis

The core code of locking is tryLockInnerAsync, and the main core is a lua script

The following is to add some comments to this lua script according to your understanding

• lockName
• redisson_lock_queue:{lockName}
• redisson_lock_timeout:{lockName}
• uuid:threadId locked thread
• waitTime in general, waitTime = threadWaitTime = 60000*5 when waitTime locking is not set
• currentTime current time

// KEY[1] lockName
// KEY[2] threadsQueueName -> redisson_lock_queue:{lockName}
// KEY[3] timeoutSetName -> redisson_lock_timeout:{lockName}
// ARGV[1] unit.toMillis(leaseTime)
// ARGV[2] uuid:threadId 
// ARGV[3] waitTime
// ARGV[4] currentTime current time

-----------------------------------loop--------------------------------------------

//  (1) Or there are no elements and they are not processed
//  (2) Or remove the expired elements
while true do 
  // Get the first element from the queue
  // lindex redisson_lock_queue:{lockName} 0
  local firstThreadId2 = redis.call('lindex', KEYS[2], 0);
  // If you don't get it, just jump out
  if firstThreadId2 == false then
    break;
  end;
  // Go to set to get the score of the element of the team head, that is, timeout
  local timeout = tonumber(redis.call('zscore', KEYS[3], firstThreadId2));
  // If the timeout is smaller than the current time, move it out of the queue and set set
  if timeout <= tonumber(ARGV[4]) then 
    redis.call('zrem', KEYS[3], firstThreadId2);
    redis.call('lpop', KEYS[2]);
  else
    break;
  end;
end;

-------------------------------------Lock------------------------------------------

// The current lock lockName is not obtained, and the lockName queue does not exist, or the header element from the queue is locked by the same thread -- >, which means that the lock can be added
// If you can lock, this is the code
// (exists lockName == 0) and 
// ((exists redisson_lock_queue:{lockName} == 0) 
//  or (lindex redisson_lock_queue:{lockName} 0 ==  uuid:threadId))
if (redis.call('exists', KEYS[1]) == 0) 
  and ((redis.call('exists', KEYS[2]) == 0) 
    or (redis.call('lindex', KEYS[2], 0) == ARGV[2])) then 
  // remove the currently locked thread from the queue and set set
  // lpop redisson_lock_queue:{lockName}
  redis.call('lpop', KEYS[2]);
  // zrem redisson_lock_timeout:{lockName} uuid:threadId 
  redis.call('zrem', KEYS[3], ARGV[2]);
  // Get all the elements in the set set and assign them to keys
  // zrange redisson_lock_timeout:{lockName} 0 -1
  local keys = redis.call('zrange', KEYS[3], 0, -1);
  // Traverse keys
  for i = 1, #keys, 1 do 
    // The zscore setting is: score+waitTime+currentTime of the previous lock
    // Make the elements in the whole set subtract waitTime
    // zincrby redisson_lock_timeout:{lockName} -waittime keys[i]
    redis.call('zincrby', KEYS[3], -tonumber(ARGV[3]), keys[i]);
  end;
  // Locked code
  // hset lockName uuid:threadId 1
  redis.call('hset', KEYS[1], ARGV[2], 1);
  // Code to set expiration time
  // pexpire lockName leaseTime
  redis.call('pexpire', KEYS[1], ARGV[1]);
  // Return nil, lock successfully, and start a watchdog scheduling task
  return nil;
end;

-------------------------------------Reentrant lock---------------------------------------

// The thread that currently holds the lock is its own thread. Reentrant locking will come here to lock
// hexists lockName uuid:threadId 
if redis.call('hexists', KEYS[1], ARGV[2]) == 1 then 
  redis.call('hincrby', KEYS[1], ARGV[2],1);
  redis.call('pexpire', KEYS[1], ARGV[1]);
  return nil;
end;

------------------------Threads are already blocked in the queue, while Acquire lock--------------------------

// Get the score of uuid:threadId key in the set set, and then give him - waittime currenttime
// zscore is set to score+waitTime+currentTime of the previous lock
// The actual return is ttl
// zscore redisson_lock_timeout:{lockName} uuid:threadId
local timeout = redis.call('zscore', KEYS[3], ARGV[2]);
if timeout ~= false then
  return timeout - tonumber(ARGV[3]) - tonumber(ARGV[4]);
end;


-----------------------------------The first time I came here--------------------------------
// Calculates and returns the ttl of the last thread in the queue and adds it to the queue and set collection

// Gets the last element in the queue
// lindex threadsQueueName -1
local lastThreadId = redis.call('lindex', KEYS[2], -1);
local ttl;
// Judge that the last element in the queue is not empty and is not equal to uuid:threadId
if lastThreadId ~= false and lastThreadId ~= ARGV[2] then
  // zscore redisson_lock_timeout:{lockName} lastThreadId - current time
  ttl = tonumber(redis.call('zscore', KEYS[3], lastThreadId)) - tonumber(ARGV[4]);
else 
  // Only the elements in the queue are empty
  // pttl lockName
  ttl = redis.call('pttl', KEYS[1]);
end;

// timeout = ttl + waitTime + currentTime
local timeout = ttl + tonumber(ARGV[3]) + tonumber(ARGV[4]);
// Setting the elements in the set collection will bring a timeout as the score
// zadd redisson_lock_timeout:{lockName} timeout uuid:threadId 
if redis.call('zadd', KEYS[3], timeout, ARGV[2]) == 1 then
  // Set the waiting thread to the queue
  // rpush redisson_lock_queue:{lockName} uuid:threadId 
  redis.call('rpush', KEYS[2], ARGV[2]);
end;

// Return ttl
return ttl;

Flow chart of locking

From the general flow chart, we can cite several situations:

• Lock for the first time: directly enter the hash key holding lockName
• The lock has been held. You can re-enter the lock: directly enter the counter+1 in the hash key to reset the expiration time

• The lock has been held, and the competitive lock appears for the first time: obtain the hash expiration time + waitTime + currentTime1 of lockName, and set timeout to the queue and set collection

Suppose 10ms has passed in the middle, that is, currentTime2 - currentTime1 = 10ms

• The lock has been held, and a competitive lock occurs for the second time: first obtain the queue elements, judge whether the timeout time of each element is smaller than currentTime2, and move the smaller one out; Obtain the timeout1 - currentTime2 of the last competitive lock. At this time, the maximum ttl is equal to the timeout1 set last time minus 10ms. This time, timeout2=ttl + waitTime + currentTime2, which ensures that the returned ttl decreases with time and that timeout2 must be larger than timeout1
• The lock has been held, and the competitive lock that appears for the first time comes again: first obtain the queue elements, judge whether the timeout time of each element is smaller than currentTime2, and move the smaller ones out; Directly return the timeout - waitTime - currentTime of the lock. What does it mean? It means that the second time to obtain the lock is the time of waitTime, and the corresponding is ttl

• The lock has been held for a long time, and the competitive lock comes again for the first time: first obtain the queue elements, judge whether the timeout time of each element is smaller than currentTime2, and move the smaller one out. Here, think about his initial timeout = ttl+waitTime+currentTime1 of lockname. Now the second time is ttl - time difference, That is, if the lock is not obtained within the ttl time when the lock is held, this element will be remove d from the queue and set set, and the timeout of other set set set elements will subtract the released waitTime
• The lock is released, and the thread that locks the second time comes: at this time, it is found that there are elements in the queue and compete for the lock again. The same lock has been held, and the competing lock that appears for the first time comes again

• When the lock is released, the queue header element comes: delete the elements in the queue and set set, enter the lock logic, and subtract one waitTime from the elements in set

Locking scenario

I simply drew the sequence diagrams of several scenes with locks - ha ha pseudo sequence diagrams. At first, I didn't think about how to draw them

Features in fair locking

Queue locking

Queuing locking is also the main difference between fair locks and rlocks. Locks can be obtained according to the order in which locks are requested

The core is to introduce a queue to store the order of obtaining locks, and control the timeout of locks by maintaining a zset ordered set

• If there is lock competition, the lock will be queued. At the same time, by setting a timeout time, it should be noted that the timeout time will be relatively large, plus a waitTime=60000 × 5 minutes, 5 minutes
• At the same time, if the first data in the queue is locked successfully, then the timeout of each element behind it needs to be subtracted. In fact, I think it can be understood that if a lock is not obtained for 5 minutes + ttl at most, it means failure
• Others are the same as RLock. If the lock is successfully added, the lease term will be renewed through a watchdog
• When locking fails, it will enter a loop to try to obtain the lock

Acquire lock timeout auto release lock

• Every time a request to acquire a lock comes in, it will start from the queue header to find whether there is a timeout. If the timeout occurs, it will be removed from the queue and zset collection
• The timeout is only removed from the redis queue and zset. At this time, if the background while loop obtains the lock again, it will rejoin the queue

Auto refresh timeout

• If a lock is successfully locked, you need to subtract the waitTime from the set in zset and refresh the score

Lock release

From the code structure, we can see that the actual release of locks is the reconstruction of the org.redisson.RedissonFairLock#unlockInnerAsync method

The core is also a lua script

-----------------------------------loop--------------------------------------------

//  (1) Or there are no elements and they are not processed
//  (2) Or remove the expired elements
while true do 
  local firstThreadId2 = redis.call('lindex', KEYS[2], 0);
  if firstThreadId2 == false then 
    break;
  end; 
  local timeout = tonumber(redis.call('zscore', KEYS[3], firstThreadId2));
  if timeout <= tonumber(ARGV[4]) then 
    redis.call('zrem', KEYS[3], firstThreadId2); 
    redis.call('lpop', KEYS[2]); 
  else 
    break;
  end; 
end;


----------------------------What is to be released is not held--------------------------------------

if (redis.call('exists', KEYS[1]) == 0) then 
  local nextThreadId = redis.call('lindex', KEYS[2], 0); 
  if nextThreadId ~= false then 
    redis.call('publish', KEYS[4] .. ':' .. nextThreadId, ARGV[1]); 
  end; 
  return 1; 
end;


----------------------------If the person holding the lock is not himself----------------------------------
if (redis.call('hexists', KEYS[1], ARGV[3]) == 0) then 
  return nil;
end; 

---------------------------If it is a reentrant lock count-1---------------------------------
local counter = redis.call('hincrby', KEYS[1], ARGV[3], -1); 
if (counter > 0) then 
  redis.call('pexpire', KEYS[1], ARGV[2]); 
  return 0;
end; 

---------------------------If the lock held is released, a broadcast message is sent----------------------
redis.call('del', KEYS[1]); 
local nextThreadId = redis.call('lindex', KEYS[2], 0); 
if nextThreadId ~= false then 
  redis.call('publish', KEYS[4] .. ':' .. nextThreadId, ARGV[1]); 
  end; 
return 1; 
    

• If the person holding the lock is not himself, null will be returned, and the failure to release the lock will be directly returned in the code
• If the lock is released successfully or the released lock is not held, that is, another thread is required to lock, a message will be sent and 1 will be returned
• If the lock is released successfully, but the lock is re entered, count-1 is returned and 0 is returned

Mainly, if null is not returned, it means that the lock is released successfully

That's all about the core fair lock knowledge. I mainly looked at the lua scripts for locking and releasing locks in detail, as well as the process of releasing locks