raft選舉筆記

請求投票

currentTerm: 伺服器最後一次知道的任期号

nextIndex ：對于每一個伺服器，需要發送給他的下一個日志條目的索引值（初始化為上司人最後索引值加一）

matchIndex 對于每一個伺服器，已經複制給他的日志的最高索引值

commitIndex ： 已知的最大的已經被送出的日志條目的索引值

lastApplied: 最後被應用到狀态機的日志條目索引值（初始化為 0，持續遞增)

applyIndex是狀态機中的應用的日志，應用了才能給你最新的值

接收者實作：

1. 如果term < currentTerm就傳回 false （5.1 節）
2. 如果日志在 prevLogIndex 位置處的日志條目的任期号和 prevLogTerm 不比對，則傳回 false （5.3 節）
3. 如果已經存在的日志條目和新的産生沖突（索引值相同但是任期号不同），删除這一條和之後所有的 （5.3 節）
4. 附加任何在已有的日志中不存在的條目

5. 如果leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志條目索引值中較小的一個

   ● (term)候選人的任期号< 目前機器的任期号 不投票

   ● 請求選票的候選人的 Id，候選人的日志至少和自己一樣新，那麼就投票給他

6. 候選者（任期日志）：

● 在轉變成候選人後就立即開始選舉過程還有speech

○ 自增目前的任期号（currentTerm）

○ 給自己投票

○ 重置選舉逾時計時器

○ 發送請求投票的 RPC 給其他所有伺服器

● 如果接收到大多數伺服器的選票，那麼就變成上司人

● 如果接收到來自新的上司人的附加日志（AppendEntries）RPC，則轉變成跟随者

● 如果選舉過程逾時，則再次發起一輪選舉

1. 所有伺服器：

   ● 如果commitIndex（已送出日志的索引值） > lastApplied（最後被應用到狀态機的日志條目索引值-初始化為 0，持續遞增），那麼就 lastApplied 加一，并把log[lastApplied]應用到狀态機中

   ● 如果接收到的 RPC 請求或響應中，任期号T > currentTerm，那麼就令 currentTerm 等于 T，并切換狀态為跟随者 (上司者不可能收到比上司還大的任期，候選者收到大的任期)

2. 跟随者

   ● 響應來自候選人和上司者的請求

   ● 如果在超過選舉逾時時間（一般是心跳時間的10倍）的情況之前都沒有收到上司人的心跳，或者是候選人請求投票的，就自己變成候選人

3. 上司人

   ● 一旦成為上司人：發送空的附加日志 RPC（心跳）給其他所有的伺服器；在一定的空餘時間之後不停的重複發送，以阻止跟随者逾時

   ● 如果接收到來自用戶端的請求：附加條目到本地日志中，在條目被應用到狀态機後響應用戶端（5.3 節）

   ● 如果對于一個跟随者，最後日志條目的索引值大于等于 nextIndex，那麼：發送從 nextIndex 開始的所有日志條目：--【人話：成為上司者以後，leader會和follower同步日志，不成功，就把目前follower的nextIndex-1，然後重試--leader會維護每個follower的nextIndex數組，類似于出現沖突，leader覆寫follower日志】

   ○ 如果成功：更新相應跟随者的 nextIndex 和 matchIndex

   ○ 如果因為日志不一緻而失敗，減少 nextIndex 重試

   ● 如果存在一個滿足N > commitIndex的 N，并且大多數的matchIndex[i] ≥ N成立，并且log[N].term == currentTerm成立，那麼令 commitIndex 等于這個 N （5.3 和 5.4 節）【人話： 也就是半數以上的follower的CommitIndex >=N, 且對應的日志記錄還是目前term送出的，說明目前leader需要更新commitIndex】

apache ratis 在選舉的時候做了兩個優化 ： PreVote（預選投票）和優先級選舉-

1. 預選投票為保證在網絡分區情況下，不會出現經常性的選舉。在正式的選舉前，先進行一輪PreVote選舉，隻有通過了PreVote選舉，才會增加Term進行正式的選舉。
2. 優先級選舉為防止出現多個Candidate候選者瓜分選票，設定每個節點的優先級，優先級高的會讓優先級低的候選者成為跟随者。

（SOFAJRaft - 優先級選舉）并維護優先級最大值，如果優先級高的節點當機，（上一輪選舉逾時）進行對最大值衰減，防止選不出上司者。

Jepsen模拟網絡分區，程序崩潰、CPU 超載，檢測各種分布式系統在故障下是否仍然滿足所預期的一緻性

快照機制：（需要異步處理）

30分鐘内有raft log送出時，才會進行snapshot

應用就算崩潰重新開機，那麼它首先也會讀取 snapshot 中的資料10，再去應用（狀态機）2條i++的 raft log，最終資料也是12

leader:

1. 如何确認 leader 在處理這次 read 的時候一定是 leader 呢?

readIndex read

1. 将目前自己的 commit index 記錄到一個 local 變量 ReadIndex 裡面。
2. 向其他節點發起一次 heartbeat，如果大多數節點傳回了對應的 heartbeat response，那麼 leader 就能夠确定現在自己仍然是 leader。
3. Leader 等待自己的狀态機執行，直到 apply index 超過了 ReadIndex，這樣就能夠安全的提供 linearizable read 了。
4. Leader 執行 read 請求，将結果傳回給 client。

● 走正常的： follow -> leader-> commit index -> 檢測所有，超過半數raft log

【使用者的請求過來，他請求的應該是最新的Commit的内容，但是Commit應用到stateMachine才能提供最新的内容】

● readIndex : follow -> leader-> commit index -> 檢測所有，超過半數heartbeat -> 應用狀态機讀取值

Lease（租約） Read

● Heartbeat 有一定的開銷

●  CPU 時鐘誤差（tikv 預設使用這個，認為大多數情況都是正确的。sofaraft預設使用的是readindex）

● 續約心跳有效期至（上次心跳時間+ 選舉逾時時間/ 時鐘漂移），減少心跳開銷

1. leader 選舉成功之後，首先送出一個 no-op 的 entry（日志資料），保證 leader 的 commit index 成為最新的 --【no-op entry 送出之後，才可以對外處理 ReadIndex】