一致性算法——Paxos、Raft、ZAB
1.1 CAP理论
分布式系统的CAP理论：理论首先把分布式系统中的三个特性进行了如下归纳：
● 一致性（C）：在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本）
● 可用性（A）：在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。（对数据更新具备高可用性）
● 分区容错性（P）：以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择。
1.2 什么是一致性？
有两种一致性模型，分别是弱一致性和强一致性
1）弱一致性
（1）最终一致性
? DNS 域名系统（英文：Domain Name System，缩写：DNS）
?
在域名解析服务提供商上添加域名解析，一般都是10分钟以内之后才能通过域名访问到当前添加的网站，因为你的域名解析ip服务只在当前供应商的服务器上添加，同步到全球或者全国需要一定的时间，在其他地区或者其他DNS服务器就有可能访问不到当前网站，需要等待一段时间。
2 ）强一致性
（1）同步
（2）Paxos
（3）Raft（multi-paxos）
（4）ZAB（multi-paxos）
1.3 Paxos
1）明确问题
一致性算法的为什么会出现，因为数据不能存在单节点上，但是存在集群中有一致性的问题（网络、宕机等原因）。
但是有其他的算法比如说主从，但是主从的可用性极低，一旦有一个节点宕机则无法对外提供服务。
所以需要在保持一致性的同时尽可能的提高可用性。
2）基本思想
多数派：
每次写入都要保证写入N/2的节点，每次读保证从何大于N/2个几点中读取
多数派加顺序存取：
在其基础上，因为有集群的概念，所以还有一个系统正确性需要保证，所以顺序非常重要！
3）Basic Paxos
Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。这个算法被认为是类似算法中最有效的。
（1）角色介绍：
Client：产生议题者或者是请求发起者 ，类似于民众
Proposer ：提议者，接收民众的建议并提出议案，在冲突时有调节作用，类似于议员
Acceptor：决策者或者是投票者，国会成员或者议员等
Learner：最终决策记录者 备份，对集群一致性没有影响
（2）基本流程：
（3）全票通过的场景
（4）部分Accepter通过
但是达到了1/2以上的节点，提案通过，反之则不通过
（5）proposer宕机或者失败
当前提案不会通过，但是有其他的proposer处理（客户端需要有重试机制）
（6）活锁问题的产生
https://www.cnblogs.com/sunnyCx/p/8108366.html
timeout解决
4）Multi Paxos
（1）Basix Paxos问题
实现难
效率低（2轮RPC，来回验证，效率低）
活锁
（2）区别
Leader：唯一propser，选举产生
所有的请求都经过leader
（3）基本流程
（4）简化角色
1.4 Raft
http://thesecretlivesofdata.com/raft/
1）角色
（1）Leader
（2）Follwer
（3）Candidate
2）三个场景
（1）Leader Election
（2）Log Repliction
（3）Safety
10.5 ZAB
1.基本与Raft相同
2.叫法的区别：zab将某一个leader的周期成为epoch，而Raft称之为term
3.心跳方向为leader向follower。ZAB则相反
1）协议原理
ZAB主要包括消息广播和崩溃恢复两个过程，进一步可以分为三个阶段，分别是发现（Discovery）、同步（Synchronization）、广播（Broadcast）阶段。ZAB的每一个分布式进程会循环执行这三个阶段，称为主进程周期。
· 发现，选举产生PL(prospective leader)，PL收集Follower epoch(cepoch)，根据Follower的反馈，PL产生newepoch(每次选举产生新Leader的同时产生新epoch)。
· 同步，PL补齐相比Follower多数派缺失的状态、之后各Follower再补齐相比PL缺失的状态，PL和Follower完成状态同步后PL变为正式Leader(established leader)。
· 广播，Leader处理客户端的写操作，并将状态变更广播至Follower，Follower多数派通过之后Leader发起将状态变更落地(deliver/commit)。
在正常运行过程中，ZAB协议会一直运行于阶段三来反复进行消息广播流程，如果出现崩溃或其他原因导致Leader缺失，那么此时ZAB协议会再次进入发现阶段，选举新的Leader。
2）运行状态
每个进程都有可能处于如下三种状态之一
· LOOKING：Leader选举阶段。
· FOLLOWING：Follower服务器和Leader服务器保持同步状态。
· LEADING：Leader服务器作为主进程领导状态。