raft 学习笔记
最近在学习 6.824 的分布式课程.
学习到 Raft 算法. 写篇文章作为记录.
什么是 Raft
Raft 是一个用于管理分布式副本一致性的算法, 设计的目的是为了使分布式一致性更加容易理解和实现.
算法细节
目前实现的 Raft 算法主要包含两个部分, 一个是领导者选举, 另外一个是日志复制.
领导者选举
在 Raft 算法中存在三种角色, 领导者/候选人/跟随者. 有两个时间的概念, 心跳时间(固定时间)/选举超时时间(随机时间).
在初始状态下, 所有的角色都是候选人, 等到选举超时时间到的时候发起选举投票, 如果得到半数以上的选票则变为领导者.
当角色变成领导者之后要立即对所有的成员发起心跳请求, 以巩固领导者的地位(阻止其他成员继续发起投票请求). 如果一个
成员收到了心跳请求, 则变成跟随者角色, 并作出响应.
日志复制
日志复制的的请求使伴随在心跳请求中的, 也就是说如果存在没有同步给其他成员的日志, 则在心跳的时候附带上这些日志.
对于客户端的请求, 只有复制到大多数成员的时候才认为这个请求使可提交的状态, 领导者提交之后也要通知其他成员提交.
Raft 算法实现
在 6.824 的课程当中提供了一个骨架以及一些测试用例, 目标是实现提供的接口, 最终通过所有的测试. 下面是论文中的实现方式.
所有服务器都需要存储的状态
在回复 RPCs 的响应之前保存到磁盘
- currentTerm 服务器所经历的最后一届领导人 (初始化为 0, 单调递增)
- votedFor 当前任期(上面的currentTerm)获取投票的候选人ID
- log[] log队列, 每个log实体包含一个给状态机的命令和领导人收到时的任期号(第一个索引号为1)
所有服务器变化的状态
- commitIndex 服务器知道的最高的应该提交的log实体编号(初始化为 0, 单调递增).
- lastApplied 服务器应用到状态机的log实体最高编号(初始化为0, 单调递增)
领导人经常变化的状态
赢得选举之后需要重新初始化.
- nextIndex[] 维护每个服务器下一个需要发送的log实体的编号(初始化为领导人最新的log实体编号 加 1).
- matchIndex[] 维护每个服务器得到确认的最大log实体编号.
所有成员需要实现的接口(RPC)
请求选举的 RPC
用于候选人调用获得选票
参数列表
- term 候选人的任期号
- candidateId 候选人ID
- lastLogIndex 候选人的最新log实体的编号.
- lastLogTerm 候选人的最新log实体的任期号
返回值
- term 当前任期号(currentTerm), 用于候选人更新自己
- voteGranted true 表示投票给该候选人
接受者的实现
- 如果 term < currentTerm 返回 false.
- 如果 votedFor 状态为空, 或者为请求中的 candidateId, 并且候选人的 log 至少跟接受者的日志一样新, 则投出选票 true, 否则 false.
复制 log 的 RPC
用于领导人调用来复制log实体. 也用于维持心跳.
参数列表
- term 领导人的任期号
- leaderId 领导人 ID, 用于跟随者可以转发请求
- prevLogIndex 上一个 log 的索引号.
- prevLogTerm 上一个 log 的任期号.
- entries[] 需要存储的 log (心跳的这个字段为空; 为了提高效率可能会发送多个)
- leaderCommit 领导人的 commitIndex
返回值
- term 当前任期(currentTerm), 用于领导人更新自己
- success 如果接受者存在与 prevLogIndex 和 prevLogTerm 匹配的日志则返回 true
接收者实现
- 如果 term < currentTerm 返回 false.
- 如果接收者的log队列中不包含与 prevLogIndex 和 prevLogTerm 匹配的日志, 返回 false.
- 如果接收者存在一个 log 与发来的 log prevLogIndex 匹配但是 prevLogTerm 不匹配, 则删掉这个 log 及之后所有的 log.
- 把所有不存在于 log 队列中的 log, 添加到队列中
- 如果 leaderCommit > commitIndex, 则 commitIndex = min(leaderCommit, 新发来的 log 的 index)
所有服务器都应该遵守的规则
所有服务器
- 如果 commitIndex > lastApplied, 增加 lastApplid, 应用 log[lastapplied] 到状态机中
- 如果 RPC 请求或者响应当中包含的任期 T > currentTerm, 则 currentTerm = T, 并且自己转换到跟随者状态.
跟随者
- 响应来自候选人和领导人的 RPC.
- 如果选举时间超时, 并且没有收到附加日志(或者心跳)的 RPC, 也没用收到选举请求, 则自己转变为候选人
候选人
- 当转变为候选人的时候, 开始选举:
- 增加currentTerm
- 给自己投票
- 重置选举超时计时器
- 发送 RequestVote RPC 给所有服务器
- 如果收到大多数服务器的支持选票则变为领导人
- 如果收到了一个新的领导人的附加日志的RPC 或者 心跳, 则转变为跟随者
- 如果选举超时, 开始一轮新的选举(跳转到步骤 1)
领导人
- 赢得选举之后不断发送心跳给所有的服务器, 防止超时
- 如果收到客户端命令: 首先添加到本地的日志队列, 在应用到状态机之后应答客户端.
- 如果最新的log编号>= 跟随者的 nextIndex 编号: 从 nextIndex 索引号开始发送附加log的 RPC.
- 如果成功: 更新跟随者的 nextIndex 和 matchIndex
- 如果因为 log 不匹配而失败: 减小 nextIndex 的值并且重试.
- 如果存在一个 N, 这个 N 满足: N > commitIndex, 并且 大多数跟随者的 matchIndex[i] >= N, 并且 log[N].term == currentTerm, 那么就让 commitIndex = N.
现在只实现了选举和日志复制两部分内容, 关于集群的变更等内容后续会继续实现, 课程中后续还会基于这个实现的基础上
来实现一个分布式的 KV存储.
最后附上代码地址: https://gist.github.com/icodinglife/910869da89a2e62a1b4deae994fb8d0b
由于刚刚接触 golang, 对于一些用法还不是太熟悉, 代码中有一些比较丑陋或者错误的设计和用法, 后续随着不断熟悉和深入
会慢慢重构掉. 欢迎大家讨论拍砖提意见 : )
欢迎打赏, 鼓励我坚持下去~~~ : )
