正文

前言

一級標題

前言

一級標題

本次調研對比了類似以太坊的實現系統，分析了交易並行執行的難點和可能性。鏈本身基於Account 模型設計，而不是採用UTXO 模型。

一級標題

一級標題

1.國內的眾多聯盟鏈，如FISCO-BCOS，支持並行執行block 內部的交易驗證。

一級標題

3.Aptos，公鏈項目，Move 虛擬機。

我們先來回顧一下傳統的交易執行過程：

FISCO-BCOS

一級標題

一級標題

一級標題

概述

3.跨合約調用衝突。本來合約Ar 先部署，合約B 需要等到合約A 部署完成之後，去調用合約A ，但是當交易並行之後，並沒有這種先後順序，這就存在著衝突。

一級標題

一級標題

交易並行方案對比

一級標題

概述

FISCO-BCOS 2.0 在處理交易的過程中運用了圖結構，設計了一種基於DAG 模型的並行交易執行器（PTE，Parallel Transaction Executor）。 PTE 能充分發揮多核處理器優勢，使區塊中的交易能夠盡可能並行執行。同時對用戶提供簡單友好的編程接口，使用戶不必關心繁瑣的並行實現細節。基準測試程序的實驗結果表明，相較於傳統的串行交易執行方案，理想狀況下4 核處理器上運行的PTE 能夠實現約200% ~ 300% 的性能提升，且計算方面的提升跟核數成正比，核數越多性能越高。

方案細節

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

模塊架構

• 用戶直接或間接通過SDK 發起交易。

• 隨後交易在節點間同步，擁有打包權的節點調用打包器（Sealer）從（TxPool）中取出一定量交易並將其打包成一個區塊。此後，區塊被發送至共識單元（Consensus）準備進行節點間共識。

• 達成共識前需要執行交易驗證，此處便是PTE 工作的開始。從架構圖中可以看到，PTE 首先按序讀取區塊中的交易，並輸入到DAG 構造器（DAG Constructor）中。 DAG 構造器會根據每筆交易的依賴項，構造出一個包含所有交易的交易DAG，PTE 隨後喚醒工作線程池，使用多個線程並行執行交易DAG。匯合器（Joiner）負責掛起主線程，直到工作線程池中所有線程將DAG 執行完畢。此時Joiner 負責根據各個交易對狀態的修改記錄計算state root 及receipt root，並將執行結果返回至上層調用者。

• 區塊驗證通過後，區塊上鍊。在交易執行完成後，若各個節點狀態一致，則達成共識。區塊隨即寫入底層存儲（Storage），被永久記錄於區塊鏈上。

交易DAG 構造流程

1.從打包好的區塊中取出區塊的所有交易。

2.將交易數量作為最大頂點數量初始化一個DAG 實例。

3.按序讀出所有交易。如果一筆交易是可並行交易，則解析其衝突域，並檢查是否有之前的交易與該交易衝突。若存在衝突，則在相應交易間構造依賴邊。若該交易不可並行，則認為其必須在前序的所有交易都執行完後才能執行，因此在該交易與其所有前序交易間建立一條依賴邊。

備註：都建立依賴邊之後則無法並行，只能順序執行。

DAG 執行流程

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

問題與解決方法

1.對於同一個區塊，如何確保所有的節點執行完成，狀態一致（三個root 匹配）？

FISCO BCOS 採用驗證state root、transaction root 和receipt root 三元組是否相等的方式來判斷狀態是否達成一致。 transaction root 是根據區塊內的所有交易計算出的一個哈希值，只要所有共識節點處理的區塊數據相同，transaction root 必定相同。由於這一點比較容易保證，因此重點在於如何保證交易執行後生成的state 和receipt root 相同。

眾所周知，對於在不同CPU 核心上並行執行的指令，指令間的執行順序無法提前預測。並行執行的交易也存在同樣的情況。在傳統的交易執行方案中，每執行一筆交易，state root 便發生一次變遷，同時將變遷後的state root 寫入交易回執中。所有交易執行完後，最終的state root 就代表了當前區塊鏈的狀態，同時再根據所有交易回執計算出一個receipt root。

可以看出，在傳統的執行方案中，state root 扮演著一個類似全局共享變量的角色。當交易被並行且亂序執行後，傳統計算state root 的方式顯然不再適用。這是因為在不同的機器上，交易的執行順序一般不同，此時無法保證最後的state root 的一致性。同理，receipt root 的一致性也無法得到保證。

在FISCO BCOS 中，先並行執行交易，將每筆交易對狀態的改變歷史記錄下來，待所有交易執行完後，再根據這些歷史記錄綜合計算出一個state root。由此就可以保證即使並行執行交易，最後共識節點仍然能夠達成一致。

2. 如何判定兩筆交易是否有依賴？

若兩筆交易本來無依賴關係但被判定為有，則會導致不必要的性能損失；反之，如果這兩筆交易會改寫同一個賬戶的狀態卻被並行執行了，則該賬戶最後的狀態可能是不確定的。因此，

依賴關係的判定是影響性能甚至能決定區塊鏈能否正常工作的重要問題。

在簡單的轉賬交易中，我們可以根據轉賬的發送者和接受者的地址來判斷兩筆交易是否有依賴關係。

以如下3 筆轉賬交易為例：A→B，C→D，D→E。可以很容易看出，交易D→E 依賴於交易C→D 的結果，但是交易A→B 和其他兩筆交易沒有聯繫，因此可以並行執行。這種分析在只支持簡單轉賬的區塊鏈中是正確的。但因為我們無法準確知道用戶編寫的轉賬合約中到底有什麼操作，這種分析一旦放到圖靈完備、運行智能合約的區塊鏈中，則不夠準確。可能出現的情況是：A→B 的交易看似與C、D 的賬戶狀態無關，但是在用戶的底層實現中，A 是特殊賬戶，通過A 賬戶每轉出每一筆錢必須要先從C賬戶中扣除一定手續費。在這種場景下， 3 筆交易均有關聯，則它們之間無法使用並行的方式執行。若還按照先前的依賴分析方法對交易進行劃分，則必定會出現問題。FISCO BCOS 將交易依賴關係的指定工作交給更熟悉合約內容的開發者。具體來講，交易依賴的互斥資源可以由一組字符串表示。 FISCO BCOS 暴露接口給到開發者，開發者以字符串形式定義交易依賴的資源，告知鏈上執行器，執行器則根據開發者指定的交易依賴項自動將區塊中的所有交易排列為交易DAG 。比如在簡單轉賬合約中，開發者僅需指定每筆轉賬交易的依賴項是｛發送者地址+接收者地址｝。進一步講，假如開發者在轉賬邏輯中引入了另一個第三方地址，那麼依賴項就需要定義為｛發送者地址+接受者地址+第三方地址｝。。

互斥

• 這種方式實現起來較為直觀簡單，也比較通用，適用於所有智能合約，但也相應增加了開發者肩上的責任。開發者在指定交易依賴項時必須十分小心，如果依賴項沒有寫正確，後果將無法預料。並行框架合約FISCO BCOS 為了開發者能夠使用並行合約這一套框架設定了一些合約編寫的規範， 細節如下：並行互斥

• 互斥接口

。互斥是指兩筆交易各自

操作合約存儲變量的集合存在交集

例如，在轉賬場景中，交易是用戶間的轉賬操作。用transfer(X, Y) 表示從X 用戶轉到Y 用戶的轉賬接口，則互斥情況如下：

互斥參數

：合約

接口

中，與合約存儲變量的“讀/寫”操作相關的參數。例如轉賬接口為transfer(X, Y)，X 和Y 都是互斥參數。

互斥對象

• ：一筆交易中，根據互斥參數提取出來的、具體的互斥內容。例如轉賬接口為transfer(X, Y)，一筆調用此接口的交易中，具體的參數是transfer(A, B)，則這筆操作的互斥對像是[A, B]；另外一筆交易調用的參數是transfer(A, C)，則這筆操作的互斥對像是[A, C]。

判斷同一時刻兩筆交易是否能並行執行，就是判斷兩筆交易的互斥對像是否有交集。相互之間交集為空的交易可並行執行。

FISCO-BCOS 提供了兩種編寫並行合約的方式，一種是solidity 合約，另一種是預編譯合約。這裡只介紹solidity 合約，預編譯合約同理。

solidity 合約並行框架

編寫並行的solidity 合約時，在基礎上只需要將ParallelContract.sol 作為需要並行的合約的基類，並調用registerParallelFunction()方法，註冊可以並行的接口即可。

parallelContract 代碼如下：

以下是基於並行框架合約進行編寫的轉賬合約：

確定接口是否可並行"globalA",可並行的合約接口，必須滿足：

無調用外部合約。• 無調用其它函數接口。

確定互斥參數string、address、uint 256、int 256 在編寫接口前，需要先確定接口的互斥參數，接口的互斥即是對全局變量的互斥。互斥參數的確定規則為：

• 接口訪問了全局mapping，mapping 的key 是互斥參數。

• 接口訪問了全局數組，數組的下標是互斥參數。

• 接口訪問了簡單類型的全局變量，所有簡單類型的全局變量共用一個互斥參數，用不同的變量名作為互斥對象。確定互斥參數後，根據規則確定參數類型和順序，規則為：。

Khipu

可以看出，

（未來會支持更多類型）。

一級標題

概述

- 所有互斥參數排列在接口參數的最前。

一級標題

可以看出，

FISCO-BCOS 交易並行其實很大程度依賴用戶編寫合約的規範。如果用戶編寫合約不規範，系統貿然的進行了並行執行，則有可能會造成賬本root 不一致的問題

一級標題概述：

與FISCO-BCOS 的觀點不同，Khipu 認為讓用戶在編寫合約的時候識別和標明會發生靜態衝突的地址範圍並且不出錯是不現實的。

競態是否會出現、在何處出現、在什麼條件下會出現，只有當確定性獲取涉及到當前狀態後才可以做判斷。以目前的合約編程語言而言，幾乎不可能通過對代碼進行靜態分析來獲取完全無誤並且沒有遺漏的結果。

Khipu 針對這方面做了比較全面的嘗試，並且完成了工程實現。

方案細節

在Khipu 的實現方案中，同一個區塊裡面的每條交易都從前一個區塊的世界狀態開始，然後並行執行，在執行過程中記錄下所有的理想經歷路徑上遇到的以上三種競態。在並行執行階段結束後，轉入合併階段。合併階段開始逐條合併並行的世界狀態，每合併一條交易時，先從記錄下來的靜態條件中判斷是否已經與前面已經合併的競態條件有衝突。如果沒有，直接合併。如果有，則將這條交易以之前已經合併的世界狀態為起點再執行一次。最後合併的世界狀態將用區塊的哈希做最後的校驗。這是最後的一道防線，如果校驗有誤，則放棄前面的並行方案，將區塊內的交易重新串行執行。

並行度指標

Khipu 在這裡引入了一個並行度指標，即一個區塊內能夠不需要再次執行就可以直接合併結果的交易比例。 Khipu 通過對以太坊從創世區塊到最新的區塊進行幾天的重放觀測發現，這個比例（並行度）平均可以達到80% 。

安達爾定理

Aptos

你能給系統進行提速的極限取決於那些不能進行並行化的部分的倒數。也就是說，如果你可以進行99% 的並行化，那麼你就可以提速到100 倍。但如果你只能實現95% 的並行化，那麼你就只能提速到20 倍。

通過對evm 代碼指令的解讀可以發現，衝突的地方是一些有限的指令對於stroage 產生了讀寫過程，因此可以通過記錄這些讀寫的地方形成一個讀寫集合。僅僅利用靜態的代碼分析無法確保這些過程都被記錄，所以需要在處理每個區塊裡面的交易時對每一筆交易並行的預執行一次。通過預執行過程，可以得知這些交易是否是對同一個account 或者storage 進行讀寫，然後對每筆交易產生一個readSet 和writeSet。簡言之，預執行的過程就是首先將世界狀態拷貝多份作為所有交易的初始狀態。假設區塊鏈裡面存在100 個交易，那麼這100 多交易就可以通過線程池並行執行。每個合約都有同樣的初始世界狀態，執行過程中會也會產生100 個readSet 和writeSet ，同時也會各自產生100 個新的狀態。

一級標題

概述

通過對以太坊主網的交易重放可以發現，凡是衝突多的地方，大部分是交易所在同一個區塊進行的有互相關聯的交易，這也是與該過程相符合的。

一級標題

處理流程圖

具體並行執行過程

一級標題

概述

Aptos 在Diem 的Move 語言和MoveVM 的基礎上創建了一個高吞吐量的鏈，實現了並行執行。 Aptos 的方法是檢測關聯關係，同時對用戶/開發者透明。也就是說，不要求交易明確聲明它們使用哪一部分狀態（內存位置）。

Aptos 使用名為Block-STM 的軟件交易內存(Software transaction Memory ) 的修改版本，基於Block-STM 論文實現了並行執行引擎。

Block-STM 使用MVCC（多版本並發控制）來避免寫-寫衝突。所有到相同位置的寫入都與它們的版本一起存儲，這些版本包含它們的tx-id 和寫入tx 被重新執行的次數。當交易tx 讀取某一個內存位置的值時，它從MVCC 中獲得在tx 之前出現的寫入該位置的值，以及關聯的版本, 從而判斷是否有讀寫衝突。在Block-STM 中，交易在區塊內是預先排序的，並在執行期間在處理器線程之間劃分以並行執行。在並行執行中，假設沒有依賴關係執行交易，被交易修改的內存位置被記錄下來。執行後，驗證所有交易結果。在驗證期間，如果發現一個交易訪問了由先前交易修改的內存位置，則該交易無效。刷新交易的結果，重新執行交易。重複該過程，直到區塊中的所有交易都被執行。當使用多個處理器內核時，Block-STM 會加快執行速度。加速取決於交易之間的相互依賴程度。

• Khipu 對區塊內交易採用並行執行，順序驗證的方式，而Aptos 對區塊內的交易採用並行執行，並行驗證的方式。這兩種方案各有優缺點。 Khipu 的方案易實現，效率略低。 Aptos 的Block-STM 實現採用了諸多線程中的同步與信號操作，難以進行代碼實現，但效率較高。

一級標題

• 由於Move 原生支持全局資源尋址，所以在利於並行執行的情況下，Aptos 會對交易進行重新排序，甚至是跨區塊進行排序。官方宣稱這個方案既可以提高並行的效率，也可以解決MEV 問題，但是這樣是否會影響用戶體驗則有待考慮。

基準測試

一級標題

從上圖可以看到，Block STM 在32 個線程並行執行的情況下比使用程的順序執行實現了16 倍的加速，而在高爭用情況下，Block-STM 實現了超過8 倍的加速。

2.FISCO-BCOS Github, FISCO-BCOS

3.Khipu Github, GitHub - khipu-io/khipu: An enterprise blockchain platform based on Ethereum

4.Aptos Github, GitHub - aptos-labs/aptos-core: Aptos is a layer 1 blockchain built to support the widespread use of of blockchain through better technology and user experience.

一級標題

綜上所述，一些方案需要用戶在編寫合約時按照既定的規則寫存儲，這樣才能夠被靜態和動態分析發現依賴關係。 Solana 和Sui 採用了類似的方案，只是用戶感知度不同。這類方案本質上都是對於存儲模型的更改以獲得更好地分析結果。

一級標題

Khipu 和Aptos 的方案屬於用戶無感知的。即用戶無需謹慎編寫合約，虛擬機會在執行前進行動態分析依賴關係，從而將沒有依賴關係的並行執行。這類方案實現難度較大，而且並行度在一定程度上取決於交易的賬戶分部情況。當交易衝突較多的時候，不斷地重新執行反而會導致性能嚴重下降。 Aptos 在論文中提到後續可能也會對用戶編寫合約進行一些優化，從而更好地分析依賴關係，達到更快的執行速度。

考慮到工程實現和效率問題，OlaVM 大概率會採用Khipu+定制化存儲模型方案。在獲得性能提升的同時，避免引入Block-STM 帶來的複雜性，也便於後期更好的進行工程優化。

一級標題

參考：

1.Block-STM 論文：[ 2203.06871 ] Block-STM: Scaling Blockchain Execution by Turning Ordering Curse to a Performance Blessing (arxiv.org)

Github：Sin 7 y

一級標題