搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 也输思雪计算机之路 > 【分布式系统-秒杀系统架构设计】第二章 paxos算法-一致性协议

【分布式系统-秒杀系统架构设计】第二章 paxos算法-一致性协议

也输思雪计算机之路 2019-03-15
举报

一 缘起

本来不打算提这个,但今早开虚拟机,打开共享目录时想到了这个,所以刚好可以谈一谈这个,放在“秒杀系统架构设计”系列是算是给读这个系列的朋友的一个彩蛋吧。这篇文章可能会打开你的分布式系统架构设计的视野或者说让你又不一样的想法。

分布式系统,分布式从定义上来说是物理介质分布在不同地方。延伸到IT互联网行业,就是微服务架构。分布式系统牵涉到的东西很多,其中有一个是,分布式系统中各个节点怎么保证数据一致性呢?也即是这些节点的数据如何保证是一样的,或者说降低点,这些数据如何满足业务要求?其实不光分布式系统有这问题,连计算机本身也会有,计算机本身也会保证一致性,比如cpu用到的缓存一致性算法MESI协议(后续会在“缓存系统架构设计”系列“缓存一致性”章节细讲)

二 paxos算法

      paxos算法是莱斯利·兰伯特(Leslie Lamport)在1990年提出的一种一致性协议算法。在他论文中是通过下面这个例子来说明的:

      希腊岛屿Paxon 上的执法者(legislators,后面称为牧师priest)在议会大厅(chamber)中表决通过法律,并通过服务员传递纸条的方式交流信息,每个执法者会将通过的法律记录在自己的账目(ledger)上。问题在于执法者和服务员都不可靠,他们随时会因为各种事情离开议会大厅,并随时可能有新的执法者进入议会大厅进行法律表决,使用何种方式能够使得这个表决过程正常进行,且通过的法律不发生矛盾。   

      paxos 协议中有四种角色


     client 议题产生者,产生一个待分布式系统达成一致的值value

     proposer 提议者,用client产生的值value,向acceptor发出提议

    acceptor 决策者,决定是否接受proposer的提议,大多数接受了提议,结果达成一致,达成一致后的结果不可更改

     learner 决策学习者,学习最终达成一致的结果。一旦学习成功,关闭对应的paxos过程(paxos instance),并通知acceptor(或acceptor主动向learner获取)。


     第一阶段:prepare  

     1,client 产生一个值value,并传递给proposer    

    2,proposer接收到该值value后,生成一个全局性ID(该ID唯一自增),然后向集群中的acceptor发送prepare请求(带着ID)。

     3,acceptor收到请求后,检查ID有效性(假设之前接收到的ID为A,现在接收到的ID为B,如果B<=A ,则拒绝,返回值为A;反之则保存B,并拒绝以后ID小于等于B的请求)

     第二阶段:accept

     1,如果proposer接收到大多数拒绝请求,则返回第一阶段继续发送prepare请求(value值为最大ID的value值,没有则用之前自己产生的值value,且ID值增大)

     2,如果proposer接收到大多数接收请求,则后续的只能是学习

     上面这理解起来太晦涩了,有没通俗点的?

     牛家弯有一家大户人家,有一个女儿今年26岁,那长得一个美啊,这不正好到了婚嫁的年纪了嘛,就有很多人来提亲。她让家人来决定选择谁,有爸爸,妈妈,妹妹(这些都是acceptor),这三人吧只看钱,谁的钱多就答应谁,而且反复无常。

     看上了姑娘的男孩(client),就会去找一个媒人(proposer)帮忙带着聘礼去提亲,然后再正式订亲(签一个协议)。

      这天【提亲】, 白公子的媒人白大妈来提亲,白大妈带着聘礼16万(每人16万,总数48万),给爸爸,妈妈,妹妹,之前还没人来提亲,所以这三人都立即同意了,并且收下了聘礼16万(拿了个红本本记下来了账);下午,李公子的媒人也来了,带着聘礼8万,这三人一看,才8万,直接拒绝,哪凉快哪待着去吧,还说了句“呵呵,人家白公子那边可是带着16万呢”(而且一表人才)。

      【订亲】这可把白公子高兴惨了啊,立马第二天就和媒婆白大妈一起去牛家弯订亲(签协议),到了那边,说之前给了聘礼的,16万,爸爸,妈妈,妹妹三人都查了下确实收了16万(各16万),接收了,正式许配女儿给白公子,说以后你是我们牛家的人了。结果下午,李公子来了,经过昨天上一次拒绝,他媒婆下午带了17万去,那三人答应了他,但告诉他,你钱多,我们可以答应你,但我们已经答应过白公子了,而且白公子还带了辆车(三轮车)【正式许配女儿后才会知道!!!】,然后李公子媒婆想“哎,看看人家白公子,都知道带辆车”,我带辆三轮车去(之前可能是自行车),所以今下午又来了,他来了后(并带着和白公子一样的三轮车),说我交了聘礼的,17万,那三人一查,是17万,于是也接收了他,也说以后你是我们牛家的人了。(虽然这里白公子,李公子都被接收了,但白公子和李公子的车都是一样的三轮车,所以系统是一致的,ps:而且白公子有老婆了 (~<~) )

      第二天【提亲】,王公子的媒婆王大妈来了,但大女儿已经嫁了,没指望了,那转向二女儿吧,也是一个国色天香,于是,这次准备足了,媒婆李大妈带着聘礼6万(还是每人会给6万),分别找上爸爸,妈妈,妹妹,这次不错(没人之前来订二女儿的亲),同意了,并拿红本本记下聘礼6万。然后,王大妈高高兴兴的走了,结果不巧的是,刚走,这隔壁村的朱公子的媒人朱大妈来了,带着聘礼7万,找上爸爸,妈妈,妹妹,这三人一看,这聘礼比王公子那边多啊,就立马收下了聘礼,同意了。

      第三天【订亲】,这王公子和媒婆王大妈来到牛家弯,说,我叫了聘礼的,6万,那三人一看红本本记下的不是6万,而是7万,于是说“滚蛋,有人出了7万了”,拒绝了。结果,朱公子和媒婆来了,说,我交了聘礼的,7万,那三人一看红本本是7万,发现没错,于是,接收了,正式许配女儿给白公子,说以后你是我们牛家的人了。话说这王公子的媒婆。被拒绝后啊,那叫一个后悔,都怪那王公子抠门,于是又带着聘礼9万来,这三人一看9万,于是答应了,也说,但我们已经答应了朱公子,而且人家朱公子还带着一辆车(三菱suv),于是朱公子的媒婆,回去后也搞了辆一样的车,再去订亲,然后三人对照红本本确实是9万,于是也接收了,也说以后你是我们牛家的人了。(这里其实和上面一样李公子的环节,为了让更好理解,所以又加了刘公子加钱又回来)

       第四天【提亲】,这隔壁村的隔壁村的曾公子的媒婆曾大妈,也来提亲了,带着聘礼8万,大女儿和二女儿都嫁了,那就三女儿好了,这曾大妈先分别找了爸爸,妈妈,爸爸妈妈一看,三女儿之前也没人来提过亲,就答应了,并且记下了(拿红本本记下聘礼),然后再去找妹妹,结果不巧的是在她之前隔壁村的隔壁村的隔壁村的萧公子的媒人萧大妈带着聘礼8万(和曾公子媒人一样的聘礼)来提亲了,她先去找的妹妹,妹妹一看,所以答应了,并记下了;这时候曾大妈来找妹妹,说提亲,聘礼8万,结果妹妹一看8万,说“呵呵,人家萧公子也是8万”,拒绝了曾大妈,;然后萧大妈再去分别找爸爸,妈妈,但爸爸妈妈都拒绝了她,因为爸爸妈妈之前答应了曾公子的媒人曾大妈,这聘礼是8万,所以直接拒绝了。那么曾大妈得到了2票,而萧大妈得到了1票,2票大于1票,所以曾大妈可以进入第二阶段订亲,而萧大妈最终被拒绝(返回第一阶段,提亲)

       第五天【订亲】,曾公子和曾大妈去牛家弯,订亲了,说,分别找到爸爸,妈妈,妹妹说我交了聘礼的,结果爸爸,妈妈一查红本本,确实是8万,就都答应了,但妹妹没收到聘礼8万,没答应,不过得到了两票,所以,接收了,正式许配女儿给白公子,说以后你是我们牛家的人了。这里有个问题,另外一情况,如果萧公子的媒人萧大妈回去后,立马拿了聘礼9万去提亲(在曾公子来订亲之前来的),那么爸爸,妈妈,妹妹,会全部答应提亲,并会告诉他,女儿还没许配出去,然后等曾公子来了时,说我给了聘礼的,8万,结果爸爸妈妈妹妹个人一查,9万,那么会拒绝曾公子,说有人给了9万呢,拜拜吧你。

      内容有点多,可以慢慢看。

      其他的一致性协议raft、zab都是paxos的改进版,所以学习好paxos的思想很有帮助。

      你学会了吗? 

      写到了这么多,点个赞吧!




版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《【分布式系统-秒杀系统架构设计】第二章 paxos算法-一致性协议》的版权归原作者「也输思雪计算机之路」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注也输思雪计算机之路微信公众号

也输思雪计算机之路微信公众号:opjesus

也输思雪计算机之路

手机扫描上方二维码即可关注也输思雪计算机之路微信公众号

也输思雪计算机之路最新文章

精品公众号随机推荐

举报