译自： https://redis.io/topics/distlock#the-redlock-algorithm

在许多环境中，分布式锁是一种非常有用的原语，其中不同的进程必须以互斥的方式与共享资源一起运行。

有许多库和博客文章描述了如何使用Redis实现DLM（分布式锁管理器），但是每个库都使用不同的方法。并且其中的许多库使用比较简单的方法，与稍微复杂的方法相比，在安全保证性上稍差一点。

我们试图提供一种更典型的算法来使用Redis实现分布式锁。我们提出了一种称为Redlock的算法，它实现了一种我们认为比vanilla单实例方法更安全的DLM。我们希望社区将对其进行分析，提供反馈，并将其作为替代设计的起点。

安全和可用性保障

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

1、 安全属性：相互排斥。 在任何给定时刻，只有一个客户端可以持有锁。

2、 可用性属性A：无死锁。 最终即使锁定资源的客户端崩溃或被分区，也始终可以获取锁。

3、 可用性属性B：容错。 只要大多数Redis节点启动，客户端就能够获取和释放锁。

为什么基于故障转移的实现还不够

为了理解我们想要改进的内容，让我们分析大多数基于Redis的分布式锁库的当前状态。

使用Redis锁定资源的最简单方法是在实例中创建锁。锁通常使用Redis expires功能在有限的生存时间内创建，最终它将被释放。当客户端需要释放资源时，它会删除这个锁。

从表面上看，这很有效，但存在一个问题：我们架构中的单点故障。如果Redis master出现故障会怎样？好吧，让我们添加一个slave！如果主服务器不可用，请使用它。遗憾的是，这不可行。通过这样做，我们无法实现互斥的安全属性，因为Redis复制是异步的。

这个模型有明显的竞争条件：

  1. 客户端A获取master服务器中的锁。
  2. 在写入密钥之前，在将key传输到slave之前master崩溃
  3. slave被提升为master。
  4. 客户端B获取对已经拥有锁的相同资源的锁。安全违规！

有时，在特殊情况下，(例如在故障期间，多个客户端可以同时保持锁定)，这样做也没有问题。如果是这种情况，您可以使用基于复制的解决方案。否则，我们建议实施本文档中描述的解决方案。

使用单个实例的正确实现

在尝试克服上述单实例实现的限制之前，让我们在这个简单的情况下检查如何正确地进行操作。 在频繁的竞争条件的应用中，这也是可被接受的方案。因为在单实例中的锁也是我们使用分布式算法的基础。

要获得锁定，可以采取以下措施：

SET resource_name my_random_value NX PX 30000

该命令仅在key不存在时才设置（NX选项），过期时间为30000毫秒（PX选项）。 键设置为值“my_random_value”。 此值必须在所有客户端和所有获取锁的请求中都是唯一的。

使用随机值是为了以安全的方式释放锁，需要使用一个脚本告诉Redis：仅当key存在且存储在key上的值恰好是我期望的值时才删除密钥。 这是通过以下Lua脚本完成的：

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

避免删除由另一个客户端创建的锁，这一点很重要。例如，客户端可能获得一个锁，在某些操作中被阻塞的时间超过锁的有效时间（密钥过期被释放的时间），等它从阻塞中恢复后会移除已经由某个其他客户端重新获取的锁。所以仅使用DEL是不安全的，因为客户端可能会删除另一个客户端的锁。使用上面的脚本，每个锁都使用随机字符串“签名”，因此只有在确认是当时枷锁的客户端去尝试删除锁定时，锁才会被删除。

这个随机字符串应该取什么值呢？我假设它是来自/dev/urandom的20个字节，但是你可以找到更有效的方法来使它对你的任务足够独特。例如，使用/dev/urandom对RC4进行种子处理，并从中生成伪随机流。一个更简单的解决方案是使用微妙级别的unix时间与client ID做组合。它可能不是那么安全，但可能在大多数环境中都可以完成任务。

我们设置的key的过期时间被称为“锁的有效时间”。它既是自动释放时间，也是客户端为了执行所需操作而在另一个客户端可能再次获取锁之前所拥有的时间。它没有在技术上违反互斥保证，只是限制了获得锁的时间窗口。

所以现在我们有了获得和释放锁的好方法。这个非分布式的单点系统，总是可用的，并且安全的。让我们将概念扩展到没有这种保证的分布式系统。

Redlock算法

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

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

  1. 获取当前毫秒级别的时间。
  2. 在所有实例中使用相同的键名和随机值，尝试按顺序获取所有N个实例中的锁。在步骤2期间，当在每个实例中设置锁时，为每次设置操作设定一个失败超时时间，这个超时时间跟总的锁的超时时间相比要小。例如，如果自动释放时间是10秒，则失败超时可以在~5-50毫秒范围内。这可以防止客户端在试图与关闭的Redis节点通信时长时间保持阻塞。也就是说如果实例不可用，我们应该尝试尽快与下一个实例通话。
  3. 客户端通过从当前时间中减去在步骤1中获得的时间戳来计算获取锁定所需的时间。当且仅当客户端能够在大多数实例中获取锁定时（至少3个）并且获取锁定所经过的总时间小于锁定有效时间，认为锁被获取。
  4. 如果获得了锁，则其有效时间被认为是初始有效时间减去经过的时间，如步骤3中计算的。
  5. 如果客户端由于某种原因（无法锁定N / 2 + 1实例或有效时间为负）无法获取锁，它将尝试解锁所有实例（即使在第二步中没有获得该锁）。

算法是异步的吗

该算法依赖于这样的假设：虽然整个过程没有同步时钟，但每个进程中的本地时间仍然大致以相同的速率流动。并且误差与锁的自动释放时间相比较小。 这个假设非常类似于真实世界的计算机：每台计算机都有一个本地时钟，我们通常可以依靠不同的计算机来获得较小的时钟漂移。

失败重试机制

当客户端无法获取锁定时，它应该在延迟随机时间后再次尝试。随机时间是为了防止多个客户端在同一个时间获取同一个资源。 此外，客户端尝试在大多数Redis实例中获取锁定的速度越快，时间窗口越小，因此理想情况下客户端应尝试将SET命令发送到N个实例 同时使用多路复用。

值得强调的是，对于未能获得大多数锁定的客户来说，尽快释放（部分）获取的锁定是多么重要，因此无需等待密钥到期以便再次获取锁定（ 但是，如果发生网络分区且客户端无法再与Redis实例通信，则需要付出一点代价，等待密钥到期。

释放锁

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

安全性分析

这个算法是否安全？ 我们可以尝试了解不同场景中会发生什么。

首先让我们假设客户端能够获得大多数实例的锁。 所有实例中的key都有一个相同的过期时间。 但是，key是在不同的时间设置的，因此key也将在不同的时间到期。 假设第一个key是在T1时间设置，最后一个key是在T2时间设置，可以确信，最先被设定的key至少能够存活 MIN_VALIDITY = TTL-（T2-T1）-CLOCK_DRIFT。 TTL是过期时间， CLOCK_DRIFT是时间漂移。

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

可用性分析

系统可用性基于三个主要特征：

  1. 锁的自动释放（因为密到期）：最终可以再次锁定。
  2. 通常情况下，客户端会在未获取锁定时或在获取锁定并且工作终止时移除锁定，这使得我们可能不必等待密到期以重新获取锁。
  3. 事实上，当客户端需要重试锁定时，它等待的时间比获取大多数锁定所需的时间要大得多，减少在资源竞争期间抢占资源的可能性。

如果一直持续的发生网络故障，那么没有客户端可以申请到锁。分布式锁系统也将无法提供服务直到网络故障恢复为止。

性能，崩溃恢复和文件同步

使用Redis作为锁服务器的许多用户在获取和释放锁的延迟以及每秒可执行的获取/释放操作的数量方面需要高性能。为了满足这一要求，与N 个Redis服务器通信以减少延迟的策略肯定是多路复用。

但是，为了实现故障恢复，还有另一个数据持久性的问题需要考虑。

首先，让我们假设我们根本没有持久性配置Redis。客户端在5个实例中的3个中获取锁定。如果其中的一台机器重启了，那么另一个客户端可以再次锁定它，违反了锁独占的安全属性。

如果我们启用AOF持久化，事情会有所改善。例如，我们可以通过发送SHUTDOWN重新启动服务器。因为Redis过期是在语义上实现的，所以当服务器关闭时，实际上时间仍然在流逝。那么停电会怎么样？如果默认情况下将Redis配置为每秒在磁盘上进行fsync，则重新启动后可能会丢失key。理论上，如果我们想要在任何类型的实例重启时保证锁定安全性，我们需要在持久性设置中启用fsync = always。这反过来将完全破坏性能。

另一种解决方案是在崩溃后，等待至少比我们使用的最大TTL多一点的时间，才启用这个实例。也就是说，实例崩溃时存在的所有锁所需的时间，都等待它自动到期无效。

即使没有使用任何的Redis持久性策略，使用延迟重启基本上可以实现安全性。但请注意，这可能会影响一部分性能。 例如，如果大多数实例崩溃，系统将变TTL时间内变为全局不可用（这里全局意味着在此期间根本没有资源可锁定）。

使算法更可靠：锁续约

如果客户端执行的工作都由小步骤组成，则默认情况下可以使用较小的锁定时间，并扩展实现锁续约机制的算法。 客户端在计算过程中如果发现快要接近锁的有效期，则可以通过向所有实例发送Lua脚本来续约锁定（如果密钥存在且其值仍然是这个客户端分配的随机值）。

如果能够将锁续约到大多数实例，并且在有效时间内（基本上使用的算法与获取锁时使用的算法非常相似），客户端续约锁成功。

但是，应该限制锁定重新获取尝试的最大次数，否则会违反其中一个可用性属性，导致该锁长时间不能被其他客户端获取。