使用Redis实现分布式锁

译文,原文链接
分布式锁是一种非常有功的工具来帮助我们处理多进程环境下不同进程必须独占式的操作共享资源的需求。
已经有非常多的库与博客文章分别实现与描述了如何使用Redi实现一个分布式锁管理工具(DLM),但是这些库与文章使用了不同的实现方式,很多实现方式有着较低的可靠性,其他的实现方式又较为复杂。
本文章将试着提供一种使用Redis实现分布式锁的更为通用的算法。我们提出名为红锁(RedLock)的算法,我们认为该算法将会比使用单一Redis实例实现的算法更为安全。我们希望Redis社区可以分析该算法,提供试用反馈,并且将其作为更复杂或其他实现的起点。

实现

在我们介绍算法前,现在已经有一些实现可以作为参考了。

安全性与可用性保证

我们将会使用三个属性来对我们的设计做定性,在我们看来,这三个属性是分布式锁所需的最基本的属性。

  1. 安全性:互斥。在任意时间,只有一个客户端可以持有一个锁。
  2. 可用性A:无死锁。最终所有客户端都有机会获得锁,即使目前已经获得锁的客户端宕机或者发生了网络分区。
  3. 可用性B:容错性。只要大部分的Redis节点在运行,客户端就可以获取与释放锁。

为什么只有故障转移的实现是不够的

为了理解我们需要提升什么,我们先分析一下当前大部分使用Redis实现的分布式锁的库的现状。
使用Redis实现锁的最简单的方式是在一个Redis实例中创建一个key。这个key通常会附带有一个存活时间,通过Redis的过期策略实现,因此锁最终会被释放(上面提到的属性2)。当需要释放资源时,客户端会删除掉这个key。
表面上看这个算法可以很好的工作,但是仍然是有这么一个问题:在系统架构中存在一个单点gu故障问题。如果Redis主节点宕机会发生什么?好吧,我们可以加一个从节点!并且当主节点宕机时使用该节点。但不幸的是,这并不可行。使用这种方式(注:即主从切换)我们无法保证互斥的这一安全性条件,因为Redis的主从复制是异步操作。
这里有一个非常明显的竟态条件在这种模型中:

  1. 客户端A在主节点上获取到锁
  2. 主节点宕机,宕机前没有将key传输到从节点上
  3. 从节点提升为主节点
  4. 客户端B获取到了客户端A已经持有的同一把锁。违反了安全性!

在某些特殊情况下,比如系统故障时,多个客户端同时持有一把锁是可以被接受的。如果是这种情况,完全可以使用主从复制的解决方案来实现分布式锁。否则,我们建议使用在本文中介绍的解决方案。

正确使用单实例实现分布式锁

在我们试着解决上面提到的单实例实现方式的局限性前,我们先探讨一下在这种简单的场景下,如何正确的实现分布式锁,因为这是一种在竟态条件可以被接受的条件下实际可行的分布式锁的实现方式,并且,在单实例中的加锁方法是我们接下来要讨论的分布式锁算法的基础。
我们使用如下方式获取一个锁:

 SET resource_name my_random_value NX PX 30000

这个命令只会在key不存在的时候(NX选项)才会设置key,并且将key的过期时间设置为30000毫秒(PX选项)。这个key的值被设置为”myrandomvalue”。这个值必须在所有申请这个锁的客户端中保持唯一。
这个随机值是用来安全的释放掉锁的,我们会使用一个脚本通知Redis:只有当key存在,并且key对应的值与我期望的值相同时才删除掉这个key。下面的Lua脚本实现了这个方式:

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

使用这种方式是为了避免删除掉其他客户端获取到的锁。例如,一个客户端获取到了锁,然后在接下来的操作中使用了超过锁可用时间(可用时间过后key会自动过期)的时间,然后删除掉了已经被其他客户端获取到的锁。仅仅使用DEL命令会误删除别的客户端获取到的锁,因此是不安全的。通过使用上面的脚本以及使用一个随机串对锁进行“签名”,可以保证锁只会被持有该锁的客户端释放。
如何生成随机串呢?我们认为从/dev/urandom中获取20个字节就可以了,你也可以针对你的任务使用其他更为轻量的生成方式。例如使用/dev/urandom作为种子的RC4算法产生一个伪随机流。一个更简单的方式是使用微秒级的unix系统时间组合客户端ID来生成一个随机串,这并不能认为是安全的,但是大部分场景下这已经足够使用。
我们将key的存活时间称为锁可用时间(lock validity time)。这个时间既是锁的自动释放时间,又是获得锁的客户端在另一个客户端在不违反互斥性保证的前提下可以获得锁之前的可操作时间区间,这个时间受限于从获取锁的瞬间开始的一段时间窗口。
所以我们有一种很好的获取与释放锁的方法了。如果我们假设Redis单实例永远可用,那么这个非分布式系统可以认为是安全的。但是我们无法保证上面的假设,因此我们将会扩展一下该系统。

RedLock 算法

分布式环境下,我们假设有N个Redis实例。这些实例之间互相完全独立,我们不会使用主从备份或者其他隐含的协调系统。我们已经介绍了如何安全的在一个实例上获取与释放锁。我们在RedLock算法中也会使用这种方式从一个实例上获取与释放锁。我们假设有5台Redis实例,这个数字是比较合理的数字,因此我们需要5台独立的计算机或者虚拟机来启动这5台Redis实例,来模拟他们独立宕机的场景。
客户端需要进行如下的步骤来获取一个锁:

  1. 客户端获取当前时间的毫秒数
  2. 客户端尝试使用相同的key与随机串从全部N个Redis实例顺序的获取锁。当尝试从每一个Redis实例中获取锁时,客户端将会设置一个尝试超时时间,这个时间将会远小于锁的自动释放时间。例如,如果申请一个10秒后自动释放的锁,那么尝试超时时间将会设置在5~50毫秒之间。这将会方式一个客户端在尝试连接一个已经宕机的Redis实例耗时过长:当一个实例无法访问,我们应该马上去尝试访问下一个实例。
  3. 客户端通过计算当前时间与第一步获取的时间间隔来计算获取锁这一步骤使用了多长时间。当且仅当客户端在大部分实例上成功获取到了锁(本例中最少为3台Redis实例),并且获取锁的时间小于锁可用时间(lock validity time),我们才认为客户端成功获取到了锁。
  4. 如果锁被成功获取,那么这个锁的可用时间为初始的锁可用时间间去第三步中的尝试加锁的流逝时间。
  5. 如果客户端因为某种原因没有成功获取到锁(无论是因为没有成功从N/2+1个实例中获取到锁还是因为剩余的锁可用时间小于0),客户端均会尝试去所有Redis实例中释放锁(即使客户端在该实例上没有能够获得锁)。

这个算法是异步算法吗?

本算法基于这样一个假设:虽然不同服务间,没有一个同步的时钟,但是每个服务的本地时钟均按相同的频率前进,并且之间相差的时间相对于锁的自动释放时间来说可以忽略不计。这个假设接近于实际的计算机:每台计算机内部均有一个本地时钟,并且我们可以认为不同计算机之间的时钟偏差非常小。
基于这一点,我们需要再次强调我们的互斥性规则:只有持有锁的客户端可以在锁可用时间(第三步中的到的时间)减去一小段时间(几毫秒的时间,用以抵消不同系统之间的时钟漂移导致的时间差异)内结束自己的工作,锁的互斥性才会得到保障。
想要了解更多的关于时钟漂移的信息,可以参考这篇论文Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

失败重试

当一个客户端无法成功获取到锁时,客户端需要等待一小段随机时间后再进行尝试获取锁,这是因为防止多个客户端在同一时间尝试获取同一把锁(这可能会导致没有客户端能获取到锁的脑裂情况的发生)。另外如果客户端更快的尝试获取锁,那么将会缩短发生脑裂(以及需要再次重试)的时间窗口,因此理想情况下,客户端应该并行的向N个Redis实例发送SET命令。
需要强调的一点是,当客户端没有成功获取到锁时,客户端应该马上释放掉自己在所有Redis节点中获取到的(部分)锁,因此其他客户端无需等待这些节点上的锁过期释放后才可以再次申请锁(然而如果发生了网络分区,客户端无法与Redis实例通讯的话,我们仍然需要等待自动过期机制过期掉相关的锁)。

锁的释放

锁的释放非常简单,只需要申请释放掉所有Redis实例上的锁即可,而不管客户端是否在这个实例上是否加锁成功。

安全争议

这个算法是否安全?我们可以通过了解在不同场景下将会发生什么来得到答案。
让我们从假设一个客户端已经成功获得了绝大多数的锁开始。所有的Redis实例会保存一个相同存活时间(time to live)的key。然而,这个key是在不同时间下设置的,因此key会在不同的时间点过期。假设T1为客户端设置第一个key的起始时间(客户端在发送请求到第一个Redis实例前的时间点),T2为客户端收到最后一个Redis实例返回值的时间,我们可以认为第一个Redis实例中的key将会至少存活MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT时间。所有其他的实例将会在稍后过期掉这个key,因此我们可以确定客户端最少会持有这个锁MIN_VALIDITY时间。
在一个客户端在大部分Redis实例已经加锁的时间段内,其他客户端无法成功获取锁,这是因为至少N / 2 + 1个Redis实例中已经存在锁。同时当一个客户端已经申请到了锁,这个客户端无法同一时间再次申请这把锁(违反了互斥性)(译注:无可重入性)。
然而我们同时希望多个客户端同时申请同一把锁时,不能多个都成功。
如果客户端获取大部分实例锁所花费的时间接近或者超过了锁的最大可用时间(使用SET命令中的参数TTL),客户端会认为锁已经失效了,并且会释放掉这个锁。因此,我们仅需要关注客户端获取锁的时间小于锁可用时间这样一种场景。在这种场景中,我们已经解释了在MIN_VALIDITY这个时间段内,不会有客户端能够获取到锁。因此只有一种情况会出现多个客户端同时获取到锁,那就是获取锁的时间超过了锁的存活时间,这样取得的锁也是无效的。
如果你能提供关于现有的类似算法的一个正式证明(指出正确性),或者是发现这个算法的bug? 我们将非常感激.

可用性争论

本系统的可用性依赖于如下三个主要特性:

  1. 锁的自动释放(因为key过期了):最终锁可以被再次获取。
  2. 客户端会在锁没有被获取到或者锁被使用完后,配合删除掉锁,使得后面等待锁的客户端无需等待锁自动过期就能及时的获取到锁。
  3. 当客户端需要重新尝试获取锁时,客户端会等待一段时间,这段时间会远大于获取锁所需要的时间,以最大限度的降低脑裂情况的发生。

然而,当网络分区时,系统将会在TTL时间段内无法工作,因此如果有持续的网络分区的发生,系统将无法在有限的时间内恢复工作。这会发生在每当客户端获取到了锁并且在删除锁之前就产生网络分区。
因此,如果网络分区持续,本算法可能会持续的无法正常工作。

性能, 故障恢复 与 fsync

许多用户为了更低的获取与释放锁的响应时间、更高的每秒钟可以有多少此获取/释放锁的操作而使用Redis作为锁服务。为了满足这种需求,我们需要同时请求N个Redis服务器来降低延迟。
然而如果我们希望系统能够在崩溃中恢复,我们需要考虑数据的持久化。
我们假设这样一种情况,我们完全没有设置Redis的持久化。一个客户端在5个Redis实例中的3个实例下获取到了锁。这3个实例中的一个发生了重启,在这种情况下,系统中又有了3个实例可以获取同一把锁,此时另一个客户端就可以获取到锁,这违反了我们系统的互斥性。
如果我们开启了AOF持久化,情况会好转一点。例如,我们可以通过向一个Redis实例发送SHUTDOWN指令并重启该实例来升级它。因为Redis的过期是语义实现,所以当Redis服务关闭时,时间仍然在流逝,因此我们的需求是可以满足的。然而只有当服务是优雅关闭的前提下,系统才不会受到影响。系统断电会发生什么?如果Redis是使用默认配置,即每一秒钟使用fsync写盘的话,我们可能会在系统重启时丢失锁信息。理论上,如果我们希望无论是什么情况下的系统重启,我们都需要保证所得安全性的话,我们需要设置将持久化设置fsync=always。这将会让系统性能降低到其他类似的保证CP的系统同一水平。
然而实际情况会比一开始想象的情况要好。当一个节点宕机重启后,只要它不参与到任意当前活动的锁中去时,系统的安全性会得到保证。
为了保证这种安全性,我们只需要让宕机的实例,在超过TTL的时间后再启动即可,这段时间内将会把所有的系统宕机前已存在的锁释放掉。使用延迟启动(delayed restarts)可以让我们在不使用Redis持久化的前提下满足安全性要求,然而这里需要注意的是,这可能导致系统进入无法正常提供锁服务的状态。例如,如果大部分实例宕机,系统将会在最少TTL时间段内完全(这里完全的意思是这段时间没有任何资源能够被锁定)无法提供服务。

锁续期,将本算法变得更为可靠

如果客户端的工作可以拆分成很多小的步骤,那么可以默认使用一个很短的锁可用时间,并且通过实现锁续期的机制来对锁的租约时间进行延长。例如客户端在工作进行中发现锁将会很快到期,那么可以通过一个Lua脚本来对锁进行续期操作,这个Lua脚本将会发送到全部的Redis实例中,让锁的有效期延长一段时间,前提是客户端在实例中仍然持有这把锁。
客户端在续期时,需要判断自己持有锁数量是否仍然超过半数,以及这些锁仍然在可用时间内(续期算法与获取锁算法非常相似)。
这在技术上没有修改这个算法,因此不能无限次数的对锁进行续期操作,因为这会导致可用性属性遭到破坏。

想要参与?

如果你深入了解分布式系统,我们非常欢迎你提出你的观点/分析。使用其他语言实现本算法将会非常宝贵。
提前感谢大家!

针对RedLock的分析

  1. Martin Kleppmann 针对 Redlock 的分析文章. 我针对该文章的反驳