1 分布式特点
分布性
对等性
并发性
缺乏全局时钟
故障总会发生
2 分布式问题
通信异常
网络分区
三态 单体应用中一次请求的结果总是明确的，分布式系统中因为网络是不可靠的，导致成功、失败和超时
节点故障
3 单机事务
ACID
A=Atomicity 原子性

C=Consistency 一致性

I=Isolation 隔离性

D=Durability 持久性

4 分布式理论
4.1 CAP
C=Consistency 一致性

A=可用性

P=分区容错性

分区容错性约束了一个分布式系统在遇到任何网络分区故障的时候，都要能够保证对外提供满足一致性和可用性的服务，除非是整个网络都发生故障

4.2 BASE
BA=Basically Available 基本可用

S=Soft State 软状态

E=Eventually consistent 最终一致性

4.3 最终一致性变种
因果一致性

读己之所写

会话一致性

单调读一致性

单调写一致性

5 一致性协议
5.1 2PC
5.1.1 角色
协调者 统一调度所有分布式节点的执行逻辑

参与者 执行节点

5.1.2 阶段
阶段一 提交事务请求
事务询问 协调者向参与者询问是否可以执行事务
执行事务 参与者执行事务，记录Undo和Redo日志信息
反馈响应 参与者反馈Ack，可以执行事务返回Yes，不可以执行事务返回No
阶段二 执行事务提交
协调者根据Ack决策

提交事务 所有参与者都回复Yes表示可以执行事务
协调者告诉参与者进行Commit
参与者提交事务，释放独占的资源
参与者向协调者Ack
协调者收到所有Ack 整个分布式事务结束
回滚事务 但凡有一个参与者回复No
协调者向参与者发送Rollback请求
参与者执行回滚，释放独占的资源
参与者回复协调者Ack
协调者收到所有参与者Ack后 整个分布式事务宣告结束
5.1.3 两阶段协议问题
同步阻塞
单点问题 极度依赖协调者
数据不一致 第二阶段时，协调者向参与者发送提交请求时，发送一半出现网络问题，导致有的参与者提交了事务，有的参与者没有提交事务
过于保守 没有设计完善的容错机制，任意一个节点的失败都会导致整个事务的失败
5.2 3PC
5.2.1 角色
协调者 统一调度所有分布式节点的执行逻辑

参与者 执行节点

5.2.2 阶段
阶段一 CanCommit
阶段二 PreCommit
阶段三 doCommit
5.2.3 三阶段提交的问题
参与者接收到preCommit消息后，如果网络出现分区，此时协调者所在的节点和参与者无法进行网络通信，在这种情况下，该参与者依然会进行事物的提交，导致数据不一致

6 Paxios算法
基于消息传递且具有高度容错特性的一致性算法

引入过半理念和支持分布式节点角色转换，避免了分布式单点问题，也解决了无限期待问题

6.1 一致性安全需求
只有被剔除的提案才能被选定
只有一个值被选定
如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个
6.2 目标
保证最终有一个提案会被选定，当提案被选定之后，进程最终也能获取到被选定的提案

6.3 角色
Proposer
Acceptor
Learner
6.4 过程
6.4.1 提案的选定
Poposer向一个Acceptor集合发送提案

足够多的Acceptor是整个Acceptor集合的一个子集，并且让这个集合大的可以包含Acceptor集合中的大多数成员

提案由一个编号和Value的组成的组合体，[编号, Value]

6.4.2 Proposer生成提案
Proposer在产生一个编号为Mn的提案时，必须要知道某一个将要活着已经被半数以上Acceptor批准的编号小于Mn但为最大编号的提案，并且Proposer会要求所有的Acceptor都不要再批准任何编号小于Mn的提案

6.4.3 Acceptor批准提案
一个Acceptor可能会收到来自Proposer的两种请求，分别是Prepare请求和Accept请求

Prepare请求 Acceptor可以在任何时候响应一个Prepare请求
Accept请求 在不违背Accept现有承诺的前提下，可以任意响应Accept请求
6.5 算法
6.5.1 Proposer和Acceptor提案选定
阶段一
1 Proposer选择一个提案编号Mn，然后向Acceptor的某个超过半数的子集发送编号为Mn的Prepare请求

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

阶段二
1 如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应，那么它就会发送一个针对[Mn,Vn]提案的Accept请求给Acceptor

2 如果Acceptor收到针对这个[Mn,Vn]提案的Accept请求，只要该Acceptor尚未对编号大于Mn的Prepare请求作出响应，就会通过这个提案

6.5.2 Learner获取提案
6.5.3 选取主Proposer保证算法活性
7 zk
7.1 集群角色
Leader
Follower
Observer
7.2 数据结构
ZNode

持久节点 除非主动移除，否则一直保存在zk上
临时节点 生命周期跟客户端会话绑定
SEQUENTIAL属性 zk允许用户为每个节点添加属性，一旦节点被标记上这个属性，那么在这个节点被创建的时候，zk会自动在其节点后面追加上一个整型数字(由父节点维护的自增数字)

7.3 版本
对于每个ZNode，zk都会维护一个Stat的数据结构

Stat中记录了这个ZNode的3个数据版本

version 当前ZNode的版本
cversion 当前ZNode子节点的版本
aversion 当前ZNode的ACL版本
7.4 ZAB协议
ZooKeeper Atomic Broadcast zk原子广播协议，数据一致性的核心算法

支持崩溃恢复的原子广播协议

zk使用一个单一的主进程接收并处理客户端的所有事务请求，采用ZAB的原子广播协议，将服务器数据的变更以事务Proposal的形式广播到所有的副本进程上

ZAB协议的这个主备模型架构保证了同一时刻集群中只能有一个主进程来广播服务器的状态变更，因此能够很好地处理客户端大量的并发请求

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

所有事务请求必须由一个全局唯一的服务器来协调处理，即Leader
Leader服务器负责将一个客户端事务请求转为一个事务Proposal提议，并将该Proposal分发给集群中所有的follower服务器
Leader服务器等待所有Follower服务器的反馈，收到半数后Leader就会再次向所有Follower服务器分发Commit消息，要求将Proposal进行提交
ZAB协议包括两种基本模式

崩溃恢复
整个服务框架启动或者Lader出现网络中断、崩溃退出与重启等异常情况时，ZAB协议就会进入恢复模式并选举产生新的Leader
当选举产生了新的Leader，同步集群中过半机器与Leader完成了同步之后ZAB就会退出恢复模式
消息广播
集群中已经过半的Follower完成了和Leader的状态同步，那么整个服务框架就可以进入消息广播模式了
当一台同样遵守ZAB协议的服务器启动后加入到集群时，如果此时集群中已经存在了一个Leader在负责进行消息广播，那么新加入的服务器会自觉加入数据恢复模式
找到Leader所在的服务器，并与其进行数据同步
然后一起参与到消息广播流程中
ZAB协议的事务编号ZXID设计中，64位

高32位 代表了Leader周期epoch的编号，每当选举产生一个新的Leader服务器，就会从这个服务器上本地日志中最大事务Proposal的ZXID中解析出对应的epoch值加1
低32位 单调递增的计数器，针对客户端的每一个事务请求，Leader服务器在产生一个的新的事务Proposal的时候都会对该计数器进行加1操作
7.4.1 过程
崩溃恢复
消息广播
7.4.2 阶段
发现 Leader选举过程
同步
广播 ZAB协议正式开始接收客户端新的事务请求，并进行消息广播流程
7.4.3 状态
Looking Leader选举阶段
Following Follower服务器和Leader服务器保持同步状态
Leading Leader服务器作为主进程领导状态
8 ZAB vs Paxos
区别
设计目标不一样

ZAB协议主要用于构建一个高可用的分布式数据主备系统
Paxos算法用于构建一个分布式的一致性状态机系统
5.6 zk典型应用场景
数据发布/订阅
负载均衡
命名服务
分布式协调/通知
集群管理
Master选举
分布式锁
分布式队列

一致性
我们用集群是为了提高整个系统的可用性，就是即使少数节点挂掉的话，整个集群还是可以去提供服务的。好，zookeeper集群每一个节点上面，它存储的数据都是全量的数据，也就是它们之间，每一台上面存储的数据都是同一份数据，而我们前面也提到，集群中它每个节点都可以去提供读取服务，所以这样的话，就得保证多个节点之间，它们的数据是一致的，才不会出现连接不同节点读取到不同的值是吧，也就是我们需要去保证集群节点间数据的一致性。那么接下来我们就来看一下，zookeeper集群是如何去做到这一点的，就是如何去做节点间数据的同步

zookeeper保证数据一致性的协议
而在我们的zookeeper中保证数据一致性用的是ZAB协议。通过这个协议来进行ZooKeeper集群间的数据同步，保证数据的一致性。

我们先来简单看一下zab协议是工作流程（图）：

ZooKeeper写数据的机制是客户端把写请求发送到leader节点上，如果发送的是follower节点，follower节点会把写请求转发到leader节点，leader节点会把数据通过proposal请求发送到所有节点，包括自己，所有到节点接受到数据以后都会写到自己到本地磁盘上面，写好了以后会发送一个ack请求给leader，leader只要接受到过半的节点发送ack响应回来，就会发送commit消息给各个节点，各个节点就会把消息放入到内存中，放内存是为了保证高性能，该消息就会用户可见了。

那这个时候，若ZooKeeper要想保证数据一致性，就需考虑如下两个情况

情况一：leader执行commit了，还没来得及给follower发送commit的时候，leader宕机了，这个时候如何保证消息一致性？
情况二：leader的事务性请求已经在部分节点应用了，这个时候leader挂掉了，如何保证消息一致性？
如果是Leader故障，事务型请求未提交的情况，也就是只在Leader服务器上提出但没有提交的操作的操作需要丢弃掉。因为实际上它只是完成了第一阶段。

Leader故障，事务型请求已提交的情况，也就是已在Leader服务器上提交的操作最终被所有的服务器节点都提交。等后面讲到ZAB协议，概念就更清晰了，在某个节点提交应用成功，那这个节点的zxid肯定更大，决定它会被选举为新的leader。然后再进行同步。

Zookeeper集群Leader选举
ZooKeeper集群中三种类型的节点
集群在运行过程中，节点发生故障时，这个集群是如何来应对的？

ZooKeeper中三种类型的节点是吧，我们逐个类型来看一下：

Observer节点，这种节点它只是为了提升读性能，并不会参与到任何决策过程，所以，就算它挂了，也是不会影响集群的正常运行的。
Follower节点，如果是少数节点挂了的话，就是没超过半数的话，那也不会影响，那如果故障节点超过半数的话，这个时候就没办法了，需要把节点恢复起来之后才可以运行
Leader节点，通过前面的学习我们也知道，这个Leader在整个集群中起着至关重要的作用，整个集群的协调工作都是由它来发起的，所以这个时候假如Leader挂掉了，整个集群也没办法正常运行，就不是有没有超过半数的问题了。
所以当Leader节点挂掉之后，就需要尽快从可用的节点中再来选出一个节点来当新的Leader，才能让集群恢复可用。那这里怎么选新的Leader，就是一个需要解决的问题了。我们想一下，可以简单的从剩下的Follower节点随便选一个来当新的领导吗？我们可以想一下这个场景：Leader故障，事务型请求已提交，在这个场景中，我们这Follower节点的状态明显是不一样的，所以当时我们也说了，这个场景下，ZooKeeper集群是有机制去保证让这个Server1当上新领导的。这里就涉及到了ZooKeeper集群的Leader选举算法了，这个算法对ZooKeeper集群去保证可用性和数据一致性是非常重要的，那么我们就来详细看一下，这个算法它具体是什么样的一个处理过程。

那么在开始分析算法之前，我们先来看一下集群中节点的几种状态，因为整个选举的过程，会涉及到这几个状态的流转。

ZAB 中的节点有四种状态
looking：节点处于选举状态
following：当前节点是跟随者，服从 leader 节点的命令，后面它是会参与投票的
Obsering：观察状态，同步leader状态，但是不参与投票
leading：当前节点是 leader，负责协调事务
Leader选举过程
好，接下来我们来看一下Leader的选举过程，那么对于Zookeeper集群来说，当出现以下两种情况的时候，就需要进行Leader选举：

集群启动期间Leader选举
集群运行期间Leader故障
然后整个Leader选举的过程，就是一个投票的过程，然后当某一个节点，它接收到超过半数节点的选票的话，就可以认为它当选Leader了。但是这里要投给谁，其实还是有讲究的。

那么我们可以想一下比如我们在选村长的时候，一般我们就看谁能力大是吧，谁能力大就投给谁，然后如果能力差不多，可能就会选年纪大一点的，德高望重嘛。好那在ZooKeeper集群选举里面，当一个节点要决定这个选票要投给谁的时候，会根据两个重要的ID来进行判断：

首先是看事务ID（zxid），哪个服务器上的事务ID最大，就投给哪个。【对应这个场景：Leader故障，事务型请求已提交】
那么当两个节点事务ID一样的话，就会看节点编号，也就是myid里面存的编号，哪个大投给哪个
好有了投票标准之后，就可以来开始选举了，但是选举的时候，可能会有不止一轮的投票，同样跟我们选村长一样一般也会有多轮投票，那这种情况下，前一轮的选票，到下一轮的话，就应该变成无效选票了是吧。

而在ZooKeeper里面，它同样有这个轮次的概念，就是每一次投票它其实是有时间限制的【syncLimit：集群中的follower服务器与leader服务器之间请求和应答之间能容忍的最多心跳数(tickTime的数量)。】，如果当前投出去的票，没有收到反馈，那么在等待一段时间后，就当作超时处理，这个时候就可以发起一下轮的投票，诶但是有可能，上一轮的反馈它是因为网络延迟的问题，这个时候才收到，那么因为现在已经是开始了下一轮了，所以这个也只能当做无效选票处理了。

图：投票响应超时则进入下一轮

选举算法
好 有了这些选举的标准和规则之后，就可以来开始选举了，选举算法：

首先每个节点均发起选举自己为领导者的投票（自己的投给自己）；因为刚开始也不知道哪个节点的事务ID最大，所以就先给自己一票再说，接着就给其它节点发消息来拉票，拉票的时候，像在选举的时候一样，拉票的时候就会说自己能力多牛，那么这里也一样，它会把当前节点上最大的事务ID给带过去
其它节点收到拉票请求时，就会比较发起者的事务ID，是否比自己最新的事务ID大，如果比自己的ID大，那好就给它投一票吧，否则就不投给它了。那如果事务ID相等的话，则比较发起者的服务器编号。这一点呢我们前面也说到过，就像选举的时候，先看一下能力谁强，再看一下谁的年纪大。
然后经过每一轮的投票之后，就看有没有哪个节点，它获得的票数（含自己的）大于集群的半数，有的话就说明这个节点竞选成功，成为了Leader节点，未超过半数且领导者未选出，则再次发起投票。
集群启动期间Leader选举
我们现在看第一种服务器启动时候对leader选举 我们来看一下这张图

假设一个 Zookeeper 集群中有5台服务器，id从1到5编号，并且它们都是最新启动的，没有历史数据

假设服务器依次启动，我们来分析一下选举过程：

服务器1启动

服务器1启动，发起一次选举，服务器1投自己一票，此时服务器1票数一票，不够半数以上，要大于等于3票，选举无法完成。 所以，这个时候对投票结果：服务器1为1票。

服务器1状态保持为LOOKING。

服务器2启动

服务器2启动，也发起一次选举，服务器1和2分别投自己一票，此时服务器1发现服务器2的服务id比自己大，更改选票投给服务器2。 所以投票结果：服务器1为0票，服务器2为2票。

服务器1，2状态保持LOOKING

服务器3启动

服务器3也启动了，同时也发起一次选举，服务器1、2、3先投自己一票，然后因为服务器3的服务器id最大，两者更改选票投给为服务器3；

这时候，投票结果为：服务器1为0票，服务器2为0票，服务器3为3票。此时服务器3的票数已经超过半数，服务器3当选Leader。

服务器1，2更改状态为FOLLOWING，服务器3更改状态为LEADING

服务器4启动

服务器4启动，也加入进来，发起一次选举，此时服务器1，2，3已经不是LOOKING 状态，不会更改选票信息。交换选票信息结果：服务器3为3票，服务器4为1票。此时服务器4服从多数，更改选票信息为服务器3。

服务器4并更改状态为FOLLOWING。

服务器5启动

与服务器4一样投票给3，此时服务器3一共5票，服务器5为0票。

服务器5并更改状态为FOLLOWING。

图 11
最终的结果：

服务器3是 Leader，状态为 LEADING；其余服务器是 Follower，状态为 FOLLOWING。

好，这就是服务器初始化启动时候的选举过程。

服务器运行期间 Leader 故障
那么，我们继续来看一下第二种选举过程，服务器运行期间 Leader 故障。

我们来看一下这个场景：

在 Zookeeper运行期间 Leader 和 follower 各司其职，当有follower 服务器宕机或加入不会影响 Leader，但是一旦 Leader 服务器挂了，那么整个 Zookeeper 集群将暂停对外服务，会触发新一轮的选举。

初始状态下服务器3当选为Leader，假设现在服务器3故障宕机了，此时每个服务器上zxid可能都不一样，server1为10，server2为12，server4为10，server5为10

运行期选举
运行期选举与初始状态投票过程基本类似，大致可以分为以下几个步骤：

状态变更。Leader 故障后，剩下的follower节点因为跟Leader联系不上了，这个时候它会将自己的服务器状态变更为LOOKING，然后开始进入Leader选举过程。
每个Server会发出投票。
接收来自各个服务器的投票，如果其它服务器的数据比自己的新会改投票。
处理和统计投票，每一轮投票结束后都会统计投票，超过半数即可当选。
改变服务器的状态，宣布当选
好，这里我们以这张图来说明比较好容易理解点：

1）第一次投票，每台机器都会将票投给自己。

2）接着每台机器都会将自己的投票发给其它机器，如果发现其它机器的zxid比自己大，那么就需要改投票重新投一次。比如server1 收到了三张票，发现server2的xzid为102，pk一下发现自己输了，后面果断改投票选server2为老大，同理，因为从图中很明显看到服务器2点xzxid是最大的，所以最后是服务器2当选leader服务器。

小结
简单来将，通常哪台机器服务器上的数据越新，那么越有可能成为leader，原因也很简单，数据越新，那么它的zxid也就越大，也就越能够保证数据的恢复。如果集群中有几个相同的最大的zxid，那么服务器id较大的服务器成为leader。