Yige

Distributed Lock#

Content from

1. Geek Time Column: “Principles and Algorithm Analysis of Distributed Technology”
2. If someone asks you about distributed locks, throw this article at them
3. This article is enough for understanding 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 common 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 of the order, causing 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 acquire the lock again.
• Lock Timeout: Supports lock timeout like local locks to prevent deadlocks.
• High Efficiency, High Availability: Locking and unlocking need to be efficient, while also ensuring high availability to prevent distributed lock failure, which may require degradation.
• Supports Blocking and Non-blocking: Similar to ReentrantLock, it supports lock, tryLock, and 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 less implemented.

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. We can consider the thread that successfully performs the operation as having 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 for high availability with master-slave database.
   

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 re-request the lock.

   Copy

   Improvement Idea: Refer to the concept of spin locks, using an outer while loop for insert operations 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 from the implementation idea of ReentrantLock, adding a field to record the host 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 and thread information can be found in the database, directly assign the lock 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. In MySQL, using primary key conflict prevention 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 conflict prevention.
   

Implementation Based on Table Field Version Number#

This strategy originates from the MVCC mechanism of MySQL. Using this strategy is not inherently problematic; 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 statement for each check, increasing the number of database operations, which is unsustainable 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 to that row. The thread that obtains the exclusive lock can then acquire the distributed lock. After obtaining the lock, it can execute the business logic of the method, and upon completion, release the lock through the connection.commit() operation.
Note: InnoDB engine uses row-level locks only when searching through indexes; otherwise, it uses table-level locks. To ensure row-level locks, we need to add indexes to the fields of the method to be executed. It is important 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 include the parameter types as well.

Analysis#

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

• The for update statement will return immediately upon successful execution and remain blocked until success if it fails.
• Using this method, if the service crashes, the database will automatically release the lock.

Shortcomings:

• Still cannot directly solve the single point of failure and reentrancy issues.
• Potential performance issues: MySQL optimizes queries; even if an index field is used in the condition, 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 has two main 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 expiration time 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 succeeded.
2. The expire() command sets the expiration time 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 successful but before the expire() command executes 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() solution to address potential deadlock issues.

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

• getset(key, "value1") returns null, and the key's value is set to value1.
• getset(key, "value2") returns value1, and the key's value is 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 is equal to oldExpireTime. If they are equal, it indicates that the current getset was successful, and the lock was acquired. If not, it means that this lock has been acquired by another request, and the current request can either return failure directly or continue to retry.
5. After acquiring the lock, the current thread can begin its business processing. After processing, compare its processing time with the lock's expiration timeout. If it is less than the lock's expiration timeout, directly execute delete to release the lock; if it exceeds the lock's expiration timeout, no further processing is needed.

Other Extension Solutions#

1. Distributed lock based on Redlock.
2. Distributed lock based on redisson, GitHub address.

IV. ZooKeeper-based Implementation of Distributed Locks#

Basic Knowledge Related to ZooKeeper Locks#

• ZooKeeper is generally composed of multiple nodes (odd number) and adopts the ZAB consistency protocol. Therefore, ZooKeeper can be viewed as a single-point structure; when modifying data, it automatically modifies data across all nodes before providing query services.
• ZooKeeper's data is structured in a directory tree, with each directory referred to as 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 each time a node is added under this node. Temporary nodes are automatically deleted when the client that created this znode loses contact with the server. Lastly, there are ordinary nodes.
• Watch mechanism: Clients can monitor changes to each node, generating an event for the client when changes occur.

Basic Solution#

• Principle: Utilize temporary nodes and the watch mechanism. Each lock occupies a regular node /lock. When needing to acquire a lock, 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, it watches the /lock node and waits for a deletion operation before contending for the lock. The benefit 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 Solution#

Principle#

Change the locking mechanism to create temporary sequential nodes. Each locking node can successfully create a node, but their sequence numbers differ. 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. Upon successfully acquiring the lock, execute the code and finally release the lock (delete the node).

V. Security Issues with 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 can lead to the following scenario:

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 continues to make write requests to the shared resource (in the image, a storage service), while the lock is actually held by Client 2, potentially leading to conflicts (the mutual exclusion of the lock is compromised).

Clock Jump#

Assume 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. Both Client 1 and Client 2 now 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 produce 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 the lock, and when Node A recovers, it is unaware that the lock has expired, leading to potential conflicts between A and B.