對數(shù)據(jù)順序達成一致共識是很多共識算法要解決的本質(zhì)問題
Fabic的pbft算法實現(xiàn)
現(xiàn)階段的共識算法主要可以分成三大類：公鏈，聯(lián)盟鏈和私鏈
私鏈揍移，所有節(jié)點可信
聯(lián)盟鏈次和，存在對等的不信任節(jié)點
私鏈：私鏈的共識算法即區(qū)塊鏈這個概念還沒普及時的傳統(tǒng)分布式系統(tǒng)里的共識算法，比如 zookeeper 的 zab 協(xié)議那伐，就是類 paxos 算法的一種踏施。私鏈的適用環(huán)境一般是不考慮集群中存在作惡節(jié)點，只考慮因為系統(tǒng)或者網(wǎng)絡(luò)原因?qū)е碌墓收瞎?jié)點罕邀。

聯(lián)盟鏈：聯(lián)盟鏈中畅形，經(jīng)典的代表項目是 Hyperledger 組織下的 Fabric 項目， Fabric0.6 版本使用的就是 pbft 算法诉探。聯(lián)盟鏈的適用環(huán)境除了需要考慮集群中存在故障節(jié)點日熬，還需要考慮集群中存在作惡節(jié)點。對于聯(lián)盟鏈肾胯，每個新加入的節(jié)點都是需要驗證和審核的竖席。

公鏈：公鏈不僅需要考慮網(wǎng)絡(luò)中存在故障節(jié)點，還需要考慮作惡節(jié)點敬肚，這一點和聯(lián)盟鏈?zhǔn)穷愃频谋霞觥：吐?lián)盟鏈最大的區(qū)別就是，公鏈中的節(jié)點可以很自由的加入或者退出帘皿，不需要嚴(yán)格的驗證和審核东跪。

在公有鏈中用的最多的是pow算法和pos算法畸陡，這些算法都是參與者的利益直接相關(guān)鹰溜，通過利益來制約節(jié)點誠實的工作，解決分布式系統(tǒng)中的拜占庭問題丁恭。拜占庭容錯算法是一種狀態(tài)機副本復(fù)制算法曹动，通過節(jié)點間的多輪消息傳遞，網(wǎng)絡(luò)內(nèi)的所有誠實節(jié)點就可以達成一致的共識牲览。

使用拜占庭容錯算法不需要發(fā)行加密貨幣墓陈，但是只能用于私有鏈或者聯(lián)盟鏈，需要對節(jié)點的加入進行權(quán)限控制第献；不能用于公有鏈贡必，因為公有鏈中所有節(jié)點都可以隨意加入退出，無法抵擋女巫攻擊（sybil attack）

一庸毫、raft算法

raft 算法包含三種角色仔拟，分別是：跟隨者（ follower ），候選人（candidate ）和領(lǐng)導(dǎo)者（ leader ）飒赃。集群中的一個節(jié)點在某一時刻只能是這三種狀態(tài)的其中一種利花，這三種角色是可以隨著時間和條件的變化而互相轉(zhuǎn)換的科侈。

raft 算法主要有兩個過程：一個過程是領(lǐng)導(dǎo)者選舉，另一個過程是日志復(fù)制炒事，其中日志復(fù)制過程會分記錄日志和提交數(shù)據(jù)兩個階段臀栈。raft 算法支持最大的容錯故障節(jié)點是（N-1）/2，其中 N 為 集群中總的節(jié)點數(shù)量挠乳。

國外有一個動畫介紹raft算法介紹的很透徹权薯，鏈接地址為：http://thesecretlivesofdata.com/raft/。這個動畫主要包含三部分內(nèi)容睡扬，第一部分介紹簡單版的領(lǐng)導(dǎo)者選舉和日志復(fù)制的過程崭闲，第二部分內(nèi)容介紹詳細版的領(lǐng)導(dǎo)者選舉和日志復(fù)制的過程，第三部分內(nèi)容介紹的是如果遇到網(wǎng)絡(luò)分區(qū)（腦裂）威蕉，raft 算法是如何恢復(fù)網(wǎng)絡(luò)一致的刁俭。

二、 pbft算法(實用拜占庭容錯算法)

pbft 算法的提出主要是為了解決拜占庭將軍問題
要讓這個問題有解韧涨，有一個十分重要的前提牍戚，那就是信道必須是可靠的。如果信道不能保證可靠虑粥，那么拜占庭問題無解如孝。關(guān)于信道可靠問題，會引出兩軍問題娩贷。兩軍問題的結(jié)論是第晰，在一個不可靠的通信鏈路上試圖通過通信以達成一致是基本不可能或者十分困難的。
拜占庭將軍問題最早是由 Leslie Lamport 與另外兩人在 1982 年發(fā)表的論文《The Byzantine Generals Problem 》提出的彬祖， 他證明了在將軍總數(shù)大于 3f 茁瘦，背叛者為f 或者更少時，忠誠的將軍可以達成命令上的一致储笑，即 3f+1<=n 甜熔。算法復(fù)雜度為 o（n^(f+1)) 。而 Miguel Castro (卡斯特羅)和 Barbara Liskov （利斯科夫）在1999年發(fā)表的論文《 Practical Byzantine Fault Tolerance 》中首次提出 pbft 算法突倍，該算法容錯數(shù)量也滿足 3f+1<=n 腔稀，算法復(fù)雜度為 o（n^2）。

1.raft和pbft的最大容錯節(jié)點數(shù)

首先我們先來思考一個問題羽历，為什么 pbft 算法的最大容錯節(jié)點數(shù)量是（n-1）/3焊虏，而 raft 算法的最大容錯節(jié)點數(shù)量是（n-1）/2 ？

對于raft算法秕磷，raft算法的的容錯只支持容錯故障節(jié)點诵闭，不支持容錯作惡節(jié)點。什么是故障節(jié)點呢跳夭？就是節(jié)點因為系統(tǒng)繁忙涂圆、宕機或者網(wǎng)絡(luò)問題等其它異常情況導(dǎo)致的無響應(yīng)们镜，出現(xiàn)這種情況的節(jié)點就是故障節(jié)點。那什么是作惡節(jié)點呢润歉？作惡節(jié)點除了可以故意對集群的其它節(jié)點的請求無響應(yīng)之外模狭，還可以故意發(fā)送錯誤的數(shù)據(jù)，或者給不同的其它節(jié)點發(fā)送不同的數(shù)據(jù)踩衩，使整個集群的節(jié)點最終無法達成共識嚼鹉，這種節(jié)點就是作惡節(jié)點。

raft 算法只支持容錯故障節(jié)點驱富，假設(shè)集群總節(jié)點數(shù)為n锚赤，故障節(jié)點為 f ，根據(jù)小數(shù)服從多數(shù)的原則褐鸥，集群里正常節(jié)點只需要比 f 個節(jié)點再多一個節(jié)點线脚，即 f+1 個節(jié)點，正確節(jié)點的數(shù)量就會比故障節(jié)點數(shù)量多叫榕，那么集群就能達成共識浑侥。因此 raft 算法支持的最大容錯節(jié)點數(shù)量是（n-1）/2。

對于 pbft 算法晰绎，因為 pbft 算法的除了需要支持容錯故障節(jié)點之外寓落，還需要支持容錯作惡節(jié)點。假設(shè)集群節(jié)點數(shù)為 N荞下，有問題的節(jié)點為 f伶选。有問題的節(jié)點中，可以既是故障節(jié)點尖昏，也可以是作惡節(jié)點仰税，或者只是故障節(jié)點或者只是作惡節(jié)點。那么會產(chǎn)生以下兩種極端情況：

第一種情況会宪，f 個有問題節(jié)點既是故障節(jié)點肖卧，又是作惡節(jié)點蚯窥，那么根據(jù)小數(shù)服從多數(shù)的原則掸鹅，集群里正常節(jié)點只需要比f個節(jié)點再多一個節(jié)點，即 f+1 個節(jié)點拦赠，確節(jié)點的數(shù)量就會比故障節(jié)點數(shù)量多巍沙，那么集群就能達成共識。也就是說這種情況支持的最大容錯節(jié)點數(shù)量是 （n-1）/2荷鼠。
第二種情況句携，故障節(jié)點和作惡節(jié)點都是不同的節(jié)點。那么就會有 f 個問題節(jié)點和 f 個故障節(jié)點允乐，當(dāng)發(fā)現(xiàn)節(jié)點是問題節(jié)點后矮嫉，會被集群排除在外削咆，剩下 f 個故障節(jié)點，那么根據(jù)小數(shù)服從多數(shù)的原則蠢笋，集群里正常節(jié)點只需要比f個節(jié)點再多一個節(jié)點拨齐，即 f+1 個節(jié)點，確節(jié)點的數(shù)量就會比故障節(jié)點數(shù)量多昨寞，那么集群就能達成共識瞻惋。所以，所有類型的節(jié)點數(shù)量加起來就是 f+1 個正確節(jié)點援岩，f個故障節(jié)點和f個問題節(jié)點歼狼，即 3f+1=n。
結(jié)合上述兩種情況享怀，因此 pbft 算法支持的最大容錯節(jié)點數(shù)量是（n-1）/3

2.算法基本流程

pbft 算法的基本流程主要有以下四步：

客戶端發(fā)送請求給主節(jié)點
主節(jié)點廣播請求給其它節(jié)點羽峰，節(jié)點執(zhí)行 pbft 算法的三階段共識流程。
節(jié)點處理完三階段流程后添瓷，返回消息給客戶端限寞。
客戶端收到來自 f+1 個節(jié)點的相同消息后，代表共識已經(jīng)正確完成仰坦。
為什么收到 f+1 個節(jié)點的相同消息后就代表共識已經(jīng)正確完成履植？從上一小節(jié)的推導(dǎo)里可知，無論是最好的情況還是最壞的情況悄晃，如果客戶端收到 f+1 個節(jié)點的相同消息玫霎，那么就代表有足夠多的正確節(jié)點已全部達成共識并處理完畢了。

3.算法核心三階段流程
算法的核心三個階段分別是 pre-prepare 階段（預(yù)準(zhǔn)備階段）妈橄，prepare 階段（準(zhǔn)備階段）庶近， commit 階段（提交階段）

三、raft和pbft的對比

流程的對比上眷蚓，對于 leader 選舉這塊鼻种， raft 算法本質(zhì)是誰快誰當(dāng)選，而 pbft 算法是按編號依次輪流做主節(jié)點沙热。對于共識過程和重選 leader 機制這塊叉钥，為了更形象的描述這兩個算法，接下來會把 raft 和 pbft 的共識過程比喻成一個團隊是如何執(zhí)行命令的過程篙贸，從這個角度去理解 raft 算法和 pbft 的區(qū)別投队。

一個團隊一定會有一個老大和普通成員。對于 raft 算法爵川，共識過程就是：只要老大還沒掛敷鸦，老大說什么，我們（團隊普通成員）就做什么，堅決執(zhí)行扒披。那什么時候重新老大呢值依？只有當(dāng)老大掛了才重選老大，不然生是老大的人碟案，死是老大的鬼鳞滨。

對于 pbft 算法，共識過程就是：老大向我發(fā)送命令時蟆淀，當(dāng)我認為老大的命令是有問題時拯啦，我會拒絕執(zhí)行。就算我認為老大的命令是對的熔任，我還會問下團隊的其它成員老大的命令是否是對的褒链，只有大多數(shù)人 （2f+1） 都認為老大的命令是對的時候，我才會去執(zhí)行命令疑苔。那什么時候重選老大呢甫匹？老大掛了當(dāng)然要重選，如果大多數(shù)人都認為老大不稱職或者有問題時惦费，我們也會重新選擇老大兵迅。
四、結(jié)語
raft 算法和 pbft 算法是私鏈和聯(lián)盟鏈中經(jīng)典的共識算法薪贫，本文主要介紹了 raft 和 pbft 算法的流程和區(qū)別恍箭。 raft 和 pbft 算法有兩點根本區(qū)別：

raft 算法從節(jié)點不會拒絕主節(jié)點的請求，而 pbft 算法從節(jié)點在某些情況下會拒絕主節(jié)點的請求 ;
raft 算法只能容錯故障節(jié)點瞧省，并且最大容錯節(jié)點數(shù)為 （n-1）/2 扯夭，而 pbft 算法能容錯故障節(jié)點和作惡節(jié)點，最大容錯節(jié)點數(shù)為 （n-1）/3 鞍匾。

pbft算法是通過投票來達成共識交洗，可以很好的解決包括分叉等問題的同時提升效率。但僅僅比較適合于聯(lián)盟鏈私有鏈橡淑，因為兩兩節(jié)點之間通信量是O(n^2)（通過優(yōu)化可以減少通信量）构拳，一般來說不能應(yīng)用于超過100個節(jié)點。
pbft有解的前提是信道必須是可靠的梁棠，存在的問題是 可擴展性（scalability）差

部分來自：https://blog.csdn.net/kojhliang/article/details/80270223
區(qū)塊鏈在設(shè)計上就是為了BFT