Martin Kleppmann 于 2016 年 2 月 8 日发布，原文
作为我的书研究的一部分，我在 Redis 网站上遇到了一种名为Redlock的算法。该算法声称在Redis之上实现了容错分布式锁（或者更确切地说，租约[1]），并且该页面要求来自分布式系统人员的反馈。该算法本能地在我的脑海中敲响了警钟，所以我花了一些时间思考并写下了这些笔记。
由于Redlock 已经有 10 多个独立的实现，我们不知道谁已经在依赖这个算法，我认为值得公开分享我的笔记。我不会深入探讨 Redis 的其他方面，其中一些已经在其他地方受到批评。
在详细介绍 Redlock 之前，先说我非常喜欢 Redis，并且我过去在生产中成功使用过它。我认为它非常适合您希望在服务器之间共享一些瞬态、近似、快速变化的数据的情况，并且如果您偶尔出于某种原因丢失这些数据也没什么大不了的。例如，一个很好的用例是维护每个 IP 地址的请求计数器（为了限制访问速率）和每个用户 ID它使用的不同 IP 地址集（用于滥用检测）。
然而，Redis 已经逐渐进入数据管理领域，那里需要有更强的一致性和持久性——这让我担心，因为这不是 Redis 的设计目标。可以说，分布式锁是这些领域之一。让我们更详细地研究一下。
1. 你用那把锁做什么？
加锁的目的是确保多个节点在尝试执行相同工作时，只有一个节点实际执行此操作（至少一次只有一个）。 这项工作可能是将一些数据写入共享存储系统、执行一些计算、调用一些外部 API 等。概括而言，您可能需要在分布式应用程序中使用锁的原因有两个：为了效率或为了正确性 [2]。为了区分这些情况，你可以问如果锁失败会发生什么：
- 效率：获取锁可以避免不必要地做两次相同的工作（例如一些昂贵的计算）。如果加锁失败并且两个节点最终完成相同的工作，结果是成本略有增加（您最终向 AWS 支付的费用比其他情况多 5 美分）或带来轻微的不便（例如，用户最终两次收到相同的电子邮件通知）。
- 正确性：使用锁可以防止并发进程相互干扰并破坏系统状态。如果加锁失败导致两个节点同时处理同一条数据，后果可能是文件损坏、数据丢失、永久性不一致、给患者服用的药物剂量错误或其他一些严重问题。
以上两者都是需要使用锁的原因，但您需要非常清楚您正在处理两者中的哪一个。
如果您仅出于效率目的使用锁，则没有必要承担 Redlock 的成本和复杂性，运行 5 个 Redis 服务器并检查大多数以获得您的锁。您最好只使用单个 Redis 实例，也许可以异步复制到副本实例，以防主实例崩溃。
如果你使用单个Redis实例，当然你的Redis节点突然断电，或者出现其他问题，你的锁也会出现一些问题。但如果你只是将锁用作效率优化，并且崩溃不会经常发生，那没什么大不了的。这种“没什么大不了”的场景正是 Redis的用武之地。至少，如果您依赖单个 Redis 实例，那么查看系统的每个人都清楚锁定是近似的，并且仅用于非关键目的。
另一方面，具有 5 个副本和多数投票的 Redlock 算法乍一看似乎适用于对锁的正确性有严格要求的情况。我将在以下各节中争辩说它不适合该目的。对于本文的其余部分，我们将假设您的锁对于正确性很重要，如果两个不同的节点同时认为它们持有相同的锁，这将是一个严重的错误。
2. 用锁保护资源
让我们暂时先把 Redlock 的细节放在一边，然后讨论一下分布式锁的一般的使用方式（独立于所使用的特定锁算法）。 重要的是要记住，分布式系统中的锁不像多线程应用程序中的互斥锁。 这是一个更复杂的设计，由于不同节点和网络都可能以各种方式独立失败。
例如，假设您有一个应用程序，其中客户端需要更新共享存储（例如 HDFS 或 S3）中的文件。 客户端首先获取锁，然后读取文件，进行一些更改，将修改后的文件写回，最后释放锁。 该锁可防止两个客户端同时执行此读取-修改-写入循环，这会导致更新丢失。 代码可能如下所示：
// THIS CODE IS BROKEN
function writeData(filename, data) {
var lock = lockService.acquireLock(filename);
if (!lock) {
throw 'Failed to acquire lock';
}
try {
var file = storage.readFile(filename);
var updated = updateContents(file, data);
storage.writeFile(filename, updated);
} finally {
lock.release();
}
}
不幸的是，即使你有完美的锁服务，上面的代码也会被破坏。 下图显示了数据如何被损坏：
在这个例子中，获取锁的客户端在持有锁后暂停了很长一段时间——例如因为垃圾收集器（GC）的启动。锁有一个超时（即它是一个租约），这总是一个好主意（否则崩溃的客户端最终可能会永远持有锁并且永远不会释放它）。但是，如果 GC 暂停持续时间超过租用到期时间，并且客户端没有意识到自己持有的锁已经过期，它可能会继续进行一些不安全的更改。
这个错误就曾经发生过：HBase 曾经有这个问题 [3,4]。通常情况下，GC 暂停时间很短，但“stop-the-world”的GC暂停有时会持续几分钟 [5]——当然足以让租约到期。即使是所谓的“并发”垃圾收集器，如 HotSpot JVM 的 CMS，也不能完全与应用程序代码并行运行——即使它们有时需要”stop-the-world” [6]。
您无法通过在写回存储之前插入对锁定到期的检查来解决此问题。请记住，GC 可以在任何时间暂停正在运行的线程，包括对您来说最不方便的时间点（在最后一次检查和写入操作之间）。
如果您因为自己使用的编程语言运行时没有长时间的 GC 暂停而感到自鸣得意，那么您的进程可能会因许多其他原因而暂停。比如也许您的进程试图读取尚未加载到内存中的地址，因此它会出现缺页错误并暂停，直到从磁盘加载该页面。也许您的磁盘实际上是 EBS，因此读取一个变量在不知不觉中变成了 Amazon 拥塞网络上的同步网络请求。也许还有许多其他进程在争夺 CPU，而您在调度程序树中遇到了一个黑色节点。也许有人不小心向进程发送了 SIGSTOP等，都会使进程暂停。
如果您仍然不相信进程暂停，那么请考虑文件写入请求在到达存储服务器之前可能会因为网络堵塞而延迟。以太网和 IP 等数据包网络可能会使数据包出现任意延迟，它们确实如此 [7]：在 GitHub 的一个著名事件中，数据包在网络中延迟了大约 90 秒 [8]。这意味着一个应用进程可能会发送一个写请求，当租约已经到期时，它可能会在一分钟后才到达存储服务器。
即使在管理良好的网络中，这种事情也可能发生。你根本无法对时间做出任何假设，所以无论你使用哪种锁服务，上面的代码都是不安全的。
3. 使用防护使锁安全
修复上面的问题其实非常简单：对存储服务的每个写请求中都带一个防护令牌。在这种情况下，防护令牌只需要是一个数字，每次客户端获取锁时它都会递增（例如，由锁服务递增）。如下图所示：
客户端1获得租约和值为33的令牌，但随后进入长时间暂停，租约到期。客户端 2 获取租约，得到值为34 的令牌（数字总是递增），然后将内容和值为34的令牌都写入到存储服务。稍后，客户端1恢复正常后，将写入请求：内容和值为33的令牌 发送到存储服务。但是，存储服务器记住它已经处理了具有更高令牌号 (34) 的写入，因此它拒绝带有令牌 33 的请求。
请注意，这需要存储服务器采取主动角色检查令牌，并拒绝令牌倒退的任何写入。但这并不是特别难，一旦你知道了诀窍。并且如果锁服务生成严格单调递增的令牌，这使得锁是安全的。例如，如果您使用 ZooKeeper 作为锁定服务，您可以使用 zxid 或 znode 版本号作为防护令牌，并且您处于良好状态 [3]。
然而，这将我们引向了 Redlock 的第一个大问题：它没有任何用于生成隔离令牌的工具。该算法不会产生任何保证–即每次客户端获取锁时都会递增的数字。这意味着即使算法在其他方面是完美的，使用它也不安全，因为在一个客户端暂停或其数据包延迟的情况下，您无法防止客户端之间的竞争条件。
对我来说，如何更改 Redlock 算法以开始生成防护令牌并不明显。它使用的唯一随机值不提供所需的单调性。仅仅在一个 Redis 节点上保留一个计数器是不够的，因为该节点可能会失败。在多个节点上保留计数器意味着它们的数据会出现不同步或同步不及时。您可能需要一个共识算法来生成围栏令牌。 （如果只是增加一个计数器是简单的。）
4. 用时间解决共识
在想使用锁保证正确性的情况下不应该使用Redlock，因为Redlock无法生成 fencing 令牌。但还有一些更进一步的问题值得讨论。
在学术文献中，这种算法最实用的系统模型是带有不可靠故障检测器的异步模型 [9]。简单来说，这意味着算法不对时间做任何假设：进程可能会暂停任意长度的时间，数据包可能会在网络中任意延迟，时钟可能会任意错误——尽管如此，算法都会做正确的事物。鉴于我们上面讨论的内容，这些都是非常合理的假设。
算法使用时钟的唯一目的是产生超时，以避免在节点关闭时永远等待。但是超时不一定准确：仅仅因为请求超时，并不意味着另一个节点已关闭 – 也可能是网络中存在很大延迟，或者您的本地时钟是错的。当用作故障检测器时，超时只是猜测出了问题。 （如果可以的话，分布式算法将完全没有时钟，但这样就不可能达成共识 [10]。获取锁就像一个比较和设置操作，需要达成共识 [11]。）
请注意，Redis 使用gettimeofday，而不是单调时钟，以确定密钥的到期时间。 gettimeofday 的手册页明确指出它返回的时间会受到系统时间不连续跳跃的影响——也就是说，它可能会突然向前跳跃几分钟，甚至时间跳跃（例如，如果时钟被NTP步进，因为它与 NTP 服务器差别太大，或者如果时钟由管理员手动调整）。因此，如果系统时钟正在做一些奇怪的事情，很容易发生 Redis 中某个键的到期比预期快得多或慢得多的情况。
对于异步模型中的算法，这不是一个大问题：这些算法通常会在不基于时间做出假设[12]的前提下保证它们的安全属性始终不变。只有活性属性取决于超时或其他一些故障检测器。通俗地说，这意味着即使计时在系统中到处都是（进程暂停，网络延迟，时钟向前和向后跳跃），导致算法的性能可能会下降，但算法永远不会做出错误的决定。
然而，Redlock不是这样的。它的安全性取决于很多时间假设：
- 它假设所有 Redis 节点在过期前都持有大约合适的时间长度
- 网络延迟比过期时间短得多
- 进程暂停时间比过期时间短得多
5. 基于时间假设的Redlock不可靠
让我们看一些例子来证明 Redlock 对时间假设的依赖。假设系统有五个 Redis 节点（A、B、C、D 、 E）和两个客户端（1 和 2）。如果其中一个 Redis 节点上的时钟向前跳跃会发生什么？
- 客户端 1 获取节点 A、B、C 上的锁。由于网络问题，无法访问 D 和 E。
- 节点 C 上的时钟向前跳跃，导致锁到期。
- 客户端 2 获取节点 C、D、E 上的锁。由于网络问题，无法访问 A 和 B。
- 客户端 1 和 2 现在都相信他们持有锁。
如果 C 在将锁定持久化到磁盘之前崩溃并立即重新启动，则可能会发生类似的问题。出于这个原因，Redlock 文档建议至少将崩溃节点的重启延迟到锁的最长存活时间。但是这种重新启动延迟再次依赖于合理准确的时间测量，但在发生时钟跳跃时也会导致失败。
可能您认为发生时钟跳跃不现实，因为您对正确配置 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 现在都相信他们持有锁。
请注意，即使 Redis 是用 C 编写的，因此没有 GC，但这对我们没有帮助：任何客户端可能遇到GC暂停的系统都有这个问题。您只能通过在客户端 2 获取锁后阻止客户端 1 在锁下执行任何操作来确保安全，例如使用上面的防护方法。
较长的网络延迟会产生与进程暂停相同的效果。这可能取决于您的 TCP 用户超时——如果您使超时明显短于 Redis TTL，则可能会忽略延迟的网络数据包，但我们必须详细查看 TCP 实现才能确定。此外，随着超时，我们再次回到时间测量的准确性！
6. Redlock的同步假设
这些例子表明，Redlock 只有在你假设一个同步系统模型时才能正确工作——也就是说，一个系统具有以下属性：
- 有界网络延迟（你可以保证数据包总是在某个最大延迟时刻内到达）
- 有界进程暂停（换句话说，hard real-time constraints，您通常只能在汽车安全气囊系统等中找到）
- 有限的时钟误差（难以避免从坏的NTP服务器获取时间）
请注意，同步模型并不意味着完全同步的时钟：这意味着您假设网络延迟、暂停和时钟漂移有一个已知的、固定的上限 [12]。 Redlock 假设延迟、暂停和漂移相对于锁的生存时间来说都很小； 如果时序问题变得与生存时间一样大，算法就会失败。
在行为合理的数据中心环境中，大部分时间都会满足时序假设——这被称为部分同步系统 [12]。但这足够了吗？一旦这些时间假设被打破，Redlock 可能会违反其安全属性，例如在另一个客户端到期之前向一个客户端授予租约。如果你依赖你的锁来保证正确性，“大部分时间”是不够的——你需要它总是正确的。
有大量证据表明，为大多数实际系统环境假设同步系统模型是不安全的 [7,8]。不断提醒自己 GitHub 事件的90 秒数据包延迟。 Redlock 不太可能在Jepsen测试中幸存下来。
另一方面，为部分同步系统模型（或带有故障检测器的异步模型）设计的共识算法是时候上场了。 Raft、Viewstamped Replication、Zab 和 Paxos 都属于这一类。这样的算法必须放弃所有时序假设。这很难：假设网络、进程和时钟比实际情况更可靠是很诱人的。但是在分布式系统的混乱现实中，你必须非常小心你的假设。
7. 结论
我认为 Redlock 算法是一个糟糕的选择：对于效率优化来说实现太复杂、成本昂贵的，对于想保证正确性的场景来说它又不够安全。
特别是，该算法对时序和系统时钟做出了危险的假设（基本上假设同步系统具有有限的网络延迟和有限的操作执行时间），如果不满足这些假设，则会违反安全属性。此外，它缺乏用于生成隔离令牌的设施（保护系统免受网络长时间延迟或暂停进程的影响）。
如果使用锁是出于效率优化的目的且可以容忍一定程度的不正确性，我建议坚持使用简单的 Redis单节点锁定算法（条件设置如果不存在以获得锁， atomic delete-if-value-matches 以释放锁），并在您的代码中非常清楚地记录锁只是近似值，有时可能会失败。不要费心设置五个 Redis 节点的集群。
另一方面，如果您需要锁定以确保正确性，请不要使用 Redlock。相反，请使用适当的共识系统，例如 ZooKeeper，可能通过实现锁定的 Curator recipes之一。 （至少，使用具有合理事务保证的数据库。）并且请在锁定下的所有资源访问中强制使用防护令牌。
正如我在开头所说的，如果正确使用Redis，它是一个很好的工具。以上都不会降低 Redis 对其预期用途的实用性。 Salvatore 多年来一直致力于该项目，其成功当之无愧。但是每个工具都有局限性，了解它们并相应地进行计划很重要。
如果您想了解更多信息，我在本书的第8章和第9章中更详细地解释了这个主题，现在可以从 O’Reilly 获得早期版本。 （上图摘自我的书。）为了学习如何使用 ZooKeeper，我推荐Junqueira和Reed的书 [3]。为了更好地介绍分布式系统理论，我推荐Cachin、Guerraoui 和 Rodrigues的教科书 [13]。
感谢 Kyle Kingsbury, Camille Fournier, Flavio Junqueira, 和 Salvatore Sanfilippo 审阅本文的草稿。当然，任何错误都是我的。
2016 年 2 月 9 日更新：Redlock 的原作者 Salvatore 对本文进行了反驳（另见HN讨论）。他提出了一些很好的观点，但我坚持我的结论。如果我有时间，我可能会在后续文章中详细说明，但请形成您自己的意见——并请参阅下面的参考资料，其中许多已经接受了严格的学术同行评审（与我们的任何一篇博文不同）。
References
[1] Cary G Gray and David R Cheriton: “Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency,” at 12th ACM Symposium on Operating Systems Principles (SOSP), December 1989. doi:10.1145/74850.74870
[2] Mike Burrows: “The Chubby lock service for loosely-coupled distributed systems,” at 7th USENIX Symposium on Operating System Design and Implementation (OSDI), November 2006.
[3] Flavio P Junqueira and Benjamin Reed: ZooKeeper: Distributed Process Coordination. O’Reilly Media, November 2013. ISBN: 978-1-4493-6130-3
[4] Enis Söztutar: “HBase and HDFS: Understanding filesystem usage in HBase,” at HBaseCon, June 2013.
[5] Todd Lipcon: “Avoiding Full GCs in Apache HBase with MemStore-Local Allocation Buffers: Part 1,” blog.cloudera.com, 24 February 2011.
[6] Martin Thompson: “Java Garbage Collection Distilled,” mechanical-sympathy.blogspot.co.uk, 16 July 2013.
[7] Peter Bailis and Kyle Kingsbury: “The Network is Reliable,” ACM Queue, volume 12, number 7, July 2014. doi:10.1145/2639988.2639988
[8] Mark Imbriaco: “Downtime last Saturday,” github.com, 26 December 2012.
[9] Tushar Deepak Chandra and Sam Toueg: “Unreliable Failure Detectors for Reliable Distributed Systems,” Journal of the ACM, volume 43, number 2, pages 225–267, March 1996. doi:10.1145/226643.226647
[10] Michael J Fischer, Nancy Lynch, and Michael S Paterson: “Impossibility of Distributed Consensus with One Faulty Process,” Journal of the ACM, volume 32, number 2, pages 374–382, April 1985. doi:10.1145/3149.214121
[11] Maurice P Herlihy: “Wait-Free Synchronization,” ACM Transactions on Programming Languages and Systems, volume 13, number 1, pages 124–149, January 1991. doi:10.1145/114005.102808
[12] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer: “Consensus in the Presence of Partial Synchrony,” Journal of the ACM, volume 35, number 2, pages 288–323, April 1988. doi:10.1145/42282.42283
[13] Christian Cachin, Rachid Guerraoui, and Luís Rodrigues: Introduction to Reliable and Secure Distributed Programming, Second Edition. Springer, February 2011. ISBN: 978-3-642-15259-7, doi:10.1007/978-3-642-15260-3
