分布式：[译] 基于 Redis 的分布式锁

原文地址：Distributed locks with Redis

当不同的进程必须以互斥的方式操作共享的资源时，分布式锁是一个非常实用的原始功能。

有很多组件库和博客都描述了如何去实现一个基于 Redis 的分布式锁管理器，但是每个库使用的实现方式不尽相同，其中许多库使用了一种简单的方式，它相比稍微复杂的设计只能提供更少的保障。

本篇尝试提供一种更加规范的算法来实现基于 Redis 的分布式锁。我们提出了一种叫做 Redlock 的算法，它可以实现一个分布式锁管理器（我们相信它比普通的单实例方法更加安全）。我们希望社区将分析它，提供反馈，并且将它作为更复杂/替代设计的基础。

实现

在描述这个算法之前，现在已经有一些可用的实现链接供参考：

• Redlock-rb (Ruby 实现). 还有一个 Redlock-rb 的分支，它为了方便分发新增了一个 gem 包，也许还有其他的。
• Redlock-py (Python 实现).
• Pottery (Python 实现).
• Aioredlock (Asyncio Python 实现).
• Redlock-php (PHP 实现).
• PHPRedisMutex (further PHP 实现)
• cheprasov/php-redis-lock (PHP 锁的库)
• rtckit/react-redlock (Async 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. 可用性 A：无死锁，即使锁住资源的客户端崩溃了或者被隔离分区，（其他客户端）也要能够获取锁
3. 可用性 B：容错，只要大部分 Redis 节点存活，客户端就能够获取和释放锁

基于故障转移的实现的不足

为了理解我们想要改善的东西，让我们先分析下大多数基于 Redis 分布式锁的库的现状。

使用 Redis 锁住一个资源最简单的方式是在实例中创建一个 key。利用 Redis 的过期特性，这个 key 会在一个有限的时间内存活，所以它最终会被释放（特性二）。当客户端想要释放资源的时候，它会删除这个 key。

表面上这样可以正常工作，但是存在一个问题：系统的单点故障。如果 Redis 的主节点宕机会发生什么？当然我们可以增加一个从节点，并且在主节点不可用时使用它。不幸的是，因为 Redis 的复制是 异步 的，这样做我们无法保证互斥的安全性。

这个模型存在一个明显的竞态条件：

1. 客户端 A 获取主节点的锁
2. 主节点在将 key 传播给从节点之前宕机
3. 从节点被提升为主节点
4. 客户端 B 获取之前被 A 锁住的资源对应的锁，违反了安全规定！

如果多个客户端在特殊情况下，比如故障期间，同时持有一个锁是完全可以的。那么你可以使用基于从节点的解决方案。否则我们建议实施本文描述的解决方案。

单实例的正确实现

在突破上文描述的单实例限制之前，让我们看看在这个简单的情况下该如何正确地做。因为这对于可以接受时不时出现竞态条件的应用实际上是一个可行的解决方案，并且着眼于单实例也是我们讨论分布式算法的基础。

下述是一个获取锁的方法：

SET resource_name my_random_value NX PX 30000

这个命令将会在 key 不存在时（NX 选项）设置这个 key，伴随着 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，这不是那么安全，但可能在大多数环境中都可以胜任。

我们设置的 key 的存活时间，被称作锁的有效时间。它既是自动释放的时间，也是客户端在锁被别的客户端再次获取之前，（保证技术上不违反互斥性）去执行所需操作的时间。互斥保证 仅限于 从锁的那一刻开始的这个给定的时间窗口。

因此现在我们有了一个好的方式去获取和释放锁。这个由始终可用的单实例组成的非分布式系统被论证为是安全的。让我们将这个概念扩展到一个没有此类保障的分布式系统。

Redlock 算法

在算法的分布式版本中，我们假设有 N 个 Redis 主节点。这些节点完全独立，我们并没有使用复制或者其他的辅助系统。我们已经描述过如何在单个实例中安全地获取和释放锁。我们也理所当然地认为算法会使用那个方法在单个实例中获取和释放锁。在我们的例子中，我们设置 N = 5，它是一个合理的值，因此我们需要在不同的计算器或虚拟机上运行 5 个 Redis 主节点来确保它们会以各自的方式宕机。

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

1. 获取毫秒级的当前时间

2. 使用相同的键名和随机的值，依次在所有 N 个实例中获取锁。在第二步往每个实例设置锁的时候，客户端使用了一个小于锁自动释放时间的 timeout 去获取锁。比如锁的自动释放为 10 秒，这个 timeout 可以在 5-50 毫秒的范围。这可以防止客户端与一个宕机的 Redis 节点维持过长的阻塞状态：如果一个实例不可用，我们应当尽快与下一个节点通信。

3. 客户端通过减去第一步中获取的时间戳计算出为了获取锁花费的时间。只有当客户端能够在大多数实例（至少 3 个）获取锁，并且花费的时间少于锁的有效时间时，才认为锁被获取了。

4. 如果锁被获取了，它的有效时间将是初始有效时间减去花费的时间，就如第三步计算的那样。

5. 如果客户端因为某些原因获取锁失败（要么是不能在 N/2+1 个实例中获取锁，要么是有效时间为负的），它会尝试 unlock 所有的实例（甚至是它认为不能锁的实例）。

算法是异步的吗？

这个算法依赖了假设 ，进程之间没有一个同步的锁，并且每个进程中的当地时钟以大致相同的速率流动，与锁的自动释放时间相比，误差很小。这个假设看起来像一个真实世界的计算机，每个计算机有一个当地时钟，我们可以依赖不同计算机来获取一个较小的时间偏移。

在这点上我们需要明确指出我们的 互斥性规则：只要持有锁的客户端在锁的有效时间（在第三步中得到的）（减去一些毫秒为了补偿不同计算机之间的时间偏移）内结束它的工作，就能保证互斥性。

更多有关需要绑定时钟偏移的类似系统的信息，这个论文是一个有趣的参考：Leases: an efficient fault-tolerant mechanism for distributed file cache consistency。

错误重试

当一个客户端无法获取锁，它应该在一个 随机延迟 后重试，来避免多个客户端在同一时刻尝试获取同一个资源的锁（这可能会导致脑裂，没有人胜出）。同时一个客户端在大多数 Redis 实例中获取锁越快，脑裂的窗口越小（重试的需要也是），因此理想情况下客户端应该尝试在同一时刻使用多路复用发送 SET 命令到 N 个实例。

值得强调的是，当客户端们获取大多数锁失败时，尽快（部分地）释放获取的锁是多么的重要，如此就没有必要去等待锁过期才能被再次获取（然而如果网络被隔离，客户端不再能与 Redis 实例通信时，将因等待锁过期产生可用性损失）。

安全论证

这个算法安全吗？我们可以尝试在不同场景下理解发生的事情。

开始我们假设一个客户端能够在大多数实例中获取锁。所有的实例都包含一个有相同存活时间的 key。然而，key 在不同的时间被设置，因此 key 们会在不同的时间过期。但是如果第一个 key 在时间 T1 被设置（极端情况，我们联系第一个服务器之前的时间），最后一个 key 在 T2 被设置（极端情况，我们从最后一个服务器得到响应的时间），我们确信集合中第一个过期的 key 至少会存活 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。所有其他的键将随后过期，因此我们确信至少这一次所有的键会被同时设置。

在大多数 key 被设置的过程中，其他客户端将不能获取这把锁，因为 N/2+1 个 SET NX 操作在 N/2+1 个 key 已经存在的情况下无法成功。因此如果一个锁已经被获取，它就没有可能在同一时刻被再次获取（违背了互斥性）。

然而我们想要确保多个客户端不能在同一时刻同时获取锁。

如果一个客户端用近乎或者大于锁有效时间（我们用 SET 时指定的存活时长）的时长锁住了大多数实例，它会认为锁失效并 unlock 所有的实例，因此我们只需要考虑客户端能够在有效时间内锁住大部分实例的情况。在这种情况下对于上文表述的论点，应该没有客户端能在 MIN_VALIDITY 内再次获取锁。因此多个客户端只有用超过存活时间的时长去锁大部分实例，才能在同一时刻锁住 N/2+1 个实例，这样会让锁失效。

你能否针对现有或类似算法，提供一个安全性的正式证明，或找到一个 bug？我们将不胜感激。

可用性论证

系统的可用性基于三个主要特性：

1. 锁的自动释放（键的过期）：最终键们可以被再次上锁

2. 客户端通常在锁没有被获取时（获取失败），或者当锁被获取且工作结束时清除锁，我们不必等待键的过期就能够重新获取锁。

3. 客户端需要重试一把锁时会等待一段（超过获取大部分锁所需的时间的）时长，为了能在资源争用期间使脑裂不太可能。

然而我们会在网络隔离时付出等同于存活时间的 可用性损失，因此如果发生连续的网络隔离，我们可能无限期地付出这个损失。每一次客户端获取了一把锁，在能够清除锁之前被隔离时，都会发生这种情况。

本质上如果存在无限连续的网络隔离，系统会在一段无限的时间内变的不可用。

性能、崩溃恢复和 fsync

许多用户使用 Redis 作为一个锁服务，需要较高的性能去获取和释放锁，并且每秒钟可能执行许多获取和释放操作。为了满足这个需求，与 N 个 Redis 服务对话来降低延迟的策略显然是采用多路复用（或者说是穷人的多路复用，也就是把 socket 设为非阻塞模式，发送所有的命令，之后再读取所有的命令，假设客户端和各个实例之间的 RTT 是相似的）。

然而，如果我们想要以崩溃恢复系统模型为模型，就还有一个关于持有型的注意事项。

为了在这里看清这个问题，让我们假设我们没有配置 Redis 的持有化。一个客户端获取了 3/5 个实例的锁。其中一个能被客户端获取锁的实例被 重启 了，此时又有三个实例能让我们为相同的资源上锁，并且其他的客户端可以再次锁住它，这违反了锁互斥的安全特性。

如果我们开启 AOF 持久化，情况就能改善很多。比如我们可以通过发送 SHUTDOWM 来升级一个服务器并重启。因为 Redis 的过期是语义上实现的，因此在服务器离线时时间仍会流逝，所有我们的需求都很好。然而只要它是干净的关闭，一切都很好。停电怎么办？ 如果 Redis 默认配置为每秒在磁盘上 fsync 一次，那么重启后我们的密钥可能会丢失。 理论上，如果我们想在任何类型的实例重启时保证锁的安全性，我们需要在持久化设置中启用 fsync=always。 这反过来又会完全破坏与传统上用于以安全方式实现分布式锁的 CP 系统相同级别的性能。

然而，事情比乍看之下要好。 基本上只要实例在崩溃后重新启动，算法就保持安全，它不再参与任何当前处于活动状态的锁。因此实例重新启动时当前处于活动状态的锁的集合，在被获取时排除了重新加入系统的这个实例。

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

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

更加可靠的算法：锁的扩展

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

如果客户端能够在有效时间内将锁扩展到大多数实例，（基本上使用的算法与获取锁时使用的算法非常相似），客户端应该只考虑重新获取锁。

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

Redlock 的分析

Martin Kleppmann 在这里分析了 Redlock。我不同意这分析，且在这里对他的分析提出了我的回复。