hashicorp Raft是raft共識算法的golang版本經典實現，閱讀它有利於深入熟悉raft細節，也有利於熟悉golang的處理範式，編程方式。
五一在家宅著不能出去，正好從頭看了一遍raft源碼。感覺之前很多不清晰、不明確的地方豁然開朗。同時又再一次震驚於golang並發處理的強大：select/chan/waitGroup等語法糖越吃越香，不得不感慨life is too short to learn C++。
此後會花時間陸陸續續整理一些讀書筆記出來，將思路再理順一遍。
我的hashicorp raft閱讀筆記分為4部分，本文主要為前2部分：
1、 概況
2、 hashicorp raft 核心數據結構
3、 hashicorp raft 對典型問題的處理：領導選舉、日誌複製
4、 處理流程：CRUD操作是如何落地的
一、概覽分布式共識算法CAP理論
根據CAP理論：一致性(Consistency), 可用性(Availability), 分區容錯性(Partition tolerance) 三者不可全得。而分布式系統，天然要優先滿足P；所以一個分布式系統大體要麼是AP的，要麼是CP的。
對於數據本身而言，CP的系統捨棄了可用性，一旦讀取數據，一定會讀到最新的數據；要麼讀不到響應。而AP系統，則一定能讀到響應，但有可能讀到舊數據。
由於CAP三者不可全得，所以系統總是在一致性（如ACID）和可用性（如電商常用的BASE）之間做trade-off。
一致性
幾個容易混淆的概念：
Consistency 和 Consensus：雖然很多中文翻譯都把它們翻譯成一致，其實並不是一個意思。Consensus是共識、只對某個提案達成一致意見的過程。在分布式場景中，通常就是幾個副本就一個值達成一致（比如set x = 10)。Paxos算法就是解決這個問題的。對一系列值達成共識，比如set x =10/x =20，對外就表現出一致性。所以一致性是對外呈現的狀態，共識是達成一致結果的一種手段和過程。
一致性分類：一致性分為嚴格一致性，強一致性（全局時鐘的線性一致性和順序一致性）,弱一致性；
共識算法
為了解決分布式系統的一致性問題，前人提出了許多算法。經典的有：paxos(包含basic-paxos和multi-paxos), raft, PBFT, POW等；
Raft
Raft屬於multi-paxos的一個變種，並在multi-paxos的基礎上做了簡化和優化，解決了multi-paxos難以實現和難以理解的問題。Raft是強領導者模型，所有的寫操作都只能通過leader來進行；leader節點負責與各follower節點達成一系列值的共識。hashicorp raft是一個典型的raft golang 實現，可以用它快速構建具有強一致性能力的系統。
Raft簡介理解Raft可以參考論文，github主頁，raft動畫演示。可以先看一下paxos的原理，建議不要直接讀蘭伯特的論文，否則你會覺得腦子有點chaos；然後看下raft的論文，raft的論文重點抓住Figure2那幾張圖，後續我會在筆記中解釋這張圖；然後看下raft動畫演示稍微放空下，再去git瞎逛逛瞎看看，下面有一堆的talk。比如開篇就通過吊打它老爸paxos的方式來介紹自己：
Raft is a consensus algorithm that is designed to be easy to understand. It's equivalent to Paxos in fault-tolerance and performance. The difference is that it's decomposed into relatively independent subproblems, and it cleanly addresses all major pieces needed for practical systems.
意思是，我跟paxos在容錯性和性能上一樣牛X，但是我說人話，你看得懂；而且我把理論分解成了幾個相對獨立的子問題，你只要稍微努力點也能擼出代碼來。
raft集群中的節點有三種類型的節點：Leader Candidate Follower。Leader負責處理寫請求、管理日誌複製、協調系統達成共識；follower是跟隨者，負責存儲日誌副本；candidate是候選節點。它們之間的狀態可能互相流轉：在leader節點故障時，follower節點可能推舉自己成為candidate，獲得quorum投票的candidate將當選為新的leader；原有的leader在恢復後，會轉為follower。
領導選舉
Raft 是強領導者模型，要對外提供服務，一定要確保有健康的Leader。只有最新、最全日誌的節點才能夠當選 Leader。一旦節點發現集群中沒有leader或者leader異常（連不上timeout，或收不到心跳），就會成為candidate發起投票、推舉自己為leader。獲得集群「大多數」 (quorumSize) 投票的節點會成為新的leader。
為了保證最新、最全，日誌完整度高的節點，拒絕投票給日誌完整度低的候選者；任期編號大的節點拒絕給任期編號小的節點投票（每次leader變更，任期編號加1；持續遞增）。
日誌複製
日誌由日誌項組成，日誌項中包含：用戶數據、索引信息、當前leader的任期等。可以看下hashicorp raft對於log的定義：
type log struct {
Index uint64 // 索引（raft日誌必須是連續的，每一條日誌項都有唯一的index）
Term uint64 // 當前索引項的leader任期
type LogType // 日誌項消息的類型：普通的用戶command, 配置更新等
Data []byte // 具體的用戶數據command
Extensions []byte // 擴展欄位，暫時不用管它
}
多條連續的日誌項組合在一起，就形成了日誌。follower的日誌必定是leader日誌的子集。 比如某個任期，leader日誌項是：
| 1 | 2| 3 | 4 | 5| 6 | 7 |
在其中的某個時刻，follower的日誌項可能是1-n (n <= 7)的某個集合。raft論文有張圖說明了這一點：
日誌複製 就是將leader的日誌，通過AppendEntries RPC消息複製到follower上。一旦過半的返回成功（成功commit）。
在hashicorp raft中，日誌複製是異步進行的。入口函數在runLeader的startStopReplication中，它會為每一個follower建立一個協程，負責處理日誌複製消息。而follower則會在processRpc方法中，處理appendEntries消息。
成員變更
成員變更包括三種情況：
1、 新節點加入集群
2、 follower節點掛掉了 （超時或者掛掉）
3、 leader節點掛掉了
新節點加入：
新節點加入集群要解決的問題是要防止集群腦裂，解決的辦法通常是通過單節點變更的方式。如果需要將一個3節點的集群擴張為5節點的集群，不是一次性加入兩個節點，而是一次加入一個節點、通過兩次變更達到目的。
hashicorpRaft中提供了AddPeer API來做新節點變更的入口，只有leader節點能處理這類消息。新節點變更會作為一條特殊的日誌項，提交到raft中。從而通知到整個集群。
follower節點掛掉了：
follower節點掛掉了，要解決的問題，是如何在節點恢復後，重新加入集群，並追上leader的日誌。這類問題和新節點加入沒有太大區別，需要注意的是，如果掛掉的follower過多。導致quorum(「大多數」)無法成立。整個集群也會不可用。
leader掛掉了：
leader掛掉的期間，在新leader選出來之前，整個集群是不可用的。如果其他副本的日誌都落後於leader，選出來的新leader後是有可能導致日誌丟失的。
為了解決此類問題，像kafka就是引入ISR副本的概念，ISR集合裡的副本都是能追的上leader的副本，一旦leader掛掉，將從ISR集合中選擇新的leader；如果ISR沒有一個可用的副本，而配置又不允許選擇unclean的副本成為leader，集群會整個不可用。
leader選舉的環節，要解決的問題是：儘快的選出更新、更全的leader。在前文有所提及。
二、hashicorp Raft關鍵數據結構raft代碼和很多其他開源的代碼一樣，注釋多到令人髮指（褒義詞）！舉個慄子：
// LeadershipTransfer will transfer leadership to a server in the cluster.
// This can only be called from the leader, or it will fail. The leader will
// stop accepting client requests, make sure the target server is up to date
// and starts the transfer with a TimeoutNow message. This message has the same
// effect as if the election timeout on the on the target server fires. Since
// it is unlikely that another server is starting an election, it is very
// likely that the target server is able to win the election. Note that raft
// protocol version 3 is not sufficient to use LeadershipTransfer. A recent
// version of that library has to be used that includes this feature. Using
// transfer leadership is safe however in a cluster where not every node has
// the latest version. If a follower cannot be promoted, it will fail
// gracefully.
func (r *Raft) LeadershipTransfer() Future {
if r.protocolVersion < 3 {
return errorFuture{ErrUnsupportedProtocol}
}
return r.initiateLeadershipTransfer(nil, nil)
}
細品一下就會發現，注釋一次爽一次，一直注釋一直爽。這種人如果去了按代碼行數付工資的公司，絕對是要被裁掉的節奏啊。
下面我會根據自己理解，對幾個關鍵的數據結構。做一點註解，方便我自己隨時翻閱。
raftraft數據結構定義在api.go文件中，每一個raft節點都會有一個實例。
由於raft結構包含的信息實在太多，本身的英文注釋又非常完備。這裡只列出了幾個我認為比較重要的結構。如下:
// Raft implements a Raft node.
type Raft struct {
// 日誌索引、任期、節點類型等信息
raftState
// logFutrue對象（後續介紹）
applyCh chan *logFuture
// 配置
conf Config
// raft有限狀態機
fsm FSM
// 節點在集群中的唯一ID（每個節點不一樣）
localID ServerID
// leader獨有的狀態
leaderState leaderState
// 日誌存儲媒介（比如存儲到磁碟、DB等）
logs LogStore
// 當前FSM的快照
snapshots SnapshotStore
// raft節點之間rpc通信的傳輸層，傳輸日誌複製、投票請求、超時處理等rpc
trans Transport
// raftState中 當前任期、投票給了誰的持久化存儲
stable StableStore
}
代碼中的數據結構，我都做了中文注釋。為更方便理解。參考論文中下圖：
注意到代碼中有 logStore和 FSM兩個對象，他們分別表示日誌的存儲和狀態機。對應著Raft中的兩個概念，commit和apply，commit一般指日誌被存儲到logStore中，而apply則是被應用到狀態機。
比如利用raft實現一直緩存的寫入操作，set x= 3；commit就是將set x= 3這條command記錄到日誌裡，同時會開啟日誌複製；apply就是會調用FSM中用戶實現的apply方法，在該方法中，你會將set x= 3這條指令在你的緩存中真正執行。
commit 與 apply之間的日誌，有個優雅的名字，叫做：infight。你得讓子彈飛一會才能apply到FSM。但一般來說，這個中間狀態應該很短。提交日誌和應用到狀態機不應該有延遲。
raft論文中有一張圖，描述了這些raft狀態：
其中需要持久化的任期、投票信息存儲在StableStore中；logs存儲在LogStore中。描述了commit/apply的位置信息叫做commitIndex, lastApplied；而leader獨有的狀態，則維護在leaderState中，它有一個commitment的對象：
type commitment struct {
sync.Mutex
// 通知commit消息待處理
commitCh chan struct{}
// matchIndexes 維護了每個follower與leader間的matchIndex
matchIndexes map[ServerID]uint64
// quorum follower commit成功的index
commitIndex uint64
// 該leader任期的commit起始位置
startIndex uint64
}
各種index，讓人不自覺想起kafka中的高水位、LEO等，是不是很類似？
FSM從上文了解到，fsm是raft的重要結構。看fsm代碼之前，我對fsm有點點發憷，因為在我的理解中。FSM一般都是動輒十幾個狀態轉來轉去，類成員必定是幾十個變量。事實上，遠非如此。
代碼貼完，好像也沒啥可說的了。就是這麼簡單：兩個方法分別是用來生成snapshot和加載snapshot的，還有一個需要使用者去實現，從log中取出command，並真正的執行apply把它寫到緩存或者什麼存儲之類的。所謂的狀態機也沒有十幾個狀態，代碼很清晰明了。
還記得前面說的commit/apply麼？processLogs會處理inflight消息，並構造commitTuple請求放入fsmMutateCh中，上圖中select第一個分支，會處理這個消息，執行fsm.Apply，並將響應通過future的response對象返回給調用方。
RPC protocolraft節點之間總共存在4種RPC：
AppendEntriesRequest : 日誌複製rpc
RequestVoteRequest : candidate發起的投票請求
InstallSnapshotRequest : 使用snapshot啟動node
TimeoutNowRequest ：領導者退位通知，接受者可以成為candidate了
先重點看下投票和日誌複製。
candidate投票RPCraft論文詳細定義了投票request/response所需要的欄位，定義了follower如何處理投票消息的流程：
再看下源碼的定義，發現只多了一個欄位（其中rpcheader是版本信息，先忽略）：
type RequestVoteRequest struct {
RPCHeader
// Provide the term and our id
Term uint64
Candidate []byte
// Used to ensure safety
LastLogIndex uint64
LastLogTerm uint64
// Used to indicate to peers if this vote was triggered by a leadership
// transfer. It is required for leadership transfer to work, because servers
// wouldn't vote otherwise if they are aware of an existing leader.
LeadershipTransfer bool
}
LeadershipTransfer, 這個欄位為true表示是leader主動退位。因為正常情況下（leader健在），follower是不會響應投票請求的。但有了這個欄位，是leader主動退位。就可以在leader健康的狀態下投票給其他candidate.
重點是保證最新、最全。最新通過logTerm來保證，term新的follower拒絕給舊term的candidate投票；最全通過logIndex來保證，日誌完整(logIndex大的)follower拒絕給，日誌不完整的投票。
// Ignore an older term
if req.Term < r.getCurrentTerm() {
return
}
...
if lastTerm == req.LastLogTerm && lastIdx > req.LastLogIndex {
r.logger.Warn("rejecting vote request since our last index is greater", "candidate", candidate, "last-index", lastIdx, "last-candidate-index", req.LastLogIndex)
return
}
每一輪（任期）投票中，每個節點只有一張票。這樣可以防止集群腦裂。