沧州推广建站,sedo这种多语言网站怎么建设,dedecms 网站地图 模板,施工合同简单通用版ZAB协议
Zookeeper并不是完全采用Paxos算法#xff0c;而是使用了一种称为Zookeeper Atomic Broadcast#xff08;ZAB#xff0c;Zookeeper原子消息广播协议#xff09;作为数据一致性的核心算法#xff0c;依据此算法来实现分布式数据一致性的解决。他是一种特别为Zooke…ZAB协议
Zookeeper并不是完全采用Paxos算法而是使用了一种称为Zookeeper Atomic BroadcastZABZookeeper原子消息广播协议作为数据一致性的核心算法依据此算法来实现分布式数据一致性的解决。他是一种特别为Zookeeper设计的奔溃可恢复的原子消息广播算法。ZAB协议的核心是定义了对应那些会改变Zookeeper服务器数据状态的师傅请求的处理方式 所有事务请求必须有一个全局唯一服务器来协调处理这样的服务器被称为leader服务器其他服务器成为follower服务器leader服务器负责讲一个客户端事务请求转换成一个事务Proposal提议并将改Proposal分发给集群中所有Follower服务器leader服务器等待所有Follower反馈等待超过半数Follower进行了正确反馈leader就会再次向所有Follower发出Commons消息要求将前一个Proposal进行提交
协议介绍
ZAB包括两种基本模式 奔溃恢复 当整个服务框架启动过程中或者leader节点出现网络故障或者崩溃退出与重启等异常情况时候ZAB协议会进入恢复模式进行选举产生新的Leader服务器当选出来Leader并且同步了半数以上的Follower节点状态状态同步就是数据同步后ZAB才退出恢复模式消息广播过半数Follower都与Leader同步完成后整个服务框架就可以进入消息广播模式了。但一台同样遵循ZAB协议的节点加入后此时已经有一个Leader节点新加入的服务会自觉进入恢复模式同步数据后加入广播流程Leader节点作用在于接受客户端事务请求后会生成对应的事务提案并发起一轮广播协议如果集群中其他节点先收到客户端事务请求他会转发给leader节点 关键字过半数节点
消息广播
ZAB协议的消息广播过程是使用的原子广播协议类似一个二阶段提交的过程上面一节提到过就如下图中所示 与二阶段提交不同的是ZAB的提交过程移除了中断逻辑也就是不存在应为单个节点没回应ACK而中断广播的情况所有Follower要么正常反馈要么抛弃leader服务器并且只需要过半数的Follower服务器访客ACK后就开始提交事务Proposal而不需要所有。这种情况有弊端无法处理leader崩溃带来的数据不一致问题恢复模式解决此问题并且整个消息广播协议是有FIFO特性的TCP协议来进行网络通信能保证消息发送的顺序
顺序性保证
因为只有Leader服务器负责生产对应Proposal来进行广播并且广播之前leader会为每一个Proposal分配一个全局唯一递增事务ID即ZXID。由此递增ID就可以保证我们每一个Proposal严格按照ZXID顺序来进行处理发送即可处理好了leader发送顺序Follower如何保证接受到顺序广播过程Leader会为每一个Follower分配一个单独队列依次将Proposal放入队列并且依据ZXID顺序FIFO策略进行消息发送每个Follower接受到事务Proposal会以事务日志形式写入本地磁盘成功写入后反馈给Leader服务器一个Ack响应。Leader收到超半数ACK后广播一个Commit消息给所有Follower服务器以通知进行事务提交同事Leader自己也完成Commit。
奔溃恢复
Leader节点奔溃后需要触发选举选出新Leader并让所有节点能够快速的感知到新的Leader服务器是哪个
基本特性 崩溃恢复可能出现两种数据不一致的隐患 针对这两种情况ZAB需要保证的特性 情况一 ZAB协议需要确保已经在Leader服务器上提交的服务最终被所有服务器都提交 事务在Leader服务器上被提交了并且已经得到过半Follower服务器的ACK反馈但在Commit消息发送给所有Follower机器之前Leader服务器挂了如下图 上图leader是Server1已经广播消息P1,P2,C1,P3和C2当leader将C2C2 是Commit of proposal2的缩写发出后崩溃此时ZAB协议需要保证Proposal2最终能在所有服务器上被提交 情况二ZAB需要确保丢弃那些只在Leader服务器上被提出的事务。 与之前相反的情况奔溃恢复过程中出现一个需要被丢弃的案例那么恢复后需要跳过次事务 上图Leader服务器Server1 提出一个事务Proposal3后就奔溃其他follower都没有收到这个事务当Server1恢复再次加入集群ZAB需要确保丢弃这个Proposal3
Leader选举
根据以上两种情况确保提交已经被Leader提交的事务Proposal同时丢弃被跳过的事情需要ZAB必须有这样的Leader选举算法 保证选举出来的Leader服务器拥有集群中所有机器最高编号最大ZXID事务Proposal那么可以把这这个新选举出来的Leader一定具有所有已经提交的案例并且可以省去服务器检查proposal的提交和丢弃工作的这部操作所有事务按最高ZXID节点拥有的数据为准。
数据同步
Leader选举后Leader服务器为每一个Follower服务器准备一个队列将那些没有被Follower服务器同步的事务以Proposal消息的方法逐个发给Follower服务器并且在每个Proposal消息后紧接着发一个Commit消息标识已经提交。等同步完成所有消息并且将数据应用到本地数据库中后leader会将Follower服务器加入到真正的可用Follower列表并且开始之后的流程。
丢弃数据
如何处理需要被丢弃的ProposalZAB协议变化ZXID设计上解决这个问题ZXID是一个64位的数据低32位是一个单调递增的计数器针对每个事物请求计数器1操作高位32位代表Leader周期epoch的编号每单选举产生一个新的Leader服务器就会从Leader服务器上去除其本地日志中最大事物Proposal的ZXID 并从该ZXID中解析出上一次的epoch值然后在这个基础上1就用此编号作为新的epoch就相当于每一个Leader都递增1 的一个策略。ZAB协议通过epoch编号来区分Leader周期变化策略能有效避免不同Leader服务器错误使用相同ZXID变化踢出不一样事务Proposal的异常情况对于识别崩溃后在恢复之后生成的Proposal非常有帮助。
结论
基于上面的策略当一个包含上一个Leader周期中没提交的事务Proposal的服务器复活的时候肯定无法成为Leader因为当前集群中包含一个Quorum集合该集合中一定包含了更高epoch的事务Proposal因此当前复活的节点事务Proposal肯定是旧的无法成为Leader当加入集群后只能以Follow角色链接Leader服务器接着Leader会根据自己服务器上最后被提交的Proposal来和Follower的Proposal对比接着会按当前Leader的匹配要求同步当前Leader的数据也就相当于回退到一个确实已经被集群中过半集群提交的最新事务Proposal。
深入ZAB协议
上面部分介绍类ZAb协议大体内容以及实际运行中消息官博和奔溃恢复这两个基本模式。以下从系统模型问题描述算法描述运行分析深入理解ZAB协议
系统模型
分布式系统模型中我门将每个server看作是一个进程p那么可以用集合∏{P1,P2,…,Pn}来表示分布式系统每个进程都具有格子的存储设备就好比缓存隔离个进程直接互相通信来实现消息传递。每个进程都肯奔溃或重启奔溃我们称为down踢出集合∏恢复存活状态我们称为up重新加入∏只要∏ 集合中有超过半数的是up状态就可以进行消息广播我们将这样一个自集合称为Quorum上文提到过之后用Q表示并假设Q已经存在满足以下
//存在任意Q Q是 ∏ 的子集
∧ ∀QQ ⊆ ∏
//存在任意时候的Q1 Q2他们的交集不等于空集合此处的意义在于Q1或Q2 任意一个都超过半数应此不管如何去交集都能得到一个子集合极端情况是正好半数多一个元素的情况
∧ ∀Q1和Q2 Q1∩Q2≠∅完整性
进程P_j如果收到来自进程P_i的消息m那么p_i一定发送来消息m
前置性
进程P_j收到来消息m那么存在这样的消息m’如果消息m’ 是消息m的前置那么P_j务必先收到m’这种关系表示m’ m
问题描述
Zookeeper需要解决一系列诸如可靠配置存储运行时状态记录等分布式协调服务因此必须具备高吞吐量低延迟特性能很好的在高并发下完成分布式数据一致性处理同时能优雅处理运行时故障快速恢复ZAB核心是只有一个主进程如果主进程挂了就重选主进程选举与消息广播密切相关。随着时间推移可能出现无限多个主进程并构成一个主进程序列P_1P_2P_3…P_e-1,P_e其中P_e ⊆ ∏ ,e表示主进程序列好吗我们这里称他为主进程周期。对于以上序列中任意一个如果存在e e’那么我们就说P_e 是P_e’ 之前的主进程使用 P_e P_e’ ,他门是同一个进程只不过是不同周期而已
主进程周期
用以上 P_e P_e’ 的案例来解释就比如进程P_e周期中主节点是L_e此时主节点L_e 挂掉了重新选出L_e’e’e1就得到了P_e’其实是同一个进程只是表示他在不同的Leader周期下而已我们表示为e e’
事物
几个概念我们假设各个进程中有一个transactions(v,z)这样的函数用来实现主进程堆状态变更的广播其中参数v事物内容z事物表示而每一个事物表示ze,c,e表示进程周期c表示周期内事物技术也就是我们上文中提到的epoch(z)表示事物标识中的主进程周期epochcounter(z)表示事务计数器每个新事务c都递增实际运行中事务z 优与事务 z’ 有两种情况 epoch(z) epoch(z’) z是上一个主进程周期中的事务z’是重新选举后的事务epoch(z) epoch(z’) 且 counter(z) counter(z’) 同一个主进程周期但是z’事务序列号更大
算法描述
ZAB协议注意包括消息广播和崩溃恢复进一步可以分三个阶段发现Discovery同步Synchronization广播Broadcast先定义如下专用标识和属于
术语名说明F.pFollower f处理过的最后一个事务ProposalF.zxidFollower f处理过的历史事务Proposal中最后一个Proposal的事务表示ZXIDh_f每一个Follower f通常都已经处理接受了不少事务Proposal并且会有一个针对已经处理过的事务的集合将其表示为Hf表示Follower f已经处理过的事务的序列I_e初始化历史记录在某个主进程周期epoch中当准Leader完成阶段一之后此时他的h_f就被标记为I_e
阶段一发现 主要是Leader选举过程用于分布式进程中选举主进程准Leader L和Follower F工作流程姑且认为Leader L是随机出来的 步骤F.1.1 Follower F将自己最后接受的事务Proposal的epoch值CEPOCH(F.p)发送给准Leader L步骤L.1.1 当接受来自过半的Follower的Cepoch(F.p)消息后准Leader L会生成NEWEPOCH(e’)这个epoch的值e’ 是Leader L从CEPOCH(F.p)消息中选取的最大epoch然后对其1得到e’(就是获取最大一个ZXID的值从中得到epoch然后在1)步骤F1.2 当Follower 接受到来自准Leader L的NEWEPOCH(e’)消息后如果其检测到当前CEPOCH(F.p)小于e’那么就将CEPOCH(F.p)e’同时向这个准Leader L反馈Ack消息。这个反馈消息ACK-E(F.p, h_f),包含当前该Follower的epoch(F.p)也就是最后一个事务的信息以及该Follower的历史事务Proposal列表h_f 当Leader L接受到来自过半Follower的确认消息Ack后Leader L就会从这过半服务器中选取出一个Follower F使用他的I_e最为初始化事务结婚I_e’ 关于这个Follower F的选取对于Quorum中其他任意一个Follower F’ F需要满足以下两个条件中的一个
//任意Follower F的epoch主节点周期值小于 Follower F主节点周期值主节点周期值也就是Leader节点序列号每次选举1这个
CEPOCH(F.p) CEPOCH(F.p)
//如果两节点Follower F与Follower F的epoch值相同也就是在同一个主节点周期那么我们比较Follower F处理的最后一个事务的ZXID要小于 选出来的Follower F处理的最后一个事务的ZXID也就是我们选出来的必然是up集合中拥有最大ZXID事务的Follower节点或者两个都相同则都可以是Leader列表的备选
(CEPOCH(F.p) CEPOCH(F.p)) ( F.zxid F.zxid 或 F.zxid F.zxid)阶段二同步
发现流程后进入同步节点此时Leader L与Follower F流程如下 L.2.1 Leader 会将e’和I_e’以NEWLEADER(e’, I_e’)消息的形式发送给Quorum中的Follower将新的epoch主节点序列号和 最全的事务列表同步步骤F.2.1 当Follower接受到来自Leader L的NEWLEADER(e’, I_e’)消息后如果Follower发现CEPOCH(F.p)≠ e’那么直接跳过进入下一轮循环因为此时Follower 发现自己还在上一轮或者更上一个的同步中因为需要在发现阶段就已经将epoch修改为e’他可能还在发现阶段属于另外一半还没收到Leader L的NEWEPOCH(e’)消息的节点如果CEPOCH(F.p) e’ ,那么Follower会执行事务应用操作具体的对每一个事务Proposal:v, z ⊆ I_e’ Follower都会接受e’, v, z。最后Follower会反馈给Leader表示字节已经接受并处理来所有I_e’中的事务此处的意思是Leader L节点将最新的一份Proposal列表的信息以及最新的epoch数据发送给每一个Follower节点让他去同步修改如果Follower中的Proposal是在其中那么我就将之前Proposal里面的epoch值也就是e修改为新的epoch值也就是e’步骤L.2.2 当Leader 接受到来自过半Follower 针对NEWWLEADER(e’, I_e’)的反馈消息后就会向所有Follower发送消息Commit至此Leader 完成阶段二步骤F.2.2 当Follower收到来自Leader的Commit后就会一次处理并提交所有在I_e’中为未理的事务至此Follower完成阶段二
阶段三广播
完成同步后ZAB开始正式工作接受客户端新事务请求进行广播流程步骤L.3.1 Leader L接受到客户端新的事务请求会生成对应的事务Proposal并且根据ZXID顺序向Follower发送提案e’, v, z其中epoch(z) e’z就是ZXID64位低32 是Proposal事务序列号高32位是Leader周期的epoch序列号步骤F.3.1 Follower根据消息接收先后顺序处理来自Leader事务的Proposal并将他们追加到h_f中去之后在反馈给Leader步骤L.3.1 当Leader接收到来自过半Follower针对事务Proposale’, v, z的Ack消息后就发送Commite’, v, z消息给所有Follower要求他们进行事务的提交步骤F.3.2 当Follow F接受到来自Leader的Commite’, v, z 就会开始提交Proposale’, v, z需要主要此时该Follower F必定已经提交来事务Proposalv’, z’ 其中v’, z’ ⊆ h_f, z’ z
总结
如下图是以上三个流程总结各个消息说明如下
CEPOCHFollower进程向准Leader发送字节处理过的最后一个事务Proposal的epoch值NEWEPOCH准Leader根据接受到的各进程的epoch生成新一轮的周期epoch值ACK-EFollower进程反馈Leader进程发来的NEWEPOCH消息NEWLEADER 准Leader进程确认字节领导地位并发生NEWLEADER消息给各个进程ACK-LDFollower进程反馈Leader进程发来的NEWLEADER消息COMMIT-LD要求Follower进程提交相应的历史事务ProposalPROPOSELeader进程生成一个针对客户端事务请求的ProposalACKFollower进程反馈Leader进程发来的PROPOSAL消息COMMITLeader发送COMMIT消息要求所有进程提交事务PROPOSE
上一篇Zookeeper–简介 下一篇Zookeeper–ZAB与Paxos算法联系与区别
