Part 06：Raft論文翻譯-《CONSENSUS BRIDGING THEORY AND PRACTICE》（基礎(chǔ)Raft-Log副本機制）
3.5 Log Replication（日志副本）
一旦選出了一個Leader，它就開始為客戶的請求提供服務(wù)。每個客戶端請求都包含一個要由已復(fù)制的狀態(tài)機執(zhí)行的命令。引導(dǎo)將命令作為新的log entry附加到日志中，然后與其他服務(wù)器并行發(fā)布AppendEntries rpc消息/請求以復(fù)制該log entry。當(dāng)log entry被安全復(fù)制后（如下所述，也就是大多數(shù)的Follower已經(jīng)復(fù)制了這個log entry，這是這個log entry已經(jīng)處于commited的狀態(tài)了），Leader就在本地的狀態(tài)機上apply這個log entry然后回復(fù)客戶端執(zhí)行結(jié)果。如果Follower崩潰或運行緩慢，或者網(wǎng)絡(luò)數(shù)據(jù)包丟失，Leader將重新嘗試AppendEntries RPC（即使在它響應(yīng)了客戶端之后），直到所有Follower最終存儲所有l(wèi)og entry。（這里有幾個問題，如果Leader apply這個log entry失敗怎么辦？它怎么回復(fù)客戶端？然后就是這個apply失敗的log entry怎么處理？） （理論上，已經(jīng)commit的log entry最終一定會被apply，但是Leader是等確認(rèn)apply成功后返回？還是apply失敗一次后就回復(fù)客戶端？如果是等待apply成功的再回復(fù)的話，是不是響應(yīng)時間過長？如果失敗就回復(fù)失敗，那么這個已經(jīng)commit的log entry就需要撤銷，但是Leadr應(yīng)該不會刪除自己的log entry的，沒記錯的話，而且這相當(dāng)于回滾，會增加算法復(fù)雜度。個人估計還是第一種策略可能性大，看看后面的文章內(nèi)容有沒有這塊的描述）
Log的組織方式如圖3.5所示。當(dāng)Leader收到一個客戶端的command時，Leader將在相應(yīng)的log entry里存儲這個command和對應(yīng)的term。log entry中的term用于檢測log之間的不一致，并確保圖3.2中的一些屬性。每個log entry也有一個整數(shù)索引index，標(biāo)識其在日志中的位置。
Leader判斷何時在狀態(tài)機apply這個log entry是安全的（這里安全的意思就是這個log entry已經(jīng)被commit，而某個log entry是否被commit的是通過其被復(fù)制的狀態(tài)來決定的，即如果集群中超過半數(shù)的服務(wù)器在相應(yīng)的位置復(fù)制了這個log entry，那么這個log entry就處于了“已提交狀態(tài)”（commited），這時候，Leader在其狀態(tài)機上apply這個log entry就是安全的）。Raft保證已提交的log entry是持久化存儲的，一旦某個log entry被commit了，那么在這個log entry之前的所有l(wèi)og entry都將處于commited狀態(tài)，包括前任Leader創(chuàng)建的log entry。第3.6節(jié)討論了在Leader變更后應(yīng)用此規(guī)則時的一些微妙之處，它也表明了該承諾的定義是安全的。Leader將跟蹤它知道要commit的最高的log entry的index，并在未來的AppendEntries RPC（包括心跳）中包括該index，以便其他服務(wù)器最終發(fā)現(xiàn)。一旦Follower得知某個log entry已經(jīng)被commit，F(xiàn)ollower將該log entry apply于其本地狀態(tài)機（按日志順序）。（這里一個Follower如何指導(dǎo)現(xiàn)在那個log entry被commit了？Leader知道哪個log entry需要commit，所以也知道哪些log entry已經(jīng)被commit了，如前面說的，Leader在AppendEntries RPC中會攜帶需要Follower復(fù)制的log entry的index，這個RPC過程中，Leader會和Follower溝通以確定Follower中合法的已經(jīng)commit的最新的log entry的index。這就保證了Follower確定自己已經(jīng)commit的log entry，那么這個log entry以及之前的log entry都可以被apply至Follower的狀態(tài)機了。但是Follower怎么知道從那個log entry的index開始apply呢？前面說到的，每個服務(wù)器會保存本地信息有一個lastApplied變量，這個變量就存儲了這個服務(wù)器已經(jīng)apply的最新的log entry的index，這樣起始位置都確定了，F(xiàn)ollower可以將起始及之間的log entry apply到自己的狀態(tài)機了。）
我們設(shè)計了Raft的日志機制來保持不同服務(wù)器上的日志之間的高度一致性。這不僅簡化了系統(tǒng)的行為，使其更可預(yù)測，而且它是確保安全的一個重要組成部分。Raft維護了以下屬性，它們共同構(gòu)成了圖3.2中的日志匹配屬性：
（1）如果兩個服務(wù)器上的兩個log entry具有相同的term和log entry index，那么這兩個log entry里面存儲的command是一樣的；
（2）如果兩個服務(wù)器上的兩個log entry具有相同的term和log entry index，那么這兩個log entry之前的所有l(wèi)og entry一定是一樣的。
第一個屬性，因為在某個term內(nèi)Leader每次只會產(chǎn)生一個log entry，而且log entry不會在log中改變位置。
第二個屬性，由AppendEntries RPC的溝通機制來保證。
當(dāng)發(fā)送AppendEntries RPC時，Leader將在RPC消息中攜帶需要同步的log entry（也可能是一組，為了提升性能）以及這個（或這些）log entry前面那個log entry的index，如果Follower在自己的log中沒有找到這個index，那么就說明Follower的最新的日志還在這個index之前，并且Follower會拒絕這個RPC請求指導(dǎo)這個index比較成果，F(xiàn)ollower回復(fù)同意請求。Raft算法中初始狀態(tài)的log全部為空，以及后面每次AppendEntries RPC的匹配檢測保證了日志一致性。也就是說只要AppendEntries RPC收到成功的回復(fù)，那么Leader就知道這個Follower在這個index之前的log entry是與自己的是一樣的（包括這個index所在的log entry）。
在正常操作過程中，Leader和Follower的日志保持一致，因此AppendEntries RPC我一致性檢查永遠(yuǎn)不會失敗。但是，Leader崩潰可能會導(dǎo)致日志不一致（舊的Leader可能沒有完全復(fù)制其日志中的所有l(wèi)og entry）。這些不一致可能會在一系列的Leader和Follower的碰撞中發(fā)生疊加。圖3.6說明了Follower日志與新Leader日志的不同方式。Follower可能缺少Leader存在的log entry，它可能擁有Leader上沒有的log entry，或者兩者都有可能。日志中缺少和無關(guān)的條目可能跨越多個term。
在Raft中，Leader通過強迫Follower復(fù)制自己的日志來處理不一致。這意味著Follower日志中的沖突log entry將被Leader日志中的相應(yīng)的log entry所覆蓋。第3.6節(jié)將表明，如果再加上限制選舉，這一點是安全的。（這里選舉的一些限制就限制了新Leader日志的合法性，保證了算法的安全性，后面內(nèi)容會敘述這些限制。）
要使Follower的日志與自己的日志保持一致，Leader必須找到兩個日志一致的最新的那個log entry的index，刪除Follower日志中這個index之后的所有其它log entry，并在此之后將此index之后的所有l(wèi)og entry同步給給Follower。所有這些操作都是為了滿足AppendEntries RPC執(zhí)行的一致性檢查。Leader為每個Follower維護一個nextIndex，這個nextIndex就是Leader將要在下一次AppendEntries RPC中發(fā)送給Follower的log entry的index。當(dāng)某個Leader剛剛勝選成為新Leader時，Leader將每個Follower的nextIndex設(shè)置成為自己的最新的log entry后面那個log entry的index（在圖3.6中，這個nextIndex=11）。然后，Leader通過AppendEntries RPC與其它的Follower來同步這個nextIndex并更新自己的nextIndex的值。然后Leader和Follower之間就通過AppendEntries RPC同步log entry并在以后就按照這個方案繼續(xù)同步（這里就不在贅述AppendEntries RPC的邏輯過程了，前面已經(jīng)講過了）。
在Leader發(fā)現(xiàn)它和Follower的日志匹配的位置之前，Leader可以發(fā)送沒有l(wèi)og entry的AppendEntries RPC（如心跳）來節(jié)省帶寬。然后，一旦發(fā)現(xiàn)matchIndex在nextIndex之前，Leader應(yīng)該開始發(fā)送log entry。
如果需要，可以優(yōu)化協(xié)議，以減少被拒絕的AppendEntries RPC的次數(shù)。例如，當(dāng)拒絕AppendEntries RPC請求時，F(xiàn)ollower可以在回復(fù)中攜帶這個沖突的log entry的term。有了這些信息，Leader可以減少AppendEntries RPC請求，以繞過該term中的所有沖突log entry；每個有沖突的log entry的term將需要一個AppendEntries RPC，而不是每個log entry需要一個AppendEntries RPC?；蛘撸琇eader可以使用二進(jìn)制搜索方法來查找Follower日志不同的第一個log entry；這有更好的最壞情況行為。在實踐中，我們懷疑這些優(yōu)化是否必要，因為失敗很少發(fā)生，也不太可能有許多不一致的log entry。**（這是對log日志匹配的一種性能優(yōu)化手段）**
使用這種機制，Leader在通電時不需要采取任何特殊操作來恢復(fù)日志一致性。它剛剛開始正常操作，日志會隨著AppendEntries RPC的一致性檢查的失敗而自動收斂。Leader永遠(yuǎn)不會覆蓋或刪除自己日志中的log entry（圖3.2中的Leader具有“僅追加”log entry的屬性）。
此日志復(fù)制機制顯示了第2.1節(jié)中描述的理想一致屬性：只要大多數(shù)服務(wù)器啟動，Raft就可以accept、replicate和apply新log entry；在正常情況下，新log entry可以通過單輪AppendEntries RPC復(fù)制到大多數(shù)集群；一個慢的Follower不會影響性能。日志復(fù)制算法也很實用，因為AppendEntries RPC請求的大小是可管理的（Leader從來不需要在一個AppendEntries RPC請求中發(fā)送多個log entry）。其他一些共識算法被描述為通過網(wǎng)絡(luò)發(fā)送整個日志；這給實現(xiàn)者帶來了開發(fā)實際實現(xiàn)所需的優(yōu)化的負(fù)擔(dān)。
