文章归档

zookeeper原理和实现

zookeeper比较重要的几篇论文:

  1. ZooKeeper’s atomic broadcast protocol: Theory and practice
  2. Zab: High-performance broadcast for primary-backup systems
  3. ZooKeeper: Wait-free coordination for Internet-scale systems
  4. 官方资料:http://zookeeper.apache.org/doc/trunk/

第一篇比较倾向zab协议的工程性实现,有伪代码比较好理解。第2篇重点是zab的数学原理,最后一篇讲述zookeeper的整体架构和设计。

zab协议定义了节点的:

  1. 三种状态:following, leading, election
  2. 三种角色:follower, leader, observer
  3. 四个parse:electing -> discovery -> sync -> broadcast

简单来说:

  1. electing:选举过程,因为zab定义了只有leader才能broadcast,所以后面三个过程都需要有一个leader。
  2. discovery:leader被选举出来后,following需要将自己的数据告知leader以便leader决策,leader要得到最新的数据
  3. sync:同步,将数据同步到集群所有的机器上,保证整个集群看到的数据都是一致的
  4. broadcast:广播提案和决策

在zookeeper的实现中,electing算法的基本策略是:谁的历史数据最新,谁就当选leader。因为leader总是会有最新的history数据,所以discovery和sync这两个步骤就合成了1个:recovery

  1. electing:选举过程,选lastZxid最新的当leader
  2. recovery:leader被选举出来后,和follower同步数据,主要是给follower发送 SNAP|DIFF|TRUNC 消息
  3. broadcast:广播提案和决策

1. Broadcast

zookeeper大部分时间在broadcast阶段,client读数据的时候不需要发起propose的,直接读节点的缓存即可。zookeeper提供顺序一致性。如果client需要写数据,过程如下:

  1. client发送修改给follower
  2. follower转发给leader,当然如果client连的是leader,这一步就省了
  3. leader准备proposal,广播给集群所有的follower
  4. follower发送ACK给leader
  5. leader发送COMMIT消息给所有follower
  6. follower处理COMMIT消息

上述过程更详细的可以参考 ZooKeeper’s atomic broadcast protocol: Theory and practice 论文的 Algorithm 3

考虑下宕机的情况:

  1. follower宕机:zookeeper提供顺序一致性保证,follower其实宕掉多少都没关系,只要leader不宕,follower重启之后和leader同步一下数据即可
  2. leader宕机 :follower需要重新选举

但是leader宕机比较棘手,是不是真宕机不好判断,分布式系统里通常只看网络连接的状态。

假设zookeeper集群被突然分成两个隔离的网络单元A和B,leader在A单元里,这两个单元里的机器都互相认为对方单元的机器宕机了,然后各自执行自己的选举策略,这种情况下,如何才能确保整个集群的数据一致性呢?如果出现两个leader,那么必然保证不了顺序一致性,如果只产生一个leader,那么其中有一个单元就会瘫痪,不过这个没有关系,只要网络恢复,集群状态仍然是一致。

所以现在的问题是这种情况下怎么才能保证只会选出一个leader?

  1. 集群数量必须是 2n + 1
  2. 只允许 n 个机器宕机,包括leader

2. recovery

每当leader宕机,集群选举出新的leader之后,recovery过程就会启动,主要目的是将集群状态恢复到一致状态(但似乎是允许丢失部分最新的数据)。这个过程的伪代码可以看 ZooKeeper’s atomic broadcast protocol: Theory and practice 论文的 Algorithm1&&Algorithm2以及Algorithm4

3. Fast Leader Election

FLE aims at electing a leader with highest lastZxid among a quorum. 具体伪代码过程可以看 ZooKeeper’s atomic broadcast protocol: Theory and practice 论文的 Algorithm6

  1. 一开始大家都投自己为leader
  2. 发现别人投的leader比自己投的leader的lastZxid高,跟着别人投
  3. 每个节点维护一个表,当发现某个leader超过半数人投票,选举结束

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>