分散式系統與一致性協議_程式設計師麻辣燙

概述

《分散式系統概念與設計》一書中對分散式系統概念的定義如下：分散式系統是一個硬體或軟體元件分佈在不同的網路計算機上，彼此之間僅僅通過訊息傳遞進行通訊和協調的系統

分散式系統的設計目標一般包括如下幾個方面

可用性：可用性是分散式系統的核心需求，其用於衡量一個分散式系統持續對外提供服務的能力。
可擴充套件性：增加機器後不會改變或極少改變系統行為，並且能獲得近似線性的效能提升。
容錯性：系統發生錯誤時，具有對錯誤進行規避以及從錯誤中恢復的能力。
效能：對外服務的響應延時和吞吐率要能滿足使用者的需求。

分散式架構比單體式架構擁有更多的挑戰

節點之間的網路通訊是不可靠的，存在網路延時和丟包等情況。
存在節點處理錯誤的情況，節點自身隨時也有宕機的可能。
同步呼叫使系統變得不具備可擴充套件性。

CAP原理

提到分散式系統，就不得不提CAP原理。

CAP的完整定義為:

C：Consistency（一致性）。這裡的一致性特指強一致，通俗地說，就是所有節點上的資料時刻保持同步。一致性嚴謹的表述是原子讀寫，即所有讀寫都應該看起來是“原子”的，或序列的。所有的讀寫請求都好像是經全域性排序過的一樣，寫後面的讀一定能讀到前面所寫的內容。
A：Availability（可用性）。任何非故障節點都應該在有限的時間內給出請求的響應，不論請求是否成功。
P：Tolerance to the partition of network（分割槽容忍性）。當發生網路分割槽時（即節點之間無法通訊），在丟失任意多訊息的情況下，系統仍然能夠正常工作。

CAP原理具有重大的指導意義：在任何分散式系統中，可用性、一致性和分割槽容忍性這三個方面都是相互矛盾的，三者不可兼得，最多隻能取其二。

直觀的說明如下：

1）AP滿足但C不滿足：如果既要求系統高可用又要求分割槽容錯，那麼就要放棄一致性了。因為一旦發生網路分割槽（P），節點之間將無法通訊，為了滿足高可用（A），每個節點只能用本地資料提供服務，這樣就會導致資料的不一致（!C）。一些信奉BASE（Basic Availability, Soft state, Eventually Consistency）原則的NoSQL資料庫（例如，Cassandra、CouchDB等）往往會放寬對一致性的要求（滿足最終一致性即可），以此來換取基本的可用性。

2）CP滿足但A不滿足：如果要求資料在各個伺服器上是強一致的（C），然而網路分割槽（P）會導致同步時間無限延長，那麼如此一來可用性就得不到保障了（!A）。堅持事務ACID（原子性、一致性、隔離性和永續性）的傳統資料庫以及對結果一致性非常敏感的應用（例如，金融業務）通常會做出這樣的選擇。

3）CA滿足但P不滿足：指的是如果不存在網路分割槽，那麼強一致性和可用性是可以同時滿足的。

正如熱力學第二定律揭示了任何嘗試發明永動機的努力都是徒勞的一樣，CAP原理明確指出了完美滿足CAP三種屬性的分散式系統是不存在的。

瞭解CAP原理的目的在於，其能夠幫助我們更好地理解實際分散式協議實現過程中的取捨。

一致性

分散式儲存系統通常會通過維護多個副本來進行容錯，以提高系統的可用性。這就引出了分散式儲存系統的核心問題——如何保證多個副本的一致性？

“一致性”有三種含義：

Coherence這個單詞只在Cache Coherence場景下出現過，其所關注的是多核共享記憶體的CPU架構下，各個核的Cache上的資料應如何保持一致。
Consensus是共識，它強調的是多個提議者就某件事情達成共識，其所關注的是達成共識的過程，例如Paxos協議、Raft選舉等。Consensus屬於replication protocol的範疇。
Consistency表達的含義相對複雜一些，廣義上說，它描述了系統本身的不變數的維護程度對上層業務客戶端的影響，以及該系統的併發狀態會向客戶端暴露什麼樣的異常行為。CAP、ACID中的C都有這層意思。

這裡重點討論的分散式系統中的一致性問題，屬於上文中提到的Consensus和Consistency範疇。

分散式系統的一致性是一個具備容錯能力的分散式系統需要解決的基本問題。通俗地講，一致性就是不同的副本伺服器認可同一份資料。一旦這些伺服器對某份資料達成了一致，那麼該決定便是最終的決定，且未來也無法推翻。

這裡有一點需要注意：一致性與結果的正確性沒有關係，而是系統對外呈現的狀態是否一致（統一）。例如，所有節點都達成一個錯誤的共識也是一致性的一種表現。

一致性協議就是用來解決一致性問題的，它能使得一組機器像一個整體一樣工作，即使其中的一些機器發生了錯誤也能正常工作。正因為如此，一致性協議在大規模分散式系統中扮演著關鍵角色。

一致性協議從20世紀80年代開始研究，一致性協議衍生出了很多演算法。衡量一致性演算法的標準具體如下：

可終止性：非失敗程序在有限的時間內能夠做出決定，等價於liveness。
一致性：所有的程序必須對最終的決定達成一致，等價於safety。
合法性：演算法做出的決定值必須在其他程序（客戶端）的期望值範圍之內。即客戶端請求回答“是”或“否”時，不能返回“不確定”。

一致性模型

在給定了與操作和狀態相關的一些規則的情況下，系統中的操作歷史應該總是遵循這些規則。我們稱這些規則為一致性模型

一致性模型分述

對於一致性，可以分別從客戶端和服務端兩個不同的視角來理解。

從客戶端來看，一致性主要是指多併發訪問時如何獲取更新過的資料的問題。

從服務端來看，則是更新如何複製分佈到整個系統，以保證資料最終的一致性。

因此，可以從兩個角度來檢視一致性模型：以資料為中心的一致性模型和以使用者為中心的一致性模型。

以資料為中心的一致性模型

實現以下這幾種一致性模型的難度會依次遞減，對一致性強度的要求也依次遞減。

嚴格一致性（Strong Consistency）

嚴格一致性也稱強一致性，原子一致性或者是可線性化（Linearizability），是要求最高的一致性模型。嚴格一致性的要求具體如下:
- 任何一次讀都能讀到某個資料的最近一次寫的資料。
- 系統中的所有程序，看到的操作順序，都與全域性時鐘下的順序一致。
**嚴格一致性維護的是一個絕對全域性時間順序。**單機系統遵守嚴格一致性，但對於分散式系統，為每個操作都分配一個準確的全域性時間戳是不可能實現的，所以嚴格一致性只是存在於理論中的一致性模型。
順序一致性（Sequential Consistency）

順序一致性，也稱為可序列化，比嚴格一致性要求弱一點，但也是能夠實現的最高級別的一致性模型。

因為全域性時鐘導致嚴格一致性很難實現，因此順序一致性放棄了全域性時鐘的約束，改為分散式邏輯時鐘實現。順序一致性是指所有的程序都以相同的順序看到所有的修改。讀操作未必能夠及時得到此前其他程序對同一資料的寫更新，但是每個程序讀到的該資料不同值的順序卻是一致的。

滿足順序一致性的儲存系統需要一個額外的邏輯時鐘服務。

下圖解釋了嚴格一致性和順序一致性

a) 順序一致性，從這兩個程序的角度來看，順序應該是這樣的：Write(y, 2)→Read(x, 0)→Write(x, 4)→Read(y, 2)，完全沒有衝突

b) 嚴格一致性，從兩個程序看到的操作順序與全域性時鐘的順序一樣，都是Write(y, 2)→Write(x, 4)→Read(x, 4)→Read(y, 2)。

c) 不滿足順序一致性，Write(x, 4)→Read(y, 0)→Write(y, 2)→Read(x, 0)，這個有衝突

3. 因果一致性（Causal Consistency）

因果關係可以描述成如下情況：

本地順序：本程序中，事件執行的順序即為本地因果順序。
異地順序：如果讀操作返回的是寫操作的值，那麼該寫操作在順序上一定在讀操作之前。
閉包傳遞：與時鐘向量裡面定義的一樣，如果a→b且b→c，那麼肯定也有a→c。

不嚴格地說，因果一致性弱於順序一致性。

因果一致性和順序一致性的對比

因果關係可能比較難以理解，下面給大家解釋一下

P2寫x=7，P2同步到P3，P3讀到7

P1寫x=2，P1同步到P3，P3讀到2

P1寫x=4，P1同步到P4，P4讀到4

P2同步到P4，P4讀到7

永遠不會出現先讀到4，再讀到2的情況

因果關係只保證因果的順序是正確的，其他的順序不理會

可序列化一致性（Serializable Consis-tency）

如果說操作的歷史等同於以某種單一原子順序發生的歷史，但對呼叫和完成時間沒有說明，那麼就可以獲得稱為可序列化的一致性模型。

在一個可序列化的系統中，有如下所示的這樣一個程式：

x = 1

x = x + 1

puts x

在這裡，我們假設每行代表一個操作，並且所有的操作都成功。因為這些操作可以以任何順序進行，所以可能打印出nil、1或2。因此，一致性顯得很弱。

但在另一方面，序列化的一致性又很強，因為它需要一個線性順序。例如，下面的這個程式：

print x if x = 3

x = 1 if x = nil

x = 2 if x = 1

x = 3 if x = 2

它可能不會嚴格地以我們編寫的順序發生，但它能夠可靠地將x從nil→1→2，更改為3，最後打印出3。

以使用者為中心的一致性模型

最終一致性（Eventual Consistency）

最終一致性是指如果更新的間隔時間比較長，那麼所有的副本都能夠最終達到一致性。

使用者讀到某一操作對系統特定資料的更新需要一段時間，我們將這段時間稱為“不一致性視窗”。

在讀多寫少的場景中，例如CDN，讀寫之比非常懸殊，如果網站的運營人員修改了一張圖片，終端使用者延遲了一段時間才看到這個更新實際上問題並不是很大。

複製狀態機

複製狀態機的基本思想是：一個分散式的複製狀態機系統由多個複製單元組成，每個複製單元均是一個狀態機，它的狀態儲存在一組狀態變數中。狀態機的狀態能夠並且只能通過外部命令來改變。

上文提到的“一組狀態變數”通常是基於操作日誌來實現的。每一個複製單元儲存一個包含一系列指令的日誌，並且嚴格按照順序逐條執行日誌上的指令。

所以，在複製狀態機模型下，一致性演算法的主要工作就變成了如何保證操作日誌的一致性。

複製狀態機的執行過程如下圖所示：

伺服器上的一致性模組負責接收外部命令，然後追加到自己的操作日誌中。它與其他伺服器上的一致性模組進行通訊以保證每一個伺服器上的操作日誌最終都以相同的順序包含相同的指令。一旦指令被正確複製，那麼每一個伺服器的狀態機都將按照操作日誌的順序來處理它們，然後將輸出結果返回給客戶端。

複製狀態機在分散式系統中常被用於解決各種容錯相關的問題，例如，GFS、HDFS、Chubby、ZooKeeper和etcd等分散式系統都是基於複製狀態機模型實現的。

需要注意的是，指令在狀態機上的執行順序並不一定等同於指令的發出順序或接收順序。

複製狀態機只是保證所有的狀態機都以相同的順序執行這些命令。

拜占庭將軍問題

拜占庭位於如今土耳其的伊斯坦布林，是東羅馬帝國的首都。由於當時拜占庭羅馬帝國幅員遼闊，出於防禦的原因，每個軍隊都相隔甚遠，將軍與將軍之間只能靠信差來傳遞訊息。發生戰爭時，拜占庭軍隊內所有將軍必需達成共識，決定是否攻擊敵人。但是軍隊內可能存在叛徒和敵軍的間諜擾亂將軍們的決定，因此在進行共識交流時，結果可能並不能真正代表大多數人的意見。這時，在已知有成員不可靠的情況下，其餘忠誠的將軍如何排除叛徒或間諜的影響來達成一致的決定，就是著名的拜占庭將軍問題。

拜占庭將軍問題講述的是一個共識問題。拜占庭將軍問題是對現實世界的模型化。

拜占庭錯誤是一個overly pessimistic模型（最悲觀、最強的錯誤模型）

研究這個模型的意義在於：如果某個一致性協議能夠保證系統在出現N個拜占庭錯誤時，依舊可以做出一致性決定，那麼這個協議也就能夠處理系統出現N個其他任意型別的錯誤。
程序失敗錯誤（fail-stop Failure，如同宕機）則是一個overly optimistic模型（最樂觀、最弱的錯誤模型）

研究這個模型的意義在於：如果某個一致性協議在系統出現N個程序失敗錯誤時都無法保證做出一致性決定，那麼這個協議也就無法處理系統出現N個其他任意型別的錯誤。

Fred Schneider在前面提到的論文《Implementing fault-tolerant services using thestate machine approach》中指出了這樣一個基本假設：

一個RSM(分散式狀態機)系統要容忍N個拜占庭錯誤，至少需要2N+1個複製節點。

如果只是把錯誤的型別縮小到程序失敗，則至少需要N+1個複製節點才能容錯。

但是不是隻要滿足上文提到的2N+1個要求就能保證萬無一失了呢？很不幸，答案是否定的。

FLP不可能性

FLP不可能性是分散式領域中一個非常著名的定理：

No completely asynchronous consensusprotocol can tolerate even a single unan-nounced process death.

在非同步通訊場景下，任何一致性協議都不能保證，即使只有一個程序失敗，其他非失敗程序也不能達成一致。

這裡的程序失敗(unannounced process death)指的是一個程序發生了故障，但其他節點並不知道，繼續認為這個程序還沒有處理完成或發生訊息延遲了。

舉個例子：

甲、乙、丙三個人各自分開進行投票（投票結果是0或1）。他們彼此可以通過電話進行溝通，但有人會睡著。例如：甲投票0，乙投票1，這時候甲和乙打平，丙的選票就很關鍵。然而丙睡著了，在他醒來之前甲和乙都將無法達成最終的結果。即使重新投票，也有可能陷入無盡的迴圈之中。

FLP定理實際上說明了在允許節點失效的場景下，基於非同步通訊方式的分散式協議，無法確保在有限的時間內達成一致性。用CAP理論解釋的話，在P的條件下，無法滿足C和A。

請注意，這個結論的前提是非同步通訊。在分散式系統中，“非同步通訊”與“同步通訊”的最大區別是沒有時鐘、不能時間同步、不能使用超時、不能探測失敗、訊息可任意延遲、訊息可亂序等。

所以，實際的一致性協議（Paxos、Raft等）在理論上都是有缺陷的，最大的問題是理論上存在不可終止性！但他們都做了一些調整，降低了概率。

Paxos協議

大神Leslie Lamport對類似拜占庭將軍這樣的問題進行了深入研究，並發表了幾篇論文。

總結起來就是回答如下的三個問題：

1）類似拜占庭將軍這樣的分散式一致性問題是否有解？

2）如果有解的話需要滿足什麼樣的條件？

3）基於特定的前提條件，提出一種解法。

Leslie Lamport在論文“拜占庭將軍問題”中已經給出了前兩個問題的回答，而第三個問題在他的論文“The Part-Time Parliament”中提出了一種基於訊息傳遞的一致性演算法。

下面講述的就是大神的日常操作：

1990年，Lamport向ACM Transac-tions on Computer Systems提交了他那篇關於Paxos演算法的論文。主編回信建議他用數學而不是神話描述他的演算法，否則他們不會考慮接受這篇論文。Lamport覺得那些人太迂腐，拒絕做任何修改，轉而將論文貼在了自己的個人部落格上。

起初Paxos演算法由於難以理解並沒有引起多少人的重視，直到2006年Google的三大論文初現“雲”端，其中Chubby Lock服務使用了Paxos作為Chubby Cell的一致性演算法，這件事使得Paxos演算法的人氣從此一路飆升，幾乎壟斷了一致性演算法領域。在Raft演算法誕生之前，Paxos幾乎成了一致性協議的代名詞。

Lamport本人覺得Paxos很簡單，但事實上對於大多數人來說，Paxos還是太難理解了。

引用NSDI社群上的一句話就是：全世界真正理解Paxos演算法的人只有5個！

這可能就是人和神之間的區別吧。

然後，更容易理解的一致性演算法Raft誕生了。

Raft協議：為可理解性而生

終於講到Raft了，我太不容易了。

Raft演算法主要使用兩種方法來提高可理解性。提高理解性主要通過兩個常用手段

問題分解

儘可能地將問題分解成為若干個可解決的、更容易理解的小問題——這是眾所周知的簡化問題的方法論。例如，Raft演算法把問題分解成了領袖選舉（leader election）、日誌複製（log repli-cation）、安全性（safety）和成員關係變化（membershipchanges）這幾個子問題。
- 領袖選舉：在一個領袖節點發生故障之後必須重新給出一個新的領袖節點。
- 日誌複製：領袖節點從客戶端接收操作請求，然後將操作日誌複製到叢集中的其他伺服器上，並且強制要求其他伺服器的日誌必須和自己的保持一致。
- 安全性：Raft關鍵的安全特性是下文提到的狀態機安全原則（State Machine Safety）——如果一個伺服器已經將給定索引位置的日誌條目應用到狀態機中，則所有其他伺服器不會在該索引位置應用不同的條目。下文將會證明Raft是如何保證這條原則的。
- 成員關係變化：配置發生變化的時候，叢集能夠繼續工作。
減少狀態空間

Raft演算法通過減少需要考慮的狀態數量來簡化狀態空間。這將使得整個系統更加一致並且能夠儘可能地消除不確定性。

Raft有幾點重要的創新

強領導人。Raft使用一種比其他演算法更強的領導形式。例如，日誌條目只從領導人發向其他伺服器。這樣就簡化了對日誌複製的管理，提高了Raft的可理解性。
領袖選舉。Raft使用隨機定時器來選舉領導者。這種方式僅僅是在所有演算法都需要實現的心跳機制上增加了一點變化，就使得衝突解決更加簡單和快速。
成員變化。Raft在調整叢集成員關係時使用了新的一致性（joint consensus，聯合一致性）方法。使用這種方法，使得叢集配置在發生改變時，叢集依舊能夠正常工作。

Raft一致性演算法

基本概念

Leader（領袖）
Candidate（候選人）
Follower（群眾）
任期（Term）：Raft演算法將時間劃分成為任意個不同長度的任期，任期是單調遞增的，用連續的數字（1, 2, 3……）表示。在Raft的世界裡，每一個任期的開始都是一次領導人的選舉。如果一個候選人贏得了選舉，那麼它就會在該任期的剩餘時間內擔任領導人。在某些情況下，選票會被瓜分，導致沒有哪位候選人能夠得到超過半數的選票，這樣本次任期將以沒有選出領導人而結束。那麼，系統就會自動進入下一個任期，開始一次新的選舉。Raft演算法保證在給定的一個任期內最多隻有一個領導人。某些Term會由於選舉失敗，存在沒有領導人的情況，如t3所示。

任期在Raft中起著邏輯時鐘的作用，同時也可用於在Raft節點中檢測過期資訊——比如過期的領導人。每個Raft節點各自都在本地維護一個當前任期值，觸發這個數字變化（增加）主要有兩個場景：開始選舉和與其他節點交換資訊。如果一個節點（包括領導人）的當前任期號比其他節點的任期號小，則將自己本地的任期號自覺地更新為較大的任期號。如果一個候選人或者領導人意識到它的任期號過時了（比別人的小），那麼它會立刻切換回群眾狀態；如果一個節點收到的請求所攜帶的任期號是過時的，那麼該節點就會拒絕響應本次請求。

領導人選舉

Raft通過選舉一個權力至高無上的領導人，並採取賦予他管理複製日誌重任的方式來維護節點間複製日誌的一致性。

領導人從客戶端接收日誌條目，再把日誌條目複製到其他伺服器上，並且在保證安全性的前提下，告訴其他伺服器將日誌條目應用到它們的狀態機中。領導人可以決定新的日誌條目需要放在日誌檔案的什麼位置，而不需要和其他伺服器商議，並且資料都是單向地從領導人流向其他伺服器。

領導人選舉的過程，就是Raft三種角色切換的過程開始的時候，系統有一個Leader和眾多Follower

每一個Raft節點（包含Follower）內有一個選舉定時器，如果收到Leader廣播的心跳包，則Follower將選舉定時器重置。
如果Follower的選舉定時器時間到了，在這個期間沒有收到任何心跳包，Follower認為Leader，自己可以當Leader了，就開始發起選舉，主要做如下步驟
- 將自己本地維護的當前任期號（current_term_id）加1
- 將自己的狀態切換到候選人（Candidate），併為自己投票
- 向其所在叢集中的其他節點發送RequestVote RPC（RPC訊息會攜帶“current_term_id”值），要求它們投票給自己
- 設定選舉超時時間，一般是隨機選取一個區間中的值
在Candidate狀態下
- 如果得到大多數選票，則成為Leader
- 如果發現已經產生了新的領導人或者有更大的任期，則狀態更改為Follower
- 如果選舉超時時間過了，候選人自增任期號（Term++）並且發起新一輪的拉選票活動
在Leader狀態下，如果發現了更高的任期，則將自己變更為Follower

日誌複製

一旦某個領導人贏得了選舉，那麼它就會開始接收客戶端的請求。領導人將把這條指令作為一條新的日誌條目加入它的日誌檔案中，然後並行地向其他Raft節點發起AppendEntriesRPC，要求其他節點複製這個日誌條目。當這個日誌條目被“安全”地複製之後，Leader會將這條日誌應用（apply，即執行該指令）到它的狀態機中，並且向客戶端返回執行結果。如果Follower發生錯誤，執行緩慢沒有及時響應AppendEntries RPC，或者發生了網路丟包的問題，那麼領導人會無限地重試AppendEntries RPC（甚至在它響應了客戶端之後），直到所有的追隨者最終儲存了和Leader一樣的日誌條目。

日誌由有序編號的日誌條目組成。每一個日誌條目一般均包含三個屬性：整數索引（log index）、任期號（term）和指令（command）。一般如下所示：

一旦領導人建立的條目已經被複制到半數以上的節點上了，那麼這個條目就稱為可被提交的。

Raft日誌複製主要流程如下：

客戶端向Leader傳送寫請求。
Leader將寫請求解析成操作指令追加到本地日誌檔案中。
Leader為每個Follower廣播AppendEntries RPC。
Follower通過一致性檢查，選擇從哪個位置開始追加Leader的日誌條目。
一旦日誌項提交成功，Leader就將該日誌條目對應的指令應用（apply）到本地狀態機，並向客戶端返回操作結果。
Leader後續通過AppendEntries RPC將已經成功（在大多數節點上）提交的日誌項告知Follower。
Follower收到提交的日誌項之後，將其應用至本地狀態機。

從上面的步驟可以看出，針對Raft日誌條目有兩個操作，提交（commit）和應用（apply），應用必須發生在提交之後，即某個日誌條目只有被提交之後才能被應用到本地狀態機上。

流程圖如下：http://www.processon.com/view/link/5fa6c1045653bb25634dea4a

安全性

本文介紹如何在領導人選舉部分加入一個限制規則來保證——任何的領導人都擁有之前任期提交的全部日誌條目。

怎樣才能具有成為領導人的資格？- 必須包含所有已提交日誌條目

RequestVote RPC的接收方有一個檢查：如果Follower自己的日誌比RPC呼叫方（候選人）的日誌更加新，就會拒絕候選人的投票請求。

這就Raft演算法使用投票的方式來阻止那些沒有包含所有已提交日誌條目的節點贏得選舉。
如何判斷日誌已經提交？

在提交之前term的日誌項時，必須保證當前term新建的日誌項已經複製到超過半數節點。這樣，之前term的日誌項才算真正提交的。

可用性與時序性

broadcastTime << electionTimeout << MTBF

broadcastTime指的是一個節點向叢集中其他節點發送RPC，並且收到它們響應的平均時間。

electionTimeout就是選舉超時時間。

MTBF指的是單個節點發生故障的平均時間間隔。

為了使領導人能夠持續傳送心跳包來阻止下面的Follower發起選舉，broadcastTime應該比electionTimeout小一個數量級。

異常情況

####追隨者/候選人異常

Raft演算法通過領導人無限的重試來應對這些失敗，直到故障的節點重啟並處理了這些RPC為止。

因為Raft演算法中的RPC都是冪等的，因此不會有什麼問題。

領導人異常

Raft資料交換流程如上圖所示，在任何時刻，領導人都有可能崩潰。

資料在到達Leader之前

不影響一致性

資料到達Leader節點，但未複製到Follower節點

不影響一致性

如果在這個階段Leader出現故障，此時資料屬於未提交狀態，那麼Client不會收到ACK，而是會認為超時失敗可安全發起重試。Follower節點上沒有該資料，重新選主後Client重試重新提交可成功。原來的Leader節點恢復之後將作為Follower加入叢集，重新從當前任期的新Leader處同步資料，與Leader資料強制保持一致。

資料到達Leader節點，成功複製到Follower的部分節點上，但還未向Leader響應接收

資料不丟失，也不影響一致性

如果在這個階段Leader出現故障，此時資料在Follower節點處於未提交狀態（Uncommitted）且不一致，那麼Raft協議要求投票只能投給擁有最新資料的節點。所以擁有最新資料的節點會被選為Leader，再將資料強制同步到Follower，資料不會丟失並且能夠保證最終一致。

資料到達Leader節點，成功複製到Follower的所有節點上，但還未向Leader響應接收

資料不丟失，也不影響一致性

如果在這個階段Leader出現故障，雖然此時資料在Fol-lower節點處於未提交狀態（Uncommitted），但也能保持一致，那麼重新選出Leader後即可完成資料提交，由於此時客戶端不知到底有沒有提交成功，因此可重試提交。針對這種情況，Raft要求RPC請求實現冪等性，也就是要實現內部去重機制。

資料到達Leader節點，成功複製到Follower的所有或大多數節點上，資料在Leader上處於已提交狀態，但在Follower上處於未提交狀態

資料不丟失，也不影響一致性

資料到達Leader節點，成功複製到Follower的所有或大多數節點上，資料在所有節點都處於已提交狀態，但還未響應Client

資料不丟失，也不影響一致性

網路分割槽導致的腦裂情況，出現雙Leader

不影響一致性

網路分割槽將原先的Leader節點和Follower節點分隔開，Follower收不到Leader的心跳將發起選舉產生新的Leader。這時就產生了雙Leader，原先的Leader獨自在一個區，向它提交資料不可能複製到大多數節點上，所以永遠都是提交不成功。向新的Leader提交資料可以提交成功，網路恢復後舊的Leader發現叢集中有更新任期（Term）的新Leader，則自動降級為Fol-lower並從新Leader處同步資料達成叢集資料一致。

總結

分散式系統和一般的業務系統區別還是挺大的，涉及到更多論文、數理知識，更加偏學術一些。隨著計算機的不斷髮展，關於分散式的知識，還是需要進行掌握的。

關於Raft演算法，建議看一下原始碼http://github.com/etcd-io/etcd/tree/master/raft。

Raft通過領導選舉機制，簡化了整體的複雜性。利用日誌複製+複製狀態機，保證狀態執行的一致。同時設定了一些對應的安全規則，加強了日誌複製的安全，維護了一致性。

如果大家時間有限，可以只看一下CAP、複製狀態機和Raft。

資料

www.infoq.cn/article/wec… 微信序列號生成器架構設計及演變
從微信朋友圈的評論可見性，談因果一致性在分散式系統中的應用
www.jianshu.com/p/ab511132a… raft 系列解讀(3) 之程式碼實現
blog.csdn.net/lanyang1234… raft協議中的日誌安全性
www.duokan.com/book/180790 雲原生分散式儲存基石：etcd深入解析

最後

大家如果喜歡我的文章，可以關注我的公眾號（程式設計師麻辣燙）

我的個人部落格為：http://shidawuhen.github.io/

往期文章回顧：

技術

讀書筆記

思考