数据一致性算法

数据一致性算法？分类？

确保多个节点之间的数据一致的机制或协议。

ZAB协议：Zookeeper中使用，通过选举一个leader来协调多个follower之间的数据更新。
2PC协议：通过预提交和提交两个阶段来保证一致性
3PC协议：在2PC协议的基础上增加超时机制和准备阶段的“可以提交”状态
Gossip协议：基于随机化，通过节点之间的随机通讯来传播数据和状态信息

Paxos算法角色？工作流程？缺点？优化？

基于消息传递

节点能同时充当不同角色
Proposer提议者：提出Proposal提案=编号（唯一，递增）+value，表示为[M,V]
Accecptor接受者：投票提案，并接受达成共识的提案
Learner学习者：被告知投票的结果，接受达成共识的提案。

Basic Paxos算法（单提议者）流程
准备阶段Prepare Phase
提议者生成编号N（大于其先前提案的编号）的提案，向超过半数的（子集）接受者发送包含提案的prepare请求，接受者Accecptor会给与提议者：
两个承诺：忽略提案号小于或等于N的Prepare请求；忽略提案号小于N的Accept请求
一个应答：回复已经接受的最大提案号的提案的提案号Nmax和值Nvalue，如果值没有接受提案则返回空值
接受阶段Accept Phase
提议者收到半数以上的接受者对于它发出的编号为N的prepare请求的响应，然后给提案设置收到的响应中编号最大的提案的值value，如果响应中不包含任何提案则随机。提议者会向超过半数的（子集）接受者发出已经设置值编号为N的Accept请求
如果N大于接受者之前返回承诺则接受者接受并向提议者和所有学习者发送Accepted消息，否则忽略
当多个提议者发送冲突的Prepare请求，或者提议者没有接收到超过半数承诺或者Accepted消息，都会使提议者发起编号更大的提案;

有多个提议者互相竞争（即多个提案编号不断增大）时可能导致提案失败并反复重试，效率低下
Multi-Paxos算法在选出一个Leader领导者作为唯一的提议者解决

Raft算法角色？工作流程？

节点只能处于三种状态中的一种
Leader领导者：处理客户端请求并将数据复制到所有节点，管理集群状态。与Follower保持heartBeat
Follower跟随者：响应Leader日志同步请求、Candidate请求，把Client请求到Follower的事务转发给Leader
Candidate候选人：发起选举投票

工作流程分为
领导选举Leader election
每轮选举是一个Term任期（递增）只产生一个Leader，选举失败则没有Leader。节点的Term正常时一致
Term递增，开始新任期选举条件
启动时
任期内没有收到足够的投票选举出Leader
Leader当选后出现异常，然后其他Follower转为Candidate
Leader或Candidate发现Term比Follower小，将转为Follower
Follower的Term比别的Term小，更新Term保持一致

启动时所有节点状态为Follower，Term为1，都设置了随机的超时时间150-300ms。其中一个Follower的超时后没有收到Leader的hearbeat转换为Candidate发起Leader选举向其他节点发起Leader Request Vote请求。Term变2，当某节点收到的请求中Term比当前Term小时则拒绝。如果Candidate收到n/2+1个节点（过半数）的投票则转换为Leader开启任期Term并向其他节点发送heartBeat。避免其他节点认为没有Leader发起选举

分裂选举：一个任期内节点只能投票一次，所以多个Candidate会出现收到的投票数都不过半问题，但定时器的时间都是随机的，相同时间概率小，所以不会存在多次多个Candidate同时发起投票的问题

日志复制Log Replication：Leader日志被复制到大多数节点后变为committed状态，应用到状态机并响应客户端。如果有异常会重试直到日志都复制到所有节点（日志连续，不能有失败引起的空洞）。每个日志条目中包含可执行的指令、任期号、位置index

日志特性：
两个日志条目的index和term相同则指令相同
不同的日志中有两个日志条目index和term相同，则之前的所有日志都相同

安全性Safety：保证每个节点都执行相同序列的安全机制，Leader一定包含前几个任期committed Log的机制（当某个Follower在当前Leader commit Log时变得不可用，稍后可能被选举为Leader，可能会用新Log覆盖旧committed Log导致节点执行不同序列）当请求投票的该Candidate的Term较大或Term相同Index更大则投票，否则拒绝该请求，保证Leader日志完整性Leader Completeness