分布式共识算法

发表于 | 分类于

一、Paxos协议

1、拜占庭将军问题


2、提出问题


3、故事背景


4、Paxos算法

4.1、基本定义


4.2、算法详解

Paxos算法有两个阶段

  • Prepare阶段（第一阶段）
  • Accept阶段（第二阶段）
1)、第一阶段
  1. Proposer希望议案V。首先发出Prepare请求至大多数Acceptor。Prepare请求内容为序列号K；
  2. Acceptor收到Prepare请求为编号K后，检查自己手里是否有处理过Prepare请求；
  3. 如果Acceptor没有接受过任何Prepare请求，那么用OK来回复Proposer，代表Acceptor必须接受收到的第一个议案；
  4. 否则，如果Acceptor之前接受过任何Prepare请求（如：MaxN），那么比较议案编号，如果K<MaxN，则用reject或者error回复Proposer；
  5. 如果K>=MaxN，那么检查之前是否有批准的议案，如果没有则用OK来回复Proposer，并记录K；
  6. 如果K>=MaxN，那么检查之前是否有批准的议案，如果有则回复批准的议案编号和议案内容（如：<AcceptN, AcceptV>， AcceptN为批准的议案编号，AcceptV为批准的议案内容）。

2)、第二阶段
  1. Proposer收到过半Acceptor发来的回复，回复都是OK，且没有附带任何批准过的议案编号和议案内容。那么Proposer继续提交批准请求，不过此时会连议案编号K和议案内容V一起提交（<K, V>这种数据形式）
  2. Proposer收到过半Acceptor发来的回复，回复都是OK，且附带批准过的议案编号和议案内容（<pok，议案编号，议案内容>）。那么Proposer找到所有回复中AcceptN最大的那个AccpetV（假设为<pok，AcceptNx，AcceptVx>）作为提交批准请求（请求为<K，AcceptVx>）发送给Acceptor。
  3. Proposer没有收到过半Acceptor发来的回复，则修改议案编号K为Kx，并将编号重新发送给Acceptors（重复Prepare阶段的过程）
  4. Acceptor收到Proposer发来的Accept请求，如果编号K<MaxN则不回应或者reject。
  5. Acceptor收到Proposer发来的Accept请求，如果编号K>=MaxN则批准该议案，并设置手里批准的议案为<K，接受议案的编号，接受议案的内容>，回复Proposer。
  6. 经过一段时间Proposer对比手里收到的Accept回复，如果超过半数，则结束流程（代表议案被批准），同时通知Leaner可以学习议案。
  7. 经过一段时间Proposer对比手里收到的Accept回复，如果未超过半数，则修改议案编号重新进入Prepare阶段。


5、Paxos流程图


二、ZAB协议

zookeeper 的 leader 选举采用了 ZAB协议，消息广播的时候没有采用ZAB协议

ZooKeeper并没有完全采用Paxos算法，而是使用了一种称之为ZooKeeper Atomic Broadcast（ZAB，ZooKeeper原子广播协议）的协议作为其数据一致性的核心算法。

ZAB协议并不像Paxos算法那样，是一种通用的分布式一致性算法，它是一种特别为ZooKeeper设计的崩溃恢复的原子消息广播算法。ZooKeeper采用一个单一的主进程接受并处理客户端的所有事务请求，并将服务器数据的状态变更以事务Proposal的形式广播到所有的副本进程上去。

ZAB协议包含两种基本的模式：

  • 崩溃恢复
  • 消息广播

ZAB协议包含三个阶段：

  • 阶段1：发现（Leader选举过程）

  • 阶段2：同步（数据同步过程）

  • 阶段3：广播（正式接受请求过程）

当整个服务框架在启动过程中，或是当 Leader 服务器出现网络中断、崩溃退出与重启等异常情况时， ZAB 协议就会进入恢复模式并选举产生新的 Leader 服务器。当选举产生了新的Leader 服务器同时集群中已经有过半的机器与该 Leader 服务器完成了状态同步之后，ZAB 协议就会退出恢复模式。

当集群中已经有过半的 Follower 服务器完成了和 Leader 服务器的状态同步，那么整个服务框架就可以进入消息广播模式了。当一台同样遵守 ZAB 协议的服务器启动后加入到集群中时，如果此时集群中已经存在一个 Leader 服务器在负责进行消息广播 ， 那么新加入的服务器就会自觉地进入数据恢复模式：找到 Leader 所在的服务器，并与其进行数据同步，然后一起参与到消息广播流程中去。

org.apache.zookeeper.server.quorum.QuorumPeer.ServerState

1
2
3
public enum ServerState {
   LOOKING, FOLLOWING, LEADING, OBSERVING;
}

1、崩溃恢复

当整个服务器在启动过程中，或者当Leader服务器出现网络中断、崩溃退出与重启等异常情况时，ZAB协议就会进入恢复模式并通过选举产生新的Leader服务器。

  • 当选举产生了新的Leader服务器，同时集群中已经有过半机器与该Leader服务器完成状态同步之后，ZAB协议就会退出恢复模式。这里的状态同步指的就是数据同步，用来保证集群中存在过半的机器能够和Leader服务器的数据保持一致。
  • 当集群中有过半的Follower服务器完成和Leader服务器的同步，那么整个服务器集群就可以进入消息广播模式。
  • 当新的机器加入集群，由于集群已经存在一个Leader，那么新加入的机器会进入数据同步模式，即找到Leader服务器，并与其进行数据同步。
  • 当Leader崩溃退出或者重启，或者及集群中不存在过半的服务器可以和Leader保持正常通信，那么在开始新一轮事务操作前所有机器会使用崩溃恢复协议来达到一个一致性的状态。

ZAB协议规定了如果一个事务Proposal在一台机器上被处理成功，那么应该在所有的机器上都被处理成功，哪怕机器出现故障崩溃。

  1. 每个Server会发出一个投票，第一次都是投自己。投票信息：（myid，ZXID）
  2. 收集来自各个服务器的投票
  3. 处理投票并重新投票，处理逻辑：优先比较ZXID，然后比较myid
  4. 统计投票，只要超过半数的机器接收到同样的投票信息，就可以确定Leader
  5. 改变服务器状态 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 选票和服务器的当前选票进行对比
protected boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, long curId, long curZxid, long curEpoch) {
    LOG.debug("id: " + newId + ", proposed id: " + curId + ", zxid: 0x" +
              Long.toHexString(newZxid) + ", proposed zxid: 0x" + Long.toHexString(curZxid));
    if(self.getQuorumVerifier().getWeight(newId) == 0){
        return false;
    }

    /*
     * 以下三种情况成立，则返回true:
     * 1- 新epoch更大
     * 2- 新epoch与当前epoch相同，但新zxid更大
     * 3- 新epoch与当前epoch相同，新zxid与当前zxid相同，但是服务器id更高。
     */
    return ((newEpoch > curEpoch) || 
            ((newEpoch == curEpoch) &&
             ((newZxid > curZxid) || ((newZxid == curZxid) && (newId > curId)))));
}

2、消息广播

消息广播类似于一个2PC提交过程。根据客户端的事务请求，Leader服务器会为其生成对应的事务投票（即Proposal）并将其发送给集群中其他服务器，然后在分表搜集各自的选票，最后进行事务提交。

与2PC不同的是，ZAB协议没有中断逻辑（所有Follower要么对Leader提成的事务Ack，要么就不回应），而且当过半的Follower服务器反馈Ack之后就开始提交事务，不用等待所有Follower都反馈。

整个消息广播协议是基于FIFO特性的TCP协议来进行网络通信，因此能够很容易地保证消息广播过程中消息接受与发送的顺序性。

  1. Leader接收到消息请求后，将消息赋予一个全局唯一的64位自增id，叫做：Zxid，通过zxid的大小比较即可实现因果有序这一特性。
  2. Leader通过先进先出队列(通过 TCP 协议来实现，以此实现了全局有序这一特性)将带有zxid的消息作为一个提案(Proposal)分发给所有Follower。
  3. 当Follower接收到Proposal，先将Proposal写到硬盘，写硬盘成功后再向Leader回一个ACK。
  4. 当Leader接收到合法数量的ACKs后，Leader就向所有Follower发送COMMIT命令，同时会在本地执行该消息。
  5. 当Follower收到消息的COMMIT命令时，就会执行该消息。

3、数据同步

整个集群完成Leader选举后，Learner会向Leader进行注册，当Learner向Leader完成注册后，就进入数据同步环节，同步过程就是Leader将那些没有在Learner服务器上提交过的事务请求同步给Learner服务器。

3.1、直接差异化同步

举例，某个时刻Leader服务器的事务队列对应的ZXID依次是：

1
2
3
4
5
0x200000001
0x200000002
0x200000003
0x200000004
0x200000005

而需要数据同步的服务器最后处理的ZXID为：

1
0x200000003

这种场景就执行“直接差异化同步”，Leader会依次将0x200000004，0x200000005同步给服务器，同步过程中顺序如下：

3.2、先回滚再差异化同步

假如在ZooKeeper集群中有A、B、C三台服务器，B当选为Leader服务器。

某个时刻，B正要处理一个ZXID=0x200000003的事务，并且已经将该事务写入到B服务器的本地的事务日志中，就在B要发送给其他Follower A、C机器进行同步的时候，B服务器挂了，Proposal并没有发送出去，而此时此时ZooKeeper会进行新一轮选举。假设A当选为新的Leader服务器对外进行工作，客户端又提交了

1
2
0x300000001
0x300000002

而此时之前的奔溃的B服务器再次启动，并开始进行数据同步。

因为B之前为Leader，故它的本地日志中事务编号为：

1
2
3
0x200000001
0x200000002
0x200000003

而A、C的本地日志中的事务编号为：

1
2
3
4
0x200000001
0x200000002
0x300000001
0x300000002

这时候就需要A服务器对数据进行回滚之后再同步，这个就称之为“先回滚再差异化同步”

3.3、仅回滚同步

先回滚再差异化的特殊模式。

3.4、全量同步

如：新加入的Follower服务器。


三、Raft协议


四、Gossip协议