Raft分布式一致性算法

2021-05-31 本文已影响0人 Oliver_Li

这里涉及到了CAP定理，如果不了解可以看看之前的文章的注册中心部分https://www.jianshu.com/p/b31853c348b1，Redis也用到的raft，所以就放到Redis部分了。
由于服务宕机、网络等问题，不可能要求所有服务器都一致，所以超过半数N/2 +1 ，就算完成一致性的统一了。
服务在选举中的三种状态：
- Leader（一个集群最多一个，负责客户端交互，消息同步给其他节点等）、
- Follower（负责在选举时投票，平时接收Leader消息更新数据即可）、
- Candidate（Leader选举阶段时的候选者）
集群整个周期可能有两个阶段：选举阶段、正常使用阶段。

选举阶段：
- 初始化时所有节点都是Follower，一段时间后会自动变成候选者。
  候选者会往其他节点发送投票请求，其他节点会返回决定，每个节点只有一次选举机会，所以谁快就把票投给谁。
  收到n/2+1投票时就会成为leader（自己也可以推荐自己）。
正常使用阶段：
- 当leader收到修改请求时，leader会往其他节点发送同步消息，其他节点响应消息，leader更新，然后再给其他节点发送确定消息其他节点更新数据。

因为开始时所有节点都是选举人，所以需要通过超时做出差异性，避免同时申请的冲突。

选举超时：例如150~300ms（一个范围内随机选取），每个选举人都会有自己的选举超时时间，超过该时间后会转变成候选者，并发送投票请求，因为超时是范围随机的，所以最快到达超时的会先向其他选举人发送消息，其他选举人收到消息后如果没有投过票的会把票投给这个候选者，其他选举人重置超时时间，候选者收到过半请求后会成为leader，并和其他选举人保持心跳，每次心跳重置刷新选举超时，因为重置机制所以正常选举人不会轻易变成候选人。
如果leader宕机，选举超时没有被重置，第一个到选举超时的选举人会变为候选者，向其他节点发送投票信息，执行上一阶段选出leader。
PS：期间会发生一个问题，节点为复数，可能会出现票数相同的情况，这种情况会加赛一轮，因为选举超时是随机的，所以理论上这种冲突不会一直下去，一定会选出一个leader。

网络中会出现一种情况，机器被分为两组，各自内部可以通信，相互之间均不可通信，这样就产生了脑裂。
旧leader被网络分割后肯定会被动划分到其中一边，一种情况是服务较多的分区，另一种情况是服务较少的分区。
- 分到较多分区：大分区继续各干各的就得了，另一部分选举超时过后，就会有节点变成选举人开始选举，但是小分区内不可能拿到n/2+1的票数并不会选出Leader。
- 分到较少分区：大分区选出Leader所以会出现两个Leader，但小分区分发时不可能拿到n/2+1的反馈，所以能查不能更新。
网络异常情况类型很多，比如：
- 单台服务与其他服务不通。
- 整体集群被网络分成两个小集群，小集群之间不通，内部可通。
- 分成两个小集群，其中一台可通两边，其他机器都是内部可通。
现实网络情况很复杂，分支情况很多，很难全面解读，这里只是简单写写，后续会仔细看看raft论文https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf，发现有问题随时修正。