Forerunner：首個(gè)面向“多未來(lái)”的推測執行技術(shù)

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

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

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

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

下面讓我們來(lái)一起了解一下推測執行技術(shù)以及 Forerunner 的原理。

基礎：“推測執行” 

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

圖1：推測執行示意圖

問(wèn)題：“多未來(lái)”推測執行

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

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

思路：“跨未來(lái)”加速

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

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

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

“未來(lái)“間的連結：控制/數據-等價(jià)性

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

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

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

圖4：CD-Equivalence 示意圖

關(guān)鍵技術(shù)：多指令序列的程序特化和記憶化

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

Forerunner的關(guān)鍵技術(shù)有以下幾個(gè)亮點(diǎn)：

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

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

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

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

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

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

圖5：Forerunner 關(guān)鍵技術(shù)示意圖

基于以太坊的實(shí)現和評測

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

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

總結與展望

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

（1）進(jìn)一步優(yōu)化 Forerunner，使其能以更低的開(kāi)銷(xiāo)獲得更高的加速比；

（2）推動(dòng) Forerunner 在具有影響力的公鏈、聯(lián)盟鏈系統中落地，并發(fā)現和解決這個(gè)過(guò)程中進(jìn)一步暴露出來(lái)的技術(shù)問(wèn)題；

（3）將 Forerunner 的核心思想和帶來(lái)的啟發(fā)，推廣到推測執行以外的更多的技術(shù)場(chǎng)景中，進(jìn)而可以應用到區塊鏈以外的更多系統中。