什么是Replicated state machines(復(fù)制狀態(tài)機(jī)):
一致性算法之所以可以保證在有節(jié)點(diǎn)掛掉時(shí)也能夠繼續(xù)服務(wù)革娄， 就是因?yàn)橛蠷eplicated state machines的存在晋南。 在分布式系統(tǒng)中蜈亩， 有兩種方式來實(shí)現(xiàn)這個(gè)復(fù)制狀態(tài)機(jī)
- 用一個(gè)專門節(jié)點(diǎn)負(fù)責(zé)記錄整個(gè)集群的元信息， 如HDFS暇务， GFS
- 每個(gè)節(jié)點(diǎn)都會(huì)記錄replicated log劣针，確保每個(gè)節(jié)點(diǎn)的log最終都包含了相同的請(qǐng)求， 并且是同樣的順序
一致性算法一般有一下特點(diǎn)：
- 保證安全（不會(huì)返回錯(cuò)誤數(shù)據(jù)）
- 只有半數(shù)以上的節(jié)點(diǎn)存活就可以繼續(xù)提供服務(wù)
- 不依賴時(shí)鐘來提供一致性押搪， 最多會(huì)造成不可用
- 通常只要半數(shù)以上節(jié)點(diǎn)完成請(qǐng)求就算成功树酪， 小部分慢節(jié)點(diǎn)不會(huì)影響整個(gè)系統(tǒng)的性能
為啥不用Paxos？
- 不清晰大州， 難以理解
- 不好實(shí)現(xiàn)续语， 只提供了single-decree Paxos的細(xì)節(jié)， 沒有給出multi-Paxos的細(xì)節(jié)
Raft一致性算法
Raft算法首先會(huì)選舉一個(gè)leader厦画， 然后又leader來管理replicated log疮茄。 leader會(huì)從client處接收請(qǐng)求， 然后轉(zhuǎn)發(fā)給別的節(jié)點(diǎn)根暑， 并且告訴這些節(jié)點(diǎn)什么時(shí)候可以把這些請(qǐng)求應(yīng)用在狀態(tài)機(jī)上（落地）力试。 當(dāng)一個(gè)leader掛了的時(shí)候， 會(huì)馬上選舉出一個(gè)新的leader排嫌。 由上可知畸裳， Raft將一致性問題拆分成了3個(gè)獨(dú)立的子問題：
- Leader選舉
- 日志的復(fù)制（Log replication）
- Safty： 不能有錯(cuò)誤數(shù)據(jù)
Raft的實(shí)踐基礎(chǔ)
一個(gè)Raft集群會(huì)有多個(gè)節(jié)點(diǎn)， 一般至少5個(gè)躏率， 這樣可以忍受2個(gè)節(jié)點(diǎn)fail躯畴。 這些節(jié)點(diǎn)在任何時(shí)間點(diǎn)都會(huì)是以下3個(gè)狀態(tài)之一： leader民鼓， follower， candidate蓬抄。
Raft將時(shí)間分為了多個(gè)term丰嘉， 選舉會(huì)產(chǎn)生一個(gè)新的term， 每個(gè)term的時(shí)長不定嚷缭，但是每個(gè)term都至多有一個(gè)leader
不同的節(jié)點(diǎn)會(huì)在不同時(shí)間感知到變化饮亏，有些節(jié)點(diǎn)甚至在一個(gè)term完結(jié)時(shí)都沒有感知到。 Terms是一個(gè)邏輯時(shí)鐘阅爽， 每個(gè)節(jié)點(diǎn)都會(huì)存儲(chǔ)當(dāng)前term路幸， 并且會(huì)一直跟別的節(jié)點(diǎn)交換信息， 一旦發(fā)現(xiàn)自己的term不是最新的付翁， 就會(huì)更新term简肴， 如果一個(gè)candidate或者leader發(fā)現(xiàn)他的term過時(shí)了，就會(huì)馬上回退成follower百侧。 如果一個(gè)節(jié)點(diǎn)收到一個(gè)過期term的請(qǐng)求砰识， 那么他會(huì)拒絕這個(gè)請(qǐng)求
Raft節(jié)點(diǎn)間通過RPC請(qǐng)求進(jìn)行通信， 基本的算法只要求兩種RPC請(qǐng)求類型佣渴。 一種是RequestVote RPCs, 由candidate在選舉時(shí)發(fā)出辫狼。 一種是AppendEntries RPCs， 由leader發(fā)出辛润， 用來復(fù)制log和發(fā)送心跳-
leader選舉
Raft用心跳來觸發(fā)leader選舉膨处， 當(dāng)節(jié)點(diǎn)啟動(dòng)時(shí)， 都是follower的狀態(tài)砂竖。只要節(jié)點(diǎn)能夠收到來自leader或者candidate的RPC真椿， 節(jié)點(diǎn)就會(huì)保持follower狀態(tài)。
Leader會(huì)定期發(fā)送RPC給所有的follower來維持他的leader地位乎澄， 但是一旦有一個(gè)節(jié)點(diǎn)在一段時(shí)間沒有收到心跳瀑粥， 那么節(jié)點(diǎn)就會(huì)認(rèn)為沒有存活的leader并且觸發(fā)新一次的選舉。
選舉開始時(shí)三圆，一個(gè)follower會(huì)給當(dāng)前term加1并且轉(zhuǎn)換成candidate狀態(tài)。 然后這個(gè)節(jié)點(diǎn)會(huì)給自己投票并且給所有其他節(jié)點(diǎn)發(fā)送RequestVote RPC避咆。
Candidate會(huì)保持這個(gè)狀態(tài)直到以下3個(gè)事件中的一個(gè)發(fā)生：- 這個(gè)節(jié)點(diǎn)贏得選舉
如果這個(gè)節(jié)點(diǎn)贏得了半數(shù)以上的vote就會(huì)成為leader舟肉，每個(gè)節(jié)點(diǎn)會(huì)按照first-come-first-served的原則進(jìn)行投票，并且一個(gè)term中只能投給一個(gè)節(jié)點(diǎn)查库， 這樣就保證了一個(gè)term最多有一個(gè)節(jié)點(diǎn)贏得半數(shù)以上的vote路媚。
當(dāng)一個(gè)節(jié)點(diǎn)贏得選舉， 他會(huì)成為leader樊销， 并且給所有節(jié)點(diǎn)發(fā)送這個(gè)信息整慎， 這樣所有節(jié)點(diǎn)都會(huì)回退成follower脏款。 - 另外一個(gè)節(jié)點(diǎn)贏得選舉
在等待vote時(shí)， 如果這個(gè)candidate收到了別的節(jié)點(diǎn)請(qǐng)求vote的RPC裤园， 那么他會(huì)檢查是否這個(gè)節(jié)點(diǎn)的term大于等于自己的term撤师， 如果是那么這個(gè)candidate就會(huì)回退成follower。 如果不是就會(huì)reject這個(gè)RPC拧揽。 - 一個(gè)選舉周期結(jié)束并且沒有l(wèi)eader選出來
這種情況是由于可能有很多follower都成為了candidate剃盾， 那么vote就會(huì)很分散， 最后沒有一個(gè)節(jié)點(diǎn)拿到半數(shù)以上的vote淤袜。最后這個(gè)term超時(shí)并且進(jìn)入下個(gè)term繼續(xù)選舉痒谴。
為了防止這種情況一直重復(fù)，每個(gè)節(jié)點(diǎn)的election 超時(shí)時(shí)間是(150~300ms)的隨機(jī)數(shù)铡羡， 這樣在一個(gè)term就會(huì)有一個(gè)節(jié)點(diǎn)很快超時(shí)進(jìn)入下一個(gè)term积蔚， 然后就能在別的節(jié)點(diǎn)timeout之前贏得選舉
- 這個(gè)節(jié)點(diǎn)贏得選舉
- Log replication
當(dāng)leader選出來后，他就可以正式給客戶端提供服務(wù)烦周。 leader會(huì)將請(qǐng)求以entry的形式追加到自己的log中尽爆，并且將這個(gè)entry以AppendEntries RPC并發(fā)發(fā)送給所有的follower節(jié)點(diǎn)。 當(dāng)這個(gè)entry成功的復(fù)制后（怎么算成功之后會(huì)談到）论矾， leader會(huì)將這個(gè)entry 應(yīng)用到自己的state machine并且給client返回成功教翩。 如果復(fù)制失敗， leader會(huì)一直重試AppendEntries RPC直到所有l(wèi)og entry都被成功復(fù)制贪壳。
Logs 組織的形式如圖所示饱亿。 當(dāng)leader收到一個(gè)Log entry時(shí)， 每個(gè)log entry都會(huì)存儲(chǔ)一個(gè)帶有term number的state machine命令闰靴。 Term number是用來探測(cè)log之間的不一致性并且保證Figure3的一些特性彪笼。 每個(gè)log也還帶有他們?cè)趌og里的索引數(shù)字。
當(dāng)leader認(rèn)為這個(gè)entry是可以成功應(yīng)用到狀態(tài)機(jī)上蚂且， 那么這個(gè)entry就被成為commited配猫。Raft保證所有commited entry最終都會(huì)被應(yīng)用到所有的節(jié)點(diǎn)上。
當(dāng)一個(gè)entry被成功復(fù)制到半數(shù)以上的節(jié)點(diǎn)后杏死， 這個(gè)log就可以認(rèn)為成功寫入了泵肄。并且會(huì)將leader之前的寫入也視為commit。
設(shè)計(jì)Raft日志機(jī)制不僅簡(jiǎn)化了系統(tǒng)的行為淑翼， 也保證了正確性腐巢。 保證了Figure3的以下特性
1. 當(dāng)不同log中的兩個(gè)entry有相同的term和index， 那么這兩個(gè)entry就是相同的
2. 當(dāng)不同log中的兩個(gè)entry有相同的term和index玄括， 那么這兩個(gè)entry之前的所有entry也都是相同的
當(dāng)leader發(fā)現(xiàn)follower的log跟自己的不同時(shí)冯丙， 他會(huì)針對(duì)每個(gè)follower維護(hù)一個(gè)nextIndex。 這個(gè)nextIndex就是Leader下次會(huì)發(fā)第幾個(gè)entry給這個(gè)follower遭京。 而follower也會(huì)拒絕這個(gè)append entry的rpc胃惜。
Safety
- 如何保證數(shù)據(jù)不丟失和數(shù)據(jù)的正確性是分布式數(shù)據(jù)庫最重要的兩點(diǎn)泞莉， Raft協(xié)議也設(shè)計(jì)了相應(yīng)的算法來保證這兩點(diǎn)。
- 所有的entry都只能從leader流向follower船殉，而要成為leader必須有所有的committed entries鲫趁。 如果有server發(fā)現(xiàn)candidate的數(shù)據(jù)沒有自己更update-to-date, 那么他會(huì)拒絕這個(gè)vote request。 如果兩個(gè)server的log term不同捺弦， 那么term number更大的更update-to-date, 如果term相同饮寞， 那么index更大的更update-to-date。
-
僅有第一點(diǎn)的保證我們?nèi)耘f可能會(huì)遇到問題列吼。 如上圖所示幽崩， a） s1成為leader，部分拷貝了index 2; b) s1掛了寞钥， s5成為leader, 寫入index 3; c）s5又掛了慌申， s1再次成為leader并且繼續(xù)將index 2拷貝到其余follower； d) s1又一次掛了理郑， s5成為leader(獲得2,3,4的選票)蹄溉， 將自己所有的s3拷貝到別的機(jī)器并且覆蓋掉了index 2; e)如果c階段沒有掛那么日志會(huì)被拷貝到s2,s3, 之后s5就不會(huì)被選為leader。
上圖演示了寫入數(shù)據(jù)可能會(huì)被覆蓋的問題您炉， 那么如何避免這個(gè)問題柒爵。 Raft規(guī)定絕不通過計(jì)算副本數(shù)的方式commit 之前term的log entries。 只有當(dāng)前term的log enties使用計(jì)算副本的方式來提交赚爵。 對(duì)于之前的term來說棉胀，當(dāng)一個(gè)log通過這個(gè)方式提交成功了，那么他之前的所有l(wèi)og都算commit成功了冀膝。如何證明這個(gè)結(jié)論的正確性唁奢， 論文用反證法進(jìn)行了論證：
如Figure 4所示， 如果term T commit的數(shù)據(jù)在之后的term U丟失了窝剖， 那么
1. 這個(gè)log一定不在Leader-U的log中（因?yàn)閘eader不會(huì)覆蓋舊數(shù)據(jù)）
2. Leader-T把這個(gè)日志復(fù)制給了大多數(shù)節(jié)點(diǎn)并且Leader-U收到了大多數(shù)節(jié)點(diǎn)的投票麻掸， 所以至少有一個(gè)節(jié)點(diǎn)是既收到了這個(gè)entry并且又給Leader-U投票了
3. 那么這個(gè)投票的節(jié)點(diǎn)也一定收到了所有Leader-T的commited entries
4. 因?yàn)檫@個(gè)投票節(jié)點(diǎn)把票投給了U, 那么說明Leader-U也至少有所有這個(gè)節(jié)點(diǎn)的entries
由此可知， 如果投票節(jié)點(diǎn)和Leader-U 共享了之前的log赐纱， 那么Leader-U肯定會(huì)有所有投票節(jié)點(diǎn)的entry脊奋。 另外， Leader-U的last-log-term必須比T大疙描， 而投票節(jié)點(diǎn)的term至少是T狂魔。之前term的leader在復(fù)制entry給Leader-U時(shí)也必須包含了之前的這個(gè)entry。 投票節(jié)點(diǎn)和之前term的leader都會(huì)有這個(gè)entry淫痰， 所以Leader-U也不會(huì)沒有這個(gè)entry≌荩可下結(jié)論所有大于T的term的leader絕對(duì)包含了所有term T commited的entries待错。
