如何进行paxos算法分析

这篇文章给大家介绍如何进行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 结构如下： 由两部分组成：

1. round number： paxos执行的回数，每个服务器都必须保持最新的maxRound【保证尽量少的出现冲突，都竞争最大编号】

2. server id：每个服务器有唯一的id【保证proposal编号不会相同 】

maxRound必须保存在永久存储介质上，一段server crash，可以重新使用 round number 发起proposal

• paxos各阶段目标：

• prepare阶段

• accept阶段

1. 使得所有acceptor接受proposal。

1. 发现任任何被选择的proposal。发现后将自己的value改为发现的Value

2. 阻塞还未完成的proposal。当proposal number较大的proposal进入prepare阶段后，旧的proposal在accept阶段会被拒绝。

主要逻辑：

所有竞争的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？

实现步骤：

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

2. 运行basic paxos， value为client command，

3. prepare return 中是否包含acceptedvalue？

• 有：chosen acceptedvalue，并重复步骤1

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

例子：

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

同理，server1 slot4 改为sub：

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

注意：上述server3 crashed！

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

如何改善multi-paxos性能？

multi-paxos的问题：

1. 多个proposer进行时，会出现冲突和重试，降低系统chosen效率；

2. 对每个选定的value需要进行2回RPC调用；

解决方案：

1. 选择learder。一次只有一个leader，这样就不会有多proposer发生冲突

2. 清除绝大多数的prepare RPC调用

• 进行一次prepare

• 大多数的log entry 能在一个RPC调用完成

3. 如何选择leader？ 1.让serverid最大的作为leader； 2.每隔Tms，每个server发送心跳包给其他server， 3.如果server在2Tms内没有收到比它大的server心跳，那么它可以作为leader，接受client 请求，拥有proposer角色 4.不是leader的server，拒绝client请求将请求重新定向到leader，acceptor角色。

4. 怎么处理prepare阶段

• 将Proposal与logEntry slot关联，每个Proposal number表示一个slot

• 最大的acceptedProposal 的values；

• 当前log entry slot中，每个server的当前slot都没有acceptedvalue，返回noMoreAccepted

1. 如果acceptor返回noMoreAccepted，则跳过同slot当前server 后的所有的prepare RPC（直到accept拒绝Proposal，拒绝Proposal说明acceptro层接受过Proposal，存在acceptedvalue）。

2. 如果leader得知noMoreAccepted，不需要使用prepare了，直接进入accpt阶段。因为所有server的该slot均为空，直接通知acceptor accept Proposal。此时只需要一轮accept RPC。

3. 阻塞旧Proposal：

   

4. 查找可能chosen的value：

5. 为什么需要prepare阶段？

6. 改进后：

怎么全备份？ 目标：每个server上的备份都是全备份。

目标细分：

1. log entry没有full replication：full replication

2. 只有proposer知道那个entry被chosen：所有server都知道那个entry被选中。

解决步骤：

1. proposer在后台一直accept 请求RPC，直到到所有server都回应。能保证大多数server都是full replication（为什么只是大多数？因为有可能之前有server crash，有些log entry为空，就算回应一次，并不能把所有slot都都填充完整，操作布恩那个进入状态机执行，不能达到full replication）

2. track chosen entries

1. 使得entries能被知道是否已经chosen：acceptedEntry[i] = 无穷大 表示第i个entry被chosen。

2. 每个server都维护一个firstUnchosenIndex，该索引是entry的索引，表示该索引前的entry均被chosen。

3. proposer（也就是leader）告知acceptor选择entry：

1. proposer在accept RPC时，发送firstUnchosenIndex。那么acceptor知道entry索引小于firstUnchosenIndex的均被chosen。

2. acceptor标记同时满足以下条件的entry为chosen：i<firstUnchosenIndex && accptedProposal[i] == proposal【proposal相等即表示是同一个leader发送的proposal，又index < firstUnchosenIndex,可知前面均chosen，】

4. 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

客户端协议

1. 发送command给leader

1. 如果leader down， 发送消息给任意的server

2. 如果联系的server不是leader，自动重定向到leader

2. leader在command被log entry选中后，在leader的状态机中执行，执行出结果，然后回应client

3. 请求超时

1. clinet请求别的server

2. 重定向leader server

3. 重新请求command

4. 如果leader在执行后，响应client前crash，一条command不能被执行两次

1. client为每个command提供唯一的标识

2. server 在log entry中保存command id

3. 状态机保最近的每个client的commandid

4. 执行command前，状态机检查command是否已经执行过，执行过，直接忽略并返回old command的执行结果。

如果client在发送command后，接受响应前crash， 然后重新登陆，会遇到同样的问题。client会提交两次command，使用上述措施可以保证每条command只执行一次。

配置修改

系统配置：serverid和address 这些直接会改变quorum。造成系统的majority数量的改变。

为什么需要系统设置变化：

1. server crash

2. replication change

安全原则：在配置变动时，避免对同一个log entry 有不同数量的majority和不同的value选择。

解决方案：使用paxos中log entry管理配置变动

1. 配置保存为log entry

2. 和其他log entry一样备份

3. 在choseing log entry i 时 使用log entry index为i-a作为系统配置。（其中a为系统参数，在系统启动时定义）

引入a后：

1. 系统的并发数量必须在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算法分析就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。