Redis 的分布式锁

Redis 的分布式锁模式

分布式锁在许多环境中是一个非常有用的原语，其中 不同的进程必须以 独家方式。

有许多库和博客文章描述了如何实现 带有 Redis 的 DLM（分布式锁管理器），但每个库使用不同的 方法，并且许多使用简单的方法，与 可以通过稍微复杂的设计来实现。

本页描述了一种更规范的算法来实现 Redis 的分布式锁。我们提出了一种算法，称为 Redlock， 它实现了一个我们认为比原版单体更安全的 DLM 实例方法。我们希望社区分析一下，提供 feedback 的 S Sample，并将其用作 implementationor more 的起点 复杂或替代设计。

实现

在描述算法之前，这里有一些实现的链接 已经可用，可供参考。

安全和活跃保证

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

  1. 安全特性：互斥。在任何给定时刻，只有一个客户端可以持有锁。
  2. 活动属性 A：无死锁。最终，即使锁定资源的 Client 端崩溃或被分区，也始终可以获取锁。
  3. 活动属性 B：容错。只要大多数 Redis 节点都已启动，客户端就可以获取和释放锁。

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

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

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

从表面上看，这运行良好，但有一个问题：这是我们架构中的单点故障。如果 Redis 主节点宕机了怎么办？ 那么，让我们添加一个副本吧！如果 master 不可用，则使用它。不幸的是，这是不可行的。这样，我们就无法实现互斥的安全属性，因为 Redis 复制是异步的。

此模型存在争用条件：

  1. 客户端 A 获取 master 中的锁。
  2. 在将对 key 的写入传输到副本之前，主服务器会崩溃。
  3. 副本将提升为主副本。
  4. 客户端 B 获取了对 A 已经持有锁的同一资源的锁。安全违规！

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

使用单个实例正确实现

在尝试克服上述单实例设置的限制之前，让我们看看在这个简单的情况下如何正确地做到这一点，因为在不时可以接受争用条件的应用程序中，这实际上是一个可行的解决方案，并且因为锁定到单个实例是我们将用于此处描述的分布式算法的基础。

要获取锁，方法如下：

    SET resource_name my_random_value NX PX 30000

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

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

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

为了避免删除由其他客户端创建的锁，这一点很重要。例如，客户端可能会获取锁，在执行某些作时被阻止，时间超过锁有效期（密钥过期的时间），然后删除已由其他客户端获取的锁。 仅使用DEL不安全，因为客户端可能会删除其他客户端的锁。相反，使用上述脚本，每个锁都使用随机字符串“签名”，因此只有当锁仍然是尝试删除它的客户端设置的锁时，才会删除该锁。

这个随机字符串应该是什么？我们假设它是 20 字节/dev/urandom，但您可以找到更便宜的方法来使其对您的任务来说足够独特。 例如，一个安全的选择是将 RC4 与/dev/urandom，并从中生成一个伪随机流。 更简单的解决方案是使用具有微秒精度的 UNIX 时间戳，将时间戳与客户端 ID 连接起来。它不那么安全，但可能足以满足大多数环境的需求。

“锁有效期”是我们用作键的生存时间的时间。它既是自动释放时间，也是客户端在另一个客户端能够再次获取锁之前执行所需作的时间，而不会在技术上违反互斥保证，该保证仅限于从获取锁的那一刻起的给定时间窗口。

所以现在我们有一个很好的方法来获取和释放锁。使用此系统，对由单个始终可用的实例组成的非分布式系统进行推理是安全的。让我们将这个概念扩展到没有此类保证的分布式系统。

Redlock 算法

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

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

  1. 它获取当前时间（以毫秒为单位）。
  2. 它尝试按顺序获取所有 N 个实例中的锁，在所有实例中使用相同的键名称和随机值。在步骤 2 中，在每个实例中设置锁时，客户端使用与总锁自动释放时间相比较小的超时来获取它。例如，如果自动释放时间为 10 秒，则超时可能在 ~ 5-50 毫秒范围内。这可以防止客户端长时间尝试与已关闭的 Redis 节点通信：如果实例不可用，我们应该尽快尝试与下一个实例通信。
  3. 客户端通过从当前时间减去步骤 1 中获取的时间戳来计算获取锁所经过的时间。当且仅当客户端能够在大多数实例（至少 3 个）中获取锁，并且获取锁所用的总时间小于锁有效期，则认为已获取锁。
  4. 如果已获取锁，则其有效期被视为初始有效期减去经过的时间，如步骤 3 中计算的那样。
  5. 如果客户端由于某种原因（无法锁定 N/2+1 个实例或有效期为负数）未能获取锁，它将尝试解锁所有实例（甚至是它认为无法锁定的实例）。

算法是异步的吗？

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

在这一点上，我们需要更好地指定我们的互斥规则：只有持有锁的 Client 端在锁有效期内终止其工作（如步骤 3 中所示），减去一些时间（为了补偿进程之间的时钟漂移，只有几毫秒），才能保证它。

本文包含有关需要绑定时钟漂移的类似系统的更多信息：Leases：分布式文件缓存一致性的高效容错机制。

失败时重试

当 Client 端无法获取锁时，它应该在随机延迟后重试，以便尝试使多个 Client 端尝试同时获取同一资源的锁不同步（这可能会导致没有人获胜的裂脑情况）。此外，客户端在大多数 Redis 实例中尝试获取锁的速度越快，出现裂脑情况的窗口就越小（并且需要重试），因此理想情况下，客户端应尝试发送SET命令同时发送到 N 个实例。

值得强调的是，对于未能获取大多数锁的客户端来说，尽快释放（部分）获取的锁是多么重要，这样就无需等待密钥到期即可再次获取锁（但是，如果发生网络分区并且客户端不再能够与 Redis 实例通信， 在等待密钥过期时需要支付可用性损失）。

释放锁

释放锁很简单，无论客户端是否认为它能够成功锁定给定实例，都可以执行释放锁。

安全参数

算法安全吗？让我们看看在不同场景中会发生什么。

首先，我们假设客户端能够在大多数实例中获取锁。所有实例都将包含一个具有相同生存时间的 key。但是，密钥是在不同的时间设置的，因此密钥也会在不同的时间过期。但是，如果第一个密钥在时间 T1（我们在联系第一个服务器之前采样的时间）设置在最差，而最后一个密钥在时间 T2（我们从最后一个服务器获得回复的时间）设置在最差时间，那么我们确信该集中第一个过期的密钥至少会存在MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT.所有其他密钥稍后都会过期，因此我们确信至少在这段时间内会同时设置这些密钥。

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

但是，我们还希望确保尝试同时获取锁的多个客户端无法同时成功。

如果客户端使用接近或大于锁定最大有效期（我们基本上用于 SET 的 TTL）的时间锁定了大多数实例，它将认为锁定无效并解锁实例，因此我们只需要考虑客户端能够在小于有效期的时间内锁定大多数实例的情况。在这种情况下，对于上面已经表达的参数，对于MIN_VALIDITY任何客户端都不应能够重新获取锁。因此，只有当锁定大多数实例的时间大于 TTL 时间时，多个客户端才能同时锁定 N/2+1 个实例（“时间”是步骤 2 的结尾），从而使锁定无效。

活动参数

系统活动性基于三个主要功能：

  1. 自动释放锁（因为密钥过期）：最终密钥可以再次被锁定。
  2. 事实上，客户端通常会在未获取锁时，或者当获取锁但工作终止时合作删除锁，这使得我们可能不必等待密钥过期即可重新获取锁。
  3. 事实上，当客户端需要重试锁时，它等待的时间比获取大多数锁所需的时间要长，以便概率地使资源争用期间的裂脑情况不太可能。

但是，我们支付的可用罚款等于TTLtime on network partitions，所以如果有连续的 partitions，我们可以无限期地支付这个代价。 每次 Client 端获取锁并在能够删除锁之前被分区时，都会发生这种情况。

基本上，如果存在无限连续的网络分区，系统可能会在无限长的时间内不可用。

性能、崩溃恢复和 fsync

许多使用 Redis 作为锁定服务器的用户在获取和释放锁定的延迟以及每秒可以执行的获取/释放作数量方面都需要高性能。为了满足这个要求，与 N Redis 服务器通信以减少延迟的策略肯定是多路复用（将 socket 置于非阻塞模式，发送所有命令，稍后读取所有命令，假设客户端和每个实例之间的 RTT 相似）。

但是，如果我们想以崩溃恢复系统模型为目标，那么围绕持久性还有另一个考虑因素。

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

如果我们启用 AOF 持久化，情况将有很大改善。例如，我们可以通过向服务器发送SHUTDOWN命令并重新启动它。因为 Redis 过期是语义实现的，所以当服务器关闭时仍然经过时间，我们所有的要求都很好。 但是，只要是干净的关机，一切都很好。停电怎么办？如果 Redis 默认配置为每秒在磁盘上 fsync，则在重新启动后，我们的密钥可能会丢失。理论上，如果我们想在面对任何类型的实例重启时保证锁的安全性，我们需要启用fsync=always在 Persistence settings （持久性设置） 中。由于额外的同步开销，这将影响性能。

然而，事情比乍一看要好。基本上 只要实例在 crash，则它不再参与任何当前活动的 lock。这意味着 获取实例重启时的当前活动锁集 通过锁定正在重新加入系统的实例以外的实例。

为了保证这一点，我们只需要在崩溃后使一个实例不可用 至少比 MAX 多一点TTL我们使用。这是需要的时间 有关实例崩溃时存在的锁的所有键 失效并自动释放。

使用延迟重启基本上可以实现安全性 没有任何类型的 Redis 持久性可用，但请注意，这可能会 转化为可用性损失。例如，如果大多数实例 crash，则系统将变为全局不可用TTL（此处的 global 表示 在此期间，根本不会锁定任何资源）。

使算法更可靠：扩展锁

如果客户端执行的工作由小步骤组成，则可以 默认使用较小的锁有效期，并扩展算法实现 锁延长机构。基本上是客户端，如果在 计算时，可能会扩展 lock 通过向所有实例发送扩展密钥 TTL 的 Lua 脚本 如果键存在并且其值仍然是客户端分配的随机值 当获取锁时。

如果客户端能够扩展 锁定到大多数实例中，并在有效期内 （基本上，要使用的算法与获取时使用的算法非常相似 锁）。

但是，这在技术上不会改变算法，因此最大数量 的锁重新获取尝试应受到限制，否则 properties 被违反。

关于一致性的免责声明

请考虑仔细阅读本页末尾的 Redlock 分析部分。 Martin Kleppman 的文章和 antirez 对此的回答非常相关。 如果您关心一致性和正确性，您应该注意以下主题：

  1. 您应该实现屏蔽令牌。 这对于可能需要大量时间的进程尤其重要，并且适用于任何分布式锁定系统。 延长锁的生命周期也是一种选择，但不要假设只要获取锁的进程处于活动状态，就会保留锁。
  2. Redis 没有将单调时钟用于 TTL 过期机制。 这意味着 wall-clock 偏移可能会导致多个进程获取 lock。 尽管可以通过阻止管理员手动设置服务器的时间并正确设置 NTP 来缓解此问题，但此问题仍有可能在现实生活中发生并损害一致性。

想要提供帮助？

如果您喜欢分布式系统，那么有您的意见/分析会很棒。其他语言的参考实现也很棒。

提前致谢！

Redlock 分析

  1. Martin Kleppmann 在这里分析了 Redlock。可以在此处找到与此分析相反的分析。