（译）RedLock，红锁？

翻译至Redis官网，原文链接

RedLock，即Distributed locks with Redis，Redis提供的分布式锁。

Distributed locks with Redis

在很多场景下，不同的进程需要以互斥的方式去访问共享资源，这时候分布式锁是非常有用的原语。

目前有很多的库和博客文章描述了如何利用Redis去实现一个分布式锁管理器（DLM - Distributed Lock Manager），但是每个库都采用了不同的实现方式，与稍微复杂一点的设计相比，这些方式都显得比较简单而且可靠性低。

这篇文章试图提供一种更规范的算法来实现Redis分布式锁。我们将这种算法命名为RedLock，相较于普通的单Redis实例实现的DLM，我们相信这种方式更加的安全可靠。我们希望社区能够去分析它并提供反馈，然后将其用作实现更复杂或者非传统设计（的分布式锁）的一个起点。

各个语言的实现库

(略).

安全性和活性的保证

活性，并发下线程能及时执行的能力。

我们将只从三个要素来建模我们的设计，因为从我们的角度来看，这三个要素是有效使用分布式锁所需要的最基本的保证。

安全性：互斥。在给定的任何时刻，仅有一个客户端能够持有锁。
活性A：无死锁。（其他客户端）最终总是能够获取到锁，即使当前锁定资源的客户端崩溃或者分区。
活性B：容错。只要大部分（一般定义为超过一半）Redis节点存活，客户端就可以获取和释放锁。

为何基于故障转移的实现方式还不够

为了理解我们到底想要改进的是什么，让我们先分析一下大多数基于Redis的分布式锁的库的当前状态。

使用Redis锁定一个资源的最简单方式就是在一台实例上创建一个key。这个key通常是利用Redis的expire命令来限制它的存活时长，所以最终会被释放掉（符合上面列出来的第2个要素）。当客户端需要释放资源时，也可以主动删除这个key。

从表面上看一切都很好，但其实存在一个问题：在我们架构中会存在单点故障。如果Redis master节点宕机了怎么办？那好，我们再加一个slave节点，然后在master节点不可用时使用它替代。不幸的是，这种方式并不可取。这样一来，我们无法实现互斥的这一安全性保证，因为Redis的复制（同步）是异步的。

该模型存在很明显的竞态条件：

客户端A获取了master节点的锁（key）。
master节点在key传输给slave节点之前崩溃了。
slave节点升级成为master。
客户端B获取了客户端A当前正在锁定的同一资源的锁（B获取了新的master节点的锁）。违反了安全性！

有时候在特殊情况下，譬如在故障期间，多个客户端同时持有锁是完全没有问题的。在这种情况下，你可以使用基于复制算法的解决方案。否则，我们还是建议使用本文所描述的方案。

单Redis实例下的正确实现方式

在尝试克服上述单Redis实例设置的局限之前，我们先来看下在这个比较简单的场景中如何正确的进行设置。因为在时刻都有可能存在竞态条件的应用程序中，这实际上是一个可行的解决方案。而且锁定到单个Redis实例是本文所描述的分布式算法的基础。

为了获取锁，会采用如下的方式

SET resource_name my_random_value NX PX 30000

这条命令只会在key不存在的情况下（NX选项）把它设置进去，过期时间是30000毫秒（PX选项）。key设置了一个对应的值”my_random_value“。这个值在所有的客户端以及锁定请求中必须是唯一的。

基本上，使用这个随机值是为了以一种安全的方式释放锁。使用一个脚本告诉Redis：当且仅当key存在且存储在key上的值恰好是我所期望的值时，才能移除此key。可以使用下面这个Lua脚本实现：

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

（上面这个脚本中）很重要的一点是避免了删除另一个客户端创建的锁。譬如，一个客户端可能获取了该锁，然后在某些操作中阻塞（执行）的时间超过了该锁的有效时间（锁将要过期的时间），之后（操作完成之后）该客户端删除了这个锁（直接执行DEL命令），但其实这个锁已经被其它客户端获取了（或者说删除了其它客户端创建的锁，因为key是一样的）。所以仅仅使用DEL命令是不安全的，因为一个客户端可能删除另一个客户端创建的锁。而使用上述脚本，由于每个锁都持有一个随机字符串的”签名“（代表某个客户端），因此仅当仍然是设置当前锁的客户端尝试将锁删除时，当前锁才会被删除。

那么这个随机字符串应该是什么样的呢？我会假设它是来自/dev/random下的20个字节。当然在你自己的程序任务中你可以去找一个更简单的方式来保证它的唯一性。（略，这段后面是一些关于随机串的选取方式。）

key的存活时间，我们把它叫做”lock validity time“（锁的有效期）。它既是锁自动释放的时间，又是当前客户端在另一个客户端再次获取锁之前必须执行的操作所需的时间，而在技术上又不违反互斥保证。该时间从获取锁的那一刻起，仅限于给定的时间窗口。

至此，我们有了一个比较好的方式去获取和释放锁。这个由单个且始终可用的实例组成的非分布式系统是安全的。接下来让我们把这个概念扩展到没有此类保证（始终可用）的分布式系统中去。

RedLock算法

在此算法的分布式版本中，假定我们有N个Redis master节点。这些节点都是相互独立的，所以我们不会使用复制或者任何其它隐式的协调系统。我们已经描述了如何在一个单实例中去安全的获取和释放锁。想让然的也会认为此算法会采用这种方法在单个实例中获取和释放锁。在我们的例子里面，N=5，这是很合理的一个数值，然后我们会在不同的计算机或者虚拟机内运行5个Redis master节点，以此来保证它们失败时都是彼此独立的。

为了保证能获取到锁，客户端会做如下一些操作：

获取当前的时间戳（毫秒）。
按顺序在N个实例中依次尝试获取锁，使用的都是同样的key和随机值。在这个步骤中，当在每一个实例中去设置锁的时候，客户端会设定一个小于锁的自动释放时长的超时时间，以便于能正常的获取锁。比如说锁的自动释放时长是10s，那么这个超时时间会设定为5~50ms之间。这样做是为了避免当一个Redis节点挂掉时，客户端仍然在相当长的一段时间内去尝试连接这个节点。如果一台实例不可用，我们应该尽快的去尝试连接下一台实例。
客户端会通过当前时间戳减去第一步中获取的时间戳，来计算在所有实例中获取锁所消耗的时间。当且仅当客户端能获取大部分实例的锁时（至少3台，大部分 = N/2 + 1），而且获取锁的总消耗时长小于锁的有效时长，分布式锁才被认为真正获取成功。
当锁获取成功后，它的有效时长会被认定为初始化设置的有效时长减去在第3步中计算出来的获取锁消耗的时长。
如果客户端由于某些原因（要么没有获取到大部分实例的锁，要么实际有效时间变为负数了）获取锁失败了，那么它会尝试去释放所有实例的锁（哪怕是那些它尝试获取锁失败的实例）。

这种算法是异步的吗

（可以认为是同步的，因为时钟漂移一般情况下很小。）该算法是基于这样一种假设，即进程（实例）之间在没有同步时钟时，每个进程中的本地时钟都是以相同的速率流动，相比于锁的自动释放时间，误差要小的多。这种假设与现实世界中的计算机非常相似：每台计算机都有一个本地时钟，我们通常可以依赖不同的计算机来获得一个很小的时钟漂移。

基于这一点，我们需要更好地指定互斥规则：持有锁的客户端在锁有效时间（步骤3中获得的）减去一些时间（为了补偿进程之间的时钟偏移，只有几毫秒）的时长后终止工作，这是可以保证的（互斥）。

（注：我的理解是锁的实际有效时长 = 初始化时长（TTL） - 获取（所有实例中的）锁消耗时长 - 时钟漂移，也就是要移除时钟漂移的误差。比如，初始化有效时长10s，获取锁消耗时长2s，不排除时钟漂移误差（假设为1s），那么有效时长为8s。由于存在时钟漂移，最后一台实例实际上相比于第一台实例，是相差了1s之后才开始有效时长计算的，这样就违背了互斥。更严格的话是要计算上时钟漂移误差的。）

失败后的重试机制

当一个客户端无法获取锁时，它应该在一个随机延迟后重试，尝试去同步多个客户端在同一时刻获得同一资源的锁（因为可能导致脑裂，nobody wins）。同样，当客户端在大多数Redis实例中尝试获取锁的速度越快，出现脑裂（以及重试）的情况的窗口就会越小，因此理想情况下，客户端应该使用多路复用的形式尝试同时发送SET命令给N个实例。

值得强调的是，对于未能获取大多数锁的客户端，尽可能快的释放（那部分）获取的锁是非常重要的，这样就不用等到key（锁）过期之后才能再次获取（但是，如果发生网络分区，并且客户端再也不能和Redis实例进行通信，那么就要付出可用性上面的代价，因为要等到这个key过期之后才能再次获取）。

锁的释放

锁的释放比较简单，只需要释放所有实例上的锁即可。不管客户端能否成功锁定给定的实例。

安全性讨论

这种算法安全么？我们可以尝试了解下在不同情况下会发生什么。

首先，我们假设客户端可以获取大多数实例上的锁。所有的实例都会包含一个具有相同过期时间的key。然而，key是在不同时间被设置的，所以它们也会在不同的时间失效。但是如果第一个key是在时间T1（在和第一台服务器连接之前采样的时间）设置的，并且最后一个key是在时间T2（从最后一台服务器得到答复的时间）设置的，我们可以确定的是集合中第一个key最小的有效时长MIN_VALIDITY = TTL（应用中设置的过期时间）- (T2 - T1) - CLOCK_DRIFT（时钟漂移）。所有其它的key都会在之后失效，所以我们可以确保至少这次这些key都会被同时设置。

在设置大多数key（成功or失败）的这段时间内，另一个客户端将无法获取锁，因为已经存在了N/2+1个key，所以N/2+1个 SET NX的操作都会失败。因此如果获取了锁，那么不可能在同一时间去重新获取它（违背了互斥性）。

然而我们还是要确保同一时间尝试获取锁的多个客户端不能同时成功。

如果一个客户端使用了一个与锁的最大过期时间（应用中设置的TTL）很接近或者更长一点的时间，来获取了大多数实例上的锁，那么这个锁就会被认为是无效的并且会被释放掉，因此我们只需要考虑客户端用小于有效时长的时间来获取大多数实例上的锁的这种情况。在这种情况下，上面已经说的很清楚了，在MIN_VALIDITY时间段内，没有客户端可以再次获取锁。所以当且仅当锁定大多数实例的时长大于TTL时长，多客户端才可以同时的锁定N/2+1的实例，而这种情况下锁会被视为无效。

您能否提供正式的安全性的证明，（或者）提出类似的现有算法，或者找出bug？这将不胜感激。

活性讨论

系统的活性主要有以下三个特征：

锁的自动释放（当key过期时）：最终所有key都能够被再次获取。
通常情况下，客户端会在获取锁失败或者锁被获取了但是程序终止的情况下移除锁，使得我们不必等待锁过期后才能够再次获取锁。
当客户端需要重试获取锁时，它会等待一段时间，这段时间会比需要获取大多数锁的时间更长。这让在资源竞争期间出现脑裂的可能性大大降低。

然而，当出现网络分区时，我们还是要付出相当于TTL时长的可用性代价，因此如果存在连续的分区，我们会无限期的付出这这个代价。每当客户端获取了锁但是在释放锁之前被分割，就会发生这种情况。

基本上，如果存在无限期的网络分区，那么系统就可能无限期的处于不可用的状态。

性能，崩溃恢复和fsync

sync - 不等待实际同步操作成功，直接返回。

fsync - 等待同步结果成功后才返回。

使用Redis作为一个分布式锁服务，对性能的要求很高，不管是获取/释放锁的延迟，还是每秒能执行的获取/释放操作的次数。为了满足这种需求，与N个Redis服务进行通信的减少延迟的策略必定是多路复用（或者叫穷人的多路复用，把Socket置于非阻塞模式下，发送所有的命令，之后再读取所有的命令，假设客户端和每个实例的RTT（Round-Trip Time：往返时延）都是接近的）。

但是，如果我们想得到能在崩溃后恢复系统的模型，那么我们还需要考虑持久化的问题。

从根本上看，这里的问题是，假设我们配置Redis时没有设置持久化这一项，客户端要获取总共5台实例里面其中3台实例的锁，然后其中一台实例在客户端获取锁时重启了，这个时候针对同一资源，我们又有3台实例能够被访问获取到锁，然后另一个客户端成功获取到了锁。这就违反了排它锁的安全性。

如果我们开启了AOF的方式进行持久化，那么情况就会得到很大的改善。例如，我们可以在升级一个服务的时候发送SHUTDOWN命令然后重启它。因为Redis的过期是在语义上实现的，所以当服务关闭时，实际上时间仍在流逝（我的理解是并不是直接关闭，而是会有一段缓冲时间来持久化内存中的数据，重启后不会丢失），我们所有的要求都可以满足。当然，只要是优雅的停机所有的情况都会很好。那么如果突然断电呢？如果Redis默认配置了每秒都进行fsync同步数据到磁盘中，那么还是有可能出现重启之后key丢失的情况。理论上，我们要想在任何情况下的实例重启中都能保证锁的安全性，我们需要启用 fsync = 一直会处于持久化的设定状态。这反过来会破坏传统上以安全方式实现分布式锁的同级别的CP系统的性能。

但是事情比乍一看要好得多。基本上，只要实例在崩溃重启后不再参与到任何当前活动的锁当中，算法就能一直保持安全性。所以，当实例重启时一组当前正在活动的锁全部是锁定（其它正常的）实例而非这台正在重新加入系统的实例。

为了保证这些，我们要做的就是在一台实例崩溃后，至少要（让这台实例）在比我们设置的最大的TTL时间更长一点的时间段内保持不可用，这个时间（TTL）就是实例崩溃时存在的所有与锁有关的key变为无效并且自动释放所需的时间。

使用delayed restarts（延迟重启）基本上能保证安全性，即便没有任何Redis持久化的设置。但要注意的是，这可能会导致可用性下降。比如说大多数的实例都崩溃了，那么系统就会在TTL时间内变得全局不可用（这儿的全局指的是没有一个资源能够在这段时间内被锁定）。