极客时间已完结课程限时免费阅读

15 | ZAB协议：如何实现操作的顺序性？

15 | ZAB协议：如何实现操作的顺序性？-极客时间

15 | ZAB协议：如何实现操作的顺序性？

2020-04-26 韩健 来自北京
《分布式协议与算法实战》
课程介绍

讲述：于航

时长11:34大小10.60M

你好，我是韩健。
很多同学应该使用过 ZooKeeper，它是一个开源的分布式协调服务，比如你可以用它进行配置管理、名字服务等等。在 ZooKeeper 中，数据是以节点的形式存储的。如果你要用 ZooKeeper 做配置管理，那么就需要在里面创建指定配置，假设创建节点"/geekbang"和"/geekbang/time"，步骤如下：
[zk: 192.168.0.10:2181(CONNECTED) 0] create /geekbang 123
Created /geekbang
[zk: 192.168.0.10:2181(CONNECTED) 1] create /geekbang/time 456
Created /geekbang/time
我们分别创建了配置"/geekbang"和"/geekbang/time"，对应的值分别为 123 和 456。那么在这里我提个问题：你觉得在 ZooKeeper 中，能用兰伯特的 Multi-Paxos 实现各节点数据的共识和一致吗？
当然不行。因为兰伯特的 Multi-Paxos，虽然能保证达成共识后的值不再改变，但它不关心达成共识的值是什么，也无法保证各值（也就是操作）的顺序性。而这就是 Zookeeper 没有采用 Multi-Paxos 的原因，又是 ZAB 协议着力解决的，也是你理解 ZAB 协议的关键。
那么为了帮你更好地理解这个协议，接下来，我将分别以如何实现操作的顺序性、领导者选举、故障恢复、处理读写请求为例，具体讲解一下。希望你能在全面理解 ZAB 协议的同时，加深对 Paxos 算法的理解。
今天这节课，我会从 ZAB 协议的最核心设计目标（如何实现操作的顺序性）出发，带你了解它的基础原理。
老规矩，在开始今天的内容之前，我们先来看一道思考题：
假如节点 A、B、C 组成的一个分布式集群，我们要设计一个算法，来保证指令（比如 X、Y）执行的顺序性，比如，指令 X 在指令 Y 之前执行，那么我们该如何设计这个算法呢？
图1
带着这个问题，我们进入今天的内容。

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

刚刚我提到“Multi-Paxos 无法保证操作的顺序性”。为了让你真正理解这个问题，我举个具体的例子演示一下（为了演示方便，我们假设当前所有节点上的被选定指令，最大序号都为 100，那么新提议的指令对应的序号就会是 101）。
首先节点 A 是领导者，提案编号为 1，提议了指令 X、Y，对应的序号分别为 101 和 102，但是因为网络故障，指令只成功复制到了节点 A。
图2
假设这时节点 A 故障了，新当选的领导者为节点 B。节点 B 当选领导者后，需要先作为学习者了解目前已被选定的指令。节点 B 学习之后，发现当前被选定指令的最大序号为 100（因为节点 A 故障了，它被选定指令的最大序号 102，无法被节点 B 发现），那么它可以从序号 101 开始提议新的指令。这时它接收到客户端请求，并提议了指令 Z，指令 Z 被成功复制到节点 B、C。
图3
假设这时节点 B 故障了，节点 A 恢复了，选举出领导者 C 后，节点 B 故障也恢复了。节点 C 当选领导者后，需要先作为学习者了解目前已被选定的指令，这时它执行 Basic Paxos 的准备阶段，就会发现之前选定的值（比如 Z、Y），然后发送接受请求，最终在序号 101、102 处达成共识的指令是 Z、Y。就像下图的样子。
图4
在这里，你可以看到，原本预期的指令是 X、Y，最后变成了 Z、Y。讲到这儿，你应该可以知道，为什么用 Multi-Paxos 不能达到我们想要的结果了吧？
这个过程，其实很明显的验证了“Multi-Paxos 虽然能保证达成共识后的值不再改变，但它不关心达成共识的值是什么。”
那么咱们接着回到开篇的问题，假设在 ZooKeeper 中直接使用了兰伯特的 Multi-Paxos，这时创建节点"/geekbang"和"/geekbang/time"，那么就可能出现，系统先创建了节点"/geekbang/time"，这样肯定就出错了：
[zk: 192.168.0.10:2181(CONNECTED) 0] create /geekbang/time 456
Node does not exist: /geekbang/time
因为创建节点"/geekbang/time"时，找不到节点"/geekbang"，所以就会创建失败。
在这里我多说几句，除了 Multi-Paxos，兰伯特还有很多关于分布式的理论，这些理论都很经典（比如拜占庭将军问题），但也因为太早了，与实际场景结合的不多，所以后续的众多算法是在这个基础之上做了大量的改进（比如，PBFT、Raft 等）。关于这一点，我在 13 讲也强调过，你需要注意一下。
另外我再延伸一下，其实在ZAB 论文中，关于 Paxos 问题（Figure 1 ​​​​）的分析是有争议的。因为 ZooKeeper 当时应该考虑的是 Multi-Paxos，而不是有多个提议者的 Basic Paxos。而在 Multi-Paxos 中，领导者作为唯一提议者，是不存在同时多个提议者的情况。也就是说，Paxos（更确切的说是 Multi-Paxos）无法保证操作的顺序性的问题是存在的，但原因不是 ZAB 论文中演示的原因，本质上是因为 Multi-Paxos 实现的是一系列值的共识，不关心最终达成共识的值是什么，不关心各值的顺序，就像我们在上面演示的过程那样。
那既然 Multi-Paxos 不行，ZooKeeper 怎么实现操作的顺序性的呢? 答案是它实现了 ZAB 协议。
你可能会说了：Raft 可以实现操作的顺序性啊，为什么 ZooKeeper 不用 Raft 呢？这个问题其实比较简单，因为 Raft 出来的比较晚，直到 2013 年才正式提出，在 2007 年开发 ZooKeeper 的时候，还没有 Raft 呢。

ZAB 是如何实现操作的顺序性的？

如果用一句话解释 ZAB 协议到底是什么，我觉得它是：能保证操作顺序性的，基于主备模式的原子广播协议。
接下来，我还是以 X、Y 指令为例具体演示一下，帮助你更好理解为什么 ZAB 能实现操作的顺序性（为了演示方便，我们假设节点 A 为主节点，节点 B、C 为备份节点）。
首先，需要你注意的是，在 ZAB 中，写操作必须在主节点（比如节点 A）上执行。如果客户端访问的节点是备份节点（比如节点 B），它会将写请求转发给主节点。如图所示：
图5
接着，当主节点接收到写请求后，它会基于写请求中的指令（也就是 X，Y），来创建一个提案（Proposal），并使用一个唯一的 ID 来标识这个提案。这里我说的唯一的 ID 就是指事务标识符（Transaction ID，也就是 zxid），就像下图的样子。
图6
从图中你可以看到，X、Y 对应的事务标识符分别为 <1, 1> 和 <1, 2>，这两个标识符是什么含义呢？
你可以这么理解，事务标识符是 64 位的 long 型变量，有任期编号 epoch 和计数器 counter 两部分组成（为了形象和方便理解，我把 epoch 翻译成任期编号），格式为 <epoch, counter>，高 32 位为任期编号，低 32 位为计数器：
任期编号，就是创建提案时领导者的任期编号，需要你注意的是，当新领导者当选时，任期编号递增，计数器被设置为零。比如，前领导者的任期编号为 1，那么新领导者对应的任期编号将为 2。
计数器，就是具体标识提案的整数，需要你注意的是，每次领导者创建新的提案时，计数器将递增。比如，前一个提案对应的计数器值为 1，那么新的提案对应的计数器值将为 2。
为什么要设计的这么复杂呢？因为事务标识符必须按照顺序、唯一标识一个提案，也就是说，事务标识符必须是唯一的、递增的。
在创建完提案之后，主节点会基于 TCP 协议，并按照顺序将提案广播到其他节点。这样就能保证先发送的消息，会先被收到，保证了消息接收的顺序性。
图7
你看这张图，X 一定在 Y 之前到达节点 B、C。
然后，当主节点接收到指定提案的“大多数”的确认响应后，该提案将处于提交状态（Committed），主节点会通知备份节点提交该提案。
图8
在这里，需要你注意的是，主节点提交提案是有顺序性的。主节点根据事务标识符大小，按照顺序提交提案，如果前一个提案未提交，此时主节点是不会提交后一个提案的。也就是说，指令 X 一定会在指令 Y 之前提交。
最后，主节点返回执行成功的响应给节点 B，节点 B 再转发给客户端。你看，这样我们就实现了操作的顺序性，保证了指令 X 一定在指令 Y 之前执行。
最后我想补充的是，当写操作执行完后，接下来你可能需要执行读操作了。你需要注意，为了提升读并发能力，Zookeeper 提供的是最终一致性，也就是读操作可以在任何节点上执行，客户端会读到旧数据：
图9
如果客户端必须要读到最新数据，怎么办呢？Zookeeper 提供了一个解决办法，那就是 sync 命令。你可以在执行读操作前，先执行 sync 命令，这样客户端就能读到最新数据了：
[zk: 192.168.0.10:2181(CONNECTED) 2] sync /geekbang/time
[zk: 192.168.0.10:2181(CONNECTED) 3] Sync returned 0
[zk: 192.168.0.10:2181(CONNECTED) 3] get /geekbang/time
456
cZxid = 0x100000005
ctime = Mon Apr 20 21:19:28 HKT 2020
mZxid = 0x100000005
mtime = Mon Apr 20 21:19:28 HKT 2020
pZxid = 0x100000005
cversion = 0
dataVersion = 0
aclVersion = 0
ephemeralOwner = 0x0
dataLength = 3
numChildren = 0
[zk: 192.168.0.10:2181(CONNECTED) 4]

内容小结

本节课我主要带你了解了为什么 Multi-Paxos 无法实现操作的顺序性，以及 ZAB 协议如何保证操作的顺序性。我希望你明确这样几个重点。
1. 兰伯特的 Multi-Paxos 只考虑了如何实现共识，也就是如何就一系列值达成共识，未考虑如何实现各值（也就是操作）的顺序性。
2.ZAB 是通过“一切以领导者为准”的强领导者模型和严格按照顺序处理、提交提案，来实现操作的顺序性的。
那么说到 ZAB，很多同学可能有这样的疑问：为什么 ZAB 作者宣称ZAB 不是 Paxos 算法，但又有很多资料提到 ZAB 是 Multi-Paxos 算法呢？到底该怎么理解呢？
我的看法是，你可以把它理解为 Multi-Paxos 算法。因为技术是发展的，概念的内涵也在变化。Raft 算法（主备、强领导者模型）与 ZAB 协议非常类似，它是作为共识算法和 Multi-Paxos 算法提出的。当它被广泛接受和认可后，共识算法的内涵也就丰富和发展了，不仅能实现一系列值的共识，还能保证值的顺序性。同样，Multi-Paxos 算法不仅指代多次执行 Basic Paxos 的算法，还指代主备、强领导者模型的共识算法。
当然了，在学习技术过程中，我们不可避免的会遇到有歧义、有争议的信息，就像在 11 讲留言区中，有同学提到“从网上搜了搜相关资料，发现大部分资料将谣言传播等同于 Gossip 协议，也有把反熵等同于 Gossip 协议的，感到很迷惑”。
这就需要我们不仅要在平时工作和学习中，认真、全面的学习理论，掌握概念的内涵，还要能“包容”和“发展”着理解技术。
最后，在本节课我们了解了 ZAB 协议的最核心设计目标（如何实现操作的顺序性），那么既然“所有数据都是以主节点的数据为准的”，主节点（也就是领导者）那么重要，那当它崩溃了，该怎么处理呢？下节课，我会重点带你了解这部分内容。

课堂思考

既然我提到在 ZAB 协议中，主节点是基于 TCP 协议来广播消息的，并保证了消息接收的顺序性。那么你不妨想想，如果 ZAB 采用的是 UDP 协议，能保证消息接收的顺序性吗？为什么呢？欢迎在留言区分享你的看法，与我一同讨论。
最后，感谢你的阅读，如果这节课让你有所收获，也欢迎你将它分享给更多的朋友。
编辑角：目前课程已经结束了，为了交付更好的内容，《分布式协议与算法实战》于 2020 年 4.26 日启动迭代计划，15 讲为迭代版本，后面也会对 ZAB 协议进行更细致化的讨论，敬请期待！
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享

赞 20

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
14 | PoW算法：有办法黑比特币吗？
下一篇
加餐 | ZAB协议（一）：主节点崩溃了，怎么办？
 写留言

精选留言(36)

  • Jialin
    2020-04-27
    如果 ZAB 采用的是 UDP 协议，无法保证消息接收的顺序性，主要是因为 TCP 协议本身支持按序确认，而 UCP 只能支持尽最大可能交付

    作者回复: 加一颗星:)

    共 5 条评论
    32
  • 充值一万
    2021-04-28
    这一节看得我一脸懵逼。。按照文中描述，Multi-Paxos 无法保证操作顺序性的原因是各节点可能先后宕机，然后最终恢复时，最终达成一致的提案可能不是预期的（X, Y 变成 Z, Y）。而ZAB 协议能保证顺序，是因为提案提交有序，TCP保证可靠通讯。 ？？？？？？？？？？？？？？？？？？？？？？？？ Multi-Paxos领导节点也可以顺序提案啊，也可以用TCP； ZAB 协议的节点也可能各种宕机啊？！
    展开
    共 2 条评论
    10
  • 爱德华
    2020-08-17
    老韩，课讲的很好，我有不懂的地方，想请教下。 zab是如何保证proposal提交的顺序型的？单纯的用zxid保证提交到FIFO队列依次广播是实现不了proposal提交的顺序性的。 zxid只能保证提交到队列顺序性，以及消息广播的顺序性。但是保证不了网络中消息先后到达follower的顺序，这是第一个问题。第二个问题就是，就算按照zxid的顺序依次到达了follower，但是follower处理每个proposal的时间是不一致的，也就是说后到达的proposal有可能先处理完，先给leader返回ack响应。这里除非zab处理是单线程的，才不会有这个问题。 我觉得zab中应该针对zxid做了特殊判断。 比如真正去提交的时候（第二阶段），先判断在此zxid之前proposal有没有提交，有的话等上一个提交了再提交。 或者另一个想法，当发现当前的需要提交的zxid之前的还有proposal没有提交，则拒绝提交，进去崩溃恢复模式。但是这样的话，leader很容易失去过半的follower。 不知道zab是怎么做的呢？
    展开
    共 1 条评论
    10
  • z
    2020-06-22
    "首先，需要你注意的是，在 ZAB 中，写操作必须在主节点（比如节点 A）上执行。如果客户端访问的节点是备份节点（比如节点 B），它会将写请求转发给主节点" 关于这一点写请求会转发到主节点， 如果客户端把X，Y发往了两个不同的备份节点，这时候主节点拿到X，Y的顺序是不是没办法保证？ 那最终执行的顺序还是没法保证呀

    作者回复: 加一颗星:)，存在这样的情况，但这不是问题，因为在实际场景中，如果我们想实现X、Y的顺序性，那么客户端可以连接一个节点，而不是多个节点，执行写操作。

    共 5 条评论
    8
  • 竹马彦四郎的好朋友影...
    2020-05-06
    本质上讲，zab和raft都是通过强领导者模型实现就多值达成共识的

    作者回复: 加一颗星:)

    8
  • andrewguo
    2020-06-06
    使用tcp协议来保证顺序的原因是 1. tcp协议栈能保证包的先后顺序 2. 虽然提案本身有递增的逻辑时钟，但zab里zxid要求不是严格连续，允许空洞。如果传输协议不能保证顺序，从节点获取提案N时无法判断是否还有比N小的提案未收到，从而无法执行。
    共 1 条评论
    5
  • 竹马彦四郎的好朋友影...
    2020-05-06
    怎么感觉zab和raft如果刨去leader选举之外就一模一样了，希望老师解惑，谢谢！

    作者回复: 加一颗星:)，在接下来的加餐中，我会补充个对比总结。

    共 2 条评论
    5
  • 达子不一般
    2021-10-05
    对文中举出的Multi Basic Paxos的实例的几个疑问： - 针对不同的key(X)、key(Z)，为何要使用相同的编号101？不同的key之间使用共识判断，有意义吗？ - 因为网络故障，指令只成功复制到了节点A 指令只成功复制到了节点A，那么返回给客户端是成功还是失败？如果是失败，那么被占据多数101的Z覆盖似乎也没啥问题 - A恢复后，102对应的Y涉及的节点不占有多数，为啥学习者C会学到102呢
    展开
    共 1 条评论
    4
  • 海连天
    2020-05-03
    感觉过程像极了两阶段提交

    作者回复: 加一颗星:)，可以对比着理解，理解为简化版的二阶段提交，基于“大多数”确认来提交。

    4
  • Heaven
    2020-08-18
    1.首先消息的前后性不能保证,因为TCP本质上是在接收和发送的两端都维护了一个栈的机制,模拟出了一条数据流,从而做到了顺序的传输,而UDP是无序的,可以在网上到处开车,可能导致消息前后错乱 2.但是消息的前后性我感觉可以从别的地方保证,可以从几点来分析下,对于失败重传,这个可以由发收双方进行手段性质的保证 而且在主节点不故障的情况下,是可以知道发送的消息,那么X不会的时候,Y也不会先提交 而且对于跟随者,只收到了Y的提交,估计也要等X的提交消息才能生效吧,不然即使是两个消息有依赖性,但是两个消息也不一定在一个TCP里面提交啊 最后,即使故障了,任期编号自然会更新,不会出现编号错乱的问题
    展开
    2
  • ezekiel
    2021-10-11
    老师您好！ 你可以看到，原本预期的指令是 X、Y，最后变成了 Z、Y。讲到这儿，你应该可以知道，为什么用 Multi-Paxos 不能达到我们想要的结果了吧？ ======================================== x、y并没有复制到大多数节点，在客户端角度来说应该是失败的。从服务端角度来说，C当选后为什么会接受A节点的y值呢？没有达成共识呀
    展开
    1
  • 熙成
    2021-09-20
    为什么 Multi-Paxos 无法保证操作顺序性？ 讲述疑惑： 提案编号既然是1，那序号101、102是表示什么？是提案内容吗？不应该看提案编号递增+1吗，为什么又搞出来个序号？
    1
  • --
    2021-05-10
    能否使用UDP得看zxid是不是连续递增的，本质上来说每个节点提案的偏序关系是一样的就能保证顺序。但是主节点故障之后，新主需要能够判断当前要提交的提案是不是第一个未提交的提案，即提案是否存在空洞。如果zxid是连续的，通过对比最后一个已提交的提案的zxid就能判断出是否有空洞，如果不是连续的，那么就无法判断了。
    1
  • zyz
    2021-02-06
    老师！“Zookeeper 提供的是最终一致性，也就是读操作可以在任何节点上执行，客户端会读到旧数据”，这句话是不是这样理解，根据zk的单一视图保证客户端不会连接到数据版本比自己之前看到的旧的服务器上。 如果这个客户端，指的是当前刚刚发起操作修改数据的客户端，断开连上还没有更新到最新事务的非领导者节点，非领导者节点会拒绝当前连接，因为客户端zxid事务Id，大于当前节点事务Id lastProcessedZxid，因此客户端需要连接其他节点。 如果这个客户端，指的是新客户端，不是刚才操作的客户端，连接上非领导者节点，看的的数据可能不是最新的。
    展开
    1
  • Bachue Zhou
    2021-01-27
    采用 udp 协议也可以保证消息的顺序性啊，只需要在上层再加一个保证消息顺序性的协议即可，比如 quic
    1
  • ezekiel
    2020-10-31
    老师您好 我有两个疑问 图 2、3、4中尚无提案准备，是Mutli-paxos中的步骤吗？我理解领导者直接进入第二阶段赋值，是否正确？ 图2中接受者已经赋值，后来领导者C执行Basic Paxos中准备阶段，将其修改。不是一旦赋值后就不能修改了吗？
    展开

    作者回复: 加一颗星:)，1. 准备阶段是可以省略的，属于优化，但是否省略，对最终结果都没有影响，为了理解方便，演示时，就没有省略。2. 不是赋值不能修改，而是算法保证被“大多数”节点接受的值就不再改变。

    1
  • piboye
    2020-09-17
    multipaxos假设就是不相关的吧，相关的数据，应该用paxos来决议log，这样就一致了。fast paxos也可以一次rpc一个提交，不过效率应该不如raft流模式。 zab比raft和paxos没有优势了吧？

    作者回复: 加一颗星:)，ZAB比paxos实现（chubby）新，比Raft旧，相比Raft，ZAB没有优势，究其原因，技术是不断继承，和发展的。

    2
  • Gavin
    2020-08-07
    在创建完提案之后，主节点会基于 TCP 协议，并按照顺序将提案广播到其他节点。这样就能保证先发送的消息，会先被收到，保证了消息接收的顺序性。 请问下，tcp协议有可能先发的消息后收到吧？

    作者回复: 加一颗星:)，不会的，TCP基于seq序号实现了TCP重组，能保证数据被严格按照顺序接收到。

    2
  • nomoshen
    2020-06-04
    第一个阶段提议ok之后，第二个committed阶段主节点挂了，那么在选举的时候这写未提交的提议咋处理？主节点反馈给客户端是否要直到comitted绝大多数才算OK

    作者回复: 加一颗星:)，问题1：因为提案已复制到大多数节点上，领导者选举能保证新的领导者一定包含这个未提交的提案，并最终将它提交。 问题2：不一定是主节点，也不需要等到committed绝大多数，具体来说，当节点接收到COMMIT消息后，提交提案，如果是自己接收的写请求，那么这时返回成功响应给客户端。

    共 2 条评论
    2
  • i_chase
    2022-11-20 来自广东
    这里Multi paxos顺序性讲的是真的看不明白。。感觉保证顺序性的唯一办法就是让每个zxid提案顺序执行？