paxos 推导过程 参考 paxos推导过程
角色
Proposor 提出议案
Acceptor 批准议案
Learner 学习议案
Proposal 议案包含议案编号, 议案的值 (N, V)
二阶段提交
prepare阶段
Proposer 将议案(N) 发送消息给过半的Acceptor
a. 如果N > Acceptor已回复的最大编号(resN), 则回复 (pok, acceptedN, accpetedValue), 并保证对编号小于N的prepare请求不回复(或回复error)
b. 如果N <= resN, 则回复(perror) 或不回复accept阶段
a. 如果收到过半Acceptor的回复, 分两种情况
(1) 如果有回复V, 选择编号最大的N对应的V当做V
(2) 如果都没有回复V, 则可以自作主张选择V
将Proposal(N,V) 发送给过半的Acceptor(不一定是prepare阶段的Acceptor集合), 并期望过半Acceptor接收该议案
Acceptor收到accept(N, Value)请求
(1) 如果Acceptor未接受过议案, 则接受该议案, 更新 acceptedN, acceptedValue为该议案的编号与值, 回复 (aok)
(2) 若果Acceptor接受过议案
a. N > 接受的编号, 则接受该议案, 并更新 acceptedN, acceptedValue为该议案的编号与值, 回复(aok)
b. N <= 接受的编号, 则不接受该议案, 回复(error) 或不回复
b. 如果收到的回复不过半, 编号N+1, 重新进入第一阶段
Acceptor要点
(resN, acceptedN, acceptedValue)
需要记住回复prepare消息的最大编号 resN, 接受过的最大编号的议案 acceptedN, acceptedValue
