Raft，分布式共識算法，是工程上使用較為廣泛的強一致性、去中心化、高可用的分布式協議。如redis-sentinel，etcd等都使用Raft協議解決分布式一致性的問題。

Nacos注冊中心是阿里巴巴貢獻的開源項目，兼具服務注冊發現、動態配置管理、動態DNS等功能。nacos集群使用了raft協議，來解決分布式一致性問題。

一、Raft算法概述

Raft算法由leader節點來處理一致性問題。leader節點接收來自客戶端的請求日志數據，然后同步到集群中其它節點進行復制，當日志已經同步到超過半數以上節點的時候，leader節點再通知集群中其它節點哪些日志已經被復制成功，可以提交到raft狀態機中執行。

通過以上方式，Raft算法將要解決的一致性問題分為了以下幾個子問題。

• leader選舉：集群中必須存在一個leader節點。
• 日志復制：leader節點接收來自客戶端的請求，然后將這些請求序列化成日志數據再同步到集群中其它節點。
• 安全性：如果某個節點已經將一條提交過的數據輸入raft狀態機執行了，那么其它節點不可能再將相同索引的另一條日志數據輸入到raft狀態機中執行。

Raft節點有三種狀態，follower、candidate、leader。

• Leader：領導者，一個集群里只能存在一個Leader。
• Follower：跟隨者，Follower是被動的，一個客戶端的修改數據請求如果發送到Follower上面時，會首先由Follower重定向到Leader上。
• Candidate：參與者，一個節點切換到這個狀態時，將開始進行一次新的選舉。

各狀態之間的轉化如下圖：

上圖中標記了狀態切換的6種路徑，下面做一個簡單介紹。

• start up：起始狀態，節點剛啟動的時候自動進入的是follower狀態。
• times out, starts election：follower在啟動之后，將開啟一個選舉超時的定時器，當這個定時器到期時，將切換到candidate狀態發起選舉。
• times out, new election：進入candidate 狀態之后就開始進行選舉，但是如果在下一次選舉超時到來之前，都還沒有選出一個新的leader，那么還會保持在candidate狀態重新開始一次新的選舉。
• receives votes from majority of servers：當candidate狀態的節點，收到了超過半數的節點選票，那么將切換狀態成為新的leader。
• discovers current leader or new term：candidate狀態的節點，如果收到了來自leader的消息，或者更高任期號的消息，都表示已經有leader了，將切換回到follower狀態。
• discovers server with higher term：leader狀態下如果收到來自更高任期號的消息，將切換到follower狀態。這種情況大多數發生在有網絡分區的狀態下。

關于Raft協議，首先，可以看一下動畫，初步認識一下這個分布式公式算法的具體步驟。

http://thesecretlivesofdata.com/raft/

整個過程大致分為 Leader選舉（Leader Election ）、日志復制（Log Replication） 兩步。

二、Leader選舉（Leader Election）

Raft算法是使用心跳機制來觸發leader選舉的。

①所有節點一開始都是follower狀態，一定時間未收到leader的心跳，則進入candidate狀態，參與選舉；

②選出leader后，leader通過向follower發送心跳來表明存活狀態，若leader故障，則整體退回到 ①中的狀態；

③每次選舉完成后，會產生一個term，term本身是遞增的，充當了邏輯時鐘的作用；

具體的選舉過程：

等待heartbeat，若超時未等到，準備選舉---->新增當前任期號（term），轉變為candidate狀態---->給自己投票，然后給其他節點發送投票請求---->等待選舉結果。

每一次開始一次新的選舉時，稱為一個“任期”。每個任期都有一個對應的整數與之關聯，稱為“任期號”，任期號用單詞“Term”表示，這個值是一個嚴格遞增的整數值。

Raft節點之間通過RPC請求來互相通信，主要有以下兩類RPC請求。RequestVote RPC用于candidate狀態的節點進行選舉之用，而AppendEntries RPC由leader節點向其他節點復制日志數據以及同步心跳數據的。

具體投票過程有三個約束：

（1）在同一任期內，單個節點最多只能投一票；

（2）候選人知道的信息不能比自己的少(Log與term)；

（3）first-come-first-served 先來先得。

選舉的三種情況：

第一種情況，贏得選舉之后，leader會給所有節點發送消息，避免其他節點觸發新的選舉

第二種情況，比如有三個節點A B C。A B同時發起選舉，而A的選舉消息先到達C，C給A投了一票，當B的消息到達C時，已經不能滿足上面提到的第一個約束，即C不會給B投票，而A和B顯然都不會給對方投票。A勝出之后，會給B,C發心跳消息，節點B發現節點A的term不低于自己的term，知道有已經有Leader了，于是轉換成follower

第三種情況， 沒有任何節點獲得majority投票，可能是平票的情況。加入總共有四個節點（A/B/C/D），Node C、Node D同時成為了candidate，但Node A投了Node D一票，NodeB投了Node C一票，這就出現了平票 split vote的情況。這個時候大家都在等啊等，直到超時后重新發起選舉。如果出現平票的情況，那么就延長了系統不可用的時間,因此raft引入了randomized election timeouts來盡量避免平票情況

數據的處理：

對于事務操作，請求會轉發給leader；

非事務操作上，可以任意一個節點來處理；

三、日志復制（Log Replication）

日志復制的流程大體如下：

• 每個客戶端的請求都會被重定向發送給leader，這些請求最后都會被輸入到raft算法狀態機中去執行。
• leader在收到這些請求之后，會首先在自己的日志中添加一條新的日志條目。
• 在本地添加完日志之后，leader將向集群中其他節點發送AppendEntries RPC請求同步這個日志條目，當這個日志條目被成功復制之后，leader節點將會將這條日志輸入到raft狀態機中，然后應答客戶端。

Raft日志的組織形式如下圖所示：

每個日志條目包含以下成員：

1. index：日志索引號，即圖中最上方的數字，是嚴格遞增的。

2. term：日志任期號，就是在每個日志條目中上方的數字，表示這條日志在哪個任期生成的。

3. command：日志條目中對數據進行修改的操作。

一條日志如果被leader同步到集群中超過半數的節點，那么被稱為“成功復制”，這個日志條目就是“已被提交（committed）”。如果一條日志已被提交，那么在這條日志之前的所有日志條目也是被提交的，包括之前其他任期內的leader提交的日志。如上圖中索引為7的日志條目之前的所有日志都是已被提交的日志。

四、為什么 Raft 通常推薦使用奇數節點而不是偶數節點？

Raft 一般會使用奇數個節點，比如 3，5，7 等等。這是因為 raft 是 一種基于多節點投票選舉機制的共識算法，通俗地說，只有超過半數節點在線才能提供服務。這里超過半數的意思是N/2+1（而不是N/2），舉例來說，3 節點集群需要 2 個以上節點在線，5 節點集群需要 3 個以上節點在線，等等。對于偶數節點的集群，2 節點集群需要 2 節點同時在線，4 節點集群需要 3 節點在線，以此類推。實際上不只是 Raft，所有基于 Quorum 的共識算法大體上都是這么個情況，例如 Paxos，Zookeeper 什么的，本文僅以 Raft 為例討論。

共識算法要解決的核心問題是什么呢？

是分布式系統中單個節點的不可靠造成的不可用或者數據丟失。Raft 保存數據冗余副本來解決這兩個問題，當少數節點發生故障時，剩余的節點會自動重新進行 leader 選舉（如果需要）并繼續提供服務，而且 log replication 流程也保證了剩下的節點（構成 Quorum，法定人數）總是包含了故障前成功寫入的最新數據，因此也不會發生數據丟失。

我們對比一下 3 節點的集群和 4 節點的集群，Quorum 分別是 2 和 3，它們能容忍的故障節點數都是 1。如果深究的話，從概率上來說 4 節點集群發生 2 節點同時故障的可能性要更高一些。于是我們發現，相對于 3 節點集群，4 節點集群消耗更多的硬件資源，卻換來了更差的可用性，顯然不是個好選擇。

五、Nacos Naming服務一致性實現

Naming服務支持兩種類型的數據存儲：臨時和永久數據。永久數據一旦創建之后會一直存在，除非顯式刪除；臨時數據創建之后和所有者的生命周期綁定，需要創建者不斷發送心跳信息來保證數據的有效性。

1. RaftConsistencyServiceImpl類

RaftConsistencyServiceImpl類提供的是基于Raft協議的永久數據存儲方案。nacos naming服務內部實現了一個簡化的Raft協議。每個節點通過本地文件系統保存所有數據，通過Raft協議選擇Leader并同步數據。Raft協議通過保證數據在各naming節點的一致性來保證naming服務的高可用。

2. DistroConsistencyServiceImpl類

DistroConsistencyServiceImpl用于存儲臨時數據。由于nacos的臨時數據需要通過創建者不斷得發送心跳數據來?；?，因此在存儲上反而比較簡單。naming服務并不會在文件系統或者數據庫中持久化存儲臨時數據，它通過心跳包來保證數據的有效性。

naming服務使用一種“分區”算法來管理臨時數據。它把所有數據分為若干個block，每個naming節點只負責一個block內數據的創建/刪除/同步。通過數據同步，每個naming節點最終都會持有完整的數據集合。