使用redis实现分布式锁

使用 Redis 的分布式锁模式

在许多环境中,分布式锁是非常有用的原语,在这些环境中,不同的进程必须以互斥的方式操作共享资源。

有许多库和博客文章描述了如何使用 Redis 实现 DLM(分布式锁管理器),但每个库都使用不同的方法,并且许多库使用简单的方法,与稍微复杂一点的方法相比,其保证较低设计。

本页描述了使用 Redis 实现分布式锁的更规范的算法。我们提出了一种名为Redlock 的算法,它实现了 DLM,我们认为它比普通的单实例方法更安全。我们希望社区能够对其进行分析、提供反馈,并将其用作实现或更复杂或替代设计的起点。

实施

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

安全和存活保证

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

  1. 安全特性:互斥。在任何给定时刻,只有一个客户端可以持有锁。

  2. 存活属性A:无死锁。最终,即使锁定资源的客户端崩溃或分区,也始终可以获取锁。

  3. 存活属性B:容错性。只要大多数 Redis 节点正常运行,客户端就可以获取和释放锁。

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

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

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

表面上这工作得很好,但有一个问题:这是我们架构中的单点故障。如果 Redis master 宕机了会发生什么?好吧,让我们添加一个副本!如果主人不可用,请使用它。不幸的是,这是不可行的。通过这样做,我们无法实现互斥的安全属性,因为 Redis 复制是异步的。

该模型存在竞争条件:

  1. 客户端A获取master中的锁。

  2. 在对密钥的写入传输到副本之前,主服务器崩溃了。

  3. 副本被提升为主节点。

  4. 客户端 B 获取对 A 已持有锁的同一资源的锁。违反安全!

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

单实例的正确实现

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

要获取锁,方法如下:

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并不安全,因为客户端可能会删除另一个客户端的锁。使用上面的脚本,每个锁都用随机字符串“签名”,因此只有当它仍然是客户端尝试删除它时设置的锁时,锁才会被删除。

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

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

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

Redlock 算法

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

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

  1. 它获取当前时间(以毫秒为单位)。

  2. 它尝试在所有 N 个实例中顺序获取锁,在所有实例中使用相同的密钥名称和随机值。在步骤 2 中,在每个实例中设置锁时,客户端使用比总锁自动释放时间较小的超时来获取锁。例如,如果自动释放时间为 10 秒,则超时可能在 5-50 毫秒范围内。这可以防止客户端在尝试与已关闭的 Redis 节点通信时长时间处于阻塞状态:如果某个实例不可用,我们应该尽快尝试与下一个实例通信。

  3. 客户端通过从当前时间减去步骤 1 中获得的时间戳来计算获取锁所花费的时间。当且仅当客户端能够在大多数实例(至少 3 个)中获取锁时,并且获取锁所花费的总时间小于锁的有效时间,则认为获取了锁。

  4. 如果获取了锁,则其有效时间被视为初始有效时间减去经过的时间(如步骤 3 中计算的那样)。

  5. 如果客户端由于某种原因未能获得锁(要么无法锁定 N/2+1 个实例,要么有效时间为负),它将尝试解锁所有实例(甚至是它认为没有锁定的实例)能够锁定)。

该算法是异步的吗?

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

此时我们需要更好地指定我们的互斥规则:只有持有锁的客户端在锁有效时间内(如步骤3中获得的)终止其工作,减去一些时间(仅几毫秒),才可以保证。以补偿进程之间的时钟漂移)。

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

失败重试

当客户端无法获取锁时,它应该在随机延迟后重试,以尝试使多个客户端同时尝试获取同一资源的锁(这可能会导致裂脑情况,其中没有人)获胜)。此外,客户端尝试获取大多数 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任何客户端都不应该能够重新获取锁。因此,只有当锁定多数实例的时间大于 TTL 时间时,多个客户端才能同时锁定 N/2+1 个实例(“时间”为步骤 2 的结束时间),从而使锁定无效。

活性参数

系统活跃度基于三个主要特征:

  1. 自动释放锁(因为钥匙过期):最终钥匙可以再次被锁定。

  2. 事实上,当没有获取锁时,或者当获取锁并且工作终止时,客户端通常会配合删除锁,这使得我们不必等待密钥过期来重新获取锁。锁。

  3. 事实上,当客户端需要重试锁定时,它会等待比获取大多数锁定所需的时间更长的时间,以便在概率上使资源争用期间不太可能出现脑裂情况。

但是,我们支付的可用性惩罚等于TTL网络分区上的时间,因此如果存在连续分区,我们可以无限期地支付此惩罚。每当客户端获取锁并在能够删除锁之前被分区时,就会发生这种情况。

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

性能、崩溃恢复和 fsync

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

然而,如果我们想要以崩溃恢复系统模型为目标,则还需要考虑持久性。

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

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

然而,事情比乍一看要好。基本上,只要实例在崩溃后重新启动时,它不再参与任何当前活动的锁,算法的安全性就会得到保留。这意味着实例重新启动时当前活动的一组锁都是通过锁定除重新加入系统之外的实例而获得的。

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

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

让算法更可靠:扩展锁

如果客户端执行的工作由小步骤组成,则可以默认使用较小的锁有效时间,并扩展实现锁扩展机制的算法。基本上,如果在计算过程中,当锁有效性接近较低值时,客户端可以通过向所有扩展该键的 TTL 的实例发送 Lua 脚本来扩展锁(如果该键存在并且其值仍然是)获取锁时客户端分配的随机值。

仅当客户端能够将锁扩展到大多数实例并且在有效时间内(基本上使用的算法与获取锁时使用的算法非常相似)时,客户端才应该考虑重新获取锁。

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

关于一致性的免责声明

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

  1. 您应该实施隔离令牌。这对于可能花费大量时间并适用于任何分布式锁定系统的进程尤其重要。延长锁的生命周期也是一种选择,但不要假设只要获取锁的进程还活着,锁就会被保留。

  2. Redis 不使用单调时钟作为 TTL 过期机制。这意味着挂钟偏移可能会导致锁被多个进程获取。尽管可以通过阻止管理员手动设置服务器时间并正确设置 NTP 来缓解该问题,但在现实生活中仍然有可能发生此问题并影响一致性。

最后更新于