用 Raft 的方式理解 Multi-Paxos

Multi-Paxos 在文献中并没有准确的实现细节，这里提供一个相对完整的流程，保持接近 Leslie Lamport 在 “ The Part-Time Parliament ” 中给出的算法。

主要参考： https:// ongardie.net/static/raf t/userstudy/paxossummary.pdf

注意：这里描述的 Multi-Paxos 尚未经过实践证明是正确的，欢迎讨论 。

众所周知 Raft 是更易理解的，所以我参照 Raft 的风格，将 Paxos 转换成了下图。

画图不易，关注个公众号鼓励一下～

Raft-style 描述 Multi-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[index]
acceptedValue[index]

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] = ∞ 

Accept 阶段前后的日志

响应：

• 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

1. 如果不是 Leader，或者 Leader 还没有初始化完成，直接返回 False

2. 如果 prepared == True：

• • index = nextIndex, nextIndex++
  • goto 7

3. index = firstUnchosenIndex，nextIndex = index + 1

4. 生成一个新的提案编号 n（maxRound++，并持久化保存）

5. 广播 Prepare(n, index) 给所有 Acceptor

6. 一旦收到超过半数 Acceptor 的 Prepare 响应（ reply.acceptedProposal,reply.acceptedValue,reply.noMoreAccepted ）：

• • 如果所有响应中最大的 reply.acceptedProposal 不等于 0，那么使用它的 reply.acceptedValue ，否则使用自己的 inputValue
  • 如果超过半数的 Acceptor 回复了 reply.noMoreAccepted = True ，那么 prepared = true

7. 广播 Accept(index, n, v) 到所有的 Acceptor

8. 一旦收到一个 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])

9. 一旦收到超过半数 Acceptor 的 Accept 响应：修改 acceptedP roposal[index] = ∞ 和 acceptedValue[index] = v

10. 如果 v == inputValue ， 返回 True

11. 跳转到 2

4. 配置变更（成员变更）

α = 3 时的配置变更

• 配置通常一个列表，每一项存着一台服务器的 id 和 ip 地址，作为一条特殊的记录存储在日志中
• α 表示配置多少条记录后才能生效。第 i 条记录 chosen 时的配置存储在第 i-α 条或 i-α 条之前
• α 用作并发限制：在 i 这个位置的值被 chosen 之前，我们不能 chosen i+α 这个位置的值