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

在近日舉行的系統(tǒng)領(lǐng)域全球頂會(huì) SOSP 2021 上，微軟亞洲研究院的研究員們?cè)谡撐摹癋orerunner: Constraint-Based Speculative Execution for Ethereum”中，提出了一種全新的、基于約束（constraints）的推測(cè)執(zhí)行（speculative execution）技術(shù)——Forerunner。這是首個(gè)面向“多未來(lái)”的推測(cè)執(zhí)行技術(shù)，其技術(shù)特點(diǎn)是把利用預(yù)執(zhí)行（pre-execution）來(lái)加速實(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ū)塊鏈中，以嘗試對(duì)位于其系統(tǒng)核心的交易（transaction）執(zhí)行環(huán)節(jié)進(jìn)行加速。為了在最真實(shí)的場(chǎng)景下對(duì)技術(shù)效果進(jìn)行評(píng)估，其中所有實(shí)驗(yàn)都是基于以太坊公鏈上實(shí)時(shí)產(chǎn)生的真實(shí)交易和區(qū)塊（block）進(jìn)行的。評(píng)估結(jié)果表明：經(jīng)過(guò)泛化的推測(cè)執(zhí)行技術(shù)能在真實(shí)系統(tǒng)中取得了可觀的性能收益。這種對(duì)交易執(zhí)行的加速能力可以用來(lái)提高以太坊核心層交易吞吐量。其主要的性能結(jié)果已經(jīng)在 SOSP 的 Artifact Evaluation 中得到了獨(dú)立的復(fù)現(xiàn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4：CD-Equivalence 示意圖

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

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

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

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

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

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

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

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

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

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

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

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

研究員們的主要評(píng)估持續(xù)了10天，包括其間真實(shí)發(fā)生在以太坊公網(wǎng)中的所有1300萬(wàn)筆交易。評(píng)估結(jié)果表明，F(xiàn)orerunner 技術(shù)在所有這些交易實(shí)現(xiàn)的平均加速為6.1。值得一提的是，在以太坊實(shí)測(cè)中，因?yàn)楦鞣N原因，有大約5%的交易沒(méi)有被用于性能評(píng)測(cè)的節(jié)點(diǎn)提前聽到，因此研究員們完全沒(méi)有機(jī)會(huì)對(duì)它們進(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)的“單未來(lái)”方法無(wú)法應(yīng)對(duì)以太坊中大量的“多未來(lái)”交易，它只能加速占比大約50%的“單未來(lái)”交易。而 Forerunner 則可以加速幾乎所有的“多未來(lái)”的交易，使得能被加速的交易占比提升到98.41%。這在本質(zhì)上打破了“多未來(lái)”場(chǎng)景中加速比提升的“天花板”，為進(jìn)一步的性能優(yōu)化打開了空間。 

總結(jié)與展望

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

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

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

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