<aside> 📌 Basic Paxos 的中心思想就是保证 Acceptor 只允许最后 Prepare 的 Proposer 写入。

</aside>

算法中提到三种节点角色 Proposer 、 Acceptor 、 Learner 。其中 Proposer 负责提出议案，由 Acceptor 决议是否通过，半数以上的 Acceptor 通过提案后告知 Learner 选择已被接受的提案。

算法流程

Basic Paxos 包含两个阶段：Prepare 和 Accept。使用 Mermaid 可以大致表示为下面的流程图：

sequenceDiagram
    participant C as Client
    participant P1 as Proposer1
    participant A1 as Acceptor1
    participant A2 as Acceptor2
    participant L as Learner

		Note over P1, A2: Phase 1: Prepare-Promise
    C->>P1: Request
    P1->>A1: Prepare(n)
    P1->>A2: Prepare(n)
    A1->>P1: Promise(n, (k, v))
    A2->>P1: Promise(n, (k, v))
		
		Note over P1, A2: Phase 2: Accept-Accepted
    P1->>A1: Accept(n, v')
    P1->>A2: Accept(n, v')
    A1->>P1: Accepted(n, v')
    A1->>L: Chosen(n, v')
    A2->>P1: Accepted(n, v')
    A2->>L: Chosen(n, v')
    L->>C: Response

在 Prepare 阶段中由 Proposer 向所有 Acceptor 发送 Prepare(n) 请求，n 为全局唯一递增的 Proposal ID。 Acceptor 收到请求后在不违背自身已经作出的承诺的情况下向 Proposer 承诺：

1. 不再对 Proposal ID 小于等于 n 的 Prepare 请求作出承诺；
2. 不再接受 Proposal ID 小于 n 的 Accept 请求。

与此同时，如果 Acceptor 发现在本轮 Paxos 中，如果自身已经接受了某个提案，那么它会将这个提案 (k, v) 同时返回给 Proposer。

当 Proposer 收到来自超过半数 Acceptor 的承诺后，可以进入 Accept 阶段。在此阶段， Proposer 将按照规则选取提案的值 v' ：

1. 如果在 Prepare(n) 阶段中 Acceptor 没有返回已经被接受的提案，则可以自由决定值；
2. 否则选择所有返回了的提案 (k, v) 中 Proposal ID k 最大的 v。

<aside> ℹ️ 第二条规则的目的是， Proposer 从 Acceptor 得到了可能被接受的提案，由于不知道那个提案是否已经被大多数接受或被选择，因此新的提案的值只能来自于最大的旧提案，否则无法保证达成了共识（可以视作是对一次未完全执行的 Paxos 的恢复）。

</aside>

在不违背 Prepare 阶段中的承诺的情况下，Acceptor 选择是否接受提案 (n, v')。如果超过半数 Acceptor 接受了此提案，则可以通知 Learner 该提案被选中，集群达成共识。

实现

Proposer 的结构定义如下：

type Proposer struct {
	uid                 uint64
	acceptorsIds        []uint64
	network             consensus.Network
	proposalIdGenerator consensus.UidGenerator

	// Only permits one propose procedure running at the same time.
	proposeLock sync.Mutex
	IsLocked    bool
	proposalId  uint64

	// Persist previously accepted proposal to restore an unfinished paxos.
	acceptedProposalLock sync.Mutex
	acceptedProposalId   uint64
	acceptedValue        uint64

	// The channel to receive chosen proposals.
	chosenChannel chan<- ChosenProposal
}

其中 acceptedProposalId 和 acceptedValue 用于保存其他 Proposer 已经进入 Accept 阶段但是可能还未完成的提案。

Acceptor 的结构定义如下：

type Acceptor struct {
	promisedProposalId uint64
	acceptedProposalId uint64
	acceptedValue      uint64

	lock sync.Mutex
}