Paxos

关注的点

选取提案的规则：

如果acceptor通过提案[M, ]的prepare请求，则向proposer保证以下承诺：

  1. acceptor承诺不再通过编号小于等于M的提案的prepare请求
  2. acceptor承诺不再通过编号小于M的提案的accept请求，也就是不再通过编号小于M的提案
  3. 如果acceptor已经通过某一提案，则承诺在prepare请求的响应中返回已经通过的最大编号的提案内容。如果没有通过任何提案，则在prepare请求的响应中返回空值

proposer在发起accept请求时，提案值由prepare响应决定。如果prepare响应有返回已通过的提案值，该accept请求则使用prepare响应中的值。如果prepare响应没有已通过的提案值，则有该proposer任意指定。

ZAB

消息广播模式

消息广播模式是一个类似于二阶段提交（2PC）过程，与2PC不同的是，ZAB移除了第二阶段的中断逻辑。所有的Follower要么接收该Proposal，要么抛弃Leader服务器。这意味着Leader收到过半的Ack响应后就可以提交该事务了，而不需要等待所有的Follower都返回Ack。

  1. 客户端发起事务请求，由Leader进行处理
  2. Leader将该请求转换为事务Proposal，同时为Proposal分配一个全局的ID，即zxid
  3. Leader为每个Follower维护一个FIFO队列，将上一步生成的Proposal放入队列中，进行广播
  4. Follower收到Proposal后，会首先将其以事务日志的方式写入本地磁盘中，写入成功后向Leader反馈一个响应消息
  5. Leader收到过半的Ack响应后，自己完成对该Proposal的提交后，向每个Follower的队列中，写入Commit消息进行广播
  6. Follower接收到Commit消息后，会将上一条事务提交

zxid，用于提交提案的先后顺序。Leader提交提案是有顺序性的，按照zxid的大小，按顺序提交提案，如果前一个提案未提交，此时是不会提交后一个提案的。

崩溃恢复模式

约定：

  1. ZAB需要确保那些已经在Leader上提交的事务最终被所有服务器都提交。
  2. ZAB需要确保丢弃那些仅仅只在Leader上被提出的事务。
Leader选举（ELECTION）

Leader选举PK的规则包含以下几个方面：

  • 任期编号（epoch），优先判断epoch，epoch大的节点当选Leader
  • 事务标示符（zxid），epoch相同，则比较zxid，zxid大的当选Leader
  • 节点ID，epoch、zxid都一致，则比较节点ID（在myid文件中指定的值）
  1. leader宕机，各个follower开始leader选举PK
  2. 各个follower都投票给自己，封装一个选票信息，广播给其他的follower。选票信息包含：
    • 自己所提议的节点ID
    • 自己所提议节点所处leader周期
    • 自己所提议节点拥有最大的zxid
    • 投票节点标示
  3. 其他节点收到选票信息后，根据上述规则开始和自己所提议的节点进行PK。如果选票有更新，当前节点则继续广播自己更新之后的选票信息
  4. 最后各节点的选票池，都有过半的选票支持某一节点，该节点晋升为准leader，完成选举
  5. 各节点分别修改自己的状态，准leader修改为LEADING，其余修改为FOLLOWING
发现（DISCOVERY）

该阶段用于确立Leader的领导关系，由Follower会主动联系准Leader。

  1. Follower将自己最后接受的事务Proposal的epoch值发送给准Leader，记作FOLLOWERINFO。
  2. 准Leader收到来自过半（包含B节点自己）的FOLLOWERINFO消息后，选取最大的epoch值，对其进行加1，作为新的epoch值，并封装成LEADERINFO消息发给这些过半的Follower。
  3. Follower收到LEADERINFO消息后
    • 更新自己的epoch
    • 将自己的运行状态变更为SYNCHRONIZATION
    • 返回ACKEPOCH给准Leader。
  4. 准Leader收到过半的ACKEPOCH消息后，也将自己的运行状态修改为SYNCHRONIZATION。至此完成发现阶段的工作，集群确立Leader的领导关系。
数据同步（SYNCHRONIZATION）

该阶段是实现崩溃恢复的关键步骤，由Leader发送数据给Follower处理。数据内容分三种：DIFF、TRUNC、SNAP。

  1. Leader根据Follower的最大zxid选择同步方式
  2. Leader将同步方式和需要同步的数据，一起封装为NEWLEADER消息发给Follower
  3. Follower在收到NEWLEADER消息后，进行修复不一致数据，并返回给Leader响应Ack消息
  4. Leader在收到过半Ack消息后，则完成数据同步阶段，将自己运行状态修改为BROADCARST（广播状态），并发送UPTODATE消息给过半的Follower，通知他们完成数据同步，修改运行状态修改为BROADCARST

Raft

leader选举

日志同步