yrl's blog
0%

共识性算法（一致性算法）

发表于 更新于 分类于 ，

一、paxos

概念

一种基于消息传递且具有高度容错性的共识性算法。

解决分布式共识性问题，即一个分布式系统中各个进程如何进某个值（决议）通过共识达成一致。

Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，最终决策学习者 (Learner)：

  • Proposer-提议者：提出提案（Proposal），信息包括提案编号（Proposal ID）、提议值（Value）。
  • Acceptor-决策者：参与决策，回应Proposer的提案。收到提案后可以接受提案，若Proposal获得多数Acceptors接受，则称该Proposal被批准。
  • Learner-学习者：不参与决策，从Proposers/Acceptors学习最新达成一致的信息（Value）。

Proposer向Acceptor集合发送提案，Acceptor集合中的每个成员都有可能同意该提案且每个Acceptor 只能批准一个提案，只有当一半以上的成员同意了一个提案，就认为该提案被选定了。

拜占庭问题

拜占庭问题：是指 拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的， 只能依靠通讯员进行传递命令，但是通讯员中存在叛徒，「它们可以篡改消息」，叛徒可以欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定， 如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。

Paxos算法的前提假设是不存在拜占庭将军问题，即通讯安全不会丢失，且发出的消息不被修改。

第一阶段

  • 一个Proposer-提议者选择一个提案编号（Proposal ID），让如prepare request中发送给其他Acceptor-决策者
  • 如果一个Acceptor-决策者接受了一个prepare request，其中的提案编号（Proposal ID）大于它之前回复过的prepare request，那么它会回复该请求，并承诺不接受比其小的提案编号（Proposal ID），并返回它已经接受的最大提案编号（Proposal ID）。

第二阶段

  • 如果Proposer-提议者收到了大多数Acceptor-决策者的回复，则会对这些Acceptor-决策者再发送一个accept request，其中包含提案编号（Proposal ID）、提议值（Value）

  • 如果一个Acceptor-决策者收到的提案编号（Proposal ID）不小于之前回复的其他请求的提案编号（Proposal ID），则接收此提议

总结

paxos协议会拒绝小于等于当前提议ID（处理或者未处理）的提议，当半数以上通过，该提议才会被通过

问题

当有两个Proposer-提议者依次剔除提案时

  • Proposer P1发送提案编号1的prepare请求，收到过半响应，完成阶段一
  • Proposer P2发送提案编号2的prepare请求，提案编号2大于提案编号1，收到过半响应，，完成阶段一
  • P1进入第二阶段，发送accept请求被Acceptor-决策者忽略，此时P1重新进入节点一，发送提案编号3
  • P2进入第二阶段，发送accept请求被Acceptor-决策者忽略，此时P1*2重新进入节点一，发送提案编号4**
  • 此时陷入死循环
  • 避免以上情况，Multi Paxos算法，选取一个主Proposer，只有主Proposer才能发起提案

二、Raft

Raft算法是Paxos算法的一种简化实现。点击查看动图

一个节点在任意状态时刻处于一下三种角色之一：

  • follower：所有节点都以follower的状态开始，如果没有收到leader消息则会变成candidate状态。
  • candidate：会向其他节点拉选票，如果得到大部分的票则成为leader，这个过程是Leader选举。
  • leader：所有对系统的修改都会先经过leader。

日志复制

  • 对于系统的修改都会先经过leader

  • 每个修改都生成一条日志，这些日志处理未提交状态，不会影响真实值

  • leader将日志复制到follower节点，

  • 当半数以上节点响应时，通知所有的follower正式提交

  • 此时整个系统处于一致状态。

选举-Leader Election

  • 每个节点生成随机选举超时时间，在这个时间内节点必须等待

  • 当超过此时间时，节点仍没有监听到leader的心跳，节点变成Candidate，发起投票

    • 重置选举超时时间
    • 发起选举投票（投自己一票）
      • 如果接收节点没有发起投票，则投给该Candidate，并重置自己的选举超时时间

  • 当Candidate获取半数以上票数时，当选leader

  • 平票或者票数不足时，本次term没有leader，等待有节点的计时器超时变成candidate开始新一轮的投票

三、ZAB

ZAB（Zookeeper Atomic Broadcast）是分布式协调服务ZooKeeper，专门设计的一种支持崩溃恢复的一致性协议。

基于该协议，ZooKeeper 实现了一种 主从模式的系统架构来保持集群中各个副本之间的数据一致性。

概念

节点角色

  • Leader ：负责整个Zookeeper 集群工作机制中的核心，主要工作有以下两个：

    • 事务请求的唯一调度和处理者，保证集群事务处理的顺序性
    • 集群内部各服务器的调度者

  • Follower ：它是 Leader 的追随者，其主要工作如下：

    • 处理客户端的非实物请求，转发事务请求给 Leader 服务器
    • 参与事务请求 Proposal 的投票
    • 参与 Leader 选举投票

  • Observer ：是 zookeeper 自 3.3.0 开始引入的一个角色，它不参与事务请求 Proposal 的投票，也不参与 Leader 选举投票，只提供非事务的服务（查询），通常在不影响集群事务处理能力的前提下提升集群的非事务处理能力。

节点状态

  • LOOKING：不确定Leader状态。该状态下的服务器认为当前集群中没有Leader，会发起Leader选举。
  • FOLLOWING： 跟随者状态。表明当前服务器角色是Follower，并且它知道Leader是谁。
  • LEADING：领导者状态。表明当前服务器角色是Leader，它会维护与Follower间的心跳。
  • OBSERVING： 观察者状态。表明当前服务器角色是Observer，与Folower唯一的不同在于不参与选举，也不参与集群写操作时的投票。

流程

Leader写

  • 当leader收到事务请求后，将请求事务转化成事务proposal。

  • 由于leader会为每个follower创建一个队列，按照FIFO的策略，将该事务proposal放入响应队列，保证事务的顺序性。

  • follower收到后会将其以事务的形式写入到本地日志中，并且向leader发送Ack信息确认。

  • 当有一半以上的follower返回Ack信息时，leader会提交该提案并且向其它节点（Follower 、Observer ）发送commit信息。

leader自己的ack也被计算、不统计Observer的ack、未commit的数据对客户端不可见

整个过程类似于两阶段提交，但却有所不同，只需半数以上follower成功即可提交。

Follower/Observer写

  • Follower/Observer均可接受写请求，但是不直接处理，而是将写请求转发给Leader处理
  • 其余流程与Leader写一致

读操作

Leader/Follower/Observer都可直接处理读请求，从本地内存中读取数据并返回给客户端即可。

选举

ZXID

一个全局有序的 64 位的数字

  • 高32位，存储epoch，代表选举周期，每次选举都会取出高32位+1，低32位置零
  • 低32位，事务计数器，每个事务请求会导致其+1，保证全局递增

每当选举一个新leader时，都会产生一个新的epoch。

使用新epoch的作用是，防止旧leader网络恢复等情况，重新连上集群，向其他的follower发送请求，follower对比epoch发现当前epoch大于旧leader的epoch，忽略这个请求。

myid

每个ZooKeeper服务器，都需要在数据文件夹下创建一个名为myid的文件，该文件包含整个ZooKeeper集群唯一的ID（整数），作为该节点在集群中的标识

1

zoo.cfg配置文件中，server.x的x对应的就是上面myid文件中的1

1
2
3
4
5
#zoo.cfg配置文件
server.1=192.168.142.121:2888:3888
server.2=192.168.142.122:2888:3888
server.3=192.168.142.123:2888:3888
server.4=192.168.142.124:2888:3888

流程

  • 每轮投票，每个节点维护自己的logicClock进行自增操作
  • 初始化投票，通过广播把票投给自己
  • 接收外部投票
    • 外部投票的logicClock大于自身，说明自身落后于其他节点的选举轮次，将票箱数据更改为外部投票数据并广播出去
    • 外部投票的logicClock小于自身，说明自身选举轮次领先，忽略该外部投票
    • 相等，进行投票PK
      • zxid大的优先，修改自己的数据广播出去
      • zxid若相同，比较myid，小的优先，修改自己的数据广播出去
  • 统计选票，当过半的节点认可自己的投票则终止投票，否则继续接受其他节点投票
  • 更新节点状态，当过半的票投给自己，则修改状态为LEADING，否则修改为FOLLOWIN
  • 数据同步
    • follower将自己最大的zxid发送给新leader
    • 新leader找出follower的zxid与自己zxid之间commit的数据同步给follower
  • 数据同步完毕后通知follower可以对外提供服务

四、Gossip

一个节点想要分享一些信息给网络中的其他的一些节点。于是，它周期性的随机选择一些节点，并把信息传递给这些节点。这些收到信息的节点接下来会做同样的事情，即把这些信息传递给其他一些随机选择的节点。

相比于Paxos、Raft、Zab等强一致性协议，Gossip可能会出现一段时间的不一致性，但会达到最终一致性。

流程

  • 固定周期，随机选择与它相连的N个节点传播消息
  • 节点收到消息后，会在下一个周期选择除给它发消息外的其他相连节点传播消息。尽管需要一定时间，但是最终所有节点都拥有相同的消息

五、Distro

  • nacos每个节点负责部分的写请求
  • 每个节点会把自己负责的新增数据同步给其他节点
  • 每个节点定时发送自己负责数据的校验值到其他节点来保持数据一致性
  • 每个节点独立处理读请求
  • 新加入的Distro节点会进行全量数据拉取（轮询所有节点发送请求拉取他们各自负责的数据）