原文地址：https://redis.io/topics/distlock

在不同进程必须以互斥的方式操作共享资源的环境中，分布式锁是一种非常有用的机制。

有很多代码库和博客描述了如何基于Redis实现DLM（Distributed Lock Manager），但是每个库使用方式都不同，并且很多人使用了比复杂设计实现保证较低的简单方法。

本文旨在提供一种更权威的算法，用于实现基于Redis的分布式锁。我们提供的算法叫做RedLock，实现了一种比vanilla单例方式更安全的DLM。我们希望社区可以分析它并进行反馈。

实现

在描述算法之前，下面有几个可用的实现链接用于参考。

Redlock-rb (Ruby).

Redlock-py (Python)

Aioredlock (Asyncio Python)

Redlock-php (PHP)

PHPRedisMutex (further PHP)

cheprasov/php-redis-lock (PHP)

Redsync.go (Go)

Redisson (Java)

Redis::DistLock (Perl)

Redlock-cpp (C++)

Redlock-cs (C#/.NET)

RedLock.net (C#/.NET)

ScarletLock (C# .NET)

node-redlock (NodeJS)

安全与可用保证

我们用3个属性对设计进行建模，依我看来，这些属性有效使用分布式锁的最小保证：

1. 安全性：互斥。在任一时刻，只有一个客户端可以持有锁。

2. 可用性 A：死锁释放。即使锁定资源的客户端崩溃或者被分区，也可以获取到锁。

3. 可用性 B：容错。只要多数Redis节点启动，客户端就可以获取和释放锁。

为什么基于故障转移的实现还不够

为了理解我们需要提升的内容，我们需要分析基于Redis的分布式锁库的现状。

使用Redis锁定资源的最简单的方式是在实例中创建一个Key。Key的创建通常会有一个存活时间，使用的是Redis的过期的特性，这样可以保证锁始终可以被释放。当客户端需要释放资源时，就删除这个Key。

表面上看，这种方式很有效，但是有一个问题：就是我们架构中的单点故障。如果Redis主机故障会发生什么？好吧，我们增加一个Slave节点。如果Master不可用，我们就使用Slave节点。很遗憾这不可行。这样做无法实现互斥的安全性，因为Redis复制是异步的。

这个方案中有明显的竞争条件：

1. 客户端A在Master中获取锁。

2. Key同步到Slave节点前，主机发生崩溃。

3. Slave被提升到Master。

4. 客户端B获取到客户端A持有的锁。违反安全性

如果发生故障时允许多个客户端同时持有同一个锁，那么就可以使用基于复制的方案。否则，建议使用本文所描述的方案。

基于单个实例的正确实现

在尝试处理单例方案问题之前，我们检查下简单的场景中如何正确实现分布式锁，因为在随时出现竞争状态的应用中，这是一个可行的解决方案，而且对于我们将要描述的分布式算法这个是基础。

要获得锁，可以采用下面的方式：

SET resource_name my_random_value NX PX 30000

只有Key不存在时（NX 选项），这条命令才会设置Key，并且30000毫秒到期（PX 选项）。Key设置为“myrandomvalue”。这个值必须要在所有的客户端以及加锁的请求中保证唯一。使用随机值本质上是为了以安全的方式释放锁，通过脚本告诉Redis：只有Key存在并且Key对应的Value是期望值，才能移除Key。这是通过以下Lua脚本完成的：

if redis.call("get",KEYS[1]) == ARGV[1] then

    return redis.call("del",KEYS[1]);

else 

    return 0;

end

避免移除其他客户端的锁是很重要的。例如客户端A获取到锁以后，锁失效后才执行完成，当客户端释放锁时锁已经被其他的客户端获取。因此客户端只用DEL命令是不安全的，也许会移除其他客户端的锁。相反，使用上述的脚本，每把锁都有一个随机的“签名”，因此，只有设置锁的客户端尝试删除时，这把锁才能被删除。

随机字符串应该是什么呢？我采取的是 /dev/urandom 生成的20个字节，但是你可以找到一种成本更低的方式，确保它在你的任务中是唯一的。例如一个安全的选择是利用RC4算法从/dev/urandom生成一个伪随机流。还有一种简单的方案是使用unix时间戳加上客户端ID，虽然不够安全，但是在大多数环境中可能足够了。

我们用作Key存活的时间，也叫做“锁可用时间”。它既是锁自动释放时间，也是其他客户端抢占锁之前客户端用来执行任务的时间，在技术上不违反互斥的原则，他保证了在获取锁以后限定的时间内保持互斥。

现在我们有了一个获取释放锁的好的方法。由单一、持续可用的实例组成的非分布式系统是安全的。让我们将这一概念扩展到分布式系统，分布式系统没有这么多保证。

Redlock算法

在这个算法的分布式版本中，我们假设有N个Redis节点。这些节点总是相互独立的，因此我们不需要同步或者其他的隐式协调系统。我们描述了在单节点环境中如何安全的获取与释放锁。我们理所当然的认为这个算法在每个节点中使用相同的方式获取和释放锁。在例子中我们set N=5，这是一个比较合适的值，因此我们需要在不同的主机或者虚拟机上运行5个Redis主节点，确保他们故障能够相互隔离。

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

1. 以毫秒为单位获取当前时间。

2. 尝试在所有的N个实例中顺序的获取锁，在所有实例中使用相同的Key和Value。步骤2中，在每个实例中设置锁时，为了获取到锁，客户端需要设置一个小于锁自动释放时间的超时时间。例如如果锁自动释放时间是10s，那么超时时间可以设置成5～50毫秒。避免客户端长时间尝试与宕掉的Redis的节点通信造成阻塞：如果一个实例不可用，我们应该尽快尝试和下一个实例通信。

3. 客户机获取锁花费的时间，是用当前时间减去步骤1获取的时间戳。如果客户端能够在多数实例（至少3个）中获取到锁，获取锁的总时间少于锁的有效时间，就可以认为锁被成功获取

4. 如果锁被获取到，就可以认为锁的实际有效时间就是初始的有效时间减去步骤3计算的时间。

5. 如果客户端因为某些原因获取锁失败（不能在N/2+1个实例中获取锁或者有效时间是负数），那么将会尝试在所有实例中解锁（包括没有成功加锁的实例）

算法是异步的吗？

该算法基于这样一个假设，虽然没有跨进程的同步时钟，但每个进程的本地时钟会以近似相同的速率流动，误差小于锁自动释放的时间。这一假定与现实世界的计算机类似：每个计算机有本地时钟，我们通常信任不同的计算机之间时间差是很小的。

现在，我们需要细化互斥规则：只要获取到锁的客户端能够在时间T内完成它的工作，就能够保证互斥，时间T的计算规则是有效时间（详见步骤3）减去一些时间（一般只有几毫秒，为了补偿不同进程之间的时间差）

想要了解更多关于时间差的类似系统，可以参考这篇有趣的文章：《Leases: an efficient fault-tolerant mechanism for distributed file cache consistency》

失败重试

当客户端不能获取到锁时，应该在随机延时后再次尝试，随机延时是为了避免多个客户端同步的在同一时间获取同一个资源的锁（否则会出现没有客户端能获取到锁的脑裂状态）。客户端在多数Redis实例中获取锁的速度越快，需要重试的时间窗口就越小。因此理想状态下，客户端应该在采用多路复用的模式同时向N个实例中发送Set命令

有必要强调一下，如果客户端获取多数锁失败，应尽快的释放已经获得的锁，这样没必要等到Key超时后再获取锁（然而出现网络分区和客户端无法连接Redis实例的情况，将失去等待锁过期这段时间的可用性）

锁释放

锁释放很简单，无论客户端是否成功的获取到锁，只需要在所有节点释放锁就行。

安全性论证

算法是否是安全的？我们可以试着思考在不同的场景下会发生什么。

开始之前，我们假设客户端可以在多数实例中获取到锁。所有的实例都包含一个有相同存活时间的Key。然而Key是在不同的时间设置的，因此这些key也会在不同的时间失效。我们假设最坏情况下，第一个Key设置的时间是T1（连接到第一个服务的时间），最后一个Key设置时间是T2（最后一个服务应答的时间），我们确定第一个设置了失效时间的Key至少存活的时间为MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT ，TTL是锁超时时间，(T2-T1)是获取锁的耗时，CLOCK_DRIFT不同进程的时间差。其他Key会在这个时间之后失效，因此我们可以确定，所有的Key在这个时间点之前是同时存在的。

在多数Key被设置的时间内，其他客户端无法获取到锁，在N/2+1个Key存在的情况下，N/2+1个 SET NX 命令是不会成功的。因此一个锁被获取，就不能同时重新获取这个锁（违反了互斥原则）

当然我们需要保证多个客户端同时获取锁时不会同时成功。

如果一个客户端锁定多数实例消耗的时间接近或者超过锁最大的有效时间（为SET使用的TTL），那么系统会认为锁失效同时解锁这些实例，因此我们只需要考虑客户端在小于锁有效时间的范围内锁定多个实例的场景。这种情况我们已经在上文进行论证，在MIN_VALIDITY时间范围内，没有客户端能够重新获取锁。因此只有当多数节点获取锁的时间远远大于TTL时，多个客户端才能同时锁定N/2+1个实例。

可靠性论证

系统可靠性是基于三个主要的特性：

1. 锁自动释放（因为Key失效）：最终被锁定的Key可以再次使用

2. 客户端通常在锁获取失败或者工作完成后主动释放锁，我们不需要等待锁过期在重新获得锁

3. 当客户端重试获取锁时，客户端等待时间远远大于获取多数锁的时间，为了降低资源竞争期间脑裂的概率

然而我们在网络分区时需要损失TTL时间的可用性，如果有持续的分区问题，那么就会持续不可用。这种情况会在每次客户端获取锁之后释放锁之前被分区时发生。

基本上，如果有持续的网络分区，系统在这段时间内就会持续不可用。

性能、故障恢复和fsync

很多使用Redis作为锁服务的用户，不仅要求获取释放锁的低延时，也要求高吞吐量，即每秒钟获取释放锁的数量。为了满足这个要求，采用多路复用的策略与N个Redis服务通信以降低延时（或者使用可怜人的多路复用，即socket设置成非阻塞模式，发送所有命令，然后读所有的命令，假设客户端和多个实例之间的RTT是相近的）

然而如果我们想要系统故障自动回复，还需要考虑持久化。我们看下这个问题，假设我们配置Redis不持久化。客户端在3个实例中获取锁，然后一个加锁的实例重启，这时相同的资源有3个实例可以获取到锁，另一个客户端就可以再次对这个资源加锁，违反了锁互斥的安全原则。

如果我们使用AOF持久化，情况会好一些。例如我们可以通过SHUTDOWN和重启升级一个服务。因为Redis失效是语义层面的实现，当服务关闭时时间实际上仍然在流逝，我们的需求都能满足。只要是正常关闭，一切都很好。断电会怎么样呢？如果Redis是默认配置，每秒执行一次fsync，重启后我们的key就有可能丢失。理论上， 如果我们要保证任何实例重启的情况下锁的安全性，我们需要在持久化设置中启用 fsync=always。反过来说，相比与其他同级别的实现安全的分布式锁的CP系统，会损失性能。

然而事情会比第一眼看起来的那样要好，只要实例崩溃后重启，不再参与到当前激活的锁，算法的安全性就能保证。因为实例重启时，当前激活的锁可以被其他实例获取。

为了满足这一条件，我们需要让一个实例在崩溃后，不可用的时间至少要比我们设置的TTL多一点，也就是说，要大于实例崩溃时所有存在的锁失效或者自动释放所需要的时间。

延迟重启基本可以保证安全性，即使没有任务可用的Redis持久化。然而，需要注意的是这也意味着可用性的损失。嫁入多数实例崩溃，TTL时间内系统全局不可用（全局意味着在这个时间内没有资源能够被锁定）

使算法更可靠：扩展锁

如果客户端的工作是由小步骤组成的，那么锁有效时间可以使用更小的默认值，扩展算法以实现锁的延长机制。当锁即将失效时，如果客户端处于计算中，那么可以通过向所有实例发送延长TTL的Lua脚本来延长锁，这个Key必须存在并且和获取锁时客户端分配的随机值一致。如果可以在多数实例中扩展锁并且是在有效期内，那么客户端只需要考虑锁的重新获取。

然而这不是在技术上改变算法，因此锁重新获取的最大次数应该被限制，否则性能会受到影响。

RedLock分析

Martin Kleppmann 对RedLock的分析How to do distributed locking

我不同意这篇评测并且上传了我的回复 Is RedLock Safe?