首页 > 代码库 > Zookeeper中的FastLeaderElection选举算法简述

Zookeeper中的FastLeaderElection选举算法简述

Zookeeper是一个开源的分布式应用协调项目, 当中为了保证各节点的协同工作,Zookeeper在工作时须要有一个Leader。 而Leader是怎样被选举出来的?Zookeep中使用的缺省算法称为FastLeaderElection。

Zookeeper的基本前提是多个节点都具备全局其他全部节点的基本信息(IP/port/SID),而SID是节点的唯一编号。

正常工作时”从节点“会从“主节点”(Leader)同步版本号信息,称为zxid。

 

一旦整个系统重新启动或某部分节点(特殊是Leader)重新启动时。就须要又一次选举Leader。

Leader选举算法的核心就是不论什么节点都与其他节点交换信息(通过tcp连接)。通过一系列迭代,终于确定某一个受到大多数(>N/2)节点推荐的Leader。

所谓推荐是依据zxid(优先)和sid值更大则推荐之。

节点启动时,先是推荐自己,然后与其他全部节点尝试建立连接。Zookeeper保证两个节点仅仅保持一个tcp连接,由于tcp连接是双工的,全部一个连接足矣。全部的节点间通信能够理解成为异步方式。节点在发送信息给其他节点时无需等待对方处理结果,这与类似http的request/response模式是不同的。 

本节点在选举阶段(Looking状态)维持有一个推荐Leader节点(初始值是自己)。之后便是进入循环,就是接收全部不论什么其他节点的信息(如: SID/zxid/推荐Leader节点)。然后依据这些信息调整本节点保持的”推荐Leader节点“,一旦该值发生变化。即发送该信息给全部其他节点(广播),该循环会持续到自己或其他节点确定出Leader,即上面提到的受到大多数节点推荐的即为Leader。

进一步思考:感觉这样的算法在节点数非常多的情况下会有非常多的消息交互, 如果是N个节点,最坏的情况下,一个节点要经过N-1次迭代(推荐Leader节点有变化),每次迭次要发N-1个消息, 所以发送消息达N-1的平方。

不知我的理解是否正确。希望有高手指正。

Zookeeper中的FastLeaderElection选举算法简述