转载请注明出处：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，单调递增）

AppendEntries RPC（leader调用来复制日志，也会被用作心跳）

• 参数
  • term：leader的任期
  • leaderId：follower用来重定向客户端
  • prevLogIndex：新记录前一个记录的索引
  • prevLogTerm：prevLogIndex记录的任期
  • entries[]：需要存储的记录（心跳传空，为了提高效率可能会发送多个）
  • leaderCommit：leader的commitIndex
• 返回
  • term：currentTerm，给leader更新自己的任期
  • success：如果follower包含匹配prevLogIndex和prevLogTerm的记录返回true
• 接收者实现
  1. term < currentTerm 返回false
  2. prevLogTerm匹配但是找不到匹配prevLogIndex的记录返回false
  3. 如果已经存在的记录与其中一个新记录（index相同但是term不同）冲突，删除存在的这条记录以及后面的所有记录
  4. 添加不存在的新的记录到后面
  5. 如果leaderCommit > commitIndex，设置commitIndex = min(leaderCommit, 最新的记录索引)

RequestVote RPC（被candidate调用来收集选票）

• 参数
  • term：candidate的任期
  • candidateId：请求投票的candidate
  • lastLogIndex：candidate最新的记录索引
  • lastLogTerm：candidate最新的记录任期
• 返回
  • term：currentTerm，给candidate更新自己的任期
  • voteGranted：true表示candidate收到投票
• 接收者实现
  1. term < currentTerm 返回 false
  2. 如果votedFor是null或者candidateId，并且candidate的日志至少和自己一样新，那么就投票给他

server 需遵守的规则

• 所有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
  • 如果举定时器超时：开始新一轮选举
• leader
  • 一旦成为领导人：发送第一个AppendEntries RPC（心跳）给每一个server；空闲时间重复发送防止选举定时器超时
  • 如果接收到客户端的命令：添加记录到本地日志后面，在完全应用到状态机后再响应客户端
  • 如果最新的记录索引 >= 某个follower的nextIndex：发送AppendEntries RPC，包含了从nextIndex开始的记录
    • 如果成功：更新follower的nextIndex和matchIndex
    • 如果因为日志不一致导致的失败：自减nextIndex并重试
  • 如果存在N > commitIndex，大多数的matchIndex[i] ≥ N并且log[N].term == currentTerm：设置commitIndex = N

算法不变量

• Election Safety：每个任期足以多只有一个leader被选举出来
• Leader Append-Only：leader不会覆盖或者删除自己的日志的记录；他只会在后面添加新的记录
• Log Matching：如果两个日志包含一个相同索引和任期的记录，那么我们认为这个索引的记录以及之前的记录的内容完全一致
• Leader Completeness：如果一个记录在一个任期内被提交，那么更高任期的leader的日志都会包含这个记录
• State Machine Safety：如果一个server应用了一个给定索引的记录到状态机，不存在其他server在相同的索引位置应用不同的记录

参考： https://github.com/maemual/raft-zh_cn

标签： # 算法