Loading... # 『笔记』基于Redis的分布式锁🔒Redlock 本文为 [Distributed locks with Redis](https://redis.io/topics/distlock) 的笔记,建议参考原文阅读。 同时,分布式锁管理器(Distributed Lock Manager)在会被称为**DLM**;而单实例(Single Instance)指在多个客户端下同步的单一实例。下文不再赘述。 ## 为什么需要分布式锁 分布式系统中,会存在多个提供相同服务的客户端。为保证数据一致性,需要对客户端之间进行数据同步。因而在一个客户端进行数据写入时,需要使用锁来限制(禁止)其它客户端读/写操作。也就是说,分布式锁是为了实现客户端之间的互斥操作而产生的。 该文章给出了一种叫做*Redlock*的算法用以实现*DML*。 ## Redlock ### 安全性与活性保证 *注:这里的活性(原文liveness)或许可以翻译成可用性?* 这里给出三个基本性质: 1. 安全性:保证互斥。在任意时刻,只有一个客户端允许持有锁🔒。 2. 活性 A:避免死锁。任何情况下,也就是说即使已持有锁的客户端崩溃或是[分区](https://en.wikipedia.org/wiki/Network_partition),其余客户端也总是有可能取得锁。 3. 活性 B:容错(鲁棒性)。只要大多数*Redis节点*启动,客户端就可以取得和释放锁。 原文作者认为,这三个性质是实现有效的分布式锁的最低要求。 ### 为什么仅基于故障转移实现是不够的 #### 对目前大多数基于Redis的分布式锁库的分析 最简单的利用Redis对一个资源上锁的办法就是——由客户端直接设置一个键(key)的值。这个键通常还附带一个过期属性,可以在过期后由Redis将其释放,这样就满足了性质2。客户端释放资源时,只要简单地删除该键就好了。 这个办法看起来是有效的,但为避免*Redis主节点(master)*宕机,可能会考虑添加一个*Redis子节点(slave)*。但样做是不可行的,因为Redis的复制是异步执行的,所以这样违反了安全性原则。下面给出了这个模型下的竞争条件(race condition,又称静态条件、竞争冒险)。 1. 客户端A请求并在主节点中持有锁。 2. 主节点在将该锁对应键**同步到从库前**崩溃。 3. 子节点被提升为主节点。 4. 客户端B请求并持有同一资源的锁。**违背安全性。** 在某些特殊应用场景中,如果可以容许多个客户端同时持有锁,那么这种方案是可行的。否则应该采用文章所给出的解决方案。 ### 单实例的正确实现 首先可以看看怎么对上面的实现方式进行调整,让它可以正确的运行。因为在时不时出现竞态条件的场景中,这种想法实际上是可行的,而且锁定一个单实例(lock into a single instance)是文章所描述算法的基础。 请求一个锁的步骤如下: ```sql SET resource_name my_random_value NX PX 30000 ``` 其中,`NX`选项指示该键仅在其不存在时被创建、`PX`选项指示该键会在`30000`毫秒后过期。这个键的值是`my_random_value`,这个值理论上应在各个客户端中唯一,即该随机值生成函数的周期应该足够大。 伪代码如下: ```python if redis.get("YOUR_KEY") == "YOUR_LOCK_RANDOM_VALUE": return redis.del("YOUR_KEY") else: return 0 ``` 基于这种逻辑,可以避免删除由另一个客户端持有的锁。比如,在某个客户端中一个操作超过了锁的过期时间,在解锁时如果没有采用这个逻辑,当其它客户端已取得锁时,可能会意外删除由其它客户端持有的锁。也就是说,这个随机值被客户端用于判断要解除的锁是否被自己持有。 我们把这个键的过期时间称为**锁有效时间**。它既是锁的自动释放时间(我觉得用时长duration会更加贴切,但是感觉会存在歧义);也是在另一个客户端获取锁前,当前客户端执行操作的最大时长。也就是,该锁仅在**锁有效时间窗口**中,对客户端提供互斥性保证。 现在我们有了一个很好的加解锁的逻辑。这个逻辑对于保证有单个始终可用的实例的非分布式Redis系统是安全的,接下来会将这个逻辑拓展到没有这种保证的分布式系统中去。 ### Redlock算法 分布式版本的算法中,假设有`N`个Redis主节点,且这些节点是完全独立的。这样我们就可以不用考虑如何协调这`N`个主节点。上文已经说明了单实例加解锁的安全性,那么我们可以理所应当地认为这个方法可以被应用于该算法中。在下面的例子中,取`N=5`。这`5`个主节点的失效需要尽可能的独立(比如运行在不同主机或虚拟机上)。 需要取得锁时,客户端执行如下操作: 1. 获取当前的毫秒时间戳 2. 使用相同的键及随机值,依次尝试在各个Redis节点中对资源加锁。在这一步中,客户端应使用相对锁有效时间而言尽可能小的超时时间(timeout,指等待Redis响应操作的时间)。比如,锁有效时间为`10`秒,那么超时时间可以是`~5-50`毫秒。这样可以避免在某个节点宕机时,客户端被阻塞的时间过长。 3. 这一步要验证该锁是否有效:基于步骤一中获取的时间戳计算经过的时长并与锁有效时间相见,得到锁的有效窗口。当且仅当客户端在多数(`N=5`时为`3`)节点中加锁成功,且有效窗口大于`0`时,该锁有效。 4. 如果客户端无法在大多数(也就是`N/2+1`个)节点上加锁或有效窗口为负值时,尝试解锁所有节点(即便是操作超时的节点)。 ### 这种算法是异步的吗 *Redlock*算法假设每个过程中时间的流动速率相同,并且速率的误差相比于锁有效时间较小。也就是说,该算法使用的是相对时间,不用考虑同步时钟。当然,对于不同计算机,时钟可能会有一些微小的偏移。这时,我们可以给出一个更好的互斥规则:它只在(有效窗口-时钟偏移)的时长内保证互斥性。这个时钟偏移取几毫秒即可。 这里有一个类似的,与时钟偏移关联的系统,这里给出它的论文地址:[Leases: an efficient fault-tolerant mechanism for distributed file cache consistency](http://dl.acm.org/citation.cfm?id=74870) ### 重试机制 当多个客户端同时尝试对相同资源进行加锁时,会导致[裂脑问题(split brain condition)](https://en.wikipedia.org/wiki/Split-brain_(computing)),也就是没有客户端能够取得锁,此时全部客户端都需要进行重试。在客户端获取锁失败后,等待随机的时间后重试,可以一定程度上避免这种问题。或者,如果一个客户端能够足够快的在大多数节点上加锁的话,遭遇裂脑问题的窗口就会变得非常小。所以在理想情况下,客户端应该尝试多路复用,将`SET`命令同时发送到`N`个节点中去。 值得强调的是,客户端在获取大部分锁失败后尽快释放(部分)已获取的锁非常重要。这样就没必要把时间浪费在等待锁过期上了。当然,如果发生了[网络分区](https://en.wikipedia.org/wiki/Network_partition),客户端无法与部分节点通讯,那么可用性降低的惩罚就是客户端对等待键过期用时的增加。 ### 释放锁 释放锁很简单,客户端甚至不需要自己是否获取到了锁,只需要在所有节点中尝试释放锁即可。 ### 安全性分析 我们尝试从不同场景分析这个算法的安全性。 我们假设一个客户端可以在大多数节点中取得锁,所有节点中都存在一个具有相同*TTL(time to live,存活时间)*的键。当然实际上这些键会在不同时间被设置,所以这些键的过期时刻是不同的。我们可知,第一个键被设置的最早时刻为`T1`(与步骤一中获取的时间戳相等),而最后一个键被设置的时间最晚为`T2`(完成对最后一个节点的请求时)。这样可以计算出**最小有效窗口**为`MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT`。所有被成功设置的键都会在该窗口结束后过期,所以,我们可以假设这些键是被同时设置的。 而且,在取得锁后,因为大部分节点已被加锁,所以同时重复加锁是不可能的(如果`N/2+1`个键已存在,那么`N/2+1`次`SET NX`操作不可能成功)。 但我们还希望确保多个客户端同时尝试获取锁时不能同时成功。 如果一个客户端对大多数节点加锁时花费的时间接近或超出了**锁最大有效时间**(通常是`TTL`),这个锁会被视为无效并尝试解锁全部节点。因此我们只需要考虑对大多数节点加锁时间小于有效时间的情况。从上面的论述中我们可知在一个客户端完成对大多数节点加锁后,至少在最小有效窗口内,其它客户端无法取得锁。因此当且仅当对大多数节点加锁时间大于`TTL`时,多个客户端才有可能同时持有锁。 ### 活性分析 活性的保证基于三个主要功能: 1. 锁的自动释放(过期后)——锁肯定可以被再次锁定 2. 一般情况下,若无法获取锁,客户端会移除节点中被自己添加的锁;或是在操作完成后客户端主动释放锁。这使得我们无需等待锁的自动释放也有可能再次获得锁。 3. 实际中客户端重新尝试获取锁之前,等待的时间比获取大多数锁的时间要长得多。这样一来,裂脑问题就不太可能出现。 当然,发生网络分区时,我们会收到与`TTL`时长相等的可用性惩罚。所以,如果发生了无限次网络分区,我们需要无限次收到这个惩罚。每当一个客户端取得锁并在释放锁之前发生网络分区都会导致这个情况。 理论上,如果发生了无限且连续的网络分区,系统可能会在无限长的时间内不可用。 ### 性能、崩溃恢复以及fsync 许多使用Redis作为锁服务器的场景都要求获取、释放锁操作的延迟尽可能低,且每秒能执行的获取、释放操作的数量尽可能多。为满足这个需求,减少与`N`个Redis的通讯延迟的策略肯定是多路复用(或丐版的多路复用,即假设客户端到各个节点间的RTT相同,使用非阻塞模式的socket,发送所有命令,并稍后读取结果)。 而对于崩溃恢复系统模型,我们需要考虑持久性。 存在这种情况,假设Redis没有配置持久化,一个客户端在`5`个节点之中的`3`个节点获取到锁。其中一个获取到锁的节点被重启,此时有三个节点可以被加锁,违背了锁的排他性。 如果我们启用了[AOF](https://zh.wikipedia.org/wiki/%E4%BE%86%E5%9B%9E%E9%80%9A%E8%A8%8A%E5%BB%B6%E9%81%B2)持久化,那么情况会有所改善。我们升级节点时只要简单地执行`SHUTDOWN`命令并重启它即可。因为Redis的过期是在语义上实现的,也就是说,当节点被关闭时,时间仍在流逝⌛。但如果是计划外的关闭,比如停电了,会发生什么呢?Redis默认情况下配置为每秒在磁盘上执行`fsync`。那么我们会在重启后丢失在最后一次`fsync`与下一次`fsync`间隔间设置的锁。事实上,如果我们需要保证锁的安全性,我们需要配置`fsync=always`。这将会导致比传统以安全方式实现的CP系统更差的性能。 事情总比它看上去的要好一些。只要一个节点崩溃重启后,不再参与任何**当前活动的**锁,算法的安全性就会得到保证。因此,所有当前活动锁的获取,都应当只通过对除了*重新加入系统的节点*之外的节点加锁。 为了保证这一点,我们只需要让一个节点崩溃重启后的不可用时间比所使用的`TTL`多一点,即节点释放崩溃时存在的所有锁所需的最长时间,这样就可以保证与该节点关联的锁已全部释放。 所以,即使不使用Redis持久化,使用延迟重启也基本可以实现安全的崩溃模型。但是注意这可能会影响可用性。比如当大部分实例崩溃时,系统将在大于等于`TTL`的时间内全局不可用(不能获取任何锁)。 ### 让算法更可靠:延长锁 如果客户端执行的操作由小步骤组成,则可以默认使用较小的锁有效时间,并配合实现锁有效时间延长的算法。当客户端在执行过程中,如果锁的有效长度达到某个较低的临界值,在确保节点中键存在且值等于客户端自身设置的随机值后,可以延长节点中的键的有效期。对所有节点执行上述操作。 如果客户端能将锁延长应用到大多数节点且仍在锁有效窗口内,那么客户端应该仅考虑重新获取锁。 当然,应当限制对锁的重新获取否则会违背活性原则。 ## 算法的争议 [How to do distributed locking](https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html) [Is Redlock safe](https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html) Martin提出,由于Redis的过期时间是基于[gettimeofday(2)](https://man7.org/linux/man-pages/man2/gettimeofday.2.html)系统调用而没有使用单调时间,因此会因为系统的原因导致最终节点间的时间流动速率不一致。从而破坏*Redlock*算法的安全性。 但排除特殊情况,一般情况下这个算法的正确性是可以得到保证的。 最后修改:2021 年 07 月 04 日 02 : 45 AM © 允许规范转载 赞赏 请我喝杯咖啡 ×Close 赞赏作者 扫一扫支付 支付宝支付 微信支付