分布式与一致性协议之ZAB协议(一)

ZAB协议

概述

很多人应该都使用过ZooKeeper， 它是一个开源的分布式协调服务，比如你可以用它进行配置管理、名字服务等。在ZooKeeper中，数据是以节点的形式存储的。如果你要用ZooKeeper做配置管理，那么就需要在里面创建指定配置，假设创建节点/geekbang和/geekbang/time,步骤如代码所示:

[zk: localhost:2181(CONNECTED) 0] create /geekbang 123
Created /geekbang
[zk: localhost:2181(CONNECTED) 1] create /geekbang/time 456
Created /geekbang/time
1
2
3
4

我们分别创建了配置节点/geekbang和/geekbang/time,对应的值分别为123和456.那么在这里提个问题:你觉得在ZooKeeper中能用兰伯特的Multi-Paxos实现各节点数据的公式一致吗？
当然不行。因为兰伯特的Multi-Paxos虽然能保证达成共识后的值不再改变，但它并不关心达成共识的值是什么，也无法保证各值(也就是操作)的顺序性。而这时ZAB协议着力解决的，也是你理解ZAB协议的关键。
为了更好地理解这个协议，接下来将分别以如何实现操作的顺序性、领导者选举、故障恢复、处理读写请求为例展开具体讲解。希望能在全面理解ZAB协议的同时，加深对Paxos算法的理解，接下来，我们从ZAB协议的最核心设计目标(如何实现操作的顺序型)出发，了解它的基础原理。
老规矩，我们先来看一道思考题。
假如有一个由节点A、B、C组成的分布式集群(如图所示)，我们要设计一个算法来保证指令(比如X、Y)执行的顺序型，比如指令X在指令Y之前执行，那么我们该如何设计这个算法呢？

如何实现操作的顺序型？

在了解如何实现操作的顺序性之前，我们先来了解下为什么Multi-Paxos无法保证操作的顺序性。

为什么Multi-Paxos无法保证操作的顺序性

为了让你真正理解这个问题，举个具体的例子演示以下(为了演示方便，我们假设当前所有节点上被选定指令的最大序号都为100，那么新提议的指令对应的序号就会是101),假设这时节点A故障了，新当选的领导者为节点B.节点B当选领导者后，需要先作为学习者了解目前已被选定的指令。节点B学习之后，发现当前被选定指令的最大序号为100(因为节点A故障了，它的被选定指令的最大序号102无法被节点B发现)，那么它可以从序号101开始提议新的指令。这时节点B接收到客户端请求，并提议指令Z,指令Z被成功复制到节点B、C，如图所示。

假设这时节点B故障了，节点A故障恢复了，选举出领导者C后，节点B故障也恢复了。节点C当选领导者后，需要先作为学习者了解目前已被选定的指令，这时它执行Basic Paxos的准备阶段就会发现之前选定的值(比如Z、Y),然后发送接受请求，最终在序号101、102达成共识的指令是Z、Y，如图所示。

可以看到，原本预期的指令是X、Y，最后变成了Z、Y。现在，你应该可以知道为社么Multi-Paxos不能达到我们想要的结果了吧？
这个过程其实很明显地验证了"Multi-Paxos虽然能保证达成共识后的值不再改变，但它不关心达成共识的值是什么"。
我们接着回到前面的问题，假设我们在ZooKeeper中直接使用了兰伯特的Multi-Paxos，那么系统在创建节点/geekbang和/geekbang/time时就可能会出现先创建节点/geekbang/time的情况，这样肯定就出错了，如代码所示

[zk: localhost:2181(CONNECTED) 9] create /geekbang/time 456
Node does not exist: /geekbang/time
1
2

因为创建节点/geekbang/time时找不到节点/geekbang，所以创建失败。
在这里多说几句，除了Multi-Paxos，兰伯特还有很多关于分布式的理论，这些理论都很经典(比如拜占庭将军问题)，但也因为提出的时间太早了，与实际场景结合的不多，所以后续的众多算法都在这些理论的基础上做了大量的改进(比如，PBFT、Raft等算法)。
另外再延申一下，其实ZAB论文"Zab:High-Performance Broadcast for Primary-Backup System"中关于Paxos问题的分析是有争议的。ZooKeeper当时应该考虑的是Multi-Paxos，而不是有多个提议者的Basic Paxos.因为在Multi-Paxos中，领导者作为唯一提议者，是不存在同时有多个提议者的情况。也就是说，Paxos(更确切地说是Multi-Paxos)无法保证操作的顺序性，但问题的原因不是ZAB论文中演示的原因，本质上是因为Multi-Paxos实现的是一系列值的共识，而不关心最终达成共识的值是什么,也不关心各值得顺序，就像上面演示的过程那样。
既然Multi-Paxos不合适，ZooKeeper是如何实现操作的顺序性的呢？答案是它采用了ZAB协议。
你可能会说:Raft算法可以实现操作的顺序性，为什么ZooKeeper不采用Raft算法呢？这个问题的答案其实比较简单，因为Raft算法是在2013年才正式提出，而ZooKeeper是在2007年开发出来的。

注意

说到ZAB协议，很多人可能有这样的疑问:为什么ZAB协议的作者在"Zab vs. Paxos"宣称ZAB协议不是Paxos算法，但又有很多资料提到ZAB协议是
Multi-Paxos算法呢？究竟该如何理解呢？
我的看法是，你可以把它理解为Multi-Paxos算法。因为技术是发展的，概念的内涵也在变化。ZAB协议与Raft算法(主备、强领导者模型)非常类似，它是作为共识算法和Multi-Paxos算法提出的。当它被广泛接受和认可后，共识算法的内涵也就丰富和发展了，不仅能实现一系列值的共识，还能保证值的顺序性。同样，Multi-Paxos算法不仅指代多次执行Basic Paxos的算法，还能指代主备、强领导者模型的共识算法。
当然，在学习技术过程中，我们不可避免地遇到有歧义、有争议地信息，比如，有人提到，“从网桑搜了搜相关资料，发现大部分资料将谣言传播等同于Gossip协议，也有把反熵等同于Gossip协议地，感到很迷惑”。这就需要我们不仅要在平时地工作和学习中认真、全面地学习理论，掌握概念地内涵，还要能"包容"和"发展"着理解技术