译文-How to do distributed locking — Martin Kleppmann’s blog

作者：Martin Kleppmann 发布于2016年2月8日。

作为我的书的研究工作的一部分，我在Redis网站上看到了一种叫做Redlock的算法。该算法声称要在Redis之上实现容错的分布式锁（或者说是租约[1]），该页面要求从事分布式系统的人提供反馈。这个算法本能地在我脑海中敲响了一些警钟，所以我花了一点时间来思考它，并写下了这些笔记。

由于已经有超过10个Redlock的独立实现，而且我们不知道谁已经在依赖这个算法，我认为这值得公开分享我的笔记。我不会去讨论Redis的其他方面，其中一些已经在其他地方被批评过了。

在我讨论Redlock的细节之前，让我说，我相当喜欢Redis，而且我过去已经成功地在生产中使用它。我认为它很适合于这样的情况：你想在服务器之间共享一些瞬时的、近似的、快速变化的数据，而且如果你偶尔因为某种原因丢失这些数据也不是什么大问题。例如，一个好的用例是维护每个IP地址的请求计数器（用于速率限制目的）和每个用户ID的不同IP地址集（用于滥用检测）。

然而，Redis已经逐渐进入数据管理领域，这些领域有更强的一致性和持久性期望--这让我很担心，因为这并不是Redis的设计目的。可以说，分布式锁就是这些领域之一。让我们更详细地研究它。

你用这个锁做什么？

锁的目的是确保在几个可能试图做同样工作的节点中，只有一个真正做了（至少一次只有一个）。这项工作可能是将一些数据写入共享存储系统，进行一些计算，调用一些外部API，或类似的。在高层次上，有两个原因可以让你在一个分布式应用中想要一个锁：为了效率或正确性[2]。为了区分这两种情况，你可以问如果锁失败了会发生什么。

• 效率。加锁可以避免不必要地将同样的工作做两次（例如一些昂贵的计算）。如果锁失败了，两个节点最终做了同样的工作，其结果是成本略有增加（你最终向AWS多支付了5美分的费用）或略有不便（例如，一个用户最终收到了两次相同的电子邮件通知）。
• 正确性。加锁可以防止并发进程互相影响，扰乱系统状态。如果锁失败了，两个节点同时处理同一份数据，结果就是文件损坏、数据丢失、持久化不一致、给病人注射的药物剂量错误，或其他严重问题。

这两种情况都是想要锁的有效情况，但你需要非常清楚你所处理的是这两种情况中的哪一种。

我认为，如果你只是为了提高效率而使用锁，那么就没有必要承担Redlock的成本和复杂性，运行5个Redis服务器，并检查是否有多数人获得你的锁。你最好只使用一个Redis实例，也许在主实例崩溃的情况下，用异步复制到一个辅助实例。

如果你使用一个Redis实例，当然，如果你的Redis节点突然断电，或者出现其他问题，你会丢掉一些锁。但如果你只是把锁作为一种效率优化，而且崩溃不会经常发生，那就没什么大不了的。这种 "没什么大不了 "的情况正是Redis的闪光之处。至少，如果你依赖一个Redis实例，那么每个看系统的人都清楚，锁是近似的，而且只用于非关键的目的。

另一方面，Redlock算法，有5个副本和多数投票，乍一看好像适合于你的锁对正确性很重要的情况。我将在下面的章节中论证它不适合这一目的。在本文的其余部分，我们将假设你的锁对正确性很重要，如果两个不同的节点同时认为他们持有相同的锁，那是一个严重的错误。

用锁来保护一个资源

让我们先把Redlock的细节放在一边，讨论一下分布式锁在一般情况下是如何使用的（与使用的特定锁算法无关）。重要的是要记住，分布式系统中的锁并不像多线程应用程序中的mutex。它是一个更复杂的野兽，因为不同的节点和网络都可以以各种方式独立故障。

例如，假设你有一个应用程序，其中一个客户端需要更新共享存储（如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();
    }
}

不幸的是，即使你有一个完美的锁服务，上面的代码也是有问题的。下图显示了你如何以损坏的数据而告终。

unsafe-lock.png

在这个例子中，获得锁的客户端在持有锁的时候暂停了很长一段时间--例如因为垃圾收集器（GC）启动了。该锁有一个超时时间（即它是一个租约），这总是一个好主意（否则一个崩溃的客户端可能最终永远持有一个锁，并且永远不会释放它）。然而，如果GC暂停的时间超过了租约的有效期，而客户端没有意识到它已经过期了，它可能会去做一些不安全的改变。

这个bug并不是理论上的：HBase曾经也有这个问题[3,4]。通常情况下，GC暂停的时间很短，但 "停止世界 "的GC暂停有时会持续几分钟[5]--当然足够长的时间让租约过期。即使像HotSpot JVM的CMS这样所谓的 "并发 "垃圾收集器也不能完全与应用程序代码并行运行--甚至它们也需要不时地停止世界[6]。

你不能通过在写回存储区之前插入一个对锁到期的检查来解决这个问题。请记住，GC可以在任何时候暂停一个正在运行的线程，包括对你来说最不方便的那一点（在最后一次检查和写操作之间）。

如果你因为你的编程语言运行时没有长的GC暂停而感到自鸣得意，还有许多其他原因导致你的进程可能被暂停。也许你的进程试图读取一个尚未加载到内存中的地址，所以它得到了一个页面故障并被暂停，直到该页面从磁盘中加载。也许你的磁盘实际上是EBS，所以读取一个变量在不知不觉中变成了亚马逊拥挤网络上的同步网络请求。也许有很多其他进程在争夺CPU，而你在调度器树上碰到了一个黑节点。也许有人不小心向进程发送了SIGSTOP。不管怎么样。你的进程会被暂停。

如果你还是不相信我说的进程暂停，那么可以考虑一下，文件写入请求在到达存储服务之前可能会在网络中被延迟。以太网和IP等分组网络可能会任意延迟数据包，而且确实如此[7]：在GitHub的一个著名事件中，数据包在网络中被延迟了大约90秒[8]。这意味着，一个应用程序可能会发送一个写请求，它可能在一分钟后到达存储服务器，而此时租约已经过期。

即使在管理良好的网络中，这种事情也可能发生。你根本不能对时间做出任何假设，这就是为什么上面的代码从根本上是不安全的，无论你使用什么锁服务。

用防护令牌

解决这个问题的方法其实很简单：你需要在每次向存储服务的写请求中包含一个防护令牌。在这种情况下，令牌只是一个数字，每次客户端获得锁时，这个数字就会增加（例如，由锁服务增加）。这在下图中有所说明。

fencing-tokens.png

客户端1获得了租约，并得到了一个33的令牌，但随后就进入了一个漫长的暂停期，租约过期。客户端2获得了租约，得到了一个34的令牌（数字总是增加的），然后把它的写发送到存储服务，包括34的令牌。后来，客户端1复活了，并把它的写发送到存储服务，包括它的令牌值33。然而，存储服务器记得它已经处理了一个具有更高的令牌号（34）的写入，所以它拒绝了带有令牌33的请求。

请注意，这需要存储服务器在检查令牌方面发挥积极作用，并拒绝任何令牌已经倒退的写入。但这并不难，只要你知道这个技巧。只要锁服务能产生严格的单调增长的令牌，这就能使锁安全。例如，如果你使用ZooKeeper作为锁服务，你可以使用zxid或znode版本号作为围栏令牌，你的情况就很好[3]。

然而，这让我们看到了Redlock的第一个大问题：它没有任何生成防护令牌的设施。该算法没有产生任何数字，保证每次客户端获得锁时都会增加。这意味着即使该算法在其他方面很完美，使用起来也不安全，因为你无法防止在一个客户端暂停或其数据包被延迟的情况下，客户端之间出现竞争条件。

对我来说，如何改变Redlock算法以开始生成防护令牌并不明显。它使用的唯一随机值并不能提供所需的单调性。仅仅在一个Redis节点上保留一个计数器是不够的，因为该节点可能会失败。在几个节点上保留计数器将意味着它们会失去同步性。你很可能需要一个共识算法来生成防护令牌。如果计数器的增量是简单的就好了）。

用时间来解决共识

Redlock无法生成防护令牌的事实，应该已经足以说明在正确性取决于锁的情况下不要使用它。但还有一些问题值得讨论。

在学术文献中，这种算法最实用的系统模型是具有不可靠的故障检测器的异步模型[9]。通俗地说，这意味着算法不对时间进行假设：进程可能会暂停任意长度的时间，数据包可能会在网络中任意延迟，时钟可能会任意出错--尽管如此，算法还是被期望做正确的事情。鉴于我们上面讨论的内容，这些都是非常合理的假设。

算法可能使用时钟的唯一目的是产生超时，以避免在一个节点停机时永远等待。但是超时不一定准确：仅仅因为一个请求超时了，并不意味着另一个节点肯定宕机了--它也可能是网络中有一个很大的延迟，或者你的本地时钟是错误的。当被用作故障检测器时，超时只是一种猜测，即有什么东西出了问题。如果可以的话，分布式算法可以完全不使用时钟，但那样的话就不可能达成共识了[10]。获取一个锁就像一个比较和设置的操作，这需要共识[11]）。)

请注意，Redis使用gettimeofday，而不是单调的时钟，来确定钥匙的到期时间。gettimeofday的手册中明确指出，它返回的时间会受到系统时间的不连续跳动的影响--也就是说，它可能会突然向前跳动几分钟，甚至是向后跳动（例如，如果时钟因为与NTP服务器相差太多而被NTP踩到，或者时钟被管理员手动调整）。因此，如果系统时钟在做奇怪的事情，很容易发生Redis中的密钥到期比预期的快得多或慢得多的情况。

对于异步模型中的算法来说，这不是一个大问题：这些算法通常确保它们的安全属性总是成立的，而不需要做任何时间假设[12]。只有活泼性属性依赖于超时或其他一些故障检测器。通俗地说，这意味着即使系统中的时序到处都是（进程暂停、网络延迟、时钟前后跳动），算法的性能可能会陷入困境，但算法绝不会做出错误的决定。

然而，Redlock不是这样的。它的安全性取决于很多时间上的假设：它假设所有Redis节点在过期前持有钥匙的时间长度大致正确；网络延迟与过期时间相比很小；进程暂停比过期时间短很多。

用坏的定时器打破Redlock

让我们看一些例子来证明Redlock对时间假设的依赖。假设系统有五个Redis节点（A、B、C、D和E），以及两个客户端（1和2）。如果其中一个Redis节点上的时钟向前跳动，会发生什么？

1. 客户端1获得了A、B、C节点上的锁，由于网络问题，无法到达D和E。
2. 节点C上的时钟向前跳动，导致锁过期。
3. 客户端2获得了节点C、D、E的锁，由于网络问题，A和B不能被联系到。
4. 客户端1和2现在都认为他们持有锁。

如果C在将锁持久化到磁盘之前崩溃，并立即重新启动，也会发生类似的问题。出于这个原因，Redlock文档建议延迟重启崩溃的节点，至少延迟最长寿命的锁的生存时间。但这个重启延迟又依赖于对时间的合理准确测量，如果时钟跳动，就会失败。

好吧，也许你认为时钟跳动是不现实的，因为你对正确配置NTP使其只进行时钟回转非常有信心。在这种情况下，让我们看一个例子，说明进程暂停可能导致算法失败。

1. 客户端1请求锁定节点A、B、C、D、E。
2. 当对客户端1的响应在路途中时，客户端1进入停止世界的GC。
3. 所有Redis节点的锁都过期了。
4. 客户端2获得了节点A、B、C、D、E的锁。
5. 客户端1完成了GC，并收到了来自Redis节点的响应，表明它成功获得了锁（当进程暂停时，它们被保存在客户端1的内核网络缓冲区）。
6. 客户端1和2现在都认为他们持有该锁。

请注意，尽管Redis是用C语言编写的，因此没有GC，但这对我们没有帮助：任何客户端可能经历GC暂停的系统都有这个问题。你只能通过防止客户端1在客户端2获得锁后在锁下进行任何操作来使其安全，例如使用上面的围栏方法。

长时间的网络延迟会产生与进程暂停相同的效果。这也许取决于你的TCP用户超时--如果你让超时大大短于Redis的TTL，也许延迟的网络数据包会被忽略，但我们必须详细查看TCP实现才能确定。另外，有了超时，我们又回到了时间测量的准确性上。

Redlock的同步性假设

这些例子表明，只有当你假设一个同步系统模型时，Redlock才能正确工作，也就是说，一个具有以下特性的系统。

• 有界的网络延迟（你可以保证数据包总是在某个保证的最大延迟内到达）。
• 有界的进程暂停（换句话说，硬实时约束，你通常只在汽车安全气囊系统和类似的系统中发现），和
• 有界的时钟误差（祈祷你不会从一个糟糕的NTP服务器上得到你的时间）。

请注意，同步模型并不意味着时钟完全同步：它意味着你假设网络延迟、停顿和时钟漂移有一个已知的、固定的上限[12] 。Redlock假设延迟、停顿和漂移相对于锁的存活时间都很小；如果时间问题变得和存活时间一样大，算法就会失败。

在一个合理的行为良好的数据中心环境中，大部分时间都会满足时间假设--这被称为部分同步系统[12]。但这够好吗？一旦这些时序假设被打破，Redlock就可能违反其安全属性，例如在另一个客户端过期之前将租约授予一个客户端。如果你依赖于你的锁的正确性，"大部分时间 "是不够的，你需要它总是正确的。

有很多证据表明，对于大多数实际的系统环境来说，假设一个同步的系统模型是不安全的[7,8]。不断提醒自己GitHub事件中90秒的数据包延迟。Redlock不太可能经受住Jepsen测试。

另一方面，为部分同步系统模型（或带有故障检测器的异步模型）设计的共识算法实际上有机会工作。Raft、Viewstamped Replication、Zab和Paxos都属于这个类别。这样的算法必须放开所有的时间假设。这很难：假设网络、进程和时钟比实际情况更可靠是非常诱人的。但在分布式系统的混乱现实中，你必须对你的假设非常小心。

结论

我认为Redlock算法是一个糟糕的选择，因为它是 "非驴非马"：对于效率优化的锁来说，它是不必要的重量级和昂贵的，但对于正确性取决于锁的情况来说，它是不够安全。

特别是，该算法对时间和系统时钟做了危险的假设（基本上是假设一个同步系统，其网络延迟和操作的执行时间是有限制的），如果这些假设没有得到满足，它就会违反安全属性。此外，它还缺少一个生成防护令牌的工具（保护系统免受网络或暂停进程中的长时间延迟）。

如果你只是在尽力的基础上需要锁（作为一种效率优化，而不是为了正确性），我建议坚持使用Redis的简单的单节点锁算法（条件性的set-if-not-exists来获得锁，原子性的delete-if-value-matches来释放锁），并在你的代码中非常清楚地说明锁只是近似的，偶尔会失败。不要费心去建立一个有五个Redis节点的集群。

另一方面，如果你需要锁的正确性，请不要使用Redlock。相反，请使用适当的共识系统，如ZooKeeper，可能是通过实现锁的Curator配方之一。(至少，请使用具有合理交易保证的数据库。)并请在锁下的所有资源访问中强制使用围栏令牌。

正如我在一开始所说的，如果你正确地使用它，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讨论）。他提出了一些好的观点，但我坚持我的结论。如果我有时间，我可能会在后续文章中详细说明，但请形成你自己的观点--请参考下面的参考资料，其中许多资料都接受了严格的学术同行评审（与我们任何一篇博文不同）。

参考文献

[1] Cary G Gray和David R Cheriton: "租赁。分布式文件缓存一致性的高效容错机制"，在第12届ACM操作系统原理研讨会（SOSP）上，1989年12月。 DOI：10.1145/74850.74870

[2] Mike Burrows: "用于松散耦合分布式系统的Chubby锁服务"，在第七届USENIX操作系统设计与实现研讨会（OSDI）上，2006年11月。

[3] Flavio P Junqueira和Benjamin Reed: ZooKeeper: 分布式进程协调。O'Reilly Media, November 2013. ISBN: 978-1-4493-6130-3

[4] Enis Söztutar: "HBase和HDFS：理解HBase中的文件系统使用"，在HBaseCon上，2013年6月。

[5] Todd Lipcon: "用MemStore-本地分配缓冲区避免Apache HBase中的完全GCs。第一部分，"blog.cloudera.com，2011年2月24日。

[6] Martin Thompson："Java垃圾收集的简化"，mechanical-sympathy.blogspot.co.uk，2013年7月16日。

[7] Peter Bailis 和 Kyle Kingsbury: "网络是可靠的"，ACM Queue，第12卷第7号，2014年7月。DOI:10.1145/2639988.2639988

[8] Mark Imbriaco: "Downtime last Saturday," github.com, 26 December 2012.

[9] Tushar Deepak Chandra和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: "有一个错误过程的分布式共识的不可能性"，《ACM杂志》，第32卷，第2号，第374-382页，1985年4月。 DOI：10.1145/3149.214121

[11] Maurice P Herlihy: "Wait-Free Synchronization"，ACM Transactions on Programming Languages and Systems，第13卷，第1号，第124-149页，1991年1月。 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: 可靠和安全分布式编程介绍，第二版。Springer, 2011年2月。ISBN: 978-3-642-15259-7, doi:10.1007/978-642-15260-3