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

许多人使用 Redis 来实现分布式锁(Distributed Lock)。许多人认为这是一个绝佳的使用场景，Redis 出色地解决了一个原本很难解决的问题。另一些人则认为这完全是错的，不安全，是 Redis 的错误用法。

基本上，双方都是对的。如果我们希望分布式锁既安全，同时又要求高可用性——即 Redis 节点可以宕机而客户端仍然能够获取和释放锁——那么分布式锁并非易事。与此同时，一个快速的锁管理器可以解决大量在实践中难以解决的问题，有时一个远非完美的方案也比一个非常慢的方案更好。

我们能基于 Redis 同时获得快速和可靠的系统吗？这篇博客文章就是对该领域的探索。我将尝试描述一个简单算法的提案，使用 N 个 Redis 实例来实现分布式且可靠的锁，希望社区能帮助我分析和评论这个算法，看看它是否是一个合格的候选方案。

# 我们真正想要的是什么？

在讨论分布式系统时，如果不说明我们想要的安全性和活性(liveness)属性，基本上是无意义的，因为只有明确了这两项要求，才有可能检验一个设计是否正确，也才能让人们分析并找出设计中的缺陷。我们将只用三个属性来建模我们的设计，我认为这是有效使用分布式锁所需的最低保证。

1）安全属性：互斥(Mutual Exclusion)。在任何时刻，只有一个客户端能够持有锁。

2）活性属性 A：无死锁。最终总是可以获取到锁，即使持有某个资源锁的客户端崩溃或被网络分区隔离。

3）活性属性 B：容错性。只要大多数 Redis 节点存活，客户端就能够获取和释放锁。

# 分布式锁，朴素的做法。

为了理解我们想要改进什么，让我们分析一下现状。

使用 Redis 锁定资源的简单方法是在一个实例中创建一个键。这个键通常通过 Redis 的过期功能设置一个有限的生命周期，这样它最终总会以某种方式被释放（即我们列表中的属性 2）。当客户端需要释放资源时，它删除这个键。

表面上这工作得很好，但有一个问题：这是架构中的单点故障。如果 Redis 主节点宕机了会怎样？

好吧，那就加一个从节点！在主节点不可用时使用它。遗憾的是，这并不可行。这样做我们无法实现互斥这一安全属性，因为 Redis 的复制是异步的。

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

1）客户端 A 在主节点上获取了锁。

2）主节点在写入该键的命令被传输到从节点之前崩溃了。

3）从节点被提升为主节点。

4）客户端 B 对客户端 A 已经持有锁的同一资源获取了锁。<- 违反了安全性！

有时，在特殊情况下——比如故障期间——多个客户端同时持有锁是完全可接受的。
如果是这种情况，就不用往下读了，尽情享受你基于复制的方案吧。否则，请继续阅读，了解一个有望更安全的实现方式。

# 首先，让我们在单个实例上正确地实现它。

在尝试克服上述单实例方案的局限性之前，让我们先看看在这个简单场景中如何正确实现，因为对于偶尔出现竞态条件可以接受的应用来说，这实际上是一个可行的方案，而且单实例加锁也是我们将在下文描述的分布式算法的基础。

要获取锁，正确的方式如下：

SET resource_name my_random_value NX PX 30000

该命令只有在键不存在时才会设置它（NX 选项），并设置 30000 毫秒的过期时间（PX 选项）。
键的值被设置为 “my_random_value”。这个值必须在所有客户端和所有锁请求中都是唯一的。

基本上，这个随机值是为了安全地释放锁：通过一个脚本告诉 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，这不如前者安全，但在大多数环境中可能已经足够胜任。

我们用作键生存期的时间被称为“锁有效时间”(lock validity time)。它既是自动释放的时间，也是客户端在另一个客户端能够再次获取锁之前完成所需操作的时间——严格来说这并不违反互斥保证，因为互斥保证仅限于从锁被获取时刻起的一个给定时间窗口内。

现在我们有了获取和释放锁的良好方式。对于一个由单个实例组成、始终可用的非分布式系统而言，这个系统是安全的。让我们把这个概念扩展到不具备这种保证的分布式系统中。

# 分布式版本

在算法的分布式版本中，我们假设有 N 个 Redis 主节点。这些节点完全独立，因此我们不使用复制或任何其他隐式的协调机制。我们已经描述了如何在单个实例上安全地获取和释放锁。我们默认该算法会使用这个方法在单个实例上获取和释放锁。在我们的示例中我们设 N=5，这是一个合理的值，因此我们需要在不同计算机或虚拟机上运行 5 个 Redis 主节点，以确保它们以基本独立的方式发生故障。

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

第 1 步）它获取当前时间，以毫秒为单位。

第 2 步）它按顺序尝试在所有 N 个实例中获取锁，在所有实例中使用相同的键名和相同的随机值。

在第 2 步中，在每个实例上设置锁时，客户端使用一个相对于锁总自动释放时间而言较小的超时时间。
例如，如果自动释放时间是 10 秒，超时时间可以在 ~ 5-50 毫秒的范围内。
这样可以防止客户端在尝试与一个已宕机的 Redis 节点通信时被长时间阻塞：如果某个实例不可用，我们应该尽快转向下一个实例。

第 3 步）客户端通过用当前时间减去第 1 步获得的时间戳，计算获取锁所耗费的时间。
当且仅当客户端能够在大多数实例中（至少 3 个）获取到锁，且获取锁所耗费的总时间小于锁有效时间时，才认为锁已被获取。

第 4 步）如果锁被获取了，其有效时间被认为是初始有效时间减去第 3 步计算出的耗时。

第 5 步）如果客户端由于某种原因未能获取锁（要么无法锁定 N/2+1 个实例，要么有效时间为负），它将尝试解锁所有实例（即使是它认为自己未能锁定的实例）。

# 同步还是非同步？

基本上，该算法是部分同步的：它依赖于这样一个假设——虽然各进程之间没有同步的时钟，但每个进程的本地时间仍以大致相同的速率流逝，其误差相对于锁的自动释放时间来说很小。这个假设非常接近真实的计算机：每台计算机都有一个本地时钟，我们通常可以信赖不同计算机之间的时钟漂移(clock drift)是很小的。

此外，我们需要细化互斥规则：只有当持有锁的客户端在锁有效时间（如第 3 步所获得的时间）减去一定时间（只需几毫秒，用于补偿进程间的时钟漂移）之内完成其工作时，互斥才得到保证。

# 重试

当客户端无法获取锁时，它应该在随机延迟后重试，以使多个同时尝试获取同一资源锁的客户端相互错开（否则可能导致脑裂(split brain)状态，即无人获胜）。此外，客户端越快在大多数 Redis 实例中尝试获取锁，出现脑裂状态（以及需要重试）的时间窗口就越小，因此理想情况下，客户端应该使用多路复用同时向 N 个实例发送 SET 命令。

值得强调的是，未能获取大多数锁的客户端必须尽快释放（部分）已获取的锁，这样就无需等待键过期才能重新获取锁（不过，如果发生网络分区且客户端不再能与 Redis 实例通信，则必须付出可用性代价并等待过期）。

# 释放锁

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

# 安全性论证

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

首先，假设一个客户端能够在大多数实例中获取锁。所有实例都将包含一个具有相同生存期的键。然而，这些键是在不同时刻设置的，因此它们也会在不同时刻过期。不过，如果第一个键最坏情况下在时刻 T1 被设置（即我们联系第一台服务器之前采样的时间），而最后一个键最坏情况下在时刻 T2 被设置（即我们获得最后一台服务器回复的时间），我们可以确定这组键中最先过期的那个键至少会存在 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 的时间。所有其他键都会更晚过期，因此我们可以确定这些键至少会在这段时间内同时处于已设置状态。

在大多数键处于已设置状态的时间内，另一个客户端无法获取锁，因为如果已有 N/2+1 个键存在，就不可能有 N/2+1 个 SET NX 操作成功。所以，如果一个锁已被获取，就不可能在同一时刻被重新获取（否则就违反了互斥属性）。

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

如果一个客户端用了接近或超过锁最大有效时间（基本上就是我们用于 SET 的 TTL）的时间锁定了大多数实例，它会认为该锁无效并解锁这些实例，因此我们只需考虑客户端在小于有效时间的时间内锁定大多数实例的情况。在这种情况下，基于上面已经给出的论证，在 MIN_VALIDITY 时间内不应有任何客户端能够重新获取锁。因此，多个客户端能够同时锁定 N/2+1 个实例（这里的“时间”指第 2 步结束的时刻），只有当锁定大多数实例所耗费的时间大于 TTL 时才会发生，而这会使锁无效。

你能给出一个安全性的形式化证明，或者找出一个缺陷吗？那将非常受欢迎。

# 活性论证

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

1）锁的自动释放（因为键会过期）：键最终会重新变得可被锁定。

2）客户端通常会在未能获取锁、或已获取锁且工作完成时配合地删除锁，这使得我们很可能无需等待键过期即可重新获取锁。

3）当客户端需要重试获取锁时，它会等待一段远长于获取大多数锁所需的时间，从而在概率上使资源争用期间的脑裂状态不太可能发生。

然而，至少存在一种场景，即某种非常特殊的网络分区/重新加入模式无限重复，可能会破坏系统的可用性。
例如，当 N=5 时，两个客户端 A 和 B 可能同时尝试锁定同一资源，谁都无法获取大多数锁，但如果我们把 A 和 B 的锁加起来，它们可能合计锁定了大多数节点（例如客户端 A 锁定了 2 个实例，客户端 B 只锁定了 1 个实例）。
然后，客户端在能够解锁这些已锁定的实例之前被网络分区隔离。这会导致该资源在约等于自动释放时间的时间内无法被锁定。当键过期后，客户端 A 和 B 重新加入分区，重复同样的模式，如此无限循环。

看待上述问题的另一个角度是：在网络分区发生时，我们要付出等于“TTL”时间的可用性代价，因此如果分区持续发生，我们可以无限期地付出这个代价。

我找不到一种简单的方法来保证活性（不过老实说我也没怎么努力尝试），但最坏的情况似乎很难触发。
基本上，这意味着使用该算法我们只能提供对属性 2 的近似保证。

# 性能、崩溃恢复与 fsync

许多使用 Redis 作为锁服务器的用户需要在两方面获得高性能：获取和释放锁的延迟，以及每秒可执行的获取/释放操作的次数。为了满足这一要求，与 N 个 Redis 服务器通信以降低延迟的策略无疑是多路复用（或者穷人的多路复用，也就是把套接字设为非阻塞模式，先发送所有命令，之后再读取所有回复，前提是客户端与每个实例之间的 RTT 大致相似）。

不过，如果我们以崩溃恢复(crash-recovery)系统模型为目标，关于持久化还有另一个需要考虑的问题。

为了看清这里的问题，让我们假设我们把 Redis 配置为完全不做持久化。一个客户端在 5 个实例中的 3 个上获取了锁。其中客户端获取了锁的一个实例重启了，此时对于同一资源又有 3 个实例可以被锁定，另一个客户端就可以再次锁定它，从而违反了锁排他性的安全属性。

如果我们启用 AOF 持久化，情况会好很多。例如，我们可以通过发送 SHUTDOWN 并重启来升级一台服务器。由于 Redis 过期的语义实现使得即使服务器关机，时间实际上仍在流逝，我们的所有要求都能得到满足。

然而，一切都好，只要这是正常关机。那么断电呢？如果 Redis 按默认配置每秒向磁盘 fsync 一次，那么重启后我们的键有可能丢失。长话短说，如果我们想在任何类型的实例重启面前保证锁的安全性，就需要在持久化设置中启用 fsync=always。而这又会彻底毁掉性能，使其降到传统上用于安全实现分布式锁的 CP 系统的水平。

好消息是，由于在我们的算法中，一旦达到大多数服务器我们并不会停止获取其余锁，实际发生安全性违规的概率很小，因为大多数时候锁会同时持有在全部 5 台服务器上，所以即使其中一台在丢失某个键的情况下重启，实际发生安全性违规在实践上是不太可能的（但并非不可能）。长话短说，这是一个由用户做出的选择，也是一个重大权衡。鉴于竞态条件的概率很小，如果可以接受在崩溃恢复事件之后以极小的概率出现多个客户端同时获取锁的情况，那么每次操作都 fsync 是可以（而且应该）避免的。

# 参考实现

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

# 想帮忙吗？

如果你对分布式系统很在行，能听到你的意见/分析就太好了。

其他语言的参考实现也会很棒。

先谢过了！

编辑：我从这篇博客文章的评论以及 Hacker News 上收到了一些值得纳入本文的反馈。

1）正如 Steven Benjamin（史蒂文·本杰明）在下方评论中指出的，如果重启一个实例后，我们可以让它足够长的时间不可用，使所有使用该实例的锁都过期，那么我们就不需要 fsync。实际上我们根本不需要任何持久化，这样我们的安全保证就可以用纯内存配置来提供。

举个例子：前面我们描述过这样一个竞态条件的例子——锁在 5 台服务器中的 3 台上被获取，其中一台获取了锁的服务器空着重启了：另一个客户端可以通过锁定这台服务器和前一个客户端未锁定的另外两台来获取同一把锁。然而，如果重启的服务器保持足够长的不可查询时间，使所有通过它获取的锁都过期，我们就能保证这种竞态不再可能发生。

2）Hacker News 用户 eurleif 指出，如果客户端发现自己完成操作耗时过长，可以将重新获取锁作为一种策略。这只需扩展现有的锁即可：发送一个脚本，只有当键中存储的值是期望值时才延长其过期时间。如果没有新的分区发生，并且我们提前足够长的时间尝试延长锁，使键不会过期，那么锁就能保证被延长。

3）Hacker News 用户 mjb 指出，“skew”一词并不适合描述不同时钟递增本地时间的速率差异，我实际上想说的是“Drift”。我已将 “skew” 一词替换为 “drift”，以使用正确的术语。

感谢这些非常有用的反馈。