CAP原则

C：一致性 A：可用性 P：分区容错性

二阶段提交

一致性协议：选出协调者来协调分布各个结点之间的调度。

1. 协调者收到请求后进入预提交事务阶段，向所有参与者发送请求,参与者执行事务，但不提交
2. 如果有部分参与者没有响应，就需要回滚事务,如果全部参与者的回复都为正常，协调者向所有的参与者发起提交事务。

三阶段提交

把二阶段提交的第一步拆分，分成了CanCommit、PreCommit和DoCommit三个步骤

1. 协调者询问参与者是否能够正常执行事务,进行网络通信的测试
2. A YES，参与者执行事务但是不提交，发送给协调者
3. B 有一个No或者超时等待则中断事务，向各个参与者发送abort中断事务

领导开会，向全部的员工发信息，有的人没有回复，领导再向员工发送，xxx不在，不开了。
复制代码

3. A 提交事务，参与者根据事务成功与否向协调者发送ack，全部收到，协调者也提交事务
4. B 2-A-B中的参与者向协调者发送abort ack，收到全部响应之后，协调者执行回滚事务

三阶段提交解决了什么问题？

同步阻塞：2PC参与者不反馈给协调者，就会同步阻塞，3PC引入了超时等待解决同步阻塞问题。
协调者挂掉：参与者长时间接收不到协调者的消息之后，就会提交事务。仍然无法解决分区问题。

Paxos算法

Paxos基于消息传递，是用来解决分布式数据一致性问题的算法。
核心原则：少数服从多数
四类角色：client（产生提案）、proposer（提案者）、acceptor（决策者）、learners（学习者）
提案：提案需要有半数的acceptor同意才能进入第二阶段，第二阶段只有半数的acceptor同意才能通过。

1. parpare阶段\

假设proposer向acceptor发起预提案，acceptor会维护一个maxN,预提案编号大于maxN才会进行响应
2. acceptor阶段
parpare阶段中通过的预提案，proposer再次向acceptor请求通过提案，accept请求（n，Value），value是提案的真正内容。
两轮半数同意可以筛选出更多提案。parpare失败，把自己的n变成maxN+1重新进行提案。

Paxos活锁问题

proposer1以id1通过了parpare阶段，proposer2以id2通过了parpare阶段，p1进入acceptor发现id1<maxN,重新以id3进入parpare，p2进入acceptor进入发现id2<maxN,重新以id4进入parpare阶段

解决方法

1. 延迟，acceptor改变maxN之后，稍微等待后再接收新的parpare请求，不让其立即改变
2. 选取主proposer进行提案parpare

ZAB协议（Fast Paxos算法）

三类角色：

• leader：处理写请求和负责发起投票
• follower：处理读请求，写请求转发给leader，负责投票
• observer：没有投票权的follower，当集群的负载很高时，不能增加follower，因为会增加f和l之间的通讯压力

Raft算法

follower等待Leader发送心跳检测。

Zookeeper选举算法

1. 更新逻辑时钟
2. 初始化投票，投给自己一票
3. 发送初始投票
4. 接收外部投票
5. 判断外部选票的term

A：外部选票的轮次大于此次，更新逻辑时钟，再次初始化投票然后PK，投出选票
B：外部选票的轮次小于此次，直接丢弃
C: 外部选票的轮次等于此次，进行PK
- 按照轮次、ZXID、SID进行变更投票
- PK完毕后进行变更，归档所有选票到revset中进行统计，如果有一个candidate收到了半数的投票则可以终止选举过程
复制代码

Raft算法

选举与故障选举过程

1. 开始的时候，每个结点等待自己的TimeOut结束，TimeOut结束后向其他结点发送选举请求。
2. 半数同意则升级为Leader，不断向子节点发送心跳检测，检测子节点是否存活，子节点也维护一个定时器，一定时间内没有收到Leader心跳检测重新开始选举，如果以前的Leader再回来由于Term小于新的Leader，成为Follower

主从复制过程

1. 主结点首先提交事务到自己的raftLog，然后向子节点请求，半数响应主结点提交事务。然后向子节点提出Append Entries。

网络分区下的主从复制

此时出现了网络分区故障

Leader2的Term更大，其完成操作后，待到网络分区故障恢复，Leader1自动降级为follower，删除RaftLog中没有提交的数据，进行同步