第 2 部分 — 日志複制
介紹
Raft 是一種共識算法，旨在以分布式方式編排副本。Raft 在設計時考慮了可了解性，隻有幾個活動部件并且易于實施。在上一篇文章中，我講了 Raft 的基礎知識，并解釋了上司者選舉機制。在這篇文章中，我們将關注另一個重要問題——日志複制。
基礎知識
Raft 本質上是一堆複制的狀态機。每當上司節點收到請求時，都會将其附加到日志中以確定持久性。相同的日志被複制到多台機器上以實作備援。
圖 0. Raft 日志，作者圖
例如，在圖 1 中，目前上司者的日志中有四個條目。關注者 1 完全同步，但關注者 2 缺少最新條目。如果你不明白圖0中的Term是什麼，可以看看我之前的文章。
用于日志複制的 RPC
為便于了解而設計，Raft 僅使用兩個 RPC 調用進行所有通信：
AppendEntry：這個RPC由leader發起，攜帶最新收到的指令。它還用作心跳消息。當追随者收到此消息時，選舉計時器将重置。AppendEntry消息是這樣的結構（我在這裡使用 Golang）
type AppendEntryArgs struct {
Term int // current term of the leader, very IMPORTANT
LeaderId int // id of the leader, 0 to N-1 where N = total servers
Entries []Entry // new data to sync
PrevLogIndex int // important metadata for log correctness
PrevLogTerm int // important metadata for log correctness
LeaderCommit int // what index have been received by the majority
}
type AppendEntryReply struct {
Term int // current term of the receiving node
Success bool // AppendEntry declined or accepted
ConflictIndex int // if declined, specifying the conflicting index
ConflictTerm int // if declined, specifying the conflicting term
} 如果您不了解每個字段的含義也沒關系。我們将一一檢查。
RequestVote：這個RPC用于leader選舉，在上一篇文章中有介紹。我将跳過它，因為我們隻關心日志複制。
日志複制詳細資訊
讓我們從普通日志複制算法開始。每當上司者收到請求時，它會将日志條目轉發給所有追随者并等待大多數人确認。
問題 1：日志排序
香草算法會在追随者到達後立即向他們發送消息。為此，它隻需要消息中的兩個字段—— leaderID和Entry。一個主要問題是由于潛在的消息延遲而無法保留日志順序。考慮圖 1 中的場景。
圖 1. 日志排序問題，作者圖
Raft 使用兩個額外的字段來確定日志的完整性——PrevLogIndex和PrevLogTerm。當一個新條目發出時，leader 也會發出之前條目的索引和任期号。接收方在将新請求附加到其本地日志之前確定其最新條目具有相同的索引和任期。
圖 2.附加記賬的AppendEntry，作者圖
有了這兩個額外的參數，我們可以實作一些很棒的東西：
- 給定日志索引，如果來自兩個日志（在兩台不同機器上）的條目共享相同的術語，則它們是相同的
- 如果不同日志中的兩個條目具有相同的索引和任期，則所有前面的條目都是相同的
第一個性質很容易證明。假設索賠是錯誤的。如果存在兩個具有相同任期的不同條目，則其中一個必須比另一個更晚被上司者接收。由于日志是僅附加的，是以其中一個條目将具有更大的PrevLogIndex。但是，如果它們出現在兩個不同日志的相同索引中，則它們必須具有相同的PrevLogIndex。（否則接收方拒絕） 沖突！！
第二個主張可以通過歸納證明：
圖 3. 聲明 2 的歸納證明，作者圖
這兩個保證共同構成了 Raft 的日志比對特性。
問題 2：具有沖突條目的關注者
如果 leader 日志是叢集中唯一的權限，它将覆寫 follower 的任何沖突。是否有可能丢失一些日志條目？考慮以下情況：
圖 4. 日志沖突，作者圖
在深入探讨這個問題之前，我想說服您上述情況确實會發生。日志在索引 2 之前同步。從那裡開始，建立這些日志可能會發生以下情況：
1) 節點 2 成為上司者（從自己投票，1 和 0）任期 22) 節點 2 收到來自用戶端的請求，但未能與其他節點同步
3) 節點 0 成為上司者（來自 1 和它自己的投票），任期為 3
4) 節點 0 收到來自用戶端的請求。但未能同步 現在，如果節點 0 重新與節點 2 聯系，它将嘗試複制其日志，如圖 5 所示
圖 5. 覆寫沖突，作者圖
如您所見，綠色條目确實被丢棄了。按照目前的設計，這個問題是不可避免的。然而，這裡的一個關鍵觀察是綠色條目沒有在大多數（至少兩個節點）上複制。如果是，它将永遠不會被丢棄，原因如下：
- 如果一個條目在大多數情況下被複制，則至少有 N/2 + 1 個節點擁有它
- 對于沒有進入選舉的節點，它需要其他節點的N/2票（候選人總是為自己投票）
- 由于候選人沒有條目，是以具有條目的 N/2 + 1 個節點不會投票給它（選舉限制在第 1 部分中解釋）
- It won't get enough votes to win the election
這就是 Raft 的第二個關鍵特性——日志完整性屬性。如果一個條目在 majority 上被複制，它将始終出現在未來的上司者日志中，無論它可能是哪個節點。如果沒有在大多數人身上複制，則如果上司層發生變化，條目可能會被删除。
對于日志完整性屬性，重要的是不要在大多數人收到之前确認用戶端請求。
問題 3：何時送出？
最後，我們到了最後一個問題——什麼時候送出條目？首先什麼是commit，為什麼要commit？Raft 是一種低級共識算法，供上層應用程式使用，如鍵值存儲（例如 ZooKeeper）。當一個條目被 Raft 安全地複制時，我們要確定用戶端可以通過應用程式看到它。是以，Raft 需要決定何時告訴上層應用程式一個條目已準備好使用（一個部分複制的條目，因為上司者日志中的最後一個條目不應該是可見的！）。
圖 6. 送出，作者圖
到目前為止，我們的香草算法沒有攜帶任何關于送出索引的資訊。因為資料流是單向的，從上司者流向追随者，是以節點不知道一個條目是否在大多數節點上被複制。
為了解決這個問題，我們可以在AppendEntry消息中添加另一個字段，稱為LeaderCommit。如果大多數接收到一個條目，上司者會增加送出索引。下面是跟蹤上司節點使用的送出索引的實際代碼。
for n := rf.getLastIndex(); n >= rf.commitIndex; n-- {
// start from the latest entry
count := 1
if rf.log[n].Term == rf.currentTerm {
// leader only cares about entries of its term
// entries with smaller terms are commited automatically when higher terms are
// committed
for i := 0; i < len(rf.peers); i++ {
if rf.peer[i].hasEntry(n) {
count++
}
}
}
if count > len(rf.peers) / 2 {
rf.commitIndex = n
// no need to go further back, for reasons stated in line 7 and 8
break
}
} 上司者如何跟蹤送出索引
概括
在這篇文章中，我們從普通的日志複制算法（廣播條目，沒有任何額外的簿記）開始，并通過考慮各種極端情況将其發展為成熟的版本。日志複制中最重要的 RPC 是AppendEntry RPC，它使用具有四個字段的結構：
- Term：對于日志複制和上司者選舉非常重要
- LeaderId : 顯示候選人的身份。
- 條目：上司者希望複制的條目清單。
- PrevLogIndex ：在Entries[0]之前的日志條目的索引。用于確定日志完整性和日志比對屬性
- PrevLogTerm ：在Entries[0]之前的日志條目的任期。用于確定日志完整性和日志比對屬性
- LeaderCommit：對上層應用很重要。隻有已送出的條目才能應用于應用程式并且對用戶端可見。