Redis的分布式锁-翻译：Distributed locks with Redis – Redis

分布式锁在许多环境中是一种非常有用的原素，不同的进程必须以相互排斥的方式操作共享资源。

有许多库和博文描述了如何用Redis实现DLM（分布式锁管理器），但每个库都使用了不同的方法，而且许多库使用的是简单的方法，与稍微复杂的设计所能达到的效果相比，保障较低。

本页试图提供一种更规范的算法来实现Redis的分布式锁。我们提出了一种算法，叫做Redlock，它实现了一个DLM，我们认为它比虚构的单实例方法更安全。我们希望社区能够对其进行分析，提供反馈，并将其作为实现或更复杂或替代设计的起点。

在描述该算法之前，这里有几个已经有的实现的链接，可以用来参考。

我们将用三个属性来模拟我们的设计，从我们的角度来看，这三个属性是以有效方式使用分布式锁所需的最低限度的保证。

为了了解我们想要改进的地方，让我们分析一下大多数基于Redis的分布式锁库的现状。

使用Redis锁定资源的最简单方法是在一个实例中创建一个密钥。这个键通常是在有限的时间内创建的，使用Redis的过期功能，所以最终它将被释放（我们列表中的属性2）。当客户端需要释放资源时，它就会删除该密钥。

表面上看这很好，但有一个问题：这是我们架构中的一个单一故障点。如果Redis的主节点坏了会怎样？好吧，让我们添加一个从节点吧! 并在主节点不可用的情况下使用它。不幸的是，这是不可行的。因为Redis复制是异步的，这样做我们就不能实现互斥的安全属性。

这种模式有一个明显的竞赛条件。

有时候，在特殊情况下，比如在故障期间，多个客户端可以同时持有锁，这是完全可以的。如果是这种情况，你可以使用你的基于复制的解决方案。否则，我们建议实施本文档中描述的解决方案。

在尝试克服上述单实例设置的限制之前，让我们检查一下如何在这个简单的情况下正确地实现它，因为这实际上是一个可行的解决方案，在应用中不时出现的竞赛条件是可以接受的，而且因为锁定到一个单实例是我们将用于这里描述的分布式算法的基础。

要获得锁，方法是这样的。

该命令只在密钥不存在的情况下设置（NX选项），过期时间为30000毫秒（PX选项）。密钥被设置为一个值 "myrandomvalue"。这个值在所有客户端和所有锁请求中必须是唯一的。

基本上，随机值是为了以安全的方式释放锁，用一个脚本告诉Redis：只有当它存在并且存储在键上的值正是我期望的值时，才会删除该键。这是由以下Lua脚本完成的。

这一点很重要，以避免删除由其他客户创建的锁。例如，一个客户可能获得了锁，在某些操作中被阻塞，时间超过了锁的有效期（钥匙将过期的时间），后来删除了已经被其他客户获得的锁。仅仅使用DEL是不安全的，因为一个客户可能会删除另一个客户的锁。在上面的脚本中，每个锁都有一个随机字符串的 "签名"，所以只有当它仍然是由试图删除它的客户端设置的锁时才会被删除。

这个随机字符串应该是什么？我假设它是来自/dev/urandom的20个字节，但你可以找到更便宜的方法来使它对你的任务来说足够独特。例如，一个安全的选择是用/dev/urandom作为RC4的种子，并从中生成一个伪随机流。一个更简单的解决方案是使用具有微秒分辨率的unix时间的组合，将其与客户的ID连接起来，它不那么安全，但在大多数环境中可能可以完成任务。

我们用来作为关键时间的时间，被称为 "锁的有效性时间"。它既是自动释放时间，也是客户端在另一个客户端能够再次获得锁之前执行所需操作的时间，在技术上不违反互斥保证，它只限于从获得锁的那一刻起的特定时间窗口。

所以现在我们有了一个获取和释放锁的好方法。这个系统，对一个由单一的、总是可用的实例组成的非分布式系统进行推理，是安全的。让我们把这个概念扩展到一个分布式系统，在那里我们没有这样的保证。

在该算法的分布式版本中，我们假设我们有N个Redis主站。这些节点是完全独立的，所以我们不使用复制或任何其他隐含的协调系统。我们已经描述了如何在单个实例中安全地获取和释放锁。我们想当然地认为，算法将使用这种方法来获取和释放单实例中的锁。在我们的例子中，我们设置了N=5，这是一个合理的值，所以我们需要在不同的计算机或虚拟机上运行5个Redis主站，以确保它们会以一种基本独立的方式失败。

为了获得锁，客户端执行以下操作。

该算法依赖于这样的假设：虽然没有跨进程的同步时钟，但每个进程的本地时间仍以近似相同的速度流动，其误差与锁的自动释放时间相比很小。这个假设与现实世界的计算机非常相似：每台计算机都有一个本地时钟，我们通常可以依靠不同的计算机有一个很小的时钟漂移。

在这一点上，我们需要更好地说明我们的互斥规则：只要持有锁的客户端将在锁的有效期内（如在步骤3中得到的），减去一些时间（为了补偿进程间的时钟漂移，只需几毫秒）终止其工作，就可以保证。

关于需要约束时钟漂移的类似系统的更多信息，这篇论文是一个有趣的参考。租约： 分布式文件缓存一致性的高效容错机制 http://dl.acm.org/citation.cfm?id=74870。

当客户端无法获取锁时，它应该在随机延迟后再次尝试，以尝试对试图在同一时间为同一资源获取锁的多个客户端进行异步处理（这可能会导致大脑分裂的情况，没有人获胜）。另外，客户端试图在大多数Redis实例中获取锁的速度越快，出现大脑分裂状况的窗口就越小（需要重试），所以理想情况下，客户端应该尝试使用复用技术同时向N个实例发送SET命令。

值得强调的是，对于未能获得大部分锁的客户端来说，尽快释放（部分）获得的锁是非常重要的，这样就不需要等待密钥过期，以便再次获得锁（然而，如果发生网络分区，客户端不再能够与Redis实例进行通信，在等待密钥过期时，需要支付可用性罚款）。

释放锁很简单，只需要在所有实例中释放锁，无论客户是否认为它能够成功锁定一个特定的实例。

该算法是否安全？我们可以试着了解在不同的情况下会发生什么。

首先，我们假设一个客户能够在大多数实例中获得锁。所有的实例将包含一个具有相同生存时间的密钥。然而，钥匙的设置时间不同，所以钥匙也会在不同的时间过期。但是，如果第一个密钥在最坏的情况下被设置在时间T1（我们在联系第一个服务器之前的采样时间），而最后一个密钥在最坏的情况下被设置在时间T2（我们从最后一个服务器获得回复的时间），我们可以肯定，集合中第一个过期的密钥将至少存在MIN_VALIDITY=TTL-（T2-T1）-CLOCK_DRIFT。所有其他的钥匙将在以后过期，所以我们确信钥匙将同时设置至少这个时间。

在大多数钥匙被设置的时间里，另一个客户端将无法获得锁，因为如果N/2+1个钥匙已经存在，N/2+1个SET NX操作就不能成功。因此，如果一个锁被获取了，就不可能在同一时间重新获取它（违反了互斥属性）。

然而我们也要确保多个试图同时获取锁的客户端不能同时成功。

如果一个客户端使用接近或大于锁的最大有效时间（基本上是我们用于SET的TTL）锁定了大多数实例，它将认为该锁无效并将解锁这些实例，所以我们只需要考虑一个客户端能够在小于有效时间的时间内锁定大多数实例的情况。在这种情况下，对于上面已经表达的论点，对于MIN_VALIDITY来说，没有客户端应该能够重新获得锁。所以多个客户端将能够同时锁定N/2+1个实例（"时间 "是指步骤2的结束时间），只有当锁定大多数的时间大于TTL时间时，才能使锁无效。

你是否能够提供一个正式的安全证明，指出现有的类似算法，或者找到一个错误？这将是非常感谢的。

系统的有效性是基于三个主要特征。

然而，我们支付的可用性惩罚等于网络分区的TTL时间，所以如果有连续的分区，我们可以无限期地支付这个惩罚。每当一个客户获得一个锁，并在能够移除该锁之前被分区时，就会发生这种情况。

基本上，如果有无限的连续网络分区，系统可能在无限长的时间

许多使用Redis作为锁服务器的用户需要高性能，包括获取和释放锁的延迟，以及每秒可能进行的获取/释放操作的数量。为了满足这一要求，与N个Redis服务器对话以减少延迟的策略肯定是多路复用（或穷人的多路复用，即把套接字置于非阻塞模式，发送所有的命令，随后读取所有的命令，假设客户端和每个实例之间的RTT相似）。

然而，如果我们想以崩溃恢复系统模型为目标，还有另一个关于持久性的考虑要做。

基本上要看到这里的问题，让我们假设我们配置的Redis完全没有持久性。一个客户端在5个实例中的3个获得了锁。客户端能够获得锁的其中一个实例被重新启动，此时又有3个实例可以为同一资源加锁，另一个客户端可以再次加锁，违反了锁的排他性的安全属性。

如果我们启用AOF持久性，情况会有很大的改善。例如，我们可以通过发送SHUTDOWN和重启来升级服务器。因为Redis的过期时间在语义上是这样实现的：当服务器关闭时，实际上时间仍然在流逝，我们所有的要求都很好。然而，只要是干净的关机，一切都很好。那停电呢？如果Redis被配置为默认的每秒在磁盘上进行fsync，那么在重新启动后，我们的密钥有可能丢失。理论上，如果我们想在任何形式的实例重启时保证锁的安全，我们需要在持久性设置中启用fsync=always。这反过来又会完全破坏性能，使之与传统上用于安全实现分布式锁的CP系统的水平相同。

然而，事情要比乍看之下要好得多。基本上，只要当一个实例在崩溃后重新启动时，它不再参与任何当前活动的锁，那么算法的安全性就会被保留下来，因此，当实例重新启动时，当前活动的锁集合都是由锁的实例获得的，而不是正在重新加入系统的那个。

为了保证这一点，我们只需要让一个实例在崩溃后，至少比我们使用的最大TTL多一点的时间不可用，也就是实例崩溃时存在的所有锁的钥匙变得无效并被自动释放所需的时间。

使用延迟重启基本上可以实现安全，即使没有任何类型的Redis持久性可用，但请注意，这可能转化为可用性惩罚。例如，如果大多数实例崩溃，系统将成为全球不可用的TTL（这里的全球意味着在这段时间内没有任何资源可以被锁定）。

如果客户端执行的工作是由小步骤组成的，就有可能在默认情况下使用较小的锁有效期，并通过实施锁扩展机制来扩展该算法。基本上，客户端，如果在计算中间，而锁的有效性接近一个低值，可以通过向所有的实例发送一个Lua脚本来扩展锁，如果钥匙存在并且其值仍然是客户端在获得锁时分配的随机值，则扩展锁。

客户端只有在能够将锁扩展到大多数实例，并且在有效期内（基本上使用的算法与获取锁时使用的算法非常相似），才应该考虑重新获得锁。

然而，这在技术上并没有改变算法，所以应该限制重新获取锁的最大次数，否则就违反了有效性属性之一。

想帮忙吗？ 如果你对分布式系统感兴趣的话，希望能得到你的意见/分析。另外，参考其他语言的实现也很好。

谢谢。

对Redlock的分析 Martin Kleppmann在这里分析了Redlock。我不同意这个分析，并在这里发表了我对他的分析的答复。