分布式共識系列文章：

《解決分布式一致性問題，不得不了解的Paxos算法》
《基本Paxos協議是如何實現分布式數據一致性的？》
《可用于實際應用場景中的Multi Paxos實用算法》

前面幾篇文章介紹了Paxos算法，一直是分布式協議的標準，但Paxos算法難于理解，更難以實現。即使google的分布式鎖系統Chubby以Paxos算法實現，也遇到了很多坑。為了簡化分布一致性算法，斯坦福大學提出了一種Raft算法。

Raft 算法在2013年發表，就是建立在希望得到一個更易于理解的 Paxos 算法的替代品。論文題目《In Search of an Understandable Consensus Algorithm》就可以看出來，可理解性是Raft算法的主要目標之一。到現在已經有了十多種語言的Raft算法的實現框架，最為出名的就是Etcd。

Etcd是CoreOS團隊于2013年6月發起的開源項目，它的目標是構建一個高可用的分布式鍵值(key-value)數據庫。

Leader選舉（Leader Election）

在一個由 Raft 協議組織的集群中有三類角色：Leader（領袖）、Follower（群眾）、Candidate（候選人）。

Raft三類角色的狀態轉換

Leader：處理所有客戶端交互，日志復制等。集群一般只能有一個領導，領導在位期間就是一個任期（Term）。Leader定期向Follower發送心跳，宣示自己的存在。
Follower：如果Follower在election timeout內沒有收到來自Leader的心跳，那么會認為Leader掛掉了。Follower會更新自己的當前任期（Current Term）并成為Candidate，并開始選舉新的Leader。
Candidate：候選人，有可能被選為一個新的領導人。如果收到了多數的投票就當選為Leader。如果超過一定時間沒有收到選票，就重新發起選舉。

一個最小的 Raft集群需要三個參與者，這樣才可能投出多數票。如下圖所示，初始狀態下 ABC三個節點開始選舉Leader。

Raft協議Leader選舉

Leader選舉過程中有三種可能的情形發生：

A節點要投自己一票，并把提議（拉票請求）發給B和C，B和C接受了A的提議，也投票給A。A成為Leader。
A節點投了自己一票，B節點也投了自己一票，C節點支持A節點的提議，少數服從多數。A成為Leader。
A節點、B節點、C節點都各自投了自己一票。沒有節點獲得多數票。

以上前二種情況都能選出 Leader，第三種情況本輪投票無效，出現了平票（Split Votes）。因為沒有任何一方獲得多數票，所以要發起新的一輪投票。

Raft協議為了不讓選舉機制反復出現平票，定義了一個隨機超時機制（randomized election timeouts）。一旦發生平票，平票的節點會各自再來一次隨機timeout倒數，然后重新拉票。先發起拉票的節點就可以優先獲得了多數節點的投票。

數據同步（Log Replication）

Raft 協議強依賴 Leader 節點的可用性來確保集群數據的一致性。數據的流向只能從 Leader節點向 Follower 節點轉移。

當 Client 向集群 Leader 節點提交數據（v=3）后，Leader 節點接收到的數據處于未提交狀態（Uncommitted）。
接著 Leader 節點會并發向所有的 Follower 節點復制數據并等待接收響應。
Leader節點確保至少集群中超過半數節點確認接收到數據。
Leader向 Client 發送Ack確認數據已接收，表明此時數據狀態進入已提交（Committed）狀態。Leader 節點向Follower 節點發通知告知該數據狀態（v=3）已提交。

數據從Leader向Follower轉移過程

Leader掛掉對一致性的影響

接下來我們看一下，如果在數據轉移過程中，Leader掛掉，對數據一致性會造成什么影響。

1. 在數據到達 Leader 節點前，這個階段 Leader 掛掉。顯然不影響一致性。

數據到達Leader前，Leader掛掉

2. 當數據到達 Leader 節點，但未復制給 Follower 節點。這個階段 Leader 掛掉，數據屬于未提交狀態。Client 沒有收到 Ack確認會認為超時失敗，于是發起重試。

Follower 節點重新選主，新的Leader上沒有該數據。Client 重新提交數據到新Leader可以成功。原來的 Leader 節點恢復后作為 Follower 加入集群，從當前任期的新 Leader 同步數據，保持和 Leader 數據一致。

數據到達Leader，處于未提交狀態

3 當數據到達 Leader 節點，并成功復制給所有Follower節點，但Follower節點尚未向 Leader 響應接收。此時 Leader 掛掉。

雖然數據在 Follower 節點處于未提交狀態（Uncommitted），但已經保持一致。重新選出 Leader 后可完成數據提交。此時 Client 由于不知到底提交成功沒有，會重試提交。針對這種情況 Raft 要求 RPC 請求實現冪等性，也就是要實現內部去重機制。

當數據到達 Leader 節點，并成功復制給所有Follower節點，但尚未提交

4. 數據到達 Leader 節點，并成功復制給 Follower 部分節點，但還未向 Leader 響應接收。在這個階段 Leader 掛掉，數據在 Follower 節點處于未提交狀態（Uncommitted）且數據不一致。

Raft 協議要求投票只能投給擁有最新數據的節點。這樣擁有最新數據的節點會被選為 Leader，再同步數據到 Follower，數據不會丟失并實現最終一致。

5 數據到達 Leader 節點，并成功復制給 Follower 所有或多數節點，數據在 Leader 處于已提交狀態，但在 Follower 處于未提交狀態。這個階段 Leader 掛掉，重新選出新 Leader 后的處理流程和上面第3種情況一樣。

數據在Leader 節點處于已提交，在Follower處于未提交狀態

6 數據到達 Leader 節點，成功復制到 Follower 所有或多數節點，數據在所有節點都處于已提交狀態，但由于某種原因，Client未收到Ack響應。這個階段 Leader 掛掉，集群內部數據其實已經是一致的，Client 重新提交數據，基于冪等策略對一致性無影響。

集群內數據已達成一致

從上面的討論可知，在Leader向Follower進行數據同步的不同階段，Leader掛掉也不會影響數據的最終一致性。那么如果由于網絡分區，導致雙Leader出現，即所謂腦裂的情況，那么對數據一致性會有影響嗎？

腦裂的情況

所謂腦裂，就是集群中出現了雙 Leader，這種情況通常是由于網絡分區導致。一山不容二虎，一個集群也不能有二主。我們來看一下這種情況下，Raft協議如何將集群恢復到正常。

網絡分區將原先的 Leader 節點和 Follower 節點分隔開，由于Follower 收不到 Leader 的心跳將發起選舉產生新的 Leader。
這時就產生了雙 Leader，原先的 Leader 獨自在一個區，向它提交數據不可能復制到多數節點，所以永遠提交不成功。
向新的 Leader 提交數據可以提交成功，網絡恢復后舊的Leader 發現集群中有了新 Leader，于是自己主動降級為 Follower，并從新 Leader 那里同步數據，最終達成集群數據一致。