文档：分布式锁

本页面正在审核中。本页面可能不正确、包含无效链接和/或需要技术审查。未来它可能会发生重大变化或被完全移除。

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

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

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

实现

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

• Redlock-rb (Ruby 实现)。还有一个 Redlock-rb 的分支，它增加了一个 gem 以方便分发。
• Redlock-py (Python 实现)。
• Pottery (Python 实现)。
• Aioredlock (Asyncio Python 实现)。
• RedisMutex (PHP 实现，同时支持 Redis 扩展 和 Predis 库 客户端)。
• Redlock-php (PHP 实现)。
• cheprasov/php-redis-lock (PHP 锁库)。
• rtckit/react-redlock (异步 PHP 实现)。
• Redsync (Go 实现)。
• Redisson (Java 实现)。
• Redis::DistLock (Perl 实现)。
• Redlock-cpp (C++ 实现)。
• Redis-plus-plus (C++ 实现)。
• Redlock-cs (C#/.NET 实现)。
• RedLock.net (C#/.NET 实现)。包含异步和锁扩展支持。
• ScarletLock (C# .NET 实现，支持可配置数据存储)。
• Redlock4Net (C# .NET 实现)。
• node-redlock (NodeJS 实现)。包含锁扩展支持。
• Deno DLM (Deno 实现)
• Rslock (Rust 实现)。包含异步和锁扩展支持。

安全性与活性保证

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

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

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

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

使用 Valkey 锁定资源的最简单方法是在实例中创建一个键。该键通常使用 Valkey 的过期功能创建，并设置有限的生存时间，以便最终被释放（我们列表中的属性 2）。当客户端需要释放资源时，它会删除该键。

表面上看这工作得很好，但存在一个问题：这是我们架构中的单点故障。如果 Valkey 主节点宕机了怎么办？

好吧，我们添加一个副本！并在主节点不可用时使用它。不幸的是，这并不可行。这样做我们将无法实现互斥的安全属性，因为 Valkey 复制是异步的。

这种模型存在竞态条件

1. 客户端 A 在主节点中获取锁。
2. 主节点在将键写入传输到副本之前崩溃。
3. 副本被提升为主节点。
4. 客户端 B 获取了与客户端 A 已持有的锁相同的资源的锁。安全性违规！

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

单实例的正确实现

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

要获取锁，方法如下

    SET resource_name my_random_value NX PX 30000

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

基本上，随机值用于安全地释放锁，通过一个脚本告诉 Valkey：只有当键存在并且键中存储的值与我期望的值完全相同时才移除该键。

在 Valkey 9.0.0 及更高版本中，可以使用内置的 DELIFEQ 命令原子地完成此操作

DELIFEQ resource_name my_random_value

在 Valkey 的早期版本中，可以使用 Lua 脚本实现相同的行为

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

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

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

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

所以现在我们有了一个获取和释放锁的好方法。有了这个系统，考虑一个由单个、始终可用的实例组成的非分布式系统是安全的。让我们将这个概念扩展到一个我们没有这种保证的分布式系统。

Redlock 算法

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

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

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

该算法是异步的吗？

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

在这一点上，我们需要更好地说明我们的互斥规则：它仅在持有锁的客户端在锁有效期内（如步骤 3 中获得）完成其工作时得到保证，减去一些时间（仅几毫秒，以补偿进程之间的时钟漂移）。

这篇论文包含了更多关于需要受限时钟漂移的类似系统的信息：租约：一种高效的分布式文件缓存一致性容错机制。

失败重试

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

值得强调的是，对于未能获取大多数锁的客户端来说，尽快释放（部分）获取的锁是多么重要，这样就不需要等待键过期才能再次获取锁（然而，如果发生网络分区并且客户端无法再与 Valkey 实例通信，则在等待键过期时会付出可用性代价）。

释放锁

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

安全论证

该算法安全吗？让我们检查不同场景下会发生什么。

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

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

然而，我们还希望确保多个同时尝试获取锁的客户端不能同时成功。

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

活性论证

系统活性基于三个主要特性

1. 锁的自动释放（因为键会过期）：最终键将再次可用于锁定。
2. 客户端通常会合作，在未获取锁时或在获取锁且工作完成后移除锁，这使得我们无需等待键过期即可重新获取锁。
3. 当客户端需要重试锁时，它会等待一个比获取大多数锁所需时间相对更长的时间，以概率性地降低资源争用期间出现脑裂情况的可能性。

然而，在网络分区上，我们会付出等于 TTL 时间的可用性代价，因此如果存在持续分区，我们可以无限期地支付此代价。这发生在客户端获取锁并在能够移除锁之前被分区隔离的每次情况。

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

性能、崩溃恢复和 fsync

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

然而，如果我们想针对崩溃恢复系统模型，还有另一个关于持久化的考虑。

基本上，要看这里的问题，我们假设我们配置 Valkey 时根本没有持久化。一个客户端在 5 个实例中的 3 个中获取了锁。其中一个客户端能够获取锁的实例被重启了，此时又出现了 3 个我们可以为相同资源加锁的实例，另一个客户端可以再次加锁，这违反了锁排他性的安全属性。

如果我们启用 AOF 持久化，情况会好很多。例如，我们可以通过向服务器发送 SHUTDOWN 命令并重新启动来升级服务器。由于 Valkey 的过期在语义上实现为服务器关闭时时间仍然流逝，所以我们所有的要求都得到了满足。然而，只要是干净关机，一切都很好。那断电怎么办？如果 Valkey 像默认那样配置为每秒将数据 fsync 到磁盘，那么在重启后我们的键可能会丢失。理论上，如果我们想在面对任何类型的实例重启时保证锁的安全性，我们需要在持久化设置中启用 fsync=always。这将由于额外的同步开销而影响性能。

然而，情况比乍看起来要好。基本上，只要实例在崩溃后重新启动时不再参与任何当前活动的锁，算法的安全性就会得到保留。这意味着当实例重新启动时，所有当前活动的锁都是通过锁定系统外的实例获得的。

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

通过使用延迟重启，即使没有任何 Valkey 持久化可用，也基本上可以实现安全性，但请注意这可能会导致可用性损失。例如，如果大多数实例崩溃，系统将全局不可用 TTL 时间（这里“全局”意味着在此期间根本没有资源可被锁定）。

使算法更可靠：扩展锁

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

客户端只有在能够将锁扩展到大多数实例中，并且在有效期内（基本上使用的算法与获取锁时使用的算法非常相似）才应认为锁已重新获取。

然而，这在技术上并没有改变算法，因此锁的重新获取尝试次数应受到限制，否则会违反其中一个活性属性。

关于一致性的免责声明

请仔细阅读本页面末尾的Redlock 分析部分。Martin Kleppmann 的文章和 antirez 的回复都非常相关。如果您关心一致性和正确性，应注意以下主题

1. 您应该实现隔离令牌（fencing tokens）。这对于可能需要大量时间的进程尤其重要，并适用于任何分布式锁定系统。扩展锁的生命周期也是一个选项，但不要假设只要获取锁的进程还活着，锁就会一直保留。
2. Valkey 没有使用单调时钟来处理 TTL 过期机制。这意味着挂钟时间偏移可能导致多个进程获取同一个锁。尽管可以通过阻止管理员手动设置服务器时间并正确设置 NTP 来缓解此问题，但在现实生活中仍有可能发生此问题并损害一致性。

想帮忙？

如果您对分布式系统感兴趣，很乐意听取您的意见/分析。其他语言的参考实现也会很棒。

提前感谢！

Redlock 分析

1. Martin Kleppmann 在此分析了 Redlock。此分析的反驳观点可在此找到。