大白话paxos raft
背景
首先他们干的事就是无论如何保持一致性,比如有三台机器,就算其中一台被炸了,另外两台依旧可以保持一致性。
你看这张图啊,如果有两台服务器A、B。客户端给服务器发送请求 x=3、y=1、y=9,如果一致性模块保证在A、B上以相同的顺序写到了日志中、那么同步到状态机的状态就是一致的,x=3,y=9,试想一下假如A中是x=3、y=1、y=9,B中是x=3、y=9、y=1,那最终A的状态机是x=3,y=9,B的状态机是 x=3,y=1,是不是就不一致了,所以paxos 和 raft 就是干这个事的。
paxos
看上面这张图,左边从上到下三角色,你就理解为每台机器都有三个进程
Proposer(提议者)
Acceptor(决策者)
Learner(学习者)
上面从左到右两个阶段 prepare、accept,其中prepare阶段为prepare(准备请求)和promise(承诺响应),accept阶段为propose(提议请求)和accept(接受响应)。
Prepare(准备)
Accept(决定)
Learn(学习)
所以大概可以知道,完成一次一致性需要两个阶段,先准备一下,在做决定。
三男三女的故事。。。
我给你讲个三男三女的故事吧,时间来到了3000年,法律规定允许一夫多妻制,但是妻子必须来自三个不同的国家,也就是1个男人可以娶三个女人,但是婚姻的时效只能是一天(每天都要进行一次选举)。于是就有了
A国的男A、女A
B国的男B、女B
C国的男C、女C
是不是看上去和上面说的每台机器有三个不同的角色
男人就是Proposer(提议者)
女人就是Acceptor(决策者)
如果一个女人同时嫁给了两个男人那不就乱伦了么?所以一致性是多么重要啊。
这么好的事每个男人都想参与,所以要到联合国婚介所(版本生成器,递增)排队取号,每个男人手里的号都是递增的,男A为v1,男B为v2,男C为v3,然后进入到关键的两个阶段,
提亲Prepare(准备)阶段
入洞房Accept(决定)阶段
由于狼多肉少所以法律做出了一些规定,女人需要给男人一些承诺。
Prepare阶段(提亲阶段)
Proposer选择一个提案编号n并将prepare请求发送给 Acceptor。
Acceptor收到prepare消息后,如果提案的编号大于它已经回复的所有prepare消息,则Acceptor将自己上次接受的提案回复给Proposer,并承诺不再回复小于n的提案。
女人不再接受version小于等于(注意:这里是<= )当前已经提亲Prepare(准备)请求。
比如拿着v2号牌的男B向女A提亲了,并且女A已经答应和男B进洞房了,如果拿着v1号牌的男A再来向女A提亲女A连理都不理,但是拿着v3号牌的男C如果向女A提亲女A会告诉男C我已经要和男B入洞房了,希望的到你的祝福就别再横刀夺爱了。
Accept阶段(入洞房阶段)
当一个Proposer收到了多数Acceptor对prepare的回复后,就进入批准阶段。它要向回复prepare请求的Acceptor发送accept请求,包括编号n和根据prepare阶段决定的value(如果根据prepare没有已经接受的value,那么它可以自由决定value)。
在不违背自己向其他Proposer的承诺的前提下,Acceptor收到accept请求后即接受这个请求。
女人不再接受version小于(注意:这里是< )当前已经入洞房Accept(决定)请求。
拿着v2号牌的男B已经要跟女A入洞房了,拿着v1号牌的男A的入洞房请求就无效了。
用事实说话
假设现在只有男A向女A女B女C提亲
男A向女A女B女C发送prepare请求(我来提亲拉)
假设女A和女B同意了男A的prepare,并返回promise响应
男A收到了多数的prepare回应,因此开始来到入洞房环节
男A给答应嫁给自己的女A和女B发送propose请求(礼金8万,现在可否跟我入洞房了)
女A和女B答应了。
男B、男C得知女A女B已经归属男A
假设现在男A和男B同时向女A女B女C提亲
男A向女A女B女C发送prepare请求(我的号牌是v1我来提亲拉)
男B向女A女B女C发送prepare请求(我的号牌是v2我来提亲拉)
这里可能出现一个场景,男A得到了女A女B的承诺我不在接受版本比你小的提亲请求了,但是比你大的请求我还是接受的,于是男B也拿到了女A女B的承诺,男A不服啊用了版本号更大的号牌v3又成功的拿到了女A女B的承诺,男B也不服用版本号更大的v4又一次夺回了女A女B的承诺,就这样男A男B一直较劲最终谁也没有进洞房,这个问题就是活锁,后面的mutil paxos解决了这个问题,后面说。
所以现阶段向解决这个问题,必须有一个男人可以走到accept(进洞房)的阶段,承诺是不值钱的,只有真正把事办了才是王道。
假设男A先进入到Accept(进洞房)阶段,女A女B的版本编程了v1,礼金变成了8万,然后男B后进入到Accept(进洞房)阶段,女A女B告诉男B我们已经和男A要入洞房了,希望得到你的祝福,一次一致性结束。
假设男B先进入到Accept(进洞房)阶段,女A女B的版本编程了v2,礼金变成了10万,然后男A后进入到Accept(进洞房)阶段,根据之前女A女B的承诺(女人不再接受version小于(注意:这里是< )当前已经入洞房Accept(决定)请求)女A女B连男A见都不见,一次一致性结束。
趁热打铁来个难一点的。
男A向女A女B女C发送prepare请求(我的号牌是v1我来提亲拉)
男B向女A女B女C发送prepare请求(我的号牌是v2我来提亲拉)
男A收到女A、女B的承诺
男B收到女B、女C的承诺
假设男A先进入到Accept(进洞房)阶段,但是失败了,因为此时女B已经被男B用版本号更大的V2提亲了。
接着男B进入到Accept(进洞房)阶段,女B女C看到当前向自己提亲的最大号牌v2就是男B于是接受了男B的入洞房的请求,礼金是10万。
不服气的男A用更大的版本号V3重新向女A女B发送prepare(提亲)请求,由于女A那里是版本号V1礼金8万,女B那里是版本号v2礼金10万,所以回复男A已经又别人抢在你前面了,版本v2礼金10万,男A看到回复后虽然不服气但是还是给女A送上了祝福,你也嫁给男B吧,就这样,女ABC和男B过上了幸福的生活。
Mutil paxos
男A、男B、男C商量,每次我们都要通过两个阶段询问女A、女B、女C太麻烦了,还容易造成活锁,谁都不能进洞房,而且上面也说了,婚姻的有效期就是1天,每天都要进行一次选举,太麻烦了,这样吧咱们三每次选个老大不就完了,你要是想一下玩10天这十天都是你的,咱也不麻烦了。
这样,如果男A成为了老大,在女A女B女C满足大多数的时候就可以进洞房就了。
所以,Mulit-Paxos基于Basic-Paxos做了优化,在Paxos集群中利用Paxos协议选举出唯一的leader,在leader有效期内所有的议案都只能由leader发起。
最后到了raft
Raft是一个用于管理日志一致性的协议。它将分布式一致性分解为多个子问题:Leader选举(Leader election)、日志复制(Log replication)、安全性(Safety)、日志压缩(Log compaction)等。
其实这句话说的特别好,他就是把mutil paxos的实现分成了几个部分,然后实现了,其中leader选举mutil paxos是一次完整的paxos而raft是根据随机的过期时间选出一个leader。
其实mutil 和 paxos已经很接近了,我这里只是说一下区别吧。
最大的区别是日志
Paxos的日志
Raft的日志
其实就是raft的日志更整齐一些,当需要重新选举leader的时候直接选择日志最完整的就可以了,但是paxos存在所谓的日志空洞,当重新选举leader的时候需要通过计算补齐一下日志。这就比raft在选择leader时候理论上慢了一些。
总结
如果面试的时候面试官问我paxos和raft有什么区别呢?我其实想回答没有什么区别,raft就是mutil paxos的一种实现。
参考
https://zhuanlan.zhihu.com/p/31780743
https://zhuanlan.zhihu.com/p/46531628
https://www.zhihu.com/question/36648084/answer/82332860
https://mp.weixin.qq.com/s/3OZgqEWQcEf6V9v6eoSUUA