分散式一致性協議之Raft
- 2020 年 3 月 11 日
- 筆記
Raft-很容易理解的分散式一致性演算法
單節點場景
你可以想像下我們的一個節點作為一個保存單一值的資料庫服務，我們有一個client可以向server發送一個值。client與server的關係如下圖：
如果client向server發送一個值為8，那麼它們的關係將變成下圖：
可以看到只有一個節點的時候就很容易達到協議共識。
多節點
有了上面的示例，我們不禁要問，當我們擁有多個節點時怎麼來達成節點間的共識呢？
客戶端的值8該怎麼在節點a、b、c之間達成一致呢，這就是分散式共識的問題。
Raft
Raft就是分散式共識協議的一種實現。我們來看一看它是如何工作的。
首先，節點有三種狀態：
- Follower(跟隨節點)
- Candidate(候選節點)
- Leader(領導節點)
下文中的Term代表的是任期
所有的節點在最開始的時候都是follower狀態：
如果followers沒有接收到leader的心跳請求（這裡有一個超時時間，超過這個時間就認為沒有接收到）然後它們就會變成candidate節點，如下圖中的a節點：
然後candidate節點（圖中a節點）開始請求其他節點投票。節點b和c將會回復給出他們的投票。
如果這時候candidate節點得到了大多數節點的投票，它就會成為leader節點。這個過程就被稱為選主。所有的系統變化都需要經過leader節點。
每個更改都作為一個條目添加到節點的日誌中。此日誌項當前未提交，因此不會更新節點的值。
要提交條目，節點首先需要將其複製到Follower節點中。
然後領導者等待，直到大多數節點都寫了該條目。
現在，該條目已提交到Leader節點上，並且節點狀態為「 5」。
然後Leader通知Follower該條目已提交。
現在，集群已就系統狀態達成共識。此過程稱為日誌複製。
選舉
在Raft中，有兩個超時設置可控制選舉。
首先是選舉超時。選舉超時是指追隨者成為候選人之前所等待的時間。選舉超時被隨機分配在150毫秒至300毫秒之間。選舉超時後，關注者成為候選人並開始新的選舉任期：
圖中Node C超時後為自己投票，並向其他節點發送請求投票消息。
如果接收節點在這個選舉周期內還沒有投票，那麼它將投票給候選人：
在投票的同時會對節點重置其選舉超時。
一旦候選人獲得多數票，便成為Leader：
Leader開始向其Follower發送「 添加條目」消息。
這些消息以心跳超時指定的時間間隔發送。Follower然後響應每個追加條目消息。
此選舉任期將持續到Follower停止接收心跳並成為候選人為止：
讓我們停止Leader，觀察選舉連任:
假設圖中節點B先達到選舉超時率先變成Candidate節點，它將成為任期2的負責人：
節點B向節點A和節點C請求投票，但是只有節點A返回了投票響應：
成為Leader的另一個條件是要獲得多數票，這樣可以確保每個任期只能選出一位Leader。如果兩個節點同時成為候選節點，則可能會發生拆分表決。
讓我們看一個分割投票的例子：
如果節點A和節點C都開始以相同的任期進行選舉:
每個都先到達一個Follower節點：
現在，每位候選人都有2票，並且在這個任期中將無法獲得更多選票：
這時Node節點將會等待一個新的超時時間重新進行投票：
節點C在第5屆中獲得了多數選票，因此成為領導者:
日誌複製
當選出一位Leader後，我們需要將系統的所有更改複製到所有節點：
通過使用與心跳相同的「 添加條目」消息來完成此操作。讓我們逐步完成該過程。
首先，客戶將更改發送給Leader：
更改將添加到Leader的日誌中:
然後將更改在下一個心跳發送給Follower，一旦大多數Follower認可，便提交該條目：
然後將響應發送給客戶端：
現在，讓我們發送一條命令，將值增加「2」：
我們的系統值現在更新為「7」：
網路分區
Raft甚至可以在面對網路分區時保持一致：
對上圖中一個集群，讓我們添加一個分區以將A&B與C,D&E分開：
由於我們的分區，我們現在有兩位Leader。讓我們添加另一個客戶端，並嘗試更新兩個領導者。
一個客戶端將嘗試將節點B的值設置為「 3」
節點B無法複製為多數，因此其日誌條目保持未提交狀態。
另一個客戶端將嘗試將節點E的值設置為「 8」
這將成功，因為它可以複製到大多數
現在讓我們修復網路分區
節點B將看到較高的選舉任期並退出Leader角色。節點A和B都將回滾其未提交的條目並匹配新領導者的日誌。
現在，我們的日誌在整個集群中是一致的。
參考
文章譯自：http://thesecretlivesofdata.com/raft/
另外，網路上有一張比較經典的圖片描述本文的：
圖片來自：https://www.codedump.info/post/20180921-raft/
