一种基于 Redis 的分布式锁模式

Database

一种基于 Redis 的分布式锁模式

在许多不同进程间必须以互斥的方式操作共享资源的场景下,分布式锁是一个非常有用的元件。

目前已经有许多的库和博客文章阐明了如何基于 Redis 去实现一个 DLMDistributed Lock Manager 分布式锁管理器),但每个库的实现方式都不同,许多库使用简单的方法实现,这与用稍为复杂的设计所实现的相比,可靠性较低。

本文介绍了一种更为规范的算法来实现基于 Redis 的分布式锁。我们提出了一个叫做红锁 (Redlock) 的算法来实现 DLM,并且我们认为它比虚无缥缈的单一实例方法更为安全。我们希望社区能够分析它,提供反馈,并将其作为实现方式的起点,或者更复杂的东西的起点,或者替代方案设计的起点。

算法的实现

在介绍该算法之前,下面这些已经可用的实现可供参考:

安全性和有效性的保障

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

  1. 安全属性:互斥性。在任何时候,只能有一个客户端能持有锁。
  2. 有效性属性 A:死锁释放。即使锁定资源的客户端崩溃或被分割,最终总是有获得锁的可能。
  3. 有效性属性 B:容错性。只要大多数 Redis 节点是正常的,客户端就能够获得和释放锁。

为何基于故障转移的设计是不够的

为了搞清楚我们想要改进什么东西,我们需要分析一下大多数基于 Redis 的分布式锁库的现状。

Redis 去锁定一个资源最简单的方式就是在一个实例上创建一个 key 。这个 key 通常都会使用 Redis 的过期特性来限制其存活时长,因此,其最终都会被释放(符合我们属性清单里的第二条)。客户端通过删除 key 来释放资源。

从表面上看,这样做效果不错,但有个问题:它只是在我们架构中出现单点故障的时候没啥问题。但如果是 Redis 主节点挂了会怎样呢?好吧,也许我们可以加个副本以便在主节点挂掉的时候使用。但很遗憾,这并不可行。这么做会破坏我们的互斥性这条安全属性,因为 Redis 的复制是异步的。

这个模型的竞态条件如下:

  1. 客户端 A 在主节点上获取到锁。
  2. 主节点在写入的 key 复制到副本节点之前就崩溃了。
  3. 副本节点升级为主节点。
  4. 客户端 B 获得了 A 已经持有锁的同一资源的锁。违反了安全属性

有时,在特殊情况下,例如在故障期间,多个客户端可以同时持有锁,这是完全没有问题的。如果是这种情况,你可以使用基于复制的解决方案。否则,我们建议实施本文所介绍的解决方案。

单实例的正确实现

在尝试克服上述单实例设定的局限性之前,让我们看看如何在这个简单的案例中正确操作,这实际上是一个可行的解决方案,在应用中不时出现的竞态条件是可以接受的,而且锁定单实例是我们将用于这里描述的分布式算法的基础。

我们使用下面这种方式来获取锁:

    SET resource_name my_random_value NX PX 30000

这条命令只会在 key 不存在的时候设置它(NX 选项),然后设置一个 30000 毫秒的过期时间(PX 选项)。key 的值是 “my_random_value”。这个值在所有客户端和所有锁请求中必须是唯一的。

通常会采用随机值来安全的释放锁,在脚本里告诉 Redis :当一个 key 存在并且其值是我所期望的值时移除它。 Lua 脚本的实现如下:

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

这样做对于避免移除其他客户端创建的锁来说是很重要的。比如:一个客户端获取到锁,然后执行某些动作的阻塞时间超过「锁有效期」(届时锁的 key 会过期),随后又移除这个锁,然而这个锁在这期间早已被另外的客户端获得了。所以仅仅使用 DEL 指令是不安全的,因为这样可能导致一个客户端删掉另一个客户端的锁。而使用上述脚本,每个锁都用一个随机字符串进行「签名」,保证了只有创建了该锁的客户端才能删除它。

那么这个随机字符串应该是什么呢?我们假定它是从 /dev/urandom 中获取到的 20 个字节,但其实你能找到一种更低成本的方式来使你的你的任务足够独特。打个比方,一种安全的选择是使用 /dev/urandom 来作为 RC4 的种子,并以此来产生一条随机流。还有一个更为简单的解决方案是使用 UNIX 毫秒级时间戳,把它和客户端 ID 拼接起来。这可能不那么安全,但对于大多数场景来说应该足够了。

对应 key 的生存时间我们称之为「锁有效期」。它既是锁自动释放的时间,也是获得锁的客户端在其他客户端再次获得该锁前所需的动作执行的时间。这在技术上不违反互斥性这个保障,但仅限于从获得锁的那一刻起的特定时间窗口。

现在,我们有了一种获得与释放锁的好方式。有了这套系统,理论上对于一个由单一的,总是可用的实例组成的非分布式系统来说,是安全的。接下来让我把这个概念扩展到对我们来说没有这种保障的分布式系统中去。

红锁算法

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

为了获取锁,客户端执行以下操作:

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

算法是异步的吗?

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

在这点上,我们需要更好地指定我们的互斥规则:确保时间点为持有锁的客户端在锁有效时间内(步骤 3 中获得)内终止其工作花费的时间,再减去一点时间(仅几毫秒以便补偿进程之间的时钟漂移)。

后面这篇文章包含了有关需要绑定时钟漂移的类似系统的更多信息:。租赁:分布式文件缓存一致性的有效容错机制.

失败重试

当客户端无法获取锁时,它应该在随机的延迟后进行重试,以尝试对试图同时获取同一资源的锁的多个客户端进行去同步化处理(这在无人值守的情况下可能会触发脑裂条件)。此外,客户端在大多数 Redis 实例中尝试获取锁的速度越快,裂脑条件的窗口(以及重试的必要性)就越小,因此理想情况下,客户端应该尝试使用多路复用将 SET 命令同时发送到 N 个实例中去。

值得强调的是,对于未能获得大部分锁的客户端来说,尽快释放(部分)获得的锁是非常重要的,这样就无需等待 key 过期才能再次获得锁(但如果发生网络分区且客户端不再能够与 Redis 实例通信,则会在 key 过期时为可用性损失付出代价)。

释放锁

释放锁很简单,无论客户端是否相信它能够成功锁定给定的实例,都可以执行释放锁的操作。

安全论据

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

首先让我们假设客户端能够在大多数实例中获取到锁。所有实例都将包含一个具有相同生存时长的 key。但是,key 是在不同的时间创建的,因此 key 也会在不同的时间过期。如果第一个 key 在时间 T1(我们在连接第一台服务器之前采样的时间)设置为最差,而最后一个 key 在时间 T2(我们从最后一个服务器获得回复的时间)设置为最差,那就可以确定集合中第一个过期的 key 将至少存活 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。其他所有 key 都将在稍后过期,因此我们确信这些 key 至少在本次将同时设置。

在设置大部分键的时间内,另一个客户端将无法获取锁,因为如果 N/2+1 个键已经存在,则 N/2+1 的 SET NX 操作将无法成功。所以如果获得了一个锁,就不可能同时重新获得它(违反互斥属性)。

但是,我们还想确保多个客户端同时尝试去获取锁不能同时成功。

如果客户端锁定大多数实例的时间接近或大于锁的最大有效时间(我们用 SET 命令设置的基础 TTL),则它会认为锁无效并解锁实例,所以我们只需要考虑客户端能够在小于锁有效期的时间内锁定大多数实例的情况即可。在这种情况下,对于上面已阐明的参数,在 MIN_VALIDITY 时间内,没有客户端能够重新获取锁。因此,只有当锁定大多数实例的时间大于 TTL 时间时,多个客户端才能同时(此「时间」即是步骤 2 的结束时间)锁定 N/2+1 个实例,从而使锁无效。

有效性论据

系统有效性基于以下三个主要特征:

  1. 锁的自动释放(由于 key 过期):最终 key 可以再次被锁定。
  2. 实际上,客户端通常会在未获取到锁或者获取锁但任务终止时帮助移除锁,这使得我们可能不必等待 key 过期来重新获取锁。
  3. 事实上,当客户端需要重试锁时,它等待的时间会比获取大多数锁所需的时间要长得多,以便在资源争用期间不太可能出现脑裂情况。

然而,我们在网络分区这块需要付出等同于TTL 时间的可用性代价,所以如果有连续的分区,我们可能会无限地为此付出代价。每次客户端获取锁并在能够移除锁之前被分区时都会发生这种情况。

通常,如果存在无限连续的网络分区,系统可能会在无限长的时间内变得不可用。

性能、崩溃恢复与 fsync

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

然而,如果我们想以「崩溃-恢复」系统模型为目标,还需围绕持久性做另一种考虑。

通常要从这方面查看问题,需要假设我们根本没有配置 Redis 持久化。一个客户端在 5 个实例中的 3 个获取锁,其中一个能够获得锁的实例重启了,此时就会又有 3 个实例可以锁定同一资源,并且另一个客户端也能再次锁定它,这违反了独占锁的安全性属性。

如果我们开启了 AOF 的持久化,那么情况将会有所改善。比如,我们可以通过发送 SHUTDOWN 命令并重新启动服务器来升级它。由于 Redis 已通过语义实现了过期,因此当服务器关闭时,时间仍然会流转,这样我们所有的需求都可以得到满足。在一个正常的关闭动作下,这一切都很好,但如果停电呢?如果配置了持久化,默认情况下,Redis 会每秒将数据 fsync 到磁盘上。这样在重启后,我们可能会丢失 1s 内的 key。从理论上讲,如果我们要确保面对任何实例重新启动时的锁安全性,我们需要在持久化设置中启用 fsync=always。但由于额外的同步开销,这将影响性能。

然而,乍一看,情况比看起来更好。通常,只要实例在崩溃后重新启动时,该算法的安全性就会保留,该实例将不再参与任何当前活跃的锁。这意味着,当实例重新启动时,这组当前活跃锁全都是通过锁定非重新加入系统的实例获得的。

为了保证这一点,我们只需要制造一个实例,其在崩溃后,至少要在比我们设置的最大 TTL 多一点点时间内不可用。这是实例崩溃后变得无效,并自动释放所有存在的锁相关的 key 所需的时间。

使用延迟重启,即便没有任何 Redis 持久化可用,也基本上可以实现安全性。但是请注意,这可能会转化为可用性代价 。例如,如果大多数实例崩溃,则该系统在 TTL 时间内将全局不可用(此处全局意味着在此期间根本不会锁定资源)。

让算法更可靠:扩展锁

如果客户端执行的任务包含小的步骤,则默认情况下可以使用较小的锁有效期,并扩展算法来实现锁定机制。通常,如果在锁有效期接近低值的情况下,如果 key 存在并且其值仍然是获得锁时客户端分配的随机值,并且客户端处在计算值中部范围内,则可以通过向所有扩展了 keyTTL 的实例发送 Lua 脚本来扩展锁。

如果客户端能够将锁扩展到大多数实例,并且花费时间在有效时间内,那么客户端应该只考虑重新获取锁(通常使用到的算法与获取锁时使用的算法非常相似)。

然而,这并没有在技术上改变算法,因此应该限制重新获取锁的最大尝试次数,否则会违反有效性属性之一。

关于一致性的免责声明

请考虑仔细查看本页末尾的红锁分析 部分。 Martin Kleppmann 的文章和 antirez 对此的回答非常具有相关性。如果您比较关心一致性和正确性,则应关注以下主题:

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

想要帮忙?

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

提前致谢!

对红锁的分析


  1. Martin Kleppmann 这里分析了 Redlock。 可以在 此处 找到与此分析的对应点。
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。

原文地址:https://redis.io/docs/reference/patterns...

译文地址:https://learnku.com/database/t/71960

本文为协同翻译文章,如您发现瑕疵请点击「改进」按钮提交优化建议
讨论数量: 2

这没分段也太长了吧 :joy:

1个月前 评论
richardguo (楼主) 1个月前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!