目录

• 拜占庭将军问题
• paxos算法
• • paxos算法流程
  • 情况一
  • 情况二
  • • 情况1
    • 情况2
• ZAB协议
• • ZAB协议内容
  • • 消息广播
    • • 过程
      • 可能出现的问题
    • 崩溃恢复
    • • 异常假设
      • leader选举
      • 数据恢复
• CAP理论

拜占庭将军问题

拜占庭罗马帝国国土辽阔，为了达到防御目的，每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序。在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成（百度百科）

paxos算法

在paxos算法中，首先将所有节点划分为proposerI（提议者）、acceptor（接收者）、learner（学习者）每个节点可以充当多个角色

paxos算法流程

1.Prepare（准备阶段）
proposer向多个acceptor发出propose请求promise
acceptor针对收到的propose请求进行promise
2.accept（接受阶段）
proposer收到多数acceptor承诺地epromise后，向acceptor发出propose请求
acceptor针对收到的propose请求进行accept处理
3.learn（学习阶段）
1.prepare:proposer生成全局唯一递增的Proposal ID，向所有Accepter发送Propose请求，这里毋须携带提案内容，只携带proposal ID即可

2.promise:acceptor收到propose请求后，做出“两个承诺，一个应答”

​ （1）不再接受proposal ID小于等于当前请求的Propose请求

​ （2）不再接受proposal ID小于当前请求的accept请求

​ （3）不违背以前作出的承诺下，回复已经accept过的提案中的proposal ID最大的哪个提案的value和proposal ID，没有则返回空值

3.propose:proposer收到多数accepter的promise应答后，从应答中选择proposal ID最大的提案的value，作为本次要发起的提案。如果所有应答的提案value均为空值，则可以自己随意决定提案value，然后携带当前proposal ID，向所有acceptor发送propose请求

4.accept:acceptot收到propose请求后，在不违背自己之前做出的承诺下，接受并持久化当前proposal ID和提案value

情况一

A1,A2,A3,A4,A5五位议员就税率问题进行决议

1.A1发起Proposal的Propose（未告知决议的内容），等待承诺

2.A2-A5回应promise

3.A1在收到两份回复时就会发起税率10%的proposal

4.A2-A5回应accept

5.通过proposal，税率10%

情况二

A1提出提案的同时，A5决定将税率定为20%

1.A1，A5同时发起Proposal的Propose（序号分别为1，2）

2.A2承诺A1，A4承诺A5，A3成为关键

情况1

3.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同时广播决议，由于A5的proposal ID大，A2，A3更新承诺

情况2

A3先收到A1的消息，承诺A1，之后立刻收到A5的消息，承诺A5

A1发起Proposal（1，10%），无足够响应，A1重新propose（序号为3），A3再次承诺A1

A5发起Proposal（2，20%），无足够响应，A5重新propose（序号为4），A3再次承诺A5

以此往复

造成这种情况的原因是系统中有一个以上的proposer相互竞争acceptor，造成长时间无法达成一致的情况。
改进方法：从系统中选出一个节点作为leader，只有leader能够发起提案。这样一次paxos只有一个proposer不会出现活锁的情况

ZAB协议

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

ZAB协议内容

ZAB协议包括：消息广播，崩溃恢复

消息广播

过程

(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，就要确保所有的服务器最终都能正确提交Proposal。

可能出现的问题

ZAB协议针对事务请求的处理过程类似于一个两阶段提交过程:(1）广播事务阶段(2）广播提交操作
这两阶段提交模型如下，有可能因为Leader宕机带来数据不一致，比如
( 1 ) Leader发起一个事务Proposal1后就宕机，Follower都没有Proposall
( 2 ) Leader收到半数ACK宕机，没来得及向Follower发送Commit

崩溃恢复

崩溃恢复主要包括两部分:Leader选举和数据恢复。

异常假设

假设两种服务器异常情况

(1）假设一个事务在Leader提出之后，Leader挂了。
(2）一个事务在Leader上提交了，并且过半的Follower都响应Ack了，但是Leader在Commit消息发出之前挂
Zab协议崩溃恢复要求满足以下两个要求:
(1）确保已经被Leader提交的提案Proposal，必须最终被所有的Follower服务器提交。(已经产生的提案，Follower必须执行)
(2）确保丢弃已经被Leader提出的，但是没有被提交的Proposal。

leader选举

选举条件:
(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列表中。

CAP理论

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

CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。
CP without A：如果不要求A（可用），相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。
AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。

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