分散式一致性演算法:Raft演算法

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

 過去, Paxos一直是分散式協議的標準,但是Paxos難於理解,更難以實現,Google的分散式鎖系統Chubby作為Paxos實現曾經遭遇到很多坑。

  來自Stanford的新的分散式協議研究稱為Raft,它是一個為真實世界應用建立的協議,主要注重協議的落地性和可理解性。

  在瞭解Raft之前,我們先了解Consensus一致性這個概念,它是指多個伺服器在狀態達成一致,但是在一個分散式系統中,因為各種意外可能,有的伺服器可能會崩潰或變得不可靠,它就不能和其他伺服器達成一致狀態。這樣就需要一種Consensus協議,一致性協議是為了確保容錯性,也就是即使系統中有一兩個伺服器當機,也不會影響其處理過程。

  為了以容錯方式達成一致,我們不可能要求所有伺服器100%都達成一致狀態,只要超過半數的大多數伺服器達成一致就可以了,假設有N臺伺服器,N/2 1 就超過半數,代表大多數了。

  Paxos和Raft都是為了實現Consensus一致性這個目標,這個過程如同選舉一樣,參選者需要說服大多數選民(伺服器)投票給他,一旦選定後就跟隨其操作。Paxos和Raft的區別在於選舉的具體過程不同。

  在Raft中,任何時候一個伺服器可以扮演下面角色之一:

  1. Leader: 處理所有客戶端互動,日誌複製等,一般一次只有一個Leader.
  2. Follower: 類似選民,完全被動
  3. Candidate候選人: 類似Proposer律師,可以被選為一個新的領導人。

Raft階段分為兩個,首先是選舉過程,然後在選舉出來的領導人帶領進行正常操作,比如日誌複製等。下面用圖示展示這個過程:

1. 任何一個伺服器都可以成為一個候選者Candidate,它向其他伺服器Follower發出要求選舉自己的請求:

2. 其他伺服器同意了,發出OK。

注意如果在這個過程中,有一個Follower當機,沒有收到請求選舉的要求,因此候選者可以自己選自己,只要達到N/2 1 的大多數票,候選人還是可以成為Leader的。

3. 這樣這個候選者就成為了Leader領導人,它可以向選民也就是Follower們發出指令,比如進行日誌複製。

4. 以後通過心跳進行日誌複製的通知

5. 如果一旦這個Leader當機崩潰了,那麼Follower中有一個成為候選者,發出邀票選舉。

6. Follower同意後,其成為Leader,繼續承擔日誌複製等指導工作:

 

值得注意的是,整個選舉過程是有一個時間限制的,如下圖:

  Splite Vote是因為如果同時有兩個候選人向大家邀票,這時通過類似加時賽來解決,兩個候選者在一段timeout比如300ms互相不服氣的等待以後,因為雙方得到的票數是一樣的,一半對一半,那麼在300ms以後,再由這兩個候選者發出邀票,這時同時的概率大大降低,那麼首先發出邀票的的候選者得到了大多數同意,成為領導者Leader,而另外一個候選者後來發出邀票時,那些Follower選民已經投票給第一個候選者,不能再投票給它,它就成為落選者了,最後這個落選者也成為普通Follower一員了。

 

日誌複製

  下面以日誌複製為例子說明Raft演算法,假設Leader領導人已經選出,這時客戶端發出增加一個日誌的要求,比如日誌是”sally”:

2. Leader要求Followe遵從他的指令,都將這個新的日誌內容追加到他們各自日誌中:

3.大多數follower伺服器將日誌寫入磁碟檔案後,確認追加成功,發出Commited Ok:

4. 在下一個心跳heartbeat中,Leader會通知所有Follwer更新commited 專案。

對於每個新的日誌記錄,重複上述過程。

如果在這一過程中,發生了網路分割槽或者網路通訊故障,使得Leader不能訪問大多數Follwers了,那麼Leader只能正常更新它能訪問的那些Follower伺服器,而大多數的伺服器Follower因為沒有了Leader,他們重新選舉一個候選者作為Leader,然後這個Leader作為代表於外界打交道,如果外界要求其新增新的日誌,這個新的Leader就按上述步驟通知大多數Followers,如果這時網路故障修復了,那麼原先的Leader就變成Follower,在失聯階段這個老Leader的任何更新都不能算commit,都回滾,接受新的Leader的新的更新。

總結:目前幾乎所有語言都已經有支援Raft演算法的庫包,具體可參考:raftconsensus.github.io

英文動畫演示Raft

CAP定理

分散式Paxos演算法

ZooKeeper在服務發現中應用

相關文章

程式語言 最新文章