Personal blog: iyuhp.top original text link: Redis Lock

Redis Lock

When we want to involve a distributed lock through Redis, the first thing we must think of is the strings set command:

set r_lock random_value PX 10000 NX	
Copy the code
  • R_lock: key, lock name, can be any value
  • Random_value: a unique value given when the client sets the lock
  • PX: Expiration time, milliseconds, 10 s here
  • NX: not exist, that is, the key r_log will succeed only when it does not exist

When the client obtains the lock, run this command. If the command succeeds, the client obtains the lock.

What’s wrong with this implementation?

  1. After client A obtains the lock, the lock is not released in A timely manner due to A long service processing period or other reasons, and the lock is automatically released after A timeout. Client B obtains the lock. When the service processing is complete, the lock is released.

  2. After the client obtains the lock, it hangs directly…

  3. After Client A obtains the lock release, other waiting clients cannot know this information in time, and they still wait for A fixed polling time

  4. There should be a mechanism for reentrant for the same thread

  5. Client A obtains the lock and sets the timeout period to 15 seconds, but the actual service processing time is 20 seconds. Client A is ok, but after 15s, the lock is still released…

  6. In Redis cluster mode, Client C1 obtains the lock from Redis server A. Redis server A is down and data has not been synchronized to slave_A. Slave_A is selected as master.

For the first problem, we can solve it with random_value. For each attempt to release the lock, verify the value set first. If the value is consistent, the DEL operation is allowed. So when A tries to release the lock, it can’t delete the lock belonging to B because the value has already changed. The delete action, which should be an atomic operation, can be described using the following Lua script:

if redis.call("get", KEYS[1]) == ARGV[1]  then
    return redis.call("del", KEYS[1])
else
    return 0
end
Copy the code

For problem two, a deadlock occurs if nothing else is done. We can solve this problem by adding an expiration time to the lock. Even if the client is offline, the lock will be deleted by Redis after the lock period expires. Other clients can continue to acquire the lock. PX 10000 to set the expiration time

For problem three, it can be understood as an optimization of the lock picker mechanism, which is solved by pub/sub in Redisson. Redisson listens for the channel redisson_lock__channel:{r_lock} on the first attempt to acquire the lock, if it does not obtain it.

The client that has obtained the lock publishes a publish redisson_LOCK__channel :{_lock_} 1 message after the lock is used up. After receiving the message, the waiting client can continue to compete without waiting for the next polling

In redisson’s implementation, instead of using the set primitive, hSET, field is the id of the current thread. In this case, when the lock is acquired by a thread, I increment the value of the field by one, and when I release the lock, I decrease it by one until it reaches zero, then I delete the key.

For problem 5, in Redisson, the expiration problem is handled by starting a Timer:

private <T> RFuture<Long> tryAcquireAsync(long leaseTime, TimeUnit unit, long threadId) {
        if(leaseTime ! = -1) {
            return tryLockInnerAsync(leaseTime, unit, threadId, RedisCommands.EVAL_LONG);
        }
        RFuture<Long> ttlRemainingFuture = tryLockInnerAsync(commandExecutor.getConnectionManager().getCfg().getLockWatchdogTimeout(), TimeUnit.MILLISECONDS, threadId, RedisCommands.EVAL_LONG);
        ttlRemainingFuture.onComplete((ttlRemaining, e) -> {
            if(e ! =null) {
                return;
            }

            // lock acquired
            if (ttlRemaining == null) {
                // This method eventually starts a Timer to handle key expiration issuesscheduleExpirationRenewal(threadId); }});return ttlRemainingFuture;
    }
Copy the code

As you can see, when leaseTime is not -1, which is when we execute lock(), the timeout is set, such as lock.lock(15, timeunit.seconds); , Redisson does not delay the key.

If no, the following methods are executed:

Timeout task = commandExecutor.getConnectionManager().newTimeout(new TimerTask() {
            @Override
            public void run(Timeout timeout) throws Exception {
                // ...
                RFuture<Boolean> future = renewExpirationAsync(threadId);
                // ...
            }
        }, internalLockLeaseTime / 3, TimeUnit.MILLISECONDS);
Copy the code

InternalLockLeaseTime (configurable CFG setLockWatchdogTimeout 45 * 1000 (l);) The default value is 30s. In this case, 1/3 is 10s(in this case, 15s). That is, the execution is performed every 10s(15s) until the current thread finishes

For the last problem, Redis gives an algorithm called redLock, see here. In Redisson, the corresponding implementation is redLock.

According to the algorithm, in order to avoid question 6, every time we acquire locks, we need to acquire locks of more than half of the masters in the cluster, that is, we need to apply for locks on more than half of the masters, and only when more than half, the action of acquiring locks is considered successful.

However, this approach is cumbersome to implement, and although Redisson provides the implementation, it is still cumbersome to use in practice. If such a low probability event is intolerable, consider zK or another more reliable distributed lock.

LRU

A. least recently used B. least recently used Common middleware, the basic will have their own LRU algorithm, used to reclaim memory.

Redis can pass

maxmemory 100m

This configuration to limit memory usage, on 64-bit systems, defaults to 0, i.e. unrestricted memory, on 32-bit systems to 3G

When the specified memory limit is reached, Redis uses different policies to perform different reclamation behaviors, which can be passed

maxmemory-policy

Redis provides the following options:

  • The iction of iction is designed not to be noevicted. In this case, Redis will return an error for the operation of adding memory, and operations such as DEL can be performed normally
  • Allkeys-lru: lru for allkeys
  • Volatile – LRU: LRU is performed only for keys whose expiration time is set
  • Allkeys-random: Randomly clears parts of allkey sets
  • Volatile -random: Randomly clears parts of the key that are set to expire
  • Volatile – TTL: Clears the parts of the key set with the short TTL

Setting expiration times for keys also consumes memory, so using allkeys-lRU is more efficient

The LRU in Redis is not a complete LRU. It does not scan all the keys according to the policy, but scans the keys of the number of samples for LRU. The sample size can be configured:

Maxmemory-samples 5 # 5 is the redis default

This does not really achieve LRU, but it does reduce memory consumption

We can resize this value at run time by using config set maxmemory-samples 10. Ten samples, according to the data given by Redis, are very close to the real LRU

Now let’s actually do it:

➜ scripts-redis./run.sh cli Connecting to Redis Server... Connected to 7000 127.0.0.1:7000> 127.0.0.1:7000> 127.0.0.1:7000> CONFIG GET maxmemory-policy 1)"maxmemory-policy"
2) "noeviction"127.0.0.1:7000 > CONFIGsetMaxmemory-policy allkeys-lru OK 127.0.0.1:7000> CONFIG GET maxmemory-policy 1)"maxmemory-policy"
2) "allkeys-lru"
Copy the code

As you can see, the maxmemory-policy for the cluster has changed to AllKeys-LRU

We can use the LRU test tool provided by Redis to test:

redis-cli -a 123456 -p 7000 --lru-test 1000000
Copy the code

I was gonna post a post-run log, but…

➜ scripts - redis sudo grep"Out of memory" /var/log/messages
[sudo] password for dylan:
Apr 15 12:12:11 iZbp10xxkuq2vc7q4vabqtZ kernel: Out of memory: Killed process 16397 (redis-cli) total-vm:452400kB, anon-rss:431280kB, file-rss:0kB, shmem-rss:0kB
Copy the code

Well, one gigabyte of ram, excluding other processes, is only about 450M usable… I’m not running!

If you are interested, you can run and see how much the miss is

Expires

Redis common command about expiration

  • Expire key seconds: expire after specified seconds: expire key 10

  • Pexpire key milliseconds: Expire after specified milliseconds: expire key 10000

  • Expireat key seconds-timestamp: expireat key 1586868680 expires after the specified timestamp is set in seconds

  • Pexpiread key milliseconds-timestamp: expireat key 1586868680000

  • Persist key: The expiration time of a key: persist key

  • TTL/PTTL key: Displays the expiration time of the key

    • -1: the key exists and the expiration time is not set
    • -2: The key does not exist or has expired

When will Redis recycle the key?

  • Each time a user accesses a key, the user checks whether the key expires and deletes the key after the expiration. This is also called lazy deletion
  • When redis starts, a cron is created and some expired keys are cleaned periodically, 10 times /s by default. That’s what they sayPeriodically delete
    • Redis randomly selects 10 keys (based on the configuration)maxmemory-samplesSure)
    • Delete expired keys
    • If the number of expired keys exceeds 25% of the sample, repeat step 1 until it is less than 25%

One More Thing

Several common caching algorithms

  • LRU: Least recently used, will be eliminated
  • LFU: The least frequently used, the least frequently used, is eliminated
  • FIFO: First in first out

Let’s assume a queue of fixed length 3 and store data 1, 2, and 3 in sequence. The queue is as follows:

head <- 3 <- 2 <- 1 <- tail
Copy the code

Then clients access 1,1,3,3,2, and the queue order becomes:

head <- 2 <- 3 <- 1 <- tail # LRU organizes data
head <- 3 <- 1 <- 2 <- tail # LFU organizes data
Copy the code

At this time, according to LRU, data 1 will be eliminated, while according to LFU, because data 2 is accessed only once during this period, data 2 will be eliminated

Sweat_smile:

Reference

Redis CN LRU

Read More

MySQL LRU implementation