MIT6.824-Raft筆記:腦裂、Majority Vote(過半投票/過半選舉)

本部分主要是問題引入，以及給出一個解決方案

1 腦裂（Split Brain）

replication system的共同點：單點

前面幾個容錯特性（fault-tolerant）的系統，有一個共同的特點。

MapReduce復制了計算，但是復制這個動作，或者說整個MapReduce被一個單主節點控制。
GFS以主備（primary-backup）的方式復制數據，會實際的復制文件內容，但它也依賴一個單主節點，來確定每一份數據的主拷貝的位置。
VMware FT在一個Primary虛機和一個Backup虛機之間復制計算相關的指令。當其中一個虛機出現故障時，為了能夠正確的恢復，需要一個Test-and-Set服務來確認，Primary虛機和Backup虛機只有一個能接管計算任務。

它們都是一個多副本系統（replication system），背后存在一個共性：它們需要一個單節點來決定，在多個副本中，誰是主（Primary）。使用一個單節點的好處是，它不可能否認自己，因為只有一個節點，它的決策就是整體的決策；缺點是，它本身又是一個單點故障（Single Point of Failure），將系統容錯的關鍵點，轉移到了這個單點上。在系統出現局部故障時，通過primary copy繼續工作。使用單點是為了避免腦裂（Split-Brain）。當出現故障時，要極其小心的決定數據的主拷貝，否則需要面臨腦裂的場景。

這里主要說明多副本系統，雖然是多副本，但是最終還是搞了一個單點來做決定，而這樣做的目的是為了避免腦裂；同樣單點故障又可以通過新的primary繼續工作。
下面通過示例可以得知，如果是多副本系統，要么同時等待所有副本響應，這樣還不如單點，因為多個是一個出現問題的多倍；要么不等待多個，那這樣就會出現腦裂，根源也很簡單，在分布式系統中，根本無法確定你連接不上的這個服務到底是宕機了，還是僅僅你連接不上而其它服務可以。

腦裂帶來的問題及其嚴重性

這里通過將單點Test-and-Set服務設計為多副本，說明為什么出現故障時，很難避免腦裂。
VMware FT中的Test-and-Set之前是一個單點服務，而VMware FT依賴這個Test-and-Set服務來確定Primary虛機，為了提高系統的容錯性構建一個多副本的Test-and-Set服務。網絡里面有兩個服務器（S1，S2）都是Test-and-Set服務的拷貝，還有兩個客戶端（C1，C2），它們需要通過Test-and-Set服務確定主節點是誰。在這個例子中，這兩個客戶端本身就是VMware FT中的Primary和Backup虛擬機。
這兩個Test-and-Set服務器中的數據記錄將從0開始，任意一個客戶端發送Test-and-Set指令，這個指令會將服務器中的狀態設置成1，兩個服務器都應該設置成1，然后將舊的值0，返回給客戶端。本質上來說，這是一種簡化了的鎖服務。
**當一個客戶端可以與其中一個服務器通信，但是不能與另一個通信時，有可能出現腦裂的問題。**假設客戶端需要將請求同時發送給兩個服務器。這時就需要考慮腦裂問題，即會出現各種情況的網絡分區，以及服務器不響應需要如何處理。

如果我們只將C1的請求設置給S1，而不設置給S2，會導致S2的數據不一致。或許應該規定，對于任何操作，客戶端必須總是與兩個服務器交互，而不是只與其中一個服務器交互。**但是這是一個錯誤的想法，因為這里根本就沒有容錯，甚至比只使用一個服務器更糟。**因為當兩個服務器中的一個故障了或者失聯了，我們的系統就不能工作了。對于一個單點的服務，我們只依賴一個服務器。現在我們有兩個服務器，并且兩個服務器都必須一致在線，這里的難度比單個服務器更大。
如果客戶端不能同時與兩個服務器交互，那它就與它能連通的那個服務器交互，同時認為另一個服務器已經關機了。這也是一個錯誤的答案呢？我們的故障場景是，另一個服務器的狀態無從知曉，實際可能是網絡線路出現了故障，從而導致C1可以與S1交互，但是不能與S2交互。同時C2可以與S2交互，但是不能與S1交互。如果一個客戶端連接了兩個服務器，為了達到一定的容錯性，客戶端只與其中一個服務器交互也應該可以正常工作。但是這樣就不可避免的出現了這種情況：假設這根線纜中斷了，將網絡分為兩個部分。C1發送Test-and-Set請求給S1，S1將自己的狀態設置為1，并返回之前的狀態0給C1。C1對應的虛擬機會認為自己可以成為主節點。但是同時S2里面的狀態仍然是0。如果現在C2也發送了一個Test-and-Set請求，本來應該發送給兩個服務器，但是現在從C2看來，S1不能訪問，根據之前定義的規則，那就發送給S2吧。同樣的C2也會認為自己持有了鎖。如果這個Test-and-Set服務被VMware FT使用，那么這兩個VMware 虛機都會認為自己成為了主虛擬機而不需要與另一個虛擬機協商，這是一個錯誤的場景。

這里主要是針對上面的共同點，通過舉反例說明單點的必要性。
實際上Lecture4中最后也提到 test and set 應該也是具有容錯性的服務，而不是某個單點。

**在有兩個拷貝副本的配置中，看起來我們只有兩種選擇：要么等待兩個服務器響應，那么這個時候就沒有容錯能力；要么只等待一個服務器響應，那么就會進入錯誤的場景（通常稱為腦裂）。**這基本是上世紀80年代之前要面臨的挑戰。多副本系統時，需要排除腦裂的可能，這里有兩種技術：

構建一個不可能出現故障的網絡。比如電腦中，連接了CPU和內存的線路就是不可能出現故障的網絡。如果網絡不會出現故障，這樣就排除了腦裂的可能。當網絡不出現故障時，那就意味著，如果客戶端不能與一個服務器交互，那么這個服務器肯定是關機了。這里假設有足夠多的資金，就能接近這個假設。

主要還是，只要有網絡的情況下，節點A和節點B連接異常，但是B本身是什么樣的，節點B和其他節點是什么樣的是未知的。

人工解決問題，不要引入任何自動完成的操作。默認情況下，客戶端總是要等待兩個服務器響應，如果只有一個服務器響應，永遠不要執行任何操作。之后通過運維人員檢查，進行關機等處理，這里本質上把人作為了一個決策器，這個人也是個單點。

很長一段時間內，人們都使用以上兩種方式中的一種來構建多副本系統。這雖然不太完美，因為人工響應不能很及時，不出現故障的網絡又很貴，但是這些方法至少是可行的。

2 Majority Vote (quorum)

盡管存在腦裂的可能，人們發現哪怕網絡可能出現故障，可能出現分區，實際上是可以正確的實現能夠自動完成故障切換的系統。這種能自動恢復，同時又避免腦裂的多副本系統，關鍵點在于多數投票（Majority Vote）。這也是用來構建Raft的一個基本概念。
網絡分區（Partition）：當網絡出現故障將網絡分割成兩半，網絡的兩邊獨自運行且不能訪問對方。
多數投票系統的第一步在于，服務器的數量要是奇數，而不是偶數。如果只有兩個服務器，被網絡故障分隔的兩邊，它們看起來完全是一樣的，它們運行了同樣的軟件，它們也會做相同的事情，這樣不太好（會導致腦裂）。但如果服務器的數量是奇數的，那么當出現一個網絡分割時，兩個網絡分區將不再對稱，這是多數投票吸引人的地方。首先你要有奇數個服務器。然后為了完成任何操作，例如Raft的Leader選舉，例如提交一個Log條目，在任何時候為了完成任何操作，你必須湊夠過半的服務器來批準相應的操作。

如果是偶數會如何呢，這里舉兩個例子：

2副本，那么如果分區，就要等待過半投票，即2/2 + 1 = 2，也就是每一個都要等待2個的響應，那這個和6.1中第二小節示例中的方案一：必須與所有副本通信，又有何區別，反而提高了故障概率。
4副本，過半投票 4/2+1=3，這里好一些了，能夠容忍1個的故障，但是這和3副本相比，并不能提高容錯概率，還不如之間5副本或者3副本，浪費反而不會提高容錯。

綜上：偶數情況下，如果被網絡故障均分，那么整個系統依然是不可用的。

這里背后的邏輯是，如果網絡存在分區，最多只有一個分區能夠擁有過半的服務器。這里有一點需要明確，當我們在說過半的時候，我們是在說所有服務器數量的一半，而不是當前開機服務器數量的一半。這個點困擾了我（Robert教授）很長時間，如果你有一個系統有3個服務器，其中某些已經故障了，如果你要湊齊過半的服務器，你總是需要從3個服務器中湊出2個，即便你知道1個服務器已經因為故障關機了。過半總是相對于服務器的總數來說。

服務器的總數：一是因為實際上很難完全知道具體出現故障的機器到底是怎么了，另一方面是因為為了后面的過半更新+過半選舉，這樣選出來的leader一定包含有最新數據。

個人思考：

這里的開機，在有網絡的情況下，A連接不上B，無法判斷B是否開機，B和C是否連接？
需要及時處理故障機
需要提供快速的數據恢復

對于多數投票，可以用一個更通用的方程式來描述：如果系統有 2 * F + 1 個服務器，那么系統最多可以接受F個服務器出現故障，仍然可以正常工作。這也被稱為多數投票（quorum）系統，因為3個服務器中的2個，就可以完成多數投票。
有關多數投票系統的一個特性就是，最多只有一個網絡分區會有過半的服務器，我們不可能有兩個分區可以同時完成操作。這里背后更微妙的點在于，如果你總是需要過半的服務器才能完成任何操作，同時你有一系列的操作需要完成，其中的每一個操作都需要過半的服務器來批準，例如選舉Raft的Leader，那么每一個操作對應的過半服務器，必然至少包含一個服務器存在于上一個操作的過半服務器中。任意兩組過半服務器，至少有一個服務器是重疊的。實際上相比其他特性，Raft更依賴這個特性來避免腦裂。
例如，當一個Raft Leader競選成功，那么這個Leader必然湊夠了過半服務器的選票，而這組過半服務器中，必然與舊Leader的過半服務器有重疊。新的Leader必然知道舊Leader使用的任期號（Term ID），因為新Leader的過半服務器必然與舊Leader的過半服務器有重疊，而舊Leader的過半服務器中的每一個必然都知道舊Leader的任期號。類似的，任何舊Leader提交的操作，必然存在于過半的Raft服務器中，而任何新Leader的過半服務器中，必然有至少一個服務器包含了舊Leader的所有操作。這是Raft能正確運行的一個重要因素。
在多數投票這種思想的支持下，大概1990年的時候，有兩個系統基本同時被提出。這兩個系統指出，你可以使用這種多數投票系統，從某種程度上來解決之前明顯不可能避免的腦裂問題，例如，通過使用3個服務器而不是2個，同時使用多數投票策略。兩個系統中的一個叫做Paxos（1989），Raft論文對這個系統做了很多的討論；另一個叫做ViewStamped Replication（VSR， 1988）。盡管Paxos的知名度高得多，Raft從設計上來說，與VSR更接近。VSR是由MIT發明的。
學生提問：可以為Raft添加服務器嗎？
Rober教授：Raft的服務器是可以添加或者修改的，Raft的作者提出了方法來處理這種場景，但是比較復雜。