本文是介紹Raft分布式共識算法及其Go完整實(shí)現(xiàn)系列文章中的第一篇慈格。以下是完整的列表:

• 第1部分：介紹(本文)
• 第2部分:選舉
• 第3部分:命令和日志復(fù)制
• 第4部分:持久性和優(yōu)化

Raft是一個相對較新的算法（2014年被實(shí)現(xiàn)）失暂，但它已經(jīng)在工業(yè)中得到了廣泛的應(yīng)用。最知名的例子可能是Kubernetes可很，它通過etcd分布式鍵值存儲依賴Raft诗力。

本系列文章的目標(biāo)是介紹一個功能完整且經(jīng)過嚴(yán)格測試的Raft實(shí)現(xiàn)，并提供一些關(guān)于Raft如何工作的例子我抠。這些并不是學(xué)習(xí)Raft的唯一資源苇本。我猜你至少讀過一次《Raft》的論文；此外菜拓，我強(qiáng)烈建議你花點(diǎn)時間仔細(xì)閱讀Raft網(wǎng)站上的資源——觀看一兩個原作者的演講瓣窄，以及raft的可視化演示，以及瀏覽Ongaro的博士論文了解更多細(xì)節(jié)纳鼎。

不要期望在一天內(nèi)完全掌握Raft俺夕。盡管它的設(shè)計(jì)比Paxos更容易理解喷橙，但《Raft》仍然相當(dāng)復(fù)雜啥么。它要解決分布式共識問題——是一個困難的問題贰逾，所以解決方案的復(fù)雜性有一個自然的下限氯迂。

狀態(tài)機(jī)副本

分布式共識算法可以看作是解決跨多個服務(wù)器復(fù)制確定性狀態(tài)機(jī)的問題。術(shù)語狀態(tài)機(jī)用于表示任意的服務(wù)；畢竟导帝，狀態(tài)機(jī)是計(jì)算機(jī)科學(xué)的基礎(chǔ)之一守谓，任何事物都可以用它來表示。數(shù)據(jù)庫您单、文件服務(wù)器斋荞、鎖服務(wù)器等都可以被認(rèn)為是復(fù)雜的狀態(tài)機(jī)。

考慮由狀態(tài)機(jī)表示的某些服務(wù)虐秦。多個客戶端可以連接到它并發(fā)出請求平酿，期望得到響應(yīng):

只要執(zhí)行狀態(tài)機(jī)的服務(wù)器是可靠的，這個系統(tǒng)就能正常工作悦陋。如果服務(wù)器崩潰蜈彼，我們的服務(wù)變得不可用，這可能是不可接受的叨恨。一般來說柳刮，我們的系統(tǒng)和運(yùn)行它的單個服務(wù)器一樣的可靠程度時一樣的挖垛。

提高服務(wù)可靠性的常用方法是通過復(fù)制(副本)痒钝。我們可以在不同的服務(wù)器上運(yùn)行服務(wù)的多個實(shí)例。創(chuàng)建一個協(xié)同工作的服務(wù)器集群來提供服務(wù)痢毒，任何一個服務(wù)器崩潰都不會導(dǎo)致整個服務(wù)不可用送矩。通過服務(wù)器之間的隔離，是消除同時影響多個服務(wù)器的常見故障的方法哪替，進(jìn)一步提高了可靠性栋荸。

客戶端不再和單個服務(wù)器通信來執(zhí)行服務(wù)，而是和整個集群通信凭舶。此外晌块，組成集群的服務(wù)器必須彼此通信，以正確地復(fù)制狀態(tài):

圖中的每個狀態(tài)機(jī)都是服務(wù)的副本帅霜。其思想是匆背，所有狀態(tài)機(jī)都是同步執(zhí)行的，從客戶端請求中獲取相同的輸入并執(zhí)行相同的狀態(tài)轉(zhuǎn)換身冀。這確保了即使某些服務(wù)器出現(xiàn)故障钝尸，它們也會向客戶端返回相同的結(jié)果。Raft是一個實(shí)現(xiàn)這一功能的算法搂根。

這里需要對本系列文章將反復(fù)使用的一些術(shù)語進(jìn)行介紹:

• service：是正在實(shí)現(xiàn)的分布式系統(tǒng)的提供的服務(wù)珍促。例如，鍵值數(shù)據(jù)庫剩愧。
• Server和Replica：通過網(wǎng)絡(luò)連接運(yùn)行raft算法的服務(wù)器猪叙，能為客戶度提供相應(yīng)的服務(wù)。
• cluster：一組協(xié)同實(shí)現(xiàn)分布式服務(wù)的Raft服務(wù)器。典型的集群大小是3或5穴翩。

共識模塊和Raft日志

下面介紹上圖中顯示的狀態(tài)機(jī)內(nèi)部情況成洗。Raft是一種通用算法，它并不規(guī)定服務(wù)如何在狀態(tài)機(jī)中實(shí)現(xiàn)藏否。它的目標(biāo)是能夠可靠地瓶殃、確定地記錄并將輸入序列(在Raft中也稱為命令)復(fù)制到狀態(tài)機(jī)。給定一個初始狀態(tài)和所有輸入副签，可以完全準(zhǔn)確地重放狀態(tài)機(jī)遥椿。換句話說：如果我們?nèi)∠嗤瑺顟B(tài)機(jī)的兩個獨(dú)立副本，并從相同的初始狀態(tài)開始為它們提供相同的輸入序列淆储，那么狀態(tài)機(jī)將以相同的狀態(tài)結(jié)束冠场，并在此過程中產(chǎn)生相同的輸出。
以下是使用Raft的通用服務(wù)的結(jié)構(gòu):

關(guān)于這些組件的更多細(xì)節(jié):

• 狀態(tài)機(jī)與我們上面看到的狀態(tài)機(jī)相同本砰。它代表了任意服務(wù)碴裙；鍵值存儲是說明Raft時的一個常見示例。
• 日志是存儲客戶端發(fā)出的所有命令(輸入)的地方点额。這些命令不會直接應(yīng)用到狀態(tài)機(jī)舔株；相反，Raft會在它們被成功復(fù)制到大多數(shù)服務(wù)器時執(zhí)行它們还棱。此外载慈，該日志是持久性的——它保存在未發(fā)生故障服務(wù)器存儲上，并可用于在崩潰后恢復(fù)狀態(tài)機(jī)珍手。
• 共識模塊是Raft算法的核心办铡；它接受來自客戶端的命令，確保將它們保存在日志中琳要，將它們復(fù)制到集群中的其他Raft服務(wù)器上(與上一個圖中的綠色箭頭相同)寡具，并在確認(rèn)狀態(tài)機(jī)安全時將它們提交到狀態(tài)機(jī)。提交到狀態(tài)機(jī)并通知客戶端請求結(jié)果稚补。
  如果你還不是很清楚童叠，不要擔(dān)心。本系列剩下的文章將詳細(xì)解釋其中的內(nèi)容!

領(lǐng)導(dǎo)者和跟隨者（leaders和followers）

Raft使用了一個強(qiáng)領(lǐng)導(dǎo)者模型孔厉，其中集群中的一個副本作為領(lǐng)導(dǎo)者拯钻，其他副本作為跟隨者。領(lǐng)導(dǎo)者負(fù)責(zé)響應(yīng)客戶的請求撰豺，將命令復(fù)制給跟隨者粪般，并將響應(yīng)返回給客戶。

在正常操作期間污桦，跟隨者(follower)的目標(biāo)只是簡單地復(fù)制領(lǐng)導(dǎo)者的日志亩歹。在領(lǐng)導(dǎo)者故障或網(wǎng)絡(luò)分區(qū)的情況下，一個跟隨者可以接管領(lǐng)導(dǎo)者，服務(wù)仍然可用小作。

這個模型有其優(yōu)點(diǎn)和缺點(diǎn)亭姥，一個顯著的優(yōu)點(diǎn)是簡單。數(shù)據(jù)總是從領(lǐng)導(dǎo)者流向跟隨者顾稀，只有領(lǐng)導(dǎo)者才會回應(yīng)客戶端的請求达罗。這使得Raft集群更容易分析、測試和調(diào)試静秆。缺點(diǎn)是性能——由于集群中只有一個服務(wù)器與客戶端通信粮揉，這可能成為客戶端請求激增時的瓶頸。對此問題的答案通常是抚笔，Raft不應(yīng)該用于大流量的服務(wù)扶认。它更適合一致性至關(guān)重要、低流量的場景殊橙，但可能會犧牲可用性——我們將在容錯一節(jié)說明這一點(diǎn)辐宾。

客戶端交互

之前，說過“客戶端不再聯(lián)系單個服務(wù)器來請求服務(wù)膨蛮，而是聯(lián)系整個集群”;但這意味著什么呢叠纹？集群只是通過網(wǎng)絡(luò)連接的一組服務(wù)器，那么如何聯(lián)系“整個集群”呢鸽疾？
答案很簡答：

• 當(dāng)使用Raft集群時吊洼，客戶端知道集群副本的網(wǎng)絡(luò)地址训貌。它是如何知道這一點(diǎn)(例如制肮，通過使用某種服務(wù)發(fā)現(xiàn)機(jī)制)這些超出了本文的討論范圍。
• 客戶端首先向任意副本服務(wù)端發(fā)送請求递沪。如果這個副本是leader豺鼻，它立即確認(rèn)請求，客戶端將等待完整的響應(yīng)款慨。在此之后儒飒，客戶端記住這個副本是leader，就不必再搜索它了(直到出現(xiàn)失敗檩奠，比如leader崩潰)桩了。
• 如果副本服務(wù)端返回它不是leader，客戶端將嘗試另一個副本埠戳。這里一個可能的優(yōu)化是井誉，一個follower副本可以告訴客戶端哪個副本是leader。由于副本之間不斷地通信整胃，通常知道leader是哪個颗圣。這可以節(jié)省客戶端幾次通信。
• 另一種情況是，如果請求在某個超時時間內(nèi)沒有提交在岂，客戶端會意識到它所請求的副本不是leader奔则。(如果它仍然認(rèn)為它是)——它可能已經(jīng)從其他Raft服務(wù)器中被分區(qū)了。當(dāng)超時結(jié)束時蔽午，客戶端將繼續(xù)搜索另一個leader易茬。

第三個要點(diǎn)中提到的優(yōu)化在大多數(shù)情況下是不必要的。一般來說及老，在Raft中區(qū)分“正常操作”和“故障場景”是很有用的疾呻。一個典型的服務(wù)將花費(fèi)99.9%的時間在“正常操作”中，在“正常操作”中写半，客戶端知道誰是領(lǐng)導(dǎo)者岸蜗，因?yàn)樵诘谝淮温?lián)系服務(wù)時緩存了這些信息。故障場景——我們將在下一節(jié)中更詳細(xì)地討論——肯定會麻煩點(diǎn)叠蝇，但只會持續(xù)很短的時間璃岳。我們將在下一篇文章中詳細(xì)了解到，Raft集群可以非常迅速地從臨時服務(wù)器故障或網(wǎng)絡(luò)分區(qū)中恢復(fù)——在大多數(shù)情況下悔捶，恢復(fù)時間不到一秒鐘铃慷。當(dāng)在新的領(lǐng)導(dǎo)者選舉成功之前，服務(wù)將會有短暫的不可用蜕该，但之后它將回到“正常運(yùn)行模式”犁柜。

Raft中的容錯和CAP定理

讓我們回顧一下三個Raft副本的狀態(tài)圖，沒有連接客戶端:

在這個集群中堂淡，我們可能會遇到哪些類型的故障?
現(xiàn)代計(jì)算機(jī)中的每個組件都可能發(fā)生故障馋缅，但為了讓討論更容易一些，我們將運(yùn)行Raft實(shí)例的服務(wù)器視為一個原子單元绢淀。只留下兩種主要的失敗類型:
1萤悴、服務(wù)器故障：其中一個服務(wù)器停止響應(yīng)所有網(wǎng)絡(luò)流量一段時間。故障的服務(wù)器通常會重新啟動皆的，并可能在短暫中斷后恢復(fù)聯(lián)機(jī)覆履。
2、網(wǎng)絡(luò)分區(qū)：由于網(wǎng)絡(luò)設(shè)備或傳輸介質(zhì)出現(xiàn)問題费薄，一個或多個服務(wù)器與其他服務(wù)器和/或客戶端斷開連接硝全。

從服務(wù)器A和服務(wù)器B通信的角度看，B服務(wù)器故障的話楞抡，在A和B之間是無法區(qū)分的伟众。表現(xiàn)形式都一樣-A停止接收來自B的消息。從系統(tǒng)級別的角度看拌倍，網(wǎng)絡(luò)分區(qū)很難處理赂鲤，因?yàn)橥瑫r影響多個服務(wù)器噪径。在本系列的下一部分中，我們將討論由于分區(qū)而產(chǎn)生的一些棘手的場景数初。

為了能夠優(yōu)雅地處理任意的網(wǎng)絡(luò)分區(qū)和服務(wù)器故障找爱，Raft要求集群中的大多數(shù)服務(wù)器在任何給定的時刻都處于可用狀態(tài)，這是為了能夠?qū)崿F(xiàn)選舉泡孩。對于3個服務(wù)器车摄，Raft可以容忍單個服務(wù)器故障。如果有5個服務(wù)器仑鸥，它可以容忍2個吮播；對于2N+1個服務(wù)器，它可以容忍N(yùn)個服務(wù)器故障眼俊。

這就引出了CAP定理意狠，其實(shí)際結(jié)果是，存在網(wǎng)絡(luò)分區(qū)(這是現(xiàn)實(shí)中不可避免的一部分)的情況下疮胖，我們必須小心地平衡可用性和一致性环戈。在這種平衡中，Raft堅(jiān)定地站在一致性陣營澎灸。它的宗旨是防止集群可能出現(xiàn)不一致的狀態(tài)院塞，即不同的客戶端接收到不同的結(jié)果。為了實(shí)現(xiàn)這一目標(biāo)性昭，Raft犧牲了可用性拦止。

正如我前面提到的，Raft不是為高吞吐量糜颠、細(xì)粒度服務(wù)而設(shè)計(jì)的汹族。每個客戶端請求都會觸發(fā)相當(dāng)多的工作——Raft服務(wù)器之間的通信，以便將其復(fù)制到大多數(shù)跟隨者括蝠，并將其持久化鞠抑；這一切都發(fā)生在客戶端得到響應(yīng)之前。

因此忌警，你不會設(shè)計(jì)一個多副本數(shù)據(jù)庫，讓所有客戶端請求都通過Raft秒梳，那就太慢了法绵。Raft更適合于粗粒度的分布式原語——比如實(shí)現(xiàn)鎖服務(wù)器、為更高級別的協(xié)議選擇領(lǐng)導(dǎo)者酪碘、在分布式系統(tǒng)中復(fù)制關(guān)鍵配置數(shù)據(jù)等等朋譬。