一致性协议 - paxos

算法 云原生
907

在分布式系统中，如果需要确保数据一致性，需要构建一些算法模型，称为一致性协议，而 zookeeper 作为一个保证 CP 的分布式系统，同样使用了一致性协议 —— zab 协议，而在此之前需要先了解 paxos 算法 。

Paxos 算法

Paxos 算法是 Lamport 宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。

问题背景

在 CP 分布式系统中，因为要具有 分区容错性 ，因此数据不可能只存在于一台主机，否则会产生单点故障。需要将数据存放到多台主机，而这些主机随时可能出现宕机，网络问题 (消息延迟、丢包、重复、乱序、网络分区) 等导致各个主机的数据不一致，例如当某个数据需要更新时，一半主机正常更新，而剩下一半主机因为网络问题没有收到更新请求，此时如果客户端需要请求该数据，则无法保证数据一致性（即客户端获取的数据在不同主机上有不同的结果）。

Paxos 算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对 某个数据的值 达成 一致 ，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

当然，CAP 定理告诉我们如果要实现 CP，则无法保证高可用，因此该算法允许进行数据同步，而在数据同步时，系统可以不可用 。

相关概念

Paxos 算法中，有三种角色：

  • Proposer 提案者
  • Acceptor 接受者
  • Learners 学习者

具体的实现中，一个节点可能同时充当多重角色，比如 既是 Proposer 又是 Acceptor 还是 Learners 。

提案，在消息的同步过程中，提案者可能会提出一个提案。一个提案包含一个提案编号和数据，每当一个提案被提出和被选中后，其数据就作为这个分布式系统的整体数据，客户端请求的数据为某个被选中的提案 。

这里只需要知道一个提案包含 提案编号 和 提案数据，具体过程之后分析 。

提案提出与接收过程

Proposer 会选择一个提案编号 N，然后向半数以上的 Acceptor 发送编号为 N 的 Prepare 请求 。

如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Accpetor 已经响应过的所有 Prepare 请求的编号，则该 Acceptor 将其接受过的编号最大的 提案 (如果有的话) 作为响应反馈给 Proposer，同时该 Acceptor 将不在接受任何 编号 小于 N 的提案 。此外，如果该 Acceptor 已经响应过比 N 大的提案，则直接不响应，或响应 error 。

Proposer 会汇总所有 Acceptor 返回的 输入，如半数以上的 Acceptor 都无响应或响应 error，则 Proposer 会将 N + 1 并再次尝试。如果某个 半数以上的 Acceptor 有返回提案，着说明 之前已经有被接受的提案（可能是之前的 Proposer 宕机而该 Proposer 为重新选取的新 Proposer），则 Proposer 会提取返回 编号最大 的提案中的数据，与刚刚的 编号 N 一起组成一个提案，并提出。如果返回的响应中没有满足添加的提案，则说明之前的提案已经失效，或没有提案，此时 Proposer 可自行决定数据 (同时，如果需要更新数据，则也可以自行决定)

一个提案提出后，Acceptor 可以接受也可以不接受，Proposer 无法干涉。

保持活性

为了保证该算法的活性，在某个时刻，只能有一个 Proposer ，需要投票选取，投票选取过程该算法没有规定 。

当分布式刚启动时，此时没有任何提案被接受，因此第一个 Proposer 的 Prepare 请求将不会收到提案响应，此时 Proposer 可自行决定提出提案的数据 。

而当 Proposer 宕机后，选取新的 Proposer，该 Proposer 则会发送 Prepare 请求尝试获取当前分布式系统接受过的编号最大的提案 。

除此之外，还需要一些其他规则：

  • 每个 Acceptor 必须接受它第一个提案
  • 每个 Acceptor 必须接受它没有承诺不接受的提案，只要该提案的编号比它当前接受的提案编号大
  • 每个 Proposer 被选举上时必须提出一个提案

提案学习

Learner 并不会对提案的过程做出任何干涉，只是为了提高分布式并发能力而在不影响原来的决策的前提下添加并发节点 。

Learner 的学习有以下三种方案：

  • Acceptor 每当接受一个提案，就将该提案发送给 Learner，Learner 每次收到提案，都会更新自己的数据。
  • Acceptor 每当接受一个提案，就将该提案发送给 主 Learner，然后主 Learner 再通知其他 Learner。
  • Acceptor 每当接受一个提案，就将该提案发送给一个 Learner 集群，然后再通知其他 Learner (又是一个分布式系统)

实际运用

该算法的过程看似简单，但是却解决了许多问题，在这个模型下，可以从数学上证明，只要在每一个时刻有半数以上的主机正常运行，则整体就能保持正常运行。这里省略推导过程，直接给出实际过程。

Paxos 是一种通用的数据一致性算法，其作为算法，只是提供一种抽象的思路。在真正实现的时候还需要考虑许多问题。比如 Proposer 选举以及提案提出时机等问题。

以下为我个人猜想中使用 paxos 的一种一致性具体协议：

  1. 客户端发起数据请求
  2. 收到请求的主机向当前 Proposer 请求 Proposer 提出的最后一个提案
  3. 如果 Proposer 有响应，则进入 4 ，否则 进入 6
  4. 如果 Proposer 返回的提案与主机的提案一致，则直接返回，否则进入 5
  5. 该主机向 Proposer 发出数据不一致信息，Proposer 会重新进入 提案提出与接收过程，在 Prepare 请求 后重新提出新的提案 。然后回到 2
  6. 如果 Proposer 没有响应，则认为 Proposer 宕机，则向整个集群发送重新选举 Proposer 的请求，开始重新选举新的 Proposer
  7. 新的 Proposer 必须提出新的提案，在此之前会先使用 Prepare 尝试获取之前接受的最后一个提案。然后回到 2

可以看出该模型下，使用了 Paxos 的提案提出和接受规则，但该过程如果一旦中途发送问题，则需要进入数据同步阶段，而在该阶段没有数据返回，因此该模型不具有高可用性 。

Zab 协议

Zab 协议全称是 Zookeeper Atomic Broadcast 协议

Zab 借鉴了 Paxos 算法，但 Zab 并不是一种通用的分布式一致性算法，而是一个专门为 Zookeeper 设计的支持崩溃恢复的原子广播协议 。

问题背景

Zookeeper 实现了主备模式的系统架构来保持集群中各个副本之间的数据一致性 。

其中主设备称为 Leader，用于处理所有的事务请求 (写请求)

从设备称为 Follower，用于处理非事务请求，当收到事务请求时需要转发给 Leader 。

而 Zab 协议主要解决该模型中两个问题

  • Leader 崩溃时，怎么重新开始选举新的 Leader (让所有节点知道要选举新的 Leader)
  • 如何进行 Leader 选举 (最终只选出一个 Leader 并且被所有 Follower 承认)

Zab 模式

在 Zab 协议中，一个分布式系统会有两种模式，并且每个时刻只会处于其中一个模式： 消息广播 和 崩溃恢复

消息广播

当集群中有过半的 Follower 服务器完成了 和 Leader 服务器的状态同步，则整个分布式系统进入 消息广播 模式，在该模式下能正常处理客户端的请求 。

而在该模式下，所有的事务请求都会被转发到 Leader，而 Leader 在处理的过程中，采用的是一种类似 paxos 的提案提出的过程。此外，对于分布式事务，则需要进行类似 2PC 的操作，在提案被正确接收后 Leader 还需要发送提交命令让各个 Follower 进行事务提交。

崩溃恢复

当 leader 崩溃后，集群将进入崩溃恢复，崩溃恢复一般分为四个阶段

  • 选举 - 选举新的 Leader 候选人
  • 发现 - 为候选人投票，如果超过半数同意，则新的 leader 产生，进入新的 epoch
  • 同步 - 集群将进行同步，保证各个节点的一致性（类似 paxos 中新的 Proposer 提出新的提案）
  • 广播 - 集群回到消息广播模式，开始接受请求

恢复过程中，该分布式系统将无法处理客户端的任何请求，此时可不可用。

ZXID

zxid - 事务ID，高 32 位为 epoch，低 32 为 递增的事务编号 (提案编号)

epoch - 年代，从1 开始，每次选举新的 leader ，epoch 加一

节点状态

LOOKING - 不确定 leader 状态，该状态下的节点认为 集群中 没有 leader，会发起 leader 选举，同时该状态的节点不会处理客户端的请求。

FOLLOWING - 跟随者状态，表面当前角色是 Follower

LEADING - 领导者状态，表面当前角色是 Leading，它会维护与其他 follower 的心跳，并且新的提案也会附带到心跳包中。

OBSERVING - 表面当前服务器的角色是 Observer，不具有投票权。

脑裂

当出现网络分区时，有可能整个集群被分为两个局域网 。此时如果 Follower 若与 leader 不在同个分区，则不会收到 leader 的心跳，则会开始进行新的选举。总体来说，当出现分区，可能会出现以下四种情况的分区：

  1. 分区中存在 Leader 同时该分区中节点数量多于原分布式系统的半数

    该分区依然可以正常对外提供服务，包括事务请求

  2. 分区中不存在 Leader 同时该分区中节点数量多于原分布式系统的半数

    该分区中的 follower 会失去与 leader 的连接，并进入崩溃恢复选出新的 Leader，同时可以选出新，因为可能过半投票。然后同步后正常对外提供服务

  3. 分区中存在 Leader 同时该分区中的节点数量少于或等于原分布式系统的半数

    该分区中所有连接都照常，但无法进行任何事务请求，因为 Leader 发起的所有提案都不可能收到半数以上的 ack 请求 (follower 的 正确反馈)，因此总会失败回滚。

    但也可能 leader 会检查与 follower 的连接，当判断多数 follower 无法响应自己时，进行退位，重新选举，而此时就相当于情况 4，无法选出新的 Leader

  4. 分区中不存在 Leader 同时该分区中的节点数量少于或等于原分布式系统的半数

    该分区会开始重新选举 Leader，但因为不可能有候选人获得超过半数投票，因此会一直进行选举，不可能选出 Leader 。

以上各种情况中，只要总的节点数为奇数，则出现两个分区的情况下总会有 1 或 2 的情况，并且只有一个，因此建议构建奇数个节点的集群。

若分区出现 2 和 3 两种情况，则系统中会存在两个 Leader，在分区存在时少数分区的 Leader 无法完成事务请求，但当分区合并后，少数分区中的 Follower 与 Leader 会收到新 Leader 的心跳，同时比较 epoch，则 旧的 Leader 会退化成 Follower 与 其他 Follower 一起进入同步模式，同步新的 Leader。

选举算法

ZAB 默认采用 TCP 版本的 FastLeaderElection 选举算法。

选票中包含了几个信息：

  • logicClock 标识这是该节点发起的第几轮的投票
  • state 当前节点的状态
  • self_id 投票节点的 myid
  • self_zxid 投票节点上保存的数据的最大的 zxid
  • vote_id 被推举的节点的 myid
  • vote_zxid 被推举的节点上保存的数据的最大的 zxid

投票流程

  1. logicClock 自增

    节点将自己储存的 loginClock 自增

  2. 初始化投票

    将自己缓存的其他节点的投票意向清空，并广播自己的初始选票，初始选票为举荐自己

  3. 接受外部投票

    选举阶段，所有节点都会接受其他节点的选票，判断后更新自己的选票然后广播，直到推选出 leader

  4. 更新轮次

    外部选票的轮次比自己小，无视该选票

    否则，更新自己的轮次

  5. PK 选票

    若外部投票的 vote_zxid 比较大，则将自己的意向修改外部投票的意向，并广播，同时更新自己缓存

    若两者 vote_zxid 一致，则比较 vote_myid，同上。

  6. 统计选票

    如果已经确定有半数以上节点投票给自己，则将自己的投票中 state 修改为 leader，并广播，同时不在接收其他选票。

    收到 state 为 leader 的选票时，将自己状态修改为 follower

  7. 更新状态

    进入同步状态。