Distributed Systems
Is Redlock safe? by antirez
Apr 04, 2020
from http://antirez.com/news/101

分布式系统研究者 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 能调正时钟非常有信心。”(这点我们同意;-) 他继续说道…)

“在这种情况下,让我们看一个进程暂停可能导致算法失败的示例:

如果你阅读了我几个月没有接触过的 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