概述
《分佈式系統概念與設計》一書中對分佈式系統概念的定義如下:分佈式系統是一個硬件或軟件組件分佈在不同的網絡計算機上,彼此之間僅僅通過消息傳遞進行通信和協調的系統
分佈式系統的設計目標一般包括如下幾個方面
- 可用性:可用性是分佈式系統的核心需求,其用於衡量一個分佈式系統持續對外提供服務的能力。
- 可擴展性:增加機器後不會改變或極少改變系統行為,並且能獲得近似線性的性能提升。
- 容錯性:系統發生錯誤時,具有對錯誤進行規避以及從錯誤中恢復的能力。
- 性能:對外服務的響應延時和吞吐率要能滿足用户的需求。
分佈式架構比單體式架構擁有更多的挑戰
- 節點之間的網絡通信是不可靠的,存在網絡延時和丟包等情況。
- 存在節點處理錯誤的情況,節點自身隨時也有宕機的可能。
- 同步調用使系統變得不具備可擴展性。
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/
往期文章回顧:
技術
- 微服務之服務框架和註冊中心
- Beego框架使用
- 淺談微服務
- TCP性能優化
- 限流實現1
- Redis實現分佈式鎖
- Golang源碼BUG追查
- 事務原子性、一致性、持久性的實現原理
- CDN請求過程詳解
- 記博客服務被壓垮的歷程
- 常用緩存技巧
- 如何高效對接第三方支付
- Gin框架簡潔版
- InnoDB鎖與事務簡析
- 算法總結
- 分佈式系統與一致性協議
讀書筆記
思考