Redis 分布式锁

分布式锁：在不同进程执行占用同一个资源时，同一时刻只能占有一个资源。Redis 提供一个叫 “Redlock” 的算法来实现分布式锁。

安全和活性保证

在设计建模之处，就建立三个属性来最小保障了高效使用的分布式锁：

  1. 属性安全：彼此互斥。在任何时刻，只有一个客户端能占有锁。
  2. 活性属性 A：无死锁。无论怎么样，最终都能获取一个锁，哪怕是这个客户端在占有锁之后宕机了。
  3. 活性属性 B：容错性。只要 Redis 主节点还在工作，客户端就能占有以及释放锁。

为什么基于故障切换的实现还不够

为了理解我们想要实现提高的，我们先来分析一下目前的大多数基于 redis 分布式锁库的状态。

使用 redis 最简单的方式就是创建一个 key 来占有资源。这个 key 通常在创建的时候是有过期时间的，所以它们最终会到期而释放锁（在上述列表中的第二点）。当客户端需要释放锁的时候就会删除它。

这看着好像执行的非常的好，但是这里实际会存在一个问题：在我们的架构中这是一个单点故障。如果 Redis 主节点挂掉了怎么办？ok，那让我们加从节点！并且在主节点不可用的情况下使用从节点。很明显这做不到，因为它并不可用。因此我们不能实现彼此互斥的安全属性，因为 Redis 备份是异步的。

在这个模式下有个很明显的竟态条件：

  1. 客户端 A 在主节点下获取锁
  2. 主节点在将 key 传输至从节点之前崩溃了
  3. 此时从节点升为主节点
  4. 客户端 B 获取锁来占用客户端 A 已经占用过的资源。这不安全

有时在特殊情况下是没问题的，像在故障期间，多客户端能在相同时间占有锁。如果这种情况下，你可以是用基于复制的解决方案。否则我们要实现我们现在要介绍的分布式锁。

单节点的正确实现

在尝试克服上述单实例设置的限制之前，先让我们来分析在这种简单的例子如何正确做，因为这实际上是一个可行的解决方案，在应用程序中，有时竞争条件是可以接受的，并且因为锁定单个实例是我们将在这里介绍分布式算法的一个基础。

为了获取锁，我们可以这样：

SET resource_name my_random_value NX PX 30000

这个命令只有在 key 不存在的时候设置，设置了 30000 毫秒的有效期。对应的值为 “myrandomvalue”。这个值在所有客户端以及所有锁请求都是唯一的。基于这个随机值，是为了能够安全的释放锁，使用一个脚本告诉 Redis：只有这个 key 存在时就会移除 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，这种方法不那么安全，但在大多数环境中可能适合这项任务。

我们用时间作为生存的关键时间，被称为 “锁有效时间”。它们都能自动释放，以及客户端拥有这个时间执行操作之前，其它客户端也会再次获取锁，这没有违反互斥技术保证,这是一个给定的有限时间的时刻加了锁。

所以我们现在有一个耗得方式来占有锁和释放锁。对于由一个始终可用的实例组成的非分布式系统进行推理的系统是安全的。那让我们拓展这个概念到分布式系统中去，那些地方我们得不到保证。

Redlock 算法

在分布式系统版本中，我假设有 N 个 Redis 主节点。这些节点始终都是互相独立得，所以我们不需要备份或者在系统之间任何的显示交互。我们之前已经描述了如何在单节点下安全的获取锁以及释放锁。在单个 Redis 实例中，我们会允许这个算法使用这个方法来获取和释放锁。在我们的例子里，我们设置 N=5，这是一个有理由的值，所以我们要在不同的主机或虚拟机中运行 5 个 Redis 主节点，来确保它们会以各自独立的方式失败。

为了获取锁，客户端需要执行下面操作：

  1. 获取当前的毫秒级时间
  2. 尝试在所有的 N 实例频繁获取锁，使用相同的 key 和随机值。在第 2 步期间，当在每个实例中设置锁时，客户端为了获取锁使用一个超时时间要比自动释放时间要小。例如一个自动释放时间为 10 秒，那么超时时间可以在 5-50 毫秒的范围。这能防止客户端在尝试与下游的 Redis 节点通话时长时间阻塞：如果一个实例不可用，我们应该尝试与下一个实例 ASAP 通话。
  3. 客户端会计算获取一个锁需要多少时间，通过当前时间减去第 1 步获取的时间得知。如果这个客户端能够在大多数节点（至少 3 个节点）中获取锁，那么获取锁的总时间要少于锁有效时间的，那么此时锁时可以被获取的。
  4. 如果锁被占用了，它的有效时间就会被认为是初始时间减去经过的时间，就像第 3 步计算的那样的。
  5. 如果客户端因为一些原因（要么不能锁定 N/2+1 个实例，要么有效时间为负）获取锁失败了，它将会尝试解锁所有的实例（甚至这些实例还被认为不能够锁）

算法是异步的么？

算法依赖于假设：这里的这些进程不存在同步时钟。每个进程中的本地时间仍然以大致相同的速度流动，其误差与锁的自动释放时间相比很小。这个假设接近一个真实世界计算机：每个计算机有一个本地始终，毕竟我们经常依赖于不同的计算机来实现一个很小的始终漂移（clock drift）。

关于这点我们要指出我们的互斥规则：只有当持有锁的客户端在锁有效时间内终止工作(如步骤3中所获得的)，减去一些时间(为了补偿进程之间的时钟漂移，只需几毫秒)，它才会得到保证。

更多关于需要固定时钟漂移的类似系统的信息详见：租期：一种有效的分布式文件缓存一致性容错机制

失败重试

当一个客户端无法持久锁时，为了让多个试图同时获取同一资源锁的客户端去同步（这可能的结果是大脑分裂，没人会赢），它会以随机的延时来重试。而且在大多数实例中，客户端尝试获取锁的速度越快，分割大脑的窗口就越小(需要重试)，所以理论上客户端应该尝试使用多播在相同时刻发送 SET 命令到 N 个实例。

值得强调的是，对于无法获得大部分锁的客户端来说，尽快释放(部分)获得的锁是非常重要的，所以这里不存在需要等待 key 过期来再次持有这个锁（然而如果发生了网络分区以及客户端不能在与 Redis 实例通话了，就会有一个可用性惩罚，因为它等待密钥过期）。

释放锁

释放锁很简单，只是涉及在所有 Redis 实例释放锁，不管客户端是否认为它能够成功锁定给定实例。

安全参数

这个算法安全么？我们可以在不同的场景中来尝试理解这里面发生了什么。

首先我们来从一个客户端能够在这些实例中的大多数实例中持有锁的假设开始。所有实例中将会包含一个相同时间的 key。但是这个 key 在不同的时间点赋值，所以这些 key 也将会在不同的时间点失效。但如果第一个 key 设置的最坏时间是 T1（我们在联系第一个服务器之前进行采样的时间）和最后一个 key设置的最坏时间点为 T2（我们获得最后一个服务器回复的时间），我们要确保第一个 key 的过期时间设置在至少 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。其它所有键将会过期，所以我们要确保至少在这次将同时设置所有的 key。

在大多数这些 key 被设置的期间，其它客户端是无法持有锁的，因为 N/2+1 SET NX 的操作是不会成功，因为 N/2+1 节点的 key 此时还不存在。所以如果这个锁被持有，那么它是不可能在同一时刻去重新持有锁的（这违反了互斥）。

然而我们也想确保多个客户端在刻尝试持有锁不能在相同时刻索取一个锁。

如果客户端锁定大多数实例的时间接近或大于锁定的最大有效时间(TTL 基本上是我们在 SET 使用的)，它会认为锁失效并且会在这个实例上解锁，所以我们只需要认为在这个例子中，在某一个小于有效时间的时刻，一个客户端时能够锁大多数实例。在这种情况下，对于上面已经讨论的参数，对于 MIN_VALIDITY，没有客户端应该能够重新获得锁。所以只有当锁定大多数实例的时间大于 TTL 时间时，多个客户端才能同时锁定 N/2+1 个实例(“time”是第 2 步的最后时间)，从而使锁定无效。

你能提供一个安全的正式证据么，指出已存在的相似算法，找出 bug？那会感激不尽

活性（Liveness）参数

系统活性是基于下面三个特性：

  1. 锁的自动释放（因为 key 过期）：最终这些 key 都是可用的并再次被锁。
  2. 事实上客户端通常会在锁没有被持有时删除这个锁，或者当持有锁并被网络中断时，能够让我们不在等待这些 key 过去并重新持有锁。
  3. 当客户端需要重新持有锁时，它会等待一个时间，这个时间要比去持有大多数锁的时间长，为了在资源争用期间不太可能出现大脑分裂的情况。

但是，我们花费的可用性惩罚等于网络分区上的 TTL 时间，因此，如果这里存在连续的分区，我们能无限花费这个惩罚。每当客户端获得一个锁并在能够删除锁之前被分区时，都会发生这种情况。

基本上如果这里有无限连续的网络分区，系统在无限长的时间里就会变得不可用。

性能，崩溃-恢复和 fsync

fsync：数据脉冲，把文件在内存中的部分写回磁盘。