Paxos解决的问题

  1. 分布式容错：
    在分布式环境下，能容忍一部分节点宕机，还能对外提供稳定的服务。
  2. 分布式共识算法：
    在分布式环境下，各个节点就某个值达成共识，即所有节点都认同某个值。

三种角色

  1. 提案者 proposer
  2. 接收者 acceptor
  3. 学习者 learner

三个阶段

  1. 准备阶段 prepare
  2. 接收阶段 accept
  3. 学习阶段 learn

提案 proposal

提案是需要达成共识的一个值。用[M,V]表示，M 表示提案编号，V 表示需要达成共识的值。

提案者（Proposer）

  1. 接受客户端请求，封装成提案。
  2. 将提案发送给接收者。
  3. 根据接收者响应情况统计，决定是否保存该提案。

接收者（Acceptor）

  1. 参与对提案的投票。
  2. 接收和处理prepare和accept两个阶段的请求。
  3. 记录三个值：
    1. 准备（prepare）通过的最大提案编号 maxPrepareM。
    2. 接收（accept）通过最大提案编号 maxAcceptM。
    3. 接收（accept）通过最大提案编号的值 maxAcceptV。

学习者（Learner）

  1. 不参与提案和投票。
  2. 接收提案结果并学习。

准备阶段（Prepare）

  1. proposer 向 acceptor 发送提案请求[M,]
  2. acceptor 根据约定决定是否响应。约定即：当一个 accepor 收到的提案号M是此 acceptor 在prepare阶段接收过的最大提案号（比maxPrepareM大）时响应通过。否则不响应。
  3. 若一个 acceptor 通过该提案的准备（prepare）请求，保存maxPrepare = M，并要保证以下几点：
    1. 不再通过编号小于等于M的提案的准备（prepare）请求。
    2. 不再通过编号小于M的提案。
    3. 如果通过此提案，则在响应中返回 [maxAcceptM,maxAcceptV]。如果没有通过任何提案，则在响应中返回空值。

接收阶段（Accept）

proposer 接收到超过半数的响应后，由 proposer 向 acceptor 发送提案[M,V],根据 acceptor 在准备阶段作出的保证

  1. 如果此 acceptor 没有通过编号大于M的 prepare 请求，即M大于 maxPrepareM，那么则会批准此提案[M,V], 并且保存 maxPrepareM = maxAcceptM = M，maxAcceptV = V。
  2. acceptor 返回最新的 maxPrepareM。
  3. proposer 统计收到的接收（accept）请求的响应，如果响应中的编号等于自己发出的提案编号，则认为该 acceptor 批准了该提案。如果超过半数 acceptor 批准该提案，则记做该提案已达成共识。如果没有大多数 acceptor 批准该提案，则重新回到 prepare 阶段进行协商。
  4. 如果在prepare请求的响应中，部分acceptor已经批准过的提案值，则V为prepare请求的响应中编号最大的提案值，否则可以由proposer任意指定。

学习阶段（Learn）

在某一个提案通过 paxos 达成共识之后，通知 learner 学习提案结果。
最佳方案：建立一个主 learner 集合，提高健壮性，先通知这个主 learner 集合，提高效率，再由主 learner 集合通知所有learner。