Raft算法学习

Raft

强一致性算法

名词

复制状态机

复制状态机的架构 复制状态机是通过复制日志来实现的, 按照日志中的命令的顺序来执行这些命令. 相同的状态机执行相同的日志命令, 获得相同的执行结果.

任期号 (currentTerm)

每个成员都会保存一个任期号, 称为服务器最后知道的任期号.

投票的候选人id (votedFor)

当前任期内, 投票的候选人id, 即响应投票请求(见下文)返回true时的候选人id.

已被提交的最大日志条目的索引值 (commitIndex)

每个成员都会持有已被提交的最大日志条目的索引值

被状态机执行的最⼤日志条⽬的索引值 (lastApplied)

每个成员都会持有被状态机执行的最⼤日志条⽬的索引值

请求

日志复制请求 (AppendEntries RPC)

由领导人发送给其他服务器, 也用作heartbeat

请求内容 - term 领导人的任期号 - leaderId 领导人的id - prevLogIndex 已经被状态机执行的最大索引值, 即最新日志之前的日志的索引值. - preLogTerm 最新日志之前的日志的领导人的任期号 - entries[] 需要被复制的日志条目 - leaderCommit 领导人提交的日志条目索引值

响应内容 - term 当前的任期号, 用于领导人更新自己的任期号 - success 目标服务器是否能够匹配prevLogIndex和preLogTerm

接受者的处理 1. 如果term < currentTerm返回false, 即发送请求的领导人任期号小于服务器最后知道的任期号, 意味着领导人发生了变更. 2. 如果prevLogIndex和preLogTerm不匹配, 返回false. 即发送请求的领导人的日志不是最新的, 3. 如果有一条已经存在的⽇志与新的冲突(index 相同但是任期号 term不同),则删除已经存在的⽇志和它之后所有的日志 4. 添加任何在已有的日志中不存在的条目 5. 如果leaderCommit > commitIndex, 则更新commitIndex为leaderCommit和最新日志条目索引值中较小的一个

发起投票请求 (RequestVote RPC)

由候选人发起的, 发给集群中已知的其他成员

请求内容 - term 候选人的任期号 (在变更为领导人之前的保存的任期号的基础上加1) - candidatedId 请求投票的候选人id - lastLogIndex 候选人最新日志条目的索引值 - lastLogTerm 候选人最新日志条目对应的任期号

响应内容 - term 目前的任期号, 用于候选人更新自己的任期号 - voteGranted 收到选票为true

接受者的处理 1. 如果term < currentTerm 返回voteGranted为false 2. 如果votedFor为空, 并且lastLogIndex和lastLogTerm匹配成功, 则为该候选人投票, 返回voteGranted为true. 并更新为候选人id

安装快照请求 (InstalSnapshotRPC)

在领导人发送快照给跟随者时使用, 按顺序发送.

请求内容 - term 领导人的任期号 - leaderId 领导人id - lastIncludedIndex 快照中包含的最后日志条目的索引值 - lastIncludedTerm 快照中包含的最后日志条目的任期号 - offset 分块在快照块中的偏移量 - data[] 快照的原始数据 - done 如果是最后一块数据则为true

响应内容 - term 目标服务器的currentTerm, 用于领导人更新自己

接受者的处理 1. 如果term < currentTerm 立刻回复 2. 如果是第一个分块(offset为0)则创建新的快照 3. 在指定的偏移量写入数据 4. 如果done未false, 则回复并继续等待之后的数据 5. 保存快照文件, 丢弃所有存在的或者部分有着更新索引号的快照 6. 如果现存的日志拥有相同的最后任期号和索引值, 则后面的数据继续保留并且回复 7. 丢弃全部日志 8. 能够使用快照来恢复状态机 (并且装载快照中的集群配置)

约束/原则

领导人选举 (Leader election)

集群成员的状态

状态转换

在同一时间, 成员只会属于其中的一种状态. 并且集群中只会存在一个领导人.

有领导人时: 一个领导人, n-1个追随者 无领导人时: x个候选人, n-x个追随者

约束

任期

时间流

时间被划分为一个个的任期, 每一个任期的开始都是领导人的选举.

随机的选举超时时间 例如150~300毫秒, 防止无限选举失败.

日志复制

约束

日志的流向只会是从领导人到追随者. 领导人不会覆盖自己的日志.

流程

领导人接受来自客户端的请求, 把请求中的命令作为日志条目加入到自己的日志中, 然后向追随者发送AppendEnties RPC请求, 要求追随者复制这条日志条目. 追随者复制完成后会响应领导人. 所有的请求都会响应后, 领导人会将该条目应用到状态机中, 并响应客户端. 假如有追随者没有响应, 领导人会无限地重试AppendEnties RPC请求直到所有的追随者都复制了该条目.

安全性

没有包含全部日志的服务器不会赢得选举, 即某些投票请求的响应返回false.

日志压缩

把当前的系统状态写入快照(snapshot)中, 并持久化到存储中, 然后丢弃之前的全部日志.

保存条目1-5到快照中

快照中包含了最后的索引值和任期号.

增量压缩(incremental approaches)

领导人必须偶尔地发送快照给一些落后的跟随者. 运行非常缓慢或者新加入的跟随者不能与领导人保持同步, 可以通过发送快照的方式让跟随者更新到最新的状态.

参考

Raft 一致性算法论文译文

Comments

comments powered by Disqus