1. 背景

raft是什麼

raft是一種共識演算法（consensus alogrithm），類似的還有paxos、zab等等，用於解決副本資料一致性問題。

raft是線性一致的嗎

raft與線性一致性並沒有必然聯絡，raft是一種

共識演算法

，可以基於這個共識演算法實現線性一致性的分散式系統，我們知道線性一致性是針對某一個物件而言的（分散式一致性總結），raft最終針對其WAL這個物件實現了一致性，raft的WAL是線性一致性的。這點可以反推出來，因為線性一致性的定義有一點是線性一致具有Locality這個特性，也就是說如果一個物件的操作歷史是線性一致性的，那麼他的每個子物件的操作歷史也必然是線性一致性的。我們知道可以透過raft實現線性一致性的分散式系統，那麼可以得出WAL這個子物件的操作歷史一定也是符合線性一致性的。

2. raft功能模組有哪些

raft設計的基礎目標就是將這個複雜的一致性問題拆解。因此raft內部其實將問題拆分成：

leader選舉

raft的leader接管所有的client請求，在叢集啟動或者leader失效的場景下需要選舉出新的leader。

log複製

raft接收client的資料，將資料複製到其他節點，當收到大部分節點的response之後返回給client。

安全性

分散式系統通常會有節點宕機，節點加入或節點撤離等變更操作，那麼在這些場景中raft需要保證日誌的一致性。

3. raft正常工作流程

正常流程中一個

raft group

啟動時，會首先選舉出一個leader，然後leader接收來自client的所有訊息，再由leader將這些訊息複製給follower，follower不主動發訊息。一個leader被選舉出來之後就對應一個任期（term），在這個任期內他會與其他

follower節點

保持心跳，這樣在無異常工作場景下（無

網路分割槽

、無宕機、無節點重啟、無網路延遲等）這個leader的任期一直持續且一致保持leader的身份不變。

4. raft的異常處理細節

就像上節描述的那樣，一個無異常的環境在真實世界裡看起來是達不到的，我們不能避免節點重啟、宕機、網路故障等等問題，但是我們依然想要在這種看似惡劣的現實環境中保持我們系統的可用性、正確性。所以需要對現實環境中的各種異常做處理。這其實也是共識演算法的職責，raft在設計的時候也將這些異常因素考慮進去了，在raft協議中其實絕大一部分是對異常場景的處理相關的描述。

所以這裡針對raft的異常場景做一些總結。

因為raft為了能夠讓演算法更容易讓大眾理解，將整個演算法做了分解，第二節已經提到了，總體分為三部分：leader election、log replicate、safety。safety主要包含了配置的一些細節，所以這裡針對這三個方面分別總結一下其異常場景下raft的處理方式。

4.1 leader election

leader election

正常流程

raft group的所有節點會在leader、follower、candidate三種身份間互相切換，在叢集初始階段節點都是follower的身份，在經過election timeout時間之後便會觸發節點身份切換為candidate，candidate所要做的工作就是自增自己的term資訊，然後向叢集中的其他節點發起投票，如果收到來自大多數節點的投票資訊後（包括自己的投票），就切換身份為leader，leader負責接收使用者請求，並將請求複製給follower，同時需要保持與follower之間的心跳。

場景1：如果是5個節點的group在初始化發起投票時，5個節點同時發起了投票，這樣選票就無法收到來自其他節點的投票了，這樣節點會再次將term加1發起投票，也很有可能會遇到相同狀況。

raft內部維持了一個election timeout時間，這個時間是一個範圍內的隨機值，所以在很大機率上每個節點選舉超時的時間是不一致的，這也基本上能解決

vote split

的問題，當然這個並不能完全解決，但這種隨機超時時間基本上可以解決vote split的問題了。

這個election timeout時間範圍肯定至少要比網路RTT要大一個數量級，比機器故障時間小一個數量級。

broadcastTime

<<

electionTimeout

<<

MTBF

。

broadcastTime也即是RTT， MTBF是一臺server平均故障時間間隔

場景2：如果當前group中的leader掛掉了，那麼這個group中的節點必須要等到election timeout才會發起新的一輪選舉，而在新的leader被選舉出來之前這個group是不能提供服務的，這樣就會造成group的可用性降低。

目前raft論文中並沒有針對這期間的可用性問題進行最佳化。極端情況下這個不可用時間是election timeout。

場景3：網路分割槽分為對稱網路分割槽與非對稱網路分割槽，三個節點A，B，C，節點A是leader，A與B，C網路分割槽，這種是對稱網路分割槽，如果A與B網路正常，與C網路分割槽，但是B與C之間網路正常，這種屬於對稱網路分割槽。

A，B，C三個節點，A是leader，B，C是follower

leader與follower出現對稱網路分割槽

這時候A聯絡不到B，C，會一直不斷的嘗試傳送心跳。

follower側在一段時間沒有接收到來自leader的心跳後，會觸發election timeout，然後自增自己的term，變更為candidate，然後向其他節點發起投票。上面說過，這個

election timeout

是一個區間內的隨機值，所以B，C會在不同時間觸發election timeout。假設B先觸發選舉，C在接收到RequestVote RPC之後，與自己當前的term和log比對，發現term和log比自己要新，就會grant這次選舉。因為節點中的配置資訊是3個節點，B接收到投票時候，符合

多數派

原則，這時候B被選成了leader，可以正常對外提供服務了。

這裡有一點：client原來是與A通訊的，但是A與其他節點網路分割槽後，就一直提供不了服務了，那麼這時候client需要有一定措施切換節點重試，也就是說client端RPC必須配置超時，並且需要具備重試其他節點的邏輯，否則會一直處於不可用狀態。

leader與follower出現非對稱網路分割槽

A，B網路正常，A與C斷連，B與C通訊正常。這時候A，B可以正常對外提供服務，C則接收不到來自leader的心跳，在election timeout時間之後，C自增term，變更為candidate，然後發起選舉。因為C與B是可以正常通訊的，這時候B發現有更高term的選舉資訊，會變更自己的tern資訊，然後回覆grant，C就可以成為新的leader。這時候再接收到來自leader A的RPC時，B會將自己的tern資訊一併傳送給leader A，leader A發現B的term更高，就會自己主動stepdown，但是這時候A與新的leader C同樣也存在了非對稱網路分割槽。然後又會迴圈上面的步驟，這就會導致叢集一致處於leader變更狀態。

follower與其他節點出現非對稱分割槽

C與A，B都網路分割槽，這時候叢集仍然能夠正常提供服務，因為大多數節點仍然是正常的，這時候C節點接收不到A發的心跳，在election timeout之後便會自增term，然後發起投票，如果網路分割槽一直不修復，C的term資訊會一直增加。

如果網路分割槽修復，C重新加到叢集中，這時候A，B會接收到C的requestVote RPC，會發現C的term資訊比自己的都大，然後A，B會stepdown，然後進入選舉狀態。這樣正常的叢集工作就被打斷了。

因此raft中推薦一種

prevote機制

來避免這種降低叢集可用性的場景。當一個節點需要發起投票之前需要先進行prevote，prevote會向其他server傳送RPC，如果大多數節點允許其選舉（對比term和log），那麼這個節點再自增term併發起選舉，否則就不自增term。

raft在leader選舉中做了一些限制，不僅僅要判斷candidate的term資訊，同時要對candidate的log的新舊做判斷，如果candidate的log不夠新（相同term的logindex較小，或者對應logindex位置term小於接收者的term）那麼就拒絕當前candidate的投票選舉。

raft的strong leader要求所有的op log都是從leader流向follower，這樣的設計簡化了日誌複製流程。

4.2 log replicate

log replicate正常流程

leader負責接收使用者請求，接收到使用者請求之後會打包傳送給叢集中的其他follower節點，然後等待這些節點的response，如果收到大多數節點的response（包括自己）之後，就將該log entry提交，並觸發statemachine提交已經commit的log。

場景1：leader never commit entry from previous term。

這是raft論文中舉的一個示例，在raft中leader只能透過多數派的方式commit當前自己任期內的entry，對於以前leader任期內的entry不能透過判斷當前的entry是否在大多數節點的raft log中來提交當前entry，但是當前leader可以透過提交自己任期內的entry的方式將前面任期的entry一併提交。

場景2：如果leader接收到來自大多數follower的appendentryRPC response，這時候leader要進行commit，如果在commit之前，leader掛掉了，這時候如果leader重啟會如何處理這個已經複製到大多數follower的entry？

A，B，C，D，E五個節點組成一個

raft叢集

，在term3的時候，在log index = 5的時候，A複製了一個log entry到B，C，然後也收到了B，C的response，在commit之前A掛掉並重啟了，那麼log index = 5這條日誌會被如何處理。

A重啟這段時間內沒有新的leader被選舉出來

A重啟後會將一些

raft meta

資訊load起來，包括

term資訊

，（後面會大概分析為什麼需要持久化這些元資訊）。A重啟後會獲取自己的raft log的lastlogindex及lastlogterm資訊，election timeout後會重新發起選舉，因為這時候的叢集中沒有leader，那麼A的日誌一定是最新的，因為在選舉的時候會比較日誌的新舊，所以新的leader只會在A，B，C三個節點中選出。如果A重新被選舉為leader，這時候A的term應該是4，這時候雖然A，B，C上logindex = 5的entry被複制到大多數節點上了，但是A並不能直接將這個entry提交，如果這時候在A的term=4內又接收到來自使用者的新請求，A會將logindex = 6的entry提交，這時候會將原來未提交的logindex = 5的log entry一併提交了。

這種就是場景4中的（e）。

A重啟這段時間有新的leader被選舉出來

新的leader肯定只能在A，B，C中選出，新的leader被選舉出之後會將原來logindex = 5的entry apply。

因為leader將log entry apply之後才會向用戶返回當前請求成功，也就是說log index = 5這個請求其實對於使用者來說並沒有成功，但是leader A在其新的任期內將這個entry apply了，那這個會不會造成使用者的資料不一致？

如果client在logindex = 5 的時候沒有收到response，而是超時，那麼client是不知道當前底層是處於什麼狀況的，成功或失敗都不清楚，所以一般client的做法是重試，那麼底層apply的業務邏輯應該需要保證冪等性，不然重試會導致資料不一致。如果重試也不成功，那麼對於client來說，底層是寫成功或失敗都是可以接受的，說明當前系統存在問題。

場景3：leader在正常工作一段時間之後重啟，假設在重啟之前raft group已經正常複製的raft log最後的log index = 10，且這10個log entry都已經applied，那麼當leader重啟後，這些applied的日誌會重新apply一遍嗎？如果業務邏輯是非冪等的，那麼重新apply豈不是違背線性一致性？

raft node在重啟時會先將沒有close的WAL load起來，會從這個沒有close的WAL中獲取其firs_log_index，braft實現中這個資訊會記錄在WAL日誌的檔名中，並會從這個open的WAL中掃描得到last_log_index。因為raft並沒有持久化

last_applied_index

這個資訊，所以無法確定當前這個fisrt_log_index對應的log entry是否已經持久化到本地儲存，所以在commit的時候還是以first_log_index作為初始apply的第一個index，那麼可能就會導致如果原來的first_log_index已經apply過了，這裡又會被再次apply，所以如果業務邏輯不是冪等性的操作，這裡的apply會造成資料違背線性一致性。

為什麼last applied index這個值不能持久化，如果持久化了，那麼是不是就能解決重啟後重放WAL log不會將已經apply的log entry再持久化一遍。但是這裡需要保證資料落盤與last applied index落盤的原子性。

場景4：raft重啟後如何識別一個log entry是不完整的？

因為每個log entry在append的時候都有固定的格式，在頭部近路當前entry的元資訊， 頭部還有checksum校驗資料，這個checksum就是為了檢驗當前entry是否是完整的依據，在重啟時會將wal檔案重新開啟，然後根據每個log entry的元資訊獲取log entry的長度，然後再計算crc進行比對，如果crc校驗錯誤則將該log丟棄。

場景5：raft的WAL是append模式，隨著執行時間增加，WAL會變得非常大

raft引入了snapshot機制，為了避免WAL日誌過大造成重啟回放需要太久，raft使用snapshot來減少WAL大小。snapshot就是儲存某一時刻WAL的最新狀態。

raft定時建立snapshot，那麼在snapshot節點之前的WAL entry就可以被刪掉了。

場景6：raft leader在會將log entry複製給follower，只要大於半數的節點回復就可以提交該entry，也就是說會有那麼一些節點的WAL有可能落後於leader，或者對於新加入的節點，其log肯定是落後於leader的，那麼這些follower如何追趕上leader並且在追趕期間還需要正常接收新的log entry嗎？

對於老的成員節點存在log 落後

老的成員在log 落後時，leader會透過每一次的AppendEntry來探測其與leader本身的log 差距，在append entry rpc中有一個next index欄位，這個欄位就是表明當前節點需要leader複製的下一個

log index

，leader會為每一個replicator節點儲存一個nextindex，然後在appendentry的時候將剩餘的entry複製給對應的replicator。

對於新新增的節點

由於新新增節點WAL為空，leader需要將自己的WAL複製給新節點，如果新的節點的加入如下場景，S4新加入叢集，S3在這個時候掛掉，那麼這個時候leader在複製新的log時，需要收到S4的回覆才能達到半數以上的要求，但是這時候S4是空的，與leader的WAL相差太多，因此沒法需要等到leader全部複製完畢之後才能提供服務，這樣就造成了叢集可用性降低的問題。

為了提高可用性，raft為新加入的節點增加了一個階段，在這個階段該節點不提供vote功能，也就是說不參與多數派決策，這個階段期間該節點只接受來自leader的log entry，這個過程稱之為catch up。

那麼什麼時候這個節點才能加入叢集，參與正常的投票決策呢？

raft論文裡也沒有給出一個明確的答案，這個時間其實是根據client所能接受的最低不可用時間來決定的。當然是越接近leader的WAL時再讓其加入決策叢集最好了。

對於新加入的節點leader還需要控制其catch up階段的時間，如果這個新節點不可用了，那麼這個節點首先是不能夠加入叢集的，另外其catch up過程也是無限迴圈的。那麼leader就需要決策是否將這個節點加入叢集。

leader將catch up分為多個round，第一個round會將leader所有的entry全部複製，第二個round會將第一個round複製期間新來的entry全部複製，第三個round重複第二個round的步驟，如果最後一個round複製時間小於election timeout，那麼leader就決定將這個新節點加入到叢集，否則就停止這次配置變更。

場景7：S1，S2，S3，S1是leader，S1與S2，S3出現對稱網路分割槽，這個時候S2，S3重新選舉，假設S2選舉為新leader，如果S1網路分割槽恢復，並且向S2，S3繼續複製之前的log entry，S2，S3如何處理？

因為每次選舉leader都會自增自己的term，當S2被選舉為新的leader時，其term資訊要比S1大，那麼S2，S3接收到來自S1的appendEntry時會判斷其term，如果小於自己的term就會忽略這個RPC。

4.3 configure change

配置變更應該說是raft裡面的一個難點了。一個叢集配置變更無非就是加節點和減節點，一次加減多個和一次只變更一個節點的複雜度差異很大。配置變更期間既要保證叢集的可用性，又要保證叢集的正確性，這本身就是一個挑戰。

場景1：同時變更多個節點容易引起腦裂，下圖來自raft論文，S1，2，3是原有配置的

叢集節點

，後來S4，5一起加入叢集，這個時候S1，2還沒有完全從原有配置轉變為新的配置，那麼他認為還是三個節點的叢集，那麼S1只要獲得S2的投票就可以被選舉為新leader，而S3，S4，S5三個節點已經轉變為新的叢集配置，這個時候S5只要獲取S3，S4的投票就可以成為leader，可以看到這裡面S5，S1在選舉的時候沒有出現交集，導致叢集中出現兩個leader，那麼就導致資料不一致的可能。

raft的解決方法是禁止同時變更多個節點，即使需要加減多個節點，也只能透過每次變更一個節點來實現。比如要加兩個節點，那麼需要呼叫兩次AddPeer。為什麼只增減一個節點能夠保證不出現腦裂的場景，因為在增減一個節點的場景中無論怎麼劃分majority，都會存在至少一個交集節點，那麼如果一個節點被成功選舉為leader，其他節點就不能再被選舉為leader了。

場景2：raft如何實現增減一個節點的配置變更的？

raft中所有的配置變更都可以透過兩個操作組合，增加一個節點，刪除一個節點。

增加一個節點

假設原有叢集為S1，S2，S3，新增一個S4，raft在配置變更的時候內部沿用原來的邏輯，配置變更只是一個OP Type為Configuration的log entry，在收到節點變更訊息之後，內部會生成一個帶有新節點配置的log entry，然後正常走log replicate的流程。其他節點接收到該Configuration的log entry時解析entry並等待該entry commit，整個叢集就可以使用新的配置了。但是這裡會有兩個問題：

在raft中leader將日誌複製給follower，然後follower會回覆ack，然後leader向上返回給client，但是這條日誌在follower並不一定commit了，follower會在接收到leader下一個entry的時候檢視leader攜帶過來的commitindex，然後commit之前的entry。所以說如果等到新的配置 entry commit之後leader和follower才能使用新的配置資訊，這首先要保證leader知道大多數follower已經commit了這條日誌，而記錄這些需要額外的邏輯。

raft在實現時去掉了這些額外邏輯，當follower接收到configuration log entry並append到其WAL之後這個新的配置便在該節點生效了。當該配置的entry commited的時候說明當前配置變更已經結束

新新增的節點需要catch up leader的日誌，在catch up的過程中可能會導致叢集的不可用，例子在log replicate章節的場景6已經給出了。因此raft在新增新的節點時分為兩個階段，先catch up leader的日誌，在這個階段該節點是不計算在多數派之內的，日誌複製的時候仍然以舊的配置作為majority計算的依據，第二步在日誌複製差不多之後（什麼才算差不多，場景6也描述了）才能真正加入決策叢集。

因為這個配置變更的log在append 到WAL就開始起作用了，但是這個log 還沒能commit之前有可能會被新的leader覆蓋，那麼在被新的leader覆蓋時需要將自己的配置回退到與leader一致的狀態。

刪除一個節點

刪除節點的流程與新增節點的流程類似，只是在節點身份不同的場景下要做一些特殊處理。

刪除普通節點

刪除一個非leader節點過程與新增一個普通節點過程一致，在該配置變更的log entry被commit之後這個普通節點就可以shutdown了。

刪除leader

刪除leader與刪除普通節點存在差別，因為上面說過一個configuration log entryappend到節點的WAL之後便生效了，如果leader接收到外部的配置變更訊息之後發現自己不在最新的配置中，這時候如果leader自己直接降級（step down）會導致什麼情況呢？如果這時候leader直接降級，那麼這條配置變更的訊息如果在傳送給follower的過程中出現超時或者其他情況需要重發，那麼已經降級的leader不能再提供重發的機會了，因為非leader身份去重發會不安全。那麼這時候就需要當前這個leader不那麼快降級，而是等到當前配置變更的log entry commit了之後才能降級，然後shutdown

場景3：一個叢集要替換一個節點是什麼樣的步驟？先刪除節點還是先增加一個幾點，兩種順序對於叢集有什麼影響？

raft論文中推薦的模式是先增再減，因為先減再增存在安全性問題。

先減節點在增節點存在的問題

對於一個三節點服務叢集A，B，C，如果要刪C並新增D，先刪除C，那麼這個時候叢集就剩下A，B了，同樣是多數派原則，這時候leaderA的日誌必須複製到B之後才能向client端返回，如果這個時候A，B只要一個節點出現問題，整個叢集就不可用了。而如果是先將D加入叢集，然後C再退出叢集，可以保證在C退出集群后仍然能夠接受一個節點出現failure的狀況，保持原有的可用性。

場景4：一次替換多個節點？

raft論文中描述的透過一系列的加減節點操作可以滿足任意情況的配置變更需求，raft作者推薦單節點變更的方式實現多節點配置變更，但是也在論文中給出了多節點配置變更的方案。

變更多節點的關鍵就是禁止在變更期間存在新舊配置單獨決策的可能，因為這個會造成腦裂，類似與場景1中描述的那樣。

在多節點同時變更時，leader接收到配置變更訊息之後會立即建立一個帶有新舊兩個配置的entry，將這entry複製到新舊所有follower，在這個entry被commit之前，叢集還是按照舊的配置工作，當這個entry被commit之後，leader再次發起一個新配置的entry，同樣複製到所有follower，當這個entry被commit之後，那些需要被刪除的節點就可以shutdown了。

場景5：在新增節點catch up期間，如果leader掛了，那麼新選舉出來的leader如何處理這個沒有catch up結束的節點？

leader掛了之後新選舉出來的leader必定包含當前新的配置資訊，那麼新的leader會繼續進行catch up。

為什麼新選出來的leader必定包含新的配置資訊，假設A，B，C三個節點，A是leader，如果A接收到來自外部的新增新節點請求之後，會將新的配置打包然後複製到B，C，如果這時候B，C都沒有接收到這個請求，A是不會向外部返回的，RPC超時之後，這個配置變更請求就失敗了。這個時候如果叢集選舉出新leader沒有新的配置資訊是正確的。如果A將配置資訊複製給B，C，並收到了來自B的一個ACK，這個log在leader一側就被提交了，A，B，C中只有A和B有資格成為新leader。因此在catch up期間（catch up期間說明leader已經commit了這條日誌）新的leader必然包含新的配置資訊。

reference：

raft 博士論文