ProHoster > Blog > Administration > Distributed Locks Using Redis

Distributed Locks Using Redis

Hello, Habr!

Today we bring you a translation of a complex article about implementing distributed locks using Redis, and we will discuss the potential of Redis as a topic. An analysis of the Redlock algorithm by Martin Kleppmann, author of the book "High-load Applications", is provided here.

Distributed locks are a very useful primitive used in many environments where different processes must work on shared resources based on the principle of mutual exclusion.

There are several libraries and posts describing how to implement a DLM (Distributed Lock Manager) using Redis, but each library has its own approach, and the guarantees they provide are rather weak compared to what can be achieved with slightly more complex design.

In this article, we will attempt to describe a conventionally canonical algorithm demonstrating how to implement distributed locks using Redis. We will discuss an algorithm called Redlock, which implements a distributed lock manager and, in our opinion, this algorithm is safer than the standard approach with a single instance. We hope that the community will analyze it, provide feedback, and use it as a starting point for the implementation of more complex or alternative projects.

Implementations

Before we proceed to describe the algorithm, let's provide some links to already existing implementations. They can be used for reference.

Safety and Availability Guarantees

We are going to model our project with just three properties that we believe provide the minimal guarantees necessary for the effective use of distributed locks.

  1. Safety Property: Mutual Exclusion. At any given time, only one client can hold the lock.
  2. Availability Property A: No Deadlocks. It is always possible to obtain a lock, even if the client holding the resource crashes or moves to another disk segment.
  3. Availability Property B: Fault Tolerance. As long as the majority of Redis nodes are operational, clients can acquire and release locks.

Why a recovery-based implementation is insufficient in this case
To understand what we are going to improve, let's analyze the current state of most libraries for distributed locks based on Redis.

The simplest way to lock a resource using Redis is to create a key in the instance. Typically, the key is created with a limited lifespan, which is achieved using the expires feature in Redis, so sooner or later this key is released (property 2 in our list). When a client needs to release the resource, it deletes the key.

At first glance, this solution works fine, but there's a problem: our architecture presents a single point of failure. What happens if the master Redis instance fails? Let's add a replica! And we will use it when the master is unavailable. Unfortunately, this option is unviable. By doing so, we cannot correctly implement the mutual exclusion property necessary for safety, because replication in Redis is asynchronous.

It is clear that such a model leads to a race condition:

  1. Client A acquires the lock on the master.
  2. The master fails before the key is transferred to the replica.
  3. The replica is promoted to master.
  4. Client B acquires the lock on the same resource already locked by A. SECURITY BREACH!

It is sometimes perfectly normal for many clients to hold a lock simultaneously under special circumstances, such as a failure. In such cases, a replication-based solution can be applied. In other cases, we recommend the solution described in this article.

Correct implementation with a single instance

Before attempting to overcome the shortcomings of the single instance configuration outlined above, let's understand how to properly act in this simple scenario, as such a solution is indeed permissible in applications where race conditions are occasionally acceptable. Additionally, the lock on the single instance serves as the basis used in the distributed algorithm described here.

To acquire a lock, proceed as follows:

SET resource_name my_random_value NX PX 30000

This command sets the key only if it does not already exist (NX option), with a lifespan of 30000 milliseconds (PX option). The key is assigned the value “myrandomvalue”. This value must be unique across all clients and all lock requests.
In principle, a random value is used for safely releasing the lock, via a script that tells Redis: delete the key only if it exists, and the value stored in it is exactly what was expected. This is achieved through the following Lua script:

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

It is important to prevent the lock from being released by another client. For instance, a client may acquire a lock, then get stuck during an operation that takes longer than the lifespan of the initial lock (so the key's expiration can occur), and later remove the lock set by another client.
Using a simple DEL is unsafe, as a client may delete a lock set by another client. In contrast, by using the above script, each lock is 'signed' with a random string, so it can only be removed by the client that originally set it.

What should this random string be? I believe it should be 20 bytes from /dev/urandom, but there are less costly ways to create a sufficiently unique string for your purposes. For example, it would be acceptable to seed RC4 with /dev/urandom and then generate a pseudorandom stream based on that. A simpler solution involves combining Unix time in microsecond resolution with the client ID; it’s not as secure but might suffice for the level of tasks in most contexts.

The time we use as the key's lifespan indicator is called 'lock duration.' This value simultaneously represents the period after which the lock will automatically be released and the time the client has to perform an operation before another client can lock the same resource without actually violating mutual exclusion guarantees. Such a guarantee is limited to a specific time window that starts when the lock is acquired.

So, we have discussed a good way to acquire and release a lock. The system (when it comes to a non-distributed system consisting of a single always available instance) is safe. Let’s extend this concept to a distributed system, where we don’t have such guarantees.

Redlock Algorithm

In the distributed version of the algorithm, we assume that we have N master Redis instances. These nodes are completely independent of each other, so we do not use replication or any other implicit coordination system. We have already explained how to safely acquire and release a lock on a single instance. We take it as given that the algorithm will use this method when working with a single instance. In our examples, we set N to 5, which is a reasonable value. Thus, we will need to use 5 master Redis instances on different computers or virtual machines to ensure that they operate mostly independently of one another.

To acquire a lock, the client performs the following operations:

  1. Gets the current time in milliseconds.
  2. The client sequentially attempts to acquire a lock on all N instances, using the same key name and random values in all cases. In step 2, when establishing the lock for each instance, the client utilizes a delay that is short enough compared to the time after which the lock is automatically released. For example, if the lock duration is 10 seconds, the delay might be in the range of ~ 5-50 milliseconds. This prevents the situation where the client could be locked for a long time while trying to connect to a failing Redis node: if the instance is unavailable, we try to connect to another instance as quickly as possible.
  3. To acquire the lock, the client calculates how much time has elapsed; to do this, it subtracts the timestamp obtained in step 1 from the current time value. Only when the client is able to acquire locks on the majority of instances (at least 3), and the total time taken to obtain the lock is less than the lock duration, is it considered that the lock has been successfully acquired.
  4. If the lock has been acquired, the duration of its effectiveness is considered to be the original lock duration minus the elapsed time calculated in step 3.
  5. If the client fails to acquire the lock for any reason (either it could not lock N/2+1 instances, or the lock duration turned out to be negative), then it will attempt to unlock all instances (even those that it was thought it could not lock).

Is the algorithm asynchronous?

This algorithm is based on the assumption that although there are no synchronized clocks across all processes, the local time in each process flows at approximately the same pace, and the error is small compared to the total time after which the lock is automatically released. This assumption is very similar to the situation typical of regular computers: each computer has local clocks, and we can usually expect that the time discrepancy between different computers is minimal.

At this stage, we need to formulate our mutual exclusion rule more carefully: mutual exclusion is guaranteed only if the client holding the lock completes its work within the time the lock is valid (this value is derived in step 3), minus a slight additional time (just a few milliseconds, to compensate for the time drift between processes).

More about such systems that require time drift synchronization is discussed in the following interesting article: Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

Retry on failure

When a client fails to acquire a lock, it should attempt to do so again after a random delay; this is done to desynchronize multiple clients that are simultaneously trying to acquire a lock on the same resource (which could lead to a 'split-brain' scenario where there are no winners). Moreover, the faster the client tries to acquire locks from most Redis instances, the narrower the window in which a split-brain situation may occur (and the less need for retries). Therefore, ideally, the client should attempt to simultaneously send SET commands to N instances using multiplexing.

It is important to emphasize how critical it is for clients that could not acquire the majority of locks to release (partially) obtained locks so that they do not have to wait for the key expiration before the lock on the resource can be acquired again (by the way, if network fragmentation occurs and the client loses connection with Redis instances, a penalty is incurred for violating availability while waiting for the key expiration).

Releasing the lock

Releasing a lock is a simple operation that just requires unlocking all instances, regardless of whether the client believes it successfully locked a particular instance.

Security considerations

Is the algorithm safe? Let’s try to envisage what happens in various scenarios.

To begin with, let's assume that the client managed to gain a lock on most of the instances. Each of the instances will contain a key with the same lifetime for all. However, each of these keys was set at its own moment, so their expiration times will vary. But, if the first key was set at a time not worse than T1 (the time we choose before contacting the first server), and the last key was set at a time not worse than T2 (the time when the response from the last server was received), then we can be sure that the first key in the set, which will expire, will exist at least for the minimum duration. MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. All other keys will expire later, so we can be sure that all keys will be valid simultaneously for at least this duration.

During the time when most keys remain valid, another client will not be able to acquire the lock, since N/2+1 SET NX operations cannot succeed if there are already N/2+1 keys in existence. Therefore, if the lock was acquired, it cannot be reacquired at the same moment (this would violate the mutual exclusion property).
Indeed, we want to ensure that a set of clients trying to acquire the lock at the same time cannot all succeed.

If a client locked the majority of instances, spending about or more than the maximum duration of the lock, they will consider the lock invalid and unlock the instances. Thus, we only need to consider the case where the client managed to lock the majority of instances in less time than the validity period. In this case, regarding the above argument, within the time MIN_VALIDITY no client should be able to reacquire the lock. Therefore, a set of clients can lock N/2+1 instances at the same time (which ends at the completion of stage 2) only when the time to lock the majority was greater than the TTL, which renders the lock invalid.

Can you provide a formal proof of security, indicate existing similar algorithms, or find a bug in the described process?

Considerations for Availability

The availability of the system depends on three main characteristics:

  1. Automatic unblocking (as the keys expire): ultimately, the keys will become available again for use in blocking.
  2. The fact that customers often help each other by removing blocks when the needed block has not been purchased or was purchased, and the work is completed; thus, it is likely that we will not have to wait for the keys to expire to reacquire the block.
  3. The fact that when a customer needs to retry obtaining a block, they tend to wait for a comparatively longer time than the period required to acquire most blocks. This reduces the likelihood of a split-brain situation when competing for resources.

However, there is a penalty for reduced availability equal to the TTL time in network segments, so if there are continuous segments, this penalty can become indefinite. This happens every time a customer acquires a block and then gets cut off in another segment before they can release it.

In principle, with infinite continuous network segments, the system could remain unavailable for an infinite period.

Performance, failover, and fsync

Many use Redis because it's necessary to ensure high performance for the locking server, at the level of latencies required for acquiring and releasing locks, as well as the number of such acquisition/release operations that can be performed per second. To meet this requirement, there is a communication strategy with N Redis servers to reduce latency. This is a multiplexing strategy (or 'poor man's multiplexing', where the socket is set to non-blocking mode, sends all commands, and reads commands later, assuming that the turnaround time between the client and each of the instances is similar).

Indeed, we must also consider the aspect of long-term data storage if we aim to create a model with reliable failover recovery.

To clarify the issue, let's assume we are configuring Redis without any persistent data storage. The client manages to lock 3 out of 5 instances. One of the instances that the client managed to lock restarts, and at that moment 3 instances for the same resource that we can lock arise again, and another client can, in turn, lock the restarted instance, violating the safety property that assumes the exclusivity of locks.

If we enable an append-only file (AOF) for data persistence, the situation improves slightly. For example, we can upgrade the server by sending the SHUTDOWN command and restarting it. Since the expiration operations in Redis are semantically implemented in such a way that time continues to flow even when the server is off, we are fine with all our requirements. This is fine as long as a proper shutdown is ensured. But what happens during power outages? If Redis is configured by default to fsync to disk every second, it is possible that after a restart we will lose our key. Theoretically, if we want to guarantee lock safety upon any instance restart, we must enable fsync=always in the data persistence settings. This will completely kill performance, bringing it down to levels of such CP systems that are traditionally used for the safe implementation of distributed locks.

But the situation is better than it seems at first glance. Essentially, the safety of the algorithm is maintained since when an instance restarts after a failure, it is no longer involved in any currently active locks.

To ensure this, we only need to make sure that after a failure, the instance remains unavailable for a duration slightly exceeding the maximum TTL we use. This way, we will wait for the expiration and the automatic release of all keys that were active at the time of the failure.

By using deferred restarts, it is theoretically possible to achieve safety even in the absence of any long-term persistence in Redis. However, it is worth noting that this may result in penalties for availability violations. For example, in the event of the failure of most instances, the system will become globally unavailable for the duration of the TTL (and no resources will be able to be blocked during this time).

Increasing algorithm availability: extending the lock

If the tasks performed by clients consist of small stages, it is possible to reduce the default lock duration and implement a mechanism for extending locks. In principle, if a client is busy with computations and the lock expiration time is dangerously decreasing, a Lua script can be sent to all instances to extend the TTL of the key, if the key still exists and its value is still the random one obtained when the lock was acquired.

The client should consider the lock to be reacquired only if they succeeded in locking the majority of the instances during the effective time.

However, technically the algorithm does not change, so the maximum number of retry attempts for acquiring locks should be limited; otherwise, availability properties will be violated.

Source: habr.com

Buy reliable website hosting with DDoS protection, VPS VDS servers 🔥 Buy reliable website hosting with DDoS protection, VPS VDS servers | ProHoster