5 The Raft consensus algorithm

Raft实现一致性：首先选举一个leader，leader完全管理log的同步。leader从client接收log entries，复制给其他servers，并通知servers状态机何时执行log entries是安全的。一个leader的好处：简化了同步日志的管理，leader不用咨询其他servers就能决定新的entries放在log的哪里，从leader到其他servers的数据流向简单。一个leader失效或者和其他servers失联，则新的leader会被选举。

Raft将一致性问题分解为三个相对独立的自问题：

• Leader election: 当一个存在的leader失效后，一个新的leader必须被选出。
• Log replication: leader必须从clients接收log entries，并复制到集群，强制其他servers的logs保持一致。
• Safety: 关键是状态机的安全。如果任何server的状态机执行了一个log entry，那么其他server不可能在相同的log index处执行不同的命令。

Raft一致性算法总结（不包含membership changes和log compaction）

• State
  • 所有servers的持久化state（响应RPCs前持久化更新）
    • currentTerm: server的最新term（初始化为0，单调递增）
    • votedFor: 在当前term收到vote的candidateId（没有vote为null）
    • log[]: log entries；每个entry包含状态机执行的命令，leader收到这个entry的term
  • 所有servers的易失state
    • commitIndex: 已知被committed的最高log entry的index（初始化为0，单调递增）
    • lastApplied: 状态机执行的最高的log entry的index
  • leaders的易失state（election后重新初始化）
    • nextIndex[]: 对于每个server，下一条发给server[i]的log entry的index。（初始化为leader最后一个log的index+1）
    • matchIndex[]: 对于每个server，已知被复制到server[i]上的最高log entry的index。
• RequestVote RPC（candidate调用收集votes）
  • Arguments
    • term: candidate的term
    • candidate Id: 请求vote的candidate
    • lastLogIndex: candidate的最后一个log entry的index
    • lastLogTerm: candidate的最后一个log entry的term
  • Results
    • term: currentTerm，candidate自我更新
    • voteGranted: true代表candidate收到vote
  • Receiver implementation
    • 如果term < currentTerm，响应false
    • 如果votedFor是null或者candidateId，candidate的log至少和被请求者一样新，则vote。
• AppendEntries RPC（leader调用复制log entries或者心跳机制）
  • Arguments
    • term: leader的term
    • leaderId: follower可以重定向到clients
    • prevLogIndex: 新entry之前的log entry
    • prevLogTerm: preLogIndex entry的term
    • entries[]: 存储的log entries。（空代表心跳，为了效率可能发送多个）
    • leaderCommit: leader的commitIndex
  • Results
    • term: currentTerm，leader自我更新
    • success: 如果follower含有匹配prevLog的entry则为true
  • Receiver implementation
    • 如果term < currentTerm则响应true
    • 如果log不包含匹配prevLog这样的entry，响应false
    • 如果存在的entry和新的entry冲突，删除存在的entry及之后的entry
    • 追加log中没有的新entries。
    • 如果leaderCommit > commitIndex，commitIndex = min{leaderCommit, index of last new entry}
• Rules for Servers
  • All Servers
    • 如果commitIndex > lastApplied：增加lastApplied，状态机执行log[lastApplied]。
    • 如果RPC请求或者响应中有T > currentTerm，设置currentTerm = T，转为follower
  • Followers
    • 响应candidates和leaders发送的RPCs请求
    • 如果election timeout没有从当前leader收到AppendEntries RPC或者candidate的请求vote，转为candidate
  • Candidates
    • 转为candidate，开始election
      • 增加currentTerm
      • vote自己
      • 重置election timer
      • 发送RequestVote RPCs给其他所有servers
    • 如果收到多数servers的votes: 转为leader
    • 如果收到新leader的AppendEntries RPC: 转为follower
    • 如果election timeout: 开始新的election
  • Leaders
    • election成功：发送空的AppendEntries RPCs（心跳）给每个server；idle期间重复发送防止election timeouts
    • 如果从client收到命令：追加entry到本地log，状态机执行之后再响应。
    • 如果一个followerlast log index >= nextIndex：发送AppendEntries RPC从nextIndex开始的log entries
      • 成功：更新nextIndex和matchIndex
      • 因为log不一致失败：减少nextIndex并重试
      • 如果存在一个N，N > commitIndex，多数matchIndex[i] >= N，并且log[N].term == currentTerm，设置commitIndex = N。