分布式系统相关的理论基础
1 - raft共识算法
Raft共识算法
推荐有兴趣的小伙伴，查看
为了解决paxos的复杂性，raft算法提供了一套更易理解的算法基础
角色划分：
- Leader：领导者，接受客户端请求，并向Follower同步请求，当数据同步到大多数节点上后告诉Follower提交日志
- Follow: 接受并持久化Leader同步的数据，在Leader告之日志可以提交之后，提交
- Candidate：Leader选举过程中的临时角色，向其他节点拉选票，得到多数的晋升为leader，选举完成之后不存在这个角色
Follower只响应其他服务器的请求。如果Follower超时没有收到Leader的消息，它会成为一个Candidate并且开始一次Leader选举。收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。
选举
Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。
Raft 使用心跳（heartbeat）来检测Leader是否存活，Leader向所有Followers周期性发送heartbeat，表示自己还活着
如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举
选举的核心要点在于：
- follower一段时间没有接受到leader的心跳，认为leader挂了，变成candidate状态。 为了避免选举冲突，这个超时时间是一个150/300ms之间的随机数
- candidate，会重置计时器，先投自己一票，向其他节点拉选票
- 得到多数选票的晋升为主节点
- 当多个节点的选票相同，则选举失败；之后等待计时器超时的follower会变成candidate，将任期加一并开始新一轮的投票。
日志同步
Leader接受外部请求，并将请求作为LogEntries加入日志中，然后复制给其他的Follow节点，
- 大部分结点响应时才提交日志
- 通知所有follower结点日志已提交
- 所有follower也提交日志
脑裂问题
指在一个高可用（HA）系统中，当联系着的两个节点断开联系时，本来为一个整体的系统，分裂为两个独立节点，这时两个节点开始争抢共享资源， 结果会导致系统混乱，数据损坏。
假设A~E五个结点，B是leader。 如果发生“脑裂”，A、B成为一个子分区，C、D、E成为一个子分区。
- 此时C、D、E会发生选举，选出C作为新term的leader。这样我们在两个子分区内就有了不同term的两个leader
- 这时如果有客户端写A时, 因为B无法复制日志到大部分follower所以日志处于uncommitted未提交状态。
- 而同时另一个客户端对C的写操作却能够正确完成，因为C是新的leader，它只知道D和E。
- 当网络通信恢复，B能够发送心跳给C、D、E了，却发现有新的leader了，因为C的term值更大，所以B自动降格为follower。 然后A和B都回滚未提交的日志，并从新leader那里复制最新的日志。
2 - zab协议
Zookeeper Atomic Broadcast, ZK原子广播协议
ZAB(Zookeeper Atomic Broadcast) 协议是为分布式协调服务ZooKeeper专门设计的一种支持崩溃恢复的一致性协议，基于该协议，ZooKeeper 实现了一种 主从模式的系统架构来保持集群中各个副本之间的数据一致性。
角色划分
- Leader: 负责整个Zookeeper 集群工作机制中的核心
- 事务请求的唯一调度和处理者，保证集群事务处理的顺序性
- 集群内部各服务器的调度者
- Follower：Leader的追随者
- 处理客户端的非实物请求，转发事务请求给 Leader 服务器
- 参与事务请求 Proposal 的投票
- 参与 Leader 选举投票
- Observer：是 zookeeper 自 3.3.0 开始引入的一个角色，
- 它不参与事务请求 Proposal 的投票，
- 也不参与 Leader 选举投票
- 只提供非事务的服务（查询），通常在不影响集群事务处理能力的前提下提升集群的非事务处理能力。
消息广播
leader再接收到事务请求之后，将请求转换为事务Proposal提案，leader会为每个follower创建一个队列，将该事务proposal放入响应队列，保证事务的顺序性；
然后再在队列中按照顺序向其它节点广播该提案；
follower收到后会将其以事务的形式写入到本地日志中，并且向leader发送Ack信息确认
有一半以上的follower返回Ack信息时， leader会提交该提案并且向其它节点发送commit信息
事务有序性
队列 + 事务递增ID（ZXID）来保证提案的有序性，
ZXID:
- 高32位：纪元epoch，新选举一个leader，纪元+1
- 低32位：计数器counter，单调递增的数字
3 - 三阶段协议
在两阶段的基础上进行扩展，将第一阶段划分两部，cancommit + precommit，第三阶段则为 docommit
第一阶段 cancommit
该阶段协调者会去询问各个参与者是否能够正常执行事务，参与者根据自身情况回复一个预估值，相对于真正的执行事务，这个过程是轻量的
第二阶段 precommit
本阶段协调者会根据第一阶段的询盘结果采取相应操作，询盘结果主要有 3 种：
| 第一阶段响应 | 步骤 |
|---|---|
| 所有的参与者都返回确定 | 1.协调者向所有的事务参与者发送事务执行通知 2.参与者收到通知后执行事务但不提交 3.参与者将事务执行情况返回给客户端 |
| 一个或多个参与者返回否定信息 | 无法执行，向各个参与者发出 abort 通知，请求退出预备状态 |
| 协调者等待超时 | 同上 |
第三阶段 docommit
如果第二阶段事务未中断，那么本阶段协调者将会依据事务执行返回的结果来决定提交或回滚事务，分为 3 种情况：
| 第二阶段响应 | 步骤 |
|---|---|
| 所有的参与者都能正常执行事务 | 1.向所有参与者提交commit 2.所有参与者在收到通知之后执行 commit 操作释放资源 3.参与者向协调者反馈事务提交结果 |
| 一个或多个参与者执行事务失败 | 协调者认为事务无法成功执行 1.向所有参与者提交rollback 2.所有参与者执行rollback回滚 3.参与者向协调者反馈事务回滚结果 |
| 协调者等待超时 | 同上 |
事务提交流程图：
事务回滚流程图：
在本阶段如果因为协调者或网络问题，导致参与者迟迟不能收到来自协调者的 commit 或 rollback 请求，那么参与者将不会如两阶段提交中那样陷入阻塞，而是等待超时后继续 commit，相对于两阶段提交虽然降低了同步阻塞，但仍然无法完全避免数据的不一致
特点
- 降低了阻塞与单点故障：
- 参与者返回 CanCommit 请求的响应后，等待第二阶段指令，若等待超时/协调者宕机，则自动 abort，降低了阻塞；
- 参与者返回 PreCommit 请求的响应后，等待第三阶段指令，若等待超时/协调者宕机，则自动 commit 事务，也降低了阻塞；
- 数据不一致问题依然存在
- 比如第三阶段协调者发出了 abort 请求，然后有些参与者没有收到 abort，那么就会自动 commit，造成数据不一致