Forerunner：首個面向“多未來”的推測執(zhí)行技術

編者按：10月26-29日，系統(tǒng)領域的全球頂會 SOSP 2021 在線上舉辦。在本屆大會上，微軟亞洲研究院研究員陳洋、郭眾鑫、李潤懷（實習生，浙江大學）、陳碩、周禮棟、張憲以及浙江大學周亞金教授共同提出了一種新穎的基于約束的推測執(zhí)行技術——Forerunner，這是第一個面向“多未來”的推測執(zhí)行技術。本篇論文獲得了 Artifact Evaluation 全部三個最高級別徽章（即代碼可評估、代碼可獲取和實驗結果可復制）。今天將為大家從這項研究的底層思路和邏輯進行梳理總結。想要了解更多技術細節(jié)和更深入的實驗數(shù)據(jù)，歡迎參閱論文原文。

在近日舉行的系統(tǒng)領域全球頂會 SOSP 2021 上，微軟亞洲研究院的研究員們在論文“Forerunner: Constraint-Based Speculative Execution for Ethereum”中，提出了一種全新的、基于約束（constraints）的推測執(zhí)行（speculative execution）技術——Forerunner。這是首個面向“多未來”的推測執(zhí)行技術，其技術特點是把利用預執(zhí)行（pre-execution）來加速實際執(zhí)行（actual execution）的手段進行了巧妙且基于通用約束的泛化。

論文鏈接：https://www.microsoft.com/en-us/research/publication/forerunner-constraint-based-speculative-transaction-execution-for-ethereum/

微軟亞洲研究院的研究員們將 Forerunner 方法應用在了支持智能合約（smart contract）的以太坊（Ethereum）區(qū)塊鏈中，以嘗試對位于其系統(tǒng)核心的交易（transaction）執(zhí)行環(huán)節(jié)進行加速。為了在最真實的場景下對技術效果進行評估，其中所有實驗都是基于以太坊公鏈上實時產(chǎn)生的真實交易和區(qū)塊（block）進行的。評估結果表明：經(jīng)過泛化的推測執(zhí)行技術能在真實系統(tǒng)中取得了可觀的性能收益。這種對交易執(zhí)行的加速能力可以用來提高以太坊核心層交易吞吐量。其主要的性能結果已經(jīng)在 SOSP 的 Artifact Evaluation 中得到了獨立的復現(xiàn)。

下面讓我們來一起了解一下推測執(zhí)行技術以及 Forerunner 的原理。

基礎：“推測執(zhí)行” 

推測執(zhí)行技術已經(jīng)成功的應用于許多系統(tǒng)之中，每當有一段需要稍后才會執(zhí)行的代碼出現(xiàn)時，都可以使用這種技術。由于決定其執(zhí)行結果的代碼輸入只有在執(zhí)行發(fā)生時才會完全知道，所以通過對輸入進行預測，可以在備用或空閑資源上預先執(zhí)行代碼。如果后來發(fā)現(xiàn)預測正確，則可以跳過實際執(zhí)行，返回預執(zhí)行結果，從而實現(xiàn)對實際執(zhí)行的加速。但是，當預測結果錯誤時，預執(zhí)行將不會起作用，并且會因為核對預測結果而引入額外的開銷。推測執(zhí)行過去多被應用于“單未來”環(huán)境中，在這種情況下，簡單地押注最可能出現(xiàn)的那種未來，就是一種有效的策略。 

圖1：推測執(zhí)行示意圖

問題：“多未來”推測執(zhí)行

“多未來”的推測執(zhí)行問題源于以太坊區(qū)塊鏈交易處理中的機遇和挑戰(zhàn)。作為可編程的區(qū)塊鏈，以太坊交易能夠觸發(fā)任意智能合約代碼的執(zhí)行。因此，其執(zhí)行環(huán)節(jié)是系統(tǒng)中的一個瓶頸。抽象的來說，以太坊是以“傳播-共識-執(zhí)行”模型來運作的。在這個模型中，交易首先通過 P2P 網(wǎng)絡進行“傳播”，然后通過去中心化的“共識”算法被接受到一個個區(qū)塊中，然后由所有以太坊節(jié)點按區(qū)塊鏈中的順序“執(zhí)行”。雖然“傳播到執(zhí)行”窗口為推測執(zhí)行創(chuàng)造了自然的機會，但由于去中心化的“傳播”和“共識”過程，使交易的進塊時機和順序存在很多不同的可能性，從而導致了“多未來”現(xiàn)象的產(chǎn)生。而且，通常沒有任何一種可能的“未來”占有壓倒性的概率優(yōu)勢。這就意味著，如果對每筆交易只做一種預測，無論每次押注在哪種可能的“未來”上，預測的總體準確度都不會很高。這種“多未來”的情況，是傳統(tǒng)“單未來”推測執(zhí)行技術無法有效應對的挑戰(zhàn)。 

圖2：以太坊交易執(zhí)行的“多未來”特性示意圖

思路：“跨未來”加速

直觀上來說，為了應對“多未來”挑戰(zhàn)必須找到一種方法，使其能夠利用一個或很少的預執(zhí)行來覆蓋大部分的可能性空間。這在本質上需要實現(xiàn)“跨未來”的加速。換言之，就是要利用在預測的某個”未來“中實施的預執(zhí)行結果，來加速在其他可能發(fā)生的”未來“中的執(zhí)行。從這種意義上來看，傳統(tǒng)的推測執(zhí)行技術實施的是”同未來“加速。雖然通過“跨未來”方式得到的加速并不一定能與“同未來”方式獲得的加速結果相匹敵。但可以通過進行合理地預測，讓預執(zhí)行所基于的“ 未來”與實際會發(fā)生的“未來” 更加相似，進而獲得更高的加速度。 

一旦我們有機會基于預測出的多種“未來”而進行多次預執(zhí)行，那么就可以引入另一種“跨未來”的加速方式。從某種意義上說，這是對剛剛描述的”一對多“想法的對偶。它是指盡可能利用已有的多個預執(zhí)行來更好地加速實際發(fā)生的真實”未來“。這種”多對一“想法大致上是將各個預執(zhí)行拆分開來，并將拆分后的部件重新組裝在一起，以盡可能接近真實的未來。目標是使用更高的相似性來實現(xiàn)更高的加速比。理想情況下，它應該允許基于幾個實際發(fā)生的預執(zhí)行，組合拼接出大量的預執(zhí)行，以增加完全命中實際的”未來“，或是非常接近它的可能性。 

圖3：“一對多”加速及“多對一(多)”加速示意圖

“未來“間的連結：控制/數(shù)據(jù)-等價性

為了實現(xiàn)“跨未來“加速，研究員們需要找出可能發(fā)生的諸多“未來”的內(nèi)在相似性，使得在一個“未來”中完成的計算可用于加速在另一個“未來”的執(zhí)行。這其中的關鍵是把在每個可能在“未來”中的執(zhí)行視為指令跟蹤（instruction trace）序列，并利用其結構上的等價性來實現(xiàn)“跨未來”加速。 

微軟亞洲研究院的研究員們提出的這種指令序列在結構上的等價性被稱為 CD-Equivalence，其中 C 和 D 分別是控制流（control flow）和數(shù)據(jù)流（data flow）的首字母。當且僅當它們的指令序列具有相同的控制流和數(shù)據(jù)流時，兩個指令跟蹤序列是控制/數(shù)據(jù)-等價的（CD-Equivalent）。這意味著，兩者執(zhí)行的所有指令以及它們的順序是完全相同的，并且對應指令間的數(shù)據(jù)依賴也是完全一致的。CD-Equivalence 能將所有可能發(fā)生的“未來”劃分到各個等價類中。在每個類的任一“未來”中的執(zhí)行都會產(chǎn)生等價（CD-Equivalent）的指令跟蹤序列。這就說明如果能以某種方式，將任一指令跟蹤序列轉化為一個可執(zhí)行程序，它就可以在同屬一個等價類的所有“未來”中產(chǎn)生與原始交易的代碼相同的執(zhí)行結果。這種基于跟蹤序列的程序有一個非常重要的特性：它本質上是針對給定等價類完全展開（unroll）和內(nèi)聯(lián) (inline)后的一條直線型指令序列，而且指令間的數(shù)據(jù)依賴關系也是單一且完全確定的。這使得它具有高度的可優(yōu)化性。因此，可以通過基于某個預測出的“未來”，進行一次預執(zhí)行并跟蹤記錄其指令序列，再通過激進的優(yōu)化將其特化為一條更短、更有效的快速路徑（fast path）程序。這條快速路徑能夠加速同屬一個等價類的所有”未來”。為了刻畫一個快速路徑的適用范圍，研究員們會生成一組針對給定等價類的約束條件（constraints），來判定一個給定的“未來”是否屬于這個等價類。 

選擇 CD-Equivalence 的另一個非常重要的原因是基于對以太坊上真實交易（transactions）的關鍵觀察：這些交易在多種不同“未來”中的執(zhí)行之間，往往具有基于 CD-Equivalence 的等價性。研究員在論文中用一個具體的例子對此進行了進一步闡釋。換言之，CD-Equivalence 能夠把以太坊真實場景的“未來”空間劃分為較少的幾個等價類，使得少數(shù)幾個預執(zhí)行就能覆蓋住全部或是大部分的可能性空間。 

圖4：CD-Equivalence 示意圖

關鍵技術：多指令序列的程序特化和記憶化

Forerunner 的關鍵技術是將兩種新穎的方法進行有機結合。它們是一種新的多指令序列的程序特化和一種新的記憶化。Forerunner 首先會對預執(zhí)行進行跟蹤（tracing），進而得到指令序列，然后利用程序特化技術（Specialization）生成由約束檢查代碼和快速路徑代碼組合而成的“加速程序”，最后再利用記憶化技術（Memoization）在“加速程序”的各個代碼段上添加“近道“（shortcut）” ?！敖馈皶鶕?jù)預執(zhí)行中記住的信息生成。而“加速程序“在其執(zhí)行過程中，則可以利用”近道“跳過部分代碼段，從而進一步提高加速效果。

Forerunner的關鍵技術有以下幾個亮點：

（1）特化生成的”加速程序“其代碼長度比原始跟蹤序列短得多，平均而言，僅為其十分之一；

（2）特化過程中的一個關鍵創(chuàng)新是將特化后的代碼轉換到一種簡化后的中間語言上。這種新的中間語言能在一個極大簡化后的虛擬機上執(zhí)行，其效率遠超支持原始代碼的復雜虛擬機。這使得本來就更短的”加速程序“代碼還能被更高效的執(zhí)行；

（3）”加速程序“ 的執(zhí)行是無需回滾的。在確信給定的”未來“可以通過其快速路徑加速之前，”加速程序“ 不會進行任何外部可見的更改。這意味著，在發(fā)現(xiàn)無法加速的情況，可以立即用原始代碼執(zhí)行，而無需任何回滾的操作；

（4）研究員們提出的創(chuàng)新的方法能夠對多個快速路徑所對應的多組約束檢查進行合并式檢查。這確保了約束檢查的成本不會隨著所需要涵蓋的等價類的數(shù)量而增加；

（5）抄”近道“機制非常靈活和強大。它可以利用在預執(zhí)行中記住的信息跳過“加速程序”的不同部分。它是實現(xiàn)前面提到的“多對一”加速的關鍵。在評估中，研究員們觀察到抄“近道“機制可以跳過 80% 以上的”加速程序“代碼。在做出完美預測的最佳情況下，抄“近道“機制可以跳過幾乎所有計算指令，這非常接近傳統(tǒng)方法的行為和執(zhí)行的效率，使得論文中提出的方法可被視為對傳統(tǒng)推測執(zhí)行技術的一種泛化。

（6）論文中提出的特化和記憶化過程本身也非常高效，可以確保在實際執(zhí)行發(fā)生之前，就及時生成好相應的“加速程序”。 

圖5：Forerunner 關鍵技術示意圖

基于以太坊的實現(xiàn)和評測

為了驗證本文的方法，研究員們將 Forerunner 具體實現(xiàn)為以太坊節(jié)點的交易執(zhí)行加速器，并測量實現(xiàn)的加速比。這個加速器能在真實的以太坊節(jié)點中穩(wěn)定運行，并且可以正確處理所有真實世界中的以太坊交易和智能合約代碼。本次實驗評估工作的亮點在于：它是在真實運行的以太坊公網(wǎng)節(jié)點中，在實時發(fā)生的區(qū)塊鏈交易上進行效果測量的。這種評估方式將技術暴露于真實的代碼和數(shù)據(jù)、真實中的“未來”不確定性，以及真實情況中能用于預執(zhí)行和其他預處理的時間約束下，這對于評估一項推測執(zhí)行技術的真實有效性至關重要。在這樣的評測中，如果本文的技術不能在實時系統(tǒng)中正確且快速地完成從預測到特化和記憶化等所有工作，那它們就不會得到任何的加速效果。

研究員們的主要評估持續(xù)了10天，包括其間真實發(fā)生在以太坊公網(wǎng)中的所有1300萬筆交易。評估結果表明，F(xiàn)orerunner 技術在所有這些交易實現(xiàn)的平均加速為6.1。值得一提的是，在以太坊實測中，因為各種原因，有大約5%的交易沒有被用于性能評測的節(jié)點提前聽到，因此研究員們完全沒有機會對它們進行任何預執(zhí)行以及后繼的加速。如果將這些未提前聽到的交易排除在計算之外，F(xiàn)orerunner 實現(xiàn)的有效平均加速比應為8.4。相比之下，傳統(tǒng)方法只能實現(xiàn)2.1的有效平均加速比。這是因為傳統(tǒng)的“單未來”方法無法應對以太坊中大量的“多未來”交易，它只能加速占比大約50%的“單未來”交易。而 Forerunner 則可以加速幾乎所有的“多未來”的交易，使得能被加速的交易占比提升到98.41%。這在本質上打破了“多未來”場景中加速比提升的“天花板”，為進一步的性能優(yōu)化打開了空間。 

總結與展望

Forerunner 提出了一種解決了“多未來”難題的有效方法，研究員們希望它能夠讓推測執(zhí)行成為高通量區(qū)塊鏈系統(tǒng)設計中的一個必備組成部分。其未來的工作將主要分為三個方面：

（1）進一步優(yōu)化 Forerunner，使其能以更低的開銷獲得更高的加速比；

（2）推動 Forerunner 在具有影響力的公鏈、聯(lián)盟鏈系統(tǒng)中落地，并發(fā)現(xiàn)和解決這個過程中進一步暴露出來的技術問題；

（3）將 Forerunner 的核心思想和帶來的啟發(fā)，推廣到推測執(zhí)行以外的更多的技術場景中，進而可以應用到區(qū)塊鏈以外的更多系統(tǒng)中。