Raft，分布式共識算法，是工程上使用較為廣泛的強(qiáng)一致性、去中心化、高可用的分布式協(xié)議。如redis-sentinel，etcd等都使用Raft協(xié)議解決分布式一致性的問題。
Nacos注冊中心是阿里巴巴貢獻(xiàn)的開源項目，兼具服務(wù)注冊發(fā)現(xiàn)、動態(tài)配置管理、動態(tài)DNS等功能。nacos集群使用了raft協(xié)議，來解決分布式一致性問題。
一、Raft算法概述
Raft算法由leader節(jié)點(diǎn)來處理一致性問題。leader節(jié)點(diǎn)接收來自客戶端的請求日志數(shù)據(jù)，然后同步到集群中其它節(jié)點(diǎn)進(jìn)行復(fù)制，當(dāng)日志已經(jīng)同步到超過半數(shù)以上節(jié)點(diǎn)的時候，leader節(jié)點(diǎn)再通知集群中其它節(jié)點(diǎn)哪些日志已經(jīng)被復(fù)制成功，可以提交到raft狀態(tài)機(jī)中執(zhí)行。
通過以上方式，Raft算法將要解決的一致性問題分為了以下幾個子問題。
- leader選舉：集群中必須存在一個leader節(jié)點(diǎn)。
- 日志復(fù)制：leader節(jié)點(diǎn)接收來自客戶端的請求，然后將這些請求序列化成日志數(shù)據(jù)再同步到集群中其它節(jié)點(diǎn)。
- 安全性：如果某個節(jié)點(diǎn)已經(jīng)將一條提交過的數(shù)據(jù)輸入raft狀態(tài)機(jī)執(zhí)行了，那么其它節(jié)點(diǎn)不可能再將相同索引的另一條日志數(shù)據(jù)輸入到raft狀態(tài)機(jī)中執(zhí)行。
Raft節(jié)點(diǎn)有三種狀態(tài)，follower、candidate、leader。
- Leader：領(lǐng)導(dǎo)者，一個集群里只能存在一個Leader。
- Follower：跟隨者，F(xiàn)ollower是被動的，一個客戶端的修改數(shù)據(jù)請求如果發(fā)送到Follower上面時，會首先由Follower重定向到Leader上。
- Candidate：參與者，一個節(jié)點(diǎn)切換到這個狀態(tài)時，將開始進(jìn)行一次新的選舉。
各狀態(tài)之間的轉(zhuǎn)化如下圖：
上圖中標(biāo)記了狀態(tài)切換的6種路徑，下面做一個簡單介紹。
- start up：起始狀態(tài)，節(jié)點(diǎn)剛啟動的時候自動進(jìn)入的是follower狀態(tài)。
- times out, starts election：follower在啟動之后，將開啟一個選舉超時的定時器，當(dāng)這個定時器到期時，將切換到candidate狀態(tài)發(fā)起選舉。
- times out, new election：進(jìn)入candidate 狀態(tài)之后就開始進(jìn)行選舉，但是如果在下一次選舉超時到來之前，都還沒有選出一個新的leader，那么還會保持在candidate狀態(tài)重新開始一次新的選舉。
- receives votes from majority of servers：當(dāng)candidate狀態(tài)的節(jié)點(diǎn)，收到了超過半數(shù)的節(jié)點(diǎn)選票，那么將切換狀態(tài)成為新的leader。
- discovers current leader or new term：candidate狀態(tài)的節(jié)點(diǎn)，如果收到了來自leader的消息，或者更高任期號的消息，都表示已經(jīng)有l(wèi)eader了，將切換回到follower狀態(tài)。
- discovers server with higher term：leader狀態(tài)下如果收到來自更高任期號的消息，將切換到follower狀態(tài)。這種情況大多數(shù)發(fā)生在有網(wǎng)絡(luò)分區(qū)的狀態(tài)下。
關(guān)于Raft協(xié)議，首先，可以看一下動畫，初步認(rèn)識一下這個分布式公式算法的具體步驟。
http://thesecretlivesofdata.com/raft/
整個過程大致分為 Leader選舉（Leader Election ）、日志復(fù)制（Log Replication） 兩步。
二、Leader選舉（Leader Election）
Raft算法是使用心跳機(jī)制來觸發(fā)leader選舉的。
①所有節(jié)點(diǎn)一開始都是follower狀態(tài)，一定時間未收到leader的心跳，則進(jìn)入candidate狀態(tài)，參與選舉；
②選出leader后，leader通過向follower發(fā)送心跳來表明存活狀態(tài)，若leader故障，則整體退回到 ①中的狀態(tài)；
③每次選舉完成后，會產(chǎn)生一個term，term本身是遞增的，充當(dāng)了邏輯時鐘的作用；
具體的選舉過程：
等待heartbeat，若超時未等到，準(zhǔn)備選舉---->新增當(dāng)前任期號（term），轉(zhuǎn)變?yōu)閏andidate狀態(tài)---->給自己投票，然后給其他節(jié)點(diǎn)發(fā)送投票請求---->等待選舉結(jié)果。
每一次開始一次新的選舉時，稱為一個“任期”。每個任期都有一個對應(yīng)的整數(shù)與之關(guān)聯(lián)，稱為“任期號”，任期號用單詞“Term”表示，這個值是一個嚴(yán)格遞增的整數(shù)值。
Raft節(jié)點(diǎn)之間通過RPC請求來互相通信，主要有以下兩類RPC請求。RequestVote RPC用于candidate狀態(tài)的節(jié)點(diǎn)進(jìn)行選舉之用，而AppendEntries RPC由leader節(jié)點(diǎn)向其他節(jié)點(diǎn)復(fù)制日志數(shù)據(jù)以及同步心跳數(shù)據(jù)的。
具體投票過程有三個約束：
（1）在同一任期內(nèi)，單個節(jié)點(diǎn)最多只能投一票；
（2）候選人知道的信息不能比自己的少(Log與term)；
（3）first-come-first-served 先來先得。
選舉的三種情況：
第一種情況，贏得選舉之后，leader會給所有節(jié)點(diǎn)發(fā)送消息，避免其他節(jié)點(diǎn)觸發(fā)新的選舉
第二種情況，比如有三個節(jié)點(diǎn)A B C。A B同時發(fā)起選舉，而A的選舉消息先到達(dá)C，C給A投了一票，當(dāng)B的消息到達(dá)C時，已經(jīng)不能滿足上面提到的第一個約束，即C不會給B投票，而A和B顯然都不會給對方投票。A勝出之后，會給B,C發(fā)心跳消息，節(jié)點(diǎn)B發(fā)現(xiàn)節(jié)點(diǎn)A的term不低于自己的term，知道有已經(jīng)有Leader了，于是轉(zhuǎn)換成follower
第三種情況， 沒有任何節(jié)點(diǎn)獲得majority投票，可能是平票的情況。加入總共有四個節(jié)點(diǎn)（A/B/C/D），Node C、Node D同時成為了candidate，但Node A投了Node D一票，NodeB投了Node C一票，這就出現(xiàn)了平票 split vote的情況。這個時候大家都在等啊等，直到超時后重新發(fā)起選舉。如果出現(xiàn)平票的情況，那么就延長了系統(tǒng)不可用的時間,因此raft引入了randomized election timeouts來盡量避免平票情況
數(shù)據(jù)的處理：
對于事務(wù)操作，請求會轉(zhuǎn)發(fā)給leader；
非事務(wù)操作上，可以任意一個節(jié)點(diǎn)來處理；
三、日志復(fù)制（Log Replication）
日志復(fù)制的流程大體如下：
- 每個客戶端的請求都會被重定向發(fā)送給leader，這些請求最后都會被輸入到raft算法狀態(tài)機(jī)中去執(zhí)行。
- leader在收到這些請求之后，會首先在自己的日志中添加一條新的日志條目。
- 在本地添加完日志之后，leader將向集群中其他節(jié)點(diǎn)發(fā)送AppendEntries RPC請求同步這個日志條目，當(dāng)這個日志條目被成功復(fù)制之后，leader節(jié)點(diǎn)將會將這條日志輸入到raft狀態(tài)機(jī)中，然后應(yīng)答客戶端。
Raft日志的組織形式如下圖所示：
每個日志條目包含以下成員：
1. index：日志索引號，即圖中最上方的數(shù)字，是嚴(yán)格遞增的。
2. term：日志任期號，就是在每個日志條目中上方的數(shù)字，表示這條日志在哪個任期生成的。
3. command：日志條目中對數(shù)據(jù)進(jìn)行修改的操作。
一條日志如果被leader同步到集群中超過半數(shù)的節(jié)點(diǎn)，那么被稱為“成功復(fù)制”，這個日志條目就是“已被提交（committed）”。如果一條日志已被提交，那么在這條日志之前的所有日志條目也是被提交的，包括之前其他任期內(nèi)的leader提交的日志。如上圖中索引為7的日志條目之前的所有日志都是已被提交的日志。
四、為什么 Raft 通常推薦使用奇數(shù)節(jié)點(diǎn)而不是偶數(shù)節(jié)點(diǎn)？
Raft 一般會使用奇數(shù)個節(jié)點(diǎn)，比如 3，5，7 等等。這是因為 raft 是 一種基于多節(jié)點(diǎn)投票選舉機(jī)制的共識算法，通俗地說，只有超過半數(shù)節(jié)點(diǎn)在線才能提供服務(wù)。這里超過半數(shù)的意思是N/2+1（而不是N/2），舉例來說，3 節(jié)點(diǎn)集群需要 2 個以上節(jié)點(diǎn)在線，5 節(jié)點(diǎn)集群需要 3 個以上節(jié)點(diǎn)在線，等等。對于偶數(shù)節(jié)點(diǎn)的集群，2 節(jié)點(diǎn)集群需要 2 節(jié)點(diǎn)同時在線，4 節(jié)點(diǎn)集群需要 3 節(jié)點(diǎn)在線，以此類推。實(shí)際上不只是 Raft，所有基于 Quorum 的共識算法大體上都是這么個情況，例如 Paxos，Zookeeper 什么的，本文僅以 Raft 為例討論。
共識算法要解決的核心問題是什么呢？
是分布式系統(tǒng)中單個節(jié)點(diǎn)的不可靠造成的不可用或者數(shù)據(jù)丟失。Raft 保存數(shù)據(jù)冗余副本來解決這兩個問題，當(dāng)少數(shù)節(jié)點(diǎn)發(fā)生故障時，剩余的節(jié)點(diǎn)會自動重新進(jìn)行 leader 選舉（如果需要）并繼續(xù)提供服務(wù)，而且 log replication 流程也保證了剩下的節(jié)點(diǎn)（構(gòu)成 Quorum，法定人數(shù)）總是包含了故障前成功寫入的最新數(shù)據(jù)，因此也不會發(fā)生數(shù)據(jù)丟失。
我們對比一下 3 節(jié)點(diǎn)的集群和 4 節(jié)點(diǎn)的集群，Quorum 分別是 2 和 3，它們能容忍的故障節(jié)點(diǎn)數(shù)都是 1。如果深究的話，從概率上來說 4 節(jié)點(diǎn)集群發(fā)生 2 節(jié)點(diǎn)同時故障的可能性要更高一些。于是我們發(fā)現(xiàn)，相對于 3 節(jié)點(diǎn)集群，4 節(jié)點(diǎn)集群消耗更多的硬件資源，卻換來了更差的可用性，顯然不是個好選擇。
五、Nacos Naming服務(wù)一致性實(shí)現(xiàn)
Naming服務(wù)支持兩種類型的數(shù)據(jù)存儲：臨時和永久數(shù)據(jù)。永久數(shù)據(jù)一旦創(chuàng)建之后會一直存在，除非顯式刪除；臨時數(shù)據(jù)創(chuàng)建之后和所有者的生命周期綁定，需要創(chuàng)建者不斷發(fā)送心跳信息來保證數(shù)據(jù)的有效性。
1. RaftConsistencyServiceImpl類
RaftConsistencyServiceImpl類提供的是基于Raft協(xié)議的永久數(shù)據(jù)存儲方案。nacos naming服務(wù)內(nèi)部實(shí)現(xiàn)了一個簡化的Raft協(xié)議。每個節(jié)點(diǎn)通過本地文件系統(tǒng)保存所有數(shù)據(jù)，通過Raft協(xié)議選擇Leader并同步數(shù)據(jù)。Raft協(xié)議通過保證數(shù)據(jù)在各naming節(jié)點(diǎn)的一致性來保證naming服務(wù)的高可用。
2. DistroConsistencyServiceImpl類
DistroConsistencyServiceImpl用于存儲臨時數(shù)據(jù)。由于nacos的臨時數(shù)據(jù)需要通過創(chuàng)建者不斷得發(fā)送心跳數(shù)據(jù)來保活，因此在存儲上反而比較簡單。naming服務(wù)并不會在文件系統(tǒng)或者數(shù)據(jù)庫中持久化存儲臨時數(shù)據(jù)，它通過心跳包來保證數(shù)據(jù)的有效性。
naming服務(wù)使用一種“分區(qū)”算法來管理臨時數(shù)據(jù)。它把所有數(shù)據(jù)分為若干個block，每個naming節(jié)點(diǎn)只負(fù)責(zé)一個block內(nèi)數(shù)據(jù)的創(chuàng)建/刪除/同步。通過數(shù)據(jù)同步，每個naming節(jié)點(diǎn)最終都會持有完整的數(shù)據(jù)集合。
