那篇文章尝试提供更标准的算法来行使Redis实现布

2020-04-11 06:23 来源:未知

分布式锁是一个在很多环境中非常有用的原语,它是不同进程互斥操作共享资源的唯一方法。有很多的开发库和博客描述如何使用Redis实现DLM,但是每个开发库使用不同的方式,而且相比更复杂的设计与实现,很多库使用一些简单低可靠的方式来实现。

在很多场景中,不同的进程必须以排他的方式操作一些共享资源,这时分布式锁就是一个非常有用的原语。

这篇文章尝试提供更标准的算法来使用Redis实现分布式锁。我们提出一种算法,叫做Relock,它实现了我们认为比vanilla单一实例方式更安全的DLM。我们希望社区分析它并提供反馈,以做为更加复杂或替代设计的一个实现。

有很多库和博客都描述了如何使用Redis实现分布式锁管理器(Distributed Lock Manager, DLM),但是每个库的实现方式都不太一样,并且其中很多使用的都是一种简单的方式,但是这降低了可靠性保障,而有的也使用了稍微复杂的设计。

实现

本文尝试提供一种更加典型的算法来实现Redis分布式锁。我们提出了一种被称为Redlock的算法来实现DLM,我们相信它比普通的单实例方式更加安全。我们希望Redis社区可以对它进行分析、提供反馈,并使用它作为更复杂的设计或替代方案的起点。

在说具体算法之前,下面有一些具体的实现可供参考.

实现细节

在开始描述该算法之前,这里有一些已经可用的实现,以供参考。

  • Redlock-rb (Ruby 实现). There is also a fork of Redlock-rb that adds a gem for easy distribution and perhaps more.

  • Redlock-py (Python 实现).

  • Aioredlock (Asyncio Python 实现).

  • Redlock-php (PHP 实现).

  • PHPRedisMutex (further PHP 实现)

  • cheprasov/php-redis-lock (PHP library for locks)

  • 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 实现). 包含了对扩展锁的支持。

Redlock-rb (Ruby实现). Redlock-php (PHP 实现). Redsync.go (Go 实现). Redisson (Java 实现).

安全性和活跃性保证

我们将使用3个特性来开始我们的设计,从我们的观点来看,这3个特性是以一种有效方式实现分布式锁的最低保障。

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

  2. 活跃性A:无死锁。即使持有锁的客户端崩溃了或是被分割,其他客户端最终依然可以获取锁。

  3. 活跃性B:容错性。只要大部分Redis节点是可用的,客户端就可以获取锁和释放锁。

安全和活跃性保证

为什么基于故障恢复的实现还不够

为了理解我们想要改进什么,让我们先来分析一下目前大多数基于Redis的分布式锁的状态。

最简单的使用Redis来锁住资源的方式是在客户端实例里创建一个键。通常创建这个键时会利用Redis的过期特性使之带上存活时间,所以该锁最终一定会被释放。当客户端需要释放锁时,它会删除这个键。

从表面上看上述锁可以工作得很好,但是还是有一个问题:在我们的架构中有单点故障的隐患。如果Redis主机宕机了怎么办?你可能会说,我们可以加上一个从机!当主机宕机了我们就可以使用从机。然而不幸的是这种方式并不可行。因为使用这种方式我们不能保证安全性中的互斥性,因为Redis的复制过程是异步的。

很显然在这个模型中有一个明显的竞争条件:

  1. 客户端A在主机中获取了锁。

  2. 在把键值写入从机之前,主机挂掉了。

  3. 从机变为主机。

  4. 客户端B获取了客户端A对同一资源已经获得的锁。

安全性被违反了!

在特定场景下,上述模型可以运行得很好,例如当主机宕机时,多个客户端同时持有了锁,而你又可以接受这种情况。此时你就可以使用基于复制的解决方案。否则我们建议你使用本文将要介绍的实现方案。

从有效分布式锁的最小保证粒度来说,我们的模型里面只用了3个属性,具体如下:

在单实例场景中的正确实现

在试图克服前文描述的单实例限制之前,我们先来看看在这种简单场景中如何正确地实现分布式锁。实际上偶尔发生竞争条件是可行的解决方案,并且单实例加锁方法也是我们在这里描述的分布式算法的基础。

为了获取锁,我们的实现方式是这样的:

SET resource_name my_random_value NX PX 30000

这个命令只有在该键不存在的时候才会为之赋值,并且带有一个30秒的过期时间。这个键的值将会被设置为"my_random_value",这个值必须在所有的客户端和所有的锁请求中都是唯一的。

基本上这个随机值被用来以安全的方式释放锁,它使用一个脚本来告诉Redis:只有这个键存在且该键上存储的值就是我锁期望的那一个是才可以删除该键。这是通过以下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的种子,然后产生一个伪随机流。一种更加简单的解决方案是使用客户端id与unix的毫秒时间相结合,它并不足够安全,但是可以满足大多数场景的要求。

我们使用的键的存活时间,被称为"锁有效时间"。它既是自动释放锁的时间,也是一个客户端在其它客户端可能重新获取这把锁之前必须完成所要求的操作的截止时间,而在技术上又不违反互斥性,也就是说客户端持有锁的时间被限制在从获取锁那一刻开始的一个指定的时间窗。

现在我们有了一种很好的方式来获取锁和释放锁。这个系统是由一个单一的、一直可用的实例构成的非分布式系统,理论上来说,该系统是安全的。现在,让我们将这个观念扩展至分布式系统,并且这个分布式系统并不能保证是一直可用的。

  1. 属性安全: 互斥行.在任何时候,只有一个客户端可以获得锁.

  2. 活跃属性A: 死锁自由. 即使一个客户端已经拥用了已损坏或已被分割资源的锁,但它也有可能请求其他的锁.

  3. 活跃属性B:容错. 只要大部分Redis节点可用, 客户端就可以获得和释放锁.

Redlock算法

在分布式版本的算法中,我们假设有N台Redis主机。这些节点是完全独立的,所以我们并不需要使用主从复制或者其他隐式的一致性机制。我们已经描述过在单实例系统中如何安全地获取锁和释放锁。我们想当然地认为该算法将采用这种方式在单个实例中获取锁和释放锁。在我们的例子中,我们假设N=5,这是一个合理的假设,所以我们需要5个Redis实例运行在不同的电脑或者虚拟机中,并且确保他们在大多数时候的宕机都是独立的。

为了获取锁,客户端会执行以下操作:

  1. 获取当前时间的毫秒数

  2. 尝试使用相同的键和随机的值依次从所有实例中获取锁。在步骤2中,在每个实例中设置锁时,为了获取锁,客户端会设置一个比锁的自动释放时间要小的超时时间。举个栗子,如果锁的自动释放时间是10秒,那么这个超时时间可以在5~50毫秒之间。这样可以防止在Redis节点宕机的情况下,客户端仍然长时间地持有锁来等待响应。如果一个实例不可用,我们就应该尽快尝试与另外一个实例建立连接。

  3. 客户端会用当前时间减去在步骤1中获取的时间来计算获取锁所消耗的时间。当且仅当客户端在在大多数(至少3个)实例中获取了锁,并且获取锁所消耗的时间小于锁锁有效时间,我们才认为该客户端成功获取了锁。

  4. 如果客户端成功获取了锁,它的真正有效时间就是最开始的有效时间减去在步骤3中计算得到的消耗时间。

  5. 如果由于某些原因,客户端获取锁失败了(无论是因为无法至少在N/2+1个实例中获取锁,还是因为获取锁时间超过了锁有效时间),它将会尝试在所有实例中释放锁(即使它在某个实例中并没有获取锁)。

为何基于容错的实现还不够

这个算法是异步的吗?

这个算法依赖于这样一个假设:即当进程之间没有时钟同步时,每个进程的本地时间都近似以相同的速度流逝,其误差小于锁的自动释放时间。这个假设与现实世界的计算机非常相似:每个电脑都有一个本地时钟,我们可以容忍不同电脑之间有非常微小的时间偏移。

在这一点上,我们需要再次强调我们的互斥规则:只有在客户端完成任务的时间小于锁有效时间(在步骤3中计算得到的时间)减去一些时间(通常是几毫秒,主要是为了补偿不同进程之间的时钟漂移),安全性才能得到保证。

想要了解更多关于需要绑定时钟漂移系统的信息,这篇文章是一个有意思的参考:Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

要理解我们所做的改进,就要先分析下当前基于Redis的分布式锁的做法。

重试机制

当客户端无法获取锁时,它应该在延迟一个随机的时间后进行重试,以使多个客户端得到同步,同时尝试获取同一个资源的锁(这可能导致脑裂的发生,在这种情况下没有赢家)。同样,客户端获取大多数实例锁的时间越短,脑裂出现的概率也就越低(同时需要重试的可能也就越小),所以理想状态是客户端应该同时向N个实例发送SET命令。

有一点值得强调的是:当客户端没能获取大多数锁时,尽快释放已获得的锁是多么的重要。这样一来就没有必要在重新获取锁时需要先等待键过期(然而如果由于网络分区的发生,客户端不再能够与Redis实例进行通信,那么此时就必须等待键过期了。)。

使用Redis锁住资源的最简单的方法是创建一对key-value值。利用Redis的超时机制,key被创建为有一定的生存期,因此它最终会被释放。而当客户端想要释放时,直接删除key就行了。

释放锁

释放锁是很简单的,我们只需要在所有实例中释放锁即可,而不用关心客户端在该实例中是否获得了锁。

一般来说这工作得很好,但有个问题: 这是系统的一个单点。如果Redis主节点挂了呢?当然,我们可以加个子节点,主节点出问题时可以切换过来。不过很可惜,这种方案不可行,因为Redis的主-从复制是异步的,我们无法用其实现互斥的安全特性。

安全性争议

这个算法是安全的码?我们可以尝试去了解一下在不同场景中到底发生了什么。

一开始让我们先假设一个客户端能够获取大多数实例的锁。所有的实例都会包含一个带有相同存活时间的键。然而,不同实例的键是在不同时间设置的,所以所有键也会在不同的时间过期。但是如果第一个键在最糟糕的时间T1(在我们与第一台服务器建立通信之前的时间采样)被设置,而最后一个键也在最糟糕的时间T2(我们从最后一台服务器得到回复的时间)被设置,那么我们可以确定的是第一个过期的键将至少存活MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT这么长的时间。其它的键将会过期得更晚,所以我们可以确定所有的键至少可以存活这么长的时间。

在大多数键的存活时间内,其它客户端将无法获取锁,因为如果N/2+1个键已经存在的话,将没有N/2+1个SETNX命令可以执行成功。所以如果已经获得了锁,同一时刻将无法再次获取锁(如果这样就将违反互斥性)。

然而我们同样想确定当多个客户端尝试在同一时间获取锁时将无法同时成功。

如果一个客户端获取大多数实例锁的时间使用的时间与锁最大有效时间(基本上是使用SET命令是的存活时间)很相近或者甚至更大,那么这把锁会被认为是无效的,并且会释放所有的实例。所以我们只需要考虑客户端获取大多数实例锁消耗的时间比有效时间小的这种场景。在这种情况下,关于前文讨论的争议,在MIN_VALIDITY时间内将没有客户端可以重新获取锁。所以只有在获取大多数实例锁的时间大于TTL时间的情况下,才有可能出现多个客户端可以同时锁住N/2+1个实例,但这种情况下获得的锁也是无效的。

对于现有的类似算法,你能给出正式的安全性证明或者发现bug吗?如果可以,我们将不胜感激。

这明显是该模型的一种竞态条件:

活跃性争议

系统的活跃性建立在下面3个主要的特征之上:

  1. 锁可以自动被释放(因为键会过期):最终键可以被重新获得。

  2. 事实上,当锁没有被获得时,或者锁已经被获取但是工作也已经完成,客户端会主动将锁释放,这样一来我们就不需要等待键过期以便再次获取锁。

  3. 当客户端尝试重新获取锁时,为了是降低在资源争夺期间出现脑裂的概率,它等待的时间会大于需要获取大多数锁的时间。

然而,当出现网络分区不可用时,我们还是会付出等待TTL时间的代价。所以如果网络持续的有问题,我们将一直处于等待状态。每次当客户端获取了锁,但是在它释放锁之前出现网络分区后,这种情况都会发生。

所以如果网络分区一直不可用,那么系统也将一直不可用。

客户端A在主节点获得了一个锁。 主节点挂了,而到从节点的写同步还没完成。 从节点被提升为主节点。 客户端B获得和A相同的锁。注意,锁安全性被破坏了!

性能、崩溃恢复和同步

许多用户将Redis作为需要高性能处理延迟获取锁和释放锁的锁服务器,并且每秒可以处理很多次获取/释放的操作。为了满足这一要求,我们减少与N台Redis服务器通信延时的策略肯定是复用(或者性能较差的复用,即使用非阻塞模式,发送所有命令,然后稍后读取所有命令的回复,假设客户端和每个实例的RTT都是相近的)。

然而,如果目标是建立一个崩溃恢复的系统模型,还需要考虑的一点是持久化。

让我们来看一下这个问题,假设我们配置Redis时完全没有考虑持久化。一个客户端在5个实例中获取了3个的锁,而在客户端获取到锁的实例中有一个重启了,这时又有3个实例可供我们对统一资源再次获取锁,另外一个客户端就可以重新锁住它,而这就违反了互斥性。

如果我们开启了AOF持久化选项,情况就会有所好转。举个栗子,我们可以通过发送SHUTDOWN命令来重启或升级一台服务器。因为Redis的过期命令是从语义上实现的,所以即使服务器关机了,时间依然在流逝,我们所有的要求都是满足的。虽然只要它是一个干净的关闭,所有事情都是ok的,那么如果是停电呢?默认情况下,Redis被配置为每秒执行一次fsync,这样在重启后我们的键就可能会丢失。理论上,如果我们想确保在任意类型的实例重启时锁的安全性,我们就需要在持久化配置中开启fsync=always选项。而这将会完全破坏用来以安全方式实现分布式锁的CP系统的性能。

然而事情往往比第一眼看到的情况要好一些。基本上算法的安全性是可以得到保证的,只要一个实例在崩溃重启后不再参与到任何当前活动的锁,所以当实例重启时,当前活动的锁依然可以通过锁住该实例来保持,而不会有新的锁重新加入系统

为了使这一点得到保证,我们只需要使实例在发生崩溃后不可用的时间比我们的最大TTL略长一点点即可,在这个时间内,当实例崩溃时,所有已经被锁住的键都变得不可用,并且会被自动释放

使用延迟重启可以在没有任何Redis持久化机制的条件下保证安全性,然而需要注意到的是,这可能会导致系统不可用。例如当大多数实例都崩溃后,整个系统将在TTL时间内完全不可用(这里完全意味着在这段时间内将没有资源可以被锁住)。

有时候,在某些情况下这反而工作得很好,例如在出错时,多个客户端可以获得同一个锁。如果这正好是你想要的,那就可以使用主-从复制的方案。否则,我们建议使用这篇文章中描述的方法。

使算法更加可靠:锁的扩展

如果客户端的工作由很多小步骤组成,那么默认情况下就有可能使用更小的锁有效时间,并实现一个扩展锁机制来扩展该算法。如果客户端正在进行计算而锁有效时间所剩无几,这时可以通过向所有实例发送一个Lua脚本来延长TTL从而扩展锁,如果锁的键依然存在并且键值与刚开始获取锁时分配的随机值相等的话。

只有可以在有效时间内在大多数实例上扩展锁成功的条件下,客户端扩展锁才算成功(基本上该算法和获取锁的算法非常相似)。

然而这从技术上并没有改变该算法,所以在扩展锁的过程中必须对最大尝试此书进行限制,否则就会违反其中一条活跃性。

单实例的正确实现方案

需要帮助?

如果你对分布式系统很感兴趣,那么你的意见/分析将非常重要。其他语言的分布式锁实现算法同样非常重要。

提前感谢各位!

在尝试解决上文描述的单实例方案的缺陷之前,先让我们确保针对这种简单的情况,怎么做才是无误的,因为这种方案对某些程序而言也是可以接受的,而且这也是我们即将描述的分布式方案的基础。

Redlock分析

Martin Kleppmann在这篇文章(http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html)中分析了Redlock,但是我并不赞同他的观点,我的回复在这里(http://antirez.com/news/101)。

2017-09-11

原文链接:https://redis.io/topics/distlock

为了获取锁,方法是这样的:复制代码 代码如下:SET resource_name my_random_value NX PX 30000

这条指令将设置key的值,仅当其不存在时生效(NX选项), 且设置其生存期为30000毫秒(PX选项)。和key关联的value值是"my_random_value"。这个值在所有客户端和所有加锁请求中是必须是唯一的。

使用随机值主要是为了能够安全地释放锁,这要同时结合这么个处理逻辑:删除key值当且仅当其已存在并且其value值是我们所期待的。看看以下lua代码:复制代码 代码如下:if redis.call("get",KEYS[1]) == ARGV[1] then return redis.call("del",KEYS[1])else return 0end

这么做很重要,可以避免误删其他客户端创建的锁。例如某个客户端获得了一个锁,但它的处理时长超过了锁的有效时长,之后它删除了这个锁,而此时这个锁可能又被其他客户端给获得了。仅仅做删除是不够安全的,很可能会把其他客户端的锁给删了。结合上面的代码,每个锁都有个唯一的随机值,因此仅当这个值依旧是客户端所设置的值时,才会去删除它。

那么应该怎样生成这个随机值呢?我们使用的是从/dev/urandom读取的20个字节,但你也可以找个更简单的方法,只要能满足任务就行。例如,可以使用/dev/urandom初始化RC4算法,然后用其产生随机数流。更简单的方法是组合unix时间戳和客户端ID, 这并不安全,但对很多环境而言也够用了。

我们所说的key的时间,是指”锁的有效时长“. 它代表两种情况,一种是指锁的自动释放时长,另一种是指在另一个客户端获取锁之前某个客户端占用这个锁的时长,这被限制在从锁获取后开始的一段时间窗口内。

现在我们已经有好的办法获取和释放锁了。在单实例非分布式系统中,只要保证节点没挂掉,这个方法就是安全的。那么让我们把这个概念扩展到分布式的系统中吧,那里可没有这种保证。

Redlock 算法

在此算法的分布式版本中,我们假设有N个Redis主节点。这些节点是相互独立的,因此我们不使用复制或其他隐式同步机制。我们已经描述过在单实例情况下如何安全地获取锁。我们也指出此算法将使用这种方法从单实例获取和释放锁。在以下示例中,我们设置N=5,这样我们需要在不同物理机或虚拟机上运行5个Redis主节点,以确保它们的出错是尽可能独立的。

为了获取锁,客户端执行以下操作:

获取当前时间,以毫秒为单位。 以串行的方式尝试从所有的N个实例中获取锁,使用的是相同的key值和相同的随机value值。在从每个实例获取锁时,客户端会设置一个连接超时,其时长相比锁的自动释放时间要短得多。例如,若锁的自动释放时间是10秒,那么连接超时大概设在5到50毫秒之间。这可以避免当Redis节点挂掉时,会长时间堵住客户端:如果某个节点没及时响应,就应该尽快转到下个节点。 客户端计算获取所有锁耗费的时长,方法是使用当前时间减去步骤1中的时间戳。当且仅当客户端能从多数节点中获得锁,并且耗费的时长小于锁的有效期时,可认为锁已经获得了。 如果锁获得了,它的最终有效时长将重新计算为其原时长减去步骤3中获取锁耗费的时长。 如果锁获取失败了,客户端会对所有实例进行解锁操作。

算法是异步的

算法依赖于这样一个假定,它在处理的时候不是同步时钟的,每个处理中仍然使用的是本地的时间,它只是大致地以同样地速率运行,这样它就会有一个小的错误,与之相比会有一个小的自动开合的时钟时间。这个假设很像真正世界的电脑:每一台电脑有一个本地时钟,通常我们使用不同的电脑会有一个很小的时钟差。

TAG标签:
版权声明:本文由www.129028.com-澳门金沙唯一官网www129028com发布于编程新闻,转载请注明出处:那篇文章尝试提供更标准的算法来行使Redis实现布