基于 Redis 的分布式锁：RedLock

对于存在多个进程必须互斥的访问共享资源的环境中，分布式锁是一个很有用的基础工具。

许多库和博客描述了怎么使用 redis 实现一个 DLM（分布式锁管理器），但是每一个库都有不同的实现方式，并且大多数都是可靠性较低的简单实现。

这里将尝试提供一个更加规范的基于 redis 实现的分布式锁的算法，称为 Redlock。该算法实现了一个比使用单实例构建分布式锁的更加安全的 DLM。

实现

以下是一些该算法的实现：

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

安全性和可用性保证

以下是将要描述的分布式锁的最小保证，拥有三个属性：

1. 安全性（Safety property）：锁的互斥。在任意时刻，只会有一个客户端持有锁。
2. 可用性 A（Liveness property A）: 死锁自动释放。当出现类似某个客户端在申请了一个锁之后崩溃了或者和 DLM 出现了网络分区，这个锁最终是可以被其它客户端申请得到，而不是永远不可用.
3. 可用性 B（Liveness property B）: 容灾. 只要大多数的 Redis 节点都是正常的，客户端就可以获取和释放锁.

基于故障转移的实现方案的问题

为了明白这个 redlock 优化了什么问题，让我们来分析一下现有的大多数基于 redis 实现的分布式锁库。

使用 redis 来锁住某个资源的最简单方式就是创建一个有 ttl 的 key，使用 redis 的过期键特性，这个锁最终都可以释放。当客户端需要释放这个资源的时候，删除该 key 即可。

表面上看是可行的，但是这里有一个问题：该 key 存储在 redis 的一个单点实例中，如果这个实例挂了就会出问题。很容易想到的是增加一个从节点，当主节点挂掉之后就使用这个从节点即可。很不幸这是不可行的，如果这样做我们将不能实现属性1–锁的互斥，因为 redis 主从复制是异步的。

下面是一个基于该模型的并发竞争的例子：

1. 客户端 A 在 master 中获得了锁
2. master 在将 key 传递到 slave 之前挂掉了
3. slave 被提升为主节点
4. 客户端 B 申请到了客户端 A 已经持有的用来锁住某资源的锁。安全性被破坏。

在某些情况下这种方式是可行的，例如业务允许在故障期间存在多个客户端同时持有相同的锁。如果是这种情况，可以使用基于主从复制实现的方案，否则建议使用 redlock。

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

在尝试解决上述提到的单点分布式锁方案的一些问题之前，先来看看如何正确地使用单点 redis 来正确地实现分布式锁，因为单点分布式锁对于不时的并发竞争还是可以接受的，而使用一个 redis key 作为一个锁是一个基础，redlock 分布式算法也会使用到这个基础。

我们将使用以下方式来获取锁：

    SET resource_name my_random_value NX PX 30000

这个命令只有在该 key 不存在的时候才会设置该 key（NX 选项），同时会将该 key 的过期时间设置为 30000 毫秒（PX 选项）。这个 key 的值被设置为 “myrandomvalue”。这个值必须在所有客户端以及所有取锁请求中是唯一的。这个随机值是安全解锁的基础，它会被这样一个脚本用来和 redis 交互：当且仅当这个 key 存在并且其值和当前请求的随机值完全一致，则删除该 key。以下是 lua 脚本的实现：

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

这对于避免释放掉其它客户端持有的锁来说是很重要的。举个例子：

• 一个客户端 A 获取了锁，然后被一些操作阻塞直至时间大于锁的有效时间（key 过期时间），然后锁因为过期被移除了
• 此时另外一个客户端 B 获得了锁
• 此时客户端 A 操作完成会进行锁释放

如果客户端 A 直接使用 DEL 删除该锁将会移除掉 B 的锁。使用上述 lua 脚本将会使得每个锁都被使用一个随机值签名了，所以删除锁的客户端只能是获取该锁的那一个。

可以使用 /dev/urandom 获取 20 字节的伪随机数，也可以根据自己的情况使用其它更简易的方式获取一个对于自己来说足够唯一的值。例如一个安全的选择是基于 /dev/urandom 使用 RC4 再进行加密。一个更简单的解决方案是使用 unix 微秒时间戳拼接客户端 ID，可能没有完全安全，但是对于大多数情况可以满足。

key 的 ttl 被称为 “锁的有效时间”。它是锁的自动释放时间，也是取到锁的客户端必须要完成自己的业务操作的时间，否则其它客户端就会取到锁，从而违背了锁互斥的安全保证。

以上的分布式的获取和释放方式对于一个非分布式的、单点的、永远可用的系统（redis）来说来说安全的。下面将对一些概念进行扩展进而讨论如何实现高可用的分布式锁。

Redlock 算法

在分布式版本的算法中假设有 N 个 redis master。这些节点是互相独立的，所以我们不使用从节点或者其它潜在的协调系统。在上面已经讨论了如何在一个实例下安全地取锁和释放锁。在以下例子中将有 5 个 master 节点，这是一个合理的数值，这 5 个 redis master 运行在不同的物理机或者虚拟机上，保证它们任何一个节点（环境）的不可用会影响到其它节点。

客户端通过以下步骤获取锁：

1. 获取当前的毫秒时间戳。
2. 使用相同的 key 和唯一值 value 对 N 个实例按顺序取锁。在此期间，客户端应该使用一个较小于锁自动释放时间的一个时间作为获取锁的动作的超时时。例如如果自动释放锁的时间是 10 秒，则取锁超时时间可以在 5 到 50 毫秒之间。这是为了防止客户端长时间阻塞在一个可能已经挂掉的 redis 节点上：如果一个实例已经不可达，则已经尽快地尝试下一个节点。
3. 客户端从当前时间戳减去步骤 1 的时间戳，计算出取锁花费的总时间。当且仅当客户端在大多数实例（至少 3 个）中获取到了锁，并且总消耗时间少于锁的有效时间，则认为该客户端取到了锁。
4. 如果一个锁被申请到了，它的有效时间就是初始有效时间减去取锁总消耗时间，就像步骤 3 的计算一样。
5. 如果客户端因为某些原因没有获取到锁（无法锁住 N/2+1 个实例或者算得有效时间是负数），它需要对所有实例进行解锁（尽管是它认为它没有锁住的实例）。

¶该算法是否异步的

这个算法的前提是假设各进程之间没有时钟同步（互不影响，非同步），每个进程的时间都以近似相同的速率流逝，允许存在相较于自动释放锁时间要小的偏差。这个假设接近于真实的计算机：所有计算机拥有本地时钟，我们通常依赖于不同的计算机之间拥有一个较小的时钟偏移。

考虑到这一点，已经更严谨地定义 redlock 的互斥性：只要客户端在锁的有效时间（步骤3计算出来的）减去一些时间（为了补偿不同进程间的时钟偏移的几毫秒）之内完成它的业务就可以保证互斥性。

¶失败重试

当一个客户端无法申请到锁的时候，它应该在一个随机的延迟之后进行重试，这是为了将多个客户端在同一时间对一个资源获取锁的动作错开（这是因为如果不错开可能会导致脑裂/因为当某个客户端在当前 redis master 无法获取锁的时候它会尽快从下一个实例获取，如果一直有多个客户端同时在获取同一个 redlock，将可能导致一直没有客户端获取到 N/2+1 个锁）。另外，只要一个客户端在大多数 Redis 实例中获取到锁的时间越短，发生脑裂的窗口也就越小（这也是失败重试所需要的），所以理想情况下客户端应该使用多路复用器（如 linux epoll）在同一时间向 N 个 Redis 实例发送 SET 命令。

客户端需要在不能完全取锁时主动尽快地那些已经锁住的实例，基于此在重新获取该锁的时候就无需等待 key 过期才能获取。（但是如果出现了网络分区然后该客户端无法再与相应的 Redis 实例通信，就需要等待 key 过期）

¶释放锁

释放锁很简单，需要在所有的实例上释放锁，无论客户端是否认为它可以成功锁住某个实例。

¶安全性讨论

假设一个客户端锁住了大多数 redis 实例。所有实例都拥有一个具有相同 ttl 的 key。但是，这个key 是在不同时间被设置的，所以这些 key 会在不同时间过期。假设第一个 key 在时间 T1 （在设置第一个 redis 之前记录的时间戳）被设置，最后一个 key 在时间 T2 （取锁成功最后一个 redis 返回的时间）被设置，所以第一个 key 的最小有效时间 MIN_VALIDITY = TTL - (T2 - T1) - CLOCK_DRIFFT 。所有的其它 keys 都会在之后过期，所以可以确认的是，所有 keys 至少在这一时间到达之前都是被该客户端设置了的。

在大多数（N/2+1） keys 被设置期间，其它客户端就不能设置 N/2+1 个 keys。所以如果一个锁被申请了，就不可能被重复申请（破坏三要素的互斥性）。

下面要确认的是同时尝试获取锁的多个客户端不会同时成功。

如果一个客户端使用了接近于或者大于锁的最大有效时间（我们设置给 key 的 TTL），它将会认为这个锁是无效的然后释放锁，所以我们仅需考虑客户端取锁（N/2+1）时间小于该最大有效时间的情况。 In this case for the argument already expressed above, for MIN_VALIDITY no client should be able to re-acquire the lock. So multiple clients will be able to lock N/2+1 instances at the same time (with “time” being the end of Step 2) only when the time to lock the majority was greater than the TTL time, making the lock invalid.

¶可用性讨论

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

1. 锁的自动释放（基于 keys 的过期）：所有 keys 最终都可以被重新锁住。
2. 客户端会在没有完全获取到锁或者获取到锁但是完成了业务的时候主动释放锁，而无需完全等待锁过期之后才能重新获取该锁。
3. 当一个客户端重试取锁的时候，将会等待一个类似大于取锁所需时间的时间，降低锁竞争期间脑裂的可能性。

另外上面提到如果一个客户端获取锁之后出现了网络分区，其它客户端就需要等待这个 key 的 TTL 之后才能申请到锁。

¶性能、崩溃恢复和 fsync

许多用户使用 Redis 作为一个高性能锁服务器，包括获取/释放锁需要的延迟、获取/释放锁的操作（可能需要一秒）数量。为了满足这一需求，肯定要使用多路复用器（或者"低配版"多路复用器，设置为实例创建的 socket 为非阻塞模式，然后一次性向所有 socket 发送所有命令，稍后再一起读取所有命令/假设客户端和每个实例之间的 RTT 近似的）来和 N 个 Redis 实例进行通信以减少延迟。

但是这里有另外一个需要考虑的点，如果我们想实现一个支持崩溃后恢复的系统，需要做持久化。假设 Redis 配置不做持久化。一个客户端在 5 个实例中的 3 个获取到了锁，然后其中一个锁住的实例发生了重启，此时对于这个锁又有了 3 个实例可以给其它客户端锁住了，破坏了锁互斥的安全性。

如果我们启用 AOF 持久化，将会稍微有所改进。例如在我们需要升级 Redis 的时候对其发送 SHUTDOWN 来重启它。因为 Redis 的过期是严格实现的，所以即使是 Redis 没有启动的时候过期时间也是在虚拟的流逝的（其实就是所有设置过期的方式都转换为给 key 设置一个死亡时间，每次读取 key 的时候都会比较该时间），此时是可以满足需求的。但是仅当 redis 的停止是"干净"的才会满足（redis 启动 AOF 之后会在 shutdown 的时候自动备份），如果是发生停电的情况下就不能满足了，默认情况下，redis 被配置为每秒 fsync 到磁盘，此时发生重启丢失 key 是有可能的。在理论上，如果我们需要在各种原因导致的 crash 下保证锁的安全性，需要启用 fsync=always 。这将会使得性能降低为和 CP 系统（安全的分布式锁的经典实现）一样。

不过这里还有另外一种方案。只要一个 crash 后重启的实例不再参与任何当前活跃的锁的获取就可以保持该算法的安全性，所以当一个实例发生重启后，当前所有活跃的锁都只能通过锁定除了重新加入集群的该实例之外的其它实例来获得。

为了实现上面提到的方案，我们仅需要使得一个 crash 的实例至少在大于所有锁的 key 中最大 TTL 的时间内不可达，这段时间需要用来等待所有在该实例 crash 的时候已经存在的锁的相关 keys 变成无效的并自动释放。

使用 delayed restarts 基本上就可以实现，无需配置 Redis 的任何持久化方案，但是需要注意的是这可能会付出一些可用性的代价。例如如果大多数的实例 crash 了，整个系统都会在 TTL 之内全局不可用（在这段时间内没有资源可以申请锁）

¶使算法更可靠：延长锁时间

如果客户端需要执行的工作由一些小的步骤组成，则默认情况下可以使用更小的时间作为锁的有效时间，然后扩展该算法以实现延长锁的有效时间的机制。当客户端在计算过程中发现锁的有效时间接近于一个很低的值的时候，可以通过发送一个 lua 脚本到所有的实例上延长 keys 的 TTL 来延长锁的时间，前提是锁依然存在并且它的值依然是该客户端之前申请该锁时设置的值。

客户端只有在它可以在大多数实例中都延长了锁的时间、并且在有效时间内的情况下才可以认为该锁被它继续占有（基本上这个算法和正常申请锁的算法很类似）。

However this does not technically change the algorithm, so the maximum number of lock reacquisition attempts should be limited, otherwise one of the liveness properties is violated.