Redis分布式锁之Redlock算法，那些你可能不知道的秘密！

「这是我参与2022首次更文挑战的第2天，活动详情查看：2022首次更文挑战」

1.前言

再往下看之前，我们先来了解下什么是RedLock算法。

Redlock算法是Redis作者antirez提出的一种分布式锁的实现方式，算法思想如下：在Redis的分布式环境中，可以假设有N个Redis master。这些节点完全互相独立，不存在主从复制或者其他集群协调机制。我们在N个实例上使用与单机Redis相同的方法获取和释放锁。现在我们假设有5个Redis master节点(官方文档里将N设置成5，实际大等于3就满足要求)并在在5台服务器上面运行这5个实例，这样保证他们不会同时都宕掉。为了取到锁，Redis客户端会执行以下操作:

1. 获取当前Unix时间，以毫秒为单位。
2. 使用同一个key和具有唯一值的value，依次尝试从这5个实例中获取锁。当向Redis请求获取锁时，客户端应该设置一个网络连接和响应超时时间，这个超时时间应该小于锁的失效时间。例如你的锁自动失效时间为10秒，则超时时间应该在5-50毫秒之间。这样可以避免服务器端Redis已经挂掉的情况下，客户端还在死死地等待响应结果。如果服务器端没有在规定时间内响应，客户端应该尽快尝试去另外一个Redis实例请求获取锁。
3. 客户端使用当前时间减去开始获取锁时间（步骤1记录的时间）就得到获取锁使用的时间。当且仅当从大多数（N/2+1，这里是3个节点）的Redis节点都取到锁，并且使用的时间小于锁失效时间时，锁才算获取成功。
4. 如果取到了锁，key的真正有效时间等于有效时间减去获取锁所使用的时间（步骤3计算的结果）。
5. 如果因为某些原因，获取锁失败（没有在至少N/2+1个Redis实例取到锁或者取锁时间已经超过了有效时间），客户端应该在所有的Redis实例上进行解锁（即便某些Redis实例根本就没有加锁成功，防止某些节点获取到锁但是客户端没有得到响应而导致接下来的一段时间不能被重新获取锁）。

关于对分布式锁算法RedLock，DDIA的作者Martin Kleppmann[1]发表了一篇很牛的文章。本文在此基础上翻译和融入个人理解，下面正式开始。

Redis 网站上发布了一种名为Redlock[2]的算法。该算法声称在Redis之上实现了容错分布式锁（或者更确切地说，租约[3]），身为分布式系统研究人员的我对此保持质疑，并写下了自己的思考。

由于Redlock 已经有 10 多个独立的实现，并且不知道谁已经在依赖这个算法，我认为是时候公开分享自己的笔记了。我不会深入探讨 Redis 的其他方面，因为Redis在其他地方已经受到批评[4]。

先说我非常喜欢 Redis，并且我过去在生产中成功使用过它。我认为它非常适合服务器之间共享一些瞬态、近似、快速变化的数据的情况，并且如果你偶尔由于某种原因丢失这些数据也没什么大不了的。例如，一个很好的用例是维护每个 IP 地址的请求计数器（为了限制访问速率）和每个用户 ID 它使用的不同 IP 地址集（用于滥用检测）。

然而，Redis 已经逐渐进入数据管理领域，那里需要有更强的一致性和持久性——这让我担心，因为这不是 Redis 的设计目标。但分布式锁是这些领域之一。让我们更详细地研究一下。

2.你为何要用分布式锁？

加锁的目的是确保多个节点在尝试执行相同工作时，只有一个节点实际执行此操作（至少一次只有一个）。这项工作可能是将一些数据写入共享存储系统、执行一些计算、调用一些外部 API 等。总而言之，你需要在分布式应用程序中使用锁的原因可能有两个：为了效率或正确性。怎么区分这两种原因呢？你可以问自己如果获取锁失败会发生什么：

• **效率：**获取锁可以避免不必要地做两次相同的工作（例如一些昂贵的计算）。如果加锁失败并且两个节点最终完成相同的工作，可能会导致成本略有增加（比如你最终向 AWS 支付的费用比其他情况多 5 美分）或带来轻微的不便（例如，用户最终两次收到相同的电子邮件通知）。
• **正确性：**使用锁可以防止并发进程相互干扰并破坏系统状态。如果加锁失败导致两个节点同时处理同一条数据，后果可能是文件损坏、数据丢失、永久性不一致，或者发生给患者服用的药物剂量错误或其他一些更严重的问题。

以上两者都是需要使用锁的原因，但你需要非常清楚自己正在处理两者中的哪一个。

如果你仅出于效率目的使用锁，则没有必要承担 Redlock 的成本和复杂性，运行 5 个 Redis 服务器并检查大多数以获得你的锁。你最好只使用单个 Redis 实例，也许可以异步复制到副本实例，以防主实例崩溃。

假如你使用单个Redis实例，在你的Redis节点突然断电，或者出现其他问题时，你的锁也会出现一些问题。但如果你出于效率优化的目而使用锁，并且Redis节点崩溃不会经常发生，那其实也没什么大不了。这种“没什么大不了”的场景正是 Redis的用武之地。至少，如果你只依赖单个 Redis 实例，那么管理系统的每个人都清楚这把锁是近似的，并且仅用于非关键路径和用途。

另一方面，具有 5 个副本和多数投票的 Redlock 算法乍一看似乎适用于对锁的正确性有严格要求的情况。但往往事与愿违，对于本文的其余部分，我们将假设你使用分布式锁是为了保证正确性，那么如果两个不同的节点同时认为它们持有相同的锁，这将是一个严重的错误。

3.用锁保护资源

让我们暂时先把 Redlock 的细节放在一边，然后讨论一下分布式锁的一般的使用方式（独立于所使用的特定锁算法）。重要的是要记住，分布式系统中的锁不像多线程应用程序中的互斥锁。这是一个更复杂的设计，因为不同节点和网络都可能以各种方式自主失败。

例如，假设你有一个应用程序，其中客户端需要更新共享存储（例如 HDFS 或 S3）中的文件。客户端首先获取锁，然后读取文件并进行一些更改，接着将修改后的文件回写，最后释放锁。该锁可防止两个客户端同时执行此读取->修改->写入同一个文件，这会导致更新丢失。代码可能如下：

 1// THIS CODE IS BROKEN
 2function writeData(filename, data) {
 3    var lock = lockService.acquireLock(filename);
 4    if (!lock) {
 5        throw 'Failed to acquire lock';
 6    }
 7
 8    try {
 9        var file = storage.readFile(filename);
10        var updated = updateContents(file, data);
11        storage.writeFile(filename, updated);
12    } finally {
13        lock.release();
14    }
15}

不幸的是，即使你有完美的锁服务，上面的代码也会被破坏。下图显示了数据如何被损坏：

在这个例子中，获取锁的客户端在持有锁后暂停了很长一段时间——例如因为垃圾收集器（GC）的启动。锁有一个超时（即它是一个租约），这是个很好的设计（否则崩溃的客户端最终可能会永远持有锁并且永远不会释放它）。但是，如果 GC 暂停持续时间超过租用到期时间，并且客户端没有意识到自己持有的锁已经过期，它可能会继续进行一些不安全的更改。

这个错误就曾经发生过：HBase 曾经有这个问题[5]。通常情况下，GC 暂停时间很短，但“stop-the-world”的GC暂停有时会持续几分钟 ——当然足以让租约到期。即使是所谓的“并发”垃圾收集器，如 HotSpot JVM 的 CMS，也不能完全与应用程序代码并行运行——因为它们有时也需要"stop-the-world"。

你无法通过在写回存储之前插入对锁定到期的检查来解决此问题。请记住，GC 可以在任何时间暂停正在运行的线程，包括你最不愿意发生的时间点（在最后一次检查和写入操作之间）。

虽然你自己使用的编程语言可能没有长时间的 GC，但你的进程还是可能会因许多其他原因而暂停。比如也许你的进程试图读取尚未加载到内存中的地址，它会导致缺页错误并暂停，直到从磁盘加载该页面。也许你的磁盘使用的是 EBS，因此在读取一个变量时可能不知不觉中变成了 Amazon 拥塞网络上的同步网络请求。也许还有许多其他进程在争夺 CPU，而你在调度程序树中遇到了一个黑色节点[6]。也许有人不小心向进程发送了 SIGSTOP等，这些都会导致进程暂停。

如果你仍然不相信进程会暂停，那么请考虑文件写入请求在到达存储服务器之前可能会因为网络堵塞而延迟。以太网和 IP 等数据包网络可能会使数据包出现任意延迟，它们确实如此：在 GitHub 的一个著名事件中，数据包在网络中延迟了大约 90 秒。这意味着一个应用进程可能会发送一个写请求，当租约已经到期时，它可能会在一分钟后才到达存储服务器。

即使在管理良好的网络中，这种事情也可能发生。你根本无法对时间做出任何假设，所以无论你使用哪种锁服务，上面的代码都是不安全的。

RedLock算法的价值在于它引入了多数派思想(paxos分布式一致性算法)，来解决单点故障对数据安全性和服务可用性的影响。但它严重依赖系统时钟和合适的租约时间设置也注定它不可能用于对强正确性有要求的场景。

4.使用fencing让锁安全

修复上面的问题其实非常简单：对存储服务的每个写请求中都带一个防护令牌。在这种情况下，防护令牌只需要是一个数字，每次客户端获取锁时它都会递增（例如，由锁服务递增）。如下图所示：

客户端1获得租约和值为33的令牌，但随后进入长时间暂停，租约到期。客户端 2 获取租约，得到值为34 的令牌（数字总是递增），然后将内容和值为34的令牌都写入到存储服务。稍后，客户端1恢复正常后，将写入请求：内容和值为33的令牌 发送到存储服务。但是，存储服务器记住它已经处理了具有更高数值令牌号 (34) 的写入，因此它拒绝带有令牌 33 的请求。

请注意，这需要存储服务器采取主动角色检查令牌，并拒绝较小值令牌的任何写操作。但这并不是特别难，一旦你知道了诀窍。并且如果锁服务生成严格单调递增的令牌，这使得锁是安全的。例如，如果你使用 ZooKeeper 作为锁定服务，你可以使用 zxid 或 znode 版本号作为防护令牌，并且你处于良好状态。

然而，这将我们引向了 Redlock 的第一个大问题：它没有任何用于生成单调递增的令牌的工具。该算法不能保证每次客户端获取锁时都会拿到递增的数字。这意味着即使算法在其他方面是完美的，使用它也不安全，因为在一个客户端进程暂停或有数据包延迟的情况下，你无法防止其他客户端此时去竞争那把锁。

对我来说，如何更改 Redlock 算法以开始生成防护令牌并不明显。它使用的唯一随机值不提供所需的单调性。仅仅在一个 Redis 节点上保留一个计数器是不够的，因为该节点可能会挂掉。在多个节点上保留计数器意味着它们的数据会出现不同步或同步不及时。你可能需要一个共识算法来生成fencing tokens。（如果只是增加一个计数器是简单的）

5.用时间解决共识

在想使用锁保证正确性的情况下不应该使用Redlock，因为Redlock无法生成 fencing 令牌。但还有一些更进一步的问题值得讨论。

在学术文献中，这种算法最实用的系统模型是带有不可靠故障检测器的异步模型[7]。简单来说，这意味着算法不对时间做任何假设：进程可能会暂停任意长度的时间，数据包可能会在网络中任意延迟，时钟可能会任意错误——尽管如此，算法都会做正确的事物。鉴于我们上面讨论的内容，这些都是非常合理的假设。

Redlock算法使用时钟的唯一目的是产生超时，以避免在节点关闭时永远等待。但是超时不一定准确：仅仅因为请求超时，并不意味着另一个节点已关闭 – 也可能是网络中存在很大延迟，或者你的本地时钟是错的。当用作故障检测器时，超时只是猜测出了问题。（如果可以的话，分布式算法将完全没有时钟，但这样就不可能达成共识[8]，获取锁就像一个比较和设置操作，需要达成共识[9]。）

请注意，Redis 使用gettimeofday[10]，而不是单调时钟[11]，以确定密钥的到期时间[12]。gettimeofday 的手册页明确指出[13]它返回的时间会受到系统时间不连续跳跃的影响——也就是说，它可能会突然向前跳跃几分钟，甚至时间跳跃（例如，如果时钟被NTP步进[14]，因为它与 NTP 服务器差别太大，或者如果时钟由管理员手动调整）。因此，如果系统时钟正在做一些奇怪的事情，很容易发生 Redis 中某个键的到期比预期快得多或慢得多的情况。

对于异步模型中的算法，这不是一个大问题：这些算法通常会在不基于时间做出假设[15]的前提下保证它们的安全属性始终不变。只有活性属性取决于超时或其他一些故障检测器。通俗地说，这意味着即使计时在系统中到处都是（进程暂停，网络延迟，时钟向前和向后跳跃），导致算法的性能可能会下降，但算法永远不会做出错误的决定。

然而，Redlock不是这样的。它的安全性取决于很多时间假设：

1. 它假设所有 Redis 节点在过期前都持有合适的时间长度
2. 网络延迟比过期时间短得多
3. 进程暂停时间比过期时间短得多

6.基于时间假设的Redlock不可靠

让我们看一些例子来证明 Redlock 对时间假设的依赖。假设系统有五个 Redis 节点（A、B、C、D 、 E）和两个客户端（1 和 2）。如果其中一个 Redis 节点上的时钟向前跳跃会发生什么？

1. 客户端 1 获取节点 A、B、C 上的锁。由于网络问题，无法访问 D 和 E。
2. 节点 C 上的时钟向前跳跃，导致锁到期。
3. 客户端 2 获取节点 C、D、E 上的锁。由于网络问题，无法访问 A 和 B。
4. 客户端 1 和 2 现在都相信他们持有锁。

如果 C 在将锁定持久化到磁盘之前崩溃并立即重新启动，则可能会发生类似的问题。出于这个原因，Redlock 文档建议至少将崩溃节点的重启延迟[16]到锁的最长存活时间。但是这种重新启动延迟再次依赖于合理准确的时间测量，但在发生时钟跳跃时也会导致失败。

可能你认为发生时钟跳跃不现实，因为你对正确配置 NTP 以调整时钟非常有信心。在这种情况下，让我们看一个进程暂停如何导致算法失败的示例：

1. 客户端 1 请求在节点 A、B、C、D、E 上锁定。
2. 当对客户端 1 的响应在进行中时，客户端 1 去进入 stop-the-world GC。
3. 所有 Redis 节点上的锁都会过期。
4. 客户端 2 在节点 A、B、C、D、E 上获取锁。
5. 客户端 1 完成 GC，并收到来自 Redis 节点的响应，表明它已成功获取锁（它们在进程暂停时保存在客户端 1 的内核网络缓冲区中） ）。
6. 客户端 1 和 2 现在都相信他们持有锁。

请注意，即使 Redis 是用 C 编写的，因此没有 GC，但这对我们没有帮助：任何客户端可能遇到GC暂停的系统都有这个问题。你只能通过在客户端 2 获取锁后阻止客户端 1 在锁下执行任何操作来确保安全，例如使用上面的防护方法。

较长的网络延迟会产生与进程暂停相同的效果。这可能取决于你的 TCP 用户超时——如果你使超时明显短于 Redis TTL，则可能会忽略延迟的网络数据包，但我们必须详细查看 TCP 实现才能确定。此外，随着超时，我们再次回到时间测量的准确性！

7.Redlock的同步假设

这些例子表明，Redlock 只有在你假设一个同步系统模型时才能正确工作——也就是说，一个系统具有以下属性：

1. 有边界时间的网络延迟（必须保证数据包总是在某个最大延迟时刻内到达）
2. 有边界时间的进程暂停（必须保证进程最长暂停时间小于设置的超时时间，即：hard real-time constraints[17]，通常你只能在汽车安全气囊系统中才能找到）
3. 有限的时钟误差（难以避免从坏的NTP服务器[18]获取时间）

请注意，同步模型并不意味着时钟是完全同步的时钟：这意味着你假设网络延迟、暂停和时钟漂移有一个已知的、固定的上限[19]。Redlock 算法假设延迟、暂停和漂移相对于锁的超时时间来说都很小；但如果时序问题变得与超时时间一样大，算法就会失败。

在运行良好的数据中心环境中，大部分时间都会满足时序假设——这被称为部分同步系统 。但这还不够，因为一旦这些时间假设被打破，Redlock 可能会违反其安全属性，例如在另一个客户端到期之前向一个客户端授予租约。如果你依赖你的锁来保证正确性，“大部分时间”是不够的——因为你需要它一直在正确运行。

有大量证据表明，假设大多数系统环境符合同步系统模型是种危险行为。我不断提醒自己 GitHub 的事故--90 秒数据包延迟[20] (90-second packet delay)。所以Redlock 不太可能在Jepsen[21]测试中幸存下来。

如果你想保证系统的正确性和强一直性，那你要利用好Raft、Viewstamped Replication、Zab 和 Paxos 这些为部分同步系统模型（或带有故障检测器的异步模型）设计的共识算法。共识算法必须放弃所有关于时序的假设。虽然假设网络、进程、时钟比实际情况更可靠是很诱人的，但在混乱复杂的分布式系统中，你必须非常小心你的假设条件。

8. 结论

我认为 Redlock 算法是一个糟糕的选择：对于效率优化来说实现太复杂、成本昂贵的，对于想保证正确性的场景来说它又不够安全。

特别是，该算法对时序和系统时钟做出了危险的假设（基本上假设同步系统具有有限的网络延迟和有限的操作执行时间），如果不满足这些假设，则会违反安全属性。此外，它缺乏用于生成隔离令牌的设施（保护系统免受网络长时间延迟或暂停进程的影响）。

如果使用锁是出于效率优化的目的且可以容忍一定程度的不正确性，我建议坚持使用简单的 Redis单节点锁定算法[22]（条件设置如果不存在以获得锁， atomic delete-if-value-matches 以释放锁），并在你的代码中非常清楚地记录锁只是近似值，有时可能会失败。不要费心设置五个 Redis 节点的集群。

另一方面，如果你需要锁定以确保正确性，请不要使用 Redlock。相反，请使用适当的共识系统，例如 ZooKeeper，可能通过实现锁定的 Curator recipes[23]之一。（至少，使用具有合理事务保证的数据库[24]。）并且请在锁定下的所有资源访问中强制使用防护令牌。

正如我在开头所说的，如果正确使用Redis，它是一个很好的工具。以上都不会降低 Redis 对其预期用途的实用性。 Salvatore[25]多年来一直致力于该项目，其成功当之无愧。但是每个工具都有局限性，了解它们并相应地进行计划很重要。

9.References

[1]原文：martin.kleppmann.com/2016/02/08/… [2] RedLock算法及实现：redis.io/topics/dist… [3]租约论文：www.semanticscholar.org/paper/Lease… [4] aphyr.com/tags/Redis [5]www.slideshare.net/enissoz/hba… [6] http://43.128.13.41/?p=188 [7] courses.csail.mit.edu/6.852/08/pa… [8] www.cs.princeton.edu/courses/arc… [9] cs.brown.edu/~mph/Herlih… [10]github.com/redis/redis… [11] linux.die.net/man/2/clock… [12]github.com/redis/redis… [13] linux.die.net/man/2/getti… [14] www.eecis.udel.edu/~mills/ntp/… [15] www.net.t-labs.tu-berlin.de/~petr/ADC-0… [16] redis.io/topics/dist… [17]stackoverflow.com/questions/1… [18] xenia.media.mit.edu/~nelson/res… [19] www.net.t-labs.tu-berlin.de/~petr/ADC-0… [20] github.com/blog/1364-d… [21] aphyr.com/tags/jepsen [22] redis.io/commands/se… [23] curator.apache.org/curator-rec… [24] www.postgresql.org/ [25] antirez.com/latest/0

兄dei，如果觉得我写的不错，不妨帮个忙

1、关注我的原创微信公众号「小梁编程汇」，每天准时推送干货技术文章，专注于写算法 + 计算机基础知识（计算机网络+ 操作系统+数据库+Linux）+ 分布式 + 面试攻略，听说关注了的不优秀也会变得优秀哦。

2、给俺点个赞呗，可以让更多的人看到这篇文章，顺便激励下我，嘻嘻。

作者简介

作者：大家好，我是小梁，曾获得ICPC亚洲赛奖牌，现就职于腾讯，我深知算法，计算机基础知识的重要性，所以申请了一个微信公众号『小梁编程汇』，专业于写这些底层知识，提升我们的内功，小梁期待你的关注，和我一起学习。 转载说明：未获得授权，禁止转载