摘要
Raft 分佈式一致性算法在 2013 年發佈，以容易理解、實現方式明確的特點，迅速在業界流行起來。本次分享將介紹 TiDB 如何使用 Raft 算法構建分佈式可擴展的後端存儲系統，以及 TiDB 在可靠性、可用性、性能等方面對 Raft 做的工程優化。
Why Ralf
假設我們有某一個業務要實現數據存儲方面的功能，最簡單方法就是實現一個節點，所有的數據讀寫都是通過這一個節點。但是這樣會存在各種各樣的問題，比如數據量增大後無法承受壓力，單節點如何向多節點分佈，數據的一致性怎麼保證，最嚴重的就是數據節點掛掉，數據全部丟失了。
Replication
為了解決節點損壞的問題，業界通用的方案是採用Replication，在Master寫數據的時候掛多個Slave，寫完後保證將log同步到Slave，這樣的流程下來才能認為寫入是成功的。
通常情況下為了保證性能，我們都會使用異步複製（Async Replication），不過會產生一些問題。當Master掛掉了之後很有可能有些數據並沒有同步到Slave，這時候如果把這個Slave提升到新的Master就會面臨數據丟失的問題。
強同步（Sync Replication）解決了異步複製（Async Replication）可能潛在的問題。Master寫入數據後必須保證Slave接收到log寫入才算成功，當然這樣會損耗一些性能，不過最嚴重在於Master掛掉後，Slave提升為Master，單節點的問題就又出現了。
為了保證系統中N臺節點掛掉後，仍然能夠對外提供服務，至少需要2N+1臺機器，也就是傳統的Quorum，這樣最少就需要三臺機器，但是數量的增大也會帶來更多的問題。
首先Master掛掉後要需要判斷該提升哪個Slave為新的Master。另外在多態集群下還容易遇到一個問題，就是在網絡情況下以前的Master出現網絡隔離，還在繼續對外提供服務，而這時新的集群和Master已經形成了，新的數據被寫入到新的Master，可是讀取的卻是舊的數據，這就是在分佈式一致性領域所面臨的線性一致性問題。
Consensus Algorithm
一致性算法（Consensus Alogrithm）就是為了解決分佈式集群所面臨的諸多問題而準備的。它保證了系統在多個狀態上的Agreement，另外在集群的大部分節點掛掉後能夠保證數據一致性。
Raft
Replicated State Machine
大多數的一致性算法其實都是採用了Replicated State Machine的模型。對於這個模型你可以認為數據是被放在狀態機上，用戶操作集群時 首先需要寫入log，然後通過一致性算法將log複製到其他機器，一旦確定其他機器都接收到log後就會認為該log被提交了，最後其他節點會依次將log存放到狀態機。
State
Raft有著三個狀態，第一個狀態就是Leader,即使Raft Group存在多個節點，Leader也只會存在一個，也只有Leader能負責所有數據的讀寫，這樣就不會出現線性一致性的問題。
當一個集群選出了Leader後其他集群的節點都會變成Follow，這個Follow只負責一件事就是接收Leader的Replication logs。當一個Follow沒有接收到數據或者發現集群中沒有Leader的時候，就會進入Candidate狀態，這個狀態表示可以開始選舉了。
Term
Raft是不依賴系統的時間，它是將時間分成一個個Term，每個Term可以是任意長度，每次Term開始的時候都是由一次新的選舉產生的，然後在這個Term內選出一個Leader，該Leader會一直服務到所在Leader結束。
結合Raft Term就可以進行Raft的選舉。首先當系統啟動後所有的節點都會進入Follow狀態，Follow沒有接收到任何請求的話，過一段時間就會進入Candidate狀態，然後詢問其他節點是否投票，如果其他節點反饋已經有新的Leader，這個Candidate就會變成Follow，而當Candidate接收到大多數的投票後就會變成Leader，之後會立即將一個log發送給其他節點開始續租Leader的時間租約。
Log Replication
一個新的Leader被選出來之後就會開始工作了，它會不停的去接收客戶端發送過來的請求，這些請求都會通過log落地，而這些log一定要是單調遞增，以保證數據的一致性。
之後log會被複制到其他的節點，絕大多數節點都接收到這個log後， Leader就認為該log是committed的。
Membership Change
對於分佈式集群來說添加節點其實是分成困難的操作，最常見的做法是先更改配置中心，然後將新的配置同步到舊的節點。不過這樣在同步配置的時候，就需要停止外部服務。而Raft採用了一種動態的成員節點變更，它會將新的節點到當作Raft log通過Leader傳遞給其他節點，這樣其他節點就知道了這個新的節點的信息。不過這個過程中有可能會在某一階段出現2個Leader的情況，為了避免這種情況就要每次只變更一個節點，而不進行多節點變更。
Raft也提供了一種多節點變更的算法，它是一種兩階段提交，Leader在第一階段會同時將新舊集群的配置同時當成一個Raft log發送給其他舊集群節點，當這些節點接收到數據後就會和新的集群節點進入join狀態，所有的操作都要進過新舊集群的大多數節點同意才會執行，然後在新的join狀態內重新提交新的配置信息，在配置被committed後新的節點會上線，舊的節點會下線。
Optimization
Pre-Vote
在Follow處於網絡抖動無法接受到Leader的消息的時候，它就會變成Candidate並且Term加一，但是其他集群其實還是在正常工作的，這樣整個集群的就混亂了。
Pre-Vote機制會在Follow沒有接收到Leader的消息並且開始投票之前進入Pre-Candidate狀態，在想其他節點發送投票請求，並獲得同意後才會進入Candidate狀態。
Pipeline
正常的Raft流程中，客戶端事先給Leader寫入數據，Leader處理後會追加到log中，追加成功後Replication到其他節點中，當Leader發現log被整個集群大多數節點接收後就會進行Apply。
這樣的一個過程其實是非常低效的，所以就需要引入Pipeline，它可以將多個請求進行併發處理，有效提高效率。
Batch
通常情況下接收到的客戶端請求都是依次過來的，而當有一批請求過來的時候，就可以通過Batch將這些請求打包成一個Raft log發送出去。
Multi-Raft
當目前的Raft Group無法支撐所有的數據的時候，就需要引入Multi-Raft處理數據，第一種做法是將數據切分成多個Raft Group分擔到不同的機器上。
為了應對更復雜的情況就需要使用動態分裂的方法，假設最開始的只有3臺機器以及一個Region，這個Region就佈置在一臺機器上，所有的數據都寫入這臺機器，當數據量達到某個預值後Region就產生分裂，得到的新的Region就可以移植到新的機器上
閱讀更多 Java高級架構師 的文章
