前言

Raft協(xié)議是現(xiàn)在使用最廣泛的分布式一致性協(xié)議，這篇文章的本意不是翻譯它的協(xié)議內(nèi)容（已經(jīng)有大神做過了突倍，中文版Raft協(xié)議）腔稀，更不是為了證明它的正確性（真沒這個(gè)能力）。而是從問題出發(fā)羽历，看Raft怎么解決分布式中的種種問題焊虏，順便就把學(xué)習(xí)筆記給做了。

分布式一致性

先問為什么秕磷，再問怎么做：“為什么需要分布式一致性協(xié)議”诵闭？
首先，需要分布式一致性協(xié)議的系統(tǒng)肯定是分布式的澎嚣。分布式系統(tǒng)是由多臺(tái)機(jī)器組成的集群來實(shí)現(xiàn)的疏尿。既然是集群，就必然引入額外的復(fù)雜度易桃，比如網(wǎng)絡(luò)故障褥琐、某個(gè)節(jié)點(diǎn)宕機(jī)等。這些是一個(gè)完整的分布式協(xié)議必須要解決的問題晤郑。
其次踩衩，系統(tǒng)有一致性要求。在單機(jī)場景下贩汉，最常用的一致性系統(tǒng)就是數(shù)據(jù)庫了驱富。它保證了寫入成功的數(shù)據(jù)在多次讀取的情況下結(jié)果是一致的，并且操作失敗的情況下也不會(huì)影響之前的數(shù)據(jù)匹舞。單機(jī)情況下褐鸥，操作系統(tǒng)可以保證內(nèi)存和硬盤讀寫的原子性，所以串行操作的一致性很容易得到保證赐稽。而數(shù)據(jù)庫通常在不同的事務(wù)隔離機(jī)制下叫榕，通過算法來保證并發(fā)的情況下也可以做到一致性浑侥。而在分布式系統(tǒng)下，無論是寫入還是讀取晰绎，都需要在多個(gè)節(jié)點(diǎn)上進(jìn)行寓落，可能面臨讀取的節(jié)點(diǎn)數(shù)據(jù)不是最新的或者部分節(jié)點(diǎn)寫入失敗的情況。這是分布式一致性協(xié)議要解決的第二類問題荞下。
總的來說伶选，分布式一致性算法就是為了讓一組機(jī)器像一個(gè)整體一樣工作，即使部分節(jié)點(diǎn)出現(xiàn)故障也能夠繼續(xù)工作下去尖昏，并且保證數(shù)據(jù)在集群內(nèi)的一致性仰税。
當(dāng)前，基于分布式一致性算法典型應(yīng)用場景有抽诉，1）提供分布式一致性的服務(wù)陨簇，比如zookeeper、etcd迹淌，業(yè)務(wù)系統(tǒng)基于它可實(shí)現(xiàn)分布式鎖及master選舉等功能河绽。2）分布式數(shù)據(jù)庫，比如mangoDB唉窃、TiDB等葵姥。

Raft協(xié)議背景

"這個(gè)世界上只有一種一致性算法，那就是Paxos", ---- MikeBurrows句携， Google Chubby的作者
Paxos是最先提出和被證明的分布式一致性算法榔幸，后續(xù)的算法都是基于它發(fā)展而來的。Paxos算法最大的問題就是難于理解矮嫉，這個(gè)不是我們普通人難于理解削咆，而是專門研究算法的專家們也很難按照協(xié)議的要求做出一個(gè)工程實(shí)現(xiàn)方案。這樣導(dǎo)致一個(gè)問題蠢笋，很多系統(tǒng)自己認(rèn)為是Paxos的實(shí)現(xiàn)拨齐，但實(shí)際上在實(shí)現(xiàn)過程中做了很多妥協(xié)之后，最終的系統(tǒng)建立在一種沒有經(jīng)過證明的算法之上昨寞。
以上就是Raft出現(xiàn)的初衷瞻惋，與其說Raft是一個(gè)全新的分布式一致性算法，不如說是Paxos的工程化擴(kuò)展援岩，是一個(gè)經(jīng)過證明的歼狼，工程實(shí)現(xiàn)可行性更高的一致性協(xié)議。舉個(gè)不太恰當(dāng)?shù)睦酉砘常绻褜?shí)現(xiàn)分布式一致性系統(tǒng)比作造一輛汽車羽峰，Paxos協(xié)議的就是告訴你需要發(fā)動(dòng)機(jī)，變速箱，車架梅屉、輪胎等等這些東西值纱，然后證明了這樣造出的車是能跑的。而Raft協(xié)議的意義就是告訴你坯汤，具體需要多少個(gè)零件虐唠，這些零件怎么組裝，能夠最快的造出一輛好車惰聂。
還有一點(diǎn)需要提及疆偿，Raft協(xié)議出現(xiàn)的時(shí)候，已經(jīng)有很多支持分布式一致性的系統(tǒng)在大規(guī)模部署的生產(chǎn)環(huán)境驗(yàn)證了可靠性庶近。所以翁脆，Raft協(xié)議跟Paxos不同眷蚓，它是先有了實(shí)現(xiàn)鼻种，后提煉的協(xié)議。從協(xié)議中也可以發(fā)現(xiàn)跟Zookeeper的ZAB協(xié)議有很多類似的設(shè)計(jì)沙热。這從側(cè)面證明了它的可靠性和可實(shí)現(xiàn)性叉钥。
后續(xù)我們從問題出發(fā)，看看Raft協(xié)議篙贸，還是要強(qiáng)調(diào)一下投队，這些問題不可能覆蓋協(xié)議的所有情況，更大的意義是做筆記幫助理解爵川，對(duì)照協(xié)議原文查看會(huì)更有幫助

Raft基礎(chǔ)

Raft包含的模塊

Raft協(xié)議分成3個(gè)部分來增加可理解性敷鸦，分別是領(lǐng)導(dǎo)人選舉、日志復(fù)制和安全性寝贡。

• 領(lǐng)導(dǎo)人選舉扒披，Raft協(xié)議規(guī)定集群中必須有且只有一個(gè)領(lǐng)導(dǎo)者，客戶端所有的讀寫請(qǐng)求最終都是發(fā)給領(lǐng)導(dǎo)人來處理的圃泡。在沒有領(lǐng)導(dǎo)人的情況下碟案，集群不對(duì)外提供服務(wù)。所以領(lǐng)導(dǎo)人選舉是首要要解決的問題颇蜡。
• 日志復(fù)制价说，一致性算法是從復(fù)制狀態(tài)機(jī)的背景下提出的，復(fù)制狀態(tài)機(jī)通常都是基于復(fù)制日志實(shí)現(xiàn)的风秤。在整個(gè)集群中鳖目，通過日志按順序執(zhí)行，來保證集群中節(jié)點(diǎn)上的數(shù)據(jù)最終都是一致的缤弦，簡單點(diǎn)可以理解成數(shù)據(jù)庫中常用的通過binlog進(jìn)行主從數(shù)據(jù)同步疑苔，只是數(shù)據(jù)庫的主從同步時(shí)一對(duì)一的。保證復(fù)制日志相同就是一致性算法的工作，所以協(xié)議針對(duì)日志復(fù)制惦费，定義了一系列需遵守的規(guī)范兵迅。
• 安全性，為了更好的保證數(shù)據(jù)一致性和容易實(shí)現(xiàn)薪贫，Raft額外定義了很多需遵守的安全性規(guī)范

Raft集群節(jié)點(diǎn)狀態(tài)

集群中節(jié)點(diǎn)的角色及狀態(tài)變換如下圖：

節(jié)點(diǎn)角色變換

集群中節(jié)點(diǎn)可能處于3種角色中的一種：

• Follower（追隨者）: 接收Leader的指令保存數(shù)據(jù)恍箭，接收Candiate的投票請(qǐng)求，然后投票
• Candidate (候選人): 發(fā)拉票請(qǐng)求給Follower瞧省，請(qǐng)求選自己為Leader
• Leader (領(lǐng)導(dǎo)人): 在同一個(gè)任期（term)內(nèi)扯夭，只會(huì)存在一個(gè)Leader節(jié)點(diǎn)

在集群處于穩(wěn)定狀態(tài)時(shí)，只會(huì)存在Leader和Follower鞍匾；當(dāng)Leader宕機(jī)后交洗，集群進(jìn)入重新選舉階段，只會(huì)存在Follower和Candidate橡淑，一旦新的Leader被選出构拳，沒選上的Candidate就轉(zhuǎn)成Follower。

本篇和后續(xù)2篇文章將按如下順序詳細(xì)解釋Raft：

• 領(lǐng)導(dǎo)人選舉
• 日志復(fù)制
• 集群擴(kuò)容&縮容

這篇文章先來看下領(lǐng)導(dǎo)人選舉

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

為什么需要選舉

Raft將整個(gè)集群的運(yùn)行過程梁棠，分成一個(gè)個(gè)任期(term)置森，任期通過任期號(hào)來標(biāo)識(shí)，是一個(gè)自增的數(shù)字符糊。Raft規(guī)定每個(gè)任期內(nèi)只能有且只有一個(gè)Leader凫海，所有發(fā)給集群的請(qǐng)求都由Leader來處理。就是說對(duì)于客戶端來說男娄，雖然我面對(duì)的是一個(gè)集群行贪，但是我只需要跟Leader交互就可以了，雖然不同的任期內(nèi)Leader可能變化模闲，但是同一時(shí)間面對(duì)的仍然只有一個(gè)節(jié)點(diǎn)建瘫。這樣做可以大大降低整個(gè)系統(tǒng)實(shí)現(xiàn)的復(fù)雜性，Zookeeper的ZAB協(xié)議也采用了同樣的設(shè)計(jì)围橡。
而選舉就是選Leader的過程暖混，所以，每一個(gè)新的任期生成翁授，一定伴隨著一次重新選舉拣播。

選舉達(dá)成的條件

決議通過都必需要超過半數(shù)的節(jié)點(diǎn)同意，這是Raft收擦、Paxos及其它所有分布式一致性協(xié)議成立的基礎(chǔ)贮配。對(duì)于領(lǐng)導(dǎo)人選舉來說，就是一個(gè)候選人收到了包括它自己在內(nèi)的超過半數(shù)節(jié)點(diǎn)的選票塞赂。比如一個(gè)5臺(tái)機(jī)器的集群泪勒，一個(gè)候選人如果收到除了它自己之外2臺(tái)機(jī)器的選票，那它就可以成功當(dāng)選。

選舉過程

選舉前的狀態(tài)
在一個(gè)正常運(yùn)行中的任期中圆存，集群中有兩種節(jié)點(diǎn)叼旋，Leader節(jié)點(diǎn)和Follower節(jié)點(diǎn)。Leader節(jié)點(diǎn)通過定時(shí)發(fā)送心跳給Follower來維持領(lǐng)導(dǎo)者狀態(tài)沦辙，F(xiàn)ollower通過接收到日志包夫植，來接收數(shù)據(jù)。所有節(jié)點(diǎn)都持久化和臨時(shí)保存一些屬性用來維持狀態(tài)和重啟時(shí)恢復(fù)數(shù)據(jù)油讯。
Raft節(jié)點(diǎn)屬性列表：

再來看一下日志復(fù)制RPC的格式

心跳包和日志復(fù)制使用同一個(gè)RPC調(diào)用笤喳，只是其中的entries屬性為空
Follower對(duì)于日志復(fù)制rpc的Response

通過以上的RPC定義可以知道贰镣，在集群運(yùn)行正常的時(shí)候，Leader不斷地發(fā)送日志復(fù)制(心跳)包給Follower膳凝，而Follower接收日志然后更新本地?cái)?shù)據(jù)和索引Index碑隆，這時(shí)候任期號(hào)(term)一直不會(huì)發(fā)生變化。
選舉觸發(fā)
有兩種情況會(huì)觸發(fā)集群的重新選舉

• 首次啟動(dòng)
  第一次啟動(dòng)后蹬音，所有節(jié)點(diǎn)默認(rèn)都是Follower上煤，自然不會(huì)有Leader發(fā)心跳，所以等待一段時(shí)間后著淆，就會(huì)有Follower將自己轉(zhuǎn)換成Candidate劫狠，給其它節(jié)點(diǎn)發(fā)請(qǐng)求投票RPC。
• 未收到Leader心跳
  集群運(yùn)行一段時(shí)間后永部，Leader因?yàn)殄礄C(jī)或者網(wǎng)絡(luò)分區(qū)導(dǎo)致Follower收不到Leader的心跳独泞，F(xiàn)ollower也會(huì)變成Candidate

以上兩種情況，F(xiàn)ollower等待直到變成Candidate的時(shí)長稱為選舉超時(shí)苔埋。Follower在等待過程中，收到任何一種請(qǐng)求，都會(huì)將等待時(shí)長清零子巾。包括Leader的心跳或者其它Candidate的投票請(qǐng)求。

Follower變成Candidate后罚随，就會(huì)立即發(fā)送拉票的RPC給其他所有節(jié)點(diǎn)，RPC格式如下：

拉選票的rpc除了攜帶任期號(hào)和自己的id外毫炉，還需要帶自己已經(jīng)接收的日志索引，這是Raft為了在選舉時(shí)能夠選出數(shù)據(jù)最新的節(jié)點(diǎn)作為新的Leader削罩，原因會(huì)在復(fù)制日志的部分解釋瞄勾。
RPC發(fā)出前，需要將當(dāng)前任期號(hào)加1弥激，作為新的任期號(hào)进陡，放到term字段中。前面說過微服，一次新的選舉必然對(duì)應(yīng)一個(gè)新的任期趾疚。
Follower在收到拉票的請(qǐng)求后，會(huì)回復(fù)如下格式的Repsonse：

投票結(jié)果
候選人的拉票請(qǐng)求發(fā)出去后可能會(huì)出現(xiàn)3種結(jié)果

• 贏得選舉
  說明該候選人收到了超過半數(shù)Follower節(jié)點(diǎn)的選票丛肮。這個(gè)時(shí)候候選人變成新Leader赡磅，一個(gè)新的任期開始，往外分發(fā)日志和心跳宝与，直到它宕機(jī)
• 輸?shù)暨x舉
  候選人把拉票請(qǐng)求發(fā)出去之后焚廊，沒有收到大部分Follower的選票，相反收到了新Leader的心跳习劫。這種情況下咆瘟，說明有別的候選人當(dāng)選了，這時(shí)候候選人主動(dòng)變成Follower诽里，承認(rèn)新的Leader袒餐。
  怎么判斷這個(gè)Leader的心跳是新當(dāng)選的而不是老的包呢？就是用心跳里的任期號(hào)谤狡，如果心跳包里的任期號(hào)大于等于自己的灸眼，則說明是新Leader，否則直接丟棄豌汇，繼續(xù)等自己的選票幢炸。
• 選舉超時(shí)
  候選人把拉票請(qǐng)求發(fā)出去之后，等啊等拒贱，既沒有等到大部分Follower的選票宛徊，也沒有等到新Leader的心跳佛嬉。則認(rèn)為選舉超時(shí)了，處理方法就是把自己的任期號(hào)再加1闸天，重新發(fā)拉票請(qǐng)求暖呕，開啟新一輪選舉。

以上就是一個(gè)完整的選舉過程了苞氮，上面的循環(huán)會(huì)一直進(jìn)行湾揽，直到一個(gè)新的Leader選出來為止。
對(duì)于選舉超時(shí)的情況笼吟，我們可以想一下原因库物。首先有可能是大家都沒得到足夠多的選票，比如一個(gè)5個(gè)節(jié)點(diǎn)的集群贷帮，Leader掛了后還剩4個(gè)戚揭，這時(shí)候其中兩個(gè)節(jié)點(diǎn)發(fā)出投票請(qǐng)求，分別得到2張選票撵枢，所以沒超過半數(shù)民晒，則沒人當(dāng)選。其次锄禽，當(dāng)前候選人在發(fā)出選票后因網(wǎng)絡(luò)問題潜必，導(dǎo)致Follower投給它的票一直沒收到，也會(huì)造成超時(shí)沃但。
帶著上面的問題進(jìn)入下一節(jié)磁滚，看看選舉過程中會(huì)出哪類問題，Raft是怎么從協(xié)議角度來規(guī)避和解決這些問題的绽慈。

選舉安全性

1. 如何保證只有一個(gè)候選人當(dāng)選
   Raft規(guī)定一個(gè)節(jié)點(diǎn)當(dāng)選必須要在一個(gè)任期內(nèi)收到超過半數(shù)Follower的投票恨旱。這個(gè)很容易理解辈毯，比如有5個(gè)節(jié)點(diǎn)坝疼，其中3個(gè)節(jié)點(diǎn)投票給我，其它候選人最多也就能得到2張選票谆沃，所以超過半數(shù)肯定是可以保證獲勝的钝凶。其實(shí)這里面隱含了Raft協(xié)議的2點(diǎn)規(guī)定：
   • 同一任期內(nèi)，F(xiàn)ollower只能投給一個(gè)候選人唁影，就是說同一個(gè)term內(nèi)只有一次投票機(jī)會(huì)耕陷，不得改變自己的主意
   • 節(jié)點(diǎn)只能響應(yīng)任期號(hào)大于或等于自己任期的請(qǐng)求，這個(gè)規(guī)定其實(shí)面向所有請(qǐng)求的据沈，不止是針對(duì)投票RPC哟沫。比如當(dāng)前Follower的任期號(hào)為5，這個(gè)時(shí)候來了一個(gè)投票的請(qǐng)求任期號(hào)是6锌介，F(xiàn)ollower就可以投票給它嗜诀，同時(shí)會(huì)把自己的任期號(hào)改為6猾警。從此以后只接收任期號(hào)大于等于6的請(qǐng)求。這樣可以處理一種情況隆敢，就是我任期5的票投給了節(jié)點(diǎn)A发皿，之后又收到節(jié)點(diǎn)B的任期6的請(qǐng)求，因?yàn)樗娜纹诟蠓餍杂职哑蓖督o了B穴墅。如果A之前沒有收到回復(fù)，重新發(fā)送了任期5的票温自，這時(shí)候會(huì)直接得到拒絕的答復(fù)玄货。
2. Follower如何決定是否投票給候選人
   • 票中帶的候選人任期號(hào)不小于Follower的任期號(hào)
   • 任期號(hào)符合條件則先到先得， 這個(gè)和Zookeeper有一點(diǎn)區(qū)別悼泌，zookeeper會(huì)拒絕serverId比自己小的節(jié)點(diǎn)
   • 候選人必須擁有最新日志比自己新誉结，這個(gè)在后面日志復(fù)制的時(shí)候解釋原因
3. 如何保證不進(jìn)入選舉超時(shí)-重新投票-選舉超時(shí)的循環(huán)
   進(jìn)入以上的循環(huán)可能是如下的原因：
   • Leader宕機(jī)后，所有Follower都變成候選人券躁，都投票給自己
   • 多個(gè)候選人瓜分選票惩坑，一直分不出勝負(fù)。比如一共4個(gè)節(jié)點(diǎn)A也拜、B以舒、C、D慢哈，A一直收到A和B的票蔓钟，C一直收到C和D的票

首先對(duì)于上面第一種情況，Raft規(guī)定選舉超時(shí)時(shí)間是從一個(gè)固定的區(qū)間（例如 150-300 毫秒）隨機(jī)選擇卵贱，這樣在Leader宕機(jī)后滥沫，大部分情況下只有一個(gè)節(jié)點(diǎn)會(huì)選舉超時(shí)并變成候選人，而不是大家同時(shí)變成候選人键俱。
其次兰绣，如果第一步還是有多個(gè)節(jié)點(diǎn)變成候選人，然后大家又瓜分了選票導(dǎo)致超時(shí)编振，這個(gè)超時(shí)也是隨機(jī)的（其實(shí)跟Leader宕機(jī)導(dǎo)致超時(shí)是一個(gè)）缀辩，這樣多個(gè)候選人不會(huì)同時(shí)發(fā)起新一輪投票，第一個(gè)發(fā)起新一輪的節(jié)點(diǎn)會(huì)把新任期號(hào)的投票率先給到其它候選人踪央，其他候選人收到比自己大的任期號(hào)的拉票請(qǐng)求臀玄，就會(huì)自動(dòng)轉(zhuǎn)成Follower。所以每一次失敗都隨機(jī)畅蹂，進(jìn)一步減少了瓜分的概率健无。

4. 如何保證在一個(gè)候選人被選為Leader后，集群內(nèi)其它節(jié)點(diǎn)迅速達(dá)成一致
   選舉過程可能出現(xiàn)一種情況液斜，候選人A收到了超過半數(shù)選票成為Leader累贤，候選人B未收到足夠多的選票而超時(shí)募胃，所以發(fā)起新的一輪選舉，因?yàn)锽的任期號(hào)更高畦浓，所以A收到B的拉票請(qǐng)求后被迫又變成Follower痹束。這樣導(dǎo)致的結(jié)果就是拉長了選舉的時(shí)間。
   理論上Raft協(xié)議無法規(guī)避這種情況讶请，而只能減少這種情況發(fā)生的概率：
   • 候選人成為Leader后會(huì)以最快的速度發(fā)出心跳祷嘶，在其它候選人超時(shí)之前，這樣其它候選人會(huì)變成Follower
   • 合理設(shè)置超時(shí)時(shí)間夺溢。一般來說在大部分網(wǎng)絡(luò)情況下论巍，廣播時(shí)間（broadcastTime） << 選舉超時(shí)時(shí)間（electionTimeout） << 平均故障間隔時(shí)間（MTBF），每個(gè)時(shí)間都差至少一個(gè)數(shù)量級(jí)风响。Raft 的 RPCs 廣播時(shí)間大約是 0.5 毫秒到 20 毫秒嘉汰。因此，建議選舉超時(shí)時(shí)間可能需要在 100 毫秒到 500 毫秒之間状勤。大多數(shù)的服務(wù)器的平均故障間隔時(shí)間都在幾個(gè)月甚至更長鞋怀，所以上面的時(shí)間要求很容易滿足。
5. Follower宕機(jī)持搜，會(huì)觸發(fā)選舉嗎
   集群中一個(gè)Follower宕機(jī)密似，Leader仍然可以收到超半數(shù)節(jié)點(diǎn)的請(qǐng)求確認(rèn)，所以不會(huì)觸發(fā)選舉葫盼。

6. 如果一次性加入多個(gè)節(jié)點(diǎn)到集群中残腌，會(huì)不會(huì)出現(xiàn)多個(gè)Leader的情況
   在集群發(fā)生大規(guī)模變化時(shí)，比如如下的集群：

   
   
   Raft集群
   
   

   開始只有Server1-3贫导，server1 通過1和2的選票當(dāng)選Leader抛猫，而后加入Server4和5，Server5通過3孩灯、4闺金、5的選票也當(dāng)選Leader
   針對(duì)這種配置更改情況，Raft協(xié)議有專門的定義钱反，防止出現(xiàn)上面多Leader的狀態(tài)掖看。在第3篇文章中會(huì)有解析

總結(jié)

Raft協(xié)議采用任期加單個(gè)Leader的方式，大大降低分布式一致性的復(fù)雜性面哥。把Leader選舉作為一個(gè)單獨(dú)的階段提取出來，雖然這樣會(huì)導(dǎo)致選舉期間集群不可用毅待，但是選舉畢竟是小概率事件尚卫，相對(duì)來說還是利遠(yuǎn)大于弊。下一篇文章繼續(xù)解析Raft對(duì)于日志復(fù)制的定義尸红。

鏈接：
分布式一致性協(xié)議-Raft詳解 (二)
分布式一致性協(xié)議-Raft詳解 (三)