分布式系统研究者 Martin Kleppmann 昨天发布了一篇 Redlock[1]的分析文章[2]。

Redlock 是我设计用于 Redis 的客户端分布式锁定算法。该算法编排了一组客户端节点，这些节点实现了具有特定功能的数据存储，以便创建一个多主容错的、安全的、具有自动释放功能的分布式锁。 你可以使用 MySQL 而非 Redis 来实现 Redlock。

该算法的目的是将那些还在使用单点 Redis 还有带有故障转移的主从设置的人员转移到更可靠、更安全的方法上来实现分布式锁。该方法具有非常低的复杂性和良好的性能。

自从我发布 Redlock 以来，人们就以多种语言实现了该功能并将其用于不同的目的。

Martin 对这个算法的分析结论是 Redlock 不安全。我在最初的 Redis 规范[3]中请求帮助分析，很高兴 Martin 发布了一个分析文章。非常感谢 Martin，尽管我不同意他的观点。好处是，与其他编程领域不同，分布式系统在数学上是非黑即白的。因此，某种算法要么可以保证给定的属性集，要么在某些假设下算法可能会无法保证它们。在此分析中，我将分析 Martin 的分析，以便该领域的其他专家可以检查这两个文档（分析和反分析），最终我们可以了解 Redlock 是否被认为是安全的。

为什么 Martin 认为 Redlock 不安全

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

1. 具有自动释放特性的分布式锁（互斥锁属性只在锁被获取后的固定时间内有效）需要一种方法来避免客户端在过期时间后使用锁时引发的问题，这违反了访问共享资源时的互斥性。Martin 说 Redlock 没有这样的机制。

2. Martin 说，不管问题1如何，这个算法本质上是不安全的，因为它对系统模型做出的假设在实际系统中无法得到保证。

为了清楚起见，我将从第一个问题开始，分别讨论这两个问题。

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

没有自动释放机制（锁的拥有者将无限期地持有它）的分布式锁基本上是没用的。如果持有锁的客户端崩溃，并且在短时间内无法恢复到完全状态，就会导致死锁，因为分布式锁试图保护的共享资源永远无法访问。这就产生了一个在大多数情况下都无法接受的活性问题，所以一个正常的分布式锁必须能够自动释放自己。

实际上锁提供给客户端最长的生存时间。在过期时间之后，互斥保证（锁的主要属性）就没有了：另一个客户端可能已经有了锁。如果两个客户端在两个不同的时间获得锁，但第一个因为 GC 暂停或其他调度问题非常慢，会尝试与获得锁第二个客户端在共享资源的情况下同时工作吗？

Martin 说，通过让分布式锁服务器为每个锁提供令牌可以避免此问题。在他的示例中，令牌只是保证始终递增的数字。Martin 使用令牌的理由是：当两个不同的客户端同时访问锁定的资源时，我们可以在数据库写入事务时使用令牌（假定可以实现客户端所做的工作）：只有具有最大锁号的客户端才可以写入数据库。

用 Martin 的话来说：

“这种问题的解决方案非常简单：你需要在每个对存储服务的请求中携带一个 fencing token。在此情况下，一个 fencing token 只是一个客户端获得一次锁时递增的数字（如被锁服务递增）。”

…

“这需要存储服务在检查 token 中扮演一个重要的角色，并且拒绝任何旧 token 的所有写请求。”

我认为这个论点有很多问题：

1. 在大多数需要一个分布式的锁系统来保证互斥性的情况中，当这个特性被破坏时，你就已经失去了它。当我们在共享资源中没有其他控制手段时，分布式锁非常有用。在 Martin 的分析中，假设当锁的互斥性被违反时，总需要其他的方法来避免竞争条件。我认为这是一种对具有强保证的分布式锁的推断的奇怪的方式。如果可以用另一种方式解决竞争问题，那么你为什么要使用具有强属性的锁？但是，为了说明 Redlock 在这种非常人为的环境中可以很好地工作，我将继续下面的其他要点。

2. 如果只要你的令牌大于所有过去的令牌时，你的数据存储区就始终可以接受写入，那么它是可线性化的存储区。如果你有一个可线性化的存储区，则可以为获取的每个 Redlock 生成一个增量 ID，因此这将使 Redlock 等效于另一个分布式锁系统，该系统为每个新锁提供一个增量令牌 ID。 但是，在下一点中，我将说明不需要这样做。

3. 但是无论如何，“2”不是一个明智的选择：大多数情况下，如果使用共享资源的结果没有写入线性化存储区，那么该怎么办？每个 Redlock 都与一个较大的随机令牌关联（该令牌以可以忽略冲突的方式生成。Redlock 规范在文本上假设“来自/dev/urandom 的20个字节”）。如何设置唯一令牌？CAS 吗？比如在开始使用共享资源时，我们将其状态写入“<token>”，然后仅当写入时令牌仍然相同时才 read-modify-write。

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 节点在锁大约到期前的时间里都持有 key；与有效期限相比，网络延迟较小；而且该过程的暂停比有效期短得多。”

所以让我们把上面的观点分成不同的部分：

1. Redis 节点持有 key 的时间大约是正确的。
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 暂停，或者网络可能会变慢或发生其他情况。因此，当锁已过期时，客户端可能会收到“确定，你持有锁”。 但是，你可以做很多事情来避免进程长时间休眠，但是不能避免网络延迟。因此需要执行一些步骤来检查获取锁之前/之后的时间，以了解还剩下多少时间。即使使用其他实现过期策略锁的系统，这也是惯例。

文件同步与否？

在某些点上，Martin 谈到了 Redlock 使用延迟重启节点。这再次要求能够或多或少地等待指定的时间，不再赘述。

但是，重要的是，此步骤是可选的。你可以将每个 Redis 节点配置为在每次操作时均进行 fsync。这样，当客户端收到答复时，它知道锁已在磁盘上持久保存。这就是大多数其他提供有力保证的系统的工作方式。关于 Redlock 的一个非常有趣的事情是，你可以通过实施延迟重启来完全退出任何涉及磁盘的操作。这意味着可以通过几个 Redis 实例每秒处理数十万个锁，而其他系统则无法实现。

GPS 单元与本地计算机时钟

回到系统模型，使 Redlock 系统模型实用的一件事是，你可以假定一个进程永远不会被系统时钟分区。请注意，与使用 GPS 单元的其他半同步模型相比，这是不同的，因为在这种情况下可能会发生两个不明显的分区：

1. GPS 已从 GPS 网络中分离出来，因此无法获得修复。

2. 进程和 GPS 不能交换消息，或者在交换消息中存在延迟。

上述问题可能会导致活性问题或违反安全性，具体取决于系统的协调方式（仅在出现设计错误时才会发生安全问题。例如，GPS 异步更新系统时间，那么当 GPS 无法工作时， 绝对时间误差可能会超过最大限制）。

Redlock 系统模型不具有这些复杂性，也不需要额外的硬件。仅需要计算机时钟，甚至是非常便宜的时钟，由于晶体温度和其他影响精度的因素，所有时钟都有明显的偏差。

结论

我认为 Martin 对单调 API 有自己的看法，Redis 和 Redlock 实现应该使用它来避免由于系统时钟改变而引起的问题。然而，我无法确定影响 Redlock 安全性的分析的其他要点。如上所述，我也没有发现他的最终结论，即：在需要互斥保证时人们不应使用 Redlock 是有道理的。

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

非常感谢我的朋友们帮我审阅了这篇文章。

[1] http://redis.io/topics/distlock
[2] http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
[3] http://redis.io/topics/distlock