CAP
C(一致性):所有节点的请求结果都是一致的
A(可用性):所有请求都会成功,不存在服务响应超时或报错等
P(分区容错性):网络分区后依然可以正常使用
Raft = CP
算法分析
- 既然是一致性算法就必然会有多节点,多节点同时存储某些数据会有一致或不一致,客户端的常常需求是得到一个强一致的结果,而不是最终一致
- 多节点如果同时对外提供服务,有通信成本前提下,无法实现更新完全同步,所以单节点对外会更容易实现强一致
- 一般都会使用主从模型“一主多从”,所有请求都通过leader发送给follower,follower只负责接收leader消息然后更新
- Raft最先讨论怎么才算写入成功,谁可以成为leader
基于Quorum机制的写入(过半写入)
- leader理论上和follower数据是一致的,leader收到消息后通知所有follower都写完再回复,这样会很浪费时间,而且某些节点宕机、网络延迟也会导致请求失败,Quorum就是写入过半就算成功。
- 过半写入后各个节点数据会不一致,虽然leader是最新的,读取也是读leader,但考虑到leader会宕机,这时就不满足是CAP里面的A了,要选出拥有最新数据的follower当leader,这时就要判断谁才是最新,如果没有类似版本号的概念直接覆盖就分不出数据新旧了,所以加入日志状态机模型。
日志状态机模型(日志索引):
- 通过有索引的日志实现数据的有序化,初始化索引从1开始,每次修改+1,所以保证每个节点都按顺序、逐一写入。
基于日志比较的选举
- leader选举有两种情况
- 最开始所有节点都是follower索引都是1,谁是leader都可以
- 中途leader宕机,就应该选择索引最新的节点成为leader,通过日志状态机很容易比较出来。
- 选举的规则:
- 要过半数的节点支持才能成为leader,否则可能选出多个leader即产生脑裂
- 一节点一票:一个节点投出一票即可,follower当轮投票后不再投票。
- 过半写入:过半写入在选举过程中也体现了价值,过半follower拥有最新数据,选举需要过半票数,所以参加选举的follower中一定包括有最新数据的节点,这个节点就是新leader
- 为什么推荐单数节点:写入和选举都是过半成功,以最低的3节点为例,其中一个节点宕机后剩余节点还可以正常运行,2节点当任意宕机一节点即不可用,考虑过半机制4节点容灾效果和3节点一样,以此类推3节点允许宕机1台,5节点允许宕机2台,才是经济实惠的最佳选择
Raft算法中的选举
- 除了leader、follower还有一种角色candidate(候选人),各节点任意时刻都是这三种中的一种
- 消息一共两种,leader和follower通过心跳消息的方式保持联系:
- RequestVote:请求投票,由candidate角色发出
- AppendEntries:日志复制或心跳(索引不增的情况下是心跳),由leader发出
- ※term全局时钟(任期):
- 这块可以按真实选举理解,换届就会+1,选举开始时会增加term,发送RequestVote消息时会带上新term(其实所有消息都会带),各节点接到任意消息和自己本地term比较,如果收到了更大的term说明因为leader宕机、分区恢复等原因换届了,这时自身无论是leader和candidate都会退化成follower,所以term的变动对于raft是一个大事
- term作为leader的任期号,follower一个选举term内只能投一次,必要时要做持久化避免宕机后重复投票。
- term和日志index都是最新的情况下,日志此时最新
- ※角色迁移过程:
- 系统开始时都是follower,这时还没有leader被选出来
- follower自身会有一个机制,一段时间没有收到心跳消息触发心跳超时,自身会转变成candidate并向其他follower发出投票请求
- 收到过半回复(candidate会默认投自己)后变成leader,如果一直未收到过半消息到超时后发起下次选举,如果其他candidate已经收到过半消息变成新leader,发出的心跳会让这个没选上的candidate退化成follower
- leader出现后会发出心跳,follower收到后重置心跳超时,所以一般情况下follower不会触发超时(所以心跳间隔设计上要比心跳超时短),也就不会再出现candidate
- 如果心跳超时是固定的,可能同时会出现多个candidate,大概率都会获得了未过半的票数就会进入下轮选举,所以心跳超时加一个小随机数可以有效避免这种情况例如超时3s~4s,心跳取间隔1s即可
Raft算法中的日志复制
- 操作数据和term即都是日志,在消息中一起发出
- 日志需要先追加再持久化,有两种状态
- 追加但未持久化:没接收到确认请求前都不做持久化操作
- 已持久化:被认为是有效日志,推进commitIndex
- 已持久化索引commitIndex这些日志被认为是有效日志,刚启动时为0
- leader会记录各个节点nextIndex下个需要复制的索引和matchIndex已匹配日志的索引
- nextIndex:最大log+1
- matchIndex:follower响应时会带自身的已提交index
- ※复制流程:
- leader接收客户端请求,追加日志,通知follower
- 过半follower响应成功后leader日志持久化,推进commitIndex并通知follower持久化
- 通知follower持久化、leader响应客户端,这两步同时进行没有顺序要求
- 一些异常场景:
- follower追加后leader宕机未收到持久化请求,这时超时follower未持久化数据就会清掉
- leader未收到过半消息超时就回复失败,清理未持久化数据
- follower因为各种网络原因日志会参差不齐,leader当选后会强制同步
- 细节其实还很多要考虑各种网络异常场景、分区、恢复后的日志补偿,进而有各种补救措施和相关变量,了解设计思路和容灾策略对以后写代码有帮助暂时就可以了。
网友评论