前言
先后拜讀了Paxos made simple和Raft兩篇大作，作為一個學數(shù)學出身的人，深感Paxos作者Leslie Lamport邏輯之嚴密翩迈，通過層層遞進不斷加強保證的方式推導出Paxos的神級算法耳鸯，論文雖不長但要徹徹底底明白作者的心思邏輯，還得細細品味一番棋嘲。筆者也深以為論文正應(yīng)如此，邏輯嚴密不差絲毫矩桂。然而沸移，在拜讀Raft大作之后，筆者卻有一種讀小說后如沐春風之感侄榴。Raft作者沒有任何頭腦風暴雹锣，清清楚楚用及其通俗的語言闡述了一個工業(yè)級的通俗易懂的一致性協(xié)議。
Paxos在1990年就已經(jīng)被提出來了癞蚕，Raft協(xié)議直到2013年才以論文的形式面世蕊爵，但短短幾年Raft的各種開源和工業(yè)級應(yīng)用卻在以指數(shù)級增長，像開源實現(xiàn)etcd就是基于Raft協(xié)議實現(xiàn)的桦山。下面我們來詳細了解下Raft協(xié)議的真面目攒射。
Raft一致性協(xié)議
為了形成多數(shù)派，Raft集群一般都是由奇數(shù)個server構(gòu)成恒水。Raft集群中的server總共有三種狀態(tài)：
- Leader
- follower
- candidate
一般情況下leader只有一個会放，其它全部都是follower。leader負責接收并處理所有client的請求钉凌，follower是被動的咧最，它只能接收leader的請求但從不主動發(fā)出任何請求。第三個狀態(tài)candidate負責選舉leader御雕，一旦server身份確定則自動轉(zhuǎn)換到leader或follower狀態(tài)窗市。下圖展示了不同狀態(tài)之間轉(zhuǎn)換的條件：
Raft協(xié)議中另外一個非常重要的術(shù)語就是term（任期），Raft把時間軸按從左到右劃分成任意長度的任期饮笛。每個term都是從一次選舉開始咨察，當某個candidate被選舉為leader后，它便成為整個term的leader福青，選舉結(jié)束后開始處理client的請求摄狱。
Leader選舉
與Paxos選舉算法相比，Raft協(xié)議選舉算法顯得相當?shù)暮唵挝尬纭囊陨系臓顟B(tài)轉(zhuǎn)換圖可以看出來媒役，只有當server處于candidate狀態(tài)時才能夠進行選舉流程。開始選舉之前server首先增加它當前的term宪迟，然后才會轉(zhuǎn)換到candidate狀態(tài)酣衷。
- A啟動后處于follower狀態(tài)，當follower在timer時間內(nèi)沒有收到leader的心跳請求次泽，會轉(zhuǎn)換到candidate狀態(tài)并觸發(fā)選舉流程穿仪。Raft協(xié)議使用多數(shù)派來保證leader的唯一性席爽，當收到全部或者多數(shù)節(jié)點的同意后，candidate認為自己可以成為leader啊片。一旦leader確定身份后只锻，它會發(fā)送心跳信息給其它的server，以此來宣告它的統(tǒng)治時代到來紫谷。
- 如下圖所示齐饮，當A發(fā)出投票后進入等待狀態(tài)，此時由于集群中已經(jīng)存在leader笤昨，A收到B的請求告知B已經(jīng)是leader祖驱。這時如果B的term大于或者等于A當前的term，則A自動轉(zhuǎn)換成follower瞒窒，如果A當前的term大于B的term捺僻，則A維持在candidate狀態(tài)繼續(xù)等待其它請求。在Raft協(xié)議中所有的請求有一個共同的原則根竿，就是如果請求中的term大于本地當前的term陵像，server會自動轉(zhuǎn)換成follower狀態(tài)就珠。
- 還有一種情況就是所有的server都處于candidate狀態(tài)寇壳，發(fā)出自己的投票，大家的投票比較分散妻怎，所以沒有server拿到大多數(shù)的投票壳炎，也就不能產(chǎn)生所謂的leader，這就是通常所說的split vote逼侦。那這種情況下怎么辦呢匿辩？Raft為了避免這種情況發(fā)生的概率，采取了隨機超時的機制榛丢，也就是說當某個server發(fā)起一次投票之前铲球，他會隨機設(shè)置超時時間，以此來減小不同server同時發(fā)出投票造成split vote的概率晰赞。
日志復制
Raft集群中每個server都維護自己的有限狀態(tài)機稼病，日志復制就是用來保證集群中有限狀態(tài)機的一致性。一般過程如圖所示掖鱼，
client向leader發(fā)出請求然走，leader首先在本地的log中增加一條記錄，同時發(fā)出append請求給其它所有的follower戏挡，follower收到請求后在自己的log中追加一條記錄并回復leader芍瑞，當leader確定有超過一半的server記錄該操作后，就會把本次操作提交到狀態(tài)機褐墅。
來看一下Raft日志的組成形式拆檬，log由一串連續(xù)的記錄組成洪己，每條記錄是一個三元組（index，term秩仆，command）码泛。其中，index是指記錄在日志中的位置澄耍，term是該條記錄在追加時的任期噪珊，command是每一次具體的操作信息。
當日志發(fā)生不一致的時候齐莲，leader和follower之間就需要進行日志比較痢站，為了快速完成這樣的操作，Raft定義了日志匹配特性可以達到此目的选酗，
- 如果不同日志中的兩個記錄有相同的index和term阵难，則它們存儲的操作是相同的；
- 如果不同日志中的兩條記錄有相同的index和term芒填，則所有以前的條目中的記錄都是相同的呜叫。
對于一般正常的操作，leader和follower的日志會一直保持一致殿衰，但是每臺機器都不是100%高可用的朱庆，leader宕機的情況下leader和follower的日志就及其容易造成不一致。
安全性
為了保證Raft算法的安全性闷祥，還需要兩個特殊的限制娱颊，接下來我們就來看看這兩個限制是什么?
選舉限制
任何leader-based一致性算法中l(wèi)eader必須保存所有的提交的日志記錄，一些一致性算法像VR凯砍，Zookeeper等在server中不包含所有committed日志的情況下依然可以被選擇為leader箱硕。事物都有其兩面性，這樣看似優(yōu)雅的處理讓協(xié)議的實現(xiàn)變得復雜困難悟衩。相反剧罩，Raft使用簡單的策略保證被選舉的leader包含所有已經(jīng)提交的日志。策略就是座泳，選舉leader的時候總是選擇擁有最新日志的server作為leader惠昔。比較方法就是利用上面提到的日志匹配特性：
- 當term不同時，term更大的log更新
- 當term相同時钳榨，選擇擁有更大index的
日志提交限制
當有半數(shù)以上的server保存了日志舰罚，leader可以安全的提交。有一種情況就是leader崩潰前并沒有提交日志薛耻，未來的leader會繼續(xù)未完成的使命营罢。然而，新的leader并不知道日志記錄是否已經(jīng)同步到半數(shù)以上的server，況且饲漾，即便半數(shù)以上的server已經(jīng)同步過了蝙搔，依然有可能被覆蓋掉。為了避免這種情況的發(fā)生考传，Raft要求leader永遠不通過統(tǒng)計副本數(shù)量的方式提交先前term的日志吃型，統(tǒng)計副本的方式只適用于當前term日志。當新的term有日志提交后僚楞，先前term的日志間接也會被提交勤晚，這就保證了同樣index的日志不會被提交兩次。
總結(jié)
相比較于Paxos協(xié)議泉褐，Raft在設(shè)計之初就本著簡單易用的宗旨赐写，才成就了這樣一個可理解的，易于實現(xiàn)的膜赃，對于人類思維毫無違和感的協(xié)議挺邀。
參考
[1]. Leslie Lamport. Paxos Made Simple. 2001
[2]. Diego Ongaro and John Ousterhout. Raft Paper. 2013
[3]. Raft Website. The Raft Consensus Algorithm
[4]. Raft Demo. Raft Animate Demo
