Redis 作者为了解决因为主备切换、脑裂导致 Redis 单集群分布式锁不安全的问题，提出了 redlock 算法，下面是针对 文章 的翻译和一些自我理解。
一、安全性和可用性保证
用三个属性来建模我们的设计方案，在我看来，这是有效使用分布式锁的最小保证：
安全性：互斥性。在任意时刻，只有一个客户端可以持有锁；可用性1：无死锁。即时获取锁的客户端崩溃或者发生网络分区，最终也是可以获取锁资源的；可用性2：容错性。只要大多数 redis 节点在运行，客户端就能获取和释放锁。
二、基于故障转移的实现还不够
为了理解我们想要提升什么，先来分析一下大多数基于 redis 的分布式锁库的现状。
使用 redis 锁住资源最简单的方式是创建一个 key，key 创建通常带有 TTL 时间，因为它最终会被释放（我们列表中可用性1）。当客户端需要主动释放资源时，删除这个 key 即可。
表面上工作很好，但是有个问题：这是我们架构中的一个单点故障。redis master 崩溃会发生什么？ok，加一个副本，master 不可用时使用它。这是不可行的，这不能实现互斥锁的安全性，因为 redis 的复制是异步的。
这个模型存在的竞争条件：
客户端 A 获取 master 的这个锁；master 在把这个 key 发送给副本前崩溃了；副本被提升为了 master；客户端 B 获取了 A 已经锁住的 相同资源的锁。违反了安全性。
有的时候会执行的很好，在特殊的场景下，例如在故障转移期间，多个客户端可以同时锁住相同的资源。在这个 case 中，你可以使用基于复制的方案（如果对业务影响不大），否则我们建议使用本文档中的方案。
三、单个实例的正确实现
在克服上面描述的单个实例的问题之前，让我们检查下在这个简单的例子中 如何正确的运行，对于一些应用来说，有时的竞态条件是可以接受，那这就是可行的方案。因为在单个实例中加锁，是我们描述分布式算法的基础。
为了获取锁，方法如下：
SET resource_name my_random_value NX PX 30000
如果 key 不存在的话（NX 选项），这个命令将设置 key，有 30000 毫秒的过期时间（PX 选项）。key 的值设置为 “my_random_value”，值必须是所有客户端和所有请求中唯一的。
这个随机值是为了以安全的方式来释放 key，通过脚本来告诉 redis：仅当 key 存在并且 key 的存储值是我们希望的。是通过下面的 lua 脚本来实现：
if redis.call("get",KEYS[1]) == ARGV[1] thenreturn redis.call("del",KEYS[1])elsereturn 0end
最重要的是避免移除了其他客户端创建的 key。例如，一个客户端获取了锁，然后执行一些阻塞操作，比锁的有效期长很久（在这时间内，key 会过期），然后客户端删除锁，此时锁已经被其他客户端获取了。仅仅使用 DEL 命令是不安全的，因为一个客户端可能会删除其他客户端的锁。在上面的脚本中，每个锁都有随机字符串进行”签名“，因此只有客户端移除它自己设置的锁时，才会移除该锁。
随机字符串应该是什么样子？我们假定是 20 字节来自于 /dev/urandom，你也可以找到更简单的方法来使它独一无二（适合你的任务）。例如，安全的选择是使用 /dev/urandom 作为 RC4 的种子，并生成一个伪随机流。一个更简单的方案是，使用 UNIX 的毫秒时间戳，并使用客户端id 连接时间戳。虽然没有那么安全，但对于大多数环境足够了。
“lock validity time” 是我们设置 key 的 TTL 时间。这也是自动释放的时间，也是客户端在另一个客户端获取锁之前的 执行操作时间，窗口时间从获取锁的那一个时刻开始计算。
现在我们有了一个很好的方法来获取和释放锁。有了这个系统，可以推理出由单个、总是可用的实例组成的非分布式的系统是安全的。下面扩展这个概念到分布式系统中，那里没有这样的保证。
四、Redlock 算法
在算法的分布式版本中，我们假定有 N 个 redis master 节点，这些节点是完全独立的，因此我们不需要任何副本和隐式的协作系统。在示例中，我们设置 N = 5，这是一个合理的值，我们需要运行 5个 redis master 在不同的物理机或者虚拟机上，确保他们之间是独立的。
为了获取锁，客户端执行下面的操作：
获取当前的毫秒时间戳；按照顺序，尝试在 N 个实例上获取锁，使用相同的 key 和 随机值 在所有的实例中。在步骤2中，在每个实例中设置锁时，客户端请求的超时时间 相比 key 的自动过期时间，应该要小很多； 例如，key 的自动过期时间是 10s，请求超时时间可以是 5~50 ms。避免客户端和挂掉的 redis 节点通信花费过长的时间，如果一个实例不可用了，应该尽快和下一个实例通信。 客户端计算获取锁使用了多长时间，需要使用当前时间 减去 第一步获取的时间。只有客户端获取了大多数实例（至少3个）的锁，并且获取锁花费的时间小于 key 的过期时间，才认为成功获取到锁了；如果获取到锁了，锁的有效时间是初始有效时间 减去 第三步计算的消耗时间；如果客户端因为某些原因，获取锁失败了（比如没有获取到 N/2+1 个实例的锁，或者锁的有效时间是负数），客户端要尝试解锁 所有的实例（包括客户端认为没有上锁成功的实例）。
1、算法是异步的吗
算法有一个依赖：所有的进程中没有时钟同步，每个进程以大致相同的速率更新本地时间，即使有误差，相比 key 的自动明过期时间也是很小的误差。这个依赖设定和现实中的计算机非常像：每个电脑都有本地时钟，我们可以依赖不同的计算机，虽然有很小的时钟漂移。
这上面这一点上，我们需要更好的指定我们的互斥规则：必须保证，客户端在 key 的有效时间（上面第三步计算的），减去一些时间（不同进程之间时钟漂移时间，只有几ms），在这个时间段内完成客户端自己的工作。
本文包含了关于 时钟漂移 的更多信息：/doi/10.1145/74851.74870。
2、失败重试
当客户端没有获取锁时，应该在一个随机延迟后重试，避免多个客户端对同一资源，在同一时刻获取锁（这可能导致脑裂，最终没有客户端成功获取锁，因为每个客户端都锁住了部分节点，没有一个客户端锁住大多数节点）。客户端获取到大多数节点锁的频率越快，集群脑裂的时间窗口就越短。理想情况下，客户端应该在同一时间，使用多路复用技术，同时给 N 个实例发送 set 命令（避免客户端只锁住部分节点）。
需要强调一下，客户端没有在大多数节点上获取锁成功时，需要尽快的释放已经获取的锁，以便不用等这个锁自动过期后 才能继续获取锁（如果网络分区发生，客户端无法和 redis 实例通信，在 key 自动过期前，需要损失系统的可用性）。
3、释放锁
释放锁比较简单，无论客户端是否成功在实例上加锁，都可以执行释放锁的逻辑（在分布式系统中，即使获取锁失败，因为网络问题 可能实例已经加锁成功）。
4、安全论证
这个算法是安全的吗？让我们来检查下不同场景会发生什么。
假定客户端已经在大多数实例上获取到了锁。所有实例中包含的这个 key 有相同的过期时间，然后这个 key 是在不同的时间设置的，因此这个 key 将会在不同的时间过期（多个实例，客户端不可能同时 set key）。在最坏的情况下，在 T1 时间（我们和第一个实例通信之前）设置第一个 key，最后一个 key 在 T2 时间设置（我们从最后一个服务器获取响应的时间）。我们可以确保第一个 key 在过期前，至少存在MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT的时间。所有其他 key 都会在这之后过期，我们可以确保在这个时间点前，这些 key 是同时存在于实例中的。
CLOCK_DRIFT 时钟漂移
为什么系统时钟会存在漂移呢？linux提供了两个系统时间：clock realtime和clock monotonic。
clock realtime 是可以被用户改变的，或者被NTP改变，gettimeofday 取的就是这个时间，redis的过期计算用的也是这个时间；
clock monotonic 是单调时间，不会被用户改变，但是会被NTP改变。
最理想的情况时，所有系统的时钟都和 NTP 服务器保持同步，但这显然是不可能的。导致系统时钟漂移的原因：系统的时钟和 NTP 服务器不同步。
redis 的过期时间是依赖系统时钟的，如果时钟漂移过大时会影响到过期时间的计算。上面 MIN_VALIDITY 的计算还减去了 CLOCK_DRIFT 时间，我的理解是，如果第一个 key 的实例发生了时钟漂移，会导致 key 提前过期，因此 MIN_VALIDITY 时间需要减去这个值。
在大多数 key 存在的时间内，其他客户端是无法获取到锁的，因为 N/2+1 个 key 已经存在了，所以 N/2+1 个 SET NX 操作不会成功。因此一旦获取到了锁，在同一时间不可能再次获取锁。
我们还需要保证多个客户端同时获取锁时不会成功。
如果客户端获取大部分实例锁的时间，接近或者大于 key 的自动过期时间（我们 SET 使用的 TTL 时间），需要考虑这个锁是无效的，并且在所有实例上解锁。所以，我们只需要考虑获取大多数实例锁的时间，远小于锁的有效时间的情况。在这种情况下，上面已经讨论过，在MIN_VALIDITY时间内，没有客户端能再次获取锁。所以多个客户端同时锁住 N/2+1 个示例，只有在 获取锁的时间大于 TTL 的情况下出现，这种情况下锁也是无效的。
4、可用性论证
系统可用性基于下面三个特性：
自动释放锁（key 过期后）：最终 key 可以再次加锁；事实上，客户端没有获取到锁时，或者获取到锁并且工作完成时，客户端会协作移除这些 key，这使得我们不用等 key 自动过期，就可以再次获取锁；事实上，当客户端重试获取锁时，它会等待一段时间，比获取大多数实例锁的时间 会长一些，为了避免在资源竞争期间产生脑裂问题。
然而，在网络分区发生的时候，我们需要付出 TTL 的不可用时间，如果网络分区持续发生，系统会一直不可用。如果客户端获取了锁，但还没有移除锁时发生了网络分区，这种情况就会出现。
基本上，如果系统持续的发生网络分区，系统也会持续的不可用。
5、性能、崩溃恢复和 fsync
需要用户使用 redis 作为分布式锁服务，是为了在获取锁、释放锁都是低延迟，以及每秒高性能的执行获取锁、释放锁。为了满足这个要求，可以通过多路复用和 N 个 redis 服务通信，达到低延迟的目的（socket 设置为非阻塞，发送所有的命令，然后读取所有的命令结果，假定客户端和每个实例之间的 RTT 是近似的）。
为了实现崩溃恢复的系统模型，我们需要考虑持久化的问题。
看下这个问题，假定所有的 redis 没有开启持久化。一个客户端获取了 5 个实例中的 3 个实例的锁，其中一个实例在客户端获取锁后重启，此刻，又有 3 个实例可以锁住相同的资源，其他客户端可以再次锁住资源，违反了互斥锁的安全性。
如果我们打开 AOF 持久化，情况会有很大改善。例如我们发送命令SHUTDOWN来升级并重启服务，因为 redis expire 是语义实现的，服务关闭的情况下时间也会流逝，我们所有的需求此时都满足。但是如果断电呢？redis 的 fsync 配置默认是一秒一次，在重启之后我们的 key 是可能丢失的。理论上，面对任何类型的重启我们想要保证上锁安全的话，我们需要开启fsync=always这个持久化配置项。由于额外的同步开销，这将影响性能。
事情不像第一眼看上去这么糟糕。只要实例崩溃重启后，不再参与任何当前活跃的锁，算法的安全性就可以保证。这意味着，当服务重启后活跃的锁都是通过锁住实例获得的，而不是新加入系统的锁。
为了保证这一点，在服务崩溃后，不可用的时间至少要比最大的 TTL 大一点，这个时间让实例中所有存在锁 key 失效，并自动释放。
使用延迟重启基本可以实现安全性，即使没有任何的持久化策略，然而需要注意，这可能导致可用性缺失。例如，大多数实例崩溃了，系统将会在 TTL 时间内全局不可用（全局不可用意味着，在这个时间内 没有资源可以被锁住）。
6、让算法更可靠：延长锁
如果客户端执行的工作有包含一些小步骤，可以使用较小的 TTL 的锁。针对客户端，如果在计算过程中，锁的有效期即将结束，可以延长锁，通过发送一个 lua 脚本到所有的实例上，来延长 key 的 TTL 时间（如果 key 存在，并且 value 值是客户端获取锁时分配的随机值）。
客户端只有在锁的有效期内，发送延长锁命令在大多数实例都成功时，才是重新获取了锁（算法耗时和获取锁时的耗时接近）。
