raft算法

算法動畫演示：

節點的三種角色：跟隨者（follower）、候選人（candidate）、領導者（leader）

最大容錯故障節點：（N - 1）/ 2

選舉超時（election timeout）：一個節點在成為候選節點（candidate）之前等待的時間，150ms到300ms之間的隨機值

心跳超時（heartbeat timeout）：心跳超時

pbft算法

最大容錯節點數：3f + 1 <= N

算法基本流程：

1.客戶端發送請求給主節點

2.主節點廣播請求給其他節點，節點執行pbft算法三階段共識流程

3.節點處理完三階段流程后，返回消息給客戶端

4.客戶端收到來自f + 1個節點的相同消息后，代表共識已經完成

pbft算法核心三階段流程：

v：視圖編號

d：客戶端消息摘要

m：消息內容

n：在[h，H]區間之間，請求編號

i：節點編號

進行主節點簽名，v，n，d>

1.Pre-prepare 階段：節點收到 pre-prepare 消息后，會有兩種選擇，一種是接受，一種是不接受。什么時候才不接受主節點發來的 pre-prepare 消息呢？一種典型的情況就是如果一個節點接受到了一條 pre-pre 消息，消息里的 v 和 n 在之前收到里的消息是曾經出現過的，但是 d 和 m 卻和之前的消息不一致，或者請求編號不在高低水位之間（高低水位的概念在下文會進行解釋），這時候就會拒絕請求。拒絕的邏輯就是主節點不會發送兩條具有相同的 v 和 n ，但 d 和 m 卻不同的消息。

2.Prepare 階段：節點同意請求后會向其它節點發送 prepare 消息。這里要注意一點，同一時刻不是只有一個節點在進行這個過程，可能有 n 個節點也在進行這個過程。因此節點是有可能收到其它節點發送的 prepare 消息的。在一定時間范圍內，如果收到超過 2f 個不同節點的 prepare 消息，就代表 prepare 階段已經完成。

3.Commit 階段：于是進入 commit 階段。向其它節點廣播 commit 消息，同理，這個過程可能是有 n 個節點也在進行的。因此可能會收到其它節點發過來的 commit 消息，當收到 2f+1 個 commit 消息后（包括自己），代表大多數節點已經進入 commit 階段，這一階段已經達成共識，于是節點就會執行請求，寫入數據。

審核編輯：湯梓紅