转载请注明出处:https://www.cnblogs.com/morningli/p/16745294.html
raft是一种管理复制日志的算法 , raft可以分解成三个相对独立的子问题:
- 选主(Leader election):原有的leader故障后需要选举一个新的leader 。
- 复制(Log replication): leader必须接受client发送的记录(log entries)然后复制到集群中其他节点 , 并强制要求其他节点的日志和自己保持一致 。
- 安全(Safety):raft安全的关键是状态机安全:如果存在server将一个特定的记录应用到状态机中 , 不存在另外一个server在相同的日志索引上应用的是不同的命令 。
- 所有server上的持久性状态(在回应PRC之前更新到稳定存储(stable storage))
- currentTerm:已知的最新的任期(term)(初始化为0,单调递增)
- votedFor:当前任期内接受投票的candidateId(如果没有为null)
- log[]:记录(log entries);每个记录包含应用到状态机的命令以及leader接收该记录时的任期
- 所有server上的易变的状态
- commitIndex:已知已经提交的最高的记录索引(初始化为0 , 单调递增)
- lastApplied:已经应用到状态机的最高的记录索引(初始化为0,单调递增)
- leader上的易变的状态(选举后重新初始化)
- nextIndex[]:对于每个server,需要发送到这个server的下一条记录的索引(初始化为leader的最新的记录索引+1)
- matchIndex[]:对于每个server,已知已经复制到这个server的最高的记录索引(初始化为0,单调递增)
- 参数
- term:leader的任期
- leaderId:follower用来重定向客户端
- prevLogIndex:新记录前一个记录的索引
- prevLogTerm:prevLogIndex记录的任期
- entries[]:需要存储的记录(心跳传空,为了提高效率可能会发送多个)
- leaderCommit:leader的commitIndex
- 返回
- term:currentTerm,给leader更新自己的任期
- success:如果follower包含匹配prevLogIndex和prevLogTerm的记录返回true
- 接收者实现
- term < currentTerm 返回false
- prevLogTerm匹配但是找不到匹配prevLogIndex的记录返回false
- 如果已经存在的记录与其中一个新记录(index相同但是term不同)冲突,删除存在的这条记录以及后面的所有记录
- 添加不存在的新的记录到后面
- 如果leaderCommit > commitIndex,设置commitIndex = min(leaderCommit, 最新的记录索引)
- 参数
- term:candidate的任期
- candidateId:请求投票的candidate
- lastLogIndex:candidate最新的记录索引
- lastLogTerm:candidate最新的记录任期
- 返回
- term:currentTerm , 给candidate更新自己的任期
- voteGranted:true表示candidate收到投票
- 接收者实现
- term < currentTerm 返回 false
- 如果votedFor是null或者candidateId,并且candidate的日志至少和自己一样新,那么就投票给他
- 所有server
- 如果commitIndex > lastApplied:lastApplied自增,将log[lastApplied]应用到状态机中
- 如果RPC请求或者返回包含term T > currentTerm: 设置currentTerm = T,并切换为follower
- follower
- 响应candidate和leader的RPC
- 如果选举定时器超时没有收到当前leader的AppendEntries RPC或者没有向candidate投票:转换为candidate
- candidate
- 在转变成candidate后就立即开始选举过程
- 自增currentTerm
- 投票给自己
- 重置选举定时器
- 发送RequestVote RPC给所有其他server
- 如果接收到大多数server的投票:成为leader
- 如果接收到新leader发出的AppendEntries RPC:成为follower
- 如果举定时器超时:开始新一轮选举
- 在转变成candidate后就立即开始选举过程
- leader
- 一旦成为领导人:发送第一个AppendEntries RPC(心跳)给每一个server;空闲时间重复发送防止选举定时器超时
- 如果接收到客户端的命令:添加记录到本地日志后面 , 在完全应用到状态机后再响应客户端
- 如果最新的记录索引 >= 某个follower的nextIndex:发送AppendEntries RPC,包含了从nextIndex开始的记录
- 如果成功:更新follower的nextIndex和matchIndex
- 如果因为日志不一致导致的失败:自减nextIndex并重试
- 如果存在N > commitIndex , 大多数的matchIndex[i] ≥ N并且log[N].term == currentTerm:设置commitIndex = N
推荐阅读
- .NET源码学习 [算法2-数组与字符串的查找与匹配]
- Javascript 手写 LRU 算法
- 8折怎么算的 8折怎么算
- 除法导数公式是什么 导数的除法运算法则
- 24点算法步骤
- 购置税怎么算 购置税怎么算2021新算法的汽车
- 房贷月供的最简单算法是什么
- 遗传算法的基本原理
- 算盘乘法怎么算图解 算盘乘法怎么算
- 征地补偿怎么算