1. 算法描述

当前multi-paxos没有权威的文献参考，目前大多采用的参考文献[1]的描述，这里首先给出其翻译版，然后分析其各个模块的细节，Lead election，CommitIndex Advance，Log Replication等。（背景图片来自[2]）

1.1. 服务器状态

所有acceptor上面持久化的状态

每个 acceptor上面存放了一个复制日志，日志index (1 <= index <= lastLogIndex)。每个Log Entry 包含如下内容：

**所有proposer上面持久化的状态**

在Proposer里经常改变的

1.2. Prepare RPC (Phase 1)

Request:

Response:

接收者实现：

当接收到 prepare request 后，如果 request. proposalId >= minProposal, 则设置minProposal = request. proposalId。并且保证拒绝所有的 minProposal < request. proposalId 的accept请求。

1.3. Accpet RPC (Phase 2)

Request:

Response:

• 接收者实现：

如果 proposalId >= minProposalId 就执行如下设置：

acceptedProposal[index] = request. proposalId; acceptedValue[index] = request.value; minProposal = request.proposalId;

对于每一个index < request.commitIndex 的log entry，如果其 acceptedProposal [index] == proposalId ，则可以设置其 acceptedProposal [index] = “无穷大”

1.4. Success (Phase 3)

Request:

Response:

• 接收者实现：

     设置

     acceptedProposal [index] = “无穷大”

     acceptedValue[index] = request.value;

• 发送者实现：

      if reply.commitIndex < commitIndex，

      则发送Success(index = reply.commitIndex + 1; value = acceptedValue[reply.commitIndex+1])

1.5. Proposer Algorithm

Write ( inputValue ) -> return bool

Notes

参考文献 [1] 原文中 02.(b) 描述上有错误，整理修正下，是 goto step 7.

这是 multi-paxos 的基本描述，相比 paxos，通过增加 leader 来消除正常情况下的绝大多数的 Prepare 阶段，直接进入 Accept 阶段，实际上熟悉 Raft 的读者可以看出，其 committed index 也是在 accept 阶段 request 来推进的，相比 Raft ，multi-paxos 增加了 success 其实就用于修复日志使用，后面将在（二）篇详细的分析。

参考文献

[1]. paxos-summay. https://ramcloud.stanford.edu/~ongaro/userstudy/paxossummary.pdf

[2]. Implementing Replicated Logs with Paxos. https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf...