分布式系统研究者 Martin Kleppmann 昨天发表了一篇关于 Redlock（http://redis.io/topics/distlock）的分析，你可以在这里看到：http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

Redlock 是我设计的一个运行在客户端的分布式锁算法，原本用于 Redis，但该算法本质上是在客户端协调一组具备特定能力的数据存储节点，以创建一个多主、容错且尽可能安全的、支持自动释放的分布式锁。例如，你完全可以用 MySQL 而不是 Redis 来实现 Redlock。

该算法的目标是让那些原本使用单个 Redis 实例或带故障转移的主从架构来实现分布式锁的人，能够转向一种更可靠、更安全，同时又保持极低复杂度和良好性能的方案。

自我发布 Redlock 以来，已有人用多种语言实现了它，并将其用于不同的场景。

Martin 对该算法的分析得出的结论是 Redlock 并不安全。Martin 能发表这样一篇分析是件好事，我在最初的 Redlock 规范（http://redis.io/topics/distlock）中就曾呼吁大家来进行分析。所以，感谢 Martin。不过我并不认同这篇分析。好在分布式系统不像编程的其他领域，它在很大程度上是相当精确的数学，要么是，要么不是，因此一个算法能否在特定假设下保证某组属性，是可以明确判断的。在本文中，我将对 Martin 的分析进行剖析，以便领域内的其他专家能够对照这两份文档（分析与反驳分析），最终弄清楚 Redlock 是否可以被认为是安全的。

Martin 为何认为 Redlock 不安全

分析中的论点主要有两点：

1. 具备自动释放功能的分布式锁（即互斥性仅在获取锁之后的一段固定时间内有效）需要一种机制，来避免客户端在过期之后仍继续使用锁、从而在访问共享资源时破坏互斥性的问题。Martin 认为 Redlock 并没有这样的机制。
2. Martin 认为，无论是否存在问题“1”，该算法本身就是不安全的，因为它对系统模型做了在实际系统中无法得到保证的假设。

为了更清晰，我将分别回应这两个担忧，先从第一个“1”开始。

分布式锁、自动释放与令牌

一个没有自动释放机制、会让持有者无限期持有锁的分布式锁，基本上是无用的。如果持有锁的客户端崩溃，且未能在短时间内以完整状态恢复，就会形成死锁，使得分布式锁原本要保护的共享资源永远无法被访问。这会导致在大多数场景下都无法接受的活性问题，因此一个合理的分布式锁必须能够自动释放。

因此，实用的锁都会以一个最大生存时间提供给客户端。过期之后，锁最核心的属性——互斥保证——就消失了：另一个客户端可能已经获得了锁。如果两个客户端在不同时间获取了锁，但第一个客户端由于 GC 停顿或其他调度问题而异常缓慢，以至于与第二个已获得锁的客户端同时尝试在共享资源的上下文中执行操作，会发生什么？

Martin 认为，这个问题可以通过让分布式锁服务在每次授予锁时提供一个令牌来避免，在他的例子中，这个令牌就是一个保证始终递增的数字。Martin 使用令牌的理由是，这样当两个不同客户端同时访问被锁资源时，我们可以在数据库写入事务（假定它体现了客户端所做的工作）中使用该令牌：只有持有最大锁编号的客户端才能成功写入数据库。

用 Martin 的话来说：

“这个问题的修复其实很简单：你需要在每次向存储服务的写请求中都带上一个 fencing token。在此上下文中，fencing token 就是一个每次客户端获取锁时都会递增的数字（例如由锁服务递增）”

… 略 …

“注意，这要求存储服务器主动参与检查令牌，并拒绝任何令牌回退的写入”。

我认为这一论点存在不少问题：

1. 在大多数需要能够保证互斥性的分布式锁系统的场景中，一旦该属性被破坏，你就已经失败了。分布式锁之所以非常有用，恰恰是因为我们在共享资源上没有其他控制手段。在他的分析中，Martin 假设当锁的互斥性被破坏时，你总有其他办法来避免竞态条件。我认为这种对强保证分布式锁的论证方式很奇怪——如果你能用别的方式解决竞态，那为什么还要使用一个强保证的锁呢。不过，为了说明 Redlock 即便在这种非常人为设定的上下文中也能很好地工作，我还是会在下面继续讨论其他几点。
2. 如果你的数据存储只有在令牌大于所有历史令牌时才接受写入，那么它就是一个线性一致的存储。如果你已经拥有一个线性一致的存储，你完全可以为每次获取到的 Redlock 生成一个递增 ID，这样 Redlock 就等同于另一个每次授予新锁都提供递增令牌 ID 的分布式锁系统了。不过在下一点中我会说明这其实并不必要。
3. 然而“2”无论如何都不是一个明智的选择：大多数时候，对共享资源进行操作的结果并不是写入一个线性一致的存储，那该怎么办？每个 Redlock 都会关联一个很大的随机令牌（其生成方式可以忽略碰撞，Redlock 规范的原文是“来自 /dev/urandom 的 20 字节”）。有了唯一令牌能做什么？例如，你可以实现 Check and Set。在开始操作共享资源时，我们将其状态设为“`<token>`”，然后仅在写入时令牌仍保持不变的情况下才执行读-改-写操作。
4. 注意，在某些用例中，有人可能会说有序令牌终归是有用的。虽然很难想到具体的用例，但要注意的是，正如 Martin 提到的 GC 停顿，获取令牌的顺序并不一定与客户端尝试操作共享资源的顺序一致，因此加锁顺序与对共享资源操作所产生的影响之间可能并没有因果关联。
5. 大多数时候，锁被用于访问以非事务方式更新的资源。例如，有时我们使用分布式锁来移动物理对象，或与另一个外部 API 交互，等等。

我想再次强调，这一切奇怪之处在于，它假定你必须总有办法来处理互斥性被破坏的情况。实际上，如果你已经有这样一套能在竞态期间避免问题的系统，你很可能根本不需要分布式锁，或者至少不需要一个强保证的锁，而只需要一个弱锁来在大多数时候避免并发访问、仅出于性能原因。

然而，即便你碰巧认同 Martin 认为上述机制非常有用的观点，归根结底，每个锁的唯一标识符也能实现同样的目标，而且在不需要存储端提供强保证方面要实用得多。

来谈谈系统模型

上述批评基本上适用于所有带自动释放、且未在每次加锁时提供单调递增计数器的分布式锁。然而 Martin 的另一项批评是专门针对 Redlock 的。在这里，Martin 真正分析了该算法，并得出结论认为它是不可靠的。

Redlock 假设的是一种半同步系统模型，即不同进程能够以大致相同的“速度”来计时。不同进程完全不需要在绝对时间上具有有界误差。它们只需要能够做到，例如以最多 10% 的误差来计量 5 秒。也就是说，一个进程实际计为 4.5 秒，另一个计为 5.5 秒，这样就没问题。

Martin 还声称 Redlock 要求消息的最大延迟是有界的，据我所知这并不正确（稍后我会解释他的推理存在什么问题）。

那么，我们先从不同进程无法以相同速率计时的问题说起。

Martin 说，系统时钟可能会由于两个原因而随机跳变：

1. 系统管理员手动修改了时钟。
2. ntpd 守护进程在收到更新后大幅调整了时钟。

上述两个问题可以通过以下方式避免：“1”不要这么做（否则即使用“echo foo > /my/raft/log.bin”来破坏 Raft 日志也是个问题），以及“2”使用不会直接跳变时间、而是将时间调整分摊到更长时间段内的 ntpd。

不过我认为 Martin 说得对，Redis 和 Redlock 的实现应该切换到大多数操作系统提供的单调时间 API，以减轻上述问题。这在过去已被多次提议，虽然会在 Redis 内部增加一些复杂性，但确实是个好主意：我会在接下来几周内实现它。然而，尽管我们会因为其优势而切换到单调时间 API，但在没有软件（时间服务器）或人为（系统管理员）因素篡改时钟的操作系统中，进程即便使用 gettimeofday() 也*能够*以有界误差来计量相对时间。

要注意，过去曾有人尝试在假设绝对时间误差有界的前提下实现分布式系统（通过使用 GPS 设备）。Redlock 并不需要那样，它只需要不同进程能够将 10 秒计为 9.5 秒或 11.2 秒（例如最多 +/- 2 秒误差）之类的能力即可。

那么，Redlock 安全吗？这取决于上述前提。为简单起见，我们假设使用单调递增的时间 API，以排除实现细节（比如热爱 POKE 和时间服务器的系统管理员）。进程能否以固定的最大误差百分比来计量相对时间？我认为答案是响亮的“能”，而且回答这个问题比回答“进程能否在不损坏日志的情况下写入日志”要简单得多。

网络延迟及其他

Martin 说，Redlock 不仅仅依赖于进程能够以大致相同的时间来计时，他说：

“然而，Redlock 并非如此。它的安全性依赖于大量的时序假设：它假设所有 Redis 节点在过期前都能以大致正确的时间持有键；假设网络延迟相对于过期时长是很小的；并且假设进程暂停远短于过期时长。”

那么，让我们把上述论断拆成几个部分：

1. Redis 节点以大致正确的时间持有键。
2. 网络延迟相对于过期时长是很小的。
3. 进程暂停远短于过期时长。

每当 Martin 说“系统时钟跳变”时，我都假定我们已经通过不以对算法造成问题的方式拨弄系统时间，或为简单起见通过使用单调时间 API，解决了这一问题。那么：

关于论点 1：这不是问题，我们已经假定能够以大致相同的速度计时，除非有任何实际的论据来反驳这一点。

关于论点 2：情况要复杂一些。Martin 说：

“好吧，也许你认为时钟跳变是不现实的，因为你非常确信自己已正确配置了 NTP，使其只会平滑地调整时钟。”（是的，这点我们认同 ;-) 他继续说道……）

“在这种情况下，让我们来看一个进程暂停如何导致算法失败的例子：客户端 1 向节点 A、B、C、D、E 请求加锁。当发往客户端 1 的响应还在传输途中时，客户端 1 进入了 stop-the-world GC。所有 Redis 节点上的锁都过期了。客户端 2 在节点 A、B、C、D、E 上获得了锁。客户端 1 结束 GC，并收到来自 Redis 节点的响应，显示它已成功获得锁（这些响应在进程暂停期间一直滞留在客户端 1 的内核网络缓冲区中）。此时客户端 1 和客户端 2 都认为自己持有了锁。”

如果你去读我已有数月未改动的 Redlock 规范，可以看到获取锁的步骤是：

1. 获取当前时间。
2. … 执行获取锁所需的所有步骤 …
3. 再次获取当前时间。
4. 检查是否已经超时，或是否已足够快地获得了锁。
5. 使用你的锁进行一些工作。

注意步骤 1 和 3。无论在相关网络或进程中发生何种延迟，在获得多数节点认可后，我们都会*再次检查*是否仍未超时。延迟只可能发生在步骤 3 之后，导致锁被认为是有效的而实际上已过期，也就是说，我们又回到了 Martin 所指出的第一个分布式锁问题——客户端未能在锁有效期过期前停止对共享资源的操作。让我再说一遍，这个问题在*所有分布式锁实现*中都是常见的，而令牌作为解决方案既不现实，也同样可以用于 Redlock。

注意，无论在 1 和 3 之间发生什么，你可以加入任意的网络延迟，如果耗时过长，锁总是会被视为无效，因此 Redlock 看起来完全不受进程间消息无界延迟的影响。它正是带着这一目标设计的，我看不出上述竞态条件如何能够发生。

然而 Martin 的博文也经过了多位分布式系统专家的审阅，所以我不确定是我在这里遗漏了什么，还是 Redlock 的工作方式同时被许多人忽略了。我很乐意就此收到一些澄清。

上述内容也回应了关于“进程暂停”的第 3 点担忧。在获取锁的过程中发生的暂停不会影响算法的正确性。不过，正如上文已讨论的，与任何其他带自动释放的分布式锁一样，它们可能会影响客户端在指定锁生存时间内完成工作的能力。

关于网络延迟的题外话

顺便简单提一下。在带自动释放的分布式锁的服务端实现中，客户端可能会请求获取锁，服务端可能会允许，但进程可能会陷入 GC 停顿，或网络可能很慢等等，因此客户端可能会过晚才收到“好的，锁是你的”这一回复，此时锁已经过期了。然而，你可以采取很多措施来避免进程长时间休眠，却很难对网络延迟做太多，因此在获取锁前后检查时间、查看还剩多少时间的步骤，实际上即便在使用其他带过期时间的锁系统时，也应该是常见做法。

要不要 fsync？

在某处，Martin 谈到 Redlock 使用了节点的延迟重启。这同样要求能够或多或少等待一段指定的时间，如上所述。没有必要再重复同样的内容。

然而，关于这一点重要的是，这一步是可选的。你可以将每个 Redis 节点配置为在每次操作时都执行 fsync，这样当客户端收到回复时，就知道锁已经被持久化到磁盘。这就是大多数提供强保证的其他系统的工作方式。Redlock 非常有趣的一点在于，你可以通过实现延迟重启来完全不涉及磁盘。这意味着仅用几个 Redis 实例就有可能每秒处理数十万个锁，这是其他系统无法做到的。

GPS 设备与本地计算机时钟的对比

回到系统模型，Redlock 系统模型之所以实用的一点在于，你可以假定进程永远不会与系统时钟发生分区。注意，这与其他使用 GPS 设备的半同步模型不同，因为在那种情况下可能会发生两种不那么明显的分区：

1. GPS 与 GPS 网络分区，无法获得定位。
2. 进程与 GPS 之间无法交换消息，或交换的消息存在延迟。

上述问题可能会导致活性或安全性违规，具体取决于系统如何编排（安全性问题仅在存在设计错误时才会发生，例如 GPS 异步更新系统时间，以至于当 GPS 不工作时，绝对时间误差可能会超出最大界限）。

Redlock 的系统模型没有这些复杂性，也不需要额外的硬件，只需要计算机时钟，甚至是一个非常廉价的、带有因晶体温度和其他影响精度的因素而产生的明显偏差的时钟即可。

结论

我认为 Martin 关于单调时间 API 的观点是有道理的，Redis 和 Redlock 的实现应该使用它来避免因系统时钟被篡改而产生的问题。然而，如上所述，我找不到分析中其他影响 Redlock 安全性的论点，也不认为他关于当需要互斥保证时人们不应使用 Redlock 的最终结论是合理的。

如果能收到更多来自专家的反馈，并使用 Jepsen 或类似工具对该算法进行测试以积累更多数据，那就太好了。

非常感谢帮助我审阅本文的朋友们。