前言

衷心感謝《The Science of the Blockchain》一書的作者Roger Wattenhofer，《The Science of the Blockchain》一書較為嚴謹地介紹了一種基礎技術——容錯分布式系統（faulttolerant distributed system），

在容錯分布式系統中，資料存盤在多臺服務器上，并且多臺服務器協同完成一項計算操作，這里面，最大的問題便是如何進行協調（coordination problem），圍繞協調問題，研究人員提出了諸多演算法與模型，如：區塊鏈，一致性協議，電子合同，共識機制，電子賬本，溯源系統，等，

容錯分布式系統具有許多重要作用：
（1）同一份資料在多臺服務器上進行備份，當一臺服務器宕機或遭到黑客惡意攻擊時，仍可從其它正常服務器獲取或恢復資料（從另一角度出發，多中心化防止了一臺服務器的腐敗，message corruption一詞用的很有意思），
（2）客戶端 C 1 C_1 C1?離 S a S_a Sa?較近而離 S b S_b Sb?較遠，客戶端 C 2 C_2 C2?則相反，且 S a S_a Sa?和 S b S_b Sb?提供相同的服務，但只有一臺服務器時，總有一個客戶端的回應時間較長，而有多臺服務器時，客戶端可就近獲取服務，減少回應時長，

狀態復制

定義2.8（狀態復制，state replication） 網路中所有結點的初始狀態一樣，然后執行相同序列的命令 ( c 1 , c 2 , c 3 , … ? ) (c_1, c_2, c_3, \dots) (c1?,c2?,c3?,…)，則稱該網路實作了狀態復制功能，

復制狀態機是一個計算機網路，整個網路系統就像單個狀態機那樣運行，即：當一臺計算機狀態欲發生變化且獲得整個網路系統許可（一個時刻僅有 n ≤ 1 n \leq 1 n≤1臺計算機獲得許可）時，這臺計算機狀態發生變化且其狀態被復制到其余所有計算機中去，

（上示圖例來自博客跨鏈技術踐行者）

Fault-Tolerance & Paxos

這里不再贅述基本概念，現約定：分布式系統中所有節點（即所有服務器和客戶端）都是誠實可靠的，服務器收到客戶端的命令 m m m后立刻執行，

先考慮一臺服務器 S S S、一個客戶端 C C C的應用場景， C C C發送一份訊息（命令） m m m給 S S S，為了解決訊息污染（訊息被黑客惡意篡改、因硬體等因素導致位元翻轉等）和訊息丟失問題，需要采用訊息驗證碼、數字簽名和訊息確認（acknowledgment，即ack）等演算法，

1. C C C發送 m m m給 S S S，并利用訊息驗證碼或數字簽名附上校驗碼 τ \tau τ；
2. S S S根據 τ \tau τ判斷 m m m是否安全（具體看密碼學安全性定義），若安全則回復一個訊息確認ack，并執行相關命令 m m m（為避免重復執行同一命令， S S S可自己存盤一張歷史串列以進行核對檢查）；
3. 若 C C C在規定時間內沒有收到相應的ack，重新發送 ( m , τ ) (m, \tau) (m,τ)，

討論. 在具體實作中如何建立可靠連接請參考：TCP 為什么是三次握手，而不是兩次或四次？ - 山盡的回答 - 知乎，注意，是建立可靠連接而非實作共識演算法，網路上很多其它解釋是錯誤的，他們所舉例子與共識演算法例子混淆了，《The Science of the Blockchain》學到下一章節便會證明：三次溝通依舊無法達成共識，

再考慮多臺服務器、一個客戶端的應用場景，易知，客戶端僅需要群發 ( m , τ ) (m, \tau) (m,τ)即可實作分布式系統，

接著考慮一臺服務器、多個客戶端的應用場景，多個客戶端可能同時發送不同命令，這多條命令之間存在沖突（服務器一次僅能處理一條命令），所幸僅有一臺服務器，它可以自由決定多條命令的執行序列，

最后考慮多臺服務器、多個客戶端的應用場景，該場景十分復雜，例如， C 1 C_1 C1?發送 m 1 m_1 m1?給 S a S_a Sa?和 S b S_b Sb?，同時間， C 2 C_2 C2?發送 m 2 m_2 m2?給 S a S_a Sa?和 S b S_b Sb?，由于網路延遲（具體參考計算機網路知識）， S a S_a Sa?可能先收到 m 1 m_1 m1?再收到 m 2 m_2 m2?，而 S b S_b Sb?可能先收到 m 2 m_2 m2?再收到 m 1 m_1 m1?，這就導致兩臺服務器執行命令后的狀態不一致，失去了分布式系統的最初功能，

為保證所有服務器的狀態一致，我們要確保它們的命令執行序列相同，即所有服務器第 i i i次命令操作都一樣，先簡化模型，僅考慮序列中的索引 i i i，問題演化成：在一次選舉中，多個客戶端分別提出各自的議案 m 1 m_1 m1?， m 2 m_2 m2?， … \dots …，眾多服務器需要從中協調選取出一個大家都認可的議案，

最簡單的方法便是指定一臺串行器（serializer），所有客戶端將各自的議案發送給串行器，由串行器決定第 i i i次命令為哪一個，然后群發給所有服務器（即先一臺服務器多個客戶端，再多臺服務器一個“客戶端”），但該主從（master-slave）方法弊端較為明顯，即當串行器死機時整個分布式系統便會徹底崩潰，

另一種可嘗試的方法便是兩段互斥鎖協議（借用計算機作業系統的相關思想），設計如下簡單協議：

1. 階段A，客戶端向所有服務器申請鎖，
2. 階段B，若規定時間內所有服務器都將鎖給了客戶端，則客戶端將訊息 m m m發送給所有服務器；否則，客戶端將當前占有的鎖還給服務器，等待一段時間并回傳階段A，

上述協議耗時較長，且不具備容錯能力（萬一1臺服務器宕機了，那么整個系統崩潰），可以進行改進，即將申請所有的鎖改成申請半數以上的鎖，

但兩段上鎖協議存在死鎖問題，假想有4臺服務器，客戶端 C 1 C_1 C1?和 C 2 C_2 C2?分別占有了半數的鎖，在階段B時， C 1 C_1 C1?本來想釋放它占有的鎖，但突然 C 1 C_1 C1?宕機了，那整個系統就徹底陷入僵死狀態，一個看似可解的方法就是讓服務器為鎖設定占有時長（開始有Paxos的影子），思考如下案例：

C 1 C_1 C1?占有了鎖 L 1 L_1 L1?和 L 2 L_2 L2?， C 2 C_2 C2?占有了鎖 L 3 L_3 L3?和 L 4 L_4 L4?， C 1 C_1 C1?宕機而 C 2 C_2 C2?正常運作，超過一定時長，服務器自認為識訓了 C 1 C_1 C1?和 C 2 C_2 C2?的鎖并其鎖 ( L 1 , L 2 , L 3 ) (L_1, L_2, L_3) (L1?,L2?,L3?)給了 C 2 C_2 C2?， C 2 C_2 C2?提交命令 m 2 m_2 m2?，碰巧的是同時間， C 1 C_1 C1?恢復作業并占有了鎖 L 4 L_4 L4?且由于作業系統錯誤 C 1 C_1 C1?仍認為它持有鎖 L 1 L_1 L1?和 L 2 L_2 L2?， C 1 C_1 C1?也提交命令 m 1 m_1 m1?，這就產生了命令沖突，

由上述例子可知，不宜僅讓服務器來維護鎖的狀態（是否歸還），而應該由客戶端和服務器 S i S_i Si?二者共同記錄鎖 L i L_i Li?的狀態，并且，二者還應該為鎖加上一個編號，當服務器看到兩者持有的鎖編號不一致時可判斷出這把鎖是無效的（服務器已識訓該鎖但客戶端誤認為自己還持有該鎖），

如何制定鎖的編號？需要遵循一條原則：先發的鎖無法覆寫后發的鎖（因為當服務器產生后發的鎖時它已認為新發的鎖被“識訓”了），既然這里有個優先級且隨時間增長優先級變大，那么就可以拿這個優先級來做鎖的編號，

由誰來決定鎖的編號？如果讓服務器來決定鎖的編號，那么有如下問題：有4臺服務器，一個客戶端向整個網路系統申請4把鎖，需要維護一個數值串列 ( L 1 , L 2 , L 3 , L 4 ) (L_1, L_2, L_3, L_4) (L1?,L2?,L3?,L4?)，存盤開銷較大（注意：4臺服務器的時鐘步長不一定一樣，這會導致該辦法中的 L i L_i Li?是不同步的），相反，如果由客戶端來決定鎖的編號，那么就沒有該問題，

如何制定鎖的占有時長？時長數值設定太大容易導致系統回應時間較長，時長數值設定太小有可能導致命令還沒來得及發送鎖就被“識訓”，Paxos協議利用客戶端的通信速度來自適應決定鎖的占有時長，

一個不完善的粗糙協議被制定如下（上述符號 m m m接下來用 c c c代替）：

注意，上述協議無法被嚴格證明是安全的（安全指不存在狀態不一致問題），假想， C 1 C_1 C1?在階段3發送了execute(c)，但不幸由網路延遲導致發送程序較慢，碰巧更不幸的是 C 2 C_2 C2?快速完成了半數以上鎖的申請并發送了另外一條execute(c’)，這時整個系統就炸了，

為解決上述問題，我們可以想辦法通知 C 2 C_2 C2?讓它主動把c’ 變成 c c c，于是就有了Paxos協議，

好了，現在所有服務器執行的便都是命令 c c c，為防止重復執行（先收到 C 1 C_1 C1?發送的execute(c)，又收到 C 2 C_2 C2?發送的execute(c)），服務器可以維護一張命令執行記錄，

本文詳細地介紹了Paxos協議的設計思路，我們研究人員在設計一份可靠協議時需要有一個完整清晰的思路，這里不再贅述安全性證明，若想深入研究Paxos的理論證明，請購買《The Science of the Blockchain》正版書籍進行研讀，這里僅介紹如何在第 i i i次協商中挑選出唯一的命令 c c c，對執行多個命令，讀者可進行自己思考（Tips. 為選舉也打上一個編號標簽），

Reference

The Science of the Blockchain筆記（一）
區塊鏈Paxos演算法
分布式共識的作業原理，Part-2：共識問題與 FLP 不可能定理