一、拜占庭将军问题

Zookeeper是如何保证数据一致性的?这也是困扰分布式系统框架的一个难题。

拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标:欺骗某些将军采取进攻行动，促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动;或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。

二、CAP理论

CAP理论告诉我们，一个分布式系统不可能同时满足以下三种

  • 一致性(C:Consistency)
  • 可用性(A:Available）
  • 分区容错性（P:Partition Tolerance )

这三个基本需求，最多只能同时满足其中的两项，因为P是必须的，因此往往选择就在CP或者AP中。

  1. 一致性(C:Consistency)：在分布式环境中，一致性是指数据在多个副本之间是否能够保持数据一致的特性。在一致性的需求下，当一个系统在数据一致的状态下执行更新操作后，应该保证系统的数据仍然处于一致的状态。
  2. 可用性(A:Available）：可用性是指系统提供的服务必须一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。
  3. 分区容错性（P:Partition Tolerance )：分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境都发生了故障。

ZooKeeper保证的是CP

  1. ZooKeeper不能保证每次服务请求的可用性。(注:在极端环境下，ZooKeeper可能会丢弃一些请求，消费者程序需要重新请求才能获得结果）。所以说，ZooKeeper不能保证服务可用性。
  2. 进行Leader选举时集群都是不可用。

三、2PC和3PC

当一个事务操作需要跨越多个分布式节点的时候，为了保持事务处理的ACID特性，就需要引入一个称为“协调者(Coordinator)”的组件来统一调度所有分布式节点的执行逻辑，这些被调度的分布式节点则被称为“参与者”(Participant)。协调者负责调度参与者的行为，并最终决定这些参与者是否要把事务真正进行提交。

2PC

二阶段提交。目前绝大多数关系型数据库采用二阶段提交完成分布式事务。将书屋分为2个阶段来进行处理。

阶段一：提交事务请求

  1. 事务询问
    协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应。
  2. 执行事务。
    各参与者节点执行事务操作，并将Undo和 Redo信息记入事务日志中。
  3. 各参与者向协调者反馈事务询问的响应。
    如果参与者成功执行了事务操作，那么就反馈给协调者Yes 响应，表示事务可以执行﹔如果参与者没有成功执行事务，那么就反馈给协调者No响应，表示事务不可以执行。

阶段一被称为“投票阶段”，各参与者投票表明是否要继续执行下去。

阶段二：执行事务提交

协调组根据参与者的反馈情况决定是否可以进行事务提交操作。

执行事务提交
  1. 发送提交请求
    协调者向所有参与者节点发出Commit 请求。
  2. 事务提交。
    参与者接收到Commit请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源。
  3. 反馈事务提交结果。
    参与者在完成事务提交之后，向协调者发送 Ack 消息。
  4. 完成事务。
    协调者接收到所有参与者反馈的Ack 消息后，完成事务。
中断事务

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

  1. 发送回滚请求。
    协调者向所有参与者节点发出Rollback 请求。
  2. 事务回滚。
    参与者接收到Rollback 请求后，会利用其在阶段一中记录的Undo信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。
  3. 反馈事务回滚结果。
    参与者在完成事务回滚之后，向协调者发送 Ack 消息。
  4. 中断事务。
    协调者接收到所有参与者反馈的Ack 消息后，完成事务中断。

二阶段提交核心是采用先尝试后提交的处理方式，二阶段提交是一个强一致性算法

优缺点

优点：简单，实现方便

缺点：同步阻塞、单点问题、脑裂、太过保守

  1. 同步阻塞
    最明显也是最大的一个问题就是同步阻塞,这会极大地限制分布式系统的性能。在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态。
  2. 单点问题
    协调者的角色在整个二阶段提交协议中起到了非常重要的作用。一旦协调者出现问题，那么整个二阶段提交流程将无法运转，更为严重的是，如果协调者是在阶段二中出现问题的话，那么其他参与者将会·一直处于锁定事务资源的状态中，而无法继续完成事务操作。
  3. 数据不一致
    在二阶段提交协议的阶段二，执行事务提交的时候，当协调者向所有的参与者发送Commit请求之后，发生了局部网络异常或者是协调者在尚未发送完Commit请求之前自身发生了崩溃，导致最终只有部分参与者收到了Commit请求。于是，这部分收到了Commit请求的参与者就会进行事务的提交，而其他没有收到Commit请求的参与者则无法进行事务提交。
  4. 太过保守
    如果在协调者指示参与者进行事务提交询问的过程中,参与者出现故障而导致协调者始终无法获取到所有参与者的响应信息的话，这时协调者只能依靠其自身的超时机制来判断是否需要中断事务。二阶段提交协议没有设计较为完善的容错机制,任意一个节点的失败都会导致整个事务的失败。

3PC

3PC，是Three-Phase Commit的缩写，即三阶段提交,将二阶段提交协议的“提交事务请求“过程一分为二,形成了由CanCommit, PreCommit和 do Commit

CanCommit

  1. 事务询问。
    协调者向所有的参与者发送一个包含事务内容的 canCommit 请求，询问是否可以执行事务提交操作，并开始等待各参与者的响应。
  2. 各参与者向协调者反馈事务询问的响应。
    参与者在接收到来自协调者的canCommit请求后，正常情况下，如果其自身认为可以顺利执行事务，那么会反馈Yes响应，并进入预备状态，否则反馈No响应。

PreCommit

在阶段二中，协调者会根据各参与者的反馈情况来决定是否可以进行事务的PreCommit操作，正常情况下，包含两种可能。

执行事务预提交

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

  1. 发送预提交请求。
    协调者向所有参与者节点发出preCommit的请求，并进入Prepared阶段。
  2. 事务预提交。
    参与者接收到preCommit请求后，会执行事务操作，并将Undo和Redo信息记录到事务日志中。
  3. 各参与者向协调者反馈事务执行的响应。
    如果参与者成功执行了事务操作，那么就会反馈给协调者Ack响应，同时等待最终的指令:提交(commit)或中止 (abort)。
中断事务

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

  1. 发送中断请求。
    协调者向所有参与者节点发出abort请求。

  2. 中断事务。

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

do Commit

执行提交
  1. 发送提交请求。
    进入这一阶段，假设协调者处于正常工作状态，并且它接收到了来自所有参与者的Ack响应，那么它将从“预提交”状态转换到“提交”状态，并向所有的参与者发送doCommit请求。
  2. 事务提交。
    参与者接收到doCommit请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源。
  3. 反馈事务提交结果。
    参与者在完成事务提交之后，向协调者发送 Ack 消息。
  4. 完成事务。
    协调者接收到所有参与者反馈的Ack 消息后，完成事务。
中断事务

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

  1. 发送中断请求。
    协调者向所有的参与者节点发送abort 请求。
  2. 事务回滚。
    参与者接收到abort请求后，会利用其在阶段二中记录的Undo信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。
  3. 反锁事务回滚结果。
    参与者在完成事务回滚之后，向协调者发送 Ack 消息。
  4. 中断事务。
    协调者接收到所有参与者反馈的Ack 消息后，中断事务。

优缺点

优点：相较于二阶段提交协议，三阶段提交协议最大的优点就是降低了参与者的阻塞范围，并且能够在出现单点故障后继续达成一致。
缺点:三阶段提交协议在去除阻塞的同时也引入了新的问题，那就是在参与者接收到preCommit消息后，如果网络出现分区，此时协调者所在的节点和参与者无法进行正常的网络通信，在这种情况下，该参与者依然会进行事务的提交，这必然出现数据的不一致性。

四、Paxos算法

Paxos算法:一种基于消息传递且具有高度容错特性的一致性算法。

Paxos算法解决的问题:就是如何快速正确的在一个分布式系统中对某个数据值达成一致，并且保证不论发生任何异常，都不会破坏整个系统的一致性。

image-20220326224050431

在一个Paxos系统中，首先将所有节点划分为Proposer(提议者)，Acceptor(接受者)，和Learner(学习者)。(注意:每个节点都可以身兼数职)。

一个完整的Paxos算法流程分为三个阶段:

  • Prepare准备阶段
    1. Proposer向多个Acceptor发出Propose请求Promise(承诺).
    2. Acceptor针对收到的Propose请求进行Promise(承诺)
  • Accept接受阶段
    1. Proposer收到多数Acceptor承 诺的Promise后，向Acceptor发出Propose请求
    2. Acceptor针对收到的Propose请求进行Accept处理
  • Learn学习阶段:
    1. Proposer将形成的决议发送给所有Learners

算法流程

  1. Prepare: Proposer生成全局唯一且递增的Proposal ID，向所有Acceptor发送Propose请求，这里无需携带提案内容，只携带Proposal ID即可。
  2. Promise: Acceptor收到Propose请求后，做出”两个承诺，一个应答“。
    • 不再接受Proposal ID小于等于（注意:这里是<=）当前请求的Propose请求。
    • 不再接受Proposal ID小于（注意:这里是<）当前请求的Accept请求。
    • 不违背以前做出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。
  3. Propose: Proposer收到多数Acceptor的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案。如果所有应答的提案Value均为空值，则可以自己随意决定提案Value。然后携带当前Proposal ID，向所有Acceptor发送Propose请求。
  4. Accept: Acceptor收到Propose请求后，在不违背自己之前做出的承诺下，接受并持久化当前Proposal ID和提案Value。
  5. Learn: Proposer收到多数Acceptor的Accept后，决议形成，将形成的决议发送给所有Learner

3种情况

A1,A2,A3,A4,A5发起提案

第一种

A1发起税率10%的提案

  1. A1发起1号Proposal的Propose，等待Promise承诺;
  2. A2-A5回应Promise;
  3. A1在收到两份回复时就会发起税率10%的Proposal;
  4. A2-A5回应Accept;

第二种

A1发起税率10%的提案，A5发起税率20%的提案

  1. A1，A5同时发起Propose(序号分别为1，2)
  2. A2承诺A1，A4承诺A5，A3行为成为关键
  3. 情况1:A3先收到A1消息，承诺A1。
  4. A1发起Proposal (1,10%)，A2，A3接受。
  5. 之后A3又收到A5消息，回复A1:(1，10%)，并承诺A5。
  6. A5发起Proposal (2，20%)，A3，A4接受。之后A1，A5同时广播决议。

第三种

A1发起税率10%的提案，A5发起税率20%的提案

  1. A1，A5同时发起Propose(序号分别为1，2)
  2. A2承诺A1，A4承诺A5，A3行为成为关键
  3. 情况2:A3先收到A1消息，承诺A1。之后立刻收到A5消息，承诺A5。
  4. A1发起Proposal（1，10%)，无足该响应，A1重新Propose (序号3)，A3再次承诺A1
  5. A5发起Proposal(2，20%），无足够相应，A5重新Propose(.序号4〕 ，A3再次承诺A5
  6. …

造成这种情况的原囚是系统中有一个以上的Proposer,多个Proposers 相互争夺Acceptor,造成迟迟无法达成一致的情况。针对这种情况，一种改进的Paxos,算法被提出:从系统中选出一个节点作为Leader，只有Leader 能够发起提案。这样，一次Paxos流程中只有一个Proposer，不会出现活锁的情况，此时只会出现例子中第一种情况。

五、ZAB协议

Zab 借鉴了Paxos算法，是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。基于该协议，Zookeeper设计为只有一台客户端（Leader）负责处理外部的写事务请求，然后Leader 客户端将数据同步到其他Follower节点。即Zookeeper 只有一个Leader可以发起提案。

Zab协议包括两种基本的模式:消息广播、崩溃恢复。

消息广播

image-20220327131940966
  1. 客户端发起一个写操作请求。
  2. Leader服务器将客户端的请求转化为事务Proposal提案，同时为每个Proposal分配一个全局的ID，即zxid。
  3. Leader服务器为每个Follower服务器分配一个单独的队列，然后将需要广播的Proposal依次放到队列中去，并且根据FIFO策略进行消息发送
  4. Follower接收到Proposal后，会首先将其以事务日志的方式写入本地磁盘中，写入成功后向Leader反馈一个Ack响应消息。
  5. Leader接收到超过半数以上Follower的Ack响应消息后，即认为消息发送成功，可以发送commit消息。
  6. Leader向所有Follower广播commit消息，同时自身也会完成事务提交。Follower按收到commit消息后，会将上一条事务提交。
  7. Zookeeper采用Zab协议的核心，就是只要有一台服务器提交了Proposal，就要确保所有的服务器最终都能正确提交Proposals

ZAB协议针对事务请求的处理过程类似于一个两阶段提交过程

  1. 广播事务阶段
  2. 广播提交操作

奔溃恢复

异常假设

这两阶段提交模型，有可能因为Leader宕机带来数据不一致，比如

  1. 假设一个事务在Leader提出之后，Leader挂了。

  2. 一个事务在Leader上提交了，并且过半的Follower都响应Ack了，但是Leader在Commit消息发出之前挂了。

    image-20220327133025139

奔溃恢复满足两个要求：

  1. 确保已经被Leader提交的提案Proposal，必须最终被所有的Follower服务器提交。(已经产生的提案，Follower必须执行。
  2. 确保丢弃已经被Leader提出的，但是没有被提交的Proposal。(丢弃胎死腹中的提案)

Leader选举

image-20220327133547020
  1. 新选举出来的Leader不能包含未提交的Proposal。即新Leader必须都是已经提交了Proposal的Follower服务器节点。
  2. 新选举的Leader节点中含有最大的zxid。这样做的好处是可以避免Leader服务器检查Proposal的提交和丢弃工作。

数据恢复

  1. 完成Leader选举后，在正式开始工作之前（接收事务请求，然后提出新的Proposal),Leader服务器会首先确认事务日志中的所有的Proposal是否己经被集群中过半的服务器Commit。
  2. Leader服务器需要确保所有的Follower服务器能够接收到每一条事务的Proposal，并且能将所有已经提交的事务Proposal应用到内存数据中。等到Follower将所有尚未同步的事务Proposal都从Leader服务器上同步过，并且应用到内存数据中以后，Leader才会把该Follower加入到真正可用的Follower列表中。