Share:Redis中的分布式锁

概述

在多核处理器中，互斥性访问共享资源的环境下，分布式锁是一项十分有用的手段（技术）]。有很多库和博客都有描述基于Redis如何实现一个分布式锁管理器（DLM：Distributed Lock Manager），但是每个库都使用不同的方案，相比复杂方案，简单方案有较低保障。

本文试图提供一个经典的方法实现基于Redis的分布式锁。我们提出一个算法，称之为 Redlock，它实现一个DLM。我们相信它比普通的单个实例方法更为安全。我们希望，社区分析它并且提供反馈，同时希望基于Redislock实现或者更为复杂或者其他可选的方案。

实现

在描述Redlock算法之前，列举目前基于Redis设计的分布式锁，具体如下：

• Redlock-rb (Ruby 实现)。 有一个 Redlock-rb的fork，它新增gem便于发布或者更多
• 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 实现 with configurable datastore)
• node-redlock (NodeJS 实现)，支持锁的扩展。

安全性和活跃性保证

从我们自己的视角来看，构建我们的设计模型具有三个特性，最低限度地保证高效使用分布式锁。

安全性：互斥性，在任何时刻，仅有一个客户端能否获得锁。
活跃性A：无死锁。不管客户端锁定资源宕或者被分割，最终就可能获得一个锁，
活跃性B:容错性。只要有大多数Redis节点正常工作，客户端就可以获得和释放锁。

为何基于故障转移¹实现不够

让我们分析一下目前基于Redis分布式锁库的工作，以便了解我们所做的改进。

使用Redis锁住资源最为简单的方法是在一个实例中创建一个key。所创建的key通常带有一个过期时间，使用了Redis过期的特性，因此它最终会释放锁（安全性和活跃性保证的第二点）。若客户端需要释放资源，只需要删除此key即可。

粗看起来，此机制很好，但是存在一个问题：在我们的体系架构中是一个单点故障。Redis主节点宕了会发生什么？ 当然，我们可以加入一个从节点！并且在主节点不可用时使用从节点。不幸的是，此方案不可行。这么做会导致我们不能实现互斥安全性，是因为Redis主从复制是异步的。

使用上述的模型存在一个很明显的竞态条件，如下：

1. 客户 A 在主节点获取一个锁；
2. 主节点在客户 A 锁住资源的key没能及时写入到从节点情况下宕了；
3. 从节点被选举为主节点；
4. 客户 B 获得客户A锁住的资源的锁。安全性被破坏！

在特定的场景下，比如在失败的场景下，多个客户端能在同一时刻获得同一个锁，此模型是很好的。如果上述场景符合你的需求，你可以使用基于主从复制解决方案。否则，我们建议实现本文中描述的方案。

单实例正确实现方式

在我们尝试解决上述单实例实现方案缺陷之前，如何在此场景下，如何确保它是正确的。当竞态条件可以接收的时候，此方案是一个可行的方案。另外，在单实例中锁机制是我们在本文中描述分布式算法的基础。为了获得锁，可以使用下面的命令：SET resource_name my_random_value NX PX 30000

此命令会在当key不存在的时候（NX 选项），就会创建一个key，带有一个30000毫秒过期时间（PX 选项）。与key关联的值为“my_random_value”。此值在所有客户端和所有请求锁中，必须是唯一的。使用随机值是为了安全释放锁，使用脚本告诉Redis：只有在key存在并且对应的value值是我们期待的时候才删除它。下面实现此方案的Lua脚本：

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

为了避免误释放其他线程创建的锁是十分重要，比如一个客户端可能获得锁，因某操作所用时间超过锁有效时间（key失效的时间）而阻塞，而另外一个线程在此期间获得锁，然后删除此锁（注：把相同的key删除）。所以，仅仅使用DEL命令是不安全的，会删除其他客户端获得的锁。使用上述脚本，判断每个锁被一个随机的字串串做了标记，所以只有设置此key的客户端才能删除此锁。

随机字符串的值是什么？我假定是来自 /dev/urandom的20字节，不过你也可以使用其他的方式生成一个唯一的值。比如
在/dev/urandom中安全的挑选RC4种子，然后生成一个伪随机流。一个简单地方案：以毫秒为精度的unix系统时间拼接客户端ID，组成一个随机字符串的可以。虽然不完全安全，但在很多场景下是可以使用的。

key有效时间称之为“锁的有效时间”。它既是自动释放锁的时间，同时也是客户端在另外一个客户端再次获得此锁之前的操作时间，然而并没有在技术上确保互斥性，仅仅是给客户端获得锁的一个窗口时间。

到目前为止，由单个一直可用的实例构成的非分布式系统上，我们有一个好的方法获取和释放锁。让我们把此概念扩展到分布式系统中，而在分布式系统中，我们不能确保给出安全性和活跃性的保障。

Redlock算法

算法的分布式版本，我们假定有N个Redis主节点，这些节点完全独立，因此我们不使用复制或者其他隐式协作系统。我们已经描述了单节点下，如何安全地获得和释放锁。同时也保证了单实例中使用此方法获得和释放锁安全性和活跃性。示例中，我们假定N=5,它是一个合理的值。【为啥这么说？】因此，我们在不同机器或者虚拟机上运行5个Redis主节点，以确保他们若是宕了也是完全独立。

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

1. 获得当前时间，以毫秒计；即为currentTimeInMs
2. N个实例使用相同的key和随机值，顺序地尝试获得锁。在此步中，每个实例获取锁时，客户端会用一个超时时间，它比所有锁自动释放的时间小。比如，若自动释放锁时间为10s,那么超时时间在5ms~50ms之间。这样做事为了避免客户端为了等待一个宕机Redis节点，长时间处于阻塞状态：若一个实例不可用，我们会尽快与下一个实例“通话”。
3. 客户端计算获得锁的时间，通过减去步骤1得到的当前时间。即为acqTimeInMS = acqLockCurrentTimeInMS-currentTimeInMs。当且仅当客户端从多个实例获得锁，设为n（n >= N/2+1）;并且总共获得锁的时间为totalAcqTime，如果totalAcqTime小于锁的有效时间(intitValidtyTimeInMS),那么就认为客户端获得了锁。
4. 若锁获得，那么有效时间validtyTimeInMS,可以认为是初始的有效时间减去步骤2中计算获得锁耗费的时间。
5. 如果客户端因某种原因不能获得锁失败（不管客户端不能锁住N/2+1实例还是有效时间为负数），它将释放所有的实例（包括哪些客户端并没有获得锁的实例）。

所有步骤的伪代码如下：

if n < N/2+1 then
    no
end
for i : n then
    acqTimeInMS = acqLockCurrentTimeInMS-currentTimeInMs
    totalAcqTime += acqTimeInMS
end

validtyTimeInMS = intitValidtyTimeInMS - totalAcqTime

if validtyTimeInMS > 0 then
    yes
else
    no
end 

if no then
 unlock all instance

算法是异步的吗？

算法所依赖的假设，一个是进程之间没有同步时钟，每个进程中本地时间按照近似相同频率；另外一个是自动释放时钟存在一点小误差。这些假设近似一台真实地电脑：每台电脑都有本地时钟，同时我们一般依赖不同电脑之间存在一点时钟偏移。

基于此，我们需要制定我们互斥性规则：只要确保客户端所占锁将在锁有效时间（第三步所得）减去一定的时间（为了弥补进程间的是时钟偏移）。

有关相似系统需要一定的时钟偏移更多信息，可以参考此论文：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之后时效，其他key将在MIN_VALIDITY之后失效。因此我们所有的key时效时间至少为MIN_VALIDITY。

在key设置期间，另外一个客户端不能获得锁，是因为N/2+1key已经存在，导致 N/2+1节点操作SET NX命令不会成功。所以，若一个锁已经被占用，那么在同一个时刻是不能被其他客户端占用的。（验证了互斥性）

然而我们也了解，多个客户端在同一时刻试图获取锁，不会相继成功的。若一个客户端锁住大多数实例耗费了相近，甚至比最大有效时间还大（使用SET命令设置的TTL），可以认为锁是失效的，并且会释放所有实例的锁，因此我们仅需要考虑的场景是一个客户端锁住大多数实例所用的时间比TTL小的情况。对于此场景，我们在上面已经计算了MIN_VALIDITY。在MIN_VALIDITY时间内，没有客户端能够重新获得锁。所以，多个客户端会在同一个时刻锁住N/2+1实例，若MIN_VALIDITY大于TLL,则锁是失效的。

你能为此提供一个形式化的证明或者指出现有那些类似的算法或者找出一个不管，我们为此十分感激。

活跃性讨论

系统活跃性基于下面三个主要特性：

1. 锁的自动释放(因为key失效)：keys最终可以重新被锁住。
2. 事实上，客户端会在获得锁失败时溢出锁，或者当锁被占用以及工作结束时，我们也没有必要等待锁失效才重新获取锁。
3. 实际上，当一个客户端需要重新获得锁，它会等待一小段时间，此时间会比获得大多数锁的时间要长，以便减少在资源竞态下发生脑裂问题的概率。

在发生网路分区是，我们加罚一个等于TLL的惩罚时间，所以若是有持续的分区，我们可以让惩罚时无限大。此时，每个客户端移除锁之前，获取锁并且被分区化。

一般情况下，若长时间的网络分区，也会导致系统变得不可用。

性能、宕机恢复、文件同步

很多用户使用Redis作为一个锁服务器，获取锁和释放锁都是高性能，低时延的。同时，也需要在每秒中多次获取、释放锁。为了满足此需求，采用多路复用策略与N个Redis服务器通信以便减少时延（或者假定每个客户端与实例之间的RTT都相近，弱化多路复用以非阻塞的方式发送socket，发送所有的命令以及后面读取所有的命令）。

然而，如果我们想要实现“崩溃-恢复”系统模式，需要考虑另外一个持久化功能。

在此我们来看问题所在，我们假定Redis没有配置持久化，一个客户端从5个实例中获取了3个实例的锁，当其中某一台需要重启之后获得锁，此时还是从3个实例锁住相同的资源，其他客户端若能获得锁，那么将违背锁的互斥性原则。

假如我们设置了AOF持久化，事情就会变得好一点了。比如，我们通过发送 SHUTDOWN 命令和重启一台Redis服务器。因为Redis失效在语义上是实现的，所有当Redis服务停机时，key的有效时间也一直再慢慢流逝，所有的要求都是满足的。然而，只要Redis服务是干净的停下，那么一切都是好的。当断电的情况下又如何呢？若在默认情况下，配置Redis，让其每秒将数据同步到磁盘，那么重启一次服务，key就可能会丢失。理论上，若要不管任何情况下实例重启都保证锁是安全的，我们需要设置持久化模式为： fsync=always。这样的话，相比于同级别的分布式锁系统，性能会受到严重损害。

然而，初看起来事情比看起来要好一些。只要一个实例因崩溃后重启不在参与到任何一个活动的锁，那么当前活动锁集合会被实例锁住的而不是重新加入系统的实例占用，从保证了算法安全性。
为了保证这一点，我们一个实例，在比最大的TLL时间后仍然不可用，其中TLL是所有key有效时间，那么此实例就变得非法并且自动释放所有资源。

在不使用任何Redis持有化，使用延时重启在一般情况下能够实现安全性。但是需要注意的是，会转变为可用而受到惩罚时间。如果很多节点崩溃，系统将在TLL时间内变得全部不可用（全部的意思在TLL内，没有任何资源被锁住）。

让算法更可靠：扩展锁

如果客户端的工作是由一些小步骤组成的，那就可能使用默认的限制时间的小型锁，并实现锁扩展机制的算法。一般来说，如果客户端在计算过程的中途，而锁的有效期抵达了一个较小的值，那么就可能扩展锁机制。通过发送一个Lua脚本，通知所有实例，若key存在且对应的value值仍旧就是客户端获得锁之前的值，就让它们延长对应此Key的TTL值。

客户端仅需要考虑锁的重新获取，若客户端扩展锁可能在短时间内有大量的实例获得此锁。

虽然这并不是从技术的角度改变算法，因此重新获得锁的最大值是要限制的，否则一个活跃性就会遭到破坏。

需要帮助？

如果你对分布式系统有深入的研究，若能提供你的观点或者分析，十分不错的。若能同时使用其他语言实现，也是不错的。在此表示感谢。

Redlock 的分析

1. Martin Kleppmann 分析的文章。我不是很同意他的意见，并且发表了 我对其分析的回应。

参考资料

¹ : https://en.wikipedia.org/wiki/Failover
² : https://en.wikipedia.org/wiki/Split-brain_(computing)