https://taozj.org/201612/learn-note-of-distributed-system-%284%29-raft-consensus.html
一、前言
Paxos在分布式系統中地位是不容置疑的，現代分布式系統的實現基本都直接或者間接依賴于Paxos算法。不過Paxos算法有著固有的缺陷：原始的BasicPaxos原理還是比較容易理解的，整個算法無非被分為Prepare和Accept兩個階段，但是要把這種算法工程化實現，各個節點的角色是對等的，系統的效率(可用性)將會非常的低，所以常用的也就是MultiPaxos變體版本以提高性能，這也就隱含的包含了leader的概念了，然后MultiPaxos還允許一個提交窗口，窗口中允許發起多個提案，但是這種情況下考慮到服務器隨時可能崩潰的情況，算法將會變得極端復雜。Lamport爺爺就此也是簡明說了幾句不清不楚的優化，沒有具體的實現細節，算是挖了一個巨坑吧。所以說了解BasicPaxos只是一個皮毛，將其推送到工程化可不是件容易的事情。
Raft算法是斯坦福兩位博士生提出的分布式一致性系統，從其論文的題目《In Search of an Understandable Consensus Algorithm》可以看出，作者以Paxos過于復雜為出發點，力求得到一個正常智商的大學生都能看懂，且工程上也容易實現的分布式系統一致性算法為目標。Raft算法借鑒了Paxos的原理，但最大不同是顯式強化了Leader這個角色(雖然很多Paxos算法的實現也會產生Leader角色，但這不是Paxos算法本身所必須的)，并添加了各種約束條件(比如日志的連續性)，讓算法更加容易理解和實現。雖然吾等草根屁民尚且不能從理論上審視這個算法的正確性，不過短短時間內美國很多著名大學分布式教學都將Raft算法列入教學課程，且基于Raft協議的項目也越來越多，這些事實已經足以證明一切了。
學習Raft算法，一篇普通論文和一篇博士學位論文算是不得不讀的經典，而前者網上發現了翻譯好的中文版本，簡單對比了一下原文，發現翻譯的質量還是挺高的，很值得參考，但有些原理中文理解困難的話可以對比英文方便理解。作為正規論文，按照論文八股需求難免有些啰嗦拖沓，本文就是按照前面論文閱讀摘抄一些重點要點出來，而后面那篇兩百多頁的博士論文，后面可以慢慢評鑒一下作為補充吧，當然最好的方式還是——一言不合就讀代碼，畢竟作者說就兩千多行！
還有，論文對狀態機的描述比較的好，算是歸納了分布式系統的本質——復制狀態機的基礎是通過復制日志來實現的：當每個副本的初始狀態相同，只要保證各個副本得到的日志都是順序且一致的，那么按照相同的順序執行這些日志中的指令，所有副本必然可以進行相同的狀態轉移得到相同的結果。所以分布式系統解決的根本問題，就是一致性問題，具體就是日志一致性問題，在這個基礎上，上層就可以方便實現分布式日志、分布式數據庫(bin log)、分布式存儲等具體業務了。
二、Raft算法
2.1 Raft算法基礎
Raft算法保證和Paxos算法具有相同的安全性，當集群中絕大多數服務器是正常的，則集群即可以正常工作，比如5個節點的集群，允許2個節點的失效。Raft算共有三種角色、需要處理三個問題，三個角色分別是Leader、Candidate、Follower，三個問題是Leader選舉、日志復制和安全性，三個問題將會在后面詳細闡述。
任何服務器只能處于上述三種角色中的一種，正常工作的集群具有一個Leader，剩余的節點都是Fellower，系統保證任何時候至多只有一個Leader，也有可能在選舉的過程中尚未產生Leader，而在選舉新Leader的時候會產生Candidate這個角色。
a. Leader
Raft算法強化了一個領導者(Leader)的角色。一旦被選舉成為Leader，就會發送空的AppendEntries RPC作為心跳給所有其他服務器，并且這個心跳會在一定空余時間后不停的發送，這樣可以阻止選取超時而阻止其他服務器重新發起選舉操作；
Leader負責接收客戶端的請求(如果客戶端和Fellower聯系，那么這個請求會被重新定向給Leader)，然后附加entry到本地日志存儲中，并負責把日志安全地復制到其他服務器上面，entry被用于Leader本地狀態機后給客戶端發送響應；
對于任何一個Fellower，如果已存儲的日志比較舊，還會向Leader不斷減小nextIndex要求發送之前的日志條目；
如果日志被安全地復制到了大多數節點上面，則增加提交索引號commitIndex，表明日志已經被安全復制；
b. Follower
通常的服務器角色狀態，只響應來自Candidate和Leader的請求；
如果在選舉超時到達后還沒收到Leader的心跳消息，或者是候選人發起投票請求，則自己變成Candidate；
c. Candidate
當轉變成Candidate后就立即開始選舉過程——增加當前term、給自己投票、重置選舉超時定時器、發送RequestVote給所有的服務器；
如果在超時之前收到絕大多數服務器的投票，就成為Leader；當一個節點收到RequestVote RPC的時候，如果請求投票節點的term不比自己舊，其日志也不比自己少，則投票給他；
如果收到來自新Leader的AppendEntries RPC，則退變成Fellower；
如果選舉過程超時，則再次發起新一輪選舉；
Raft中使用term表示Leader的任期，使用連續遞增的整數來標記區分，在Raft中充當了邏輯時鐘的作用，很多操作和記錄會打上這個“邏輯時間戳”；每個服務器存儲自己的term，服務器之間通信也會交換各自當前term，通過比較term可以確定哪些信息已經過期；當Candidate或Leader發現自己的term過期之后，會立即退變成Fellower的角色；如果服務器收到包含過期term的請求，就會直接拒絕這個請求返回false。
Raft算法中節點之間的通信使用RPC的方式，主要包括RequestVote、AppendEntries以及InstallSnapshot三種，RPC可以并行的被發起，而當沒有及時收到響應的時候會進行重試，同時RPC只需要在絕大多數快速的節點上完成就可以了，少部分比較慢的節點不會影響到系統的整體性能。
2.2 Leader選舉
很顯然以Leader為中心可以大大簡化系統的設計和實現，但是分布式系統中任何一個服務器都可能隨時崩潰不可用，那么必須使用選舉機制來解決Leader出錯導致的單點故障。
Raft中Leader地位的維持和心跳機制密切相關。集群中所有服務器默認都是Fellower的角色，如果Fellower在一段時間中沒有收到任何消息(無論是正常消息還是心跳消息)，就會觸發選舉超時，從而認為系統中沒有可用的領導者，進而開始進行選舉。選舉開始的時候，Fellower會增加當前term并切換為Candidate角色，然后并行向集群中所有其他服務器節點發送RequestVote RPC來給自己投票，候選人等待直到三種情況之一發生：
a. 該Candidate贏得該次選舉成為新Leader
當某個Candidate從集群中絕大多數服務器獲得針對該term的選票，則其贏得該次選舉成為Leader，因為按照先來先得的原則，每個服務器最多會對一個term投出一張選票，獲得絕大多數選票確保了至多只有一個候選人贏得該次選舉。
一旦Candidate成為Leader，就會向其他服務器發送心跳消息維護自己Leader的地位，并且阻止產生新的Leader。
b. 其他服務器成為新Leader
Candidate在收集選票的時候，很可能收到其他服務器發送的聲明自己是Leader的AppendEntries RPC消息，此時如果收到的AppendEntries RPC的term不小于該Candidate當前的term，則Candidate承認發送該AppendEntries RPC的服務器的Leader合法地位，自己退化為Fellower角色。否則會拒絕這個RPC并維持自己Candidate的角色。
c. 一段時間后沒有任何Candidate勝出
一般出現在多個Fellower變成Candidate，然后同時發出RequestVote RPC請求，導致選票被瓜分后，沒有任何一個Candidate獲得絕大多數選票。此時Candidate會增加term并開始新一輪的Leader選舉。
通常情況下這種選票瓜分的惡性競爭會持續下去。Raft采用隨機選舉超時的機制來減少這種情況的發生，選舉超時設置為某個固定時間區域中的隨機值(比如150-300ms)，這樣當現有Leader掛掉之后，通常也只有一個Fellower會首先超時，然后迅速切換為Candidate、發出RequestVote RPC并贏得選舉，然后快速發送心跳包；同時在發生選票瓜分的情況下，每次在Candidate開始新一輪的選舉時候，會重置一個隨機的選舉超時時間。通過這機制，發生選票瓜分的幾率被大大降低了。
2.3 日志復制
一旦Leader的角色被確定，就可以接受客戶端的請求并提供服務了。客戶端的每一個請求都包含狀態機的執行指令，Leader負責剛其作為一個entry追加到自己本地日志中，然后并行的向其他服務器發送附含執行指令的AppendEntries RPC，使其他服務器都復制這個日志entry。當該條日志被安全的復制后(即通過AppendEntries RPC調用的結果得知，該日志被安全地復制到絕大多數服務器上面了)，Leader會應用這條日志到自己的狀態機中，并將執行的結果返回給客戶端。如果(少部分)Fellower崩潰或者運行緩慢，或者因為網絡等問題，即使Leader已經回復了客戶端，Leader仍然會不斷的重試AppendEntries RPC直到所有的Fellower都最終存儲了所有的日志條目。
在Raft算法中，日志是有序序號標記的entry組成的，每個entry包含該創建時候的term、狀態機需要執行的指令、在所有日志中的位置索引組成。Raft保證當日志條目被復制到絕大多數服務器上面的時候，該日志entry就會被提交，即更新commitIndex，Raft算法同時也保證所有已提交的日志都是持久化的并且最終會被所有的可用狀態機執行。
Leader跟蹤了最大將會被提交日志entry的索引，并且該索引值會被包含在未來所有的AppendEntries RPC中(包含附加日志內容為空的心跳包)，這可以方便的讓其他服務器知道Leader的提交位置，一旦Fellower知道一條日志已經被提交，就會按照日志的順序將其應用到本地的狀態機中去執行。
和Paxos不同的是，Raft的日志約束為連續的、中間不允許有空洞，而且相同索引的日志在各個服務器上面指令完全相同，這樣的設計可以減少很多不必要的麻煩，具體來說：
(1) 如果在不同服務器的日志中擁有相同的索引和Term，那么他們存儲了相同的指令；
(2) 如果不同服務器中兩個日志具有相同的索引和Term，那么他們之前所有的日志條目也都全部相同。
對于上面第二點，通過每次RPC簡單一致性檢查就可以確保。每當Leader發送AppendEntries RPC的時候，會包含新entry緊接之前條目的索引位置和term附加在里面，當Fellower接收到的時候會進行一致性檢查，如果發現索引及term指定的日志找不到，就會拒絕接收該AppendEntries RPC請求。這種一致性通過強制Fellower復制Leader日志的方式來解決，領導者對每一個Fellower都維護了一個nextIndex，表示下一個需要發送給Fellower日志條目的索引位置，Leader通過不斷減少nextIndex后退的方式嘗試最終會找到和Fellower日志不一致位置開始的地方，然后從這個地方開始Leader將自己的日志同步給Fellower就可以了。不過這種大規模的日志不一致性通常在服務器接連崩潰的情況下更容易產生，當新選出了Leader之后，該Leader也會強制所有服務器的nextIndex為自己本地最后一條日志索引值+1，這樣在后續正常發送AppendEntries RPC請求后，所有的Fellower就會自動進行本地日志一致性檢查并在必要情況下進行同步操作了。
通過這種方式，只需Leader向Fellower單方面同步日志就可以完成，而且只需要Leader正常發送AppendEntries RPC請求，Fellower自己進行一致性檢查，Leader得到失敗的反饋信息后，再同Fellower進行不斷交互以使得兩者日志最終趨于一致，而且這種操作不會影響到其他的Fellower，因而也不會影響到系統整體的性能。
2.4 安全性
上面的內容都比較的理想化，但是在現實環境中Leader、Fellower各個服務器隨時都可能崩潰不可用，如果沒有額外的約束整個系統的工作是不安全的，比如當只有少量日志的Fellower被選取成了新Leader的情況。
簡單來說，此處就是要實現即使發生了Leader重新選取，也要讓任何新Leader對于給定的term，都必須有前任Leader所有已經被提交的日志條目，那么上面的機制就仍然可以正常工作。
2.4.1 增加選舉限制
如果任何的Fellower都可以成為新人Leader，那么這個新Leader很有可能缺失前Leader的部分提交日志，很多一致性算法確實是這樣的，然后通過某些方法識別出新Leader缺失日志，并在選舉階段或者成為新Leader之后快速的將這些缺失日志補齊，這些方法實現起來比較復雜。Raft算法通過很簡單的限制解決了這個問題：在RequestVote RPC 中包含了Candidate的日志信息，然后投票人會拒絕掉那些日志沒有自己新的請求。
上面的這條約束肯定是有效的：對于一個被提交的日志，那么這個日志肯定是被大多數服務器所見而被存儲的，而一個Candidate要想成為Leader就必須和集群中的大多數服務器所通信，這樣一來新Leader肯定會遇到至少一個記錄著最新提交日志的服務器。再加上上面的限制條件，那么一個新當選的Leader至少會和大多數的服務器節點一樣新，其肯定持有了所有已經提交了的日志條目。
2.4.2 提交前term內的日志條目
在Raft算法中，當一個日志被安全的復制到絕大多數的機器上面，即AppendEntries RPC在絕大多數服務器正確返回了，那么這個日志就是被提交了，然后Leader會更新commitIndex。
這里書中描述的比較復雜，其實本質就是通過上面的選舉機制和提交限制，讓Raft算法是安全的，即使是針對前term的日志：如果日志被復制到絕大多數服務器上面，那么含有較少日志的S5服務器就不會被選舉成Leader，也就不會發生描述的entry-2日志即使被復制到絕大多數服務器上面，也最終被覆蓋的情況；而當含有被復制的絕大多數日志entry-2的服務器被選為新節點的時候，提交entry-4也會讓前面的entry-2被隱式提交。
2.4.3 Candidate和Fellower崩潰
Candidate和Fellower崩潰的情況處理要簡單的多。如果這類角色崩潰了，那么后續發送給他們的 RequestVote和AppendEntries的所有RCP都會失敗，Raft算法中處理這類失敗就是簡單的無限重試的方式。
如果這些服務器重新可用，那么這些RPC就會成功返回。如果一個服務器完成了一個RPC，但是在響應Leader前崩潰了，那么當他再次可用的時候還會收到相同的RPC請求，此時接收服務器負責檢查，比如如果收到了已經包含該條日志的RPC請求，可以直接忽略這個請求，確保對系統是無害的。
三、集群成員變更
集群成員的變更和成員的宕機與重啟不同，因為前者會修改成員個數進而影響到Leader的選取和決議過程，因為在分布式系統這對于majority這個集群中成員大多數的概念是極為重要的。
在集群中成員變更的NEW配置不可能立即在所有成員中生效，所以必須采用兩階段的方式來保證安全性，傳統方式是將集群暫停工作，讓其不再接受新客戶的請求，更新配置完成后在讓集群繼續正常運行。
Raft中集群成員的變更是全自動的，通過產生一個“共同一致狀態”來過渡傳播NEW配置，并且做到在集群成員變更過程中仍然支持客戶端請求，依靠在臨界狀態下達成一致的操作(針對選取和提交)需要分別在新舊兩種配置上都獲得絕大多數服務器投票才可以。成員變更請求在日志中以特殊的configuration entry來存儲和通信，主要通過C-old,new和C-new這兩個特殊日志entry來實現。
在Leader接收到成員變更請求后，會創建C-old,new日志entry，然后Leader會首先將其添加到自己本地日志中，并通過之前描述的普通日志復制提交流程，確保在OLD、NEW兩個配置下的在絕大多數服務器上復制成功并提交；接下來Leader會創建一個C-new并在NEW配置下的絕大多數機器上復制成功并提交，創建C-new之后NEW配置就可以單獨做出決議了。此外，這里還有一個關鍵性的約定——所有的服務器一旦存儲了C-old,new日志條目后(實際就是見到NEW配置后)，就總是會用NEW配置而無論這個配置日志條目是否已經被提交，通過這種方式實現NEW配置在集群成員中快速傳播。一旦C-old,new被提交后，OLD和NEW配置都不能單方面的產生決議(只能在新舊兩個配置下都完成絕大多數投票)以保證安全，直到NEW配置下的C-new日志條目被產生，NEW配置就可以單獨決議了。
至于在C-old,new提交和C-new創建之間為什么會有間隙，原文沒有說清楚。其實也很容易理解：在C-old,new日志entry的創建和提交之間，Leader還可能有其他新的決議發起(比如客戶端請求)，按照日志順序一旦C-old,new被提交，那么集群中絕大多數主機都更新成NEW配置了，但是在NEW配置傳播的過程中，為了保證安全在這個期間產生的所有日志都必須在新老配置中都得到絕大多數投票才允許真正被提交。至于C-new的產生，是為了表明Leader承諾從這個時候起所有的日志都不再會發給OLD配置主機，所以這個點之后NEW配置就可以獨立工作了，由于Raft序列化日志的特性，一旦這個C-new日志條目被提交，集群配置中被刪除的服務器就可以安全下線了。
新加入的機器日志都是空白的，起始階段都在進行日志追趕(catch up)，Raft算法為了減少可能的性能損耗，對新加入的機器都是以旁觀者的狀態一直追趕舊日志而不會追加新日志參與投票，只有到了追趕日志和Leader對齊了，再參與新日志追加投票以行使正常集群成員的職能。還有NEW配置可能會把現任Leader刪除掉，那么當C-new被提交后，該Leader將會卸任并退化成Fellower的角色，此時在NEW配置下會發生新Leader的選舉，選舉得到的新Leader一定是NEW配置下的主機，而在這之前由于一致性狀態的約束，如果發生Leader選舉那么選出來只可能是OLD配置中的服務器，因為一致性狀態選舉操作必須在新舊配置中都得到絕大多數選票才行。
四、日志壓縮
日志會隨著系統的不斷運行會無限制的增長，這會給存儲帶來壓力，幾乎所有的分布式系統(Chubby、ZooKeeper)都采用快照的方式進行日志壓縮，做完快照之后快照會在穩定持久存儲中保存，而快照之前的日志和快照就可以丟棄掉。
Raft算法中快照所需保存的數據有：快照點時候狀態機的狀態信息；最后被快照所取代的日志條目在日志中的索引值；上面被取代條目所屬的任期term，此外為了支持成員更新，快照還會將當前最新的成員配置寫入上面描述的那個日志索引中。
Raft采用讓服務器獨立創建快照，而不是只讓Leader負責創建快照，主要考慮到在所有服務器本地已經具有了創建快照所需的全部信息，而且本地創建快照代替Leader創建快照，就免除了Leader要向各個節點傳輸快照的額外任務、帶寬和性能損耗，而且在Leader負責客戶端響應、發送RPC的任務外如果還需維護快照的任務，其角色就會更加復雜。
在Raft中快照都是各個服務器獨立創建的，但是有時候需要Leader向其他服務器發送快照，比如某些服務器跟隨的速度緩慢，或者新加入集群的服務器，此時需要向Leader同步日志的時候，如果Leader創建了快照并將之前的日志都刪除掉了，那么此時就必須通過快照的方式發送了。
Raft中采用一個額外的InstallSpanshot RPC的調用來實現日志傳輸，雖然名曰快照，其實也就算是一個特殊的日志entry。當接收到快照的時候，通常情況下快照會包含接受者中沒有的信息，即快照代表的日志entry會比接受者當前本地含有的日志要新，此時接收者會丟棄掉自己所有的日志，并在指定位置寫入該快照作為最新狀態；如果因為網絡或其他因素，接收者含有比快照更新的日志，那么接收者負責把快照位置之前的數據全部刪除，同時比快照新的數據需要保留下來。
五、Client交互
Client只向Leader發送請求，當Client開始的時候會隨機向集群中的任何一個服務器發送請求，如果Client挑中的恰巧不是Leader，那么該服務器會拒絕Client的請求，并將其最近獲得的Leader信息(包括通信用的IP:Port)返回給Client，接下來Client根據這個信息直接向Leader重新發送請求；如果此時Leader恰巧崩潰了，那么Client的請求就會超時出錯，Client會再次重新隨機挑選服務器再次發送請求。
Raft算法要求Client的請求是線性化語義的，即每次請求會被立即執行，在請求和響應中只會被執行一次(也就是RESTful中的等冪性，同一個請求發起一次或者多次，最終的效果是相同的)，而要確保這個效果的方式是客戶端負責對每條指令都賦予一個唯一的序列號，然后狀態機跟蹤每條指令最新序列號和其響應結果，如果后面收到一條指令具有相同的序列號但是該序列號已經被執行了，那么就直接返回結果而不重新執行該指令。
對于只讀操作可以直接處理而不需要記錄日志，但是會有讀取臟數據的風險。在Leader穩定運行的時態，Leader肯定知道當前已經提交的entry，但是在新Leader選取剛上任的時候，雖然肯定是含有最完整的日志信息的，但是還不知道提交到哪條entry了(可以參看上面提交前term日志條目的情況)，所以在新Leader上任的時候會發起一個no-op的entry來刷新得到最新commit信息。然后，Leader在響應只讀請求的時候，需要向絕大多數服務器發送一個心跳信息，確保當前自己還是合法的Leader。
總結
如果在工程化的水平上考慮，Raft算法的確比MultiPaxos要簡單容易的多，而且對比PhxPaxos中做出的諸如Master選舉與心跳、Master負責所有客戶端請求(允許普通節點響應臟數據除外)、日志壓縮與快照等等操作，在這里看來也是那么的熟悉，只不過Raft對于整個分布式的設計和實現要更清晰、更系統，而不會讓人感覺是在MultiPaxos的基礎上縫縫補補拼湊出來的一個怪物吧。
眼觀這么多論文，大家對Paxos的工程化實現，感覺都是相互借鑒啊，哈哈！
參考