raft算法

算法動(dòng)畫演示：

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

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

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

心跳超時(shí)（heartbeat timeout）：心跳超時(shí)

pbft算法

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

算法基本流程：

1.客戶端發(fā)送請(qǐng)求給主節(jié)點(diǎn)

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

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

4.客戶端收到來(lái)自f + 1個(gè)節(jié)點(diǎn)的相同消息后，代表共識(shí)已經(jīng)完成

pbft算法核心三階段流程：

v：視圖編號(hào)

d：客戶端消息摘要

m：消息內(nèi)容

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

i：節(jié)點(diǎn)編號(hào)

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

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

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

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

審核編輯：湯梓紅