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:AcceptoracceptedProposal[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

  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. 配置变更(成员变更)

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