Raft算法学习
Raft
强一致性算法
名词
复制状态机
复制状态机是通过复制日志来实现的, 按照日志中的命令的顺序来执行这些命令. 相同的状态机执行相同的日志命令, 获得相同的执行结果.
任期号 (currentTerm)
每个成员都会保存一个任期号, 称为服务器最后知道的任期号.
投票的候选人id (votedFor)
当前任期内, 投票的候选人id, 即响应投票请求(见下文)返回true时的候选人id.
已被提交的最大日志条目的索引值 (commitIndex)
每个成员都会持有已被提交的最大日志条目的索引值
被状态机执行的最⼤日志条⽬的索引值 (lastApplied)
每个成员都会持有被状态机执行的最⼤日志条⽬的索引值
请求
日志复制请求 (AppendEntries RPC)
由领导人发送给其他服务器, 也用作heartbeat
请求内容
- term 领导人的任期号
- leaderId 领导人的id
- prevLogIndex 已经被状态机执行的最大索引值, 即最新日志之前的日志的索引值.
- preLogTerm 最新日志之前的日志的领导人的任期号
- entries[] 需要被复制的日志条目
- leaderCommit 领导人提交的日志条目索引值
响应内容
- term 当前的任期号, 用于领导人更新自己的任期号
- success 目标服务器是否能够匹配prevLogIndex和preLogTerm
接受者的处理
- 如果term < currentTerm返回false, 即发送请求的领导人任期号小于服务器最后知道的任期号, 意味着领导人发生了变更.
- 如果prevLogIndex和preLogTerm不匹配, 返回false. 即发送请求的领导人的日志不是最新的,
- 如果有一条已经存在的⽇志与新的冲突（index 相同但是任期号 term不同），则删除已经存在的⽇志和它之后所有的日志
- 添加任何在已有的日志中不存在的条目
- 如果leaderCommit > commitIndex, 则更新commitIndex为leaderCommit和最新日志条目索引值中较小的一个
发起投票请求 (RequestVote RPC)
由候选人发起的, 发给集群中已知的其他成员
请求内容
- term 候选人的任期号 (在变更为领导人之前的保存的任期号的基础上加1)
- candidatedId 请求投票的候选人id
- lastLogIndex 候选人最新日志条目的索引值
- lastLogTerm 候选人最新日志条目对应的任期号
响应内容
- term 目前的任期号, 用于候选人更新自己的任期号
- voteGranted 收到选票为true
接受者的处理
- 如果term < currentTerm 返回voteGranted为false
- 如果votedFor为空, 并且lastLogIndex和lastLogTerm匹配成功, 则为该候选人投票, 返回voteGranted为true. 并更新为候选人id
安装快照请求 (InstalSnapshotRPC)
在领导人发送快照给跟随者时使用, 按顺序发送.
请求内容
- term 领导人的任期号
- leaderId 领导人id
- lastIncludedIndex 快照中包含的最后日志条目的索引值
- lastIncludedTerm 快照中包含的最后日志条目的任期号
- offset 分块在快照块中的偏移量
- data[] 快照的原始数据
- done 如果是最后一块数据则为true
响应内容
- term 目标服务器的currentTerm, 用于领导人更新自己
接受者的处理
- 如果term < currentTerm 立刻回复
- 如果是第一个分块(offset为0)则创建新的快照
- 在指定的偏移量写入数据
- 如果done未false, 则回复并继续等待之后的数据
- 保存快照文件, 丢弃所有存在的或者部分有着更新索引号的快照
- 如果现存的日志拥有相同的最后任期号和索引值, 则后面的数据继续保留并且回复
- 丢弃全部日志
- 能够使用快照来恢复状态机 (并且装载快照中的集群配置)
约束/原则
- 选举安全原则 Election Safety: 一个任期内最多只有一个领导人当选
- 领导人只增加原则 Leader Append-Only: 领导人永远不会覆盖或者删除自己的日志, 它只会增加条目
- 日志匹配原则 Log Matching: 如果两个日志在相同的索引位置上的日志条目的任期号相同, 那么我们就认为日志从头到这个索引位置之间的条目完全相同
- 领导人完全原则 Leader Completeness: 如果一个日志条目在一个给定任期内被提交, 那么这个条目一定会出现在所有任期号更大的领导人中
- 状态机安全原则 State Machine Safety: 如果一个服务器已经将给定索引位置的日志条目应用到状态机中, 则所有的其他服务器不会在该索引位置应用不同的条目
领导人选举 (Leader election)
集群成员的状态
- 领导人
- 候选人
- 追随者.
在同一时间, 成员只会属于其中的一种状态. 并且集群中只会存在一个领导人.
有领导人时: 一个领导人, n-1个追随者 无领导人时: x个候选人, n-x个追随者
约束
- 集群中最多存在一个领导人
- 追随者不会发送请求, 只会接受来自领导人的AppendEntries RPC请求, 和候选人的RequestVote RPC请求. AppendEntries RPC请求同时提供heartbeat机制
- 领导人只接受来自客户端的请求
任期
时间被划分为一个个的任期, 每一个任期的开始都是领导人的选举.
随机的选举超时时间 例如150~300毫秒, 防止无限选举失败.
日志复制
约束
日志的流向只会是从领导人到追随者. 领导人不会覆盖自己的日志.
流程
领导人接受来自客户端的请求, 把请求中的命令作为日志条目加入到自己的日志中, 然后向追随者发送AppendEnties RPC请求, 要求追随者复制这条日志条目. 追随者复制完成后会响应领导人. 所有的请求都会响应后, 领导人会将该条目应用到状态机中, 并响应客户端. 假如有追随者没有响应, 领导人会无限地重试AppendEnties RPC请求直到所有的追随者都复制了该条目.
安全性
没有包含全部日志的服务器不会赢得选举, 即某些投票请求的响应返回false.
日志压缩
把当前的系统状态写入快照(snapshot)中, 并持久化到存储中, 然后丢弃之前的全部日志.
快照中包含了最后的索引值和任期号.
增量压缩(incremental approaches)
领导人必须偶尔地发送快照给一些落后的跟随者. 运行非常缓慢或者新加入的跟随者不能与领导人保持同步, 可以通过发送快照的方式让跟随者更新到最新的状态.
