译文-Is Redlock safe? - <antirez>
Redlock是安全的吗？
antirez 1973 天前. 316555次浏览。
分布式系统研究员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不安全
分析中的论点主要有两个。
具有自动释放功能的分布式锁（互斥锁属性只在获得锁后的固定时间内有效）需要一种方法来避免客户在过期后使用锁，在访问共享资源时违反互斥的问题。Martin说，Redlock没有这样的机制。
Martin说，即使不管上述问题1，该算法本质上是不安全的，因为它对系统模型做了假设，而这些假设在实际系统中无法保证。
为了清楚起见，我将分别讨论这两个问题，从第一个问题 "1 "开始。
分布式锁、自动释放和tokens
一个没有自动释放机制的分布式锁，锁的主人将无限期地持有它，基本上是没有用的。如果持有锁的客户端崩溃了，并且没有在很短的时间内恢复完整的状态，就会产生一个死锁，即分布式锁试图保护的共享资源永远无法访问。这就产生了一个在大多数情况下不可接受的有效性问题，所以一个合理的分布式锁必须能够自动释放自己。
因此，实用的锁是提供给客户的，有一个最大的生存时间。在过期后，作为锁的*主要属性的互斥保证就没有了：另一个客户端可能已经拥有了这个锁。如果两个客户端在两个不同的时间获得了锁，但由于GC暂停或其他调度问题，第一个客户端的速度非常慢，它将试图在共享资源的上下文中与第二个获得锁的客户端同时进行工作，会发生什么情况？
Martin说，这个问题可以通过让分布式锁服务器为每个锁提供一个令牌来避免，在他的例子中，令牌只是一个数字，保证总是递增的。马丁使用令牌的理由是，这样一来，当两个不同的客户同时访问被锁的资源时，我们可以在数据库写入事务中使用令牌（假定将客户的工作具体化）：只有拥有最大锁号的客户才能写入数据库。
用马丁的话说。
"这个问题的解决方法其实很简单：你需要在向存储服务的每个写请求中包含一个防护令牌。在这种情况下，防护令牌只是一个数字，每次客户端获得锁的时候，这个数字就会增加（例如由锁服务增加）"
......剪辑......
"请注意，这需要存储服务器在检查令牌方面发挥积极作用，并拒绝任何令牌已经倒退的写入"。
我认为这种说法有很多问题。
大多数时候，当你需要一个能够保证相互排他性的分布式锁系统时，当这个属性被违反时，你已经输了。分布式锁正是在我们对共享资源没有其他控制的时候非常有用。在他的分析中，Martin假设当锁的互斥性被违反时，你总是有一些其他的方法来避免竞争条件。我认为这是一种非常奇怪的方式来推理具有强保障的分布式锁，不清楚为什么你会使用具有强属性的锁，如果你能以不同的方式解决竞争。然而，我将继续下面的其他观点，只是为了说明Redlock在这种非人为的情况下可以很好地工作。
如果你的数据存储总是在你的令牌大于所有过去的令牌时才接受写入，那么它就是一个可线性化存储。如果你有一个可线性化的存储，你就可以为每一个Redlock获得的ID生成一个增量，所以这将使Redlock等同于另一个分布式锁系统，在每一个新的锁中提供一个增量的令牌ID。然而在下一点中，我将说明这一点是不需要的。
然而 "2 "并不是一个明智的选择：大多数时候，对共享资源工作的结果并不是写到一个可线性化的存储中，那么该怎么做？每个Redlock都与一个大的随机令牌相关联（该令牌的生成方式可以忽略碰撞。Redlock规范的文字假设是 "来自/dev/urandom的20字节"）。) 你对一个唯一的令牌做什么？例如，你可以实现Check和Set。当开始处理一个共享资源时，我们把它的状态设置为"
<token>"，然后我们只在写入时令牌仍然相同的情况下操作读-修改-写入。请注意，在某些用例中，人们可以说，无论如何，有秩序的令牌是很有用的。虽然很难想出一个用例，但请注意，对于Martin提到的同样的GC暂停，获得令牌的顺序，并不一定尊重客户尝试对共享资源工作的顺序，所以锁的顺序可能与对共享资源工作的效果不随便相关。
大多数时候，锁被用来访问那些以非事务性方式更新的资源。有时我们使用分布式锁来移动物理对象，比如说。或者与另一个外部API进行交互，等等。
我想再次提到，这一切的奇怪之处在于，它假定你总是必须有一种方法来处理相互排斥被违反的事实。事实上，如果你有这样一个系统来避免竞争条件下的问题，你可能根本不需要一个分布式锁，或者至少你不需要一个有强大保证的锁，而只是一个弱锁来避免，大多数时候，由于性能原因的并发访问。
然而，即使你碰巧同意Martin关于上述事实是非常有用的，底线是每个锁的唯一标识符可以用于相同的目标，但在不要求存储的强一致方面更实用。
我们来谈谈系统模型
上面的批评基本上是所有的东西都有的，它是一个自动释放的分布式锁，而不是在每个锁上提供一个单调增加的计数器。然而，Martin的另一个批评是针对Redlock的。在这里，Martin真正分析了这个算法，得出的结论是它被破坏了。
Redlock假设了一个半同步的系统模型，不同的进程可以以差不多的 "速度 "计算时间。不同的进程不需要以任何方式在绝对时间上有一个约束误差。他们需要做的只是，例如，能够以最大10%的误差计算5秒。因此，一个人计算实际4.5秒，另一个人计算5.5秒，我们就可以了。
Martin还指出，Redlock需要约束信息的最大延迟，就我所知，这并不正确（我将在后面解释他的推理有什么问题）。
因此，让我们从不同进程无法以相同的速度计算时间的问题开始。
Martin说，由于两个问题，时钟会在系统中随机跳跃。
系统管理员手动改变了时钟。
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和时间服务器情有独钟的系统管理员）。一个进程可以用最大误差的固定百分比来计算相对时间吗？我认为这是一个响当当的YES，对这个问题的回答是比对的更简单。"一个进程能否在不破坏日志的情况下写入日志"？
网络延迟与合作
Martin说，Redlock不仅仅取决于进程可以在大约同一时间计算时间，他说。
"然而，Redlock不是这样的。它的安全性取决于很多时间上的假设：它假设所有Redis节点在过期前持有密钥的时间长度大致正确；网络延迟与过期时间相比很小；进程暂停比过期时间短很多"。
因此，让我们把上述主张分成不同的部分。
Redis节点持有密钥的时间长度大致合适。
网络延迟与过期时间相比是很小的。
进程暂停时间比到期时间短得多。
在Martin说 "系统时钟跳动 "的所有时间里，我假设我们通过不以对算法有问题的方式探究系统时间，或者为了简单起见，通过使用单调的时间API来覆盖这个问题。所以。
关于权利要求1：这不是一个问题，我们假定我们可以以相同的速度计算时间，除非有任何实际的反对意见。
关于权利要求2：事情要复杂一些。Martin说
"好吧，也许你认为时钟跳动是不现实的，因为你对正确配置NTP，使其只进行时钟回转非常有信心。" (是的，我们在这里同意;-)他继续说...)
"在这种情况下，让我们看一个例子，说明进程暂停可能导致算法失败。
客户端1请求锁定节点A、B、C、D、E。
当对客户端1的响应在路途中时，客户端1进入停止世界的GC。
所有Redis节点的锁都过期了。
客户端2获得了节点A、B、C、D、E的锁。
客户端1完成了GC，并收到了来自Redis节点的响应，表明它成功获得了锁（当进程暂停时，它们被保存在客户端1的内核网络缓冲区）。
客户端1和2现在都认为他们持有该锁。"
如果你阅读了我几个月没碰过的Redlock规范，你可以看到获取锁的步骤是。
获取当前时间。
...获取锁所需的所有步骤...
再次获取当前时间。
检查我们是否已经没有时间了，或者我们是否足够快地获得了锁。
用你的锁做一些工作。
注意步骤1和3。无论网络或相关进程中发生什么延迟，在获得大多数人之后，我们再次检查我们是否超出了时间。延迟只能发生在步骤3之后，导致锁被认为是可以的，而实际上已经过期了，也就是说，我们又回到了Martin发现的分布式锁的第一个问题，即客户未能在锁有效期过期之前停止对共享资源的工作。让我再讲讲这个问题是如何在所有的分布式锁实现中普遍存在的，以及作为解决方案的令牌是如何既不现实又可以用于Redlock的。
请注意，无论在1和3之间发生什么，你都可以添加你想要的网络延迟，如果时间过长，锁将永远被认为是无效的，所以Redlock看起来完全不受进程之间有非绑定延迟的消息的影响。它在设计时就考虑到了这一目标，我看不出上述的竞赛条件会发生。
然而Martin的博文也被多位DS专家审阅过，所以我不确定我在这里是否遗漏了什么，或者仅仅是Redlock的工作方式被很多人同时忽略了。我很乐意收到一些关于这方面的澄清。
上述内容也解决了 "过程暂停 "的关注点3。在获取锁的过程中，暂停不会对算法的正确性产生影响。然而，它们会影响客户端在指定的锁时间内进行工作的能力，就像上面已经提到的任何其他自动释放的分布式锁一样。
关于网络延迟的题外话
只是一个简单的说明。在带有自动释放功能的分布式锁的服务器端实现中，客户端可能会要求获得一个锁，服务器可能会允许客户端这样做，但进程可能会停止进入GC暂停，或者网络可能很慢或其他什么原因，所以客户端可能会在锁已经过期的情况下收到 "OK，锁是你的 "的消息，这已经太晚了。然而，你可以做很多事情来避免你的进程沉睡很长时间，你也不能做很多事情来避免网络延迟，所以在获得锁之前/之后检查时间的步骤，看看还有多少时间，实际上应该是常见的做法，即使是在使用其他实现过期锁的系统。
是否同步？
在某些时候，Martin谈到了Redlock使用延迟重启节点的事实。这同样需要能够或多或少地等待指定的时间，如上文所述。再次重复同样的事情是没有用的。
然而关于这一点，重要的是，这一步是可选的。你可以配置每个Redis节点在每次操作时进行fsync，这样，当客户端收到回复时，它就知道锁已经持久化在磁盘上了。这就是其他大多数提供强担保的系统的工作方式。Redlock非常有趣的一点是，你可以通过实现延迟重启来选择不涉及任何磁盘。这意味着用几个Redis实例就可以每秒处理几十万个锁，这在其他系统中是无法实现的。
GPS装置与本地计算机时钟的对比
回到系统模型，使Redlock系统模型实用的一点是，你可以假设一个进程永远不会与系统时钟发生分区。请注意，这与其他使用GPS单元的半同步模型不同，因为在这种情况下，有两种非明显的分区可能发生。
GPS被隔断在GPS网络之外，所以它不能获得一个固定值。
进程和GPS不能交换信息，或者交换的信息有延迟。
上述问题可能会导致失效或安全违规，这取决于系统的协调方式（安全问题只有在设计错误时才会发生，例如，如果GPS异步更新系统时间，那么，当GPS不工作时，绝对时间误差可能会超过最大界限）。
Redlock系统模型没有这些复杂性，也不需要额外的硬件，只需要计算机时钟，甚至是一个非常便宜的时钟，由于晶体温度和其他影响精度的东西，会有所有明显的偏差。
结论
我认为Martin对于单调的API是有道理的，Redis和Redlock的实现应该使用它来避免由于系统时钟被改变而引起的问题。然而，我无法确定影响Redlock安全性的其他分析点，正如上面所解释的那样，我也不认为他的最后结论是合理的，即在需要互斥保证时人们不应该使用Redlock。
如果能从专家那里得到更多的反馈，并且用Jepsen或类似的工具测试该算法，以积累更多的数据，那将是非常好的。
衷心感谢帮助我审核这篇文章的朋友。
blog comments powered by Disqus
