如何进行paxos算法分析

lewis 1年前 (2024-04-27) 阅读数 16 #技术

这篇文章给大家介绍如何进行paxos算法分析，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

基础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阶段会被拒绝。

主要逻辑：

proposeracceptor1.选择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 minProposol7. 获取大多数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能正常进行。

解决方案：每次重试必须在随机的时延后进行。

multi-paxos

如何选择log entry？

实现步骤：

找到第一个log entry 不知道是否chosen的entry slot，（不一定是第一个为空的slot）

运行basic paxos， value为client command，

prepare return 中是否包含acceptedvalue？

有：chosen acceptedvalue，并重复步骤1

无:chosen client请求，该slot即是寻找的slot

例子：

1234567server 1movaddcmp

ret
server 2movadd
sub
ret
server 3movaddcmp
cmpret

如上表，当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。

1234567server 1movaddcmp

ret
server 2movaddcmpsub
ret
server 3movaddcmp
cmpret

同理，server1 slot4 改为sub：

1234567server 1movaddcmpsub
ret
server 2movaddcmpsub
ret
server 3movaddcmp
cmpret

然后slot5， acceptedValue=null；次次Proposal的value为元定义的value，即client的command。

1234567server 1movaddcmpsubjmpret
server 2movaddcmpsubjmpret
server 3movaddcmp
cmpret
找到 log entry slot。

注意：上述server3 crashed！

在上述处理过程中：server可以同时接收多个client请求，只要能保证client 请求的log Entry不同即可；但是在command进入server状态机执行的时候，必须是顺序进行。

如何改善multi-paxos性能？

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]=无穷大
returnfirstUnchosenIndex

客户端协议

发送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加速配置改变。

核心为代码

核心逻辑伪代码：

---PaxosProposer---
proposer(v):
	whilenotdecided:
	choosen,uniqueandhigherthananynseensofar
	sendprepare(n)toallserversincludingself
	ifprepare_ok(n,na,va)frommajority:
		v’=vawithhighestna;chooseownvotherwise
		sendaccept(n,v’)toall
		ifaccept_ok(n)frommajority:
			senddecided(v’)toall

---PaxosAcceptor---
acceptorstateoneachnode(persistent):
np---highestprepareseen
na,va---highestacceptseen

acceptor’sprepare(n)handler:
	ifn>np
		np=n
		replyprepare_ok(n,na,va)
	else
		replyprepare_reject

acceptor’saccept(n,v)handler:
	ifn>=np
	np=n
	na=n
	va=v
	replyaccept_ok(n)
	else
		replyaccept_reject

关于如何进行paxos算法分析就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。