一種面向小集群同步的改進Raft的分布式一致性模型

余 瑯，戴振邦，黃家珞，劉官啟，鄭林杰，虎俊瑤

（西北民族大學數學與計算機科學學院 甘肅 蘭州 730124）

0 引言

分布式云存儲服務是新一代數字技術發展的重要基石。分布式系統只能滿足一致性[1]、可用性、分區容錯性（Consistency、Availability、Partition tolerance）中的兩種特性，即CAP理論。對于大部分分布式應用來說，都需要滿足A、P特性，舍棄一致性。在保證業務的高并發性、高可用性和高穩定性的同時，如何保證數據的一致性成為一個比較嚴峻的問題。在最理想的情況下，集群中每個存儲單元的變化都能立即被其他節點知道，并且能時刻保持數據的一致性[2]，這就是強一致性模型。但大多數情況下，網絡IO是不可控制的。在保證強一致性的大多數情況下，我們會犧牲高可用性，比如Guerraoui等[3]基于增量更新所提出的ICG方案，通過犧牲通信開銷和查詢正確度，提高了ICG的操作延時。

因此，在大部分分布式應用中選擇保證可用性、分區容錯性，而舍棄強一致性。與MySQL集群一樣，Redis集群采用最終一致性以保證集群數據的同步收斂，來達到分布式系統的穩定性。

1 Raft模型選舉

Raft算法[4]是一種基于Paxos的典型主從復制模式，相較于Paxos更加容易理解和工程實現，解決主機選舉問題是Raft模型的首要關鍵點。初始狀態下，所有服務器都是Follower，并且隨機睡眠一段時間（0～1 000 ms），接著進行倒計時。最先被喚醒的Follower會升級為Candidate，并請求其他Follower為它投票，多于半數則成為Leader。由此完成Leader的選舉。

1.1 Raft心跳以及Leader宕機解決方案

在Raft模型中，Leader通過不斷地向所有Follower發送心跳包來判斷其是否在線的方法來維護一個Follower集合。在某Follower宕機后，Leader會將這個Follower移出集合，以確保每臺Follower的可用性。但Leader掛機后，休眠的Follower將進入激活狀態，其中某些Follower會進入Candidate狀態，并向其他Follower進行選舉聲明，要求投票，收到半數投票后的Candidate將升級為Leader。

Raft模型利用上述方案解決了集群中主從的轉換問題。但在Raft模型中，Leader掛機后可能會同時有多個Follower升級為Candidate。由于在相同的選舉周期中每個Follower只有一次投票機會，若群集數量足夠，則可以避免同時將多個Candidate升級為Leader。但在少量集群的情況下，若選舉過程中Candidate比Follower更多，所有的Candidate都會無法升級為Leader，結果會導致阻塞系統多個選舉期。

1.2 最終一致性保證

Raft模型中只有Leader能夠執行寫操作，當Leader接受寫操作時，就更新寫日志，同時對Leader管理的Follower進行同步復制。為了確保可用性，只有在其他Follower全部同步完成之后，才會將所讀請求負載均衡地分配給各個服務器，否則讀操作會全部轉發到Leader中操作。

1.3 Raft日志

對于Raft模型來說，每臺服務器無論是領導者還是跟隨者，都各自保存一份日志。日志來自于客戶端的請求，其本身被分成了多條記錄，記錄是由下標索引的位置來進行確定其唯一性。在記錄中有兩個主要信息：（1）每條記錄都包括一條供狀態機執行的命令，命令的格式可以是客戶端與狀態機所達成一致的某種格式。（2）每條記錄都包括一個任期號，這個任期號是該條記錄創建時，領導者所處的任期。隨著日志記錄的增多，這個任期號也會單調上升。每臺服務器都必須保證日志能在崩潰后還可以恢復，所以日志通常是存于磁盤或其他穩定的存儲介質中。無論服務器作何更新，它都需要在接收到其他服務器的響應之前將內容寫入磁盤。如果某條記錄在大多數服務器的日志中都存在，那么我們就稱該條記錄已提交(Committed)。如果一條記錄是已提交的，那么它就能安全的被狀態機執行，Raft 就可保證該條記錄的持久性。

1.4 Raft日志一致性

Raft期望能將集群日志維持高水準的一致性。理想狀態下，所有日志在任何時候信息都是相同的，甚至是服務器崩潰時也如此。雖難以達到理想狀態，但Raft會盡可能地保證在所有服務器上的日志是一樣的。

日志記錄的索引以及任期號在任何時候都是有效的，他們的組合可以唯一地標識每一條日志的記錄。如果在不同的服務器中有兩條記錄的索引是相同的，任期號也是相同的，那么就可以保證它們所存儲的記錄也是相同的。除此之外，還能保證在這條記錄之前的所有記錄都能一一對應。所以任期號和索引的組合可以保證整個日志的起始位置至該點位置的記錄的一致性。如果某條記錄是已提交的，那么在該記錄之前的記錄都應該處于已提交狀態。

2 Raft模型針對小集群優化方案

2.1 同步方案——網狀同步

在同步方案中，我們不采用Raft的原本同步方案，Leader不再主動進行心跳檢測，而是讓Follower進行定期向Leader報告當前信息。Leader會添加Follower集合和Leader集合的差集，然后將其發送給Follower最新的集群集合。通過這種方式，我們可以確保所有Follower都能在一個周期內與Leader維護系統的集群集合相同，實現網狀同步。

如圖1所示，若服務器在接入時因為網絡等問題發生故障，導致Follower相對于Leader發生分區（圖1左），就不可實現分布式的可用性。但在經過上述過程（網狀同步）之后，Follower會重新被分配到Leader上，同時該服務器會對Leader進行同步，從而解決分區問題。

2.2 選舉問題優化方案——繼承

上文提到了當 Leader發生宕機時 Raft模型所提供的解決方案，并提到了在該解決方案中由于集群較小，服務器數量較少可能導致多個選舉周期阻塞問題。該問題的關鍵在于同一時間有多個Follower升級為Candidate的投票分歧問題。吳奕等[5]提出了為每個節點設置C標志位的策略。但該方法適用于具有大量節點的集群。那么我們在小集群中可以選擇使用Leader定期地選擇出下一個Candidate的方法來解決該問題。在 Leader發生宕機之后，Candidate經過其他 Follower同意便可繼承 Leader的角色（這里為了確定Leader發生宕機問題，Candidate不可以直接升級為Leader，要由半數以上的Follower同意后才可以升級為Leader）。同時 Raft算法中的周期選舉被替換為周期分配。在周期分配模式中，Leader將為所維護的節點集合分配角色，包括一個 Candidate和多個Follower。

2.3 優化后每個節點的工作流程

如圖2所示：在優化之后，每個服務器在一個工作周期中執行以下任務：Leader：定期發送任命報告，為每個服務器分配新的角色。Candidate：定期檢查Leader的存活狀態，若發現宕機就讓Follower進行檢測，一旦有一半以上的Follower檢測到Leader不在線，則Candidate將立即升級為Leader，并為所有的Follower分配新角色。若當Leader在線時，Candidate也會進行Follower的工作。Follower：定期上報服務器集合狀態，更新最新的服務器集合。

2.4 優化效果

以上的優化，在我們用Goland語言設計的goDFS——分布式文件系統中得到實現。在實驗過程中可實現網狀同步。在選舉過程中，通過Leader定期地選擇出下一個Candidate，不再使用Raft模型原始的選舉方法，可以有效避免同時產生多個Candidate，避免不斷重新選舉導致系統堵塞的情況。

在選舉過程中，Leader通過繼承的方式定期地選擇出下一個Candidate。雖然該方法使Leader和Candidate同時宕機的概率非常小，但在實驗中我們也手動停止Leader和Candidate的運行，結果是會導致集群崩潰，說明該算法后期還需進行優化。

2.5 優化后的集群失效問題

通過上述說明，繼承模式相對于選舉模式而言，不會產生多個Candidate競爭所引起的選舉周期阻塞問題，在Leader正常的情況下有更小的開銷。但繼承模式相對于選舉模式來說安全性較低，如當Candidate和Leader同時宕機時，則不能將其恢復為正常狀態，即Leader會失效。對于小型集群來說，Leader的壓力更大，而Candidate和Leader同時宕機的概率是極小的。而且在少量機器中，兩個節點同時失效，也會使集群崩潰。但在一般情況下，小集群中使用繼承模式是可以保證集群穩定運行，且一定程度上可解決小集群同步問題。

2.6 繼承失敗問題以及解決方案

繼承的解決方案雖然一定程度上解決了Raft競爭選舉中斷導致的多集群問題，但是繼承方案仍然存在一定的問題，如可能發生Leader和Candidate同時掛機的情況（在Leader重新任命一個Candidate之前，Leade發生故障，并且同時Candidate也發生故障導致導致節點繼承失敗）。對于該問題我們可以對選舉流程進行優化。一種可行的方法是，Leader在選舉時可以指定多個Candidate作為候選者，通過對Candidate的冗余來解決上述問題。當Leader和其中一個或多個Candidate宕機時，其他Candidate可以再次請求Follower進行投票來選舉Leader。但同時，也會引入多個Candidate競爭的問題，這時我們可以控制在選舉Leader時對 Candidate進行排序，使得 Candidate形成線性關聯關系，即使在選舉過程中發生多個Candidate升級為多個Leader的問題，也會在下一個周期由最高級別的Candidate（Leader）發生網狀同步來恢復集群的一致性。但系統在一段時間可能會出現多個集群，即便恢復后，也有可能發生日志的沖突，因此需要一定的時間進行恢復。

第二種方法是由Candidate選擇一個服務器進行信息備份，Candidate的備份服務器會監聽Candidate的狀態。當Candidate以及Leader都發生宕機時，Candidate的備份服務器則會進行繼承升級，成為新的Leader。雖然這種方案并沒有從根本上解決Leader以及Candidate同時失效的問題，但是在集群數量較少的情況下，Candidate以及Leader都發生宕機后，則整個系統大概率將會進入降級或者不可用的狀態，所以在一定程度上可以解決Leader以及Candidate同時失效的問題。

3 結語

本文針對Raft模型在小集群情況下對Leader選舉方案和日志同步方案進行優化，但仍有些問題需要探討和研究。如在選舉過程中我們采用的是繼承的方法，通過Leader狀態的服務器定期地選擇出下一個Candidate。但該方法可能會出現Leader和Candidate同時宕機的極小概率情況，在小集群中會導致集群崩潰。在3.5所提的方法中，Leader在選舉時指定多個Candidate作為候選者的方法會使得某段時間內系統出現多個集群，需要一定的時間來進行恢復，即便恢復后，日志也有可能發生沖突，所以恢復所需要的時間具有不確定性。但在小集群中由于節點少，同步日志的時間和恢復時間仍然是較短的，因此該方法仍然具有一定的可行性。另一種方法是由Candidate選擇一個服務器進行信息備份，這種方案并沒有從根本上解決Leader和Candidate同時宕機的問題，但Candidate 和Leader同時宕機大概率會使得系統將會進入降級狀態或者崩潰不可用，所以該方法在小集群中的使用仍然具有一定的適用性。因此這些問題優化的設計和實現后期仍有待研究。