Redis 分布式锁：Redlock 算法

使用 Redis 和 Redlock 算法来实现分布式锁。

前言

若某个场景涉及到了多个进程互斥地操作共享数据，那么分布式锁会是一种很有用的机制。

目前，网络上已经有很多使用 Redis 实现分布式锁管理器（DLM）的教程，甚至是第三方库。但是，每个库的实现方式都不同，一些库使用的方式过于简单，和稍微复杂一点的设计相比，它们能够提供的保证更少。

本文介绍了一种更加规范的算法，用于使用 Redis 实现分布式锁。这个算法叫做 RedLock，它实现了一个分布式锁管理器（DLM），比普通的单例方式要安全得多。

Redlock 算法实现

在开始介绍之前，你可以看看下面这些链接，它们是各个语言对该算法的实现，供你参考：

• Redlock-rb —— Ruby 实现
• Redlock-py —— Python 实现
• Pottery —— Python 实现
• Aioredlock —— Python 的异步实现
• Redlock-php —— PHP 实现
• PHPRedisMutex —— PHP 的进一步实现
• cheprasov/php-redis-lock —— PHP 实现。
• rtckit/react-redlock —— PHP 的异步实现。
• Redsync —— Go 实现。
• Redisson —— Java 实现。
• Redis::DistLock —— Perl 实现。
• Redlock-cpp —— C++ 实现。
• Redlock-cs —— C# .NET 实现。
• RedLock.net —— C# .NET 实现，包括异步和锁扩展支持。
• ScarletLock —— C# .NET 实现，包括可配置的数据存储。
• Redlock4Net —— C# .NET 实现。
• node-redlock —— NodeJS 实现，包括锁扩展支持。

锁的安全和存活保证

下面我将介绍三个属性，它们是实现一个高效的分布式锁的最低要求。这三个属性分别为：

1. 互斥性：在任何时刻，只有一个客户端可以持有锁。
2. 存活性：不会产生死锁，也就是说，客户端最终总是能够获取到锁，即使持有锁的客户端崩溃或者被分区。
3. 容错性：只要多数的 Redis 节点存活，客户端就能够正常地获取或释放锁。

基于故障转移的实现

为了理解 Redlock 算法有什么改进，让我们先来分析一下目前大多数基于 Redis 实现的分布式锁，并对其中涉及到的环节进行评估。

使用 Redis 来实现分布式锁的最简单的方式，就是在单个实例中创建一个 key。这个 key 通常在创建时就设置了有限的存活时间（通过 Redis 的 key 过期特性），这样一来，无论如何，它最终都会被释放（即实现了上面的存活性）。当客户端需要释放资源时，它只要把 key 删除掉即可。

这个算法看起来很好，但实际上，它有一个致命的问题：这么做会给当前架构引入一个单点故障。

万一 Redis 主节点宕机了怎么办呢？嗯……那就加个副本吧！当主节点不可用时，转而使用它的副本。

然而，不幸的是，这也是不可行的。如果这样做，我们就不能够实现互斥性，因为 Redis 是异步复制的。

下面是这个模型的竞态条件：

1. 客户端 A 在主节点上获取到了锁（创建了 key）。
2. 主节点宕机，创建 key 的操作还没来得及发送到副本上。
3. 副本被提升为主节点。
4. 客户端 B 获取到了 A 正在持有的同一个锁。互斥性被破坏！

有时候，在特殊场景下，例如在故障时，许多客户端可能持有同一个锁，这是完全可以接受的。如果是这种情况，那么你可以使用基于复制的解决方案。否则，建议你实现本文介绍的 Redlock 算法来生成和管理分布式锁。

单实例算法的正确实现方式

在尝试克服单实例的局限性（单点故障）之前，让我们先来看看如何正确地实现上述的简单算法。一方面，因为对于某些应用程序来说，它们有时可以接受竞态条件，这不失为一个可行方案。另一方面，也因为单实例锁是本文介绍的分布式锁算法的基础。

若要获得锁，执行下面的命令：

SET resource_name my_random_value NX PX 3000

在这个命令中，key 只会在其不存在时才被创建并设值（通过 NX 选项），并且会在 30000 毫秒后过期（通过 PX 选项）。上述 key 的值被设置为“my_random_key”。在实践中，这个值必须在所有客户端和锁申请中唯一。

基本上，这个随机值的用途就是安全地释放锁，同时还要结合脚本来告诉 Redis：只在 key 存在、且其值和预期相同时，才删除该 key（释放锁）。这是通过下面的 Lua 脚本实现的：

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

这么做很重要，目的是避免移除别的客户端创建的 key。

举个例子，当一个客户端获得锁后，开始执行一些耗时操作，还没有执行完，锁就失效了（key 过期了）。之后，由于 key 清理策略的存在，过期的锁（key）被清理，然而在此之前，别的客户端已经获得了该锁。这将导致互斥性被破坏。

单纯使用 DEL 是不安全的，因为一个客户端能够释放另一个客户端已经持有的锁。使用上述脚本后，每个锁都与随机字符串唯一绑定，这样一来，只有获得锁的客户端才能够释放锁。

那么，这个随机字符串应该是什么呢？它默认为 /dev/urandom 的前 20 个字节。不过，对于具体的应用场景，你或许能够找到代价更小的方案来生成一个足够唯一unique的值。

例如，若要保证绝对安全，你可以使用 /dev/urandom 来作为 RC4 的种子，然后从中生成一个伪随机流。

不过，你也可以选择使用更简单的方式：直接结合 UNIX 时间戳和客户端 ID。它没有前者安全，但是对于大多数场景来说，它都足够安全了。

“锁的有效时间”就是我们设置的 key 过期时间。它同时也是锁的自动释放时间，是客户端在获得锁后可以执行操作的时间，时间到后，别的客户端就能够获取到锁，而不会破坏锁的互斥性。不过，锁的互斥保证仅限于锁被获得后的一段时间内。

现在，我们有了一个获得/释放锁的好方法。有了这个机制，由单个永久可用的实例组成的非分布式的系统，也是安全的。

那么，如何把这个机制扩展到更复杂的分布式系统呢？

Redlock 算法

在以上算法的分布式版本中，我们假设有 N 个 Redis 主节点。这些节点互相独立，所以我们不需要复制或任何其他隐式协调机制。

由于已经介绍了在单实例上安全地获得/释放锁的算法，我们默认在 N = 1 时使用它。

在下面的例子中，我们设 N = 5，这是一个合理的值。这意味着我们需要 5 个主节点，并让它们分别运行在不同的主机或者虚拟机上，以此来保证它们故障时互不影响。

算法流程

在这个算法中，客户端获得锁的流程为：

1. 获取当前时间（毫秒）。
2. 顺序地尝试在 N 个主机上获得锁，在这个过程中使用同一个 key 和随机值。当设置 key 值时，客户端使用了一个相对短的超时时间（与锁的有效时间相比）。若超过这个时间还未能成功设置 key 值，那就放弃操作。例如，若锁的有效时间为 10 秒，这个超时时间可能只有 5 到 50 毫秒。这么做能够防止客户端长时间尝试和一个已经宕机的节点通信：如果一个实例不可用，我们应该立即转而尝试下一个。
3. 客户端计算获得锁所需的时间，计算方式为把当前的时间减去步骤 1 中获取的时间戳。当且仅当客户端能够在多数节点中获得锁，并且获得锁所需的时间小于锁的有效时间，它才会被认为成功获得了锁。
4. 如果客户端获得了锁，锁的有效时间将会是它的初始值减去步骤 3 中计算出来的所需时间。
5. 如果客户端由于某些原因未能获得锁（要么是它不能够至少锁住 N/2 个实例，要么是有效时间为负值），它都会尝试释放所有实例的锁（包括那些它未能成功获得锁的实例）。

异步

这个算法的正确性依赖于一个假设：进程之间没有同步锁，且每个进程的本地时间都以大致相同的速率更新，就算有误差，和锁的自动释放时间相比，它也应该很小才行。

这个假设与现实世界中的计算机非常相似：每台计算机都有本地时钟，我们通常可以依赖于许多不同的计算机，来获得一个小的时钟漂移。

到了这个时候，我们需要更好地定义互斥规则：只有在特定条件被满足时，互斥性才能够被保证。这个条件是，在步骤 3 中获得锁的客户端要某个时间前结束工作，这个时间就是锁的有效时间减去一小段时间（大概几毫秒，用于补充进程间的时钟漂移）。

你可以阅读 《Leases：一个高效、可容错的分布式文件缓存一致性机制》 ，它是发表在 ACM 上的一篇论文，其中包含了更多关于绑定时钟漂移的介绍。

失败重试

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

值得强调的是，对于未能获得多数锁的客户来说，尽快释放（部分）获得的锁是十分重要的。这样一来，它就不需要等待 key 过期才能再次获取锁（但是，如果发生网络分区，客户端就不再能够与 Redis 实例通信，那么在等待 key 过期时，系统的可用性会降低）。

锁释放

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

安全保证

这个算法是安全的吗？我们可以设想以下场景来验证。

作为开始，让我们假设客户端能够获得多数实例的锁。所有的实例上都有一个相同的 key，并且它们的存活时间也相同。然而，这个 key 是在不同时间被设置的，因此它们的过期时间是不同的。但是，我们可以假设一种最坏的情况，即：第一个 key 设置于 T1 时刻（假设此时还未与第一个服务端通信），而最后一个 key 设置于 T2（假设此时获得到了最后一个服务端的响应），那么我们可以确定第一个 key 至少会存活 MIN_VALIDITY = TTL - (T2 - T1) - CLOCK_DRIFT 那么长的时间。所有其他的 key 都会在这之后过期，那么我们就可以确定这些 key 会被同时设置至少一次。

在这段时间里，多数 key 都被设置，另一个客户端将不能够获得锁，因为 SET NX 不可能成功 N/2 + 1 次，如果已经存在了 N/2 + 1 个 key 的话。因此，如果一个锁已被获得，它就不可能同时又被重新获得（破坏互斥性）。

不过，我们还需要确保多个客户端同时尝试获得锁时，它们不会同时成功。

如果客户端在一个接近于或是大于锁最大有效时间（就是使用 SET 命令时的 TTL）之内，锁住了多数实例，它就会认为这个锁是无效的，继而解锁所有实例。所以，我们只需要考虑一种情况：当客户端能够在锁有效时间内，成功锁住多数实例。在这个情况下，由于前面已经提到的原因，客户端将无法重新获得锁。因此，当多个客户端能够同时锁定 N/2 + 1 个实例（在步骤 2 中描述的时间内），当且仅当锁住多数实例的耗时要大于 TTL，而这样在这种情况下锁是无效的。

存活保证

得益于下面三个特性，锁的存活得到了保证：

1. 锁自动释放（key 过期）：最终 key 是可以被重新上锁的。
2. 当不能获得锁时，或者当获得了锁，工作结束后，客户端通常都会配合地删除锁。这使得我们很大概率不需要等待 key 过期才能重新获得锁。
3. 当客户端需要重试锁时，它会延迟一段时间，这段时间和获得锁所需时间相比要长，这样一来可以从概率上，避免发生资源争用时的脑裂情况。

然而，由于使用了多台主节点，当网络分区时，我们将会损失 TTL 这么长时间的可用性。如果网络分区持续存在的话，我们的系统将持续不可用。这种情况有可能会发生，如果客户端获得了锁，却在释放锁之前就被分区了的话。

后语

下一篇文章，我将介绍 Redis 的数据结构。保持关注喔！

参考

• Redis Documentation - Distributed Locks with Redis

本文使用 CC BY-SA 4.0 国际协议 进行许可，欢迎 遵照协议规定 转载。
作者：六开箱
链接：https://lkxed.github.io/posts/redis-distributed-locks-redlock/