这篇文章给大家介绍如何进行paxos算法分析,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
只有一个acceptor可以吗? 不可以。所有的proposer都往一个acceptor上发消息,这个acceptor crashed,那么整个系统就crashed。 解决方法:使用quorum (仲裁人数)。多个acceptor, 只需要大多数acceptor选中某个value就可以了,万一某一个acceptor crashed,不影响系统。
每个acceptor 只chose第一个value,这样可以吗? 不可以。因为这样可能会出现proposal1的acceptor和proposal2的acceptor的数量一样多,无法选出哪一个proposal作为chosenproposal。例如server1 选中proposal1,server2 选中proposal1和proposal2,server3 选中proposal2。 解决方案:每个proposer在发起proposal前必须确认当前是否有proposal选中,如果有,则放弃自己的proposal。
chosen过程中会出现冲突,依据冲突不同得出结论: 一旦选中一个proposal,其他竞选proposal必须选择同样的value;proposal按照proposal number排序,拒绝旧proposal;
通过上述描述, 可设计proposal number 结构如下: 由两部分组成:
round number: paxos执行的回数,每个服务器都必须保持最新的maxRound【保证尽量少的出现冲突,都竞争最大编号】
server id:每个服务器有唯一的id【保证proposal编号不会相同 】
maxRound必须保存在永久存储介质上,一段server crash,可以重新使用 round number 发起proposal
paxos各阶段目标:
prepare阶段
accept阶段
使得所有acceptor接受proposal。
发现任任何被选择的proposal。发现后将自己的value改为发现的Value
阻塞还未完成的proposal。当proposal number较大的proposal进入prepare阶段后,旧的proposal在accept阶段会被拒绝。
主要逻辑:
proposer | acceptor |
---|---|
1.选择proposal number n | |
2.广播给acceptor prepare(n) | |
3. 响应prepare(n) : if (n > minProposol) then minProposol=n; Return(acceptedProposol,acceptedValue) | |
4. 获取大多数acceptor回复:如果有返回,选择返回中最大的proposal number 对应的value作为本次proposal的value;如果没有返回,可继续使用之前的value | |
5.向所有acceptor广播accept(n,value) | |
6. 响应accept(n,value) :if(n >= minProposol) then acceptedProposol = minProposol = n; accptedValue = value; Return minProposol | |
7. 获取大多数acceptor返回:如果存在result>n;表示proposal被拒绝,重复1~6,且下次设置的n比result大,否则chosen proposal |
所有竞争的proposal必须有一个公共的acceptor,这样就能发现新旧proposal,并及时终止旧proposal。
paxos活锁:导致无proposal chosen。 proposal A 早prepare阶段通过,另一proposal B进入prepare, acceptor的minProposal增加,导致A在accept阶段被拒绝,A立即重试,并进入prepare阶段,导致acceptor的minProposal增加,B进入accept阶段后被拒绝。。。如此往复。没有command能正常进行。
解决方案:每次重试必须在随机的时延后进行。
实现步骤:
找到第一个log entry 不知道是否chosen的entry slot,(不一定是第一个为空的slot)
运行basic paxos, value为client command,
prepare return 中是否包含acceptedvalue?
有:chosen acceptedvalue,并重复步骤1
无:chosen client请求,该slot即是寻找的slot
例子:
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|
server 1 | mov | add | cmp | ret | |||
server 2 | mov | add | sub | ret | |||
server 3 | mov | add | cmp | cmp | ret |
如上表,当client请求jmp时,假设server3 crashed,此时到slot3,由于server1和server2不同,不知道是否chosen Proposal,于是以client command的值为value; 运行paxos,进入prepare(n),server1 slot3已经有acceptedvalue,所以Proposal的value会改为server 1 slot 3的值,然后进行accept阶段,server2 slot3 接收value。将server2 slot3 改为cmp。
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|
server 1 | mov | add | cmp | ret | |||
server 2 | mov | add | cmp | sub | ret | ||
server 3 | mov | add | cmp | cmp | ret |
同理,server1 slot4 改为sub:
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|
server 1 | mov | add | cmp | sub | ret | ||
server 2 | mov | add | cmp | sub | ret | ||
server 3 | mov | add | cmp | cmp | ret |
然后slot5, acceptedValue=null;次次Proposal的value为元定义的value,即client的command。
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|
server 1 | mov | add | cmp | sub | jmp | ret | |
server 2 | mov | add | cmp | sub | jmp | ret | |
server 3 | mov | add | cmp | cmp | ret | ||
找到 log entry slot。 |
注意:上述server3 crashed!
在上述处理过程中:server可以同时接收多个client请求,只要能保证client 请求的log Entry不同即可; 但是在command进入server状态机执行的时候,必须是顺序进行。
multi-paxos的问题:
多个proposer进行时,会出现冲突和重试,降低系统chosen效率;
对每个选定的value需要进行2回RPC调用;
解决方案:
选择learder。一次只有一个leader,这样就不会有多proposer发生冲突
清除绝大多数的prepare RPC调用
进行一次prepare
大多数的log entry 能在一个RPC调用完成
如何选择leader? 1.让serverid最大的作为leader; 2.每隔Tms,每个server发送心跳包给其他server, 3.如果server在2Tms内没有收到比它大的server心跳,那么它可以作为leader,接受client 请求,拥有proposer角色 4.不是leader的server,拒绝client请求将请求重新定向到leader,acceptor角色。
怎么处理prepare阶段
将Proposal与logEntry slot关联,每个Proposal number表示一个slot
最大的acceptedProposal 的values;
当前log entry slot中,每个server的当前slot都没有acceptedvalue,返回noMoreAccepted
如果acceptor返回noMoreAccepted
,则跳过同slot当前server 后的所有的prepare RPC(直到accept拒绝Proposal,拒绝Proposal说明acceptro层接受过Proposal,存在acceptedvalue)。
如果leader得知noMoreAccepted
,不需要使用prepare了,直接进入accpt阶段。因为所有server的该slot均为空,直接通知acceptor accept Proposal。此时只需要一轮accept RPC。
阻塞旧Proposal:
查找可能chosen的value:
为什么需要prepare阶段?
改进后:
怎么全备份? 目标:每个server上的备份都是全备份。
目标细分:
log entry没有full replication:full replication
只有proposer知道那个entry被chosen:所有server都知道那个entry被选中。
解决步骤:
proposer在后台一直accept 请求RPC,直到到所有server都回应。能保证大多数server都是full replication(为什么只是大多数?因为有可能之前有server crash,有些log entry为空,就算回应一次,并不能把所有slot都都填充完整,操作布恩那个进入状态机执行,不能达到full replication)
track chosen entries
使得entries能被知道是否已经chosen:acceptedEntry[i] = 无穷大
表示第i个entry被chosen。
每个server都维护一个firstUnchosenIndex
,该索引是entry的索引,表示该索引前的entry均被chosen。
proposer(也就是leader)告知acceptor选择entry:
proposer在accept RPC时,发送firstUnchosenIndex
。那么acceptor知道entry索引小于firstUnchosenIndex
的均被chosen。
acceptor标记同时满足以下条件的entry为chosen:i<firstUnchosenIndex && accptedProposal[i] == proposal
【proposal相等即表示是同一个leader发送的proposal,又index < firstUnchosenIndex,可知前面均chosen,】
acceptor不能确认proposal number不同的log entry 是否chosen。 解决方案:acceptor在返回时,返回acceptor的firstUnchosenIndex
,若proposer的firstUnchosenIndex
大于acceptor的firstUnchosenIndex
, 那么proposer在后台发送[success] RPC。
success(Index, v): acceptedValue[index] = v; acceptedProposal[index]=无穷大 return firstUnchosenIndex
发送command给leader
如果leader down, 发送消息给任意的server
如果联系的server不是leader,自动重定向到leader
leader在command被log entry选中后,在leader的状态机中执行,执行出结果,然后回应client
请求超时
clinet请求别的server
重定向leader server
重新请求command
如果leader在执行后,响应client前crash,一条command不能被执行两次
client为每个command提供唯一的标识
server 在log entry中保存command id
状态机保最近的每个client的commandid
执行command前,状态机检查command是否已经执行过,执行过,直接忽略并返回old command的执行结果。
如果client在发送command后,接受响应前crash, 然后重新登陆,会遇到同样的问题。client会提交两次command,使用上述措施可以保证每条command只执行一次。
系统配置:serverid和address 这些直接会改变quorum。造成系统的majority数量的改变。
为什么需要系统设置变化:
server crash
replication change
安全原则:在配置变动时,避免对同一个log entry 有不同数量的majority和不同的value选择。
解决方案:使用paxos中log entry管理配置变动
配置保存为log entry
和其他log entry一样备份
在choseing log entry i 时 使用log entry index为i-a作为系统配置。(其中a为系统参数,在系统启动时定义)
引入a后:
系统的并发数量必须在a以内:因为在log entry i 被chosen后才能 chosen entry a+i; 可以使用一些无操作的command加速配置改变。
核心逻辑伪代码:
--- Paxos Proposer --- proposer(v): while not decided: choose n, unique and higher than any n seen so far send prepare(n) to all servers including self if prepare_ok(n, na, va) from majority: v’ = va with highest na; choose own v otherwise send accept(n, v’) to all if accept_ok(n) from majority: send decided(v’) to all
--- Paxos Acceptor --- acceptor state on each node (persistent): np --- highest prepare seen na, va --- highest accept seen acceptor’s prepare(n) handler: if n > np np = n reply prepare_ok(n, na, va) else reply prepare_reject acceptor’s accept(n, v) handler: if n >= np np = n na = n va = v reply accept_ok(n) else reply accept_reject
关于如何进行paxos算法分析就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。