跳转至

Redis分布式锁

http://www.redis.cn/topics/distlock.html

分布式锁在很多场景中是非常有用的原语， 不同的进程必须以独占资源的方式实现资源共享就是一个典型的例子。

有很多分布式锁的库和描述怎么实现分布式锁管理器（DLM)的博客,但是每个库的实现方式都不太一样，很多库的实现方式为了简单降低了可靠性，而有的使用了稍微复杂的设计。

这个页面试图提供一个使用 Redis 实现分布式锁的规范算法。我们提出一种算法，叫 Redlock,我们认为这种实现比普通的单实例实现更安全,我们希望 redis 社区能帮助分析一下这种实现方法，并给我们提供反馈。

实现细节

在我们开始描述算法之前，我们已经有一些可供参考的实现库.

  • Redlock-rb (Ruby 版). There is also a fork of Redlock-rb that adds a gem for easy distribution and perhaps more.
  • Redlock-py (Python 版).
  • Aioredlock (Asyncio Python 版).
  • Redlock-php (PHP 版).
  • PHPRedisMutex (further PHP 版)
  • cheprasov/php-redis-lock (PHP library for locks)
  • Redsync.go (Go 版).
  • Redisson (Java 版).
  • Redis-DistLock (Perl 版).
  • Redlock-cpp (C++ 版).
  • Redlock-cs (C#/.NET 版).
  • RedLock.net (C#/.NET 版). Includes async and lock extension support.
  • ScarletLock (C# .NET 版 with configurable datastore)
  • node-redlock (NodeJS 版). Includes support for lock extension.

安全和活性失效保障

按照我们的思路和设计方案，算法只需具备 3 个特性就可以实现一个最低保障的分布式锁。

  1. 安全属性（Safety property）: 独享（相互排斥）。在任意一个时刻，只有一个客户端持有锁。
  2. 活性 A(Liveness property A): 无死锁。即便持有锁的客户端崩溃（crashed)或者网络被分裂（gets partitioned)，锁仍然可以被获取。
  3. 活性 B(Liveness property B): 容错。 只要大部分 Redis 节点都活着，客户端就可以获取和释放锁.

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

为了更好的理解我们想要改进的方面，我们先分析一下当前大多数基于 Redis 的分布式锁现状和实现方法.

实现 Redis 分布式锁的最简单的方法就是在 Redis 中创建一个 key，这个 key 有一个失效时间（TTL)，以保证锁最终会被自动释放掉（这个对应特性 2）。当客户端释放资源(解锁）的时候，会删除掉这个 key。

从表面上看，似乎效果还不错，但是这里有一个问题：这个架构中存在一个严重的单点失败问题。如果 Redis 挂了怎么办？你可能会说，可以通过增加一个 slave 节点解决这个问题。但这通常是行不通的。这样做，我们不能实现资源的独享,因为 Redis 的主从同步通常是异步的。

在这种场景（主从结构）中存在明显的竞态:

  1. 客户端 A 从 master 获取到锁
  2. 在 master 将锁同步到 slave 之前，master 宕掉了。
  3. slave 节点被晋级为 master 节点
  4. 客户端 B 取得了同一个资源被客户端 A 已经获取到的另外一个锁。安全失效！

有时候程序就是这么巧，比如说正好一个节点挂掉的时候，多个客户端同时取到了锁。如果你可以接受这种小概率错误，那用这个基于复制的方案就完全没有问题。否则的话，我们建议你实现下面描述的解决方案。

单 Redis 实例实现分布式锁的正确方法

在尝试克服上述单实例设置的限制之前，让我们先讨论一下在这种简单情况下实现分布式锁的正确做法，实际上这是一种可行的方案，尽管存在竞态，结果仍然是可接受的，另外，这里讨论的单实例加锁方法也是分布式加锁算法的基础。

获取锁使用命令:

Bash
    SET resource_name my_random_value NX PX 30000

这个命令仅在不存在 key 的时候才能被执行成功（NX 选项），并且这个 key 有一个 30 秒的自动失效时间（PX 属性）。这个 key 的值是“my_random_value”(一个随机值），这个值在所有的客户端必须是唯一的，所有同一 key 的获取者（竞争者）这个值都不能一样。

value 的值必须是随机数主要是为了更安全的释放锁，释放锁的时候使用脚本告诉 Redis:只有 key 存在并且存储的值和我指定的值一样才能告诉我删除成功。可以通过以下 Lua 脚本实现：

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

使用这种方式释放锁可以避免删除别的客户端获取成功的锁。举个例子：客户端 A 取得资源锁，但是紧接着被一个其他操作阻塞了，当客户端 A 运行完毕其他操作后要释放锁时，原来的锁早已超时并且被 Redis 自动释放，并且在这期间资源锁又被客户端 B 再次获取到。如果仅使用 DEL 命令将 key 删除，那么这种情况就会把客户端 B 的锁给删除掉。使用 Lua 脚本就不会存在这种情况，因为脚本仅会删除 value 等于客户端 A 的 value 的 key（value 相当于客户端的一个签名）。

这个随机字符串应该怎么设置？我认为它应该是从/dev/urandom 产生的一个 20 字节随机数，但是我想你可以找到比这种方法代价更小的方法，只要这个数在你的任务中是唯一的就行。例如一种安全可行的方法是使用/dev/urandom 作为 RC4 的种子和源产生一个伪随机流;一种更简单的方法是把以毫秒为单位的 unix 时间和客户端 ID 拼接起来，理论上不是完全安全，但是在多数情况下可以满足需求.

key 的失效时间，被称作“锁定有效期”。它不仅是 key 自动失效时间，而且还是一个客户端持有锁多长时间后可以被另外一个客户端重新获得。

截至到目前，我们已经有较好的方法获取锁和释放锁。基于 Redis 单实例，假设这个单实例总是可用，这种方法已经足够安全。现在让我们扩展一下，假设 Redis 没有总是可用的保障。

Redlock 算法

在 Redis 的分布式环境中，我们假设有 N 个 Redis master。这些节点完全互相独立，不存在主从复制或者其他集群协调机制。之前我们已经描述了在 Redis 单实例下怎么安全地获取和释放锁。我们确保将在每（N)个实例上使用此方法获取和释放锁。在这个样例中，我们假设有 5 个 Redis master 节点，这是一个比较合理的设置，所以我们需要在 5 台机器上面或者 5 台虚拟机上面运行这些实例，这样保证他们不会同时都宕掉。

为了取到锁，客户端应该执行以下操作:

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

这个算法是异步的么?

算法基于这样一个假设：虽然多个进程之间没有时钟同步，但每个进程都以相同的时钟频率前进，时间差相对于失效时间来说几乎可以忽略不计。这种假设和我们的真实世界非常接近：每个计算机都有一个本地时钟，我们可以容忍多个计算机之间有较小的时钟漂移。

从这点来说，我们必须再次强调我们的互相排斥规则：只有在锁的有效时间（在步骤 3 计算的结果）范围内客户端能够做完它的工作，锁的安全性才能得到保证（锁的实际有效时间通常要比设置的短，因为计算机之间有时钟漂移的现象）。.

想要了解更多关于需要时钟漂移间隙的相似系统, 这里有一个非常有趣的参考: Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

失败时重试

当客户端无法取到锁时，应该在一个随机延迟后重试,防止多个客户端在同时抢夺同一资源的锁（这样会导致脑裂，没有人会取到锁）。同样，客户端取得大部分 Redis 实例锁所花费的时间越短，脑裂出现的概率就会越低（必要的重试），所以，理想情况一下，客户端应该同时（并发地）向所有 Redis 发送 SET 命令。

需要强调，当客户端从大多数 Redis 实例获取锁失败时，应该尽快地释放（部分）已经成功取到的锁，这样其他的客户端就不必非得等到锁过完“有效时间”才能取到（然而，如果已经存在网络分裂，客户端已经无法和 Redis 实例通信，此时就只能等待 key 的自动释放了，等于被惩罚了）。

释放锁

释放锁比较简单，向所有的 Redis 实例发送释放锁命令即可，不用关心之前有没有从 Redis 实例成功获取到锁.

安全争议

这个算法安全么？我们可以从不同的场景讨论一下。

让我们假设客户端从大多数 Redis 实例取到了锁。所有的实例都包含同样的 key，并且 key 的有效时间也一样。然而，key 肯定是在不同的时间被设置上的，所以 key 的失效时间也不是精确的相同。我们假设第一个设置的 key 时间是 T1(开始向第一个 server 发送命令前时间），最后一个设置的 key 时间是 T2(得到最后一台 server 的答复后的时间），我们可以确认，第一个 server 的 key 至少会存活 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。所有其他的 key 的存活时间，都会比这个 key 时间晚，所以可以肯定，所有 key 的失效时间至少是 MIN_VALIDITY。

当大部分实例的 key 被设置后，其他的客户端将不能再取到锁，因为至少 N/2+1 个实例已经存在 key。所以，如果一个锁被（客户端）获取后，客户端自己也不能再次申请到锁(违反互相排斥属性）。

然而我们也想确保，当多个客户端同时抢夺一个锁时不能两个都成功。

如果客户端在获取到大多数 redis 实例锁，使用的时间接近或者已经大于失效时间，客户端将认为锁是失效的锁，并且将释放掉已经获取到的锁，所以我们只需要在有效时间范围内获取到大部分锁这种情况。在上面已经讨论过有争议的地方，在 MIN_VALIDITY 时间内，将没有客户端再次取得锁。所以只有一种情况，多个客户端会在相同时间取得 N/2+1 实例的锁，那就是取得锁的时间大于失效时间（TTL time)，这样取到的锁也是无效的.

如果你能提供关于现有的类似算法的一个正式证明（指出正确性），或者是发现这个算法的 bug？ 我们将非常感激.

活性争议

系统的活性安全基于三个主要特性:

锁的自动释放（因为 key 失效了）：最终锁可以再次被使用. 客户端通常会将没有获取到的锁删除，或者锁被取到后，使用完后，客户端会主动（提前）释放锁，而不是等到锁失效另外的客户端才能取到锁。. 当客户端重试获取锁时，需要等待一段时间，这个时间必须大于从大多数 Redis 实例成功获取锁使用的时间，以最大限度地避免脑裂。. 然而，当网络出现问题时系统在失效时间(TTL)内就无法服务，这种情况下我们的程序就会为此付出代价。如果网络持续的有问题，可能就会出现死循环了。 这种情况发生在当客户端刚取到一个锁还没有来得及释放锁就被网络隔离.

如果网络一直没有恢复，这个算法会导致系统不可用.

性能，崩溃恢复和 Redis 同步

很多用户把 Redis 当做分布式锁服务器，使用获取锁和释放锁的响应时间，每秒钟可用执行多少次 acquire / release 操作作为性能指标。为了达到这一要求，增加 Redis 实例当然可用降低响应延迟（没有钱买硬件的”穷人”,也可以在网络方面做优化，使用非阻塞模型，一次发送所有的命令，然后异步的读取响应结果，假设客户端和 redis 服务器之间的 RTT 都差不多。

然而，如果我们想使用可以从备份中恢复的 redis 模式，有另外一种持久化情况你需要考虑，.

我们考虑这样一种场景，假设我们的 redis 没用使用备份。一个客户端获取到了 3 个实例的锁。此时，其中一个已经被客户端取到锁的 redis 实例被重启，在这个时间点，就可能出现 3 个节点没有设置锁，此时如果有另外一个客户端来设置锁，锁就可能被再次获取到，这样锁的互相排斥的特性就被破坏掉了。

如果我们启用了 AOF 持久化，情况会好很多。我们可用使用 SHUTDOWN 命令关闭然后再次重启。因为 Redis 到期是语义上实现的，所以当服务器关闭时，实际上还是经过了时间，所有（保持锁）需要的条件都没有受到影响. 没有受到影响的前提是 redis 优雅的关闭。停电了怎么办？如果 redis 是每秒执行一次 fsync，那么很有可能在 redis 重启之后，key 已经丢弃。理论上，如果我们想在 Redis 重启地任何情况下都保证锁的安全，我们必须开启 fsync=always 的配置。这反过来将完全破坏与传统上用于以安全的方式实现分布式锁的同一级别的 CP 系统的性能.

然而情况总比一开始想象的好一些。当一个 redis 节点重启后，只要它不参与到任意当前活动的锁，没有被当做“当前存活”节点被客户端重新获取到,算法的安全性仍然是有保障的。

为了达到这种效果，我们只需要将新的 redis 实例，在一个 TTL 时间内，对客户端不可用即可，在这个时间内，所有客户端锁将被失效或者自动释放.

使用延迟重启可以在不采用持久化策略的情况下达到同样的安全，然而这样做有时会让系统转化为彻底不可用。比如大部分的 redis 实例都崩溃了，系统在 TTL 时间内任何锁都将无法加锁成功。

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

如果你的工作可以拆分为许多小步骤，可以将有效时间设置的小一些，使用锁的一些扩展机制。在工作进行的过程中，当发现锁剩下的有效时间很短时，可以再次向 redis 的所有实例发送一个 Lua 脚本，让 key 的有效时间延长一点（前提还是 key 存在并且 value 是之前设置的 value)。

客户端扩展 TTL 时必须像首次取得锁一样在大多数实例上扩展成功才算再次取到锁，并且是在有效时间内再次取到锁（算法和获取锁是非常相似的）。

这样做从技术上将并不会改变算法的正确性，所以扩展锁的过程中仍然需要达到获取到 N/2+1 个实例这个要求，否则活性特性之一就会失效。

想要得到帮助?

如果你正在做分布式系统，你的意见和分析非常重要。其他语言实现分布式锁的算法同样非常宝贵。

提前感谢各位!

Redlock 分析

Martin Kleppmann 在这儿分析了 Redlock. 我不赞同他的说法，并且对他做出了回复 我的回复在这儿.

回到页面顶部