用 Raft 的方式理解 Multi-Paxos
文章目录
Multi-Paxos 在文献中并没有准确的实现细节,这里提供一个相对完整的规范,保持接近 Leslie Lamport 在 “The Part-Time Parliament.” 中给出的算法。
这里描述的 Multi-Paxos 尚未经过实践证明其正确性。
众所周知 Raft 是更易理解的,所以我参照 Raft 的风格,将 Paxos 转换成了下图。
1. 基础
- 提案编号 n = (round number, server ID)
- T: 固定的超时时间,用于选举算法
- α:并发限制,用于配置变更
1.1 Leader 选举算法
- 每个节点每隔 T(ms) 向其它服务器发送心跳
- 如果一个节点在 2(Tms) 时间内没有收到比自己 server ID 更大的心跳,那它自己就转为 Leader
2. 持久化
2.1 Acceptor 上的持久化状态
- lastLogIndex:已经接受的最大的日志index
- minProposal:已经接收提案中的最小提案编号,如果还未收到 Prepare 请求,则为 0
每个 Acceptor 上还会存储一个日志,日志索引 i ∈ [1, lastLogIndex],每条日志记录包含以下内容:
- acceptedProposal[i]:第 i 条日志最后接受的提案编号。初始化时为 0;如果提案被 chosen,则 acceptedProposal[i] = 无穷大
- acceptedValue[i]:第 i 条日志最后接受的 value,初始化时为
null
- firstUnchosenIndex:i > 0 且 acceptedProposal[i] < ∞ 的最小日志 index
2.2 Proposer 上的持久化状态
- maxRound:Proposer 已知的最大 round number
2.3 Proposer 上的易失性状态
- nextIndex:客户端请求要写的下一个日志 index
- prepared:如果 prepared 为 True,那么 Proposer 不再需要发起 Prepare 请求(超过半数的 Acceptor 回复了
noMoreAccepted
);初始化为 False
3 流程
3.1 Prepare(阶段 1)
请求:
- n:提案编号
- index:Proposer 的提案对应的日志 index
接受者处理:
收到 Prepare 请求后,如果 request.n >= minProposal
,则 Acceptor 设置 minProposal = request. proposalId
;同时承诺拒绝所有提案编号 < request.n 的 Accept 请求。
响应:
- acceptedProposal:Acceptor 的
acceptedProposal[index]
- acceptedValue:Acceptor 的
acceptedValue[index]
- noMoreAccepted:Acceptor 遍历 >= index 的日志记录,如果之后没有接受过任何值(都是空的记录),那么 noMoreAccepted = True;否则设为 False
3.2 Accept(阶段 2)
请求:
- n:和 Prepare 阶段一样的提案编号
- index:日志 index
- v:提案的值,如果 Prepare 阶段收到一个更大的提案编号,那么就是该最大的提案的值,否则 Proposer 使用来自 Client 的值
- firstUnchosenIndex:节点日志上第一个没有被 chosen 的日志 index
接受者处理:
收到 Accept 请求后,如果 n >= minProposal,
则:
acceptedProposal[index] = n
acceptedValue[index] = v
- minProposal = n
对于每个
index < request.firstUnchosenIndex
,如果acceptedProposal[index] = n
,则acceptedProposal[index] = ∞
响应:
- n:Acceptor 的 minProposal 值
- firstUnchosenIndex:Acceptor 的 firstUnchosenIndex 值
3.3 Success(阶段 3)
请求:
- index:日志的索引
- v:log[index] 已 chosen 的提案值
接受者处理:
Acceptor 收到 Success RPC 后,更新已经被 chosen 的日志记录:
- acceptedValue[index] = v
- acceptedProposal[index] = 无穷大
响应:
- firstUnchosenIndex:Acceptor 的 firstUnchosenIndex 值
当发送者收到响应后,如果 reply.firstUnchosenIndex < firstUnchosenIndex
,则发送者再发生请求: Success(index = reply.firstUnchosenIndex, value = acceptedValue[reply.firstUnchosenIndex])
3.4 Proposer 算法:write(inputValue) → bool
- 如果不是 Leader,或者 Leader 还没有初始化完成,直接返回 False
- 如果 prepared == True:
- index = nextIndex, nextIndex++
- goto 7
- index = firstUnchosenIndex,nextIndex = index + 1
- 生成一个新的提案编号 n(maxRound++,并持久化保存)
- 广播
Prepare(n, index)
给所有 Acceptor - 一旦收到超过半数 Acceptor 的 Prepare 响应(
reply.acceptedProposal,reply.acceptedValue,reply.noMoreAccepted
):- 如果所有响应中最大的
reply.acceptedProposal
不等于 0,那么使用它的reply.acceptedValue
,否则使用自己的inputValue
- 如果超过半数的 Acceptor 回复了
reply.noMoreAccepted = True
,那么prepared = true
- 如果所有响应中最大的
- 广播
Accept(index, n, v)
到所有的 Acceptor - 一旦收到一个 Acceptor 的响应(
reply.n, reply.firstUnchosenIndex
)- 如果
reply.n > n
,则从reply.n
中修改maxRound
,修改prepared = False
,跳转到 1 - 如果
reply.firstUnchosenIndex ≤ lastLogIndex
并且acceptedProposal[reply.firstUnchosenIndex] == ∞
,就发送Success(index = reply.firstUnchosenIndex, value = acceptedV alue[reply.firstUnchosenIndex])
- 如果
- 一旦收到超过半数 Acceptor 的 Accept 响应:修改
acceptedP roposal[index] = ∞
和acceptedValue[index] = v
- 如果
v == inputValue
, 返回 True - 跳转到 2
4. 配置变更(成员变更)
- 配置通常一个列表,每一项存着一台服务器的 id 和 ip 地址,作为一条特殊的记录存储在日志中
𝛼
表示配置多少条记录后才能生效。第i
条记录 chosen 时的配置存储在第i-𝛼
条或i-𝛼
条之前α
用作并发限制:在i
这个位置的值被 chosen 之前,我们不能 choseni+α
这个位置的值
微信公众号
