精华内容
下载资源
问答
  • Redis RedLock 完美的分布式锁么? P...
    itemprop="mainEntityOfPage" href="https://xilidou.com/2017/10/29/Redis-RedLock-%E5%AE%8C%E7%BE%8E%E7%9A%84%E5%88%86%E5%B8%83%E5%BC%8F%E9%94%81%E4%B9%88%EF%BC%9F/">

    Redis RedLock 完美的分布式锁么?

    上周花了点时间研究了 Redis 的作者提的 RedLock 的算法来实现一个分布式锁,文章地址。在官方的文档最下面发现了这样一句话。

    Analysis of RedLock

    Martin Kleppmann analyzed Redlock here. I disagree with the analysis and posted my reply to his analysis here.

    突然觉得事情好像没有那么简单,就点进去看了看。仔细读了读文章,发现了一个不得了的世界。于是静下心来研究了 Martin 对 RedLock 的批评,还有 RedLock 作者 antirez 的反击。

    Martin 的批评

    Martin上来就问,我们要锁来干啥呢?两个原因:

    1. 提升效率,用锁来保证一个任务没有必要被执行两次。比如(很昂贵的计算)
    2. 保证正确,使用锁来保证任务按照正常的步骤执行,防止两个节点同时操作一份数据,造成文件冲突,数据丢失。

    对于第一种原因,我们对锁是有一定宽容度的,就算发生了两个节点同时工作,对系统的影响也仅仅是多付出了一些计算的成本,没什么额外的影响。这个时候 使用单点的 Redis 就能很好的解决问题,没有必要使用RedLock,维护那么多的Redis实例,提升系统的维护成本。

    对于第二种原因,对正确性严格要求的场景(比如订单,或者消费),就算使用了 RedLock 算法仍然不能保证锁的正确性。

    我们分析一下 RedLock 的有啥缺陷吧:
    unsafe-lock

    作者 Martin 给出这张图,首先我们上一讲说过,RedLock中,为了防止死锁,锁是具有过期时间的。这个过期时间被 Martin 抓住了小辫子。

    • 如果 Client 1 在持有锁的时候,发生了一次很长时间的 FGC 超过了锁的过期时间。锁就被释放了。
    • 这个时候 Client 2 又获得了一把锁,提交数据。
    • 这个时候 Client 1 从 FGC 中苏醒过来了,又一次提交数据。

    这还了得,数据就发生了错误。RedLock 只是保证了锁的高可用性,并没有保证锁的正确性。

    这个时候也许你会说,如果 Client 1 在提交任务之前去查询一下锁的持有者是不自己就能解决这个问题?
    答案是否定的,FGC 会发生在任何时候,如果 FGC 发生在查询之后,一样会有如上讨论的问题。

    那换一个没有 GC 的编程语言?
    答案还是否定的, FGC 只是造成系统停顿的原因之一,IO或者网络的堵塞或波动都可能造成系统停顿。

    文章读到这里,我都绝望了,还好 Martin给出了一个解决的方案:

    fencing-tokens

    为锁增加一个 token-fencing。

    • 获取锁的时候,还需要获取一个递增的token,在上图中 Client 1 还获得了一个 token=33的 fencing。
    • 发生了上文的 FGC 问题后,Client 获取了 token=34 的锁。
    • 在提交数据的时候,需要判断token的大小,如果token 小于 上一次提交的 token 数据就会被拒绝。

    我们其实可以理解这个 token-fencing 就是一个乐观锁,或者一个 CAS。

    Martin 还指出了,RedLock 是一个严重依赖系统时钟的分布式系统。

    还是这个过期时间的小辫子。如果某个 Redis Master的系统时间发生了错误,造成了它持有的锁提前过期被释放。

    • Client 1 从 A、B、C、D、E五个节点中,获取了 A、B、C三个节点获取到锁,我们认为他持有了锁
    • 这个时候,由于 B 的系统时间比别的系统走得快,B就会先于其他两个节点优先释放锁。
    • Clinet 2 可以从 B、D、E三个节点获取到锁。在整个分布式系统就造成 两个 Client 同时持有锁了。

    这个时候 Martin 又提出了一个相当重要的关于分布式系统的设计要点:

    好的分布式系统应当是异步的,且不能时间作为安全保障的。因为在分布式系统中有会程序暂停,网络延迟,系统时间错误,这些因数都不能影响分布式系统的安全性,只能影响系统的活性(liveness property)。换句话说,就是在极端情况下,分布式系统顶多在有限的时间内不能给出结果,但是不能给出错误的结果

    所以总结一下 Martin 对 RedLock 的批评:

    • 对于提升效率的场景下,RedLock 太重。
    • 对于对正确性要求极高的场景下,RedLock 并不能保证正确性。

    这个时候感觉醍醐灌顶,简直写的太好了。

    RedLock 的作者,同时也Redis 的作者对 Martin的文章也做了回应,条理也是相当的清楚。

    antirez 的回应

    antirez 看到了 Martin 的文章以后,就写了一篇文章回应。剧情会不会反转呢?

    antirez 总结了 Martin 对 RedLock的指控:

    1. 分布式的锁具有一个自动释放的功能。锁的互斥性,只在过期时间之内有效,锁过期释放以后就会造成多个Client 持有锁。
    2. RedLock 整个系统是建立在,一个在实际系统无法保证的系统模型上的。在这个例子中就是系统假设时间是同步且可信的。

    对于第一个问题:
    antirez 洋洋洒洒的写了很多,仔细看半天,也没有解决我心中的疑问。回顾一下RedLock 获取锁的步骤:

    1. 获取开始时间
    2. 去各个节点获取锁
    3. 再次获取时间。
    4. 计算获取锁的时间,检查获取锁的时间是否小于获取锁的时间。
    5. 持有锁,该干啥干啥去

    如果,程序在1-3步之间发生了阻塞,RedLock可以感知到锁已经过期,没有问题。
    如果,程序在第 4 步之后发生了阻塞?怎么办???
    答案是,其他具有自动释放锁的分布式锁都没办解决这个问题

    对于第二个指控:
    antirez 认为,首先在实际的系统中,从两个方面来看:

    1. 系统暂停,网络延迟。
    2. 系统的时间发生阶跃。

    对于第一个问题。上文已经提到了,RedLock做了一些微小的工作,但是没办法完全避免。其他带有自动释放的分布式锁也没有办法。

    第二个问题,Martin认为系统时间的阶跃主要来自两个方面:

    1. 人为修改。
    2. 从NTP服务收到了一个跳跃时时钟更新。

    对于人为修改,能说啥呢?人要搞破坏没办法避免。
    NTP受到一个阶跃时钟更新,对于这个问题,需要通过运维来保证。需要将阶跃的时间更新到服务器的时候,应当采取小步快跑的方式。多次修改,每次更新时间尽量小。****

    说个题外话,读到这里我突然理解了运维同学的邮件:
    Screenshot 2017-10-29 3.43.22

    所以严格来说确实, RedLock建立在了 Time 是可信的模型上,理论上 Time 也是发生错误,但是在现实中,良好的运维和工程一些机制是可以最大限度的保证 Time 可信。

    最后, antirez 还打出了一个暴击,既然 Martin 提出的系统使用 fecting token 保证数据的顺序处理。还需要 RedLock,或者别的分布式锁 干啥??

    回顾

    看完二人的博客来往,感觉就是看武侠戏里面的高手过招,相当得爽快。二人思路清晰,Martin 上来就看到RedLock的死穴,一顿猛打,antirez见招拆招成功化解。
    至于二人谁对谁错?
    我觉得,每一个系统设计都有自己的侧重或者局限。工程也不是完美的。在现实中工程中不存在完美的解决方案。我们应当深入了解其中的原理,了解解决方案的优缺点。明白选用方案的局限性。是否可以接受方案的局限带来的后果。
    架构本来就是一门平衡的艺术。

    最后

    Martin 推荐使用ZooKeeper 实现分布事务锁。Zookeeper 和 Redis的锁有什么区别? Zookeeper解决了Redis没有解决的问题了么?且听下回分解。

    参考

    1. Distributed locks with Redis
    2. How to do distributed locking
    3. Is Redlock safe?
    4. 基于Redis的分布式锁到底安全吗(上)?
    展开全文
  • Redlock-Hyperf composer require zonghay/redlock-hyperf 基于转换为 本sdk基于redlock-php向hyperf〜2.1版本改造。 使用前建议先了解一下Redlock算法的原理, 使用 try { $ lock = $ this -> container -> get ...
  • Redis RedLock分析反驳

    2020-04-29 18:22:56
    作为本书研究的一部分,我在Redis网站上遇到了一种称为Redlock的算法。该算法声称在Redis的顶部实现容错的分布式锁(或更确切地说,租约[1]),并且该页面要求来自分布式系统人员的反馈。该算法本能地触发了我的脑海...

    如何做分布式锁定

    Martin Kleppmann于2016年2月8日发布。

    作为本书研究的一部分,我在Redis网站上 遇到了一种称为Redlock的算法。该算法声称 在Redis的顶部实现容错的分布式锁(或更确切地说, 租约 [1]),并且该页面要求来自分布式系统人员的反馈。该算法本能地触发了我的脑海,因此我花了一些时间思考并编写这些注释。

    由于Redlock已经有10多个独立的实现,而且我们不知道谁已经在依赖此算法,因此我认为值得公开分享我的笔记。我不会讨论Redis的其他方面,其中一些已经在其他地方受到了批评 。

    在详细介绍Redlock之前,我要说我非常喜欢Redis,并且过去我已经在生产中成功使用了Redis。我认为这非常适合以下情况:您希望在服务器之间共享一些瞬时的,近似的,快速变化的数据,并且如果由于某种原因偶尔丢失这些数据也没什么大不了的。例如,一个好用例是维护每个IP地址的请求计数器(出于速率限制的目的)和每个用户ID的不同IP地址集(用于滥用检测)。

    但是,Redis一直在逐步进入具有更高一致性和持久性期望的数据管理领域,这让我担心,因为这不是Redis的目标。可以说,分布式锁定是这些领域之一。让我们更详细地研究它。

    您将那个锁用于什么用途?

    锁定的目的是确保在可能尝试执行同一工作的多个节点中,只有一个实际上可以执行(一次至少一次)。这项工作可能是将一些数据写入共享存储系统,执行一些计算,调用某些外部API等。从高层次上讲,您可能想在分布式应用程序中锁定的原因有两个: 效率或正确性  [2]。为了区分这些情况,您可以询问锁定失败的情况:

    • 效率:进行锁定可以避免不必要地重复执行两次相同的工作(例如,一些昂贵的计算)。如果锁定失败,并且两个节点最终完成相同的工作,则结果是成本略有增加(您最终向AWS支付的费用比原本多5美分)或带来的不便(例如,用户最终两次收到相同的电子邮件通知)。
    • 正确性:进行锁定可以防止并发进程踩到彼此的脚趾并弄乱系统状态。如果锁定失败,并且两个节点同时处理同一数据,则结果将导致文件损坏,数据丢失,永久性不一致,向患者使用的药物剂量错误或其他一些严重问题。

    两者都是想要锁定的有效情况,但是您需要非常清楚要处理的是哪一种。

    我会争辩说,如果您仅出于提高效率的目的使用锁,则不必招致Redlock的成本和复杂性,无需运行5台Redis服务器并检查是否有大多数人可以获得您的锁。您最好只使用一个Redis实例,如果主实例崩溃,则可以异步复制到辅助实例。

    如果您使用单个Redis实例,那么如果Redis节点突然断电或发生其他问题,您当然会丢掉一些锁。但是,如果您仅将锁用作效率优化,并且崩溃不会经常发生,那没什么大不了的。Redis大放异彩是这种“没什么大不了”的场景。至少如果您仅依靠单个Redis实例,那么查看系统的每个人都清楚锁是近似的,并且仅用于非关键目的。

    另一方面,具有5个副本和多数投票的Redlock算法乍一看,似乎适用于锁定对于正确性很重要的情况。在以下各节中,我将争辩说它适合该目的。对于本文的其余部分,我们将假定您的锁对于正确性很重要,并且如果两个不同的节点同时认为它们持有相同的锁,则这是一个严重的错误。

    用锁保护资源

    让我们暂时搁置一下Redlock的细节,并讨论一般如何使用分布式锁(与所使用的特定锁定算法无关)。重要的是要记住,分布式系统中的锁不像多线程应用程序中的互斥锁。由于存在不同的节点和网络都可以以各种方式独立发生故障的问题,因此这是一个更加复杂的野兽。

    例如,假设您有一个应用程序,其中客户端需要更新共享存储中的文件(例如HDFS或S3)。客户端首先获取锁,然后读取文件,进行一些更改,将修改后的文件写回,最后释放锁。该锁可防止两个客户端同时执行此读取-修改-写入周期,这将导致更新丢失。该代码可能看起来像这样:

    // THIS CODE IS BROKEN
    function writeData(filename, data) {
        var lock = lockService.acquireLock(filename);
        if (!lock) {
            throw 'Failed to acquire lock';
        }
    
        try {
            var file = storage.readFile(filename);
            var updated = updateContents(file, data);
            storage.writeFile(filename, updated);
        } finally {
            lock.release();
        }
    }

    不幸的是,即使您拥有完善的锁定服务,上面的代码也已损坏。下图显示了如何以损坏的数据结束:

     

    在此示例中,获取锁的客户端在持有锁的同时暂停了一段较长的时间–例如,因为垃圾收集器(GC)被踢了进来。锁具有超时(即,它是租约),即总是一个好主意(否则,崩溃的客户端最终可能永远持有一把锁,而永远不会释放它)。但是,如果GC暂停的持续时间长于租约到期期限,并且客户没有意识到它已过期,则可能会继续进行一些不安全的更改。

    这个错误不是理论上的:HBase曾经有这个问题  [3,4]。通常,GC暂停时间很短,但是有时人们知道“世界停下来”的GC暂停时间可以持续 几分钟  [5] –肯定足够长,足以使租约到期。即使是像HotSpot JVM的CMS这样的所谓的“并发”垃圾收集器,也无法与应用程序代码完全并行运行-甚至他们需要时不时地停止运行[6]。

    您不能通过在写回存储之前在锁定到期时插入检查来解决此问题。请记住,GC可以在任何时候暂停正在运行的线程,包括对您而言最大的麻烦(在最后一次检查和写入操作之间)。

    而且,如果由于编程语言运行时没有长时间的GC暂停而感到自鸣得意,则还有许多其他原因导致您的进程可能被暂停。也许您的进程试图读取一个尚未加载到内存中的地址,所以它遇到了页面错误,并被暂停,直到从磁盘加载页面为止。也许您的磁盘实际上是EBS,所以读取变量会不经意间转变为通过Amazon拥塞网络发出的同步网络请求。也许还有许多其他竞争CPU的进程,而您在调度程序树中遇到了一个黑色节点。也许有人不小心将SIGSTOP发送到该进程。随你。您的过程将暂停。

    如果您仍然不相信我有关进程暂停的信息,那么可以考虑在到达存储服务之前,网络中的文件写入请求可能会延迟。诸如以太网和IP之类的数据包网络可能会任意延迟数据包,而它们确实做到了  [7]:在GitHub的一次著名 事件中,数据包在网络中被延迟了大约90秒[8]。这意味着应用程序进程可以发送写请求,并且当租约已经到期时,它可能在一分钟后到达存储服务器。

    即使在管理良好的网络中,也会发生这种情况。您根本无法对时间做出任何假设,这就是无论您使用哪种锁定服务,上述代码从根本上来说都不安全的原因。

    用栅栏保护锁安全

    解决此问题的方法实际上非常简单:您需要在对存储服务的每个写入请求中都包含隔离标记。在这种情况下,防护令牌只是每次客户端获取锁时都会增加(例如,通过锁服务增加)的数字。如下图所示:

    使用隔离令牌使资源访问安全

    客户端1获得了租约并获得了33的令牌,但随后进入了长暂停状态,租约到期。客户端2获得租约,获得令牌34(该数字始终在增加),然后将其写操作(包括令牌34)发送到存储服务。随后,客户端1恢复工作并将其写操作发送到存储服务,包括其令牌值33。但是,存储服务器记住它已经处理了具有较高令牌号的写入(34),因此它拒绝了具有令牌33的请求。

    请注意,这要求存储服务器在检查令牌中发挥积极作用,并拒绝令牌已倒退的所有写操作。但是,一旦知道了窍门,这并不是特别困难。并且只要锁服务生成严格单调递增的令牌,就可以使锁安全。例如,如果您将ZooKeeper用作锁定服务,则可以将zxid 或znode版本号用作防护令牌,并且状态良好[3]。

    但是,这使我们遇到了Redlock的第一个大问题:它没有任何生成防护令牌的工具。该算法不会产生任何保证每次客户端获取锁都会增加的数字。这意味着,即使该算法在其他方面是完美的,也将无法安全使用,因为在一个客户端暂停或其数据包被延迟的情况下,您无法防止客户端之间的竞争状态。

    对于我来说,还不知道如何更改Redlock算法以开始生成隔离令牌。它使用的唯一随机值不能提供所需的单调性。仅在一个Redis节点上保留一个计数器是不够的,因为该节点可能会失败。在多个节点上保留计数器将意味着它们将不同步。您可能需要一个共识算法才能生成围栏令牌。(如果仅增加一个计数器很简单。)

    用时间解决共识

    Redlock无法生成隔离令牌的事实应该已经成为在正确性取决于锁定的情况下不使用它的充分理由。但是还有一些其他问题值得讨论。

    在学术文献中,用于这种算法的最实用的系统模型是带有不可靠故障检测器的 异步模型  [9]。用简单的英语来说,这意味着该算法不对时序做任何假设:进程可能会暂停任意时间长度,数据包可能会在网络中被任意延迟,时钟可能会被任意错误-尽管如此,该算法仍有望正确执行事情。鉴于我们上面讨论的内容,这些是非常合理的假设。

    算法可以使用时钟的唯一目的是生成超时,以避免在节点发生故障时永远等待。但是超时不必一定是准确的:仅仅是因为一个请求超时,并不意味着另一个节点肯定已关闭–也可能是网络中存在较大的延迟,或者您的本地时钟是错的。当用作故障检测器时,超时仅是某些错误的猜测。(如果可以的话,分布式算法将完全不使用时钟,但是共识变得不可能了  [10]。获取锁就像比较设置操作,需要达成共识  [11]。)

    请注意,Redis 使用gettimeofday而非单调时钟来确定密钥到期时间。的手册页gettimeofday 明确指出,返回的时间会受到系统时间的不连续跳跃-也就是说,它可能突然向前跳跃几分钟,甚至跳回时间(例如,如果时钟由NTP步进,因为它与NTP服务器的差异太大,或者时钟是由管理员手动调整的)。因此,如果系统时钟做奇怪的事情,很容易发生Redis中的密钥过期比预期快得多或慢得多的情况。

    对于异步模型中的算法来说,这不是一个大问题:这些算法通常可确保始终保持其安全性,而无需进行任何时序假设  [12]。仅活动属性取决于超时或其他故障检测器。用简单的英语来说,这意味着,即使系统中的时序无处不在(进程暂停,网络延迟,时钟向前和向后跳动),算法的性能也可能会陷入困境,但该算法永远不会错误的决定。

    但是,Redlock不是这样的。它的安全性取决于许多时序假设:它假设所有Redis节点在过期前大约保持正确的时间长度;与有效期相比,网络延迟小;而且该过程的暂停比有效期短得多。

    用不好的时机打破Redlock

    让我们看一些示例来说明Redlock对时序假设的依赖。假设系统有五个Redis节点(A,B,C,D和E)和两个客户端(1和2)。如果Redis节点之一上的时钟向前跳怎么办?

    1. 客户端1获取节点A,B,C的锁定。由于网络问题,无法访问D和E。
    2. 节点C上的时钟向前跳,导致锁过期。
    3. 客户端2获取节点C,D,E的锁定。由于网络问题,无法访问A和B。
    4. 现在,客户1和2都认为他们持有该锁。

    如果C在将锁保留到磁盘之前崩溃并立即重新启动,则可能会发生类似的问题。因此,Redlock文档建议将崩溃的节点的重新启动至少延迟最长寿命的锁的生存时间。但是,此重新启动延迟再次依赖于合理准确的时间度量,并且如果时钟跳变将失败。

    好的,所以您可能认为时钟跳变是不现实的,因为您对正确配置NTP仅能摆正时钟非常有信心。在这种情况下,让我们看一个进程暂停可能导致算法失败的示例:

    1. 客户端1请求锁定节点A,B,C,D,E。
    2. 在发送对客户端1的响应时,客户端1进入了世界停止GC。
    3. 锁在所有Redis节点上失效。
    4. 客户端2获得对节点A,B,C,D,E的锁定。
    5. 客户端1完成GC,并接收来自Redis节点的响应,表明它已成功获取了锁(在进程暂停时它们已保存在客户端1的内核网络缓冲区中)。
    6. 现在,客户1和2都认为他们持有该锁。

    请注意,即使Redis是用C编写的,因此没有GC,但这在这里也无济于事:任何客户端可能会遇到GC暂停的系统都存在此问题。您只能通过阻止客户端1在客户端2获得锁之后执行该锁下的任何操作来确保此安全,例如使用上述防护方法。

    较长的网络延迟会产生与过程暂停相同的效果。这可能取决于您的TCP用户超时-如果您将超时时间大大短于Redis TTL,则可能会忽略延迟的网络数据包,但是为了确保这一点,我们必须详细研究TCP。另外,随着超时,我们又回到了时间测量的准确性!

    Redlock的同步假设

    这些示例表明,只有在假设使用同步系统模型(即具有以下属性的系统)的情况下,Redlock才能正常工作:

    • 有界的网络延迟(您可以保证数据包始终在一定的最大延迟内到达),
    • 有限的过程暂停(换句话说,严格的实时约束,通常只能在汽车安全气囊系统等中找到),并且
    • 有限的时钟错误(用手指指您无法从错误的NTP服务器获取时间)。

    请注意,同步模型并不意味着时钟完全同步:这意味着您假设网络延迟,暂停和时钟漂移的固定上限已知的 [12]。Redlock假设相对于锁的生存时间而言,延迟,暂停和漂移都很小;如果计时问题变得与生存时间一样大,则该算法将失败。

    在行为良好的数据中心环境中,大多数 时间都将满足时序假设–这被称为部分同步系统  [12]。但这足够好吗?一旦这些时间假设被打破,Redlock可能会违反其安全属性,例如,在一个客户过期之前将其授予租约。如果您依靠锁来确保正确性,那么“大多数时候”是不够的–您需要始终保持正确性。

    有大量证据表明,对于大多数实际系统环境而言,假设同步系统模型并不安全[7,8]。持续90秒钟的数据包延迟提醒自己GitHub事件 。Redlock不可能在Jepsen测试中幸存下来。

    另一方面,为部分同步的系统模型(或带有故障检测器的异步模型)设计的共识算法实际上有工作的机会。筏,带时间戳的复制,Zab和Paxos都属于此类。这种算法必须放弃所有时序假设。很难:假设网络,进程和时钟比实际更可靠。但是在混乱的分布式系统现实中,您必须非常谨慎地进行假设。

    结论

    我认为Redlock算法是一个错误的选择,因为它“既不是鱼也不是禽”:对于效率优化锁来说,它不必要地繁重且昂贵,但是对于正确性取决于锁的情况,它并不是足够安全。

    特别是,该算法对时序和系统时钟进行了危险的假设(本质上是假设同步系统具有受限的网络延迟和操作的受限执行时间),并且如果不满足这些条件,就会违反安全性。而且,它缺乏用于生成隔离令牌的功能(可以保护系统免受网络或暂停进程中的长时间延迟)。

    如果您仅在尽力而为的基础上需要锁(作为效率优化,而不是为了正确性),我建议您为Redis 坚持使用简单的单节点锁算法(不存在条件集的情况下获取锁,原子的delete-if-value-matches来释放锁),并在代码中非常清楚地证明锁只是近似的,有时可能会失败。不必理会由五个Redis节点组成的集群。

    另一方面,如果您需要锁定以确保正确性,请不要使用Redlock。相反,请使用适当的共识系统,例如ZooKeeper,可能通过 实现锁定的Curator配方之一。(至少,使用具有合理事务保证数据库。)并且请在锁定下的所有资源访问上强制使用防护令牌。

    正如我在开始时所说的,Redis是一个很好的工具,如果您正确使用它。以上所有内容都不会削弱Redis用于其预期目的的有用性。萨尔瓦多(Salvatore)多年来一直致力于该项目,其成功理所应当。但是每种工具都有局限性,了解它们并据此计划很重要。

    如果您想了解更多信息,我将在我的书的第8章和第9章中更详细地解释该主题,该书现在可以从O'Reilly的Early Release中获得。(以上图表摘自我的书。)为了学习如何使用ZooKeeper,我推荐Junqueira和Reed的书  [3]。为了更好地介绍分布式系统理论,我推荐Cachin,Guerraoui和Rodrigues的教科书  [13]。

    感谢Kyle KingsburyCamille FournierFlavio Junqueira和 Salvatore Sanfilippo审阅本文草稿。当然,任何错误都是我的。

    2016年2月9日更新: Redlock的原始作者 Salvatore对本文发表了反驳(另请参见 HN讨论)。他提出了一些意见,但我坚持我的结论。如果有时间,我可能会在后续帖子中进行详细说明,但请形成您自己的意见-请查阅以下参考资料,其中许多参考资料都经过了严格的学术同行评审(与我们的任何一篇博文均不同)。

    参考文献

    [1] Cary G Gray和David R Cheriton:“ 租赁:分布式文件缓存一致性的有效容错机制 ”,在第12届ACM操作系统原理研讨会(SOSP)上,1989年12月 。doi:10.1145 / 74850.74870

    [2] Mike Burrows:“ 松散耦合分布式系统的Chubby锁服务 ”,在2006年11月举行的第七届USENIX操作系统设计和实现(OSDI)研讨会上

    [3] Flavio P Junqueira和Benjamin Reed: ZooKeeper:分布式过程协调。O'Reilly Media,2013年11月。ISBN:978-1-4493-6130-3

    [4] EnisSöztutar:“ HBase和HDFS:了解HBase中的文件系统使用 ”,在HBaseCon上,2013年6月。

    [5] Todd Lipcon:“ 避免使用带有MemStore本地分配缓冲区的Apache HBase中的完整GC:第1部分 ”,blog.cloudera.com,2011年2月24日。

    [6]马丁·汤普森(Martin Thompson):“ Java垃圾收集已蒸馏 ”,mechanical-sympathy.blogspot.co.uk,2013年7月16日。

    [7] Peter Bailis和Kyle Kingsbury:“ The Network is Reliable ”, ACM Queue,第12卷,第7期,2014年7月 。doi:10.1145 / 2639988.2639988

    [8] Mark Imbriaco:“ 上周六停机,” github.com,2012年12月26日。

    [9] Tushar Deepak Chandra和Sam Toueg:“ 可靠的分布式系统的不可靠故障检测器 ” ,ACM杂志,第43卷,第2期,第225-267页,1996年3月 。doi:10.1145 / 226643.226647

    [10] Michael J Fischer,Nancy Lynch和Michael S Paterson:“ 不可能通过一个错误的过程达成分布式共识 ” ,ACM杂志,第32卷,第2期,第374-382页,1985年4月 。doi:10.1145 / 3149.214121

    [11] Maurice P Herlihy:“无等待同步 ”, ACM Transactions on Programming Languages and Systems,第13卷,第1期,第124-149页,1991年1月 。doi:10.1145 / 114005.102808

    [12]辛西娅·德沃克(Cynthia Dwork),南希·林奇(Nancy Lynch)和拉里·斯托克迈尔(Larry Stockmeyer):“ 存在部分同步的共识 ” ,《美国计算机学会》 ,第35卷,第2期,第288-323页,1988年4月 。doi:10.1145 / 42282.42283

    [13] Christian Cachin,Rachid Guerraoui和LuísRodrigues: 可靠和安全的分布式编程简介,第二版。斯普林格,2011年2月。ISBN:978-3-642-15259-7, doi:10.1007 / 978-3-642-15260-3

    展开全文
  • 分布式锁之Redis RedLock算法

    千次阅读 2019-04-08 20:25:02
    一、原始的Redis锁 1、使用setnx对资源上锁,产生的键值是<key,value>,key是随机生成的数字。 2、上锁成功则表示已经获得锁,使用acquire设置超时时间 3、其他进程上锁则返回失败,并且检查锁是否设置超时...

    一、原始的Redis锁

    1、使用setnx对资源上锁,产生的键值是<key,value>,key是随机生成的数字。
    2、上锁成功则表示已经获得锁,使用acquire设置超时时间
    3、其他进程上锁则返回失败,并且检查锁是否设置超时时间,如果没有设置则设置超时时间。

    16位随机数字uuid的选取:

    【官方推荐】1、从 /dev/urandom/中取20个byte作为随机数
    例如使用RC4加密算法在/dev/urandom中得到一个种子(Seed),然后生成一个伪随机流。
    2、也可以用更简单的使用时间戳+客户端编号的方式生成随机数
    

    二、竞态模型场景

    为了避免Redis宕机引起锁服务不可用, 需要为Redis实例(master)增加热备(slave),如果master不可用则将slave提升为master。这种主从的配置方式存在一定的安全风险,由于Redis的主从复制是异步进行的, 可能会发生多个客户端同时持有一个锁的现象。

    竞态模型:
    1、Client A 获得在master节点获得了锁
    2、在master将key备份到slave节点之前,master宕机
    3、slave 被提升为master
    4、Client B 在新的master节点处获得了锁,Client A也持有这个锁。

    这导致:master不可用时,它所包含的锁同样不被记录,之前已经获得的锁被视为无效,对于刚升级为master的slave而言,仍可以对某资源加锁。
    解决方法:分布式下的RedLock算法

    三、多Redis实例解决单点故障-----RedLock算法

    一个Client想要获得一个锁需要以下几个操作:

    1、得到本地时间

    2、Client使用相同的key和随机数,按照顺序在每个Master实例中尝试获得锁。在获得锁的过程中,为每一个锁操作设置一个快速失败时间(如果想要获得一个10秒的锁,那么每一个锁操作的失败时间设为5-50ms)。这样可以避免客户端与一个已经故障的Master通信占用太长时间,通过快速失败的方式尽快的与集群中的其他节点完成锁操作。

    3、客户端计算出与master获得锁操作过程中消耗的时间,当且仅当Client获得锁消耗的时间小于锁的存活时间,并且在一半以上的master节点中获得锁。才认为client成功的获得了锁。

    4、如果已经获得了锁,Client执行任务的时间窗口是锁的存活时间减去获得锁消耗的时间。

    5、如果Client获得锁的数量不足一半以上,或获得锁的时间超时,那么认为获得锁失败。客户端需要尝试在所有的master节点中释放锁, 即使在第二步中没有成功获得该Master节点中的锁,仍要进行释放操作。

    可用性分析:
    (1)锁的自动释放(key expire),最终锁将被释放并且被再次申请。
    (2)客户端在未申请到锁以及申请到锁并完成任务后都将进行释放锁的操作,所以大部分情况下都不需要等待到锁的自动释放期限,其他client即可重新申请到锁。
    (3)假设一个Client在大多数Redis实例中申请锁请求所成功花费的时间为Tac。那么如果某个Client第一次没有申请到锁,需要重试之前,必须等待一段时间T。T需要远大于Tac。 因为多个Client同时请求锁资源,他们有可能都无法获得一半以上的锁,导致脑裂双方均失败。设置较久的重试时间是为了减少脑裂产生的概率。

    **脑裂(split brain):**
    三个Client同时尝试获得锁,分别获得了2,2,1个实例中的锁,三个锁请求全部失败。
    一个client在全部Redis实例中完成的申请时间越短,发生脑裂的时间窗口越小。
    所以比较理想的做法:同时向N个Redis实例发出异步的SET请求。
    
    展开全文
  • 基于Redis RedLock的分布式同步锁

    千次阅读 2018-11-13 11:16:20
    本文采用Redis官网提供的RedLock来实现分布式同步锁,实现了单机模式和哨兵集群模式两种。 安全和可靠性保证 在描述我们的设计之前,我们想先提出三个属性,这三个属性在我们看来,是实现高效分布式锁的基础。 安全...

    本文采用Redis官网提供的RedLock来实现分布式同步锁,实现了单机模式和哨兵集群模式两种。

    安全和可靠性保证

    在描述我们的设计之前,我们想先提出三个属性,这三个属性在我们看来,是实现高效分布式锁的基础。

    • 安全属性:互斥,不管任何时候,只有一个客户端能持有同一个锁。
    • 效率属性A:不会死锁,最终一定会得到锁,就算一个持有锁的客户端宕掉或者发生网络分区。
    • 效率属性B:容错,只要大多数Redis节点正常工作,客户端应该都能获取和释放锁。

    1、RedLock原理

    • 1.获取当前时间(单位是毫秒)

    • 2.轮流用相同的key和随机值在N个节点上请求锁,在这一步里,客户端在每个master上请求锁时会有一个和总的锁释放时间相比小的多的超时时间。比如如果锁自动释放时间是10秒钟,那每个节点锁请求的超时时间可能是5-50毫秒的范围,这个可以防止一个客户端在某个宕掉的master节点上阻塞过长时间,如果一个master节点不可用了,我们应该尽快尝试下一个master节点

    • 3.客户端计算第二步中获取锁所花的时间,只有当客户端在大多数master节点上成功获取了锁(在这里是3个),而且总共消耗的时间不超过锁释放时间,这个锁就认为是获取成功了

    • 4.如果锁获取成功了,那现在锁自动释放时间就是最初的锁释放时间减去之前获取锁所消耗的时间

    • 5.如果锁获取失败了,不管是因为获取成功的锁不超过一半(N/2+1)还是因为总消耗时间超过了锁释放时间,客户端都会到每个master节点上释放锁,即便是那些他认为没有获取成功的锁。

    更为详细的介绍请参见:官网文档http://ifeve.com/redis-lock/

    2、maven导入依赖

    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-data-redis</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-configuration-processor</artifactId>
        <optional>true</optional>
    </dependency>
    <dependency>
        <groupId>org.redisson</groupId>
        <artifactId>redisson</artifactId>
        <version>3.7.5</version>
    </dependency>
    

    主要配置文件

    @Configuration
    @ConfigurationProperties(prefix = "redisson")
    @ConditionalOnProperty("redisson.password")
    @Data
    public class RedissonProperties {
        /**
         * 连接超时时长
         */
        private int timeout = 3000;
        /**
         * ip
         */
        private String address;
        /**
         * 密码
         */
        private String password;
        /**
         * 连接库
         */
        private int database = 0;
        /**
         * 连接池大小
         */
        private int connectionPoolSize = 64;
        /**
         * 最小连接数
         */
        private int connectionMinimumIdleSize = 10;
        /**
         * 备用服务器连接数
         */
        private int slaveConnectionPoolSize = 250;
        /**
         * 主服务器连接数
         */
        private int masterConnectionPoolSize = 250;
        /**
         * 哨兵地址
         */
        private String[] sentinelAddresses;
        /**
         * 主服务器名称
         */
        private String masterName;
    }
    

    分布式锁初始化类

    @Configuration
    @ConditionalOnClass(Config.class)
    @EnableConfigurationProperties(RedissonProperties.class)
    public class RedissonAutoConfiguration {
    
        @Autowired
        private RedissonProperties redissonProperties;
    
        @Bean
        @ConditionalOnProperty(name="redission.master-name")
        RedissonClient redissonSentinel(){
            Config config = new Config();
            SentinelServersConfig sentinelServersConfig = config.useSentinelServers()
                    .setDatabase(redissonProperties.getDatabase())
                    .addSentinelAddress(redissonProperties.getSentinelAddresses())
                    .setMasterName(redissonProperties.getMasterName())
                    .setTimeout(redissonProperties.getTimeout())
                    .setMasterConnectionPoolSize(redissonProperties.getMasterConnectionPoolSize())
                    .setSlaveConnectionPoolSize(redissonProperties.getSlaveConnectionPoolSize());
            if(StringUtils.isNotBlank(redissonProperties.getPassword())){
                sentinelServersConfig.setPassword(redissonProperties.getPassword());
            }
            return Redisson.create(config);
        }
    
        @Bean
        @ConditionalOnProperty(name = "redisson.address")
        RedissonClient redissonClient(){
            Config config = new Config();
            SingleServerConfig singleServerConfig = config.useSingleServer()
                    .setAddress("redis://" + StringUtils.trim(redissonProperties.getAddress()))
                    .setDatabase(redissonProperties.getDatabase())
                    .setTimeout(redissonProperties.getTimeout())
                    .setConnectionPoolSize(redissonProperties.getConnectionPoolSize())
                    .setConnectionMinimumIdleSize(redissonProperties.getConnectionMinimumIdleSize());
            if( StringUtils.isNotEmpty(redissonProperties.getPassword()) ){
                singleServerConfig.setPassword(redissonProperties.getPassword());
            }
            return Redisson.create(config);
        }
    
    
        @Bean
        @ConditionalOnBean(RedissonClient.class)
        DistributedLock distributedLock(RedissonClient redissonClient){
            DistributedLock lock = new RedissonDistributedLocker(redissonClient);
            return lock;
        }
    }
    

    根据配置动态生成哨兵集群模式和单机模式。主要对Redis集群进行配置后根据Redisson初始化Redisson连接。

    分布式锁接口

    /**
     * 基于Redisson的分布式锁接口
     * @author liumeng
     */
    public interface DistributedLock {
    
        /**
         * 获取锁
         * @param lockKey
         * @return
         */
        RLock lock(String lockKey);
    
        /**
         * 获取锁,设置锁超时时长
         * @param lockKey
         * @param leaseTime
         * @return
         */
        RLock lock(String lockKey, long leaseTime);
    
        /**
         * 获取锁,设置锁超时时长
         * @param lockKey
         * @param leaseTime
         * @param timeUnit
         * @return
         */
        RLock lock(String lockKey, long leaseTime, TimeUnit timeUnit);
    
    
        /**
         * 尝试获取锁
         * @param lockKey
         * @param waitTime
         * @param leaseTime
         * @param timeUnit
         * @return
         */
        boolean tryLock(String lockKey, long waitTime, long leaseTime, TimeUnit timeUnit);
    
        /**
         * 释放锁
         * @param lockKey
         */
        void unLock(String lockKey);
    
        /**
         * 释放锁
         * @param rLock
         */
        void unLock(RLock rLock);
    }
    

    分布式锁接口实现类

    /**
     * @author liumeng
     */
    @Slf4j
    public class RedissonDistributedLocker implements DistributedLock {
    
        private RedissonClient redissonClient;
    
        public RedissonDistributedLocker(RedissonClient redissonClient){
            this.redissonClient = redissonClient;
        }
    
        @Override
        public RLock lock(String lockKey) {
            RLock rLock = this.getRLock(lockKey);
            rLock.lock();
            return rLock;
        }
    
        @Override
        public RLock lock(String lockKey, long leaseTime) {
            return this.lock(lockKey, leaseTime, TimeUnit.SECONDS);
        }
    
        @Override
        public RLock lock(String lockKey, long leaseTime, TimeUnit timeUnit) {
            RLock rLock = this.getRLock(lockKey);
            rLock.lock(leaseTime, timeUnit);
            return rLock;
        }
    
        @Override
        public boolean tryLock(String lockKey, long waitTime, long leaseTime, TimeUnit timeUnit) {
            RLock rLock = this.getRLock(lockKey);
            try {
                return rLock.tryLock(waitTime, leaseTime, timeUnit);
            } catch (InterruptedException e) {
                log.error("", e);
            }
            return false;
        }
    
        @Override
        public void unLock(String lockKey) {
            RLock rLock = this.getRLock(lockKey);
            rLock.unlock();
        }
    
        @Override
        public void unLock(RLock rLock) {
            if( null == rLock ){
                throw new NullPointerException("rLock cannot be null.");
            }
            rLock.unlock();
        }
    
        private RLock getRLock(String lockKey) {
            if( null == redissonClient ){
                throw new NullPointerException("redisson client is null.");
            }
            return redissonClient.getLock(lockKey);
        }
    }
    
    参考:Redisson官方文档
    展开全文
  • https://www.cnblogs.com/rgcLOVEyaya/p/RGC_LOVE_YAYA_1003days.html
  • redisredLock

    2020-06-04 07:55:43
    Redis 官方站这篇文章提出了一种权威的基于 Redis 实现分布式锁的方式名叫 Redlock,此种方式比原先的单节点的方法更安全。它可以保证以下特性: 安全特性:互斥访问,即永远只有一个 client 能拿到锁 避免死锁:...
  • Redis / redlock warning

    2020-12-09 04:12:48
    passthrough has been deprecated and will be removed in redis-namespace 2.0 (at /usr/local/rbenv/versions/2.4.1/lib/ruby/gems/2.4.0/gems/redlock-0.2.0/lib/redlock/client.rb:127:in `load_scripts&#...
  • redis: RedLock algorithm

    2018-11-30 22:30:03
    redis分布式锁实现的: RedLock 算法 The algorithm's goal was to move away people that were using a single Redis instance, or a master-slave setup with failover, in order to implement distributed locks,...
  • redisRedlock

    千次阅读 2018-05-24 22:12:59
    RedisConnection connection = template.getConnectionFactory().getConnection(); try { long l = System.nanoTime() - nowTime; while (l ) { // 锁是否存在 if (connection.setNX(LOCK_KEY....
  • 引言之前自己在用redis来实现分布式锁的时候都是基于单个Redis实例,也就是说Redis本身是有单点故障的,Redis的官方文档介绍了一种"自认为"合理的算法,Redlock来实现分布式Redis下的分布式锁。Martin Kleppmann写了...
  • 但这种实现是基于单个redis服务,若redis服务不可用,显然所有客户端无法加锁,该实现还未到高可用的水平,因此需要进一步提升分布式的锁的逻辑,好在redis官方提供了相应的权威描述并称之为Redlock,具体参考文章:...
  • Redlock是一种算法,Redlock也就是Redis Distributed Lock,可用实现多节点redis的分布式锁。 RedLock官方推荐,Redisson完成了对Redlock算法封装。 此种方式具有以下特性: 互斥访问:即永远只有一个 client 能...
  • 设计分布式锁需要哪些条件? 首先应该是互斥性,即无论任何情况下...用Redis来实现分布式锁最简单的方式就是在单实例里创建一个键值,创建出来的键值一般都是有一个超时时间的(这个是Redis自带的超时特性),所以...
  • 引言之前自己在用redis来实现分布式锁的时候都是基于单个Redis实例,也就是说Redis本身是有单点故障的,Redis的官方文档介绍了一种"自认为"合理的算法,Redlock来实现分布式Redis下的分布式锁。Martin Kleppmann写了...
  • 引言之前自己在用redis来实现分布式锁的时候都是基于单个Redis实例,也就是说Redis本身是有单点故障的,Redis的官方文档介绍了一种"自认为"合理的算法,Redlock来实现分布式Redis下的分布式锁。Martin Kleppmann写了...
  • Redis】Is Redlock safe?

    2017-10-12 20:59:12
    Article Source : http://antirez.com/news/101 Martin Kleppmann, a distributed systems researcher, yesterday published an analysis of Redlock (http://redis.io/topics/distlock), that you can find here: ...
  • RedLock算法的基本思路是让客户端依次和多个redis实例请求加锁,对于单个节点加锁有可能成功也有可能失败,最后统计一下成功加锁的节点数量,如果对超过一半的节点返回成功那就可以认为这个分布式锁成功加锁了;...
  • 引言之前自己在用redis来实现分布式锁的时候都是基于单个Redis实例,也就是说Redis本身是有单点故障的,Redis的官方文档介绍了一种"自认为"合理的算法,Redlock来实现分布式Redis下的分布式锁。Martin Kleppmann写了...
  • Redis 官方站这篇文章提出了一种权威的基于 Redis 实现分布式锁的方式名叫 Redlock,此种方式比原先的单节点的方法更安全。它可以保证以下特性: 安全特性:互斥访问,即永远只有一个 client 能拿锁 避免死锁:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 665
精华内容 266
关键字:

redisredlock

redis 订阅