精华内容
下载资源
问答
  • RedLock.net, 在 C# 中,Redlock算法的实现 RedLock.net 一种 Redlock分布式锁算法的实现。利用优秀的 StackExchange.Redis 插件库。分布式锁对于确保在任何给定时间( 即使这些进程在不同的机器上运行) 只使用一个...
  • redlock算法及其问题

    2019-05-30 15:00:00
    redlock算法是为了解决什么问题呢? 在单redis实例实现分布式锁时,可能会出现线程A设置完锁后,master挂掉,slave提升为master,因为异步复制的特性,线程A设置的锁丢失了,这时候线程B设置锁也能够成功,导致线程...

    背景

    redlock算法是为了解决什么问题呢?

    在单redis实例实现分布式锁时,可能会出现线程A设置完锁后,master挂掉,slave提升为master,因为异步复制的特性,线程A设置的锁丢失了,这时候线程B设置锁也能够成功,导致线程A和B同时拥有锁

    然后redis作者提出了redlock算法

    算法描述

    1. 获得当前时间(ms)

    2. 首先设置一个锁有效时间valid_time,也就是超过这个时间后锁自动释放,使用相同的key和value对所有redis实例进行设置,每次链接redis实例时设置一个小于valid_time的超时时间,比如valid_time时10s,那超时时间可以设置成50ms,如果这个实例不行,那么换下一个设置

    3. 计算获取锁总共占用的时间,再加上时钟偏移,如果这个总时间小于valid_time,并且成功设置锁的实例数>= N/2 + 1,那么加锁成功

    4. 如果加锁成功了,那么这个锁的有效时间就是valid_time - 获取锁占用的时间 - 时钟偏移

    5. 如果加锁失败,解锁所有实例(每个redis实例都运行del key)

    问题

    好了,算法看完了,给我的感觉就是,好像更不靠谱了,因为引入了一个不靠谱的时间,时间偏差在分布式系统中应该是很容易出现的吧,在锁有效时间里虽然减去了时钟偏移,但是应该减多少合适呢,要是这个值设置不好,很容易出现问题

    先不提这个,我们回顾一下单redis实例的问题,主从切换时可能会有两个线程占有锁,那么redlock有没有这个问题呢

    假设我们有5个redis实例a,b,c,d,e,线程A分别加锁,然后a,b,c加锁成功,因为网络分区问题,d,e失败。同时,线程B也加锁,因为网络分区问题,a,b加锁失败,但是d,e加锁成功。这时候,显然线程A会获得锁,但是如果这时候c的master挂了,然后切换成了slave,slave中没有A加锁的信息,恰巧这时线程B对c加锁的命令到了,那线程B就会加锁成功,这时候,线程A和B都给三个节点加锁成功了,他们同时拥有锁。所以我认为redlock仍然没有解决这个问题,只是让这个问题更不容易发生了,这里如果我想错的话欢迎指正

    另外,redis作者也对这个算法进行了分析,建议对锁互斥的安全性要求高的应用不要使用这个算法,分析了GC停顿,page fault,clock jump等等对时间产生的影响,可以参考http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

    转载于:https://www.cnblogs.com/luocaodan/p/10949558.html

    展开全文
  • 在多线程共享临界资源的场景下,分布式锁是一种非常重要的组件。许多库使用不同的方式使用redis实现一个分布式锁管理。...在介绍RedLock算法之前,我们列出了一些已经实现了分布式锁的类库供大家参考。Redlock-rb ...

    在多线程共享临界资源的场景下,分布式锁是一种非常重要的组件。

    许多库使用不同的方式使用redis实现一个分布式锁管理。

    其中有一部分简单的实现方式可靠性不足,可以通过一些简单的修改提高其可靠性。

    这篇文章介绍了一种指导性的redis分布式锁算法RedLock,RedLock比起单实例的实现方式更加安全。

    在介绍RedLock算法之前,我们列出了一些已经实现了分布式锁的类库供大家参考。

    Redlock-rb (Ruby 实现).

    Redlock-py (Python 实现)

    Redlock-php (PHP 实现)

    PHPRedisMutex (further 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 实现)

    分布式锁应该具有的特性(Safety & Liveness)

    我们将从三个特性的角度出发来设计RedLock模型:

    安全性(Safety):在任意时刻,只有一个客户端可以获得锁(排他性)。

    避免死锁:客户端最终一定可以获得锁,即使锁住某个资源的客户端在释放锁之前崩溃或者网络不可达。

    容错性:只要Redsi集群中的大部分节点存活,client就可以进行加锁解锁操作。

    故障切换(failover)实现方式的局限性

    通过Redis为某个资源加锁的最简单方式就是在一个Redis实例中使用过期特性(expire)创建一个key, 如果获得锁的客户端没有释放锁,那么在一定时间内这个Key将会自动删除,避免死锁。

    这种做法在表面上看起来可行,但分布式锁作为架构中的一个组件,为了避免Redis宕机引起锁服务不可用, 我们需要为Redis实例(master)增加热备(slave),如果master不可用则将slave提升为master。

    这种主从的配置方式存在一定的安全风险,由于Redis的主从复制是异步进行的, 可能会发生多个客户端同时持有一个锁的现象。

    此类场景是非常典型的竞态模型:

    Client A 获得在master节点获得了锁

    在master将key备份到slave节点之前,master宕机

    slave 被提升为master

    Client B 在新的master节点处获得了锁,Client A也持有这个锁。

    如何正确实现单实例的锁

    在单redis实例中实现锁是分布式锁的基础,在解决前文提到的单实例的不足之前,我们先了解如何在单点中正确的实现锁。

    如果你的应用可以容忍偶尔发生竞态问题,那么单实例锁就足够了。

    我们通过以下命令对资源加锁

    SET resource_name my_random_value NX PX 30000

    SET NX 命令只会在Key不存在的时给key赋值,PX 命令通知redis保存这个key 30000ms。

    my_random_value必须是全局唯一的值。这个随机数在释放锁时保证释放锁操作的安全性。

    通过下面的脚本为申请成功的锁解锁:

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

    如果key对应的Value一致,则删除这个key。

    通过这个方式释放锁是为了避免client释放了其他client申请的锁。

    例如:

    Client A 获得了一个锁,

    当尝试释放锁的请求发送给Redis时被阻塞,没有及时到达Redis。

    锁定时间超时,Redis认为锁的租约到期,释放了这个锁。

    client B 重新申请到了这个锁

    client A的解锁请求到达,将Client B锁定的key解锁

    Client C 也获得了锁

    Client B client C 同时持有锁。

    通过执行上面脚本的方式释放锁,Client的解锁操作只会解锁自己曾经加锁的资源。

    官方推荐通从 /dev/urandom/中取20个byte作为随机数或者采用更加简单的方式, 例如使用RC4加密算法在/dev/urandom中得到一个种子(Seed),然后生成一个伪随机流。

    也可以用更简单的使用时间戳+客户端编号的方式生成随机数,

    这种方式的安全性较差一些,但是对于绝大多数的场景来说也已经足够安全了。

    PX 操作后面的参数代表的是这key的存活时间,称作锁过期时间。

    当资源被锁定超过这个时间,锁将自动释放。

    获得锁的客户端如果没有在这个时间窗口内完成操作,就可能会有其他客户端获得锁,引起争用问题。

    通过上面的两个操作,我们可以完成获得锁和释放锁操作。如果这个系统不宕机,那么单点的锁服务已经足够安全,接下来我们开始把场景扩展到分布式系统。

    RedLock算法介绍

    下面例子中的分布式环境包含N个Redis Master节点,这些节点相互独立,无需备份。这些节点尽可能相互隔离的部署在不同的物理机或虚拟机上(故障隔离)。

    节点数量暂定为5个(在需要投票的集群中,5个节点的配置是比较合理的最小配置方式)。获得锁和释放锁的方式仍然采用之前介绍的方法。

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

    得到本地时间

    Client使用相同的key和随机数,按照顺序在每个Master实例中尝试获得锁。在获得锁的过程中,为每一个锁操作设置一个快速失败时间(如果想要获得一个10秒的锁, 那么每一个锁操作的失败时间设为5-50ms)。

    这样可以避免客户端与一个已经故障的Master通信占用太长时间,通过快速失败的方式尽快的与集群中的其他节点完成锁操作。

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

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

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

    RedLock能保证锁同步吗?

    这个算法成立的一个条件是:即使集群中没有同步时钟,各个进程的时间流逝速度也要大体一致,并且误差与锁存活时间相比是比较小的。实际应用中的计算机也能满足这个条件:各个计算机中间有几毫秒的时钟漂移(clock drift)。

    失败重试机制

    如果一个Client无法获得锁,它将在一个随机延时后开始重试。使用随机延时的目的是为了与其他申请同一个锁的Client错开申请时间,减少脑裂(split brain)发生的可能性。

    三个Client同时尝试获得锁,分别获得了2,2,1个实例中的锁,三个锁请求全部失败。

    一个client在全部Redis实例中完成的申请时间越短,发生脑裂的时间窗口越小。所以比较理想的做法是同时向N个Redis实例发出异步的SET请求。

    当Client没有在大多数Master中获得锁时,立即释放已经取得的锁时非常必要的。(PS.当极端情况发生时,比如获得了部分锁以后,client发生网络故障,无法再释放锁资源。

    那么其他client重新获得锁的时间将是锁的过期时间)。

    无论Client认为在指定的Master中有没有获得锁,都需要执行释放锁操作。

    RedLock算法安全性分析

    我们将从不同的场景分析RedLock算法是否足够安全。首先我们假设一个client在大多数的Redis实例中取得了锁,

    那么:

    每个实例中的锁的剩余存活时间相等为TTL。

    每个锁请求到达各个Redis实例中的时间有差异。

    第一个锁成功请求最先在T1后返回,最后返回的请求在T2后返回。(T1,T2都小于最大失败时间)

    并且每个实例之间存在时钟漂移CLOCK_DRIFT(Time Drift)。

    于是,最先被SET的锁将在TTL-(T2-T1)-CLOCK_DIRFT后自动过期,其他的锁将在之后陆续过期。

    所以可以得到结论:所有的key这段时间内是同时被锁住的。

    在这段时间内,一半以上的Redis实例中这个key都处在被锁定状态,其他的客户端无法获得这个锁。

    锁的可用性分析(Liveness)

    分布式锁系统的可用性主要依靠以下三种机制

    锁的自动释放(key expire),最终锁将被释放并且被再次申请。

    客户端在未申请到锁以及申请到锁并完成任务后都将进行释放锁的操作,所以大部分情况下都不需要等待到锁的自动释放期限,其他client即可重新申请到锁。

    假设一个Client在大多数Redis实例中申请锁请求所成功花费的时间为Tac。那么如果某个Client第一次没有申请到锁,需要重试之前,必须等待一段时间T。T需要远大于Tac。 因为多个Client同时请求锁资源,他们有可能都无法获得一半以上的锁,导致脑裂双方均失败。设置较久的重试时间是为了减少脑裂产生的概率。

    如果一直持续的发生网络故障,那么没有客户端可以申请到锁。分布式锁系统也将无法提供服务直到网络故障恢复为止。

    性能,故障恢复与文件同步

    用户使用redis作为锁服务的主要优势是性能。其性能的指标有两个

    加锁和解锁的延迟

    每秒可以进行多少加锁和解锁操作

    所以,在客户端与N个Redis节点通信时,必须使用多路发送的方式(multiplex),减少通信延时。

    为了实现故障恢复还需要考虑数据持久化的问题。

    我们还是从某个特定的场景分析:

    Redis实例的配置不进行任何持久化,集群中5个实例 M1,M2,M3,M4,M5

    client A获得了M1,M2,M3实例的锁。

    此时M1宕机并重启。

    由于没有进行持久化,M1重启后不存在任何KEY

    client B获得M4,M5和重启后的M1中的锁。

    此时client A 和Client B 同时获得锁

    如果使用AOF的方式进行持久化,情况会稍好一些。例如我们可以向某个实例发送shutdown和restart命令。即使节点被关闭,EX设置的时间仍在计算,锁的排他性仍能保证。

    但当Redis发生电源瞬断的情况又会遇到有新的问题出现。如果Redis配置中的进行磁盘持久化的时间是每分钟进行,那么会有部分key在重新启动后丢失。

    如果为了避免key的丢失,将持久化的设置改为Always,那么性能将大幅度下降。

    另一种解决方案是在这台实例重新启动后,令其在一定时间内不参与任何加锁。在间隔了一整个锁生命周期后,重新参与到锁服务中。这样可以保证所有在这台实例宕机期间内的key都已经过期或被释放。

    延时重启机制能够保证Redis即使不使用任何持久化策略,仍能保证锁的可靠性。但是这种策略可能会牺牲掉一部分可用性。

    例如集群中超过半数的实例都宕机了,那么整个分布式锁系统需要等待一整个锁有效期的时间才能重新提供锁服务。

    使锁算法更加可靠:锁续约

    如果Client进行的工作耗时较短,那么可以默认使用一个较小的锁有效期,然后实现一个锁续约机制。

    当一个Client在工作计算到一半时发现锁的剩余有效期不足。可以向Redis实例发送续约锁的Lua脚本。如果Client在一定的期限内(耗间与申请锁的耗时接近)成功的续约了半数以上的实例,那么续约锁成功。

    为了提高系统的可用性,每个Client申请锁续约的次数需要有一个最大限制,避免其不断续约造成该key长时间不可用。

    展开全文
  • 1 前言 今天开始来和大家一起学习一下Redis实际应用篇,会写几个Redis的常见应用。...结合笔者的日常工作,今天和大家一起研究下基于Redis的分布式锁和Redlock算法的一些事情。 2.初识锁 1. 锁的双面性 ...

    1 前言

    今天开始来和大家一起学习一下Redis实际应用篇,会写几个Redis的常见应用。

    在我看来Redis最为典型的应用就是作为分布式缓存系统,其他的一些应用本质上并不是杀手锏功能,是基于Redis支持的数据类型和分布式架构来实现的,属于小而美的应用。

    结合笔者的日常工作,今天和大家一起研究下基于Redis的分布式锁和Redlock算法的一些事情

    2.初识锁

    1. 锁的双面性

    现在我们写的程序基本上都有一定的并发性,要么单台多进线程、要么多台机器集群化,在仅读的场景下是不需要加锁的,因为数据是一致的,在读写混合或者写场景下如果不加以限制和约束就会造成写混乱数据不一致的情况。

    如果业务安全和正确性无法保证,再多的并发也是无意义的。 

    这个不由得让我想起一个趣图:

    高并发多半是考验你们公司的基础架构是否强悍,合理正确地使用锁才是个人能力的体现。

    凡事基本上都是双面的,锁可以在一定程度上保证数据的一致性,但是锁也意味着维护和使用的复杂性,当然也伴随着性能的损耗,我见过的最大的锁可能就是CPython解释器的全局解释器锁GIL了。

    没办法 好可怕 那个锁 不像话--《说锁就锁》

    锁使用不当不但解决不了数据混乱问题,甚至会带来诸如死锁等更多问题,通俗地说死锁现象:

     

    几年前会出现这样的场景:在异地需要买火车票回老家,但是身份证丢了无法购票,补办身份证又需要本人坐火车回老家户籍管理处,就这样生活太难。

    2. 无锁化编程

    既然锁这么难以把控,那不得不思考有没有无锁的高并发。

    无锁编程也是一个非常有意思的话题,后续可以写一篇聊聊这个话题,本次就只提一下,要打开思路,不要被困在凡是并发必须加锁的思维定势

    在某些特定场景下会选择一种并行转串行的思路,从而尽量避免锁的使用,举个栗子:

     

    Post请求:http://abc.def/setdata?reqid=abc123789def&dbname=bighero

    假如有一个上述的post请求的URI部分是个覆盖写操作,reqid=abc123789def,服务部署在多台机器,在大前端将流量转发到Nginx之后根据reqid进行哈希,Nginx的配置大概是这样的:

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    upstream myservice{  #根据参数进行Hash分配  hash $urlkey;  server localhost:5000;  server localhost:5001;  server localhost:5002;}

    经过Nginx负载均衡相同reqid的请求将被转发到一台机器上,当然你可能会说如果集群的机器动态调整呢?我只能说不要考虑那么多那么充分,工程化去设计即可。

    然而转发到一台机器仍然无法保证串行处理,因为单机仍然是多线程的,我们仍然需要将所有的reqid数据放到同一个线程处理,最终保证线程内串行,这个就需要借助于线程池的管理者Disper按照reqid哈希取模来进行多线程的负载均衡。

    经过Nginx和线程内负载均衡,最终相同的reqid都将在线程内串行处理,有效避免了锁的使用,当然这种设计可能在reqid不均衡时造成线程饥饿,不过高并发大量请求的情况下还是可以的。

    只描述不画图 就等于没说:

     

    3. 单机锁和分布式锁

    锁依据使用范围可简单分为:单机锁和分布式锁

    Linux提供系统级单机锁,这类锁可以实现线程同步和互斥资源的共享,单机锁实现了机器内部线程之间对共享资源的并发控制。

    分布式部署高并发场景下,经常会遇到资源的互斥访问的问题,最有效最普遍的方法是给共享资源或者对共享资源的操作加一把锁。

    分布式锁是控制分布式系统之间同步访问共享资源的一种方式,用于在分布式系统中协调他们之间的动作。

    3.分布式锁

    1. 分布式锁的实现简介

    分布式CAP理论告诉我们需要做取舍:

     

    任何一个分布式系统都无法同时满足一致性Consistency、可用性Availability和分区容错性Partition Tolerance三个方面,最多只能同时满足两项。

    在互联网领域的绝大多数的场景中,都需要牺牲强一致性来换取系统的高可用性,系统往往只保证最终一致性。在很多场景中为了保证数据的最终一致性,需要很多的技术方案来支持,比如分布式事务、分布式锁等。

    分布式锁一般有三种实现方式:

    • 基于数据库
      在数据库中创建一张表,表里包含方法名等字段,并且在方法名字段上面创建唯一索引,执行某个方法需要使用此方法名向表中插入数据,成功插入则获取锁,执行结束则删除对应的行数据释放锁

    • 基于缓存数据库Redis
      Redis性能好并且实现方便,但是单节点的分布式锁在故障迁移时产生安全问题,Redlock是Redis的作者 Antirez 提出的集群模式分布式锁,基于N个完全独立的Redis节点实现分布式锁的高可用

    • 基于ZooKeeper
      ZooKeeper 是以 Paxos 算法为基础的分布式应用程序协调服务,为分布式应用提供一致性服务的开源组件

    2. 分布式锁需要具备的条件

    分布式锁在应用于分布式系统环境相比单机锁更为复杂,本文讲述基于Redis的分布式锁实现,该锁需要具备一些特性:

    • 互斥性
      在任意时刻,只有一个客户端能持有锁 其他尝试获取锁的客户端都将失败而返回或阻塞等待

    • 健壮性
      一个客户端持有锁的期间崩溃而没有主动释放锁,也需要保证后续其他客户端能够加锁成功,就像C++的智能指针来避免内存泄漏一样

    • 唯一性
      加锁和解锁必须是同一个客户端,客户端自己不能把别人加的锁给释放了,自己持有的锁也不能被其他客户端释放

    • 高可用
      不必依赖于全部Redis节点正常工作,只要大部分的Redis节点正常运行,客户端就可以进行加锁和解锁操作

    3. 基于单Redis节点的分布式锁

    本文的重点是基于多Redis节点的Redlock算法,不过在展开这个算法之前,有必要提一下单Redis节点分布式锁原理以及演进,因为Redlock算法是基于此改进的

    最初分布式锁借助于setnx和expire命令,但是这两个命令不是原子操作,如果执行setnx之后获取锁但是此时客户端挂掉,这样无法执行expire设置过期时间就导致锁一直无法被释放,因此在2.8版本中Antirez为setnx增加了参数扩展,使得setnx和expire具备原子操作性

    在单Matster-Slave的Redis系统中,正常情况下Client向Master获取锁之后同步给Slave,如果Client获取锁成功之后Master节点挂掉,并且未将该锁同步到Slave,之后在Sentinel的帮助下Slave升级为Master但是并没有之前未同步的锁的信息,此时如果有新的Client要在新Master获取锁,那么将可能出现两个Client持有同一把锁的问题,来看个图来想下这个过程:

    为了保证自己的锁只能自己释放需要增加唯一性的校验,综上基于单Redis节点的获取锁和释放锁的简单过程如下:

    // 获取锁 unique_value作为唯一性的校验
    SET resource_name unique_value NX PX 30000
    
    // 释放锁 比较unique_value是否相等 避免误释放
    if redis.call("get",KEYS[1]) == ARGV[1] then
        return redis.call("del",KEYS[1])
    else
        return 0
    end
    

    这就是基于单Redis的分布式锁的几个要点。

    4.Redlock算法过程

    Redlock算法是Antirez在单Redis节点基础上引入的高可用模式

    在Redis的分布式环境中,我们假设有N个完全互相独立的Redis节点,在N个Redis实例上使用与在Redis单实例下相同方法获取锁和释放锁。

    现在假设有5个Redis主节点(大于3的奇数个),这样基本保证他们不会同时都宕掉,获取锁和释放锁的过程中,客户端会执行以下操作:

    • 1.获取当前Unix时间,以毫秒为单位

    • 2.依次尝试从5个实例,使用相同的key和具有唯一性的value获取锁
      当向Redis请求获取锁时,客户端应该设置一个网络连接和响应超时时间,这个超时时间应该小于锁的失效时间,这样可以避免客户端死等

    • 3.客户端使用当前时间减去开始获取锁时间就得到获取锁使用的时间。当且仅当从半数以上的Redis节点取到锁,并且使用的时间小于锁失效时间时,锁才算获取成功

    • 4.如果取到了锁,key的真正有效时间等于有效时间减去获取锁所使用的时间,这个很重要

    • 5.如果因为某些原因,获取锁失败(没有在半数以上实例取到锁或者取锁时间已经超过了有效时间),客户端应该在所有的Redis实例上进行解锁,无论Redis实例是否加锁成功,因为可能服务端响应消息丢失了但是实际成功了,毕竟多释放一次也不会有问题

    上述的5个步骤是Redlock算法的重要过程,也是面试的热点,有心的读者还是记录一下吧!

    5.Redlock算法是否安全的争论

    1.关于马丁·克莱普曼博士

    2016年2月8号分布式系统的专家马丁·克莱普曼博士(Martin Kleppmann)在一篇文章How to do distributed locking 指出分布式锁设计的一些原则并且对Antirez的Redlock算法提出了一些质疑。

    笔者找到了马丁·克莱普曼博士的个人网站以及一些简介,一起看下:

    搜狗翻译看一下:

    1.我是剑桥大学计算机科学与技术系的高级研究助理和附属讲师,由勒弗乌尔姆信托早期职业奖学金和艾萨克牛顿信托基金资助。我致力于本地优先的协作软件和分布式系统安全
    2.我也是剑桥科珀斯克里斯蒂学院计算机科学研究的研究员和主任,我在那里从事本科教学。
    3.2017年,我为奥雷利出版了一本名为《设计数据密集型应用》的书。它涵盖了广泛的数据库和分布式数据处理系统的体系结构,是该出版社最畅销书之一。
    4.我经常在会议上发言,我的演讲录音已经被观看了超过15万次。
    5.我参与过各种开源项目,包括自动合并、Apache Avro和Apache Samza。
    6.2007年至2014年间,我是一名工业软件工程师和企业家。我共同创立了Rapportive(2012年被领英收购)和Go Test(2009年被红门软件收购)。
    7.我创作了几部音乐作品,包括《二月之死》(德语),这是唐克·德拉克特对该书的音乐戏剧改编,于2007年首映,共有150人参与。

    大牛就是大牛,能教书、能出书、能写开源软件、能创业、能写音乐剧,优秀的人哪方面也优秀,服气了。

     

    2.马丁博士文章的主要观点

    马丁·克莱普曼在文章中谈及了分布式系统的很多基础问题,特别是分布式计算的异步模型,文章分为两大部分前半部分讲述分布式锁的一些原则,后半部分针对Redlock提出一些看法:

    • Martin指出即使我们拥有一个完美实现的分布式锁,在没有共享资源参与进来提供某种fencing栅栏机制的前提下,我们仍然不可能获得足够的安全性

    • Martin指出,由于Redlock本质上是建立在一个同步模型之上,对系统的时间有很强的要求,本身的安全性是不够的

    针对fencing机制马丁给出了一个时序图

    获取锁的客户端在持有锁时可能会暂停一段较长的时间,尽管锁有一个超时时间,避免了崩溃的客户端可能永远持有锁并且永远不会释放它,但是如果客户端的暂停持续的时间长于锁的到期时间,并且客户没有意识到它已经到期,那么它可能会继续进行一些不安全的更改,换言之由于客户端阻塞导致的持有的锁到期而不自知

    针对这种情况马丁指出要增加fencing机制,具体来说是fencing token隔离令牌机制,同样给出了一张时序图:

    客户端1获得锁并且获得序号为33的令牌,但随后它进入长时间暂停,直至锁超时过期,客户端2获取锁并且获得序号为34的令牌,然后将其写入发送到存储服务。随后,客户端1复活并将其写入发送到存储服务,然而存储服务器记得它已经处理了具有较高令牌号的写入34,因此它拒绝令牌33的请求
    Redlock算法并没有这种唯一且递增的fencing token生成机制,这也意味着Redlock算法不能避免由于客户端阻塞带来的锁过期后的操作问题,因此是不安全的。

    这个观点笔者觉得并没有彻底解决问题,因为如果客户端1的写入操作是必须要执行成功的,但是由于阻塞超时无法再写入同样就产生了一个错误的结果,客户端2将可能在这个错误的结果上进行操作,那么任何操作都注定是错误的

     

    3.马丁博士对Redlock的质疑

    马丁·克莱普曼指出Redlock是个强依赖系统时间的算法,这样就可能带来很多不一致问题,他给出了个例子一起看下:

    假设多节点Redis系统有五个节点A/B/C/D/E和两个客户端C1和C2,如果其中一个Redis节点上的时钟向前跳跃会发生什么?

    • 客户端C1获得了对节点A、B、c的锁定,由于网络问题,法到达节点D和节点E

    • 节点C上的时钟向前跳,导致锁提前过期

    • 客户端C2在节点C、D、E上获得锁定,由于网络问题,无法到达A和B

    • 客户端C1和客户端C2现在都认为他们自己持有锁

    分布式异步模型:
    上面这种情况之所以有可能发生,本质上是因为Redlock的安全性对Redis节点系统时钟有强依赖,一旦系统时钟变得不准确,算法的安全性也就无法保证。

    马丁其实是要指出分布式算法研究中的一些基础性问题,好的分布式算法应该基于异步模型,算法的安全性不应该依赖于任何记时假设

    分布式异步模型中进程和消息可能会延迟任意长的时间,系统时钟也可能以任意方式出错。这些因素不应该影响它的安全性,只可能影响到它的活性,即使在非常极端的情况下,算法最多是不能在有限的时间内给出结果,而不应该给出错误的结果,这样的算法在现实中是存在的比如Paxos/Raft,按这个标准衡量Redlock的安全级别是达不到的。

    4.马丁博士文章结论和基本观点

    马丁表达了自己的观点,把锁的用途分为两种:

    • 效率第一
      使用分布式锁只是为了协调多个客户端的一些简单工作,锁偶尔失效也会产生其它的不良后果,就像你收发两份相同的邮件一样,无伤大雅

    • 正确第一
      使用分布式锁要求在任何情况下都不允许锁失效的情况发生,一旦发生失效就可能意味着数据不一致、数据丢失、文件损坏或者其它严重的问题,就像给患者服用重复剂量的药物一样,后果严重

    最后马丁出了如下的结论:

    • 为了效率而使用分布式锁
      单Redis节点的锁方案就足够了Redlock则是个过重而昂贵的设计

    • 为了正确而使用分布式锁
      Redlock不是建立在异步模型上的一个足够强的算法,它对于系统模型的假设中包含很多危险的成分

    马丁认为Redlock算法是个糟糕的选择,因为它不伦不类:出于效率选择来说,它过于重量级和昂贵,出于正确性选择它又不够安全。

    6.Antirez的反击

    马丁的那篇文章是在2016.2.8发表之后Antirez反应很快,他发表了"Is Redlock safe?"进行逐一反驳,文章地址如下:

     

    http://antirez.com/news/101

    Antirez认为马丁的文章对于Redlock的批评可以概括为两个方面:

    • 带有自动过期功能的分布式锁,必须提供某种fencing栅栏机制来保证对共享资源的真正互斥保护,Redlock算法提供不了这样一种机制

    • Redlock算法构建在一个不够安全的系统模型之上,它对于系统的记时假设有比较强的要求,而这些要求在现实的系统中是无法保证的

    Antirez对这两方面分别进行了细致地反驳。

    关于fencing机制

    Antirez提出了质疑:既然在锁失效的情况下已经存在一种fencing机制能继续保持资源的互斥访问了,那为什么还要使用一个分布式锁并且还要求它提供那么强的安全性保证呢?

    退一步讲Redlock虽然提供不了递增的fencing token隔离令牌,但利用Redlock产生的随机字符串可以达到同样的效果,这个随机字符串虽然不是递增的,但却是唯一的。

    关于记时假设

    Antirez针对算法在记时模型假设集中反驳,马丁认为Redlock失效情况主要有三种:

    • 1.时钟发生跳跃

    • 2.长时间的GC pause

    • 3.长时间的网络延迟

    后两种情况来说,Redlock在当初之处进行了相关设计和考量,对这两种问题引起的后果有一定的抵抗力。
    时钟跳跃对于Redlock影响较大,这种情况一旦发生Redlock是没法正常工作的。
    Antirez指出Redlock对系统时钟的要求并不需要完全精确,只要误差不超过一定范围不会产生影响,在实际环境中是完全合理的,通过恰当的运维完全可以避免时钟发生大的跳动

    7.马丁的总结和思考

    分布式系统本身就很复杂,机制和理论的效果需要一定的数学推导作为依据,马丁和Antirez都是这个领域的专家,对于一些问题都会有自己的看法和思考,更重要的是很多时候问题本身并没有完美的解决方案

    这次争论是布式系统领域非常好的一次思想的碰撞,很多网友都发表了自己的看法和认识,马丁博士也在Antirez做出反应一段时间之后再次发表了自己的一些观点:

     

    For me, this is the most important point: I don’t care who is right or wrong in this debate — I care about learning from others’ work, so that we can avoid repeating old mistakes, and make things better in future. So much great work has already been done for us: by standing on the shoulders of giants, we can build better software.

     

    By all means, test ideas by arguing them and checking whether they stand up to scrutiny by others. That’s part of the learning process. But the goal should be to learn, not to convince others that you are right. Sometimes that just means to stop and think for a while.

    简单翻译下就是:
    对马丁而言并不在乎谁对谁错,他更关心于从他人的工作中汲取经验来避免自己的错误重复工作,正如我们是站在巨人的肩膀上才能做出更好的成绩。

    另外通过别人的争论和检验才更能让自己的想法经得起考验,我们的目标是相互学习而不是说服别人相信你是对的,所谓一人计短思考辩驳才能更加接近真理

    在Antirez发表文章之后世界各地的分布式系统专家和爱好者都积极发表自己的看法,笔者在评论中发现了一个熟悉的名字:

    8.巨人的肩膀

    • https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

    • http://antirez.com/news/101

    • http://zhangtielei.com/posts/blog-redlock-reasoning.html

    • http://zhangtielei.com/posts/blog-redlock-reasoning-part2.html

    铁蕾大神的两篇文章写的非常好,本文从中做了很多参考,也是铁蕾大神的文章让笔者了解到这场精彩的华山论剑,感兴趣的可以直接搜索阅读参考3和4。

    展开全文
  • 在多线程共享临界资源的场景下,分布式锁是一种非常重要的组件。 许多库使用不同的方式使用redis实现一个分布式锁管理。...在介绍RedLock算法之前,我们列出了一些已经实现了分布式锁的类库供大家参考。 Redl...

    在多线程共享临界资源的场景下,分布式锁是一种非常重要的组件。
    许多库使用不同的方式使用redis实现一个分布式锁管理。
    其中有一部分简单的实现方式可靠性不足,可以通过一些简单的修改提高其可靠性。
    这篇文章介绍了一种指导性的redis分布式锁算法RedLock,RedLock比起单实例的实现方式更加安全。

    在介绍RedLock算法之前,我们列出了一些已经实现了分布式锁的类库供大家参考。

    Redlock-rb (Ruby 实现).
    Redlock-py (Python 实现)
    Redlock-php (PHP 实现)
    PHPRedisMutex (further 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 实现)

    分布式锁应该具有的特性(Safety & Liveness)

    我们将从三个特性的角度出发来设计RedLock模型:

    1. 安全性(Safety):在任意时刻,只有一个客户端可以获得锁(排他性)。
    2. 避免死锁:客户端最终一定可以获得锁,即使锁住某个资源的客户端在释放锁之前崩溃或者网络不可达。
    3. 容错性:只要Redsi集群中的大部分节点存活,client就可以进行加锁解锁操作。

    故障切换(failover)实现方式的局限性

    通过Redis为某个资源加锁的最简单方式就是在一个Redis实例中使用过期特性(expire)创建一个key, 如果获得锁的客户端没有释放锁,那么在一定时间内这个Key将会自动删除,避免死锁。
    这种做法在表面上看起来可行,但分布式锁作为架构中的一个组件,为了避免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也持有这个锁。

    如何正确实现单实例的锁

    在单redis实例中实现锁是分布式锁的基础,在解决前文提到的单实例的不足之前,我们先了解如何在单点中正确的实现锁。
    如果你的应用可以容忍偶尔发生竞态问题,那么单实例锁就足够了。

    我们通过以下命令对资源加锁
    SET resource_name my_random_value NX PX 30000
    SET NX 命令只会在Key不存在的时给key赋值,PX 命令通知redis保存这个key 30000ms。
    my_random_value必须是全局唯一的值。这个随机数在释放锁时保证释放锁操作的安全性。

    通过下面的脚本为申请成功的锁解锁:
    if redis.call("get",KEYS[1]) == ARGV[1] then return redis.call("del",KEYS[1]) else return 0 end

    如果key对应的Value一致,则删除这个key。

    通过这个方式释放锁是为了避免client释放了其他client申请的锁。
    例如:

    1. Client A 获得了一个锁,
    2. 当尝试释放锁的请求发送给Redis时被阻塞,没有及时到达Redis。
    3. 锁定时间超时,Redis认为锁的租约到期,释放了这个锁。
    4. client B 重新申请到了这个锁
    5. client A的解锁请求到达,将Client B锁定的key解锁
    6. Client C 也获得了锁
    7. Client B client C 同时持有锁。

    通过执行上面脚本的方式释放锁,Client的解锁操作只会解锁自己曾经加锁的资源。
    官方推荐通从 /dev/urandom/中取20个byte作为随机数或者采用更加简单的方式, 例如使用RC4加密算法在/dev/urandom中得到一个种子(Seed),然后生成一个伪随机流。
    也可以用更简单的使用时间戳+客户端编号的方式生成随机数,
    这种方式的安全性较差一些,但是对于绝大多数的场景来说也已经足够安全了。

    PX 操作后面的参数代表的是这key的存活时间,称作锁过期时间。

    1. 当资源被锁定超过这个时间,锁将自动释放。
    2. 获得锁的客户端如果没有在这个时间窗口内完成操作,就可能会有其他客户端获得锁,引起争用问题。

    通过上面的两个操作,我们可以完成获得锁和释放锁操作。如果这个系统不宕机,那么单点的锁服务已经足够安全,接下来我们开始把场景扩展到分布式系统。


    RedLock算法介绍

    下面例子中的分布式环境包含N个Redis Master节点,这些节点相互独立,无需备份。这些节点尽可能相互隔离的部署在不同的物理机或虚拟机上(故障隔离)。
    节点数量暂定为5个(在需要投票的集群中,5个节点的配置是比较合理的最小配置方式)。获得锁和释放锁的方式仍然采用之前介绍的方法。

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

    1. 得到本地时间
    2. Client使用相同的key和随机数,按照顺序在每个Master实例中尝试获得锁。在获得锁的过程中,为每一个锁操作设置一个快速失败时间(如果想要获得一个10秒的锁, 那么每一个锁操作的失败时间设为5-50ms)。
      这样可以避免客户端与一个已经故障的Master通信占用太长时间,通过快速失败的方式尽快的与集群中的其他节点完成锁操作。
    3. 客户端计算出与master获得锁操作过程中消耗的时间,当且仅当Client获得锁消耗的时间小于锁的存活时间,并且在一半以上的master节点中获得锁。才认为client成功的获得了锁。
    4. 如果已经获得了锁,Client执行任务的时间窗口是锁的存活时间减去获得锁消耗的时间。
    5. 如果Client获得锁的数量不足一半以上,或获得锁的时间超时,那么认为获得锁失败。客户端需要尝试在所有的master节点中释放锁, 即使在第二步中没有成功获得该Master节点中的锁,仍要进行释放操作。

    RedLock能保证锁同步吗?

    这个算法成立的一个条件是:即使集群中没有同步时钟,各个进程的时间流逝速度也要大体一致,并且误差与锁存活时间相比是比较小的。实际应用中的计算机也能满足这个条件:各个计算机中间有几毫秒的时钟漂移(clock drift)。


    失败重试机制

    如果一个Client无法获得锁,它将在一个随机延时后开始重试。使用随机延时的目的是为了与其他申请同一个锁的Client错开申请时间,减少脑裂(split brain)发生的可能性。

    三个Client同时尝试获得锁,分别获得了2,2,1个实例中的锁,三个锁请求全部失败

    一个client在全部Redis实例中完成的申请时间越短,发生脑裂的时间窗口越小。所以比较理想的做法是同时向N个Redis实例发出异步的SET请求
    当Client没有在大多数Master中获得锁时,立即释放已经取得的锁时非常必要的。(PS.当极端情况发生时,比如获得了部分锁以后,client发生网络故障,无法再释放锁资源。
    那么其他client重新获得锁的时间将是锁的过期时间)。
    无论Client认为在指定的Master中有没有获得锁,都需要执行释放锁操作

    RedLock算法安全性分析

    我们将从不同的场景分析RedLock算法是否足够安全。首先我们假设一个client在大多数的Redis实例中取得了锁,
    那么:

    1. 每个实例中的锁的剩余存活时间相等为TTL。
    2. 每个锁请求到达各个Redis实例中的时间有差异。
    3. 第一个锁成功请求最先在T1后返回,最后返回的请求在T2后返回。(T1,T2都小于最大失败时间)
    4. 并且每个实例之间存在时钟漂移CLOCK_DRIFT(Time Drift)。

    于是,最先被SET的锁将在TTL-(T2-T1)-CLOCK_DIRFT后自动过期,其他的锁将在之后陆续过期。
    所以可以得到结论:所有的key这段时间内是同时被锁住的。
    在这段时间内,一半以上的Redis实例中这个key都处在被锁定状态,其他的客户端无法获得这个锁。

    锁的可用性分析(Liveness)

    分布式锁系统的可用性主要依靠以下三种机制

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

    如果一直持续的发生网络故障,那么没有客户端可以申请到锁。分布式锁系统也将无法提供服务直到网络故障恢复为止。

    性能,故障恢复与文件同步

    用户使用redis作为锁服务的主要优势是性能。其性能的指标有两个

    1. 加锁和解锁的延迟
    2. 每秒可以进行多少加锁和解锁操作

    所以,在客户端与N个Redis节点通信时,必须使用多路发送的方式(multiplex),减少通信延时。

    为了实现故障恢复还需要考虑数据持久化的问题。

    我们还是从某个特定的场景分析:
    <code>
    Redis实例的配置不进行任何持久化,集群中5个实例 M1,M2,M3,M4,M5
    client A获得了M1,M2,M3实例的锁。
    此时M1宕机并重启。
    由于没有进行持久化,M1重启后不存在任何KEY
    client B获得M4,M5和重启后的M1中的锁。
    此时client A 和Client B 同时获得锁
    </code>

    如果使用AOF的方式进行持久化,情况会稍好一些。例如我们可以向某个实例发送shutdownrestart命令。即使节点被关闭,EX设置的时间仍在计算,锁的排他性仍能保证。

    但当Redis发生电源瞬断的情况又会遇到有新的问题出现。如果Redis配置中的进行磁盘持久化的时间是每分钟进行,那么会有部分key在重新启动后丢失。
    如果为了避免key的丢失,将持久化的设置改为Always,那么性能将大幅度下降。

    另一种解决方案是在这台实例重新启动后,令其在一定时间内不参与任何加锁。在间隔了一整个锁生命周期后,重新参与到锁服务中。这样可以保证所有在这台实例宕机期间内的key都已经过期或被释放。

    延时重启机制能够保证Redis即使不使用任何持久化策略,仍能保证锁的可靠性。但是这种策略可能会牺牲掉一部分可用性。
    例如集群中超过半数的实例都宕机了,那么整个分布式锁系统需要等待一整个锁有效期的时间才能重新提供锁服务。


    使锁算法更加可靠:锁续约

    如果Client进行的工作耗时较短,那么可以默认使用一个较小的锁有效期,然后实现一个锁续约机制。

    当一个Client在工作计算到一半时发现锁的剩余有效期不足。可以向Redis实例发送续约锁的Lua脚本。如果Client在一定的期限内(耗间与申请锁的耗时接近)成功的续约了半数以上的实例,那么续约锁成功。

    为了提高系统的可用性,每个Client申请锁续约的次数需要有一个最大限制,避免其不断续约造成该key长时间不可用。

     



    作者:我叫刘大饼
    链接:https://www.jianshu.com/p/fba7dd6dcef5
    来源:简书
    简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。

    展开全文
  • RedLock.net 在C#中的实现。 利用了出色的库。 分布式锁可用于确保在任何给定时间仅一个进程正在使用特定资源(即使进程在不同的计算机上运行)。 使用NuGet可以使用搜索 。 注意: RedLock 2.2.0+需要...
  • 三、RedLock 算法 一、简介 什么是分布式锁? 分布式锁就是保证某个时刻,只能有一个进程访问共享资源。比如在分布式环境下,要保证定时调度不能重复执行、执行扣减库存等操作不能同时有两个进程在执行,这些都...
  • 关于分布式锁的实现方式思路已经在上一篇文章写过了,一般是基于redis或者zookeeper实现的 ... 但是真正应用中通常还要考虑redis和zookeeper集群环境下怎么去...redis集群分布式锁实现算法:RedLock算法 为什么需要Red
  • RedLock算法如何落地?前言Redis的高可用(容错性)如何实现?RedLock算法如何落地? 前言 每日一题专栏 Redis的高可用(容错性)如何实现?RedLock算法如何落地? Redis的数据同步是异步的。如果加锁数据还没有从...
  • NodeJS 基于redis的分布式锁的实现(Redlock算法) 1. 前言 开发时,碰到互斥问题,需要保证在分布式环境下,避免重复性操作修改用户状态,如:用户订单状态,购票时,修改票的余额等 2. 分布式锁的条件 分布式锁...
  • RedLock算法的基本思路是让客户端依次和多个redis实例请求加锁,对于单个节点加锁有可能成功也有可能失败,最后统计一下成功加锁的节点数量,如果对超过一半的节点返回成功那就可以认为这个分布式锁成功加锁了;...
  • Redlock 算法算法的分布式版本中,假设有 N 个 Redis 节点。而且这些节点全都是相互独立的,都是 master 节点,且不使用分布式协调方案。假设 N=5 ,即部署 5 个 Redis master 节点在不同的机器(或虚拟机)上。...
  • 分布式锁之Redis RedLock算法

    千次阅读 2019-04-08 20:25:02
    三、多Redis实例解决单点故障-----RedLock算法 一个Client想要获得一个锁需要以下几个操作: 1、得到本地时间 2、Client使用相同的key和随机数,按照顺序在每个Master实例中尝试获得锁。在获得锁的过程中,为每...
  • 单节点锁,主从拷贝模式下的锁失效问题: 1.客户端A从master上获取了锁。...RedLock中,为了防止死锁,锁是具有过期时间的。这个过期时间被 Martin 抓住了小辫子。 如果 Client 1 在持有锁的时候,发生..
  • 分布式锁方案—redlock算法

    千次阅读 2017-07-14 23:09:50
    二、Redlock 实现方案 Redlock 是 redis 作者 antirez 大神在 redis 官网中给出的一种基于 redis 的分布式锁方案。直白点说,就是采用 N (通常是 5 )个独立的 redis 节点,同时 ...
  • 在不同进程需要互斥地访问共享资源时,分布式锁是一种非常有用的... 这篇文章的目的就是尝试提出一种官方权威的用Redis实现分布式锁管理器的算法,我们把这个算法称为RedLockRedlock是redis官方提出的实现分布式...
  • 但这种实现是基于单个redis服务,若redis服务不可用,显然所有客户端无法加锁,该实现还未到高可用的水平,因此需要进一步提升分布式的锁的逻辑,好在redis官方提供了相应的权威描述并称之为Redlock,具体参考文章:...
  • 否则最好还是使用本文后续将会提到的 Redlock 算法。 单实例情况下正确的实现 在解决单实例单点故障的限制前,我们先来看看如何正确地执行它 获取一个锁的方式: set resource_name my_random_value NX PX ...
  • 这篇文章的目的就是尝试提出一种官方权威的用Redis实现分布式锁管理器的算法,我们把这个算法称为RedLockRedlock是redis官方提出的实现分布式锁管理器的算法。这个算法会比一般的普通方法更加安全可靠。关于这...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 272
精华内容 108
关键字:

redlock算法