一種面向持久化內(nèi)存的熱點變量快速寫入算法

燕保躍，姜 博

(北京航空航天大學 計算機學院 軟件開發(fā)環(huán)境國家重點實驗室，北京 100191)

1 引 言

近年來出現(xiàn)的新型非易失性內(nèi)存(No-Volatile Memory，簡稱NVM)[1,2]，具有掉電非易失、低功耗、低延遲、大容量、可字節(jié)尋址等諸多優(yōu)良特性，取得了工業(yè)界和學術(shù)界的廣泛關(guān)注[3-6].NVM旨在大幅度提升設備內(nèi)存容量以及降低設備靜態(tài)功耗的同時，提供可持久化字節(jié)尋址等特性以簡化系統(tǒng)的設計.然而，新介質(zhì)與傳統(tǒng)的DRAM在讀寫性能、I/O訪問特性等存在較大不同，從而對應用的設計帶來較大挑戰(zhàn).尤其在保證數(shù)據(jù)持久化方面，雖然CPU可以直接通過load/store指令訪問NVM[7,8]，但從CPU寄存器到NVM控制器之間的大部分數(shù)據(jù)傳輸路徑均掉電易失.用戶需要顯式使用昂貴的刷緩存指令(flush)以確保數(shù)據(jù)完整的從CPU緩存寫入到NVM設備中.另外，現(xiàn)代CPU架構(gòu)中通常采用亂序執(zhí)行等技術(shù)加速指令流執(zhí)行.為確保數(shù)據(jù)按照正確順序被持久化，用戶需要顯式使用內(nèi)存屏障指令(fence)以消除指令亂序執(zhí)行帶來的數(shù)據(jù)持久化不一致.

在降低持久化開銷方面，現(xiàn)有工作主要從批量刷新、延遲刷新等入手以減少持久化操作的次數(shù)，或者從應用角度嘗試減少上層邏輯中需要持久化的部分.然而這些方案難以應用到熱點變量(dancing variable)的寫入優(yōu)化中.熱點變量的更新涉及到頻繁刷新同一個CPU緩存行.實驗發(fā)現(xiàn)，現(xiàn)有NVM硬件體系結(jié)構(gòu)下，頻繁刷新同一個緩存行要比不同緩存行的開銷大2倍.熱點變量在實際的應用中普遍存在，如計數(shù)器、狀態(tài)機等.因此針對熱點變量的快速寫入優(yōu)化存在較大意義.

本文針對以上問題，提出了一種快速熱點變量寫入算法PDV(Persistent Dancing Variable)，其核心思想為通過對熱點變量設置多個位于不同緩存行的影子變量，在每次更新時采用輪詢策略依次選擇不同的影子變量進行更新，以確保每次更新刷新不同的緩存行.為了保證在系統(tǒng)恢復時能夠解析出最新寫入的影子變量，PDV對每個影子變量設置一個標簽域(tag)，在每次刷新影子變量同時根據(jù)當前狀態(tài)設置對應標簽域的值.本文證明，對于任意數(shù)量的影子變量，僅需2比特標簽域即可保證PDV算法總能正確的恢復.在系統(tǒng)恢復時，PDV通過掃描熱點變量所有影子變量的標簽，從而計算出最近寫入的影子變量.在Intel傲騰持久化內(nèi)存平臺的實驗結(jié)果表明，PDV算法對于熱點變量的寫入性能提升高達1.9倍.

2 背景與動機

2.1 持久化內(nèi)存

業(yè)界對于持久化內(nèi)存的研究已經(jīng)持續(xù)很多年，其最初被期望具備持久化與可字節(jié)尋址特性，用于解決DRAM的可擴展問題(scale).常見的持久化存儲介質(zhì)有相變存儲器(PCM)[9-11]、憶阻器(Memristor)[12]、自旋扭矩磁阻存儲區(qū)(STT-RAM)[13]以及可變電阻存儲器(ReRAM)[14].這類存儲器件提供與DRAM相同的字節(jié)尋址能力，但具備非易失性且相比DRAM具有更高的存儲密度以及更低的靜態(tài)功耗.2019年，Intel發(fā)布基于3DXPoint PCM存儲介質(zhì)的商用版持久化內(nèi)存傲騰DCPMM，也是第一個在服務器領(lǐng)域大規(guī)模產(chǎn)業(yè)化的持久化內(nèi)存設備.其單根PM內(nèi)存條可提供512GB的容量，而傳統(tǒng)的DRAM受限于刷新率、功耗等限制當前最大僅能提供64GB的單根容量.后文提及NVM也特指傲騰DCPMM.

當前，NVM在性能表現(xiàn)上慢于DRAM，但普遍快于傳統(tǒng)的固態(tài)盤(SSD)，因此曾被期望作為DRAM與SSD之間的持久化緩存層.大量已有文獻對于NVM的讀寫特性已有較為充分的調(diào)研[8,15-22]，本文不再詳述.圖1給出了當前NVM的主要硬件架構(gòu).和傳統(tǒng)的DRAM類似，NVM通過iMC(integrated Memory Controller)控制器連接到CPU.iMC可以配置NVM工作在兩種模式：內(nèi)存模式(memory mode)和應用直連模式(app direct).在內(nèi)存模式中，NVM僅作為更大容量的DRAM，且由iMC硬件自動接管DCPMM的使用.直連模式中，DRAM與NVM統(tǒng)一暴露給CPU接管，CPU可以直接通過load/store指令訪問NVM.另外，NVM的存儲介質(zhì)與CPU基本的數(shù)據(jù)操作操作單位并不相同，DDR控制器以64字節(jié)(一個緩存行)為單位訪問NVM內(nèi)存模組，而NVM控制器以256字節(jié)為單位(XPLine)訪問其持久化存儲介質(zhì)，因此產(chǎn)生一定的讀寫放大問題.雖然CPU以緩存行為單位刷新數(shù)據(jù)，但NVM硬件控制器當前僅能提供8字節(jié)的原子寫入.由于本文重點關(guān)注NVM的持久化特性，因此配置其工作在應用直連模式.

圖1 NVM主要硬件結(jié)構(gòu)

2.2 數(shù)據(jù)持久化

雖然NVM可以提供字節(jié)尋址的可持久化存儲，但在CPU的數(shù)據(jù)路徑中，大多的路徑依然是掉電易失的.如圖1所示，寫入路徑中，CPU中的緩存(寄存器、多級緩存等)依然是掉電易失(注：Intel于2021年Q4發(fā)布第三代Xeon處理器，其將緩存納入ADR域中，無需再顯式使用緩存刷新指令[23])，僅當數(shù)據(jù)進入到iMC控制器后才能保證數(shù)據(jù)可以正確地寫入并持久化到NVM中.Intel處理器平臺定義了ADR(Asynchronous DRAM Refresh)域(domian)的概念，保證數(shù)據(jù)進入ADR域后可以由硬件保證掉電不易失.如圖1右半部分所示，ADR域針對每一個DCPMM模組使用分別使用一個讀等待隊列(RPQ)以及寫等待隊列(WPQ)，且在寫入時以一定的時間間隔將WPQ中的數(shù)據(jù)刷入到控制器.

由于CPU的緩存是易失性的，因此用戶需要顯式使用刷緩存的指令以保證數(shù)據(jù)寫回到NVM中[24,25].當前Intel提供clflush、clflushopt用于顯式的淘汰某個緩存行并刷新到內(nèi)存中，其中clflushopt可以針對不同的緩存行并行執(zhí)行.其次，clwb指令用于刷新對應的緩存行到內(nèi)存中而不淘汰對應行的數(shù)據(jù).另外，Intel提供ntstore指令等一系列的指令用于繞過CPU緩存，而將數(shù)據(jù)直接寫入到內(nèi)存中，以旁路掉緩存的操作開銷.然而由于現(xiàn)代X86處理器的亂序執(zhí)行的高級特性，存儲指令可能會被CPU重排用于提高內(nèi)存訪問吞吐量.亂序執(zhí)行可能破壞數(shù)據(jù)存儲的一致性，因此對于存儲順序有要求的場景需要顯式通過內(nèi)存屏障指令，如sfence等，強制存儲操作按照指定的順序進行.NVM寫入性能受緩存行的數(shù)量影響較大，如圖2(a)所示.其次頻繁寫入同一個緩存行的開銷明顯大于寫入不同緩存航的開銷，如圖2(b)所示.其根本原因為寫入不同的緩存行可以通過clflushopt并行，而單個緩存行只能串行進行.

圖2 NVM寫入I/O特性

2.3 研究動機

熱點變量在應用中普遍存在，但在傳統(tǒng)的面向易失性DRAM的場景中，由于不需要保證持久化，因而不需要頻繁的刷新該變量所在的緩存行.但在可持久化NVM應用場景中，熱點變量的頻繁更新需要頻繁的調(diào)用刷新指令，因而難以避免頻繁的刷新同一個緩存行.現(xiàn)代NVM硬件體系結(jié)構(gòu)中，頻繁刷新同一個緩存行的效率明顯低于頻繁刷新不同緩存行.一個直觀的解決方案是針對熱點變量設置多個位于不同緩存行的影子變量.每次更新時選擇不同的影子變量.然而該種做法的一個較大的挑戰(zhàn)是如何在系統(tǒng)恢復時確定最近更新的影子變量.本文提出PDV算法以解決以上問題.

3 模型概述

設置多個位于不同緩存行的影子變量(下文統(tǒng)一簡稱為影子)的方法存在兩個難點.其一是每次如何選取不同的影子；其二是系統(tǒng)恢復時如何找到最近更新的影子.考慮圖3所示的3個例子.例子(a)表示每次輪詢選擇下一個影子，但不記錄任何額外的信息，該方式顯然無法在恢復時確定最新的影子.例子(b)中，每次選擇影子時均有持久化head指針記錄所選影子的編號，但由于每次寫入影子時均需要更新head指針，因此問題又被遞歸的引入.例子(c)中通過對每個影子添加一個標簽，恢復時通過掃描標簽信息計算出最近寫入的影子，進而實現(xiàn)了每次均寫入到不同的緩存行且又能夠保證恢復時確定最近寫入的影子.

圖3 訪問不同影子變量的實例圖

3.1 PDV模型

(1)

(2)

(3)

(4)

3.2 數(shù)據(jù)恢復

表1 快照集合判定的充分條件

證畢

證畢

證畢

證畢

定理1.對于n個影子的熱點變量，PDV算法總能夠正確的恢復.

證畢

3.3 最小標簽比特數(shù)

(5)

定理2.對于存在n≥2個影子的熱點變量，PDV算法中每個標簽所需的比特數(shù)與n無關(guān)，其恒為2比特.

證明：由上述分析可知，m≥2時，PDV總能正確恢復.因此每個影子標簽最小所需的比特數(shù)為k=「log22+1?=2，且與n無關(guān).

證畢

3.4 狀態(tài)機設計

圖4 PDV運行狀態(tài)機

表2 PDV狀態(tài)轉(zhuǎn)移表

4 算法實現(xiàn)

算法1.PDV數(shù)據(jù)結(jié)構(gòu)定義

1.Template

2.structPDV{

3.chari=-1; //輪詢影子選擇指示

5.chatc=0 //復用計數(shù)器

6. T*(*pdata)[N]=nulptr; //影子數(shù)組指針

/*操作接口*/

7. T getVal();

8.voidpersistVal();

9.voidrecoverFrom(T*(*p)[N]);

10. }//16 bytes in total

算法1給出了本文對于PDV的詳細實現(xiàn)的細節(jié).其中單個PDV實例運行時的內(nèi)存開銷為16字節(jié)(對齊后)，其中包括8字節(jié)的影子變量所在NVM中的數(shù)組指針(第6行).運行時，i用于指示當前選擇的影子，s表明當前的狀態(tài).由于推動PDV狀態(tài)機的4個計數(shù)器同一時刻僅有一個計數(shù)器發(fā)揮作用，因此在實現(xiàn)中可以設置一個復用計數(shù)器c為狀態(tài)計數(shù)器(第5行).PDV當前僅支持不大于8字節(jié)的基本類型，如char，short，int以及l(fā)ong類型.主要有兩個原因.1)當前NVM硬件僅能確保不大于8字節(jié)的原子寫入，因此更大的數(shù)據(jù)類型存在部分寫問題(torn write)；2)熱點變量，如計數(shù)器等，大多以基本類型為主.所有影子的最高兩位比特用于存儲標簽值，即c的最大值為2.

影子的分配在實現(xiàn)中分為兩種：稀疏布局和密集布局.稀疏布局即每個影子獨占一個緩存行，因而會導致空間浪費較嚴重.但當熱點變量較少時，空間開銷可以忽略不計，獨占緩存行實現(xiàn)更為簡單.密集布局允許不同熱點變量的影子共享緩存行.在熱點變量較多時該中方式可大幅度節(jié)省空間，但共享緩存行在一定程度上會降低性能.其本質(zhì)上是空間開銷和性能的折中考慮.在實現(xiàn)中，本文采用緩存池的方式提供不同的影子布局.

算法2.PDV數(shù)據(jù)持久化算法實現(xiàn)

1.voidPDV：：persistVal(T val){

2. i=(i+1)%N;

3.chartag=0;

4.switchsdo

8.if(c<2)then

9. c++，tag=c;

10.else

13.if(c

14. c++，tag=3;

15.else

18.if(c

19. c++，tag=0;

20.else

22. persist((*pdata)[i]，wrap(val，tag));

23. }

算法3.PDV數(shù)據(jù)恢復算法實現(xiàn)

1.voidPDV：：recoverFrom(T*(*p)[N]){

/*nb0記錄標簽值為0的數(shù)目*/

/*nbx記錄標簽值為0

/*n3記錄標簽值為3的數(shù)目*/

/*vm記錄最大的標簽值*/

2.charnb0，nbx，nb3，vm←scan(p，N);

3.if(vm==0)then

4. initPDV(); //初始化

5.elseif(nb3==0∧vm>0)then

6. i=pos_max(p，N);// 引理2

7. s=1，c=vm；

8.elseif(nb3≥1nbx>0)then

9. i=pos_leap_m(p，N);// 引理 3

10. s=2，c=nb3;

11.elseif(nb0>1∧nb_3≥1∧nbx==0)then

12. i=pos_leap_0(p，N);// 引理 4

13. s=3，c=nb0;

14.else

19. /*輸入數(shù)據(jù)不合法*/

20. pdata=p;

23. }

如算法1所示，PDV提供3個操作接口：getVal獲取當前值，persistVal更新值，recoverFrom啟動恢復.在獲取當前值時，PDV讀取當前的影子并移除2比特的標簽.在更新值時PDV通過算法2中的流程選擇下一個影子以及計算標簽值.算法2首先計算下一個影子的位置(第2行)，之后根據(jù)當前的狀態(tài)以及計數(shù)器的值確定下一個狀態(tài)值以及變遷的值(第4到21行).最后將需要更新的值與標簽值嵌合之后寫入到選擇的影子中并使用持久化指令刷入到NVM中(第22行).

在系統(tǒng)恢復時，PDV根據(jù)算法3流程掃描一個熱點變量的所有影子的標簽，并根據(jù)掃描結(jié)果計算最近的影子以及恢復當前的狀態(tài)和每個狀態(tài)對應的計數(shù)值.算法3首先統(tǒng)計當前所有影子標簽的0值個數(shù)(nb0)，中間值個數(shù)nbx，和3值個數(shù)n3以及最大值vm(第2行)，之后根據(jù)引理1判斷當前處于何種狀態(tài)并根據(jù)引理2到4中的方法分別計算最近更新的影子(第3到19行).對于不合法的輸入，PDV報告非法輸入，由上層應用處理后續(xù)情況.

5 實驗評估

本文對PDV算法進行以下3個方面的評估：不同影子數(shù)對性能的影響，不同影子布局對性能和空間的影響，多線程環(huán)境下的影響.實驗在阿里云ecs.re6p.2xlarge真實的持久化內(nèi)存實例上進行.該實例配置8個Intel Xeon Platinum 8269CY CPU核心，32GB DRAM內(nèi)存，126GB Intel傲騰持久化內(nèi)存.實例運行Linux 4.19.91內(nèi)存版本.傲騰內(nèi)存按照SNIA[27]編程模型配置為應用直連模式，其中數(shù)據(jù)的緩存刷新使用clwb指令，且每次刷新操作后均緊跟內(nèi)存屏障sfense指令.

5.1 影子數(shù)的影響

該試驗中，所有的影子均采用稀疏布局以保證不同的影子處于不同的緩存行.由于所有的影子獨占64字節(jié)緩存行，不失一般性，實驗采用4字節(jié)的int型熱點變量進行評估.緩存池大小設置為不超過CPU LLC的大小，以盡量減少數(shù)據(jù)從NVM加載到CPU緩存的影響.由于實驗主要測試寫入的延遲，實驗預先讀取所有的緩存行以保證數(shù)據(jù)均已被加載到緩存中.每次更新熱點變量時均寫入不同的值，以確保對應的緩存行處于臟寫狀態(tài)(dirty).實驗統(tǒng)計100萬次寫入的平均值，以減少噪聲的影響.

圖5表明，在64個影子的設置下，PDV對于熱點變量的寫入性能提升高達1.9倍，且在16個影子下性能已接近最優(yōu).PDV算法使得熱點變量的更新被路由到不同的緩存行中.不同緩存行的刷新可以充分利用clwb的指令流并行化特性加速.而在無影子的情況下，這些寫入均刷新同一個緩存行，導致clwb的并行化失效.其次PDV對每個影子僅引入2比特的標簽開銷，對于硬件實現(xiàn)較為友好.

圖5 不同影子數(shù)的性能表現(xiàn)

5.2 數(shù)據(jù)布局的影響

該實驗建立固定大小的緩存池，并從該緩存池中分配影子.緩存池的設計保證對單個PDV實例的所有影子均放置到不同的緩存行.但多個PDV實例的影子可能被放置在同一個緩存行以減少空間的占用.為了評估緩存池大小以及影子數(shù)量對性能的影響，實驗設置影子數(shù)固定為16，但改變緩存池大小從1個緩存行到64個緩存行.實驗設置兩種不同的緩存池，分別用于分配4字節(jié)的int型變量以及1字節(jié)的char型變量.在對多個PDV實例的寫入中，實驗每次從中隨機選擇實例寫入.

圖6中，N=1表示實驗中有一個PDV實例；size=1表示實驗中緩存池大小設置為1個緩存行；x表示緩存池無法分配足夠的影子.結(jié)果表明，在相同影子數(shù)下，隨著緩存池的增大，吞吐量顯著增加.因為大的緩存池分配影子時共享緩存行的概率更低.當size=1時，意味著所有的影子共享同一個緩存行.當size=32時，如果分配32個int型PDV實例，則意味著單個PDV實例的所有影子一定不會共享緩存行.共享緩存行是一種空間效率和時間效率的折中考慮.圖6中，對于int類型，當緩存池大小為32且PDV實例數(shù)為32時，性能表現(xiàn)為9.1Mops.然而對于稀疏布局，32個int型帶有16個影子的PDV實例性能表現(xiàn)為10.4Mops，1.14倍的性能提升卻導致32倍的空間放大.

圖6 不同緩存池與PDV實例下的性能表現(xiàn)

5.3 多線程環(huán)境

現(xiàn)代CPU體系結(jié)構(gòu)通常采用緩存一致性算法確保緩存數(shù)據(jù)在多核CPU之間的數(shù)據(jù)一致性.多核CPU在頻繁更新相同的緩存行時會出現(xiàn)性能比單核情況下更低的情況.為了評估多核情況下PDV的表現(xiàn)，實驗設置多線程環(huán)境下的兩種配置，其中每個線程使用獨立的PDV實例.配置1，所有的PDV實例的所有影子均不共享緩存行，即稀疏部署.配置2，所有PDV的實例數(shù)固定為16，允許不同PDV的實例的影子共享緩存行，即密集布局.密集布局下多線程可能存在同時更新同一個緩存行的情況.

圖7(a)中顯示了配置一的實驗結(jié)果.由于在該配置中，線程之間不共享緩存行，因此在平均每線程的吞吐量隨著實例的影子數(shù)的增加而增加.但受限于硬件的總的并行能力，隨著線程的增加，每個線程的平均吞吐量逐漸減少.另外，在多線程環(huán)境下，即使每個線程相對自己刷新不同的緩存行，但相對CPU緩存，不同線程仍然是刷新不同的緩存行，因此PDV在多線程環(huán)境下提升效果不明顯.圖7(b)中，影子之間可能存在共享緩存行，在多線程環(huán)境下，緩存池越大，平均每線程的吞吐隨著線程的增加而下降更加緩慢.當緩存池較小時，在多線程情況下性能較單線程明顯下降.多線程環(huán)境下可以通過設置線程獨立的緩存池進一步提高吞吐.

圖7 不同線程與不同影子數(shù)下的性能表現(xiàn)

6 結(jié) 論

本文指出在現(xiàn)代NVM硬件體系結(jié)構(gòu)下，熱點變量的更新導致頻繁刷新同一個緩存行，開銷較刷新不同緩存行大2倍左右.針對該問題，本文提出PDV算法，其為熱點變量設置多個位于不同緩存行的影子變量，且為每個影子變量添加一個固定大小的標簽.在每次更新熱點變量時，PDV采用輪詢策略選擇不同的影子變量以確保每次寫入不同的緩存行，同時根據(jù)當前的狀態(tài)更新其對應的標簽值，以確保在系統(tǒng)恢復時能正確的解析出最近更新的影子變量.對于任意數(shù)量的影子變量，本文證明了僅需要2比特大小的標簽即可確保PDV總能正確的恢復.鑒于標簽比特數(shù)與影子數(shù)無關(guān)，因此其對于后續(xù)硬件的實現(xiàn)較為友好.實驗結(jié)果顯示，PDV算法對于熱點變量的寫入速度提升高達1.9倍.