来源: Distributed locks with Redis

在许多情况下，分布式锁是一个很重要的部件，可以让不同的进程以互斥的方式对共享资源进行操作。

本文提供一种基于 Redis 来实现分布式锁的算法，叫做 Redlock。作者认为这种算法比一般的单例 (single instance) 方法安全性更好。

安全性和活跃性保证

分布式锁需要满足的最少条件：

  1. 安全性：互斥。在每个时刻，仅有一个客户端持有锁。
  2. 活跃性 A：无死锁。最终总能获取一个锁，即便锁住相应资源的客户端崩溃了或者被隔离了。
  3. 活跃性 B：容错。只要 Redis 节点的大部分还在运行，则客户端可以获取并释放锁。

为何基于 failover 的实现还不够

最简单的用 Redis 来锁资源的方法是，在一个实例中创建一个键。这个键一般只有有限的生存时间 (利用了 Redis 的过期机制)，因此最终资源会被释放。当客户端要释放资源时，它就删掉这个键。

问题是，这带来了一个单点故障。当 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

上述做法避免了删除由另一个客户端创建的锁。比如，一个客户端有可能获得一个锁，然后在某个操作中花时间太长以至于超过了锁的有效期，然后删除锁，结果删除的锁是由另一个客户端创建的。采用上述脚本避免了这个问题，因为每个锁相当于被“签名”了。

有多种生成随机字符串的方法；不赘述。

键的存活时间也被称为“锁合法时间”。它既是自动释放时间，也是客户端能在别的客户端获取这个锁之前对这个锁进行操作的最长时间。

Redlock 算法

对于算法的分布式版本，我们有 N 个 Redis 主节点。这些节点完全独立，所以我们不使用任何复制或协调机制。对于单例情形，采用之前的算法。对于分布式情形，我们假定 N = 5，也就是说我们需要在不同的电脑上跑 5 个 Redis 主节点。这些主节点会以几乎独立的方式崩溃。

为了获得锁，客户端进行如下操作：

  1. 获得当前时间 (毫秒级)。
  2. 按顺序从 N 个实例获得锁，使用相同的键名和随机数。在这一步，客户端采用一个相对锁的自动释放时间很短的超时时间。比如，如果自动释放时间是 10 秒，超时时间可以是 5-50 毫秒。这避免了客户端长时间试图与一个已经挂掉的 Redis 节点通讯：如果一个实例不可访问，应该尽快与下一个节点通讯。
  3. 客户端将当前时间减去第一步的时间，计算为了获取锁花费了多少时间。当且仅当客户端能从多数实例中获得锁，并且为了获得锁花费的总时间少于锁的合法时间的情况下，才认为锁被获取了。
  4. 如果锁被获取了，其合法时间是初始的合法时间减去第三步计算出的花费时间。
  5. 如果客户端未能获得锁 (可能是因为未能锁住多数，或者合法时间是负数)，它会试图解锁所有的实例 (包括那些未能锁住的)。

这个算法是异步的吗？

这个算法依赖于每个进程的本地时间流逝速度基本一样的假设，尽管进程间不存在同步时钟。

关于互斥原则：持有锁的客户端会在锁的有效期到来之前一点点 (几毫秒) 内中止这个锁。

错误恢复

当一个客户端没能成功获得锁，它会在等待一个随机的时间长度之后重试。客户端应该尽量同时发出 N 个 SET 命令。

客户端在未能获得锁的情况下，也应该释放那些已经部分获得的锁，这样避免了等待锁自然过期的时间。

安全性

活跃性

性能

对锁的扩展

相当于对锁延期

附录 1

Martin Kleppmann 的批评

Redis 适合需要共享某些快速变化、对精确度要求不高、丢失了损失不大的数据的情形，比如可以用来记录每个 IP 地址的访问量，以及每个账户登录所用的不同的 IP 地址。

他认为，对于分布式应用而言，有两种用到锁的情形：

  1. 为了效率：避免重复计算。
  2. 为了正确性：避免状态的混乱。

他认为，如果只是为了效率，则没有必要使用多个 Resis 服务器，只需要单例就够了。他认为上面那篇文章的算法对正确性没有帮助。

用锁来保护资源

分布式系统中如何使用锁？注意，这可与多线程应用中的 mutex 不一样，而是要复杂许多，因为不同的节点和网络可以独立地以不同方式挂掉。一个例子是两个客户端试图写入同一个文件，第一个获得锁，然后准备写的过程中被打断，继续要写入的时候锁已经过期，此时文件已经被第二个客户端获取了。通过在客户端加入对过期时间的检查也没用。还有其它许多可能的出错方式。

解决办法是，在每次写入操作中加入一个 token，这个 token 可以是一个整数，每次获取锁的时候让这个数加一；这需要被操作的服务器主动检查 token。

他建议使用 ZooKeeper。

附录 2

原作者的回应

Hacker news 上的讨论

https://news.ycombinator.com/item?id=11059738