摘自Raft一致性算法論文：https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
github上開源的raft實現(xiàn)：https://raft.github.io/#implementations

一、paxos算法的缺點說起

• Paxos 有兩個致命的缺點。第一個是 Paxos 太難以理解。它的完整的解釋晦澀難懂；很少有人能完全理解，只有少數(shù)人成功的讀懂了它。并且大家做了許多努力來用一些簡單的術(shù)語來描述它。盡管這些解釋都關(guān)注于單一決策子集問題，但仍具有挑戰(zhàn)性。在 NSDI 2012 會議上的一次非正式調(diào)查顯示，我們發(fā)現(xiàn)大家對 Paxos 都感到不滿意，其中甚至包括一些有經(jīng)驗的研究員。
• Paxos 的第二個缺點是它難以在實際環(huán)境中實現(xiàn)。其中一個原因是，對于多決策 Paxos （multi-Paxos） ，大家還沒有一個一致同意的算法。Lamport 的描述大部分都是有關(guān)于單決策 Paxos （single-decree Paxos）；他僅僅描述了實現(xiàn)多決策的可能的方法，缺少許多細(xì)節(jié)。有許多實現(xiàn) Paxos 和優(yōu)化 Paxos 的嘗試，但是他們都和 Lamport 的描述有些出入。另外，Paxos 的結(jié)構(gòu)也是不容易在一個實際系統(tǒng)中進(jìn)行實現(xiàn)的，這是單決策問題分解帶來的又一個問題。

Paxos 算法的描述與實際實現(xiàn)之間存在巨大的鴻溝…最終的系統(tǒng)往往建立在一個沒有被證明的算法之上。

二、Raft算法

• 正因為存在這些問題，認(rèn)為 Paxos 不僅對于系統(tǒng)的構(gòu)建者來說不友好，同時也不利于教學(xué)。鑒于一致性算法對于大規(guī)模軟件系統(tǒng)的重要性，試著來設(shè)計一種另外的比 Paxos 更好的一致性算法。Raft 就是這樣的一個算法。
• Raft 是一種用來管理日志復(fù)制的一致性算法。它和 Paxos 的性能和功能是一樣的，但是它和 Paxos 的結(jié)構(gòu)不一樣；這使得 Raft 更容易理解并且更易于建立實際的系統(tǒng)。為了提高理解性，Raft 將一致性算法分為了幾個部分，例如領(lǐng)導(dǎo)選?。╨eader selection），日志復(fù)制（log replication）和安全性（safety），同時它使用了更強(qiáng)的一致性來減少了必須需要考慮的狀態(tài)。

1、復(fù)制狀態(tài)機(jī)

• 一致性算法是從復(fù)制狀態(tài)機(jī)的背景下提出的。在這種方法中，一組服務(wù)器上的狀態(tài)機(jī)產(chǎn)生相同狀態(tài)的副本，并且在一些機(jī)器宕掉的情況下也可以繼續(xù)運行。復(fù)制狀態(tài)機(jī)在分布式系統(tǒng)中被用于解決很多容錯的問題。例如，大規(guī)模的系統(tǒng)中通常都有一個集群領(lǐng)導(dǎo)者，像 GFS、HDFS 和 RAMCloud，典型應(yīng)用就是一個獨立的的復(fù)制狀態(tài)機(jī)去管理領(lǐng)導(dǎo)選舉和存儲配置信息并且在領(lǐng)導(dǎo)人宕機(jī)的情況下也要存活下來。比如 Chubby 和 ZooKeeper。
  
  復(fù)制狀態(tài)機(jī)結(jié)構(gòu)
• 復(fù)制狀態(tài)機(jī)通常都是基于復(fù)制日志實現(xiàn)的，每一個服務(wù)器存儲一個包含一系列指令的日志，并且按照日志的順序進(jìn)行執(zhí)行。每一個日志都按照相同的順序包含相同的指令，所以每一個服務(wù)器都執(zhí)行相同的指令序列。因為每個狀態(tài)機(jī)都是確定的，每一次執(zhí)行操作都產(chǎn)生相同的狀態(tài)和同樣的序列。
• 保證復(fù)制日志相同就是一致性算法的工作了。在一臺服務(wù)器上，一致性模塊接收客戶端發(fā)送來的指令然后增加到自己的日志中去。它和其他服務(wù)器上的一致性模塊進(jìn)行通信來保證每一個服務(wù)器上的日志最終都以相同的順序包含相同的請求，盡管有些服務(wù)器會宕機(jī)。一旦指令被正確的復(fù)制，每一個服務(wù)器的狀態(tài)機(jī)按照日志順序處理他們，然后輸出結(jié)果被返回給客戶端。因此，服務(wù)器集群看起來形成一個高可靠的狀態(tài)機(jī)。

2、一致性算法應(yīng)該有的特征

1、確保安全性（從來不會返回一個錯誤的結(jié)果），即使在所有的非拜占庭（Non-Byzantine）情況下，包括網(wǎng)絡(luò)延遲、分區(qū)、丟包、冗余和亂序的情況下。
2、高可用性，只要集群中的大部分機(jī)器都能運行，可以互相通信并且可以和客戶端通信，這個集群就可用。因此，一般來說，一個擁有 5 臺機(jī)器的集群可以容忍其中的 2 臺的失?。╢ail）。服務(wù)器停止工作了我們就認(rèn)為它失?。╢ail）了，沒準(zhǔn)一會當(dāng)它們擁有穩(wěn)定的存儲時就能從中恢復(fù)過來，重新加入到集群中。
3、不依賴時序保證一致性，時鐘錯誤和極端情況下的消息延遲在最壞的情況下才會引起可用性問題
4、不依賴時序保證一致性，時鐘錯誤和極端情況下的消息延遲在最壞的情況下才會引起可用性問題

3、Raft算法分解

• 算法實現(xiàn)過程：Raft 通過首先選出一個領(lǐng)導(dǎo)人來實現(xiàn)一致性，然后給予領(lǐng)導(dǎo)人完全管理復(fù)制日志（replicated log）的責(zé)任。領(lǐng)導(dǎo)人接收來自客戶端的日志條目，并把它們復(fù)制到其他的服務(wù)器上，領(lǐng)帶人還要告訴服務(wù)器們什么時候?qū)⑷罩緱l目應(yīng)用到它們的狀態(tài)機(jī)是安全的。通過選出領(lǐng)導(dǎo)人能夠簡化復(fù)制日志的管理工作。例如，領(lǐng)導(dǎo)人能夠決定將新的日志條目放到哪，而并不需要和其他的服務(wù)器商議，數(shù)據(jù)流被簡化成從領(lǐng)導(dǎo)人流向其他服務(wù)器。如果領(lǐng)導(dǎo)人宕機(jī)或者和其他服務(wù)器失去連接，就可以選取下一個領(lǐng)導(dǎo)人。
• 通過選出領(lǐng)導(dǎo)人，Raft 將一致性問題分解成為三個相對獨立的子問題：

1、領(lǐng)導(dǎo)人選?。↙eader election）： 在一個領(lǐng)導(dǎo)人宕機(jī)之后必須要選取一個新的領(lǐng)導(dǎo)人
2、日志復(fù)制（Log replication）： 領(lǐng)導(dǎo)人必須從客戶端接收日志然后復(fù)制到集群中的其他服務(wù)器，并且強(qiáng)制要求其他服務(wù)器的日志保持和自己相同
3、安全性（Safety）：如果一個服務(wù)器已經(jīng)將給定索引位置的日志條目應(yīng)用到狀態(tài)機(jī)中，則所有其他服務(wù)器不會在該索引位置應(yīng)用不同的條目

4、Raft基礎(chǔ)

• 一個 Raft 集群包含若干個服務(wù)器節(jié)點；通常是 5 個，這允許整個系統(tǒng)容忍 2 個節(jié)點的失效。在任何時刻，每一個服務(wù)器節(jié)點都處于這三個狀態(tài)之一：領(lǐng)導(dǎo)人、跟隨者或者候選人。在通常情況下，系統(tǒng)中只有一個領(lǐng)導(dǎo)人并且其他的節(jié)點全部都是跟隨者。跟隨者都是被動的：他們不會發(fā)送任何請求，只是簡單的響應(yīng)來自領(lǐng)導(dǎo)者或者候選人的請求。領(lǐng)導(dǎo)人處理所有的客戶端請求（如果一個客戶端和跟隨者聯(lián)系，那么跟隨者會把請求重定向給領(lǐng)導(dǎo)人）。候選人選舉新領(lǐng)導(dǎo)人時使用的。
  
  服務(wù)器狀態(tài)

跟隨者只響應(yīng)來自其他服務(wù)器的請求。如果跟隨者接收不到消息，那么他就會變成候選人并發(fā)起一次選舉。獲得集群中大多數(shù)選票的候選人將成為領(lǐng)導(dǎo)者。在一個任期內(nèi)，領(lǐng)導(dǎo)人一直都會是領(lǐng)導(dǎo)人直到自己宕機(jī)了。

領(lǐng)導(dǎo)選舉時序

時間被劃分成一個個的任期，每個任期開始都是一次選舉。在選舉成功后，領(lǐng)導(dǎo)人會管理整個集群直到任期結(jié)束。有時候選舉會失敗，那么這個任期就會沒有領(lǐng)導(dǎo)人而結(jié)束。任期之間的切換可以在不同的時間不同的服務(wù)器上觀察到。Raft 保證了在一個給定的任期內(nèi)，最多只有一個領(lǐng)導(dǎo)者。
(不同的服務(wù)器節(jié)點可能多次觀察到任期之間的轉(zhuǎn)換，但在某些情況下，一個節(jié)點也可能觀察不到任何一次選舉或者整個任期全程。任期在 Raft 算法中充當(dāng)邏輯時鐘的作用，這會允許服務(wù)器節(jié)點查明一些過期的信息比如陳舊的領(lǐng)導(dǎo)者。每一個節(jié)點存儲一個當(dāng)前任期號，這一編號在整個時期內(nèi)單調(diào)的增長。當(dāng)服務(wù)器之間通信的時候會交換當(dāng)前任期號；如果一個服務(wù)器的當(dāng)前任期號比其他人小，那么他會更新自己的編號到較大的編號值。如果一個候選人或者領(lǐng)導(dǎo)者發(fā)現(xiàn)自己的任期號過期了，那么他會立即恢復(fù)成跟隨者狀態(tài)。如果一個節(jié)點接收到一個包含過期的任期號的請求，那么他會直接拒絕這個請求。)

• Raft 算法中服務(wù)器節(jié)點之間通信使用遠(yuǎn)程過程調(diào)用（RPCs），并且基本的一致性算法只需要兩種類型的 RPCs。請求投票（RequestVote） RPCs 由候選人在選舉期間發(fā)起，然后附加條目（AppendEntries）RPCs 由領(lǐng)導(dǎo)人發(fā)起，用來復(fù)制日志和提供一種心跳機(jī)制。為了在服務(wù)器之間傳輸快照增加了第三種 RPC。當(dāng)服務(wù)器沒有及時的收到 RPC 的響應(yīng)時，會進(jìn)行重試， 并且他們能夠并行的發(fā)起 RPCs 來獲得最佳的性能。

5、領(lǐng)導(dǎo)人選舉

• Raft 使用一種心跳機(jī)制來觸發(fā)領(lǐng)導(dǎo)人選舉。當(dāng)服務(wù)器程序啟動時，他們都是跟隨者身份。一個服務(wù)器節(jié)點繼續(xù)保持著跟隨者狀態(tài)只要他從領(lǐng)導(dǎo)人或者候選者處接收到有效的 RPCs。領(lǐng)導(dǎo)者周期性的向所有跟隨者發(fā)送心跳包（即不包含日志項內(nèi)容的附加日志項 RPCs）來維持自己的權(quán)威。如果一個跟隨者在一段時間里沒有接收到任何消息，也就是選舉超時，那么他就會認(rèn)為系統(tǒng)中沒有可用的領(lǐng)導(dǎo)者,并且發(fā)起選舉以選出新的領(lǐng)導(dǎo)者。
  （1）要開始一次選舉過程，跟隨者先要增加自己的當(dāng)前任期號并且轉(zhuǎn)換到候選人狀態(tài)。然后他會并行的向集群中的其他服務(wù)器節(jié)點發(fā)送請求投票的 RPCs 來給自己投票。候選人會繼續(xù)保持著當(dāng)前狀態(tài)直到以下三件事情之一發(fā)生：(a) 他自己贏得了這次的選舉，(b) 其他的服務(wù)器成為領(lǐng)導(dǎo)者，(c) 一段時間之后沒有任何一個獲勝的人。
  （2）情況一：當(dāng)一個候選人從整個集群的大多數(shù)服務(wù)器節(jié)點獲得了針對同一個任期號的選票，那么他就贏得了這次選舉并成為領(lǐng)導(dǎo)人。每一個服務(wù)器最多會對一個任期號投出一張選票，按照先來先服務(wù)的原則，要求大多數(shù)選票的規(guī)則確保了最多只會有一個候選人贏得此次選舉。一旦候選人贏得選舉，他就立即成為領(lǐng)導(dǎo)人。然后他會向其他的服務(wù)器發(fā)送心跳消息來建立自己的權(quán)威并且阻止新的領(lǐng)導(dǎo)人的產(chǎn)生。
  （3）情況二：在等待投票的時候，候選人可能會從其他的服務(wù)器接收到聲明它是領(lǐng)導(dǎo)人的附加日志項 RPC。如果這個領(lǐng)導(dǎo)人的任期號（包含在此次的 RPC中）不小于候選人當(dāng)前的任期號，那么候選人會承認(rèn)領(lǐng)導(dǎo)人合法并回到跟隨者狀態(tài)。 如果此次 RPC 中的任期號比自己小，那么候選人就會拒絕這次的 RPC 并且繼續(xù)保持候選人狀態(tài)。
  （4）情況三：候選人既沒有贏得選舉也沒有輸：如果有多個跟隨者同時成為候選人，那么選票可能會被瓜分以至于沒有候選人可以贏得大多數(shù)人的支持。當(dāng)這種情況發(fā)生的時候，每一個候選人都會超時，然后通過增加當(dāng)前任期號來開始一輪新的選舉。然而，沒有其他機(jī)制的話，選票可能會被無限的重復(fù)瓜分。

Raft 算法使用隨機(jī)選舉超時時間的方法來確保很少會發(fā)生選票瓜分的情況，就算發(fā)生也能很快的解決。為了阻止選票起初就被瓜分，選舉超時時間是從一個固定的區(qū)間（例如 150-300 毫秒）隨機(jī)選擇。這樣可以把服務(wù)器都分散開以至于在大多數(shù)情況下只有一個服務(wù)器會選舉超時；然后他贏得選舉并在其他服務(wù)器超時之前發(fā)送心跳包。同樣的機(jī)制被用在選票瓜分的情況下。每一個候選人在開始一次選舉的時候會重置一個隨機(jī)的選舉超時時間，然后在超時時間內(nèi)等待投票的結(jié)果；這樣減少了在新的選舉中另外的選票瓜分的可能性。

6、日志復(fù)制

• 一旦一個領(lǐng)導(dǎo)人被選舉出來，他就開始為客戶端提供服務(wù)。客戶端的每一個請求都包含一條被復(fù)制狀態(tài)機(jī)執(zhí)行的指令。領(lǐng)導(dǎo)人把這條指令作為一條新的日志條目附加到日志中去，然后并行的發(fā)起附加條目 RPCs 給其他的服務(wù)器，讓他們復(fù)制這條日志條目。

• 當(dāng)這條日志條目被安全的復(fù)制，領(lǐng)導(dǎo)人會應(yīng)用這條日志條目到它的狀態(tài)機(jī)中然后把執(zhí)行的結(jié)果返回給客戶端。如果跟隨者崩潰或者運行緩慢，再或者網(wǎng)絡(luò)丟包，領(lǐng)導(dǎo)人會不斷的重復(fù)嘗試附加日志條目 RPCs （盡管已經(jīng)回復(fù)了客戶端）直到所有的跟隨者都最終存儲了所有的日志條目。

  
  
  日志結(jié)構(gòu)

日志由有序序號標(biāo)記的條目組成。每個條目都包含創(chuàng)建時的任期號（圖中框中的數(shù)字,從領(lǐng)導(dǎo)者獲取），和一個狀態(tài)機(jī)需要執(zhí)行的指令。每一條日志條目同時也都有一個整數(shù)索引值來表明它在日志中的位置。一個條目當(dāng)可以安全的被應(yīng)用到狀態(tài)機(jī)中去的時候，就認(rèn)為是可以提交了。

• 領(lǐng)導(dǎo)人來決定什么時候把日志條目應(yīng)用到狀態(tài)機(jī)中是安全的；這種日志條目被稱為已提交。Raft 算法保證所有已提交的日志條目都是持久化的并且最終會被所有可用的狀態(tài)機(jī)執(zhí)行。在領(lǐng)導(dǎo)人將創(chuàng)建的日志條目復(fù)制到大多數(shù)的服務(wù)器上的時候，日志條目就會被提交。同時，領(lǐng)導(dǎo)人的日志中之前的所有日志條目也都會被提交，包括由其他領(lǐng)導(dǎo)人創(chuàng)建的條目。
• 在 Raft 算法中，領(lǐng)導(dǎo)人處理不一致是通過強(qiáng)制跟隨者直接復(fù)制自己的日志來解決了。這意味著在跟隨者中的沖突的日志條目會被領(lǐng)導(dǎo)人的日志覆蓋。

7、安全性

8、其他