區塊鏈全方位的並行處理

2020 年 1 月 5 日
筆記

背景

PTE（Parallel Transaction Executor，一種基於 DAG 模型的並行交易執行器）的引入，使 FISCO BCOS 具備了並行執行交易的能力，顯著提升了節點交易處理的效率。

BCOS中交易並行

名詞解釋

1.1. DAG

一個無環的有向圖稱做有向無環圖（Directed Acyclic Graph），簡稱DAG圖。在一批交易中，可以通過一定方法識別出每筆交易需要佔用的互斥資源，再根據交易在Block中的順序及互斥資源的佔用關係構造出一個交易依賴DAG圖，如下圖所示，凡是入度為0（無被依賴的前序任務）的交易均可以並行執行。如下圖所示，基於左圖的原始交易列表的順序進行拓撲排序後，可以得到右圖的交易DAG。

模組架構

1 2 3 4 5 6 7 8

其中主要流程包括：用戶直接或間接通過SDK發起交易。交易可以是能夠並行執行的交易和不能並行執行的交易；交易進入節點的交易池中，等待打包；交易被Sealer打包為區塊，經過共識後，發送至BlockVerifier進行驗證； BlockVerifier根據區塊中的交易列表生成交易DAG； BlockVerifier構造執行上下文，並行執行交易DAG；區塊驗證通過後，區塊上鏈。

重要流程

3.1. 交易DAG構建

3.1.1. DAG數據結構

方案中所用到的DAG數據結構如下：

其中：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

頂點（Vertex） inDegree用於存儲頂點當前的入度; outEdge用於保存該頂點的出邊資訊，具體為所有出邊所連頂點的ID列表。 DAG： vtxs是用於存儲DAG中所有節點的列表； topLevel是一個並發隊列，用於存儲當前入度為0的節點ID，執行時供多個執行緒並發訪問； totalVtxs：頂點總數 totalConsume：已經執行過的頂點總數； void init(uint32_t _maxSize)：初始化一個最大頂點數為maxSize的DAG； void addEdge(ID from, ID to)：在頂點from和to之間建立一條有向邊； void generate()：根據已有的邊和頂點構造出一個DAG結構； ID waitPop(bool needWait)：等待從topLevel中取出一個入度為0的節點； void clear()：清除DAG中所有的節點與邊資訊。 TxDAG: dag：DAG實例 exeCnt：已經執行過的交易計數； totalParaTxs：並行交易總數； txs：並行交易列表 bool hasFinished()：若整個DAG已經執行完畢，返回true，否則返回false; void executeUnit()：取出一個沒有上層依賴的交易並執行；

3.1.2. 交易DAG構造流程

流程如下：

1 2 3

從打包好的區塊從取出區塊中的所有交易；將交易數量作為最大頂點數量初始化一個DAG實例；按序讀出所有交易，如果一筆交易是可並行交易，則解析其衝突域，並檢查是否有之前的交易與該交易衝突，如果有，則在相應交易間構造依賴邊；若該交易不可並行，則認為其必須在前序的所有交易都執行完後才能執行，因此在該交易與其所有前序交易間建立一條依賴邊。

3.2. DAG執行流程

流程如下：

1 2

主執行緒會首先根據硬體核數初始化一個相應大小的執行緒組，若獲取硬體核數失敗，則不創建其他執行緒；當DAG尚未執行完畢時，執行緒循環等待從DAG中pop出入度為0的交易。若成功取出待執行的交易，則執行該交易，執行完後將後續的依賴任務的入度減1，若有交易入度被減至0，則將該交易加入topLevel中；若失敗，則表示DAG已經執行完畢，執行緒退出。

瓶頸

對這個階段性結果，我們並不滿足，繼續深入挖掘發現，FISCO BCOS 的整體 TPS 仍有較大提升空間。用木桶打個比方：如果參與節點的交易處理所有模組構成木桶，交易執行只是組成整個木桶的一塊木板，根據短板理論，一隻木桶能盛多少水取決於桶壁上最矮的那塊，同理，FISCO BCOS 的性能也由速度最慢的組件決定。

儘管 PTE 取得了理論上極高的性能容量，但是 FISCO BCOS 的整體性能仍然會被其他模組較慢的交易處理速度所掣肘。為了能夠最大化利用計算資源以進一步提高交易處理能力，在 FISCO BCOS 中全面推進並行化改造勢在必行。

數據分析

根據並行程式設計的『分析→分解→設計→驗證』四步走原則，首先需定位出系統中仍存在的性能瓶頸的精確位置，才能更深入地對任務進行分解，並設計相應的並行化策略。使用自頂向下分析法，我們將交易處理流程分為四個模組進行性能分析，這四個模組分別是：

區塊解碼（decode）：

區塊在節點間共識或同步時需要從一個節點發送至另一個節點，這個過程中，區塊以 RLP 編碼的形式在網路間傳輸。節點收到區塊編碼後，需要先進行解碼，將區塊還原為記憶體中的二進位對象，然後才能做進一步處理。

交易驗簽（verify）：

交易在發送之前由發送者進行簽名，簽名得到的數據可以分為 (v, r, s) 三部分，驗簽的主要工作便是在收到交易或交易執行前，從 (v, r, s) 數據中還原出交易發送者的公鑰，以驗證交易發送者的身份。

交易執行（execute）：

執行區塊中的所有交易，更新區塊鏈狀態。

數據落盤（commit）：

區塊執行完成後，需要將區塊及相關數據寫入磁碟中，進行持久化保存。

以包含 2500 筆預編譯轉賬合約交易的區塊為測試對象，在我們的測試環境中，各階段的平均耗時分布如下圖所示：

從圖中可以看出，2500 筆交易的執行時間已經被縮短到了 50 毫秒以內，可以證明 PTE 對 FISCO BCOS 交易執行階段的優化是行之有效的。但圖中也暴露出了非常明顯的問題：其他階段的用時遠遠高於交易執行的用時，導致交易執行帶來的性能優勢被嚴重抵消，PTE 無法發揮出其應有的價值。

早在 1967 年，電腦體系結構領域的元老 Amdahl 提出的以他名字命名的定律，便已經向我們闡明了衡量處理器並行計算後效率提升能力的經驗法則：

其中，SpeedUp 為加速比，Ws 是程式的串列分量，Wp 是程式中的並行分量，N 為 CPU 數量。可以看出，在工作總量恆定的情況下，可並行部分程式碼佔比越多，系統的整體性能越高。我們需要把思維從線性模型中抽離出來，繼續細分整個處理流程，找出執行時間最長的程式熱點，對這些程式碼段進行並行化從而將所有瓶頸逐個擊破，這才是使通過並行化獲得最大性能提升的最好辦法。

根因拆解

串列的區塊解碼區塊解碼主要性能問題出在 RLP 編碼方法本身。RLP 全稱是遞歸的長度前綴編碼，是一種用長度作為前綴標明編碼對象中元素個數的編碼方法。如下圖所示，RLP 編碼的開頭即是此編碼中的對象個數（Object num）。在個數後，是相應個數的對象（Object）。遞歸地，每個對象，也是 RLP 編碼，其格式也與下圖相同。

需要特別注意的是，在 RLP 編碼中。每個 Object 的位元組大小是不固定的，Object num 只表示 Object 的個數，不表示 Object 的位元組長度。

RLP 通過一種長度前綴與遞歸結合的方式，理論上可編碼任意個數的對象。下圖是一個區塊的 RLP 編碼，在對區塊進行編碼時，先遞歸至最底層，對多個 sealer 進行編碼，多個 sealer 被編碼並加上長度前綴後，編碼成為一串 RLP 編碼（sealerList），此編碼又作為一個對象，被編入上層的一串 RLP 編碼（blockHeader）中。此後層層遞歸，最後編碼成為區塊的 RLP 編碼。由於 RLP 編碼是遞歸的，在編碼前，無法獲知編碼後的長度。

解碼時，由於 RLP 編碼中每個對象的長度不確定，且 RLP 編碼只記錄了對象的個數，沒記錄對象的位元組長度，若要獲取其中的一個編碼對象，必須遞歸解碼其前序的所有對象，在解碼前序的對象後，才能訪問到需要訪問的編碼對象的位元組位置。例如在上圖中，若需要訪問區塊中的第 0 筆交易，即 tx0，必須先將 blockHeader 解碼，而 blockHeader 的解碼，需要再次遞歸，把 parentHash，stateRoot 直至 sealerList 都解碼出來。

解碼區塊最重要的目的是解碼出包含在區塊中的交易，而交易的編碼都是互相獨立的，但在 RLP 特殊的編碼方式下，解碼一筆交易的必要條件是解碼出上一筆交易，交易的解碼任務之間環環相扣，形成了一種鏈式的依賴關係。需要指出的是，這種解碼方式並不是 RLP 的缺陷，RLP 的設計目標之一本就是盡量減少空間佔用，充分利用好每一個位元組，雖然編解碼變得低效了些，但編碼的緊湊度卻是有目共睹，因此這種編碼方式本質上還是一種時間換空間的權衡結果。

由於歷史原因，FISCO BCOS 中使用了 RLP 編碼作為多處資訊交換協議，貿然換用其他並行化友好的序列化方案可能會帶來較大的開發負擔。基於這一考慮，我們決定在原有的 RLP 編解碼方案稍作修改，通過為每個被編碼的元素添加額外的位置偏移資訊，便可以做到並行解碼 RLP 的同時不會改動大量原有程式碼。

交易驗簽 & 數據落盤開銷大通過對交易驗簽和數據落盤部分的程式碼進行拆解，我們發現兩者的主要功能都集中在一個耗時巨大的 for 循環。交易驗簽負責按序取出交易，然後從交易的簽名數據中取出 (v, r, s) 數據，並從中還原出交易發送者的公鑰，其中，還原公鑰這一步，由於涉及密碼學演算法，因此耗時不少；數據落盤負責從快取中逐個取出交易相關數據，將其編碼為 JSON 字元串後寫入磁碟，由於 JSON 編碼過程本身效率比較低，因此也是性能損失的重災區。

兩者程式碼分別如下所示：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17	// 交易驗簽 for(int i = 0; i < transactions.size(); ++i) { tx = transactions[i]; v, r, s = tx.getSignature(); publicKey = recover(v, r, s); // 從 (v, r, s) 中復原出發送者公鑰 … } 複製程式碼 // 數據落盤 for(int i = 0; i < datas.size(); ++i) { data = datas[i]; jsonStr = jsonEncode(data); // 將數據編碼為 JSON 字元串進行存儲 db.commit(jsonStr); … }

兩個過程共有的特點是，它們均是將同樣的操作應用到數據結構中不同的部分，對於這種類型的問題，可以直接使用數據級並行進行改造。所謂數據級並行，即是將數據作為劃分對象，通過將數據劃分為大小近似相等的片段，通過在多個執行緒上對不同的數據片段上進行操作，達到並行處理數據集的目的。

數據級並行唯一的附加要求是任務之間彼此獨立，毫無疑問，在 FISCO BCOS 的實現中，交易驗簽和數據落盤均滿足這一要求。

優化實踐

區塊解碼並行化改造過程中，我們在系統中使用的普通 RLP 編碼的基礎上，加入了 offset 欄位，用以索引每個 Object 的位置。如下圖所示，改造後編碼格式的開頭，仍然是對象的個數（Object num），但是在個數欄位後，是一個記錄對象偏移量的數組（Offsets）。

數組中的每個元素有著固定的長度。因此要讀取某個 Offset 的值，只需向訪問數組一樣，根據 Offset 的序號直接索引便可以進行隨機訪問。在 Offsets 後，是與 RLP 編碼相同的對象列表。相應序號的 Offset，指向相應序號的對象的 RLP 編碼位元組位置。因此，任意解碼一個對象，只需要根據對象的序號，找到其偏移量，再根據偏移量，就可定位到相應對象的 RLP 編碼位元組位置。

編碼流程也進行了重新設計。流程本身仍然基於遞歸的思路，對於輸入的對象數組，首先將對象數組的大小編碼在輸出編碼的開頭處，若數組大小超過 1，則按序逐個取出待編碼對象並快取其遞歸編碼，並在 Offsets 數組中記錄該對象的偏移位置，待數組遍歷完後，將快取的對象編碼第一次性取出並附加至輸出編碼末尾；若數組大小為 1，則遞歸對其編碼並寫入輸出編碼的末尾，結束遞歸。

編碼流程的偽程式碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

Rlps = RLP(); // Output，初始時為空 void encode(objs) //Input: objs = 待編碼對象的數組 { offset = 0; codes = []; objNum = objs.size() Rlps.push(objNum) if objNum > 1 { for obj in objs { rlp = encode(obj); // 遞歸調用編碼方法 Rlps.push(offset); offset += rlp.size(); codes.add(rlp); // 快取遞歸編碼的結果 } for x in codes { Rlps.push(x); } } else { rlp = encode(objs[0]); Rlps.push(rlp); } }

偏移量的引入使解碼模組能夠對元素編碼進行隨機訪問。Offsets 的數組範圍可以在多個執行緒間均攤，從而每個執行緒可以並行訪問對象數組的不同部分，分別進行解碼。由於是只讀訪問，這種並行方式是執行緒安全的，僅需最後再對輸出進行匯總即可。

解碼流程的偽程式碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	Objs decode(RLP Rlps) { objNum = Rlps.objNum； // 獲取對象個數 outputs = [] // 輸出的對象數組 if objNum > 1 { parallel for i = 0 to objNum { offset = Rlps.offsets[i]; code = Rlps.objs[offset]; x = decode(code); outputs.add(x); // 有序插入 outputs } } else { outputs.add(decode(Rlps.objs[0])); } return outputs; }

交易驗簽 & 數據落盤並行化對於數據級並行，業內已有多種成熟的多執行緒編程模型。雖然 Pthread 這類顯式的多執行緒編程模型能夠提供對執行緒進行更精細的控制，但是需要我們對執行緒通訊、同步擁有嫻熟的駕馭技巧。實現的複雜度越高，犯錯的幾率越大，日後程式碼維護的難度也相應增加。我們的主要目標僅僅對密集型循環進行並行化，因此在滿足需求的前提下，Keep It Simple & Stupid 才是我們的編碼原則，因此我們使用隱式的編程模型來達成我們的目的。

經過再三權衡，我們在市面上眾多隱式多執行緒編程模型中，選擇了來自 Intel 的執行緒構建塊（Thread Building Blocks，TBB）開源庫。在數據級並行方面，TBB 算是老手，TBB 運行時系統不僅屏蔽了底層工作執行緒的實現細節，還能夠根據任務量自動在處理器間平衡工作負載，從而充分利用底層 CPU 資源。

使用 TBB 後，交易驗簽和數據落盤的程式碼如下所示：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// 並行交易驗簽 tbb::parallel_for(tbb::blocked_range<size_t>(0, transactions.size()), & { for(int i = _range.begin(); i != _range.end(); ++i) { tx = transactions[i]; v, r, s = tx.getSignature(); publicKey = recover(v, r, s); // 從 (v, r, s) 中復原出發送者公鑰 … } }); // 並行數據落盤 tbb::parallel_for(tbb::blocked_range<size_t>(0, transactions.size()), & { for(int i = _range.begin(); i != _range.end(); ++i) { data = datas[i]; jsonStr = jsonEncode(data); // 將數據編碼為 JSON 字元串進行存儲 db.commit(jsonStr); … } });

可以看到，除了使用 TBB 提供的 tbb::parallel_for 進行並行循環和 tbb::blocked_range 引用數據分片外，循環體內的程式碼幾乎沒有任何變化，接近 C++ 原生語法正是 TBB 的特點。TBB 提供了抽象層級較高的並行介面，如 parallel_for、parallel_for_each 這類泛型並行演算法，從而使得改造能夠較為容易地進行。同時，TBB 不依賴任何語言或編譯器，只要有能支援 ISO C++ 標準的編譯器，便有 TBB 的用武之地。

當然，使用 TBB 並不是完全沒有額外負擔，比如執行緒間安全還是需要開發人員的仔細分析來保證，但 TBB 考慮周到，提供了一套方便的工具來輔助我們解決執行緒間互斥的問題，如原子變數、執行緒局部存儲和並行容器等，這些並行工具同樣被廣泛地應用在 FISCO BCOS 中，為 FISCO BCOS 的穩定運行保駕護航。

壓力測試的結果表明，FISCO BCOS 的交易處理能力，相較於並行化改造之前，成功提升了 1.74 倍，基本達到了這個環節的預期效果。

但是我們也深深明白，性能優化之路漫漫，木桶最短的一板總是交替出現，並行之道在於，通過反覆的分析、拆解、量化和優化，使得各模組互相配合齊頭並進，整個系統達到優雅的平衡，而最優解總是在「跳一跳」才能夠得著的地方。