• 新版网站前后台即将上线,2019年将致力于提高文章质量,加大原创力度,打造一个更加舒适的阅读体验!
  • 极客文库小编@勤劳的小蚂蚁,为您推荐每日资讯,欢迎关注!
  • 新版网站前后台即将上线,2019年将致力于提高文章质量,加大原创力度,打造一个更加舒适的阅读体验!
  • 如果有任何体验不佳的地方,欢迎向客服反馈!

zookeeper 入门系列 :zab 协议


上一章讨论了 paxos 算法,把 paxos 推到一个很高的位置。但是,paxos 有没有什么问题呢?实际上,paxos 还是有其自身的缺点的:

1. 活锁问题。在 base-paxos 算法中,不存在 leader 这样的角色,于是存在这样一种情况,即 P1 提交了一个 proposal n1 并且通过了 prepare 阶段;此时 P2 提交了一个 proposal n2(n2>n1)并且也通过了 prepare 阶段;P1 在 commit 时因为已经通过了 n2 而被拒绝;于是 P1 继续提交一个 proposal n3 并且通过 prepare 阶段;巧的是此时 P2 开始 commit 了,由于 n2<n3 再次被拒绝……如此循环往复。这种情况被称为活锁。即整个系统都没死,但由于互相请求资源而被互相锁死。为了不发生活锁的情况,最简单的方式当然是缩减 proposer 到一个,这样就不会发生互相请求锁死的情况,也即退化。事实上很多后来的工业级协议,都是 paxos 协议的退化或者变种。

2. 复杂度问题。base-paxos 协议中还存在这样那样的问题,于是各种变种 paxos 出现了,比如为了解决活锁问题,出现了 multi-paxos;为了解决通信次数较多的问题,出现了 fast-paxos;为了尽量减少冲突,出现了 epaxos。可以看到,工业级实现需要考虑更多的方面,诸如性能,异常等等。这也是为啥许多分布式的一致性框架并非真正基于 paxos 来实现的原因。

3. 全序问题。对于 paxos 算法来说,不能保证两次提交最终的顺序,而zookeeper需要做到这点,可以参考文献 1。

For high-performance, it is important that  
ZooKeeper can handle multiple outstanding state changes requested by the client and  
that a prefix of operations submitted concurrently are committed according to FIFO  
order.

基于以上这些原因,zookeeper并没有用 paxos 作为自己实现的协议,取而代之采用了一种称为 zab 的协议,全称是zookeeper atomic broadcast。下面简单介绍一下 zab 协议。

上面说过了,paxos 存在活锁问题,为了解决活锁问题,zab 引入了 leader,但是单 leader 就是赤裸裸的单点问题,如何解决这个单点呢?

paxos 采用的方法是 leader 选举(没有采用主备,因为主备过于固定,不够分布式)。leader 选举就必然出现状态不一致的情况,于是就有着同步这样的过程。

zab 协议分为 4 个阶段,即阶段 0 为 leader 选举,阶段 1 为发现,阶段 2 为同步,阶段 3 为广播。而实际实现时将发现及同步阶段合并为一个恢复阶段。


0. leader 选举阶段。当集群中没有 leader 或者其他人感受不到 leader 时会进入这一阶段,这一阶段的主要目的是选出 zxid 最大的节点作为准 leader。

1. recovery 阶段。本阶段的主要目的是根据准 leader 的情况将数据同步到其他节点。同步完成后准 leader 变为 leader。

2. broadcast 阶段。本阶段的主要目的是 leader 收到请求,并将请求转为 proposal,其他节点根据协议进行批准或通过。broadcast 阶段事实上就是一个两阶段提交的简化版。其所有过程都跟两阶段提交一致,唯一不一致的是不能做事务的回滚。

广播的过程实际上类似于二阶段提交,但是如果实现完整的两阶段提交,那就解决了一致性问题,没必要发明新协议了,所以 zab 实际上抛弃了两阶段提交的事务回滚,于是一台 follower 只能回复 ACK 或者干脆就不回复了,leader 只要收到过半的机器回复即通过 proposal。但是这样的设计就存在很多问题,比如如果一个 follower 因为网络问题从头到尾一直没收到过 leader 的 proposal,后续的询问刚好落到这台 follower 上该如何处理?比如 leader 第一阶段收到了所有 follower 的 ACK 后提交,然后通知其他 follower 提交,这时自己挂了该如何处理?于是诞生了崩溃恢复阶段,旨在对各种不一致情况做出恢复和处理。

对于选举和恢复阶段。zab 算法需要确保两件事。

1. 已经处理过的 proposal 不能被丢弃

发生场景:leader 发送了 proposal,follower1 和 follower2 回复了 ACK 给 leader,leader 向所有 follower 发送 commit 请求并 commit 自身,此时 leader 挂了。leader 已经提交,但是 follower 尚未提交,这会存在不一致的情况。

确保方式:

a. 重新选举 leader 时只挑选 zxid 最大的 follower。因为至少半数的 follower 曾今回复 ACK,意味着重新选举时 zxid 最大的 follower 应该是当初回复 ACK 但尚未提交的其中一台。

b. 该 follower 即准 leader,将自身收到 prepare 但尚未提交的 proposal 提交

c. 在选举阶段准 leader 已经能拿到其余 follower 的所有事务集合,于是准 leader 根据各个 follower 的事务执行情况,分别建立队列,先发送 prepare 请求,再发送 commit 请求,让所有 follower 都同步到与 leader 一样的状态。

通过以上方式,能够确保提交过的 proposal 不会出现丢弃的情况。

2. 已经丢弃的 proposal 不能被重复处理

发生场景:leader 收到请求,包装为 proposal,此时网络挂了或者 leader 挂了导致其他 follower 没收到请求,此时进入崩溃恢复阶段,此时其他 follower 选主并成功之后这个挂了 的 leader 以 follower 的身份加入,此时它有一个多余的 proposal,与其他节点不一致。

确保方式:

通过 zxid 的大小能够直接确定。zxid 的编码方式为高 32 位为 epoch(即纪元,可以理解为代),低 32 位为每个 proposal 顺序递增的数字。每次变换一个 leader,则 epoch 加一,可以理解为改朝换代了,这样,新朝代的 zxid 必然比旧朝代的 zxid 大,新代的 leader 可以要求将旧朝代的 proposal 清除。

可以考虑一下,如果 leader 在崩溃恢复阶段就满血复活了,此时集群的情况是什么样的。 

参考



丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:zookeeper 入门系列 :zab 协议
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

欢迎 注册账号 登录 发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00