Skip to content

Latest commit

 

History

History
executable file
·
607 lines (319 loc) · 30.8 KB

分布式一致性算法.md

File metadata and controls

executable file
·
607 lines (319 loc) · 30.8 KB

分布式系统

概念

分布式系统是一个硬件或软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统。

特点

  1. 分布性

    分布式系统中各个计算机空间上随意分布、时间上也会随时变动。

  2. 对等性

    分布式系统中的计算机没有主/从之分，组成分布式系统的所有计算机节点都是对等的。

    副本 Replica，指的是分布式系统对数据和服务提供的一种冗余方式，为了提高可用性，往往会对数据和服务做一定数量的副本。

  3. 并发性

    同一个分布式系统中的多个节点，可能会并发地操作一些共享资源，如数据库。

  4. 缺乏全局时钟

    在分布式系统中，很难定义两个事件究竟谁先谁后。

  5. 故障总是会发生

    组成分布式系统的所有计算机，都可能发生任何形式的故障。

问题

  1. 通信异常

    网络本身的不可靠性，如光纤、路由器、DNS等不可用都会导致分布式系统无法顺利完成一次网络通信 。

  2. 网络分区

    发生网络异常导致分布式系统中部分节点之间的网络延时不断增大，最终导致组成分布式系统的所有结点中只有部分节点之间能够正常通信，而另一些节点则不能，这种现象称为网络分区，俗称脑裂。

  3. 三态

    分布式系统中的每一次请求与响应，存在特有的三态概念，即成功、失败、超时。由于网络原因，请求消息并没有成功的发送到接收方、或者请求消息成功被接受并处理后响应消息没有成功的反馈给发送方，发送方是无法确定当前消息是否被成功处理的。

  4. 节点故障

    组成分布式系统的服务器节点出现宕机或僵死的现象。

ACID

数据库事务的ACID特性

  1. Atomiciy 原子性

  2. Consistency 一致性

  3. Isolation 隔离性

    Read Uncommitted

    Read Committed

    Repeatable Read

    Serializable

  4. Durability 持久性

分布式事务

CAP定理

  1. C Consistency 一致性

    在分布式环境中，一致性是指数据在多个副本之间能够保持一致的特性。在满足一致性的系统中，应该能够保证数据从一个一致的状态更新到另一个一致的状态。

  2. A Availability 可用性

    是指系统提供的服务必须一直处于可用的状态，对于用户的每个操作总是能够在有限的时间内返回结果。 有限的时间，对于用户的每一个操作，系统必须能够在指定的时间（响应时间）内返回对应的处理结果，如果超过了这个时间，则认为系统是不可用的。 返回结果 要求在完成对用户的请求的处理后，返回一个正常的响应结果。

  3. P Partition tolerance 分区容错性

    分布式系统在遇到任何网络分区故障时，仍需要能够保证对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。 网络分区 是指在分布式系统中不同的节点分布在不同的子网络中，由于一些特殊原因导致这些子网络出现网络不连通的状况，但各个子网络内部网络时正常的，从而导致整个系统的网络环境被切分成了若干个孤立的区域

一个分布式系统无法同时满足C、A、P三个需求，而只能满足其中的两个，因此在对CAP定了进行应用时，需要抛弃其中的一项。

因为分布式系统中，各个组件必然被部署到不同的节点，也就必然会出现子网络，所以，分区容错性是一个分布式系统最基本的要求。

BASE理论

  1. B Basically Available 基本可用

    分布式系统在出现不可预知的故障时，运行损失部分可用性。 比如 响应时间上的损失 允许响应时间增加 功能上的损失 做功能降级等

  2. Soft state 软状态

    或者弱状态，是指允许系统中的数据存在中间状态，并且该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

  3. Eventually consistent 最终一致性

    强调在系统中的所有数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态，即保证最终数据能够达到一致、而不是实时保证系统的强一致性。

    1. 因果一致性

      如果进程A的更新操作发生在进程B对数据的操作之前，即A先于B发生，那么进程B对该数据的访问总是能获取到进程A更新后的值，并且进程B对该数据的更新操作也必须基于进程A更新后的值，即不能发生丢失更新的情况。而与进程A没有因果关系的进程C则不受此限制。

    2. 读己之所写

      进程A更新一个数据后，它总是能够访问到其更新过的最新值，而不会看到旧值。

    3. 会话一致性

      系统能够保证在同一个有效的会话中实现读己之所写，也就是客户端在同一个会话中始终能够读取到该会话更新后的最新值

    4. 单调读一致性

      进程从系统中读取一个数据的值后，该进程后续对该数据的访问不应该返回更旧的值

    5. 单调写一致性

      系统需要保证来自同一个进程的写操作被顺序执行

一致性协议

2PC

Two-Phase Commit，即二阶段提交，是计算机网络尤其是数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务处理过程中能够保持原子性和一致性而设计的一种算法。

是一种一致性协议，用来保证分布式系统数据的一致性。

绝大多数关系型数据库都采用2PC来完成分布式事务处理。

两个阶段

  1. 阶段一：提交事务请求

    1. 事务询问

      协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各个参与者的响应

    2. 执行事务

      各个参与者节点执行事务操作，并将Undo和Redo信息计入事务日志中。

    3. 各个参与者向协调者反馈事务询问的响应

      如果参与者成功执行了事务操作，反馈Yes给协调者，表示事务可以执行；

      如果参与者没有成功执行事务操作，反馈No给协调者，表示事务不可以执行。

    以上过程类似协调者组织各个参与者对一次事务操作的投票表态过程，因此，这一阶段也被称为投票阶段。

  2. 阶段二：执行事务提交

    在这一阶段，协调者根据各个参与者的反馈来决定最终是否可以执行事务提交操作，正常情况下有两种可能：执行事务提交或者中断事务

    • 执行事务提交

      假如协调者从所有参与者获得的反馈都是Yes，那么执行事务提交

      1. 发送提交请求

        协调者向所有参与者阶段发送Commit请求

      2. 提交事务

        参与者收到Commit请求，正式执行事务提交操作，并在完成提交后释放在整个事务执行期间占用的事务资源

      3. 反馈事务提交结果

        参与者在完成事务提交之后，向协调者发送Ack消息

      4. 完成事务

        协调者收到所有参与者反馈的Ack消息后，完成事务

    • 中断事务

      假如任何一个参与者向协调者反馈了No响应，或者在等待超时后协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务。

      1. 发送回滚请求

        协调者向所有参与者节点发送Rollback请求

      2. 事务回滚

        参与者收到Rollback请求后，利用其在阶段一记录的Undo信息来执行事务回滚操作，并在完成回滚后释放在整个事务执行期间占用的资源

      3. 反馈事务回滚结果

        参与者完成事务回滚后，向协调者发送Ack消息

      4. 中断事务

        协调者接收到所有参与者反馈的Ack消息后，完成事务中断

优缺点

  1. 优点

    原理简单、实现方便

  2. 缺点

    1. 同步阻塞

      所有参与该事务操作的逻辑都是阻塞的

    2. 单点问题

      一旦协调者出现问题，这个2PC提交流程将无法运转。

      更甚，如果协调者在阶段二中出现问题，那么参与者将会一直处于锁定事务资源的状态。

    3. 数据不一致

      在阶段二，由于网络或其它原因导致只有部分参与者收到了Commit请求并执行了事务提交操作，而其它参与者因没有接收到Commit请求而无法执行事务提交操作，于是整个系统便出现了数据不一致的现象

    4. 太过保守

      没有完善的容错机制。假如在阶段二，由于网络或其它原因，协调者始终无法接收到参与者的反馈，那么协调者只能通过自身的超时机制来判断事务是否需要中断。

3PC

Three-Phase Commit，即三阶段提交，将2PC的阶段一分为两步，形成了由CanCommit、PreCommit、DoCommit三个阶段组成的事务处理协议

  1. 阶段一：CanCommit

    1. 事务询问

      协调者向所有参与者发送一个包含事务内容的canCommit请求，询问是否可以执行事务提交操作，并开始等待各参与者的响应

    2. 个参与者向协调者反馈事务询问的响应

      参与者在接受到canCommit请求后，正常情况下，如果其自身认为可以顺利执行事务，那么会反馈Yes响应，否则反馈No响应

  2. 阶段二：PreCommit

    在这一阶段，协调者会根据各参与者的反馈来决定是否可以进行事务的PreCommit操作，正常情况下由两种可能：执行事务预提交或者中断事务

    • 执行事务预提交

      假如协调者从所有参与者获得反馈都是Yes响应，那么执行事务预提交

      1. 发送预提交请求

        协调者向所有参与者节点发送preCommit请求，并进入Prepared阶段

      2. 事务预提交

        参与者接收到preCommit请求后，会执行事务操作，并将Undo和Redo信息记录到事务日志

      3. 各参与者向协调者反馈事务执行的响应

        如果参与者成功执行了事务操作，那么会反馈个协调者Ack响应，同时等待最终指令：提交commit或者终止abort（如果之后协调者除了问题或者协调者与参与者之间网络出现问题，导致该参与者等待超时后仍无法接收到commit或者abort指令，该参与者仍然会执行事务提交）

    • 中断事务

      假如任何一个参与者向协调者反馈了No响应，或则在等待超时后协调者尚无法接收到所有参与这的反馈响应，那么就会中断事务

      1. 发送中断请求

        协调者向所欲参与者节点发送abort请求

      2. 中断事务

        无论是收到来自协调者的abort请求，或者是等待协调者请求过程中出现超时，参与者都会中断事务

  3. 阶段三：DoCommit

    该阶段将进行真正的事务提交，会存在以下两种可能的情况：执行提交或者中断事务

    • 执行提交

      1. 发送提交请求

        假设协调者处于正常工作状态，并且它接收到了来自所有参与者的Ack响应，那么它将从预提交状态转换到提交状态，并向所有的参与者发送doCommit请求

      2. 事务提交

        参与者收到doCommit请求后，会正式实现事务提交操作，并在完成后释放事务资源

      3. 反馈事务提交结果

        参与者在完成事务提交后，向协调者发送Ack消息

      4. 完成事务

        协调者接收到所有参与者反馈的Ack消息，完成事务

    • 中断事务

      假如协调者处于正常工作状态，并且由任意一个参与者向协调者反馈了No响应，或者在等待超时后协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务

      1. 发送中断请求

        协调者向所有参与者节点发送abort请求

      2. 事务回滚

        参与者接收到abort请求后，利用其记录的Undo日志来执行事务回滚，完成收释放事务资源

      3. 反馈事务回滚结果

        参与者完成事务回滚后，向协调者发送Ack消息

      4. 协调者接收到所有参与者反馈的Ack消息后，中断事务

    阶段三可能会出现两种故障

    1. 协调者出现问题
    2. 协调者与参与者之间出现问题

    无论哪种情况，最终都会导致参与者无法及时接收到来自协调者的doCommit或者是abort请求，针对这一的情况，参与者都会在等待超时后继续进行事务提交

优缺点

优点：

  1. 降低阻塞范围
  2. 出现单点故障后继续达成一致

缺点：

Paxos算法

三种角色 Proposer（提议者）、Acceptor（接收者）、Learner（学习者）

  1. 提案的选定

    Proposer向一个Acceptor集合发送提案，同样，集合中的每个Acceptor都可能会批准（Accept）该提案，当有足够多的Acceptor批准该提案的时候，我们就可以认为该提案被选定了。

    • 假设足够多的Acceptor是整个Acceptor集合的一个包含大多数成员的子集；再假设每个Acceptor最多只能批准一个提案。那么就能保证只有一个提案被选定。

    • 一个Acceptor必须批准它接收到的第一个提案；一个Acceptor必须能够批准不止一个提案；

    • 如果提案[M,V]被选定了，那么所有编号比M更高且被选定的提案其值必须为V;

    • 如果提案[M,V]被选定了，那么所有编号比M更高且被Acceptor批准的提案其值必须为V;

    • 如果提案[M,V]被选定了，那么之后任何Proposer产生的编号更高的提案其值必须为V；

    • 对于任意M、V，如果提案[M,V]被提出，那么肯定存在一个由半数以上的Acceptor组成的集合S满足以下两个条件

      • S中不存在任何批准过编号小于M的提案的Acceptor
      • 选取S中所有Acceptor批准过的小于M的提案，其中编号最大的那个提案其值是V

  2. Proposer生成提案

    对于一个Proposer来说，获取那些已被通过的提案比预测未来可能会被通过的提案简单。 因此，Proposer在产生一个编号为M的提案时，必须要知道当前某一个将要或者已经被半数以上Acceptor批准的编号小于M的最大编号的提案。并且，Proposer会要求所有的Acceptor都不要在批准任何编号小于M的提案，这就引出了如下的提案生成算法：

    1. Proposer选择一个新的提案编号为M，然后向某个Acceptor集合的成员发送请求，要求该集合中的Acceptor做出如下回应.

      • 向Proposer承诺，保证不再批准任何编号小于M的提案
      • 如果Acceptor已经批准过任何提案，那么其就向Proposer反馈当前该Acceptor已批准的编号小于M的最大编号的那个提案的值

    将该请求称为编号为M的提案的Prepare请求

    1. 如果Proposer收到了来自半数以上的Acceptor的响应结果，那么它就可以产生编号为M、Value值为V的提案，这里V是所有响应中编号最大的提案的Value值。如果半数以上的Acceptor都没有批准过任何提案，即响应中不包含任何提案，那么此时的V值可以由Proposer任意选择

    在确定提案后，Proposer就会将该提案再次发送个某个Acceptor集合，并期望获得它们的批准，我们称此请求为Accept请求。此时接收Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合。

  3. Acceptor批准提案

    Acceptor会接收到来自Proposer的两种请求

    • Prepare请求 Acceptor可以在任何时候响应一个Prepare请求
    • Accept请求 在不违背Accept现有承诺的前提下，可以任意响应Accept请求

    因此，对Acceptor逻辑处理的约束条件大体如下： 一个Acceptor只要尚未响应过任何编号大于M的Prepare请求，那么它就可以接受这个编号为M的提案

  4. 算法优化

    1. Acceptor可以忽略掉那些编号小于它已响应过的Prepare请求

      假设一个Acceptor收到了一个编号为M的Prepare请求，但此时该Acceptor已经对编号大于M的Prepare请求做了响应，显然Acceptor没必要对这个编号为M的Prepare请求作出响应，Acceptor可以忽略这个请求。

    2. Acceptor可以忽略掉那些它已经批准过的提案的Prepare请求

    经过优化，对于每个Acceptor，它只需要记住它已经批准的提案的最大编号、已经响应的Prepare请求的最大编号；对于Proposer，只要它可以保证不会生成相同编号的提案，那么它就可以丢弃任意提案以及它所有的运行时信息

    Acceptor{
	X; //已经批准的提案的最大编号 // A忽略编号小于X的Prepare请求
	Y; //已经响应的Prepare请求的最大编号 // A忽略编号小于Y的Prepare请求
}

  5. 算法陈述

    1. 阶段一

      1. Proposer选择一个提案编号M，然后向Acceptor的某个超过半数的子集成员发送编号为M的Prepare请求

      2. 如果一个Acceptor收到一个编号为M的Prepare请求，且编号M大于该Acceptor已经响应的所有Prepare请求的编号，那么它就将它已批准过的最大编号的提案作为响应反馈给Proposer，同时该Acceptor承诺不会再批准任何编号小于M的提案

        比如一个Acceptor已经响应过的所有Prepare请求对应的提案编号为1、2、...、5、7，那么该Acceptor再接收到编号为8的Prepare请求后，会将编号为7的提案反馈给Proposer

    2. 阶段二

      1. 如果Proposer收到来自半数以上的Acceptor对于其发出的编号为M的Prepare请求的响应，那么它就会发送一个针对[M, V]提案Accept请求给Acceptor。V的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它就是任意值

      2. 如果Acceptor收到这个针对[M, V]提案Accept请求，只要该Acceptor尚未对编号大于M的Prepare请求做出响应，它就可以通过这个提案

  6. 提案的获取

    Acceptor可以将批准的提案发送给一个特定的Learner集合，该集合中的每个Learner都可以再一个提案被选定后通知所有其它的Learner。

  7. 选取主Proposer

    为了保证算法的活性，必须选择一个主Proposer，并且规定只有主Proposer才能提出议案。这样，只要主Proposer和超过半数的Acceptor能够正常进行通信，那么但凡主Proposer提出一个编号更高的提案，该提案终将会被批准；如果Proposer发现当前已经有一个编号更大的提案被提出或正在接收批准，那么它会丢弃当前这个编号较小的提案，最终能够选出一个编号足够大的提案。

Zookeeper

Zookeeper致力于提供一个高性能、高可用、严格顺序访问控制能力的分布式协调服务。

一致性

它可以保证如下分布式一致性：

  1. 顺序一致性

    从同一个客户端发起的事务请求，最终会严格地按照其发起顺序被应用到Zookeeper中

  2. 原子性

    所有事务请求的结果在整个集群中的所有机器上的应用情况是一致的

  3. 单一视图

    无论客户端连接的是那个Zookeeper服务器，其看到的服务端数据模型是一致的

  4. 可靠性

    一旦服务端成功应用了一个事务并完成对客户端的响应，那么该事务所引起的服务端状态变更将被一直保留下来，除非有另一个事务又对其进行了变更

  5. 实时性

    Zookeeper保证在一定的时间段内，客户端最终一定能够从服务端读取到最新的数据状态

设计目标

  1. 简单的数据模型

    它使得分布式程序能够通过一个共享的、树型结果的名字空间来进行相互协调

  2. 可以构建集群

    一般3～5台机器就可以组成一个可用的Zookeeper集群

  3. 顺序访问

    对于来自客户端的每一个更新请求，Zookeeper都会分配一个全局唯一的递增编号，这个编号反映了所有事务操作的先后顺序

  4. 高性能

    Zookeeper将全量数据存储在内存中，并直接服务于客户端的所有非事务请求

基本概念

  1. 集群角色

    集群中有三种角色

    1. Leader

      Leader服务器为客户端提供读、写服务

    2. Follower

      Follower服务器为客户端提供读服务，并且它参与Leader的选举过程

    3. Observer

      Follower服务器为客户端提供读服务，并且，它不参与Leader的选举过程，也不参与写操作的“过半写成功”策略

  2. 会话 session

    客户端会话，客户端启动时，首先会与服务器建立一个TCP长链接，客户端会话的生命周期也就开始了。

    通过这个连接，客户端能够使用心跳检测与服务器保持有效的会话，也能够向Zookeeper发送请求并接收响应，也可以通过该连接来接收来自服务器的Watch事件通知。

    session的sessionTimeout值用来设置客户端会话的超时时间。客户端只要在sessionTimeout时间内能够重新与集群中的任意服务器连接，这个会话就依然有效

  3. 数据结点 Znode

    Zookeeper的数据模型是一颗树，Znode Tree，由 / 分割的路径就是一个Znode，每个Znode上都会保存自己的数据内容和一些属性信息

    Znode结点分为两类：持久结点和临时结点。持久结点一旦创建，就会一直存在，除非主动删除；临时结点的生命周期和客户端会话绑定，一旦客户端会话失效，这个会话创建的所有临时结点都会被删除。

    Zookeeper还允许为每个结点添加一个SEQUENTIAL属性，Zookeeper会自动为有这个属性的结点名后面追加一个整形数字，这个整形数字是一个由其父结点维护的自增数字

  4. 版本

    对于每个Znode，Zookeeper都会为其维护一个叫做Stat的数据结构，Stat记录Znode的三个数据版本，分别为

    1. version 当前Znode的版本
    2. cversion 当前Znode字节点的版本
    3. aversion 当前Znode的ACL版本

  5. Watcher

    时间监听器，Zookeeper允许客户端在指定结点上注册一些Watcher，当指定事件发生时，Zookeeper会将事件通知到感兴趣的客户端上去

  6. ACL

    Access Control Lists，权限控制，Zookeeper定义了5种权限

    1. CREATE 创建子结点的权限
    2. READ 获取结点数据和子结点列表的权限
    3. WRITE 更新结点数据的权限
    4. DELETE 删除字节的权限
    5. ADMIN 设置结点ACL的权限

ZAB协议

即Zookeeper Atomic Broadcast，Zookeeper原子广播协议。

Zookeeper并没有完全使用Paxos算法，而是使用ZAB协议作为其数据一致性的核心算法。

ZAB协议是为Zookeeper专门设计的一种支持崩溃恢复的原子广播协议。

在Zookeeper中，主要依赖ZAB协议来实现分布式数据一致性，基于该协议，Zookeeper实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。

  • Zookeeper使用一个单一的主进程来接收并处理客户端的所有事务请求，并采用ZAB将服务器数据的状态已事务Proposal的形式广播到所有的副本进程上去。ZAB协议的这个主备模型架构保证了同一时刻集群中只能够有一个主进程来广播服务器的状态变更，因此能够更好的处理客户端大量的并发请求。

  • ZAB协议需要保证如果一个状态变更已经被处理了，那么所有其依赖的状态变更都应该在此之前被全部处理了。

  • 主进程在任何时候都有可能崩溃或重启，因此，ZAB协议还需要做到当前主进程崩溃和重启时依旧能够正常工作。

ZAB协议的核心定义了对于那些会改变Zookeeper服务器数据状态的事务请求的处理方式，即：

  1. 所有事务请求必须由一个全局唯一的服务器在协调处理，这样的服务器被称为Leader服务器，而余下的其它服务器被称为Follower服务器。

  2. Leader服务器负责将一个客户端事务请求转换为一个事务Proposal，并将该Proposal分发给集器中的所有Follower服务器。

    如果非Leader服务器接收到客户端的事务请求，那么这些非Leader服务器首先将这个事务请求转发给Leader服务器。

  3. Leader服务器等待所有Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，Leader服务器将再次向所有的Follower服务器分发Commit消息，同时，Leader也进行提交。Follower接收到Commit消息后，要将前一个Proposal进行提交。

两种基本模式：

  1. 崩溃恢复

    在整个集群服务启动过程中，或者Leader服务器出现网络中断、崩溃退出与重启等异常情况时，ZAB协议进入恢复模式并选举新的Leader服务器

    当选举产生了新的Leader服务器，同时集群中已有过半的机器与该Leader服务器完成了状态同步之后，ZAB协议退出崩溃恢复模式。

    在崩溃恢复，ZAB协议需要一个高效且可靠的Leader选举算法，从而确保能够快速的选举出新的Leader。同时，Leader选举算法不仅需要让Leader知道自身已经被选举为Leader，还需要让集群中所有其它服务器也能够快熟的感知到选举产生的新的Leader服务器。

    ZAB协议规定了如果一个事务Proposal在一台机器上被处理成功，那么它应该在所有机器上都被处理成功，哪怕机器出现故障崩溃。

    崩溃恢复过程中的两个数据不一致

    • ZAB协议需要确保那些已经在Leader服务器上提交的事务最终被所有服务器都提交

      假设一个事务在Leader服务器上被提交了，并且已经得到过半的Follower服务器的Ack反馈，但在它将Commit消息发送给所有的Follower服务器之前，Leader服务器崩溃了。这时，就出现了不一致。

    • ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务

      如果在崩溃恢复过程中出现一个需要被丢弃的提案，那么在崩溃恢复后需要跳过该事务Proposal。假设初始的Leader服务器S1在提出一个事务Proposal后就崩溃了，从而集群中的其它服务器都没有收到这个事务Proposal。于是，当S1恢复过来再次加入集群的时候，ZAB协议需要丢弃这个事务Proposal。

    所以ZAB协议必须设计这样一个Leader选举算法：能够确保提交已经被Leader提交的事务Proposal，同时丢弃已经被跳过的事务Proposal。

    • 如果新选出的Leader服务器拥有集群中所有机器ZXID最大的事务Proposal，就可以保证这个新选举出的Leader一定具有所有已提交的提案
    • 或者，如果让具有最大ZXID的机器成为Leader，就可以省去Leader服务器检查Proposal的提交和丢弃的工作了。

  2. 消息广播

    当集群中已有过半的Follower服务器完成了和Leader服务器的状态同步，整个集群服务就可以进入消息广播模式了。

    ZAB的消息广播过程是一种类似于二阶段提交的过程。

    针对客户端的事务请求，Leader服务器会为其生成对应的事务Proposal，并将其发送给集群中其余所有的机器，然后再分别收集各个服务器结点的反馈，最后进行事务提交。

    注意，此处的二阶段提交不同于2PC，它移除了中断逻辑，这就意味着：

    • 所有的Follower服务器要么正常反馈Leader提出的事务Proposal，要么就抛弃Leader服务器。
    • 同时，此处的二阶段提交可以在过半的Follower服务器反馈Ack之后就开始提交事务Proposal了，而不需要等待所有的Follower服务器都反馈响应。

    当然，这种简化了的二阶段提交无法处理Leader服务器崩溃退出而带来的数据不一致问题。因此，ZAB协议添加了崩溃恢复模式来解决这个问题。

    另外，消息广播基于具有FIFO特性的TCP协议进行网络通信，因此很容易保证消息广播过程中消息接收与发送的顺序性。

    在消息广播过程中，Leader 服务器会为每个事务请求生成对应的Proposal来进行广播，并且在广播事务Proposal之前，Leader 服务器会首先为这个事务Proposal分配一个全局单调递增的唯一ID，即ZXID，我们称之为事务ID。这样ZAB就可以按照这个ZXID的先后顺序来排序并处理每一个事务Proposal，从而保证了每一个消息的严格的因果关系。

    具体的，在消息广播过程中，Leader服务器会为每一个Follower 服务器都各自分配一个单独的队列，然后将需要广播的事务Proposal一次入队，并且根据FIFO的策略进行消息发送。每一个Follower 服务器在接收到这个事务Proposal后，都会首先将其以事务日志的形式写入到本地磁盘，并且在成功写入后反馈给Leader 服务器一个Ack响应。当Leader 服务器接收到过半Follower 服务器的Ack响应后，就会广播一个Commit消息给所有的Follower服务器以通知其进行事务提交，同时Leader 服务器自身也会完成事务的提交，而每一个Follower 服务器在收到Commit消息后也会完成对事务的提交。

  3. 数据恢复

    当一台通用遵循ZAB协议的服务器启动后加入集群时，如果此集群已经存在一个Leader服务器在负责消息广播，那么新加入的机器自动进入数据恢复模式：找到Leader服务器，并与其进行数据同步，然后一起参与到消息广播流程中去。

  4. 数据同步

    所有正常允许的服务器，要么成为Leader，要么成功Follower并和Leader保持同步。Leader 服务器需要确保所有的Follower服务器能够接收到每一条事务Proposal，并且能够正确的将所有已提交了的事务Proposal应用到内存数据库中去。

    • 正常情况下的数据同步

      Leader 服务器会为每一个Follower服务器准备一个队列，并将那么没有被各Follower服务器同步的事务Proposal以Proposal消息的形式逐个发送给Follower 服务器，并在每一个Proposal消息后面紧接着再发送一个Commit消息，以表示该事务已经被提交。等到Follower服务器将所有其尚未同步是事务Proposal都从Leader 服务器同步过来并成功应用到本地内存数据库后，Leader 服务器就会将该Follower 服务器加入到真正可用的Follower 列表中，并开始之后的其它流程。

    • 怎样处理需要被丢弃的事务Proposal

      ZAB的ZXID是一个64位的数字，其中，低32位可以看作是一个简单的单调递增的计数器，针对客户端的每一个事务请求，Leader 服务器在产生一个新的事务Proposal时候，都会对该计数器进行加1操作；而高32位则代表了Leader周期的epoch编号，妹子选举产生一个新的Leader 服务器，就会从这个Leader服务器上取出其本地日志中最大事务Proposal的ZXID，并从中解析出该ZXID对应的epoch，然后对其进行加1操作，之后就会以此位编号作为新的epoch，并将低32位置为0来开始新的ZXID。

      基于这个策略，当一个包含了上一个Leader周期中尚未提交过的事务Proposal的服务器启动时，其肯定无法成为Leader，因为该集群中肯定已经包含了更高Epoch的事务Proposal。那么这台机器会议Follower的角色加入到该集群，之后，Leader服务器根据自己服务器上最后提交的Proposal来和该Follower 服务器的Proposal进行对比，对比的结果是Leader要求Follower进行一个回退操作：回到到一个确实已经被集群中过半机器提交的最新的事务Proposal。