Redlock 安全吗？
分布式系统研究者 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 以来，人们用多种语言实现了它，并将其用于不同的目的。
马丁对该算法的分析结论是 Redlock 不安全。马丁发表了这篇分析，这是很好的事情，因为我在最初的 Redlock 规范中就请求过这样的分析，见这里： http://redis.io/topics/distlock。所以谢谢你，马丁。不过我不同意这篇分析。好消息是，分布式系统与其他编程领域不同，在数学上是相当精确的：要么成立，要么不成立——一组给定的性质要么能由某个算法保证，要么该算法在某些假设下无法保证它们。在本文中，我将分析马丁的分析，以便该领域的其他专家能够核查这两份文档（原分析和反分析），并最终弄清 Redlock 是否可以被认为是安全的。
马丁为什么认为 Redlock 不安全
这篇分析中的论点主要有两个：
- 具有自动释放特性的分布式锁（互斥性仅在获得锁之后的固定时间内有效）需要某种机制来避免客户端在锁过期之后仍然使用锁、从而在访问共享资源时破坏互斥性的问题。马丁说 Redlock 没有这样的机制。
- 马丁说，即使不考虑问题“1”，该算法本质上也是不安全的，因为它对系统模型所做的假设在实际系统中无法得到保证。
为清晰起见，我将分别讨论这两个问题，先从第一个“1”开始。
分布式锁、自动释放与令牌
一个没有自动释放机制的分布式锁——即锁的持有者会无限期地持有它——基本上是没用的。如果持有锁的客户端崩溃，并且在短时间内没有以完整状态恢复，就会产生死锁：分布式锁本想保护的共享资源将永远无法访问。这在大多数情况下都是不可接受的 liveness（活性）问题，所以一个合理的分布式锁必须能够自动释放。
因此，实用的锁会向客户端提供一个最长生存时间。过期之后，互斥性保证——锁的*主要*性质——就不复存在了：另一个客户端可能已经拿到了锁。如果两个客户端在不同的时刻获得锁，但第一个客户端由于 GC 停顿或其他调度问题而非常慢，以至于它会和第二个已获得锁的客户端同时尝试对共享资源做工作，会发生什么？
马丁说，这个问题可以通过让分布式锁服务器在提供每个锁时附上一个令牌来解决，在他的例子里，这个令牌就是一个保证总是递增的数字。马丁使用令牌的理由是：这样，当两个不同的客户端同时访问被锁住的资源时，我们可以在数据库写入事务（假定客户端的工作就体现在这个事务里）中使用该令牌：只有持有较大锁编号的客户端才能写入数据库。
用马丁的话说：
“这个问题的修复方法其实相当简单：你需要在对存储服务的每个写请求中包含一个 fencing token(围栏令牌)。在这里，围栏令牌就是一个每次客户端获得锁时都会递增的数字（例如由锁服务递增）”
……略……
“注意，这要求存储服务器在检查令牌方面扮演主动角色，拒绝任何令牌出现回退的写入”。
我认为这个论点存在几个问题：
- 大多数时候，当你需要一个能保证互斥性的分布式锁系统时，一旦这个性质被破坏，你就已经输了。分布式锁恰恰在我们对共享资源没有其他控制手段时才非常有用。在他的分析中，马丁假定当锁的互斥性被破坏时，你总是有某种其他方式来避免竞态条件。我认为这是一种非常奇怪的推理方式——如果你能以别的方式解决竞态，那你究竟为什么要使用具有强性质的锁呢？不过为了表明 Redlock 在这个非常人为的场景下也能良好工作，我将继续讨论下面各点。
- 如果你的数据存储只有在你的令牌大于所有过去的令牌时才接受写入，那它就是一个 linearizable store(线性一致存储)。如果你有一个线性一致存储，你只需为每次获得的 Redlock 生成一个递增 ID，这会使 Redlock 等价于另一个为每把新锁提供递增令牌 ID 的分布式锁系统。不过在下一点中我会说明为什么并不需要这样做。
- 而且“2”本身也不是一个合理的选择：大多数时候，对共享资源工作的结果并不是写入一个线性一致存储，那该怎么办？每个 Redlock 都关联着一个大的随机令牌（其生成方式使得碰撞可以忽略不计。Redlock 规范原文假定“来自 /dev/urandom 的 20 个字节”）。对于一个唯一令牌你能做什么？例如，你可以实现 Check and Set。开始对共享资源工作时，我们把它的状态设为“`<token>`”，然后只有当令牌在写入时仍然相同时才执行读-改-写操作。
- 注意，在某些用例中，可以说有序的令牌无论如何还是有用的。虽然很难想出这样的用例，但要注意，由于马丁提到的同样的 GC 停顿问题，令牌被获取的顺序并不一定符合客户端尝试对共享资源工作的顺序，所以锁的顺序可能与对共享资源工作的结果没有因果关系。
- 大多数时候，锁被用来访问以非事务方式更新的资源。例如，有时我们用分布式锁来搬运物理对象，或者与另一个外部 API 交互，等等。
我想再次指出，这一切的奇怪之处在于：它假定你必须总是有办法处理互斥性被破坏这一事实。实际上，如果你有这样一套在竞态条件期间避免问题的系统，你很可能根本不需要分布式锁，或者至少不需要具有强保证的锁，而只需要一个弱锁来出于性能原因在大多数时候避免并发访问即可。
不过，即使你恰好同意马丁关于上述方案非常有用的看法，底线是：每把锁的唯一标识符可以达到同样的目标，而且实用得多，因为它不要求存储提供强保证。
来谈谈系统模型
上面的批评基本上对一切具有自动释放、但不随锁提供单调递增计数器的分布式锁都成立。然而马丁的另一项批评是专门针对 Redlock 的。在这里马丁才真正分析了算法本身，并得出它有缺陷的结论。
Redlock 假定一个半同步系统模型，其中不同的进程可以以大致相同的“速度”计量时间。这些进程完全不需要在绝对时间上有界误差。它们需要做的只是，例如，能够以最大 10% 的误差计量 5 秒。一个进程实际计了 4.5 秒，另一个计了 5.5 秒，这就没问题。
马丁还说 Redlock 要求有界的消息最大延迟，据我所知这是不正确的（稍后我会解释他的推理问题出在哪里）。
那么我们先从“不同进程无法以相同速率计量时间”这个问题开始。
马丁说，系统中的时钟可能因两个问题而随机跳变：
- 系统管理员手动修改时钟。
- ntpd 守护进程因为收到更新而大幅改变时钟。
上述两个问题可以这样避免：“1”不去做这件事（否则用“echo foo > /my/raft/log.bin”破坏一个 Raft 日志也算是个问题），而“2”使用一种不会直接跳变时间、而是把改变分散到较长时间跨度内完成的 ntpd。
不过我认为马丁有一点是对的：Redis 和 Redlock 的实现应该改用大多数操作系统提供的单调时间 API，以使上述问题不那么严重。过去已经有人多次提出这个建议，它会给 Redis 内部增加一点复杂度，但这是个好主意：我会在接下来几周内实现它。不过，虽然我们会切换到单调时间 API（因为它有好处），但在没有软件（时间服务器）或人为（系统管理员）因素改变时钟的操作系统上运行的进程，*即使*使用 gettimeofday() 也*能够*以有界误差计量相对时间。
注意，过去甚至有人尝试在假定绝对时间误差有界的条件下实现分布式系统（通过使用 GPS 设备）。Redlock 不需要任何那样的东西，只需要不同进程能够把 10 秒计量为 9.5 或 11.2 秒（例如最大 ±2 秒）的能力。
那么 Redlock 到底安全不安全？这取决于上面所说的。为简单起见，让我们假定使用单调递增时间 API，以排除实现细节问题（热爱 POKE 的系统管理员和时间服务器）。一个进程能以固定的最大误差百分比计量相对时间吗？我认为这是一个响亮的“是”，而且回答“是”比回答“一个进程能否在不损坏日志的情况下写日志？”要简单得多。
网络延迟等
马丁说，Redlock 不仅仅依赖于进程能够以大致相同的速度计量时间这一事实，他说：
“然而，Redlock 并非如此。它的安全性依赖于大量的时间假设：它假定所有 Redis 节点都在大致正确的时间长度内持有键然后过期；网络延迟相对于过期时长来说很小；进程停顿远短于过期时长。”
那么让我们把上述论断拆分成几个部分：
- Redis 节点在大致正确的时间长度内持有键。
- 网络延迟相对于过期时长来说很小。
- 进程停顿远短于过期时长。
马丁每次提到“系统时钟跳变”时，我都假定我们已经通过不以便碍算法的方式改动系统时间解决了这个问题，或者为了简单起见使用单调时间 API。那么：
关于论断 1：这不是问题，我们已假定能够以大致相同的速度计量时间，除非有实际的论据反驳这一点。
关于论断 2：事情要稍微复杂一些。马丁说：
“好吧，也许你认为时钟跳变不现实，因为你非常确信自己正确配置了 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 和 3。无论网络或相关进程中发生什么延迟，在获得多数派之后，我们*再次检查*自己没有超时。延迟只能发生在步骤 3 之后，导致锁被认为仍然有效而实际上已过期，也就是说，我们回到了马丁识别出的第一个问题：分布式锁中客户端未能在锁有效期到期之前停止对共享资源的工作。让我再说一遍，这个问题在*所有*分布式锁实现中都很常见，而令牌作为解决方案既不现实，也同样可以与 Redlock 一起使用。
注意，无论步骤 1 和 3 之间发生什么，你可以随意添加网络延迟，如果流逝的时间太多，锁总会被认为无效，所以 Redlock 看起来对进程之间具有无界延迟的消息完全免疫。它的设计目标正是如此，我看不出上述竞态条件怎么可能发生。
不过，马丁的博文也经过了多位分布式系统专家的审阅，所以我不确定是我遗漏了什么，还是 Redlock 的工作方式被许多人同时忽略了。我很乐意收到一些澄清。
上面的内容也回应了“进程停顿”这一第 3 项担忧。在获得锁的过程中发生的停顿不会影响算法的正确性。但它们可能会影响客户端在指定的锁生存时间内完成工作的能力——这与任何其他具有自动释放的分布式锁一样，如上所述。
关于网络延迟的题外话
只是简单一提。在具有自动释放的分布式锁的服务端实现中，客户端可能请求获得锁，服务器可能允许客户端这么做，但进程可能陷入 GC 停顿，或者网络可能很慢或发生其他情况，于是客户端可能过晚才收到“好的，锁是你的”，而那时锁已经过期。不过你可以做很多事情来避免进程长时间休眠，却无法做太多来避免网络延迟，所以在获得锁之前/之后检查时间、看还剩多少时间的步骤，即使在使用其他带过期的锁系统时，也应当成为常见实践。
Fsync 还是不 fsync？
马丁在某个地方谈到 Redlock 使用了节点的延迟重启。这同样需要能够等待大致指定的时间量的能力，如上所述。没必要重复同样的话。
不过这里重要的一点是：这一步是可选的。你可以配置每个 Redis 节点在每次操作时都执行 fsync，这样当客户端收到回复时，它就知道锁已经被持久化到磁盘了。大多数其他提供强保证的系统就是这样工作的。Redlock 非常有趣的一点是，你可以通过实现延迟重启来完全选择不涉及任何磁盘操作。这意味着用几个 Redis 实例每秒处理数十万把锁是可能的，这是其他系统无法做到的。
GPS 设备与本地计算机时钟
回到系统模型，使 Redlock 的系统模型实用的一点是：你可以假定一个进程永远不会与系统时钟发生分区。注意，这与使用 GPS 设备的其他半同步模型不同，因为在这种情况下可能发生两种不太明显的分区：
- GPS 设备与 GPS 网络被分区隔开，因此无法获得定位。
- 进程与 GPS 设备无法交换消息，或者交换的消息存在延迟。
上述问题可能导致 liveness（活性）或 safety（安全性）违规，具体取决于系统如何组织（安全问题只会在存在设计错误时发生，例如 GPS 异步地更新系统时间，以至于当 GPS 不工作时，绝对时间误差可能超出最大界限）。
Redlock 的系统模型没有这些复杂性，也不需要额外的硬件，只需要计算机时钟，甚至是一个非常廉价的时钟，尽管它由于晶振温度和其他影响精度的因素而存在各种明显的偏差。
结论
我认为马丁关于单调 API 的观点是有道理的，Redis 和 Redlock 的实现应该使用它，以避免系统时钟被改动带来的问题。然而，如上所述，我找不出分析中其他影响 Redlock 安全性的论点，也不认为他关于“需要互斥性保证时人们不应使用 Redlock”的最终结论是站得住脚的。
如果能收到更多专家的反馈，并用 Jepsen 或类似工具测试该算法以积累更多数据，那就太好了。
衷心感谢帮助我审阅这篇文章的朋友们。