別再懷疑自己的智商了，Raft協議本來就不好理解

github.com

最近花了一些時間把他的代碼通讀了一邊，發現居然都可以理解，感覺離自己造輪子更近了一步。加上之前實現過RPC框架，再擼一套Raft服務應該是可以很快變成現實了。

首先我們假設有三個RaftNode，每個RaftNode都會開設一個埠，這個埠的作用就是接受客戶端的(Get/Set)請求以及其它RaftNode的RPC請求。這裡需要說明的是多數著名開源項目一般會選擇兩個埠，一個面向客戶端，一個面向RPC，好處是可以選擇不同的IP地址，客戶端埠可以面向外網，而RPC則是安全的內網通信。作者選擇了一個埠是因為只用於內網，在實現上也會簡單不少。

客戶端可以連接任意一個節點。如果連接的不是Leader，那麼發送的請求會在服務端進行轉發，從當前連接的RaftNode轉發到Leader進行處理。另外一種可選的設計是所有的客戶端都連接到Leader，這樣就避免了轉發的過程，可以提升性能。

但是服務端轉發也有它的好處，那就是當客戶端在數據一致性要求不好的情況下，讀請求可以不用轉發，直接在當前的RaftNode進行處理。所以返回的數據可能不是實時的。這可以擋住大部分客戶端請求，提升整體的讀性能。

RaftNode中包含的重要組件都在這張圖上了。

首先Local Server接收到請求後，立即將請求日誌附加到SegmentedLog中，這個日誌會實時存到文件系統中，同時內存里也會保留一份。因為作者考慮到日誌文件過大可能會影響性能和安全性（具體原因未知，Redis的aof日誌咋就不需要分段呢），所以對日誌做了分段處理，順序分成多個文件，所以叫SegmentedLog。

日誌有四個重要的索引，分別是firstLogIndex/lastLogIndex和commitIndex/applyIndex，前兩個就是當前內存中日誌的開始和結束索引位置，後面兩個是日誌的提交索引和生效索引。之所以是用firstLogIndex而不是直接用零，是因為日誌文件如果無限增長會非常龐大，Raft有策略會定時清理久遠的日誌，所以日誌的起始位置並不是零。commitIndex指的是過半節點都成功同步的日誌的最大位置，這個位置之前的日誌都是安全的可以應用到狀態機中。Raft會將當前已經commit的日誌立即應用到狀態機中，這裡使用applyIndex來標識當前已經成功應用到狀態機的日誌索引。

該項目示例提供的狀態機是RocksDB。RocksDB提供了高效的鍵值對存儲功能。實際使用時還有很多其它選擇，比如使用純內存的kv或者使用leveldb。純內存的缺點就是資料庫的內容都在內存中，Rocksdb/Leveldb的好處就是可以落盤，減輕內存的壓力，性能自然也會有所折損。

如果伺服器設置了本地落盤即可返回(isAsyncWrite)，那麼Local Server將日誌塞進SegmentedLog之後就會立即向客戶端返回請求成功消息。但是這可能會導致數據安全問題。因為Raft協議要求必須等待過半伺服器成功響應後才可以認為數據是安全的，才可以告知客戶端請求成功。之所以提供了這樣一個配置項，純粹是為了性能考慮。分散式資料庫Kafka同樣也有類似的選項。是通過犧牲數據一致性來提高性能的折中方法。

正常情況下，Local Server通過一個Condition變數的await操作懸掛住當前的請求不予返回。

對於每個RPCClient，它也要維護日誌的兩個索引，一個是matchIndex表示對方節點已經成功同步的位置，可以理解為局部的commitIndex。而nextIndex就是下一個要同步的日誌索引位置。隨著Leader和Follower之間的消息同步，matchIndex會努力追平nextIndex。同樣隨著客戶端的請求的連續到來，nextIndex也會持續前進。

Local Server在懸掛住用戶的請求後，會立即發出一次非同步日誌同步操作。它會通過RPC Client向其它節點發送一個AppendEntries消息（也是心跳消息），包含當前尚未同步的所有日誌數據(從commitIndex到lastLogIndex)。然後等待對方實時反饋。如果反饋成功，就可以前進當前的日誌同步位置matchIndex。

matchIndex是每個RPCClient局部的位置，當有過半RPCClient的matchIndex都前進了，那麼全局的commitIndex也就可以隨之前進，取過半節點的matchIndex最小值即可。

commitIndex一旦前進，意味著前面的日誌都已經成功提交了，那麼懸掛的客戶端也可以繼續下去了。所以立即通過Condition變數的signalAll操作喚醒所有正在懸掛住的請求，通知它們馬上給客戶端響應。

注意日誌同步時還得看節點日誌是否落後太多，如果落後太多，通過AppendEntries這種方式同步是比較慢的，這時就是要考慮走另一條路線來同步日誌，那就是snapshot快照同步。

快照同步就是Leader將最新的快照文件發送到Follower節點，Follower安裝快照後成功後，Leader繼續同步SegmentedLog，力圖讓Follower追平自己。

RaftNode初始是處於Follower狀態，啟動後立即開啟一個startNewElection定時器，在這個定時器到點之前如果沒有收到來自Leader的心跳消息或者其它Candidate的請求投票消息，就立即變身成為Candidate，發起新一輪選舉過程。

集群成員變化

分散式系統的一個非常頭疼的問題就是同樣的動作發生的時間卻不一樣。比如上圖的集群從3個變成5個，集群的配置從OldConfig變成NewConfig，這些節點配置轉變的時間並不完全一樣，存在一定的偏差，於是就形成了新舊配置的疊加態。

在圖中紅色剪頭的時間點，舊配置的集群下Server[1,2]可以選舉Server1為Leader，Server3不同意沒關係，過半就行。而同樣的時間，新配置的集群下Server[3,4,5]則可以選舉出Server5為另外一個Leader。這時候就存在多Leader並存問題。

為了避免這個問題，Raft使用單節點變更演算法。一次只允許變動一個節點，並且要按順序變更，不允許並行交叉，否則會出現混亂。如果你想從3個節點變成5個節點，那就先變成4節點，再變成5節點。變更單節點的好處是集群不會分裂，不會同時存在兩個Leader。

如圖所示，藍色圈圈代表舊配置的大多數(majority)，紅色圈圈代碼新配置的帶多數。新舊配置下兩個集群的大多數必然會重疊(舊配置節點數2k的大多數是k+1，新配置節點數2k+1的大多數是k+1，兩個集群的大多數之和是2k+2大於集群的節點數2k+1)。這兩個集群的term肯定不一樣，而同一個節點不可能有兩個term。所以這個重疊的節點只會屬於一個大多數，最終也就只會存在一個集群，也就只有一個Leader。

集群變更操作日誌不同於普通日誌。普通日誌要等到commit之後才可以apply到狀態機，而集群變更日誌在leader將日誌追加持久化後，就可以立即apply。為什麼要這麼做，可以參考知乎孫建良的這篇文章 https://zhuanlan.zhihu.com/p/29678067，這裡面精細描述了commit & reply集群變更日誌帶來的集群不可用的場景。

關注公眾號「碼洞」，加入我們一起來進階Raft演算法。