共计 5995 个字符，预计需要花费 15 分钟才能阅读完成。
这篇文章给大家介绍如何进行 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]= 无穷大
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 算法分析就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
