From pessimistic locks, optimistic locks to distributed locks

preface

When we design goods down the module in order to prevent “inventory” oversold condition, we often use a lock mechanism and solve the problem of data consistency under the multithreading, but in the distributed cluster order node locks are often unable to meet the needs of the business, this blog since pessimistic locking, optimistic locking, gradually introduce distributed data consistency – the most effective tools for distributed lock.

The body of the

Pessimistic locks and optimistic locks

The difference between pessimistic and optimistic locks:

  • Pessimistic locking: a piece of execution logic with a pessimistic lock. When different threads are executing at the same time, only one thread can execute it. The other threads wait at the entrance until the lock is releasedsychronizedPessimistic locks are provided
  • Optimistic lock: a piece of execution logic plus optimistic lock, when different threads execute at the same time, can enter the execution at the same time, in the last update of data to check whether the data has been modified by other threads (version and the initial execution is the same), the update, otherwise abandon this operation.

Common solutions for pessimistic and optimistic locking are:

Java

  • Pessimistic locks:synchronizedorReentrantLock
  • Optimistic locking:java.util.concurrent.atomicThe atomic variable

Mysql

  • Pessimistic locks:for update
  • Optimistic lock: timestamp orversionThe version number

Redis

  • Pessimistic lock: none
  • Optimistic lock: usewatchMonitor object changes to achieve optimistic locking

Zookeeper

  • Pessimistic lock: none
  • Optimistic lock: useversionVersion numbers implement optimistic locking

A distributed lock

Sometimes we need to ensure that a method can only be executed by the same thread at the same time. In single-machine mode, it can be implemented by sychronized, lock, etc.

Three actions for a distributed lock:

  • lock
  • unlock
  • Lock expired

Implementation of distributed lock solutions

Database lock scheme

  • Determine resource usage based on a record in a table
  • Use database-based exclusive locks (i.eselect * from tb_User for update)
  • The way optimistic locks are used, i.eCASActions (orversionField)

Redis scheme

Redis distributed locks have three behaviors:

  • lockUse:setnxTo rob the lock, set the lock identifier to 1 to indicate that the lock is occupied.
  • unlockUse:setnxTo release the lock and set the lock identifier to 0 to indicate that the lock has been released.
  • Lock expired:expireAdd an expiration date to the lock in case it forgets to release,expireTime expiration returns 0.

Setnx and EXPIRE are atomic operations, and in practice lua scripts are used to ensure atomicity.

Redis can cause data inconsistency in some extreme cases:

Case 1: The master is down

  1. redis clusterIn A clustered environment, if client A wants to lock now, it will select one based on routing rulesmasterNode writeskey mylockAfter the lock is successfully added,masterThe node tokeyAsynchronously copy to correspondingslaveNode.
  2. If at this timeredis masterWhen the node is down, an active/standby switchover is performed to ensure cluster availability.slaveInto theredis master. B Client in the newmasterThe node is successfully locked, and client A thinks it is successfully locked.
  3. In this case, multiple clients lock a distributed lock at the same time, resulting in various dirty data.

Case two: The lock expires and the business is not finished

A special scenario causes slow service processing, but the lock expires and data is modified by other threads, resulting in dirty data.

Case 3: The transaction times out because the lock is not obtained for a long time

Transaction timeout Is used to control the timeout of transaction execution. The execution time is the sum of all code executions within a transaction, in seconds. The default value is -1, which indicates that the transaction will never timeout. If the timeout period is set for some services, the transaction will be automatically rolled back if the lock cannot be obtained for a long time.

Case 4: THE lock of B is released by A

Simulation scenario:

  • A, B two threads to try to givekey myLockThread A takes the lock first (if the lock expires after 3 seconds) and thread B waits to try to acquire the lock.
  • If the business logic is time consuming, the execution time has expiredredisWhen the lock expires, the lock of thread A is automatically released (deleted)key), thread B has detectedmyLockthiskeyNone, execute

    SETNXThe command also got the lock.
  • However, thread A will still release the lock (delete) after executing the business logickey), which causes thread B’s lock to be released by thread A.

Solution: Each thread must be identified with its own value when locking, and only release the key of the specified value. Otherwise, the scene of chaotic lock release will occur.

Redisson scheme

Redisson is an enterprise-level open source Redis Client that also provides distributed lock support:

  • RedissonAll orders passedluaScript execution, whileluaScripts support atomic execution;
  • Assuming thatRedissonSet up akeyThe default expiration time of theRedisson“Guard dog” mechanism, it will be after you acquire the lock, every 10 seconds for youkeyIn this case, the lock will not appear even if it is held all the timekeyExpired, another thread is getting the lock.
  • RedissonThe “watchdog” logic of the “watchdog” ensures that no deadlocks occur: if the machine goes down, the watchdog is gone. It’s not going to be prolongedkeyAfter 30 seconds, the lock will automatically expire. Other threads can obtain the lock.

RedLock scheme

RedLock is a distributed lock algorithm implemented by multi-node Redis, which can solve the mutual exclusion failure caused by inconsistent data when the master is down under asynchronous master/slave replication in Redis sentry mode.

RedLock’s algorithm features:

  • synchronous:RedLockBecause eachredisThe time flow rate is about the same, soRedLockYou can think of it as a synchronous algorithm;
  • The mutex: Only one at any timeclientAcquiring a lock;
  • Release deadlock: The lock can be released even if the service or partition that locks the resource crashes.
  • Fault tolerance: As long as mostredisNodes (more than half) are in use,clientCan acquire and release locks;

Suppose there are five completely independent Redis primary servers:

  1. Get the current timestamp;
  2. clientTry using the same ones in orderkey.valueGet all theredisThe lock of a service is acquired for a much shorter time than the lock expires in order not to wait too long for closed locksredisService. And try to get the next oneredisInstance. Such as:TTLAs 5s, set the maximum duration of acquiring the lock to 1s. Therefore, if the lock cannot be acquired within a second, the lock will be abandoned and the next lock will be attempted.
  3. clientBy taking all available locks minus the time of the first step, the time difference is less thanTTLTime and at least threeredisOnly when the instance successfully obtains the lock, the lock is successfully obtained.
  4. If the lock is successfully acquired, the lock’s true duration isTTLSubtract the time difference of step 3; Such as:TTLIs 5s. It takes 2s to acquire all the locks, minus clock drift (which can be ignored in practice), so the actual lock duration is 3s.
  5. If the client fails to acquire the lock for some reason, it starts unlocking everythingredisInstance; Because less than 3 locks may have been acquired, they must be released or others will be affectedclientAcquiring a lock;

TTL: redis key expiration time or validity time

Clock drift: Refers to the difference in time between two computers (or between two processes) when the time flow rate between two computers is basically the same; If the computer is too far away, the clock drift value will be too large

Zookeeper scheme

Zookeeper distributed lock features:

  • Based on thezookeeperTemporary ordered nodes can achieve distributed locking. The general idea is that when each client locks a method, the value ofzookeeperIn the directory of the specified node corresponding to the method, a unique instantaneous ordered node is generated.
  • The way to determine whether to obtain the lock is very simple, just need to determine the smallest serial number in the ordered node. When the lock is released, the instantaneous node is simply removed.
  • CuratorIs azookeeperOpen source client, also provides distributed lock implementation;

The algorithm flow of distributed lock using ZooKeeper is as follows:

  1. If the root node of the lock space does not exist, it is created firstZnodeThe root node. So let’s say that this is”/test/lock“. This root node represents a distributed lock.
  2. If the client needs to occupy the lock, the/test/lock“To create temporary and ordered child nodes.
  3. If a client needs to occupy a lock, it also needs to check whether the child node created by the client is the child node with the smallest serial number in the current child node list. If yes, the lock is considered acquired, otherwise listen on the previous oneZnodeChild node change message, after obtaining the child node change notification, repeat this step until obtaining the lock;
  4. Once the lock is acquired, the business process is processed. After the service process is complete, delete the child node to release the lock. So that subsequent nodes acquire distributed locks.

Differences between Redis distributed lock and Zookeeper distributed lock

  • redisDistributed lock, in fact, you need to constantly try to obtain the lock, compared to consume performance;
  • zookeeperDistributed lock, can not obtain the lock, register a listener, do not need to constantly actively try to obtain the lock, low performance overhead;
  • redisThe client that acquires the lockbugThe lock can only be released after the timeout period. whilezkBecause it’s temporaryznodeAs soon as the client dies,znodeThen it will automatically release the lock;
  • redisChoice is usedRaftAlgorithm but it itself adopts asynchronous replication, so its data is not strong consistency, some extreme cases will lead to data inconsistency, but can be adoptedRedissonScheme,RedLockProgrammes to reduce the impact of these extremes;
  • zookeeperUsing thePaxosThe algorithmzabThe protocol ensures strong consistency of data.