Yige

Distributed Lock#

Content from

1. Geek Time Column: “Principles and Algorithm Analysis of Distributed Technology”
2. If someone asks you about distributed locks again, throw this article at them
3. This article is enough to understand distributed locks

I. Basic Concepts#

A distributed lock refers to a lock that implements distributed mutual exclusion in a distributed environment where the system is deployed across multiple machines. To ensure that multiple processes can see the lock, it is stored in a shared storage (such as Redis, Memcache, databases, etc.), allowing multiple processes to concurrently access the same critical resource, with only one process able to access the shared resource at any given time, ensuring data consistency.

Application Scenarios#

• Improving performance and efficiency: Using distributed locks can avoid different nodes repeating the same work, which wastes resources. For example, after a user pays, different nodes may send multiple text messages.
• Ensuring data correctness: Adding distributed locks can also prevent correctness issues. If two nodes operate on the same data, such as multiple nodes processing different workflows on the same order, it may lead to incorrect final states for the order, resulting in losses.

Characteristics of Distributed Locks#

• Mutual Exclusion: Like local locks, mutual exclusion is fundamental, but distributed locks need to ensure mutual exclusion across different threads on different nodes.
• Reentrancy: If the same thread on the same node acquires the lock, it can also acquire the lock again.
• Lock Timeout: Like local locks, it supports lock timeouts to prevent deadlocks.
• High Efficiency, High Availability: Locking and unlocking need to be efficient, while also ensuring high availability to prevent distributed lock failures, which can include degradation.
• Supports Blocking and Non-blocking: Similar to ReentrantLock, it supports lock and tryLock as well as tryLock(long timeOut).
• Supports Fair and Non-fair Locks (optional): Fair locks mean acquiring locks in the order of requests, while non-fair locks are unordered. This is generally implemented less frequently.

Considerations for Using Distributed Locks#

1. Be aware of the overhead of distributed locks.
2. Pay attention to the granularity of locking.
3. Locking methods.

Implementation of Distributed Locks#

• Database-based implementation of distributed locks, referring to relational databases (MySQL).
• Redis-based implementation of distributed locks.
• ZooKeeper-based implementation of distributed locks.
• Other middleware implementations, such as Consul.

II. Database-based Implementation of Distributed Locks#

Unique Implementation Based on Table Primary Key#

Utilizing the uniqueness of the primary key, if multiple requests are submitted to the database simultaneously, the database will ensure that only one operation can succeed. Thus, we can consider that the thread that successfully performs the operation has acquired the lock for that method. After the method execution is complete, to release the lock, simply delete this database record.

Disadvantages#

1. Strong dependency on database availability, leading to a single point of failure.

   Copy

   Improvement Idea: Design a high availability solution for master-slave databases.
   

2. No expiration time limit; for example, if the lock release fails to delete the database record, it can lead to blocking.

   Copy

   Improvement Idea: Implement a scheduled task to periodically clean up expired data in the database.
   

3. Only supports non-blocking, as acquiring the lock is done through a database insert operation. If the operation fails, it can only request the lock again.

   Copy

   Improvement Idea: Refer to the idea of spin locks, using an outer while loop to keep inserting until successful.
   

4. Does not support reentrant operations; the same thread cannot acquire the lock again before releasing it, as a unique record already exists in the data.

   Copy

   Improvement Idea: Borrow the implementation idea of ReentrantLock, adding a field to record the host information and thread information of the machine that currently holds the lock. When trying to acquire the lock again, check the database; if the current machine's host information and thread information can be found in the database, the lock can be directly assigned to it.
   

5. Non-fair lock; whether one can acquire the lock is purely a matter of luck.

   Copy

   Improvement Idea: Create an intermediate table to record all threads waiting for the lock, sorted by creation time, allowing only the first created to acquire the lock.
   

6. Using primary key conflict prevention in MySQL may cause lock phenomena under high concurrency.

   Copy

   Improvement Idea: Generate primary keys in the program rather than relying on the database to automatically generate primary keys for prevention.
   

Implementation Based on Table Field Version Number#

This strategy is derived from MySQL's MVCC mechanism. There is actually no problem with using this strategy, but the only issue is that it is quite invasive to the data table. We need to design a version number field for each table and write a judgment SQL each time, increasing the number of database operations, which is unbearable under high concurrency requirements.

Distributed Lock Based on Database Exclusive Lock#

By adding for update to the query statement, the database will add an exclusive lock to the database table during the query process. Once a record is locked, other threads cannot add an exclusive lock on that row. The thread that obtains the exclusive lock can acquire the distributed lock. After acquiring the lock, it can execute the business logic of the method, and after the method execution is complete, the lock can be released through the connection.commit() operation.
Note: InnoDB engine uses row-level locks only when searching through indexes; otherwise, it will use table-level locks. If we want to use row-level locks, we need to add indexes to the fields of the method to be executed. It is worth noting that this index must be created as a unique index; otherwise, there will be issues with multiple overloaded methods being accessed simultaneously. For overloaded methods, it is recommended to also include parameter types.

Analysis#

This solves the timeout release and blocking lock issues of the unique implementation based on table primary key:

• The for update statement will return immediately after successful execution, while it will remain in a blocking state until successful if it fails.
• Using this method, if the service crashes, the database will automatically release the lock.

Disadvantages:

• Still cannot directly solve the single point of failure and reentrancy issues.
• There may be performance issues: MySQL optimizes queries, and even if an index field is used in the conditions, whether to use the index for data retrieval is determined by MySQL based on the cost of different execution plans. If MySQL determines that a full table scan is more efficient, such as for very small tables, it will not use the index. In this case, InnoDB will use table locks instead of row locks.
• Using exclusive locks for distributed locks means that if an exclusive lock is not committed for a long time, it will occupy the database connection. Once similar connections become numerous, it may overwhelm the database connection pool.

III. Redis-based Implementation of Distributed Locks#

Distributed Lock Using Redis's setnx() and expire() Methods#

setnx()
The meaning of setnx is SET if Not Exists, which mainly has two parameters setnx(key, value). This method is atomic; if the key does not exist, it successfully sets the current key and returns 1; if the current key already exists, it fails to set the current key and returns 0.

expire()
Expire sets the expiration time. It is important to note that the setnx command cannot set the timeout for the key; it can only be set through expire().

Steps

1. setnx(lockkey, 1) If it returns 0, it indicates that the occupation failed; if it returns 1, it indicates that the occupation was successful.
2. The expire() command sets the timeout for lockkey to avoid deadlock issues.
3. After executing the business code, the key can be deleted using the delete command.

Note
If a crash occurs after the first step setnx() is successfully executed but before the expire() command is executed successfully, a deadlock issue may still arise.

Distributed Lock Using Redis's setnx(), get(), and getset() Methods#

This solution is mainly an optimization of the setnx() and expire() scheme to address potential deadlock issues.

getset()
This command mainly has two parameters getset(key, newValue). This method is atomic; it sets the key to newValue and returns the old value of the key. Assuming the key originally does not exist, executing this command multiple times will yield the following effects:

• getset(key, "value1") returns null, at this point the key's value will be set to value1.
• getset(key, "value2") returns value1, at this point the key's value will be set to value2.
• And so on.

Steps

1. setnx(lockkey, current time + expiration timeout), if it returns 1, the lock is successfully acquired; if it returns 0, the lock was not acquired, proceed to step 2.
2. get(lockkey) retrieves the value oldExpireTime, and compares this value with the current system time. If it is less than the current system time, it is considered that this lock has timed out, allowing other requests to re-acquire it, proceed to step 3.
3. Calculate newExpireTime = current time + expiration timeout, then getset(lockkey, newExpireTime) will return the current lockkey's value currentExpireTime.
4. Check if currentExpireTime equals oldExpireTime; if they are equal, it means the current getset was successful, and the lock was acquired. If not, it means this lock has been acquired by another request, and the current request can either return failure or continue to retry.
5. After acquiring the lock, the current thread can start its business processing. After processing, compare its processing time with the lock's set timeout. If it is less than the lock's set timeout, directly execute delete to release the lock; if it exceeds the lock's set timeout, no further processing is needed.

Other Extended Solutions#

1. Distributed locks based on Redlock.
2. Distributed locks based on redisson, GitHub link.

IV. ZooKeeper-based Implementation of Distributed Locks#

Basic Knowledge Related to ZooKeeper Locks#

• ZooKeeper generally consists of multiple nodes (odd number), using the ZAB consistency protocol. Therefore, ZooKeeper can be seen as a single point structure; when modifying data, it automatically updates all nodes' data internally before providing query services.
• ZooKeeper's data is in the form of a directory tree, with each directory called a znode. A znode can store data (generally not exceeding 1M) and can also have child nodes.
• There are three types of child nodes. Sequential nodes automatically increment the name of the node when a new node is added under it. Temporary nodes are automatically deleted when the client that created this znode loses contact with the server. Finally, there are ordinary nodes.
• Watch mechanism, clients can monitor changes to each node, and when changes occur, an event is generated for the client.

Basic Scheme#

• Principle: Utilize temporary nodes and the watch mechanism. Each lock occupies a normal node /lock. When a lock is needed, a temporary node is created under the /lock directory. If creation is successful, it indicates that the lock has been successfully acquired; if it fails, watch the /lock node and wait for a delete operation before contending for the lock. The advantage of temporary nodes is that when a process crashes, the automatically deleted nodes cancel the lock.
• Disadvantages: All processes that fail to acquire the lock listen to the parent node, which can easily lead to a herd effect, where all waiting processes create nodes simultaneously after the lock is released, resulting in high concurrency.

Optimization Scheme#

Principle#

Change the locking to create temporary sequential nodes. Each locking node can successfully create a node, but with different sequence numbers. Only the node with the smallest sequence number can hold the lock. If this node's sequence number is not the smallest, it watches the previous node with a smaller sequence number (fair lock).

Steps#

1. Create a sequential temporary node (EPHEMERAL_SEQUENTIAL) under the /lock node. Check if the created node's sequence number is the smallest; if it is, the lock is successfully acquired. If not, the lock acquisition fails, and it watches the previous node with a smaller sequence number.
2. When lock acquisition fails, after setting the watch, wait for the watch event to arrive, then check again if the sequence number is the smallest.
3. If the lock is successfully acquired, execute the code, and finally release the lock (delete the node).

V. Security Issues of Distributed Locks#

Reference Links#

• Martin's article How to do distributed locking
• Is the distributed lock based on Redis really safe? (Part 1)
• Is the distributed lock based on Redis really safe? (Part 2)

GC's STW (stop-the-world)#

The Java virtual machine may experience STW phenomena during garbage collection, meaning a global pause. For example, the CMS garbage collector has two phases to prevent references from continuing to change. This may lead to the following situation:

As shown in the figure: Client 1 holds the lock but experiences a long GC pause. During this time, the lock it holds expires, and Client 2 acquires the lock. When Client 1 recovers from the GC pause, it is unaware that its lock has expired and still sends write requests to the shared resource (in the figure, a storage service), while the lock is actually held by Client 2. Therefore, the write requests from both clients may conflict (the mutual exclusion of the lock is ineffective).

Clock Jump#

Assuming there are 5 Redis nodes A, B, C, D, E:

1. Client 1 successfully acquires the lock from Redis nodes A, B, C (the majority). Due to network issues, communication with D and E fails.
2. The clock on node C jumps forward, causing the lock it maintains to expire quickly.
3. Client 2 successfully acquires the lock for the same resource from Redis nodes C, D, E (the majority).
4. Client 1 and Client 2 now both believe they hold the lock.

This example illustrates that if the expiration mechanism of the lock heavily relies on time, once the system's clock becomes inaccurate, the security of the algorithm cannot be guaranteed. However, distributed locks implemented based on ZooKeeper do not rely on time but rather on the session of each node.

Long Network Delays#

In a distributed system, network issues are unavoidable. Long network delays can create situations similar to the above two problems, where Node A has acquired the lock, but due to network delays exceeding the timeout limit, it becomes invalid. At this point, Node B requests to acquire the lock, and when Node A recovers, it is unaware that the lock has expired, leading to a conflict between A and B.