Redis的分布式锁的研究实现

﹏ヽ暗。殇╰゛Y 2022-11-06 05:55 123阅读 0赞

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

有许多库和博客文章描述了如何使用Redis实现DLM（分布式锁管理器），但是每个库都使用不同的方法，与使用稍微复杂一些的方法相比，许多库使用的方法具有较低的保证。设计。

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

## 实作 ##

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

*  [Redlock-rb][]（Ruby实现）。还有[Redlock-rb的][Redlock-rb 1]一个[分叉，][Redlock-rb 1]它添加了一个gem，以便于分发，甚至更多。
 *  [Redlock-py][]（Python实现）。
 *  [陶器][Link 1]（Python实现）。
 *  [Aioredlock][]（Asyncio Python实现）。
 *  [Redlock-php][]（PHP实现）。
 *  [PHPRedisMutex][]（更多的PHP实现）
 *  [cheprasov / php-redis-lock][cheprasov _ php-redis-lock]（用于锁定的PHP库）
 *  [rtckit / react-redlock][rtckit _ react-redlock]（异步PHP实现）
 *  [Redsync][]（执行Go）。
 *  [Redisson][]（Java实现）。
 *  [Redis :: DistLock][Redis _ DistLock]（Perl实现）。
 *  [Redlock-cpp][]（C ++实现）。
 *  [Redlock-cs][]（C＃/。NET实现）。
 *  [RedLock.net][]（C＃/。NET实现）。包括异步和锁扩展支持。
 *  [ScarletLock][]（带有可配置数据存储的C＃.NET实现）
 *  [Redlock4Net][]（C＃.NET实现）
 *  [node-redlock][]（[NodeJS][node-redlock]实现）。包括对锁扩展的支持。

## 安全和活泼的保证 ##

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

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

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

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

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

从表面上看，这很好，但是存在一个问题：这是我们架构中的单点故障。如果Redis主服务器宕机了怎么办？好吧，让我们添加一个奴隶！如果主服务器不可用，请使用它。不幸的是，这是不可行的。这样，我们就无法实现互斥的安全属性，因为Redis复制是异步的。

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

1.  客户端A获取主服务器中的锁。
2.  在将密钥写入传输到从机之前，主机崩溃。
3.  奴隶晋升为主人。
4.  客户端B获取对相同资源A的锁定，而该资源A已经为其持有了锁定。**安全违规！**

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

## 单个实例正确实施 ##

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

要获取锁，必须遵循以下方法：

SET resource_name my_random_value NX PX 30000

该命令仅在密钥不存在时才设置密钥（NX选项），并且到期时间为30000毫秒（PX选项）。密钥设置为“我的*随机*值”。该值在所有客户端和所有锁定请求中必须是唯一的。

基本上，使用随机值是为了以安全的方式释放锁，并且脚本会告诉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主服务器，以确保它们将以大多数独立的方式发生故障。

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

1.  它以毫秒为单位获取当前时间。
2.  它尝试在所有N个实例中依次使用所有实例中相同的键名和随机值来获取锁定。在第2步中，当在每个实例中设置锁时，客户端使用的超时时间小于总锁自动释放时间，以便获取该超时时间。例如，如果自动释放时间为10秒，则超时时间可能在5到50毫秒之间。这样可以防止客户端长时间与处于故障状态的Redis节点通信时保持阻塞：如果一个实例不可用，我们应该尝试与下一个实例尽快通信。
3.  客户端通过从当前时间中减去在步骤1中获得的时间戳，来计算获取锁所花费的时间。 ，并且获取锁所花费的总时间小于锁有效时间，则认为已获取锁。
4.  如果获取了锁，则将其有效时间视为初始有效时间减去经过的时间，如步骤3中所计算。
5.  如果客户端由于某种原因（无法锁定N / 2 + 1实例或有效时间为负数）而未能获得该锁，它将尝试解锁所有实例（即使它认为不是该实例）能够锁定）。

## 算法是异步的吗？ ##

该算法基于这样的假设：尽管各进程之间没有同步时钟，但每个进程中的本地时间仍以近似相同的速率流动，并且与锁的自动释放时间相比，误差较小。这个假设与现实世界的计算机非常相似：每台计算机都有一个本地时钟，我们通常可以依靠不同的计算机来产生很小的时钟漂移。

在这一点上，我们需要更好地指定我们的互斥规则：只有在拥有锁的客户端将在锁有效时间内（如步骤3中获得的）减去一定时间（仅几毫秒）的情况下终止工作，才能保证这一点。以补偿进程之间的时钟漂移）。

有关需要限制*时钟漂移的*类似系统的更多信息，本文提供了有趣的参考：[租约：一种用于分布式文件缓存一致性的有效容错机制][Link 2]。

## 重试失败 ##

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

值得强调的是，对于未能获取大多数锁的客户端，尽快释放（部分）获取的锁有多么重要，这样就不必等待密钥期满才能再次获取锁（但是，如果发生网络分区，并且客户端不再能够与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服务器进行通信以减少延迟的策略肯定是多路复用（或穷人的多路复用，即将套接字置于非阻塞模式，发送所有命令，并读取所有命令）之后，假设客户端和每个实例之间的RTT相似）。

但是，如果我们要针对崩溃恢复系统模型，则还需要考虑持久性。

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

如果启用AOF持久性，则情况将会大大改善。例如，我们可以通过发送SHUTDOWN并重新启动它来升级服务器。因为Redis过期是从语义上实现的，所以实际上在服务器关闭时时间仍然流逝，所以我们的所有要求都很好。但是，只要关闭干净，一切都很好。停电呢？如果默认情况下将Redis配置为每秒在磁盘上进行fsync，则重启后可能会丢失我们的密钥。从理论上讲，如果我们想在遇到任何类型的实例重新启动时确保锁的安全性，则需要在持久性设置中始终启用fsync = always。反过来，这将完全破坏性能，使其达到传统上以安全方式实现分布式锁的CP系统的水平。

然而，事情总比乍看之下要好。基本上，只要实例在崩溃后重新启动，它就不再参与任何**当前活动的**锁，算法安全性就得以保留，因此，实例重新启动时的一组当前活动的锁全部是通过锁定实例而不是其他实例来获得的。正在重新加入系统。

为了保证这一点，我们只需要使一个实例在崩溃后至少不可用，而不是我们使用的最大[TTL（][TTL]即实例崩溃时存在的所有与锁有关的所有键）所需的时间。变得无效并被自动释放。

使用*延迟重新启动*，即使没有任何种类的Redis持久性，也基本上可以实现安全性，但是请注意，这可能会转化为可用性损失。例如，如果大多数实例崩溃，则该系统将对[TTL][]全局不可用（此处，全局意味着在此期间根本没有资源可锁定）。

## [\*][Link 3]使算法更可靠：扩展锁 ##

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

客户端仅应在能够在有效时间内将锁扩展到大多数实例中的情况下，才考虑重新获得锁（基本上，所使用的算法与获取锁时所使用的算法非常相似）。

但是，这不会从技术上改变算法，因此应限制最大的锁重新获取尝试次数，否则会破坏活动性之一。

[Redlock-rb]: https://github.com/antirez/redlock-rb
[Redlock-rb 1]: https://github.com/leandromoreira/redlock-rb
[Redlock-py]: https://github.com/SPSCommerce/redlock-py
[Link 1]: https://github.com/brainix/pottery#redlock
[Aioredlock]: https://github.com/joanvila/aioredlock
[Redlock-php]: https://github.com/ronnylt/redlock-php
[PHPRedisMutex]: https://github.com/malkusch/lock#phpredismutex
[cheprasov _ php-redis-lock]: https://github.com/cheprasov/php-redis-lock
[rtckit _ react-redlock]: https://github.com/rtckit/reactphp-redlock
[Redsync]: https://github.com/go-redsync/redsync
[Redisson]: https://github.com/mrniko/redisson
[Redis _ DistLock]: https://github.com/sbertrang/redis-distlock
[Redlock-cpp]: https://github.com/jacket-code/redlock-cpp
[Redlock-cs]: https://github.com/kidfashion/redlock-cs
[RedLock.net]: https://github.com/samcook/RedLock.net
[ScarletLock]: https://github.com/psibernetic/scarletlock
[Redlock4Net]: https://github.com/LiZhenNet/Redlock4Net
[node-redlock]: https://github.com/mike-marcacci/node-redlock
[Link 2]: http://dl.acm.org/citation.cfm?id=74870
[TTL]: https://redis.io/commands/ttl
[Link 3]: https://redis.io/topics/distlock#making-the-algorithm-more-reliable-extending-the-lock