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

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

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

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

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

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

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

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

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

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

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

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

思路：“跨未來”加速

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

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

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

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

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

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

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

圖4：CD-Equivalence 示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)與展望

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

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

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

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