深入淺出RAFT共識算法

雲栖号資訊：【 點選檢視更多行業資訊

】

在這裡您可以找到不同行業的第一手的上雲資訊，還在等什麼，快來！

分布式一緻性問題

如果說，伺服器隻有一個節點，那麼，要保證一緻性，沒有任何問題，因為所有讀寫都在一個節點上發生。那如果server端有2個、3個甚至更多節點，要怎麼達成一緻性呢？下面就來介紹其中一種分布式共識算法—raft算法。

Raft是什麼

1.曆史背景

在講Raft前，有必要提一下Paxos算法，Paxos算法是Leslie Lamport于1990年提出的基于消息傳遞的一緻性算法。然而，由于算法難以了解，剛開始并沒有得到很多人的重視。其後，作者在八年後，也就是1998年在ACM上正式發表，然而由于算法難以了解還是沒有得到重視。而作者之後用更容易接受的方法重新發表了一篇論文《Paxos Made Simple》。

可見，Paxos算法是有多難了解，即便現在放到很多高校，依然很多學生、教授都回報Paxos算法難以了解。同時，Paxos算法在實際應用實作的時候也是比較困難的。這也是為什麼會有後來Raft算法的提出。

2.概念

Raft是實作分布式共識的一種算法，主要用來管理日志複制的一緻性。它和Paxos的功能是一樣，但是相比于Paxos，Raft算法更容易了解、也更容易應用到實際的系統當中。而Raft算法也是聯盟鍊采用比較多的共識算法。

備注：區塊鍊分為：公有鍊、聯盟鍊和私有鍊

Raft的三種狀态（角色）

• Follower（群衆） 被動接收Leader發送的請求。所有的節點剛開始的時候是處于Follower狀态。
• Candidate（候選人） 由Follower向Leader轉換的中間狀态。
• Leader（上司） 負責和用戶端互動以及日志複制（日志複制是單向的，即Leader發送給Follower），同一時刻最多隻有1個Leader存在。

三種狀态的轉換關系如下，下一節的Raft工作機制會具體講到。

幾個關鍵概念

1、複制狀态機

我們知道，在一個分布式系統資料庫中，如果每個節點的狀态一緻，每個節點都執行相同的指令序列，那麼最終他們會得到一個一緻的狀态。也就是和說，為了保證整個分布式系統的一緻性，我們需要保證每個節點執行相同的指令序列，也就是說每個節點的日志要保持一樣。是以說，保證日志複制一緻就是Raft等一緻性算法的工作了。

• 複制狀态機架構

這裡就涉及Replicated State Machine（複制狀态機），如上圖所示。在一個節點上，一緻性子產品（Consensus Module，也就是分布式共識算法）接收到了來自用戶端的指令。然後把接收到的指令寫入到日志中，該節點和其他節點通過一緻性子產品進行通信確定每個日志最終包含相同的指令序列。一旦這些日志的指令被正确複制，每個節點的狀态機（State Machine）都會按照相同的序列去執行他們，進而最終得到一緻的狀态。然後将達成共識的結果傳回給用戶端，如下圖所示。

2、任期（Term）概念

在分布式系統中，“時間同步”是一個很大的難題，因為每個機器可能由于所處的地理位置、機器環境等因素會不同程度造成時鐘不一緻，但是為了識别“過期資訊”，時間資訊必不可少。

Raft算法中就采用任期（Term）的概念，将時間切分為一個個的Term（同時每個節點自身也會本地維護currentTerm），可以認為是邏輯上的時間，如下圖。

每一任期的開始都是一次上司人選舉，一個或多個候選人（Candidate）會嘗試成為上司（Leader）。如果一個人赢得選舉，就會在該任期（Term）内剩餘的時間擔任上司人。在某些情況下，選票可能會被評分，有可能沒有選出上司人（如t3），那麼，将會開始另一任期，并且理科開始下一次選舉。Raft 算法保證在給定的一個任期最少要有一個上司人。

**3、心跳（heartbeats）和逾時機制（timeout）

**

在Raft算法中，有兩個timeout機制來控制上司人選舉：

一個是選舉定時器（eletion timeout）：即Follower等待成為Candidate狀态的等待時間，這個時間被随機設定為150ms~300ms之間

另一個是headrbeat timeout：在某個節點成為Leader以後，它會發送Append Entries消息給其他節點，這些消息就是通過heartbeat timeout來傳送，Follower接收到Leader的心跳包的同時也重置選舉定時器。

Raft的工作機制

Raft算法可以分為如下3個部分：

1、上司人選舉（Leader Election）

（1）一開始，所有節點都是以Follower角色啟動，同時啟動選舉定時器（時間随機，降低沖突機率）

（2）如果一個節點發現在超過選舉定時器的時間以後一直沒有收到Leader發送的心跳請求，則該節點就會成為候選人，并且一直處于該狀态，直到下列三種情況之一發生：

該節點（Candidate）赢得選舉

其他節點赢得選舉 一段時間後沒有任何一台伺服器赢得選舉（進入下一輪Term的選舉，并随機設定選舉定時器時間）

（3）然後這個候選人就會向其他節點發送投票請求（Request Vote），如果得到半數以上節點的同意，就成為Leader（Leader）。如果選舉逾時，還沒有Leader選出，則進入下一任期，重新選舉。

（4）完成Leader選舉後，Leader就會定時給其他節點發送心跳包（Heartbeat），告訴其他節點Leader還在運作，同時重置這些節點的選舉定時器。

2、日志複制（Log Replication）

（1）Client向Leader送出指令（如：SET 5），Leader收到指令後，将指令追加到本地日志中。此時，這個指令處于“uncomitted”狀态，複制狀态機不會執行該指令。

（2）然後，Leader将指令（SET 5）并發複制給其他節點，并等待其他其他節點将指令寫入到日志中，如果此時有些節點失敗或者比較慢，Leader節點會一直重試，知道所有節點都儲存了指令到日志中。之後Leader節點就送出指令（即被狀态機執行指令，這裡是：SET 5），并将結果傳回給Client節點。

（3）Leader節點在送出指令後，下一次的心跳包中就帶有通知其他節點送出指令的消息，其他節點收到Leader的消息後，就将指令應用到狀态機中（State Machine），最終每個節點的日志都保持了一緻性。

Leader節點會記錄已經交的最大日志index，之後後續的heartbeat和日志複制請求（Append Entries）都會帶上這個值，這樣其他節點就知道哪些指令已經送出了，就可以讓狀态機（State Machine）執行日志中的指令，使得所有節點的狀态機資料都保持一緻。

下面我們來看下日志内容不一緻的情況下，Raft算法如何處理？

如果在一個分布式網絡中，各個節點的日志狀态如下。當Leader節點發送日志複制請求的時，它會帶上上一次的日志記錄的index和term。

此時Leader節點發送日志複制請求。此時，A節點收到Leader的請求後，對比Leader節點記錄的上一個日志記錄的index和term，發現：

index（leader）> index（A） term（leader）> currentTerm（A） 發現自己的日志中不存在這個指令，于是拒絕這個請求。此時，Leader節點知道發生了不一緻，于是遞減nextIndex，并重新給A節點發送日志複制請求，直到找到日志一緻的地方為止。然後把Follower節點的日志覆寫為Leader節點的日志内容。

也就是說，Raft算法對于日志内容不一緻的請求，會采取Leader節點的日志内容覆寫Follower節點的日志内容的做法，先找到兩者日志記錄第一次不一緻的地方，然後一直覆寫到最新送出的指令位置。

3、安全性

之前的内容讨論了 Raft 算法是如何進行上司選取和複制日志的。然而，到目前為止這個機制還不能保證每一個狀态機能按照相同的順序執行同樣的指令。例如，當上司人送出了若幹日志條目的同時一個追随者可能當機了，之後它又被選為了上司人然後用新的日志條目覆寫掉了舊的那些，最後，不同的狀态機可能執行不同的指令序列。

而Raft算法通過在上司人選舉階段增加一個限制來完善了Raft算法。這個限制能保證，對于固定任期，任何上司人都擁有之前任期送出的全部日志指令。Raft算法通過投票的方式來阻止那些沒有包含全部日志指令的節點赢得選舉。

一個Candidate節點要成為赢得選舉，就需要跟網絡中大部分節點進行通信，這就意味着每一條已經送出的日志條目最少在其中一台伺服器上出現。如果候選人的日志至少和大多數伺服器上的日志一樣新，那麼它一定包含有全部的已經送出的日志條目。RequestVote RPC 實作了這個限制：這個 RPC包括候選人的日志資訊，如果它自己的日志比候選人的日志要新，那麼它會拒絕候選人的投票請求。

那麼，怎麼判斷兩個節點日志内容比較新呢？其标準如下，Raft算法通過比較日志中最後一個指令的索引（index）和任期号（term）來判定哪一個日志内容比較新。

如果兩個日志的任期号不同，任期号大的日志内容更新；如果任期号相同，日志長的日志内容更新。

下面我們來考慮一個比較極端的情況，出現網絡分區的時候，Raft如何保持一緻性。

我們将分布式網絡分割為兩個子網，分别是子網絡AB和子網絡CDE，此時節點B是Leader節點。

然而由于網絡分區導緻子網1不存在Leader節點，此時，C、D和E節點由于沒有收到Leader節點的心跳，導緻選舉定時器逾時進而進入Candidate狀态，開始進行上司人選舉。

這時，我們假設C節點赢得選舉，成為子網1的Leader節點。

此時，如果兩個子網有Client節點分别向各個子網的Leader節點送出資料（如：X←3），由于子網2中Leader節點B不可能複制到大部分節點，是以其X←3指令會一直處于“uncomitted”狀态。而子網1由于成功複制給大部分節點，是以X←3最終在子網1達成共識，如下圖所示。

我們假設，子網1經過多次選舉和資料互動，最終子網1的日志狀态如下圖所示：

而此時，分區隔離狀态消失。Leader C和Leader B分别會發送心跳請求，最終Leader B發現Leader C選票比自己更多，進而轉換為Follower狀态。而通過日志複制（Log Replication），最終所有節點日志達成一直，

【雲栖号線上課堂】每天都有産品技術專家分享！

課程位址：

https://yqh.aliyun.com/zhibo

立即加入社群，與專家面對面，及時了解課程最新動态！

【雲栖号線上課堂 社群】

https://c.tb.cn/F3.Z8gvnK

原文釋出時間：2020-04-13

本文作者：cocoachina

本文來自：“cocoachina”，了解相關資訊可以關注“cocoachina”