主要从以下几点理解paxos：
- 基础paxos算法
- 阶段一：prepare
- 阶段二：accept
- multi-paxos
- 选择log entry
- leader选举
- 消除prepare RPC调用
- 全备份
- 客户端协议
- 改变系统配置
基础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阶段
- 发现任任何被选择的proposal。发现后将自己的value改为发现的Value
- 阻塞还未完成的proposal。当proposal number较大的proposal进入prepare阶段后，旧的proposal在accept阶段会被拒绝。
- accept阶段
- 使得所有acceptor接受proposal。
- prepare阶段
主要逻辑：
| 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能正常进行。
解决方案：每次重试必须在随机的时延后进行。
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
例子：
| 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性能？
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阶段
- 为什么需要prepare阶段？
- 阻塞旧Proposal：
- 将Proposal与logEntry slot关联，每个Proposal number表示一个slot
- 查找可能chosen的value：
- 最大的acceptedProposal 的values；
- 当前log entry slot中，每个server的当前slot都没有acceptedvalue，返回
noMoreAccepted
- 阻塞旧Proposal：
- 改进后：
- 如果acceptor返回
noMoreAccepted，则跳过同slot当前server 后的所有的prepare RPC（直到accept拒绝Proposal，拒绝Proposal说明acceptro层接受过Proposal，存在acceptedvalue）。 - 如果leader得知
noMoreAccepted，不需要使用prepare了，直接进入accpt阶段。因为所有server的该slot均为空，直接通知acceptor accept Proposal。此时只需要一轮accept RPC。
- 如果acceptor返回
- 为什么需要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。
- 使得entries能被知道是否已经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，】
- proposer在accept RPC时，发送
- 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
