我对 Redlock 算法的疑问

[JasonLaw]

在Distributed locks with Redis – Redis中，首先它描述了如何正确地使用单实例实现分布式锁，然后它介绍了分布式版本的算法。但是对于分布式版本，我有许多疑问。

首先，那篇文章说

In the distributed version of the algorithm we assume we have N Redis masters. Those nodes are totally independent, so we don’t use replication or any other implicit coordination system. We already described how to acquire and release the lock safely in a single instance. We take for granted that the algorithm will use this method to acquire and release the lock in a single instance. In our examples we set N=5, which is a reasonable value, so we need to run 5 Redis masters on different computers or virtual machines in order to ensure that they’ll fail in a mostly independent way.

In order to acquire the lock, the client performs the following operations:

1. It gets the current time in milliseconds.
2. It tries to acquire the lock in all the N instances sequentially, using the same key name and random value in all the instances. During step 2, when setting the lock in each instance, the client uses a timeout which is small compared to the total lock auto-release time in order to acquire it. For example if the auto-release time is 10 seconds, the timeout could be in the ~ 5-50 milliseconds range. This prevents the client from remaining blocked for a long time trying to talk with a Redis node which is down: if an instance is not available, we should try to talk with the next instance ASAP.
3. The client computes how much time elapsed in order to acquire the lock, by subtracting from the current time the timestamp obtained in step 1. If and only if the client was able to acquire the lock in the majority of the instances (at least 3), and the total time elapsed to acquire the lock is less than lock validity time, the lock is considered to be acquired.
4. If the lock was acquired, its validity time is considered to be the initial validity time minus the time elapsed, as computed in step 3.
5. If the client failed to acquire the lock for some reason (either it was not able to lock N/2+1 instances or the validity time is negative), it will try to unlock all the instances (even the instances it believed it was not able to lock).

我的疑问

1. 为什么要顺序地尝试获取所有实例里的锁呢？同时尝试获取会存在什么问题呢？
2. Redlock 算法所说的 auto-release time 是类似于Distributed locks with Redis – Redis - Correct implementation with a single instance中所说的SET resource_name my_random_value NX PX {ttl}中的 ttl 吗？也就是我下面所说的 TTL，是吗？
3. 在第二步时，会尝试在所有实例中获取锁，它所做的行为跟单实例所做的行为是一样的，也就是SET resource_name my_random_value NX PX {ttl}，那么 ttl 是怎么计算出来的呢？我认为不同实例的 ttl 是不同的，因为尝试获取在不同的实例里的锁的时间是不一样的。因为要确保“如果所有实例的同一个 key 都在同一时间被删除”，所以我觉得每个实例里所设置的 ttl 是“TTL - (在某个实例尝试获取锁的时间 - 第一步获取到的时间)”，对吗？（这里的 TTL 表示的是逻辑上的 TTL，并不是真实设置在某个实例里的 ttl，也就是所有实例里的同一个 key 都会在“第一步获取到的时间 + TTL”这个时间被删除）

关于第3点，在Distributed locks with Redis – Redis - Safety arguments中说了

To start let’s assume that a client is able to acquire the lock in the majority of instances. All the instances will contain a key with the same time to live. However, the key was set at different times, so the keys will also expire at different times. But if the first key was set at worst at time T1 (the time we sample before contacting the first server) and the last key was set at worst at time T2 (the time we obtained the reply from the last server), we are sure that the first key to expire in the set will exist for at least MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. All the other keys will expire later, so we are sure that the keys will be simultaneously set for at least this time.

所有实例将会包含拥有一样ttl的key，然而，键是在不同时间被设置的，所以也会在不同的时间失效。这样子还能够保证mutual exclusion属性吗？比如client1获取到了锁，它期望在获取到锁之后的ttl时间内都能够唯一拥有锁，但是一些实例上的key可能提前失效，导致client2能够成功获取锁，这就违背了mutual exclusion属性。是我理解错了吗？

这么久过去了，重新看了Distributed locks with Redis – Redis，有了很多新的理解，也知道了很多疑问的答案。

• 关于疑问1，我暂时没有答案，不过我又提了一个新的问题，已经忘记我曾经有过同样的疑问了🤣。
• 关于疑问2，auto-release time就是SET resource_name my_random_value NX PX {ttl}中的{ttl}。
• 关于疑问3，向所有实例请求SET resource_name my_random_value NX PX {ttl}，{ttl}都是一样的。而且Redlock无法确保“所有实例的同一个 key 都在同一时间被删除”，它只是能够确保在MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT这段时间内的mutual exclusion。

其它资料

Clock drift - Wikipedia

[jybox]

>为什么要顺序地尝试获取所有实例里的锁呢？同时尝试获取会存在什么问题呢？

同时获取可能会死锁（每个客户端成功在一半的实例加锁），所有客户端都顺序访问就不会出现死锁了。

>键是在不同时间被设置的，所以也会在不同的时间失效。这样子还能够保证 mutual exclusion 属性吗？

按我的理解这个 TTL 只是为了避免出现加锁后（因进程崩溃）没有解锁的情况，在一定时间后自动解锁，这本来就是一个特殊情况下的措施，其实在发生达到 TTL 时，锁的有效性就已经得不到保证了（你不知道是进程真的崩了还是暂时卡住了），所以这个 TTL 差个几毫秒并不是那么重要。

正常的应用中不应该出现「期望在获取到锁之后的 ttl 时间内都能够唯一拥有锁」的情况，应该（比如在时间用掉了一半的时候）不断地续期，在结束后主动地释放锁。

[hdbzsgm]

在有 clock_drift 的情况下 redlock 的设计一定会有失败的 case 出现 。redlock 的设计正确性是依赖时间正确性模型的

[JasonLaw]

@jybox #1 你说“同时获取可能会死锁（每个客户端成功在一半的实例加锁），所有客户端都顺序访问就不会出现死锁了”。我不太同意你的说法，比如在某个时刻，client1 获取到了 5 个中的 2 个，client2 获取到了 5 个中的 2 个，它们都想去获取最后一个，但是只有一个能够成功获取，不会存在你说的死锁情况，因为不会出现“client1 持有 client2 需要的资源，client2 持有 client1 需要的资源”这种情况，不会构成一个环。

[gantleman]

赞同顺序使用锁防止死锁的答复。

锁本身也相当于一种队列，保证随机或顺序使用资源。

因为锁和资源不在同一个服务器，没有强制的使用约束，容易出现不一致的状况

[JasonLaw]

@hdbzsgm #2 我不确定我是否正确理解你所说的，你所说的是[Distributed locks with Redis – Redis - Is the algorithm asynchronous?]( https://redis.io/topics/distlock#is-the-algorithm-asynchronous)中所说的“The algorithm relies on the assumption that while there is no synchronized clock across the processes, still the local time in every process flows approximately at the same rate, with an error which is small compared to the auto-release time of the lock. This assumption closely resembles a real-world computer: every computer has a local clock and we can usually rely on different computers to have a clock drift which is small.”吗？算法依赖于每个进程内的时间的流动速度是差不多一样的。是吗？

[liprais]

https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

[AmmeLid]

@JasonLaw #3 我认为避免的是活锁问题，在你的例子中引入一个 client3 获取 1 个锁，或者某个节点故障，剩 4 个节点的情况，就容易产生活锁。

[ALLLi]

append 里贴的英文不是已经解答了 append 里面的问题了吗，redlock 并不保证在获得锁之后的 TTL 时间里窦独占，而是保证在 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 里独占

[JasonLaw]

@AmmeLid #7

我觉得并不是，维基百科说“A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing.”。

但是就我们这个例子，比如一个实例下线了，只剩下 4 个，client1 获取到两个，client2 获取到另外两个，它们都无法成功获取到锁，之后释放，但是 https://redis.io/topics/distlock#retry-on-failure 中说了“When a client is unable to acquire the lock, it should try again after a random delay in order to try to desynchronize multiple clients trying to acquire the lock for the same resource at the same time (this may result in a split brain condition where nobody wins).”，因为随机的延迟，最后不会出现“none progressing”这种情况。

[JasonLaw]

@ALLLi #8 是的，https://redis.io/topics/distlock#is-the-algorithm-asynchronous 中也说了“At this point we need to better specify our mutual exclusion rule: it is guaranteed only as long as the client holding the lock will terminate its work within the lock validity time (as obtained in step 3), minus some time (just a few milliseconds in order to compensate for clock drift between processes).”。

[AmmeLid]

@JasonLaw #9 感觉我们说的并不矛盾，随机延迟是可以最终摆脱活锁的情况，但是就单次获取锁的操作来说依然会出现活锁。这个是无谓的消耗，如果随机的延迟不合理，可能会在多次获取失败才能成功获取锁。

[wakzz]

> 1：为什么要顺序地尝试获取所有实例里的锁呢
为了避免死锁问题，顺序获取锁的场景，只有第一个节点存在锁竞争。
> 2：Redlock 算法所说的 auto-release time 的 ttl 也就是我下面所说的 TTL，是吗？
是。
> 3：那么 ttl 是怎么计算出来的呢
一般有个默认值例如 30 秒，然后由 WatchDog 线程不断给未释放的锁续期，直到锁释放。

[JasonLaw]

@wakzz #12 我不太认可你所说的“避免死锁”，因为根本都不会出现死锁这种情况。关于 ttl，所有实例里的同一个 key 的 ttl 都一样。https://redis.io/topics/distlock#making-the-algorithm-more-reliable-extending-the-lock 有讲到延长 ttl，但是它也强调了“so the maximum number of lock reacquisition attempts should be limited, otherwise one of the liveness properties is violated”。所以不是“不断给未释放的锁续期”，而是 client 还未完成计算，但是失效时间快要到了，client 可以请求延长时间。就算是这样，也不是“直到锁释放”，延长是有次数限制的，不然就会违反活跃性这个特性。

[JasonLaw]

@liprais #6

我看完了 https://redis.io/topics/distlock，https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html，http://antirez.com/news/101 。

我个人挺认可 Redis 作者所说的“Most of the times when you need a distributed lock system that can guarantee mutual exclusivity, when this property is violated you already lost.”。如果方便的话，可以分享一下你的想法吗？谢谢。

[wakzz]

@JasonLaw
如果不顺序获取锁，会出现同一个 key 的锁，一个节点获取了 N 个 redis 实例的锁，另一个节点也获取了 N 个 redis 实例的锁，然后两者相互等待对方释放而出现死锁。

[yibo2018]

@wakzz 不可能，要保证 n/2+1 的量，所以一定俩个 client 在获取锁的时候，一定会有在一个服务器争锁的情况，最终只会有一个 client 获取

[maorui139]

@jybox 问题一：我觉得不是死锁，这个情况并不复合死锁的定义。
应该是为了保证并发时一定有一个客户端获得锁，顺序的话只有第一个节点存在竞争，且一定有一个客户端获得锁；
如果是并发加锁，那么可能同时有 x 个客户端各获得 y 个锁，大家都无法获得锁

[maorui139]

问题一是为了避免活锁