分布式锁是一个非常有用的原语，在需要不同进程间互斥操作共享资源时使用。
有很多的开发库和博客描述如何使用Redis实现DLM（Distributed Lock Manager，分布式锁管理），每个开发库使用不同的方式，有的设计与实现相对复杂一些，有的简单低可靠。
本文尝试提供更标准的算法来使用Redis实现分布式锁。我们提出一种叫做 Redlock 的算法，我们认为它能够实现比vanilla单例方式更安全的DLM。我们希望社区分析它并提供反馈，以做为更加复杂或替代设计的一个实现。

实现

在说具体算法之前，下面有一些可供参考的具体实现.

安全和活跃性保证

从保证实现有效分布式锁的最小粒度来说，我们设计的模型只有三个属性：

  1. 属性安全：相互排斥。在任何特定的时刻，只有一个客户端可以持有锁。
  2. 活跃属性A：无死锁。即使一个客户端已经获得一个损坏或部分资源的锁，它依然可以请求其他锁。
  3. 活跃属性B：容错。只要大部分 Redis 节点可用，客户端就可以获得和释放锁。

为什么基于容错实现还不够

要理解我们想要进行的改进，就让我们先来分析下当前基于 Redis 的分布式锁的实现方式。
使用Redis锁住资源的最简单的方法就是在一个实例中创建一个key。利用 Redis 的超时机制，创建key 时设置生存期，以便它最终会被释放（实现属性2）。而当客户端想要释放时，直接删除key就行了。
一般来说，这样就行，但有个问题：这是我们架构中的一个失败点。如果 Redis 主节点挂了呢？当然，我们可以加个子节点，主节点出问题时可以切换过来。不过很可惜，这种方案不可行。因为 Redis 的主-从复制是异步的，我们无法用其实现互斥的安全特性。
这明显是该模型的一种竞态条件：

  1. 客户端A在主节点获得了一个锁。
  2. 在从节点上写同步完成前，主节点挂了。
  3. 从节点被提升为主节点。
  4. 客户端B获得和A相同的锁。注意，锁安全性被破坏了！

在某些情况下这反而工作得很好，例如在出错时，多个客户端可以获得同一个锁。如果这正好是你想要的，那就可以使用主-从复制的方案。否则，我们建议使用这篇文章中描述的方法。

单实例的正确实现方案

在尝试解决上文描述的单实例方案的缺陷之前，先让我们确保针对这种简单的情况，怎么做才是无误的，因为这种方案对某些程序而言也是可以接受的，而且这也是我们即将描述的分布式方案的基础。
为了获取锁，方法是这样的：

SET resource_name my_random_value NX PX 30000

仅当其不存在时生效（NX选项），这条指令将设置key的值， 且设置其生存期为30000毫秒（PX选项）。key对应的value值是自己设置的随机值。这个值在所有客户端和所有加锁请求中是必须是唯一的。
使用随机值主要是为了能够安全地释放锁，通过脚本通知 Redis：当且仅当key存在并且是我们所期待时，可以删除key。看看以下lua代码：

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

这么做很重要，可以避免误删其他客户端创建的锁。例如某个客户端获得了一个锁，但它的处理时长超过了锁的有效时长（key的过期时间），之后它删除了这个锁，而此时这个锁可能又被其他客户端给获得了。仅仅做删除是不够安全的，很可能会把其他客户端的锁给删了。结合上面的代码，每个锁都有个唯一的随机值，因此仅当这个值依旧是客户端所设置的值时，才会去删除它。

那么应该怎样生成这个随机值呢？我们使用的是从 /dev/urandom 读取的20个字节，但你也可以使用满足你任务的其他更简单有效的方法。例如，可以使用 /dev/urandom 初始化 RC4 算法，然后用其产生随机数流。更简单的方法是使用unix时间戳和客户端ID组成的串, 但这并不安全，但对很多环境而言也够用了。

我们所说的key的有效时间，即“锁的有效时长”。 它代表两种情况，一种是指锁的自动释放时长，另一种是指在另一个客户端获取锁之前某个客户端占用这个锁的时长，这被限制在从锁获取后开始的一段时间窗口内。

现在我们已经有好的办法获取和释放锁了。在单实例非分布式系统中，只要保证节点没挂掉，这个方法就是安全的。那么让我们把这个概念扩展到分布式的系统中吧，那里可没有这种保证。

Redlock 算法

在此算法的分布式版本中，我们假设有N个 Redis 主节点。这些节点是相互独立的，因此我们不使用复制或其他隐式同步机制。我们已经描述过在单实例情况下如何安全地获取锁。我们也指出此算法将使用这种方法从单实例获取和释放锁。在以下示例中，我们设置N=5（这是个比较适中的值），这样我们需要在不同物理机或虚拟机上运行5个Redis主节点，以确保它们的出错是尽可能独立的。

为了获取锁，客户端执行以下操作：

  1. 获取当前时间，以毫秒为单位。
  2. 以串行的方式尝试从所有的N个实例中获取锁，在所有实例中使用的是相同的key和随机value值。在第二步中，在每个实例获取锁时，客户端会设置一个连接超时，其时长相比锁的自动释放时间要短得多。例如，如果锁的自动释放时间是10秒，那么连接超时大概设在5到50毫秒之间。这可以避免当Redis节点挂掉时，会长时间堵住客户端：如果某个节点没及时响应，就应该尽快转到下个节点。
  3. 客户端计算获取所有锁耗费的时长，方法是使用当前时间减去步骤1中的时间。当且仅当客户端能从多数节点（至少3个）中获得锁，并且耗费的时长小于锁的有效期时，可认为锁已经获得了。
  4. 如果锁获得了，它的最终有效时长将重新计算为其原时长减去步骤3中获取锁耗费的时长。
  5. 如果锁获取失败了（要么是没有锁住N/2+1个节点，要么是锁的最终有效时长为负数），客户端会对所有实例进行解锁操作（即使对那些没有加锁成功的实例也一样）。

算法是异步的?

算法依赖于这样一个假定，它在处理的时候不是（基于）同步时钟的，每个处理中仍然使用的是本地的时间，它只是大致地以同样地速率运行，这样它就会有一个小的错误，与之相比会有一个小的自动开合的时钟时间。这个假设很像真正世界的电脑：每一台电脑有一个本地时钟，通常我们使用不同的电脑会有一个很小的时钟差。

基于这个观点，我们需要更好地指明我们的互斥法则：这是保证客户端能长时间保持状态锁定，其将会终止它们在有效时间内的工作（在步骤3中获得），减去一些时间（在处理时时间差时减去了一些毫秒用来补偿）。

想要了解更多关于相似系统获取一个时间差范围的内容，可以参考这篇文章：
Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

失败时重试

当客户端无法获取锁时，它应该在一个随机延迟后重试，从而避免多个客户端同时请求相同资源的锁（这可能会导致崩溃，没人会胜出）。同样的，客户端在大多数场合下尝试获取锁的速度越快，崩溃的窗口就越少（重试也越少），所以实际情况下客户端应尝试采用复用方式发送SET命令到多个实例。

强调客户在获取主锁失败是值得的，尽快释放（或部分释放）锁，这样没有必要等待key超时，就能够再次请求锁（但是如果网络分区发生变化时客户端不能与Redis实例通信的情况下，需要显性提示并等待key超时）。

释放锁

释放锁是简单的，只需要释放所有实例的锁即可，尽管客户端认为有能力成功锁住一个给出的实例。

安全参数

这个算法安全吗？我们可以尝试着去理解在不同的情景下发生了什么。

我们可以假设客户端在大多数情况下都能获得锁来开始，所有的实例都包含相同生存周期的key。由于key是在不同的时间设定的，所以key也将在不同的时间超时。然而，如果第一个节点最迟在T1时刻建立（第一个服务器的接触时间），最后一个key最迟在T2时刻建立（最后一个服务器的回复时间）。可以确定的是第一个key在超时之前将生存至少MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。所有其他的key到期后，至少这次key将同时在这一时刻设置。

在多半的key被设置这段时间里，另一个客户端将无法获得锁，因为如果N/2+1个key已经存在，N/2+1个SET NX操作将不能成功。所以一个锁被获取后，不可能在同一时刻被重复获取（违反互斥性）。

我们还想在多个客户端同时获取锁的时候不能同时成功。

如果一个客户端锁定大部分实例的时间超过了锁的最大有效时间（key有效时间） ，将认为锁无效，并进行解锁。所以我们仅考虑一个客户端在有效时间内获得大部分实例的锁的情况。这种情况已经在上文中讨论过， 在最小有效时间内，没有客户端会重新获取锁。所以大多数客户端可以同时锁定N/2+1个实例，只有当锁时间超过了有效时间，才会使锁失效。
你是否能提供一个明确的安全性证明，指出现存的相似的算法，或找出些bug? 那我们将感激不尽。

活性参数

系统的活性基于以下三个主要特性：

  1. 锁的自动释放（key会到期）: 最终所有的key将可以被重新锁住；
  2. 一般来说，客户端如果没有成功获得锁，或者获得了锁并且完成了工作，都会及时释放锁，使得我们无需等待key自动释放以重新获得。
  3. 当客户端重新获取锁之前，它会等待一段时间，这段时间比获取锁本身要长得多，这是为了尽量降低资源竞争引起的脑裂条件的概率。

然而，在网络割裂的情况下，我们得付出等同于存货时间的可用性代价，如果网络持续割裂，我们就得无限的付出这个代价。这发生于当客户端获取了一个锁，而在删除锁之前网络断开了。
基本上，如果网络无限期地持续割裂，那系统将无限期地不可用。

性能、故障恢复和文件同步

许多用户使用Redis作为一个高性能的加锁服务器，可以根据延迟动态的获取和释放锁，每秒可以成功执行大量的获取/释放锁操作。为了满足这些需求，在N台 Redis服务器之间减少延迟的方式是多路复用策略协同（或者叫做穷人协同，也就是说，将端口置为 non-blocking 模式，发送所有的命令，延迟读出所有的命令，假定客户端和每个Redis实例的往返时间是相似的）。

然而，如果我们旨在实现一种故障系统的恢复模式，这里有另一种与持久性相关的思路。

考虑这个基本问题，假定我们完全没有配置Redis的持久性。一个客户端需要锁定5个实例中的3个。其中一个允许客户端获取的锁重新启动，虽然我们可以再次为一些资源锁定3个实例，但其它的客户端同样可以锁定它，违反了排他锁安全性。

如果我们启用AOF持久性，情况就会得到相当的改善。例如我们可以通过发送 SHUTDOWN 升级一个服务器并且重启它。因为 Redis 的期限是通过语义设置的，所以服务器关闭的情况下虚拟时间仍然会流逝，我们所有的需求都得到了满足。不管怎样所有事务都会正常运转只要服务器完全关闭。如果电源中断会怎样？如果Redis进行了相关配置，默认情况下每秒文件都会同步写入磁盘，很有可能在重启后我们的数据会丢失。理论上，如果我们想在任何一种实例重启后保证锁的安全性，我们需要确保在持久性配置中设置 fsync=always。这将会在同等级别的CP系统上损失性能，传统上这种方式用来更安全的分配锁。

不管怎样事情总比我们一开始看起来好些。基本上算法的安全性得到保留，就算是当一个实例在故障后重启，它也将不再参与任何当前活跃的锁的分配。因此当实例重启时，当前所有活动锁的设置将从锁定的实例中获取，而不是从加入的实例中获取。

为了保证这一点，我们只需要做一个实例，在超过最大生存时间后，崩溃，不可用，那么就需要时间去获取所有存在着的锁的key，当实例崩溃时，其就会变得无效，会被自动释放。
使用延时重启可以大体实现安全，甚至不需要利用任何 Redis 的持久化特性，但是这存在着另外的副作用。举例来说，如果大量的实例崩溃，在生存时间内系统将变得全局不可用（这里的全局意味着根本就没有资源可用，在这个时间内所有的资源都会被锁定）。

让算法更可靠: 扩展锁

如果客户端的工作是由一小步一小步组成，就可以默认有效时间内使用范围更小的锁，并可以扩展算法来实现锁扩展机制。通常来说，当锁的值是比较小的值，在计算中，客户端可以向所有包含已经扩展存活时间的key实例发送 Lua 脚本来扩展锁，如果key存在，当获取锁时，它的值是客户端的随机值。

如果它能够在有效时间内，在大多数实例中扩展锁，客户端应该考虑重新获得锁（一般情况下，算法的使用非常类似于获取锁的使用）。

虽然不是从技术上修改算法，但是需要限制尝试请求锁的最大次数，否则的话，将违反活性参数中的一个。

原文链接：Distributed locks with Redis
翻译：沉潜飞动
译文链接：使用 Redis 实现分布式锁