您的位置: 首页  >  文章  >  Zookeeper选举算法与数据一致性

Zookeeper选举算法与数据一致性

分类: 文章 • 2022-12-31 00:30:27

在前面的两篇文章中了解过了Zookeeper的基本原理使用以及分布式集群的基本CAP定理：

ZAB协议

Zookeeper内部基于ZAB（Zookeeper Atomic Broadcast原子广播协议）协议来实现，其选举过程与数据同步都依赖于此协议。该协议的核心算法如下：
所有的事务请求都必须依赖于一个全局唯一的服务器来协调处理，其被称为Leader服务器，其余的被称为Follower，Leader接收客户端的一个请求，并且将其转换为一个Proposal（提议），然后将该Proposal广播给所有的Follower，如果接收到半数以上的Follower的正确反馈，那么会发送Commit命令给所有的Follower，提交该Proposal。

ZAB协议分为下面三个阶段：

  • 发现（Discover阶段）：即选举Leader过程。
  • 同步阶段：即选举完成后，Follower或者Observer同步最新Leader的最新数据。
  • 广播阶段：当同步完成之后，接收客户端的请求，广播给所有的服务器，实现数据在集群中的多副本存储。

在Zookeeper中，所有的服务器主要被分为下面三种角色：

  • Leader：事务请求的唯一调度者和协调者，保证事务处理的顺序。
  • Follower：处理客户端的非事务请求，转发事务请求给Leader，参与Leader的选举和Proposal的提议。
  • Observer：处理客户端的非事务请求，转发事务请求给Leader，不参与任何选举，主要为了提高读性能。

Zookeeper的选举过程

在ZK的选举过程中，主要有下面四种状态，由org.apache.zookeeper.server.quorum. ServerState这个枚举类维护这四种状态，源码如下：

   public enum ServerState {
        LOOKING, FOLLOWING, LEADING, OBSERVING;
    }
  • Looking：选举Leader过程
  • Following：跟随状态，表明当前节点是Follower
  • Leader：领导状态，表明当前节点是Leader
  • Observing：观察者转态，表明当前节点是Oberver

Zookeeper主要有三种选举算法LeaderElection，FastLeaderElection，AuthFastLeaderElection。在Zookeeper3.4.5之后，默认的使用FastLeaerElection选举算法。因此，这里只讨论ZK默认的选举算法。

它基于TCP协议进行通信，为了两个节点之间重复的建立TCP连接，ZK会按照myid小的节点去连接myid大的节点，比如myid为1的节点向myid为2的节点发起tcp连接。

在配置时，我们会发现需要配置两个端口号，第一个端口号2888，是通信和数据同步的端口号，第二个端口号3888，是进行选举的端口号。

该算法的实现在ZK的源码的FastLeaderElection类中可以查看到，如下图所示：
Zookeeper选举算法与数据一致性

在了解其算法之前先理解以下词的意思：

  • zxid：64位，高32位代表主进程周期epoch，每选举一次，则主进程周期加1，低32在选举完成之后，表示事务单调递增的计数器，从0开始。
  • myid：每个server的id

其算法描述如下：
server在启动或者恢复加入集群中时（此时没有leader，服务器处于looking状态），每个server都会选举自己为leader，然后server会发送自己的(server id,zxid)到其他server中，这里会先比较epoch，即zxid的高32位，然后比较server id的大小，具体比较规则如下：

1.如果接收到的epoch大于自己的epoch，则将刷新自己的epoch，更新为最大的epoch，然后将该消息广播到所有server中
2.如果接收的epoch小于自己的epoch，则将自己的epoch发送给对方
3.如果接收到的epoch和自己的相等，则比较server id，id值大的胜出，广播该消息。

接着所有的server根据广播的消息做出选举，即使没有所有的server的消息，只要有半数以上的server支持某个server，那么该server就会称为leader，接着会进行同步操作，选举结束。

举例1：一个集群三个节点启动，myid分别是1，2，3。每个节点都没有数据。

  • 节点1：启动，zxid为0，myid为1，读取自己的zxid和myid。
  • 节点2：启动，zxid为0，myid为2，读取自己的zxid和myid并且进行广播，此时节点1和节 点2的zxid都为0，比较myid，此时节点2的myid大，所有节点1支持节点2，节点2支持自己，因此节点2胜出，成为leader，节点1称为follower。
  • 节点3：此时集群中已有leader，加入集群中，成为follower。

举例2：三台server，server2为leader，此时server2宕机，server1和server3成为looking状态

  • server1发起投票，选举自己成为leader，给自己投一票，然后广播自己的消息(server id:1 , zxid:100)。
  • server3发起投票，给自己投一票，广播自己的消息(server id :3 , zxid:102)。
  • 此时server1收到server3的消息，server3的zxid大于自己的，改变自己的投票给server3。
  • server3收到server1的消息，zxid小于自己的，因此不改变自己的投票。
  • 统计投票结果，server3胜出，成为leader，server1成为follower。

当server加入时，服务器不是looking状态，此时判断收到的epoch，如果和自己的epoch相等，则统计投票结果，判断自己是否得到半数以上的server的支持，如果是则成为leader。如果不相同，则表明集群中有leader，自己成为follower，此时同步最新数据，退出选举。

提问：为什么要求半数以上的server投票支持才能成为leader？
这个问题很少有人能说出其具体原因（至少我碰到的人中几乎都不知道），要说原因，我们都知道zookeeper是一主多备的集群架构，如果得不到半数以上的server的选举，当集群发生脑裂时，可能会产生多个主节点，这样不符合ZK的设计初衷，数据的一致性也得不到保证，（好比一个人不能同时接收到两个大脑的控制，那不是乱了套了？），比如，有7台server，server1-server4和server5~server7之间发生脑裂，那么各自选举出leader，那么集群中就会出现两个Leader。而要求半数以上的投票结果则防止了这种现象的发生。

Zookeeper的同步过程

当leader选举完成之后，就需要将最新Leader的消息同步。
首先在leader端：
leader需要告知其他服务器当前的最新数据，即最大zxid是什么，此时leader会构建 一个NEWLEADER的数据包，包括当前最大的zxid，发送给follower或者observer，此时leader会启动一个leanerHandler的线程来处理所有follower的同步请求，同时阻塞主线程，只有半数以上的folower同步完毕之后，leader才成为真正的leader，退出选举同步过程。
Follower端：
首先与leader建立连接，如果连接超时失败，则重新进入选举状态选举leader，如果连接成功，则会将自己的最新zxid封装为FOLLOWERINFO发送给leader

同步算法：

  • 直接差异化同步（DIFF同步）
  • 仅回滚同步，即删除多余的事务日志（TRUNC）
  • 先回滚再差异化同步（TRUNC+DIFF）
  • 全量同步（SNAP同步）

差异化同步（DIFF）：
条件：MinCommitedLog < peerLastZxid < MaxCommitedLog
举例：leader的未proposal的队列中有0X50001,0X50002,0X50003,0X50004，0X50005，此时follower的peerLastZxid为0X50003，因此需要使用差异化同步将0X50004和0X50005同步给follower。同步顺序如下：
0X50004 -> Proposal -> Commit
0X50005 -> Proposal -> Commit

TRUNC+DIFF同步：
假设此时leaderB发送proposal并且提交了0X50001,0X50002，但没有提交0X50003，但是没有发送commit命令宕机，如果server C成为leader，经过同步后其自大MaxCommitedLog为0X60002，此时server B重新加入集群，由于Leader C中没有proposal 0X50003的提交记录，因此，发送TRUNC回滚数据，回滚完成之后，C向B发送确认消息，确认当前B的最新zxid为0X50002，然后发送DIFF进行差异化同步，此时B发送ACK给C，接着C会差异化同步相应的Proposal，然后提交，接着通知B，B在同步完成之后会发送确认ACK消息给C，同步结束。

全量同步（SNAP）
使用与当一个节点宕机太久，中间已经生成了大量的文件，此时集群的MinCommitedLog比宕机节点的最大zxid还要大，此时需要进行全量同步。

首先leader会发送SNAP命令给follower，follower接收到命令后进入同步阶段，leader会将所有的数据全量发送给follower，follower处理完毕之后leader还会将同步期间发生变化的数据增量发送给follower进行同步。

到这里本篇文章已经讲述完了Zookeeper的选举过程已经数据一致性同步过程，如有任何问题，欢迎各位前辈留言指教。

如果你想和我们一起讨论学习java，大数据方面的知识，欢迎加群同步进步：731423890

相关推荐