raft算法

算法動畫演示：

節(jié)點的三種角色：跟隨者（follower）、候選人（candidate）、領(lǐng)導(dǎo)者（leader）

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

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

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

pbft算法

最大容錯節(jié)點數(shù)：3f + 1 <= N

算法基本流程：

1.客戶端發(fā)送請求給主節(jié)點

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

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

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

pbft算法核心三階段流程：

v：視圖編號

d：客戶端消息摘要

m：消息內(nèi)容

n：在[h，H]區(qū)間之間，請求編號

i：節(jié)點編號

進(jìn)行主節(jié)點簽名，v，n，d>

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

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

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

審核編輯：湯梓紅