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
接收者實現
1. term < currentTerm 返回false
2. prevLogTerm匹配但是找不到匹配prevLogIndex的記錄返回false
3. 如果已經存在的記錄與其中一個新記錄（index相同但是term不同）衝突，刪除存在的這條記錄以及後面的所有記錄
4. 添加不存在的新的記錄到後面
5. 如果leaderCommit > commitIndex，設置commitIndex = min(leaderCommit, 最新的記錄索引)

參數
- term：candidate的任期
- candidateId：請求投票的candidate
- lastLogIndex：candidate最新的記錄索引
- lastLogTerm：candidate最新的記錄任期
返回
- term：currentTerm，給candidate更新自己的任期
- voteGranted：true表示candidate收到投票
接收者實現
1. term < currentTerm 返回 false
2. 如果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
- 如果舉定時器超時：開始新一輪選舉
leader
- 一旦成為領導人：發送第一個AppendEntries RPC（心跳）給每一個server；空閑時間重複發送防止選舉定時器超時
- 如果接收到客戶端的命令：添加記錄到本地日誌後面，在完全應用到狀態機後再響應客戶端
- 如果最新的記錄索引 >= 某個follower的nextIndex：發送AppendEntries RPC，包含了從nextIndex開始的記錄
  - 如果成功：更新follower的nextIndex和matchIndex
  - 如果因為日誌不一致導致的失敗：自減nextIndex並重試
- 如果存在N > commitIndex，大多數的matchIndex[i] ≥ N並且log[N].term == currentTerm：設置commitIndex = N