共識算法入門

aft算法

算法動畫示範：​​thesecretlivesofdata.com/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：節點編号

<PRE-PREPARE，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 階段，這一階段已經達成共識，于是節點就會執行請求，寫入資料。