如何建设手机网站首页,平面设计包括哪些软件,房产网站建设什么类型,郑州制作网站文章目录 什么是ZAB 算法#xff1f;深入ZAB算法1. 消息广播两阶段提交ZAB消息广播过程 2. 崩溃恢复选举参数选举流程 ZAB算法需要解决的两大问题1. 已经被处理的消息不能丢2. 被丢弃的消息不能再次出现 最近需要设计一个分布式系统#xff0c;需要一个中间件来存储共享的信息… 文章目录 什么是ZAB 算法深入ZAB算法1. 消息广播两阶段提交ZAB消息广播过程 2. 崩溃恢复选举参数选举流程 ZAB算法需要解决的两大问题1. 已经被处理的消息不能丢2. 被丢弃的消息不能再次出现 最近需要设计一个分布式系统需要一个中间件来存储共享的信息来保证多个系统之间的数据一致性调研了两个主流框架Zookeeper和ETCD发现都能满足我们的系统需求。 其中ETCD是K8s中采用的分布式存储而其底层采用了RAFT算法来保证一致性之前已经详细分析了Raft算法的原理今天主要仔细分析下Zookeeper的底层算法-ZAB算法。
什么是ZAB 算法
ZAB的全称是 Zookeeper Atomic Broadcast Zookeeper原子广播)。Zookeeper 是通过 Zab 算法来保证分布式事务的最终一致性。 Zab协议是为分布式协调服务Zookeeper专门设计的一种 支持崩溃恢复 的 原子广播协议 是Zookeeper保证数据一致性的核心算法。Zab借鉴了Paxos算法但又不像Paxos那样是一种通用的分布式一致性算法。它是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。 在Zookeeper中主要依赖Zab协议来实现数据一致性基于该协议zk实现了一种主备模型即Leader和Follower模型的系统架构来保证集群中各个副本之间数据的一致性。 这里的主备系统架构模型就是指只有一台客户端Leader负责处理外部的写事务请求然后Leader客户端将数据同步到其他Follower节点。
客户端的读取流程客户端会随机的链接到 zookeeper 集群中的一个节点如果是读请求就直接从当前节点中读取数据如果是写请求那么节点就会向 Leader 提交事务Leader 接收到事务提交会广播该事务只要超过半数节点写入成功该事务就会被提交。
深入ZAB算法
ZAB算法分为两大块内容消息广播和崩溃恢复。 消息广播boardcastZab 协议中所有的写请求都由 leader 来处理。正常工作状态下leader 接收请求并通过广播协议来处理。 崩溃恢复recovery当服务初次启动或者 leader 节点挂了系统就会进入恢复模式直到选出了有合法数量 follower 的新 leader然后新 leader 负责将整个系统同步到最新状态。
1. 消息广播
消息广播的过程实际上是一个简化的两阶段提交过程这里对两阶段提交做一个简单的介绍。
两阶段提交
两阶段提交算法本身是一致强一致性算法适合用作数据库的分布式事务其实数据库的经常用到的TCC本身就是一种2PC。
下面以MySQL中对数据库的修改过程来介绍下两阶段提交的具体流程在MySQL中对一条数据的修改操作首先写undo日志记录的数据原来的样子接下来执行事务修改操作把数据写到redo日志里面万一捅娄子事务失败了可从undo里面恢复数据。数据库通过undo与redo能保证数据的强一致性。 首先第一阶段叫准备节点事务的请求都发送给一个个的资源这里的资源可以是数据库也可以是其他支持事务的框架他们会分别执行自己的事务写日志到undo与redo但是不提交事务。 当事务管理器收到了所以资源的反馈事务都执行没报错后事务管理器再发送commit指令让资源把事务提交一旦发现任何一个资源在准备阶段没有执行成功事务管理器会发送rollback让所有的资源都回滚。这就是2pc非常简单。
说他是强一致性的是他需要保证任何一个资源都成功整个分布式事务才成功。
优点原理简单实现方便 缺点同步阻塞单点问题数据不一致容错性不好
同步阻塞在二阶段提交的过程中所有的节点都在等待其他节点的响应无法进行其他操作。这种同步阻塞极大的限制了分布式系统的性能。单点问题协调者在整个二阶段提交过程中很重要如果协调者在提交阶段出现问题那么整个流程将无法运转。更重要的是其他参与者将会处于一直锁定事务资源的状态中而无法继续完成事务操作。数据不一致假设当协调者向所有的参与者发送commit请求之后发生了局部网络异常或者是协调者在尚未发送完所有 commit请求之前自身发生了崩溃导致最终只有部分参与者收到了commit请求。这将导致严重的数据不一致问题。容错性不好二阶段提交协议没有设计较为完善的容错机制任意一个节点是失败都会导致整个事务的失败。
ZAB消息广播过程
Zookeeper集群中存在以下三种角色的节点 LeaderZookeeper集群的核心角色在集群启动或崩溃恢复中通过Follower参与选举产生为客户端提供读写服务并对事务请求进行处理。 FollowerZookeeper集群的核心角色在集群启动或崩溃恢复中参加选举没有被选上就是这个角色为客户端提供读取服务也就是处理非事务请求Follower不能处理事务请求对于收到的事务请求会转发给Leader。 Observer观察者角色不参加选举为客户端提供读取服务处理非事务请求对于收到的事务请求会转发给Leader。使用Observer的目的是为了扩展系统提高读取性能。 Leader 接收到消息请求后将消息赋予一个全局唯一的 64 位自增 id叫做zxid通过 zxid 的大小比较即可实现因果有序这一特性。 Leader 通过先进先出队列通过 TCP 协议来实现以此实现了全局有序这一特性将带有 zxid 的消息作为一个提案proposal分发给所有 follower。 当 follower 接收到 proposal先将 proposal 写到硬盘写硬盘成功后再向 leader 回一个 ACK。 当 leader 接收到合法数量的 ACKs 后leader 就向所有 follower 发送 COMMIT 命令同时会在本地执行该消息。 当 follower 收到消息的 COMMIT 命令时就会执行该消息。
相比于完整的二阶段提交Zab 协议最大的区别就是不能终止事务follower 要么回 ACK 给 leader要么抛弃 leader在某一时刻leader 的状态与 follower 的状态很可能不一致因此它不能处理 leader 挂掉的情况所以 Zab 协议引入了恢复模式来处理这一问题。 从另一角度看正因为 Zab 的广播过程不需要终止事务也就是说不需要所有 follower 都返回 ACK 才能进行 COMMIT而是只需要合法数量2n1 台服务器中的 n1 台 的follower也提升了整体的性能。 Leader 服务器与每一个 Follower 服务器之间都维护了一个单独的 FIFO 消息队列进行收发消息使用队列消息可以做到异步解耦。 Leader 和 Follower 之间只需要往队列中发消息即可。如果使用同步的方式会引起阻塞性能要下降很多。 2. 崩溃恢复
崩溃恢复的主要任务就是选举LeaderLeader ElectionLeader选举分两个场景
Zookeeper服务器启动时Leader选举。Zookeeper集群运行过程中Leader崩溃后的Leader选举。
选举参数
在介绍选举流程之前需要介绍几个参数
myid: 服务器ID这个是在安装Zookeeper时配置的myid越大该服务器在选举中被选为Leader的优先级会越大。ZAB算法中通过myid来规避了多个节点可能有相同zxid问题注意可以对比之前的Raft算法Raft算法中通过随机的timeout来规避多个节点可能同时成为Leader的问题。zxid: 事务ID这个是由Zookeeper集群中的Leader节点进行Proposal时生成的全局唯一的事务ID由于只有Leader才能进行Proposal所以这个zxid很容易做到全局唯一且自增。因为Follower没有生成zxid的权限。zxid越大表示当前节点上提交成功了最新的事务这也是为什么在崩溃恢复的时候需要优先考虑zxid的原因。epoch: 投票轮次每完成一次Leader选举的投票当前Leader节点的epoch会增加一次。在没有Leader时本轮此的epoch会保持不变。
另外在选举的过程中每个节点的当前状态会在以下几种状态之中进行转变。
LOOKING: 竞选状态。FOLLOWING: 随从状态同步Leader 状态参与Leader选举的投票过程。OBSERVING: 观察状态同步Leader 状态不参与Leader选举的投票过程。LEADING: 领导者状态。
选举流程
选举的流程如下
每个Server会发出一个投票,第一次都是投自己。投票信息myidZXID收集来自各个服务器的投票处理投票并重新投票处理逻辑优先比较ZXID,然后比较myid统计投票只要超过半数的机器接收到同样的投票信息就可以确定leader改变服务器状态进入正常的消息广播流程。
ZAB算法需要解决的两大问题
1. 已经被处理的消息不能丢 这一情况会出现在以下场景当 leader 收到合法数量 follower 的 ACKs 后就向各个 follower 广播 COMMIT 命令同时也会在本地执行 COMMIT 并向连接的客户端返回「成功」。但是如果在各个 follower 在收到 COMMIT 命令前 leader 就挂了导致剩下的服务器并没有执行都这条消息。 为了实现已经被处理的消息不能丢这个目的Zab 的恢复模式使用了以下的策略
选举拥有 proposal 最大值即 zxid 最大 的节点作为新的 leader由于所有提案被 COMMIT 之前必须有合法数量的 follower ACK即必须有合法数量的服务器的事务日志上有该提案的 proposal因此只要有合法数量的节点正常工作就必然有一个节点保存了所有被 COMMIT 的 proposal。 而在选举Leader的过程中会比较zxid因此选举出来的Leader必然会包含所有被COMMIT的proposal。新的 leader 将自己事务日志中 proposal 但未 COMMIT 的消息处理。 新的 leader 与 follower 建立先进先出的队列 先将自身有而 follower 没有的 proposal 发送给 follower再将这些 proposal 的 COMMIT 命令发送给 follower以保证所有的 follower 都保存了所有的 proposal、所有的 follower 都处理了所有的消息。
2. 被丢弃的消息不能再次出现 这一情况会出现在以下场景当 leader 接收到消息请求生成 proposal 后就挂了其他 follower 并没有收到此 proposal因此经过恢复模式重新选了 leader 后这条消息是被跳过的。 此时之前挂了的 leader 重新启动并注册成了 follower他保留了被跳过消息的 proposal 状态与整个系统的状态是不一致的需要将其删除。 Zab 通过巧妙的设计 zxid 来实现这一目的。一个 zxid 是64位高 32 是纪元epoch编号每经过一次 leader 选举产生一个新的 leader新 leader 会将 epoch 号 1。低 32 位是消息计数器每接收到一条消息这个值 1新 leader 选举后这个值重置为 0。这样设计的好处是旧的 leader 挂了后重启它不会被选举为 leader因为此时它的 zxid 肯定小于当前的新 leader。当旧的 leader 作为 follower 接入新的 leader 后新的 leader 会让它将所有的拥有旧的 epoch 号的未被 COMMIT 的 proposal 清除。
Zab 协议设计的优秀之处有两点一是简化二阶段提交提升了在正常工作情况下的性能二是巧妙地利用率自增序列简化了异常恢复的逻辑也很好地保证了顺序处理这一特性。
