-----------------
更新：该算法现已在 Redis 文档中说明，详见 => http://redis.io/topics/distlock。本文保留为旧版，后续更新将直接写入 Redis 文档。
-----------------

很多人用 Redis 来实现分布式锁。不少人认为这是个非常好的应用场景，Redis 很好地解决了一个原本很棘手的问题。也有人认为这完全是错误、不安全的，是对 Redis 的误用。

其实双方都有道理。如果既要求安全性，又要求高可用——即便部分 Redis 节点宕机，客户端仍能获取和释放锁——那么分布式锁并不简单。另一方面，一个快速的锁管理器又能解决大量实践中难以处理的问题，有时一个远非完美但足够快的方案，也比一个非常慢的方案更有价值。

能否基于 Redis 同时做到快速与可靠？本文就是对此的探索。我将尝试描述一种使用 N 个 Redis 实例来实现分布式可靠锁的简单算法，希望社区能帮忙分析与评论，看看它是否是一个可行的方案。

# 我们究竟想要什么？

不先明确想要的安全性和活性就去讨论分布式系统，往往意义不大，因为只有明确了这两类需求，才能判断设计是否正确，他人也才能去分析、发现设计中的缺陷。我们将用三个属性来刻画设计，我认为这是有效使用分布式锁所需的最基本保障。

1) 安全性：互斥。在任意时刻，只有一个客户端能持有一把锁。

2) 活性 A：无死锁。即使持有资源的客户端崩溃或发生网络分区，最终也总能获取到锁。

3) 活性 B：容错。只要大多数 Redis 节点仍然可用，客户端就能获取和释放锁。

# 分布式锁的朴素做法

为了弄清楚我们想改进什么，先来看看现状。

用 Redis 给资源加锁，最简单的做法是在某个实例中创建一个 key。通常会利用 Redis 的过期功能给这个 key 设置一个存活时间，让它最终总能以某种方式被释放（满足我们列表中的第 2 点）。当客户端需要释放资源时，就直接删除这个 key。

表面上看这能很好地工作，但有一个问题：这是架构中的单点故障。如果 Redis 主库宕机了会怎样？
好，给它加一个从库！主库不可用时就用从库。可惜这条路行不通。这样做无法实现我们要求的互斥安全性，因为 Redis 的复制是异步的。

在这种模型下会出现一个明显的竞态条件：

1) 客户端 A 在主库上获取了锁。

2) 主库在把这条写入同步给从库之前就崩溃了。

3) 从库被提升为主库。

4) 客户端 B 对 A 已经持有的同一资源再次获取了锁。 <- 安全性被破坏！

有时，在故障等特殊情况下允许多个客户端同时持有锁是完全可以接受的。
如果是这种情况，就不必再往下看了，基于复制的方案就够用了。否则，请继续往下看一种更安全的实现方式。

# 首先，在单实例上把它做对

在尝试克服上述单实例方案的局限之前，先看看在这种简单情况下如何正确地实现，因为在那些可以偶尔容忍竞态的应用里，这本身就是一个可行的方案，同时单实例加锁也是本文所述分布式算法的基础。

获取锁的正确做法如下：

SET resource_name my_random_value NX PX 30000

这条命令仅在 key 不存在时才会设置（NX 选项），并设置 30000 毫秒的过期时间（PX 选项）。
key 的值设为 “my_random_value”。这个值必须在所有客户端、所有加锁请求之间保持唯一。

之所以需要这个随机值，是为了能安全地释放锁——通过一段脚本告诉 Redis：只有当 key 存在且其值恰好是我期望的值时，才删除它。这通过以下 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 存活时间的这段时间，被称为“锁有效期”。它既是自动释放时间，也是客户端在另一个客户端能够再次获取锁之前完成所需操作的时间窗口，在技术上并未打破互斥保障——该保障仅在加锁时刻起的一段有限时间窗口内有效。

至此，我们已经有了获取和释放锁的可靠方法。如果把系统看作由单个始终可用的实例组成的非分布式系统，那么它是安全的。接下来把这一思路扩展到不具备这种保障的分布式系统。

# 分布式版本

在分布式版本的算法中，我们假定有 N 个 Redis 主节点。这些节点完全独立，我们不使用复制或任何其他隐式协调机制。前面已经说明如何在单个实例上安全地获取和释放锁，这里默认会用同样的方法在单个实例上执行加锁与解锁操作。在示例中我们取 N=5，这是一个比较合理的值，因此需要在不同的机器或虚拟机上运行 5 个 Redis 主节点，以确保它们尽可能独立地发生故障。

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

步骤 1）获取当前时间的毫秒数。

步骤 2）依次尝试在全部 N 个实例上获取锁，在所有实例中使用相同的 key 名和随机值。

在步骤 2 中，每次向实例设置锁时，客户端使用的超时时间要远小于锁的整体自动释放时间。
例如，如果自动释放时间是 10 秒，超时时间可以设在约 5-50 毫秒范围内。
这样可以避免客户端在与宕机的 Redis 节点通信时被长时间阻塞：如果某个实例不可用，应尽快尝试下一个实例。

步骤 3）客户端通过用当前时间减去步骤 1 中获取的时间戳，计算出获取锁所花费的总耗时。
当且仅当客户端在大多数实例（至少 3 个）上成功获取了锁，且总耗时小于锁的有效期时，才认为锁获取成功。

步骤 4）如果锁已获取，则其有效期被视为初始有效期减去步骤 3 中计算出的耗时。

步骤 5）如果客户端由于某种原因未能获取锁（要么是未能在 N/2+1 个实例上加锁，要么是有效期已为负），它将尝试解锁所有实例（即使是那些它认为未能成功加锁的实例）。

# 是同步还是非同步？

本质上，该算法是部分同步的：它依赖于这样一个假设——尽管各进程之间没有同步时钟，但每个进程的本地时间仍以大致相同的速率推进，其误差相对于锁的自动释放时间来说很小。这一假设与真实计算机的情况非常接近：每台计算机都有本地时钟，不同机器之间的时钟漂移通常很小。

此外，我们还需要对互斥规则做更精细的界定：只有当持有锁的客户端能在锁的有效期内（即步骤 3 所得的有效期）减去一小段时间（仅几毫秒，用于补偿进程间的时钟漂移）完成工作时，互斥性才能得到保证。

# 重试

当客户端未能获取锁时，应在随机延迟后重试，以尽量让多个同时尝试对同一资源加锁的客户端去同步化（否则可能出现谁也赢不了的脑裂状况）。同时，客户端越快在大多数 Redis 实例上完成加锁，出现脑裂的时间窗口就越小（也就越不需要重试），因此理想情况下客户端应通过多路复用同时向 N 个实例发送 SET 命令。

需要特别强调的是，未能获取大多数锁的客户端应尽快释放已部分获取的锁，这样就不必等待 key 过期后才能再次获取锁（不过如果发生了网络分区，客户端已无法与 Redis 实例通信，那就只能承受可用性代价，等待过期）。

# 释放锁

释放锁很简单，只需在所有实例上释放即可，无论客户端认为自己是否在某个实例上成功加过锁。

# 安全性论证

这个系统安全吗？我们可以尝试分析不同场景下会发生什么。

首先假设某个客户端已在大多数实例上成功获取了锁。所有实例都会包含一个具有相同存活时间的 key。但由于 key 是在不同时刻设置的，它们也会在不同时刻过期。不过，如果第一个 key 最早在 T1 时刻（联系第一台服务器前采样的时间）设置，最后一个 key 最晚在 T2 时刻（收到最后一台服务器响应时的时间）设置，那么我们可以确定，这一组 key 中最早过期的那个，至少会存在 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 这么久。其他 key 会更晚过期，因此可以确定这些 key 至少会同时存在这么长时间。

在大多数 key 同时存在的这段时间内，另一个客户端将无法获取锁，因为如果已有 N/2+1 个 key 存在，N/2+1 个 SET NX 操作不可能全部成功。所以如果一把锁已被获取，就不可能在同一时间被再次获取（从而违背互斥性）。

但我们还想确保多个客户端同时尝试获取锁时，不会同时成功。

如果某个客户端用接近或超过锁的最大有效期（也就是 SET 时使用的 TTL）的时间才锁住大多数实例，它会认为锁无效并解锁这些实例，因此我们只需考虑客户端在小于有效期的时间内成功锁住大多数实例的情况。在这种情况下，根据上面的论证，在 MIN_VALIDITY 这段时间内不应有任何客户端能重新获取锁。因此，只有当锁住大多数实例所需的时间大于 TTL、导致锁无效时，多个客户端才可能在同一时刻（以步骤 2 结束时为准）各自锁住 N/2+1 个实例。

你能给出形式化的安全性证明，或是发现其中的缺陷吗？非常欢迎。

# 活性论证

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

1) 锁的自动释放（因为 key 会过期）：key 最终会再次变得可被加锁。

2) 客户端通常会在未获取到锁，或已完成工作后主动配合删除锁，这使得我们大概率不必等到 key 过期就能重新获取锁。

3) 当客户端需要重试时，它会等待一段远大于获取大多数锁所需时间的时间，从而在概率上降低资源竞争期间出现脑裂的可能性。

不过，至少存在一种场景：一种非常特殊的网络分区/重连模式若被无限重复，就可能破坏系统的可用性。
例如，当 N=5 时，两个客户端 A 和 B 同时尝试锁定同一资源，谁都无法获取大多数锁，但如果把 A 和 B 的加锁数加起来，却可能覆盖了大多数节点（例如客户端 A 锁住了 2 个实例，客户端 B 锁住了 1 个）。
随后客户端在解锁已锁定实例之前就被分区隔离。这会导致资源在约等于自动释放时间的时长内无法被锁定。等 key 过期后，两个客户端 A 和 B 重新加入分区并重复同样的模式，如此无限循环。

换个角度看上述问题，就是我们在网络分区上付出了等于 “TTL” 时间的可用性代价，因此如果持续出现分区，就可能无限期地付出这一代价。

我暂时想不到能保证活性的简单办法（老实说也没太深入去想），但最坏情况似乎很难被触发。
本质上，这意味着使用该算法，我们只能近似地提供第 2 条属性的保障。

# 性能、崩溃恢复与 fsync

许多将 Redis 用作锁服务的用户对获取和释放锁的延迟，以及每秒可执行的加锁/解锁次数都有很高的性能要求。为了满足这一需求，与 N 台 Redis 服务器通信时降低延迟的策略无疑是多路复用（或简易的多路复用，即将套接字设为非阻塞模式，一次性发送所有命令，稍后再一次性读取所有响应，假设客户端到各实例的往返时延大致相当）。

然而，如果我们想针对崩溃恢复的系统模型，关于持久化还有另一点需要考虑。

为了看清问题所在，假设我们完全没有配置 Redis 持久化。一个客户端在 5 个实例中的 3 个上获取了锁。其中一个已成功加锁的实例重启，此时对于同一资源又有了 3 个可供加锁的实例，另一个客户端就可以再次将其锁住，从而违背锁的排他性安全保障。

如果启用 AOF 持久化，情况会好很多。例如，我们可以通过发送 SHUTDOWN 并重启服务器来升级。由于 Redis 的过期在语义上是虚拟时间——即便服务器关闭期间时间仍在流逝——我们的所有要求都能得到满足。
不过，这一切仅在正常关闭时成立。那断电呢？如果 Redis 按默认配置每秒 fsync 一次，重启后我们的 key 可能会丢失。简言之，如果想在任何形式的实例重启面前都保证锁的安全性，就需要在持久化设置中启用 fsync=always。这又会把性能拉低到与传统上用于安全实现分布式锁的 CP 系统相当的水平。

好消息是，由于在算法中我们并不是一达到多数就停止加锁，实际发生安全性破坏的概率很小，因为大多数时候锁会在全部 5 台服务器上都被持有，所以即便其中一台重启后丢失了 key，真正出现安全性破坏的可能性在实践中很低（但并非不可能）。简言之，这是用户的权衡与取舍。鉴于竞态概率很小，如果可以接受在崩溃恢复后以极小的概率出现多客户端同时持有锁的情况，就可以（也应该）避免每次操作都 fsync。

# 参考实现

我用 Ruby 基于 redis-rb 写了一个简单的参考实现，地址是：http://github.com/antirez/redlock-rb

# 需要帮助？

如果你熟悉分布式系统，非常欢迎你提出看法/分析。
其他语言的参考实现也会很有价值。

提前致谢！

编辑：我在本文评论以及 Hacker News 上收到了一些值得纳入正文的反馈。

1) 如 Steven Benjamin 在下方评论中指出的，如果重启后能让实例在足够长的时间内保持不可用——长到足以让所有使用该实例的锁过期——那么就不需要 fsync。实际上我们完全不需要任何持久化，仅靠纯内存配置就能提供安全性保障。

举例：前面描述的竞态是锁在 5 台中的 3 台上获取，其中一台已加锁的服务器空重启后，另一个客户端可能通过锁住这台服务器以及另外两台未被前一个客户端锁住的服务器来再次获取同一把锁。但如果重启的服务器在足够长的时间内对查询不可用——长到所有经由它获取的锁都已过期——就能保证这种竞态不再可能发生。

2) Hacker News 用户 eurleif 指出，如果客户端发现完成操作耗时过长，可以通过重新获取锁来作为一种策略。这可以通过发送一段脚本来延长 key 的过期时间来实现，前提是 key 的值仍是期望值。只要没有新的分区，且我们提前足够早地尝试延长锁、让 key 不会过期，就能保证锁被成功延长。

3) Hacker News 用户 mjb 指出，用 “skew” 来描述不同时钟推进本地时间的速率差异是不准确的，我实际想说的是 “drift”。我已将 “skew” 替换为 “drift” 以使用正确的术语。

感谢这些非常有价值的反馈。