Raft算法
一致性算法的要求:
- 安全性,网络延迟、分区、丢包、重复和乱序等错误需要保证正确
- 可用性:集群中只需要大多数机器即可运行
- 不依赖时序保证一致性
三种状态:follower,candidate,leader
任期:逻辑时钟的作用,每一段任期从一次选举开始
-
分票可能会导致一个任期没有leader
-
用于检测一些过期的信息,比如说过期的leader(term小于candidate的term)
leader选举
什么时候选举:follower一段时间内没有收到任何消息(leader的追加日志,或candidate的投票请求),超过选举超时时间
什么情况投票:先来先服务 + candidate的日志必须和大多数服务节点的日志至少一样新
这是为了保证,成为leader的人必然拥有之前所有任期内已经被commit的日志,避免不同的状态机执行不同的指令序列
体现在代码上:使用log最后一个条目的term和idx来判断哪个是更新的日志
什么时候成为leader:获取大多数服务器节点针对同一任期号的选票
成为leader后做什么:立刻发送一轮心跳包维护自己权威,阻止发起新的选举
如果有旧leader从宕机恢复,并发送追加日志给candidate怎么办:比较两者的任期大小
如果产生分票,怎么避免:随机选举超时时间,把服务器的选举时间都分散开,对选举超时时间的基本要求为:大于 发送RPC一去一回的总时间, 小于 单个server平均故障间隔的时间
日志复制
什么时候追加日志给follower:
当leader接收到上层服务下发的命令后:将命令放到自己的log中,并行将应发送给各follower的日志条目发送给follower
体现在代码上:
在leader中维护了matchidx数组,记录每个follower现在更新到的日志下标;
nextidx数组,记录了要发送给每个follower的下个日志的下标;
prelogindex 和 prelogterm 指向 leader要发送日志的前一个日志,用以判断follower之前的日志是否与leader冲突,如果冲突则追加日志失败,follower返回Xterm,Xindex,Xlen
- Xterm = -1, Xindex = -1, Xlen = follower全部日志长度:全部日志冲突
- Xterm = 冲突log的term,Xindex = 冲突term内的第一条log的下标
帮助leader快速修改nextidx数组,定位到下一批应该追加给该follower的日志
什么时候返回结果:
当leader收到了大多数follow的追加成功回复后,leader会commit该日志,然后尝试apply该日志给上层存储服务,让上层执行并返回结果给客户端;
如果leader crash怎么办:follower太久没有收到heartbeat消息,触发选举超时,转变成candidate开始选举
如果follower crash怎么办:leader会无限重试发送追加日志给它们,直到它们重启
体现在代码上:
leader中有个专门的协程遍历matchindex数组,更新commitindex
并会在追加日志的时候附带发送commitindex,让follower更新该值;
leader和follower中都有个专门的协程,在commitindex更新时被唤醒,开始执行日志的apply
日志持久化
该部分较简单,只需在需要持久化的状态currentTerm,votedFor,log三者任一发生变化时,立刻调用persist()
保存raftstate即可
其中currentTerm保存leader的当前任期值,votedFor保存follower的投票选择,log保存节点的日志,而诸如commitindex、lastapplied、nextindex[]、matchindex[]等状态,都可以通过保存的log,在Append Entries RPC的发送和返回中逐步调整恢复,故不需要保存
日志快照
-
为了防止日志随着增长越来越大重放时间越来越长,所以使用snapshot,对一部分早期的日志进行快照
-
快照内容除了包括应用数据信息,还包括了一些元数据信息:如快照中最后一个日志包含的term以及index
-
一旦系统将快照持久化到了磁盘上,就可以删除快照最后一个日志之前的日志以及快照
-
有时候,follower的进度太慢了,leader已经把应该发给它的日志给删除了,这个时候leader必须通过installsnapshot RPC给follower发送快照
- 如果这个快照里包含了follower所没有的日志信息(也就是快照里的日志进度比follower所有的日志进度快),follower就会接收该快照,更新到自己的快照信息中
在本处实现上,我选择follower在接收installsnapshot RPC时并不直接删除快照中所包含的日志,而是在上层应用调用
CondInstallSnapshot
判断成功应用快照后,才真正进行日志的裁剪因为在实现逻辑上,只有当上层应用调用
CondInstallSnapshot
判断可以安装快照之后,raft节点上快照所包含的日志信息才真正失效
该部分较为繁琐,涉及到很多关于日志的判断和操作,由于在该部分中日志的Index0也将发生变化,故也需要重构之前的日志追加功能,包括follower日志为空时的处理、包括leader日志为空时的处理等等
我选择在节点创造后的最开始时,在日志下标为0处保存一个空日志(方便还未接收上层应用的command时,可以顺利实现leader所发送的心跳包逻辑),而在日志进行快照而裁剪后,日志下标为0处即为有效日志,此时有两种情况
- 日志不为空,该情况不影响心跳包逻辑的处理
- 日志为空,在该情况下,我选择持久化lastsnapshotIndex、lastsnapshotTerm,使用此两个变量代行心跳包逻辑处理中prevLogIndex,prevLogTerm的功能