** 一. 基础知识**
1.2 产生背景
1.2.1 集中式服务
所有的请求与处理都在一台机器上面执行，或者在多个横向扩展的业务机器中，但是最终数据存储都是在同一个存储节点上。也就是所有的业务的处理，包括状态和数据都是保存在同一个地方的，不需要考虑数据的一致性问题。当其到达瓶颈的时候就需要纵向扩展服务器或者存储节点的性能，不能横向扩展。
1.2.2 分布式服务
一个集群堆外提供服务，在客户端看来就像一个机器一样， 不管访问到谁， 最终提供的结果都是一样的。
在一个打的分布式服务集群内部，又分为多个小的分布式组件集群，每个组件负责一个功能， 例如注册中心， 缓存中心， 配置中心等，他们都需要以集群形式部署，以保证高可用和拓展性。
1.2.3 一致性算法产生背景
上面分布式服务上说到的，业务集群中的各个分布式组件都是需要以集群形式存在，这些组件的集群都需要保证数据一致，这样在这个组件的客户端访问这个集群的时候才能保证功能都是一致， 例如由a、b、c单个节点组成其中一个分布式组件集群，访问a、b或者c任意一个节点都需要保证返回的结果都是一样的。
试想我们可以通过什么样的方式来实现这个功能， 如何做到访问a,b,c三个节点，产生的结果都是一样的呢？
首先我们想到的就是借助数据库， a,b,c访问同一个数据库，或者数据库集群，由数据库来保证访问这三个节点中的随便一个都是一样的结果。对于数据库的方式，先不讨论数据库是否能真正实现分布式(实际上传统关系型数据库的高可用集群部署是依赖硬件环境完成的，并且不追求分布式，采用最简单的主从复制或者双写的方式进行数据的冗余备份)，单就引入数据库，和对数据库的集群要求的重量级程度，便已经是一个需要考虑的指标了。
假如我们这就是一个轻量中间件，不需要借助数据库或者第三方的存储系统的时候， 如何保证三个节点出来的数据都是一样的呢， 这个时候就需要一致性算法了， 来保证在a\b\c三个节点上保存的数据都是一致的。
1.3 CAP理论
CAP(Consistency, Availability, Partition Tolerance)，
C一致性：各个节点的数据备份是一致的，强一致性(数据实时同步)。
A可用性：每个请求都能返回响应， 但是响应的数据不一定是最新的(数据不是实时同步，而是后台异步复制)
P容错性：集群中的某一个分区(节点)异常， 不影响集群的整体对外服务。
CAP理论的结论是， 三者不可兼得，实现一个分布式集群必须要有一个舍弃。
总结，
CA系统：除了传统的关系型数据库：oracle，mysql是属于CA。其他的分布式系统都是在C与A中进行取舍。
CP系统：保证集群能返回数据，且保证数据是最新的。代表中间件：单点redis，
AP系统：保证集群能返回数据，不保证是最新的数据。代表中间件：redis集群，zookeeper,
1.4 BASE理论
Base Available：基本可用。保证核心可用，容忍部分功能不可用。
Soft state：软状态。中间状态，这个中间状态不影响上面的基本可用性， 在某一段时间内容忍数据不同步。
Eventually consistent：最终一致性。在经过一段时间以后， 最终数据完成的强一致性的同步。
简单概括中心思想就是：各个业务应该基于业务的特点，在保证集群基本可用的前提下， 允许存在中间状态， 这个中间状态允许短时间数据不同步，但需要实现数据的最终一致性
1.5 NWR机制
N：复制的节点数，即一份数据被保存的副本数
W：写操作成功的节点数，即每次数据写入写成功的副本数，W肯定是小于等于N的。
R：读操作获取最新版本数据所需的最小节点数，即每次读取成功至少需要读取的副本数
只要保证（W+R>N）就一定能读取到最新的数据，数据一致性级别完全可以根据读写副本数的约束来达到强一致性！
W=1,R=N ，Write Once Read All - 读差，分区容错差，写强
R=1,W=N，Read Only Write All - 写差，读强，容错强
R=Q,W=Q, where Q = N/2 +1 - 读、写、容错取得一个平衡的点
二. ZAB协议
2.1 基础名词
Epoch : 选举周期，别名也叫逻辑时钟，每一个新leader就一个新周期。
ZXID : 全局ID，高32位存放Epoch，低32位存放消息ID， 代表的就是每一轮选举完以后，这一轮的leader发起的所有的请求。
serverid：每个节点的ID
节点状态：looking，following，observing，leading
Quorum ：法人机制，半数以上节点成功便可通过。
2.2 运行原理
分布式一致性， 就是在写入一个数据的时候， 要么都写入， 要么都不写入，zab通过quorum机制，半数以上通过，还有zxid的全局唯一性，来保证消息的全局有序和唯一性。
ZAB一共有两种模式，消息广播模式和奔溃恢复模式。
2.3 消息广播模式(正常写数据)
- leader将客户端请求转换成propose提案， 生成一个全局唯一ZXID
- leader将提案发送给follower，follower将提案写入到本地事务日志中，并回复ACK确认
- leader收到半数以上的follower的ack后， 发送commit给所有节点确认写入
2.4 奔溃恢复模式
2.4.1 选举主节点
2.4.1.1 选票构成
serverid，zxid，epoch, 节点状态
2.4.1.2 选举逻辑
- looking状态的选票处理逻辑
- 判定逻辑时钟Epoch。
- 我的逻辑时钟比对方的新，告诉对方。
- 对方的比我的新，则清空我的选票箱并更新他的票据。
- 更新自己选票结果，并广播给其他的servrer。选票生成逻辑，先比对zxid，再比对serverid，大者获胜
- 统计是否接收到所有节点(或者半数以上节点)的选票信息， 根据这些信息，确定自己的状态(follower, leader)。
- following、leading状态的选票处理逻辑
- 同一个逻辑时钟Epoch，统计票据，根据票据判定是否有多数节点选举他，是的话设置状态，退出选举过程
- 不是同一个逻辑时钟，说明自己的角色装填已经在另一个逻辑时钟的选举周期里面新建成功的，想选票更新会给客户端
2.4.3 数据恢复
选举出leader以后， leader会将follower和自己所有commit过的zxid一起同步给所有的follower
2.3 总结
通过选举机制， 保证了集群只有一个节点做主节点， 一个主节点进行写保证了集群中的所有提议的唯一性和连续性，但是由于只有一个主节点，所以写操作性能远远不及读性能，适合读多写少的场景使用。
三. Raft协议
3.1 基础名词
Term: 任期，每一任期内一个主节点
节点状态：Follower、Leader、Candidate
3.2 选举
- 所有节点起来的时候节点会设置一个选举超时（150-300ms），哪个节点最先经过这个时间以后便会成为Candidate观察者
- 观察者给自己设置一个term，然后给自己投票并广播给其他节点。
- 其他节点没有在这个term投过票的话就会投票给这个观察节点，并同时再设置一个超时时间
- 观察者收到半数以上节点的时候就会转换成leader节点，并且广播给其他节点一个同步指令，这些指令都需要在心跳超时前发送出去。
- 其他节点收到了心跳信息以后， 转换自己的状态为follower，并且设置心跳超时，只要leader节点在心跳超时时间前发送了心跳过来，则保持这一个term的角色状态。集群选举完成
当follower在心跳超时时间还没收到心跳的时候， follower会转换成candidate, 重新发起上面的选举步骤，并且在自己的term内收到大多数节点的响应后成为这个term的主节点。
3.3 日志同步
当一个节点当选为主节点后， 这个集群内所有的变动都需要同步到别的节点上面，流程如下
- 客户端向主节点发送了一个写请求
- 主节点收到请求以后， 在下一次心跳中带上这个请求信息，告诉其他的节点
- 其他节点收到了请求以后响应给主节点是否执行
- 当主节点收到超半数节点的响应执行后，返回结果给客户端，并在下一次心跳中，将这个动作commit
四. Paxos协议
4.1 基础名词
Paxos中一共有三种角色
Proposer ：提议者，可以执行写操作，多个
Acceptor ：接收者，负责提议投票，接受提议，多个
Leaner ：学习者，负责集群的数据备份，不影响一致性，多个
4.2 运行原理
集群中节点启动的时候便确定角色， 不需要想zab和raf那样进行选举，应为所有的proposer都是主节点， 都可以发起提议。
4.2.1 数据一致性流程
- prepare阶段：客户端发过来的请求， proposer将请求转为提议发给acceptor，acceptor对提议序号进行校验，并且返回promise给proposer，不在接受比这个提议序号更小的提议。
- accept阶段：proposer接受到了半数以上的acceptor的promise以后，发起propose请求，acceptor对propose请求进行处理
- learn阶段：proposer收到了多数的acceptor响应以后， 形成决议，发送给所有的learner进行备份。
第一阶段a：prepare（请求）
proposer发起一个提议给Acceptor，编号为N，不包含内容
第一阶段b：promise（响应）
如果N大于Acceptor的此前接受的提议编号则接受，否则拒绝
第二阶段a：Accept（请求）
达到多数节点的promise， proposer发起accept请求，包含编号和内容
第二阶段b：Accepted（响应）
Acceptor在此期间没有接受到比这个更大的提议， 则接受，否则拒绝。
总结：
Paxos由于支持多个proposer进行提议，并且需要半数以上节点accept才行成功，多个proposer之间的提议可能会出现死锁。