標籤：

Raft協議

02-05

Raft是一種分散式集群一致性的協議，源於Paxos協議，但是Paxos很難理解，所以有了Raft協議。Raft利用只有唯一leader簡化了問題，這也是與Paxos peer-to-peer最大的不同點。

主要特點：

  • 強且唯一的leader：log只從leader到follower。follower一段時間沒收到leader的心跳就認為leader掛了，開始變成candidate。
  • 隨機timeout選舉：避免持續平票的局面。
  • 成員變更：添加一台機器通過請求變更配置。
  • log entry的強一致性：leader有最多的log entry，且保證committed的index，所有server一致。沒有數據的空隙。
  • 心跳時間<<選舉timeout時間<<宕機恢復時間：確保不會心跳內時間有很多新的選舉。

解決什麼問題？

如果數據存在一台機器裡面，機器掛了怎麼辦？重啟的這段時間，服務不可用，損失了avaiability。如果用三台機器，其中一台掛了，可以用另外一台。多台伺服器之間引申出來另外一個問題：如何確保這三台伺服器的數據是一致的，即consistency。

Raft如何解決？

選舉一台機器當領導(leader)，只有leader機器和客戶打交道。如果請求發送到了其它機器，則轉發至leader機器。

數據只能從leader向其他機器寫，其他機器只是被動接受。

如何選舉leader (leader election)？

最開始所有機器都是follower狀態，給每個follower一個隨機的過期時間，通常是10ms到500ms。follower過期後變成candidate狀態；candidate會向其他人拉票。這時候會出現三種情況：

1.競選成功，獲得了超過一半的票數，當選為leader。

2.競選失敗，退回來變成follower。

3.平局，重新競選。

領導如何同步數據給follower (log replication)？

集群中超過半數的follower確認數據同步成功後，才通知客戶成功了。

leader掛了怎麼辦 (safety)？

leader通過定期向follower發送心跳，通常是0.5ms到20ms，來確定自己的統治。如果follower一段時間沒有收到leader的心跳，就認為leader掛了，重新選舉。

這時候有些follower的數據未完成同步。在拉選票的時候，如果候選人的數據沒有投票者數據新，會被拒絕。以此確認新的leader擁有最全的數據。

leader無法通信怎麼辦？

類似於掛了。新的leader開始新的統治後，會增加任期。老的leader恢復後，看到自己任期較小，重新變成follower的狀態。

所以有了下面的圖：

圖片來自百度，如果侵權，我馬上刪除。

成員變更：

簡單說，等新的機器數據同步完後，給系統發送新的配置，包括所有機器的ip地址等，打包成請求給集群；如果得到大多數的committed，就表示變更成功了。

cs.brown.edu/research/p

「Every node in the raft cluster keeps track of the current configuration, namely, the addresses of other nodes in the cluster, as well as the total number of nodes. When the leader receives a request to either add or remove a node, it will switch the cluster to a state known as joint consensus. During joint consensus, the leader must hear back from a majority of nodes in the current configuration, as well as a majority of nodes in the new configuration before it can apply any changes to the state machine. It is also during this time that the leader alerts the rest of the nodes in the cluster that the

number of nodes in the cluster will be changing. Once a majority of the nodes in the old and new configuration tell the leader they are ready to switch to the new one, the leader will send out a message to the nodes that it is now operating under the new configuration, and conclude the transition.「

術語：

term：任期，表示一個leader從開始競選到結束統治的時間。

safety：never returning an incorrect result. 如果某機器的數據已經確認了，就不能被更改。

assumption：

心跳時間 << 競選時間 << 機器宕機恢復時間

reference:

In Search of an Understandable Consensus Algorithm by Diego Ongaro and John Ousterhout (all credits to them)


推薦閱讀：

※Indexed Shared Log

TAG:Raft |