簡介
Client會發(fā)送一系列請求給各個replicas節(jié)點來執(zhí)行相應(yīng)的操作，BFT算法保證所有正常的replicas節(jié)點執(zhí)行相同序列的操作。因為所有的replicas節(jié)點都是deterministic，而且初始狀態(tài)都相同，根據(jù)狀態(tài)機原理（state machine replication），這些replicas會產(chǎn)生相同的結(jié)果狀態(tài)。當(dāng)Client收到f+1個replicas節(jié)點返回的結(jié)果時，如果這些結(jié)果都一樣，因為BFT算法確保了最多有f個replicas出現(xiàn)問題，所以至少有一個replicas是正確的，那么Client收到的這些結(jié)果都是正確的。
但是state machine replication的難點在于確保正常replicas節(jié)點都以相同的序列執(zhí)行同樣的一些請求，尤其是如何來面對拜占庭故障。PBFT會融合primary-backup 和 quorum replication 兩種技術(shù)來序列化請求。
primary-backup
這個機制下有一個叫view的概念，在一個view里，一個replica會是主節(jié)點（primary），其余的replicas都叫備份節(jié)點（backups）。主節(jié)點負(fù)責(zé)將來自Client的請求給排好序，然后按序發(fā)送給備份節(jié)點們。但是主節(jié)點可能會是faulty的：它可能會給不同的請求編上相同的序號，或者不去分配序號，或者讓相鄰的序號不連續(xù)。備份節(jié)點應(yīng)當(dāng)有職責(zé)來主動檢查這些序號的合法性，并能通過timeout機制檢測到主節(jié)點是否已經(jīng)宕掉。當(dāng)出現(xiàn)這些異常情況時，這些備份節(jié)點就會觸發(fā)view change協(xié)議來選舉出新的主節(jié)點。
quorums有兩個重要的屬性：
Intersection： 任意兩個quorums至少有一個共同的并且正確的replica
Availability: 總是存在一個沒有faulty replicas的quorum
如果一個replica把信息寫給一個quorum，并讓該quorum來存儲信息，在收到每一個quorum中的成員的確認(rèn)反饋后，那么我們可以認(rèn)為該replica的信息已經(jīng)被可靠的保存在了這個分布式系統(tǒng)中。這是強的約束，當(dāng)然還有一個weak certificates：就是至少f+1個節(jié)點來共同存取信息，這樣至少有一個正確的replica存到了這份信息。
我們先來約定一些符合：
R是所有replicas的集合，每一個replica用一個整數(shù)來表示，依次為：
{ 0, …, |R - 1 }
簡單起見，我們定義
|R = 3f + 1
f 是最大可容忍的faulty節(jié)點
另外我們將一個view中的primary節(jié)點定義為replica p，
p = v mod |R
v 是view的編號，從0開始一直連續(xù)下去，這樣可以理解為從replica 0 到 replica |R-1 依次當(dāng)primary節(jié)點，當(dāng)每一次view change發(fā)生時。
我們定義一個quorum為至少包含2f+1個replicas的集合。
The Client
一個Client會將請求
?REQUEST,o,t,c? 其中o表示具體的操作，t表示timestamp，給每一個請求加上時間戳，這樣后來的請求會有高于前面的時間戳
replicas會接收請求，如果他們驗證了條請求，就會將它寫入到自己的log中。在共識算法保證下每個replica完成對該請求的執(zhí)行后直接將回復(fù)返回給client：
?REPLY,v,t,c,i,r? v是當(dāng)前的view序號，t就是對應(yīng)請求的時間戳，i是replica節(jié)點的編號，r是執(zhí)行結(jié)果
我們上面提到過weak certificate，在這里，client也會等待這個weak certificate：即有f+1個replicas回復(fù)，并且它們的回復(fù)擁有相同的 t 和 r，由于至多有f個faulty replicas，所以確保了回復(fù)是合法的。我們叫這個weak certificate為 reply certificate。
每一個replica會與每一個處于active狀態(tài)的client共享一份秘鑰。秘鑰所占據(jù)空間較少，加上會限制active client的數(shù)量，所以不必?fù)?dān)心以后出現(xiàn)的擴展性問題。
Normal Case Operation
我們采用三階段協(xié)議來廣播請求給replicas：pre-prepare, prepare, commit。
（1）pre-prepare階段：
主節(jié)點收到客戶端請求，給請求編號，并發(fā)送pre-pre類型信息給其他從節(jié)點。
從1節(jié)點收到pre-pre類型信息，如果同意這個請求的編號，如果同意就進入prepare階段
（2）Prepare階段：
從1節(jié)點同意主節(jié)點請求的編號，將發(fā)送prepare類型消息給主節(jié)點和其他兩個從節(jié)點。如果不發(fā)，表示不同意。
圖：從1節(jié)點發(fā)prepare信息給其他節(jié)點
從1節(jié)點如果收到另外兩個從節(jié)點都發(fā)出的同意主節(jié)點分配的編號的prepare類型的消息，則表示從1節(jié)點的狀態(tài)為prepared,該節(jié)點會擁有一個prepared認(rèn)證證書。
為了防止viewchange導(dǎo)致主節(jié)點給請求分配的編號失效，引入commit階段。
（3）commit階段
從1節(jié)點進入prepared狀態(tài)后，將發(fā)送一條COMMIT類型信息給其它所有節(jié)點告訴他們它有一個prepared認(rèn)證證書了。
圖：從1節(jié)點發(fā)commit類型信息給其他節(jié)點
如果從1節(jié)點收到2f+1條commit信息，證明從1節(jié)點已經(jīng)進入commited狀態(tài)。
只通過這一個節(jié)點，我們就能認(rèn)為客戶端的請求在需要的節(jié)點中都到達了prepared狀態(tài)，每一個需要的節(jié)點都同意了主節(jié)點分配的編號。當(dāng)一個請求在某個節(jié)點中到達commited狀態(tài)后，該請求就會被該節(jié)點執(zhí)行。
Garbage Collection
分布式系統(tǒng)的復(fù)雜性在于要考慮到各種各樣的意外和蓄意破壞，你要制定出一套有效的法律來約束這個系統(tǒng)里可能發(fā)生的一切行為，并沒有完美的分布式系統(tǒng)存在。
當(dāng)replica執(zhí)行完請求時，需要把之前記錄的該請求的信息清除掉。但是不能這樣輕易的去清除，其中包含的prepared certificate可能會在后面用得上。所以要有種機智來保證何時可以清除。
其實很簡單，每執(zhí)行完一條請求，該節(jié)點會再一次發(fā)出廣播，就是否可以清除信息在全網(wǎng)達成一致。更好的方案是，我們一連執(zhí)行了K條請求，在第K條請求執(zhí)行完時，向全網(wǎng)發(fā)起廣播，告訴大家它已經(jīng)將這K條執(zhí)行完畢，要是大家反饋說這K條我們也執(zhí)行完畢了，那就可以刪除這K條的信息了，接下來再執(zhí)行K條，完成后再發(fā)起一次廣播，即每隔K條發(fā)起一次全網(wǎng)共識，這個概念叫checkpoint，每隔K條去征求一下大家的意見，要是獲得了大多數(shù)的認(rèn)同（a quorum certificate with 2 f + 1 CHECKPOINT messages (including its own)），就形成了一個 stable checkpoint（記錄在第K條的編號），我們也說該replica擁有了一個stable certificate就可以刪除這K條請求的信息了。
這是理想的情況，實際上當(dāng)replica i向全網(wǎng)發(fā)出checkpoint共識后，其他節(jié)點可能并沒有那么快也執(zhí)行完這K條請求，所以replica i不會立即得到響應(yīng)，它還要繼續(xù)自己的步伐，那這個checkpoint在它那里就不是stable的。那這個步伐快的replica可能會越來越快，可能會把大家拉的越來越遠(yuǎn)，這時我們來看一下上面提到的高低水位的作用。對該replica來說，它的低水位h等于它上一個stable checkpoint的編號，高水位H=h+L，L是我們指定的數(shù)值，它一般是checkpoint周期K的常數(shù)倍（這個常數(shù)是比較小的， 比如2倍），這樣即使該replica步伐很快，它處理的請求編號達到高水位H后也得停一停自己的腳步，直到它的stable checkpoint發(fā)生變化，它才能繼續(xù)向前。
View Changes
當(dāng)主節(jié)點掛掉后就觸發(fā)了view change協(xié)議。我們需要確保在新的view中如何來延續(xù)上一個view最終的狀態(tài)，比如給這時來的新請求的編號，還有如何處理上一個view還沒來得及完全處理好的請求。
Data Structures
所以我們需要記錄上一個view里發(fā)生什么。
有兩個集合P和Q，replica i 的P存著 i 在上一 view 中達到prepared狀態(tài)的請求的一些信息，有了P，在新的view中，replica i就會明白接下來處于prepared狀態(tài)的請求不能與上一個view中處于prepared狀態(tài)的請求的編號相同。Q是記錄在上一個view里到達pre-prepared狀態(tài)的請求的一些信息。
View-Change Messages
我們來看一下Fig 2， 當(dāng)備份節(jié)點 i 懷疑 view v中的主節(jié)點出問題（比如是壞節(jié)點）后，它會進入 view v+1，并廣播一條VIEW-CHANGE信息給所有的replicas，其中包含該replica i最新的stable checkpoint的編號，還有 replica i上存的每一個checkpoint的編號和digest的集合，還有上面所說的該replica的P和Q兩個集合。
View-Change-Ack Messages
replicas 會收集VIEW-CHANGE信息并發(fā)送ACK確認(rèn)給 view v+1 中的主節(jié)點
。新的主節(jié)點收集了VIEW-CHANGE和VIEW-CHANGE-ACK（包含自己的信息），它會將VIEW-CHANGE存在一個集合S中。主節(jié)點需要選出一個checkpoint作為新view處理請求的起始狀態(tài)。它會從checkpoint的集合中選出編號最大（假設(shè)編號為h）的checkpoint。接下來，主節(jié)點會從h開始依次選取h到h+L（L就是normal case階段我們提到的設(shè)置值）之間的編號n對應(yīng)的請求在新的view中進行pre-prepare，如果一條請求在上一個view中到達了committed狀態(tài)，主節(jié)點就選取這個請求開始在新的view中進行三階段。之所以選取committed的請求，是因為上面我們提到增加COMMIT階段為了across view來考慮的，處于committed狀態(tài)的請求的編號在新的view中是有效的，可以繼續(xù)使用。但是如果選取的請求在上一view中并沒有被一個quorum給prepare，那它的編號n有可能是不被一個quorum給同意的，我們選擇在新的view中作廢這樣的請求。
