中國科學(xué):信息科學(xué)SCIENTIASINICAInformationis評評述非易失主存的系統(tǒng)軟件研究進展清華大學(xué)計算機科學(xué)與技術(shù)系,北京100084*通信作者.E-mail:shujw@收稿日期:2019–06–21;修回日期:2019–09–04;接受日期:2019–09–18;網(wǎng)絡(luò)出版日期:2021–05–13國家重點研發(fā)計劃(批準號:2018YFB1003301)、國家自然科學(xué)基金重點項目(批準號:61832011)和廣東省科技創(chuàng)新戰(zhàn)略專項項目(批準號:2018B010109002)資助摘要互聯(lián)網(wǎng)和物聯(lián)網(wǎng)規(guī)模的迅速擴張促使全球數(shù)據(jù)存儲總量呈現(xiàn)爆炸式的增長,導(dǎo)致數(shù)據(jù)系統(tǒng)從計算密集型向數(shù)據(jù)密集型方向發(fā)展.如何構(gòu)建可靠高效的數(shù)據(jù)存儲系統(tǒng),成為大數(shù)據(jù)時代迫切需要解決的問題.相比傳統(tǒng)磁盤,非易失主存具有性能高以及字節(jié)尋址等優(yōu)點,這些獨特的優(yōu)勢為高效存儲系統(tǒng)的構(gòu)建提供了新的機遇.然而,傳統(tǒng)存儲系統(tǒng)的構(gòu)建方式不適用于非易失主存,無法發(fā)揮出非易失主存的性能優(yōu)勢,并且容易造成一致性開銷高、空間利用率低、編程安全性低等問題.為此,本文分析了基于非易失主存構(gòu)建存儲系統(tǒng)面臨的挑戰(zhàn),在系統(tǒng)軟件層次分別綜述了空間管理機制、新型編程模型、數(shù)據(jù)結(jié)構(gòu)、文件系統(tǒng)和分布式存儲系統(tǒng)等方面的研究進展,并展望了基于非易失主存構(gòu)建存儲系統(tǒng)的未來研究方向.關(guān)鍵詞非易失主存,系統(tǒng)軟件,空間管理機制,編程模型,數(shù)據(jù)結(jié)構(gòu),文件系統(tǒng),分布式系統(tǒng)1引言互聯(lián)網(wǎng)和物聯(lián)網(wǎng)規(guī)模的迅速擴張促使全球數(shù)據(jù)存儲總量呈現(xiàn)爆炸式的增長.根據(jù)IDC公司的報告,全球數(shù)據(jù)總量正以每兩年翻一番的速度快速增長,到2020年將達到44ZB的規(guī)模[1].此外,大數(shù)據(jù)種類更加復(fù)雜多變,超過85%以上的數(shù)據(jù)將以非結(jié)構(gòu)化或者半結(jié)構(gòu)化的形式存在[2].因此,數(shù)據(jù)密集型應(yīng)用逐漸成為大數(shù)據(jù)時代的主流應(yīng)用,這對存儲系統(tǒng)的性能提出了越來越高的要求.然而,隨著多核處理器技術(shù)的快速發(fā)展,外存存儲性能的提升速度遠低于處理器性能的提升速度[3],外存存儲系統(tǒng)將難以滿足日益增長的應(yīng)用需求.因此,如何設(shè)計構(gòu)建高效可靠的數(shù)據(jù)存儲系統(tǒng),支撐應(yīng)用層越來越高的性能需求,成為了大數(shù)據(jù)時代迫切需要解決的問題.近年來,新型非易失存儲器(non-volatilememory,NVM)以高集成度、低靜態(tài)能耗、持久性和接近DRAM的性能等特性,為存儲系統(tǒng)的發(fā)展帶來巨大的機遇,吸引了研究人員的廣泛關(guān)注.目前主流引用格式:舒繼武,陳游旻,胡慶達,等.非易失主存的系統(tǒng)軟件研究進展.中國科學(xué):信息科學(xué),2021,51:869–899,doi:10.1360/SSI2019-0128ShuJW,ChenYM,HuQD,etal.Developmentofsystemsoftwareonnon-volatilemainmemory(inChinese).SciSinInform,2021,51:869–899,doi:10.1360/SSI-2019-0128?c2021《中國科學(xué)》雜志社舒繼武等:非易失主存的系統(tǒng)軟件研究進展的非易失存儲器包括相變存儲器(phasechangememory,PCM)[4]、自旋矩存儲器(spintransfertorqueRAM,STT-RAM)[5]、阻變存儲器(resistiveRAM,RRAM)[6]、賽道存儲器(racetrackmemory,RM)[7],以及Intel公司和Micron公司聯(lián)合開發(fā)了3DXPoint非易失存儲技術(shù)[8].其中,基于3DXPoint技術(shù)的PCIe接口設(shè)備已于2017年進入市場,而基于DIMM接口的OptaneDC持久性內(nèi)存也于2019年4月剛剛發(fā)布.因此,可以利用這些非易失存儲器構(gòu)建高吞吐、低延遲的大內(nèi)存存儲系統(tǒng).隨著非易失存儲器技術(shù)的進一步發(fā)展與應(yīng)用,基于該技術(shù)構(gòu)建持久性主存存儲系統(tǒng)是滿足應(yīng)用日益增長的性能需求的有效方法.然而,相比于磁盤或者閃存等傳統(tǒng)外存存儲介質(zhì),非易失主存的特性存在較大的差異,如何構(gòu)建持久性主存存儲系統(tǒng)仍然面臨諸多需要解決的難題.(1)軟件棧開銷高.非易失主存將持久性數(shù)據(jù)讀寫訪問延遲從毫秒級降至納秒級,而傳統(tǒng)存儲架構(gòu)是針對外存設(shè)計的,持久化路徑上的軟件棧開銷較高,難以發(fā)揮新型存儲器件的性能優(yōu)勢.(2)一致性開銷高.非易失主存提供主存層次的數(shù)據(jù)持久性,而處理器的片上緩存系統(tǒng)依然是易失性的,系統(tǒng)故障可能導(dǎo)致非易失主存上的持久性數(shù)據(jù)處于不一致的中間狀態(tài),而傳統(tǒng)的一致性技術(shù)往往會導(dǎo)致過高的持久化延遲,嚴重降低非易失主存系統(tǒng)的性能.(3)空間利用率低.非易失主存的價格明顯高于傳統(tǒng)外存,傳統(tǒng)主存空間管理機制容易引入主存碎片,主存碎片問題將顯著降低非易失主存的空間利用率,增加系統(tǒng)的成本.(4)編程安全性低.主存層次的數(shù)據(jù)持久性導(dǎo)致編程中引入的程序錯誤變得更加難以解決,例如野指針、多次釋放同一個對象、內(nèi)存泄露等問題,即使系統(tǒng)重啟也無法解決主存中存在的程序錯誤.綜上所述,傳統(tǒng)存儲系統(tǒng)的構(gòu)建方式不僅無法發(fā)揮出非易失主存的性能優(yōu)勢,而且易于產(chǎn)生一致性開銷過高、空間利用率過低、編程安全性過低等方面的問題.目前,基于非易失主存構(gòu)建存儲系統(tǒng)已成為學(xué)術(shù)界和工業(yè)界的熱點研究問題.本文首先介紹現(xiàn)有存儲系統(tǒng)在非易失主存的系統(tǒng)軟件設(shè)計上面臨的獨特挑戰(zhàn)和需要解決的問題,然后在此基礎(chǔ)上從非易失主存的空間管理機制、新型編程模型、數(shù)據(jù)結(jié)構(gòu)、文件系統(tǒng)和分布式存儲系統(tǒng)等5個方面詳細綜述現(xiàn)有研究工作的進展,最后展望未來的研究趨勢和方向.2非易失主存系統(tǒng)軟件設(shè)計的挑戰(zhàn)及需要解決的問題相比于傳統(tǒng)磁盤或固態(tài)硬盤,非易失內(nèi)存表現(xiàn)出完全不同的硬件特性,這促使我們重新設(shè)計新的系統(tǒng)軟件,以更好地利用其硬件屬性.本節(jié)將首先論述面向非易失內(nèi)存的系統(tǒng)軟件設(shè)計將面臨的挑戰(zhàn),然后指出系統(tǒng)軟件設(shè)計過程中需要解決的問題.2.1非易失主存的挑戰(zhàn)現(xiàn)有的存儲系統(tǒng)針對磁盤或者閃存的特性設(shè)計了大量的優(yōu)化策略.但是,字節(jié)尋址的非易失主存提供主存層次的數(shù)據(jù)持久性,可在主存層次構(gòu)建持久性存儲系統(tǒng),這對存儲系統(tǒng)的構(gòu)建方法提出了新的挑戰(zhàn),具體表現(xiàn)在:(1)軟件棧開銷.傳統(tǒng)存儲架構(gòu)、軟件及各模塊都是針對磁盤或者閃存設(shè)計的,難以發(fā)揮出新型存儲器件的性能優(yōu)勢.例如,現(xiàn)有的存儲系統(tǒng)除了維護易失性主存中的數(shù)據(jù)外,還需要將關(guān)鍵數(shù)據(jù)以不同于主存對象的組織方式(如文件格式)寫入到外存中,從而確保在程序正常結(jié)束或系統(tǒng)突然斷電時數(shù)據(jù)的持久性.然而,將數(shù)據(jù)從主存持久化到外存的過程會觸發(fā)昂貴的軟件棧延遲,例如,與外存設(shè)備進行頁交換、在(反)序列化時更改數(shù)據(jù)格式,以及觸發(fā)臃腫的系統(tǒng)調(diào)用等操作均會造成嚴重的系統(tǒng)開銷.此外,相比磁盤或者閃存,非易失主存將持久性數(shù)據(jù)讀寫訪問延遲從毫秒級降至納秒級.因此,上6期Percentage%)rddrivePCIeFlash(2007)PCIePCM(2010)PCIeFlashPercentage%)rddrivePCIeFlash(2007)PCIePCM(2010)PCIeFlash(2012)PCIePCM(2013)BBDRAM(2012)DDRNVM(2014)94.09%88.40%0%1.90%1.90%0% iteboxckboxksvicetype圖1傳統(tǒng)持久化路徑的軟件棧開銷[9]Figure1Softwarestackoverheadinthetraditionalpersistencepath[9]AMVolatilePersistentsistentsistentmoryks(a)(b)圖2易失性{持久性邊界的變化[10]Figure2Thechangeofthevolatile-persistentboundary[10].(a)Disk-basedstoragesystem;(b)NVM-basedstorageystem述的軟件開銷占比還將進一步被放大.圖1[9]對比了使用不同接口訪問不同存儲介質(zhì)時軟件棧開銷在存儲總開銷中的占比.如圖所示,在基于磁盤的傳統(tǒng)存儲系統(tǒng)中,由于訪問持久性數(shù)據(jù)的性能瓶頸在于硬盤的訪問延遲,所以軟件棧開銷占比僅為0.30%;而在基于DIMM接口的非易失主存存儲系統(tǒng)中,因為訪問持久性數(shù)據(jù)的延遲大幅降低,所以軟件系統(tǒng)的開銷比例大幅增加,軟件棧開銷占比高達94.1%.因此,基于非易失主存的存儲系統(tǒng)需要設(shè)計更加高效的軟件接口,減少軟件棧開銷.(2)一致性開銷.非易失主存同時具備接近DRAM的性能和數(shù)據(jù)持久性,消除了傳統(tǒng)易失性主存和持久性外存的邊界,從易失性主存+持久性外存的“兩級結(jié)構(gòu)”變?yōu)榱朔且资灾鞔妗皢渭壗Y(jié)構(gòu)”.這種結(jié)構(gòu)上的顛覆性變化帶來了一致性機制維護上的挑戰(zhàn).如圖2[10]所示,在基于外存的傳統(tǒng)存儲系統(tǒng)中,易失性–持久性邊界位于主存和外存之間;而在基于非易失主存的存儲系統(tǒng)中,易失性–持久性邊界位于處理器緩存和主存之間.雖然非易失主存提供了主存層次的數(shù)據(jù)持久性,然而處理器的片上存儲系統(tǒng)(例如處理器緩存)依然是易失性的,程序錯誤和電力故障都可能導(dǎo)致處理器緩存中的數(shù)據(jù)丟失,而位于非易失主存的數(shù)據(jù)可能處于未完成的中間舒繼武等:非易失主存的系統(tǒng)軟件研究進展Table1表1不同存儲器件的價格[16]Thepriceofdi?erentmemorytechnologies[16]StoragedevicePriceHDDSDBattery-backedDRAMPCM3D-XPointSTT-RAM<$0.06/GB<$0.9/GB$12/GB$28/GB$28/GBThehighest狀態(tài),從而導(dǎo)致持久性數(shù)據(jù)在系統(tǒng)重啟后出現(xiàn)不一致性的問題.因此,處理器緩存中的數(shù)據(jù)需要原子性地寫回到非易失主存.由于目前64位計算機只支持8字節(jié)數(shù)據(jù)的原子操作[11],系統(tǒng)設(shè)計者需要額外的機制保證數(shù)據(jù)的一致性[1013].然而,非易失主存往往存在讀寫不對稱的特性,寫操作會帶來更高的延遲和能耗,因此,額外引入的一致性機制往往會引入過高的持久化開銷[13].此外,在原有雙層結(jié)構(gòu)中,傳統(tǒng)存儲系統(tǒng)通過軟件的方式控制需要持久化的主存頁,系統(tǒng)性能主要由外存的數(shù)據(jù)組織及主存的數(shù)據(jù)管理決定,而處理器緩存效率對存儲系統(tǒng)影響較小.基于持久性內(nèi)存的單層存儲體系架構(gòu)下,處理器緩存是由硬件控制的,大多數(shù)現(xiàn)代處理器通過對主存寫操作進行重排序來提高系統(tǒng)性能,因此,處理器緩存效率直接影響了內(nèi)存級存儲系統(tǒng)的性能.然而,這些優(yōu)化機制可能打亂數(shù)據(jù)持久化到非易失主存的順序,導(dǎo)致持久性數(shù)據(jù)在系統(tǒng)故障時處于不一致的狀態(tài).為了解決這個問題,系統(tǒng)設(shè)計者需要通過硬件刷寫指令(如cllush,cllushopt等)[14]保證數(shù)據(jù)持久化操作的順序:這些硬件刷寫指令能確保將某個數(shù)據(jù)對應(yīng)的處理器緩存行替換到非易失主存中.然而,這些刷寫指令往往十分昂貴,可產(chǎn)生高達200ns的延遲[15].因此,如何確保處理器緩存中的數(shù)據(jù)及時有序地寫回到非易失主存,高效地保證存儲系統(tǒng)數(shù)據(jù)的一致性,成為系統(tǒng)設(shè)計者亟待解決的問題.(3)空間利用率.隨著非易失存儲器技術(shù)的進一步成熟,非易失主存不僅可以保證主存層次的數(shù)據(jù)持久性,而且可以達到高于傳統(tǒng)DRAM主存的容量.然而,非易失主存的價格依然遠高于傳統(tǒng)持久性存儲器,非易失主存的空間利用率直接決定了存儲系統(tǒng)的成本.如表1[16]所示,以PCM/3D-XPoint/STT-RAM為代表的非易失主存,它們的價格遠遠高于磁盤和閃存.然而,傳統(tǒng)的主存分配器容易產(chǎn)生主存碎片,這主要包括兩種不同類型的碎片[13]:第1種是內(nèi)部碎片,以Intel公司的PMDK[12]系統(tǒng)為例,它將任意一個主存分配操作的大小與64B的倍數(shù)對齊.如果應(yīng)用申請65B的主存,PMDK會分配給它128B,這樣就產(chǎn)生了63B的內(nèi)部碎片.第2種是外部碎片,假設(shè)應(yīng)用釋放了一系列不連續(xù)的64B主存區(qū)域,但是在這些區(qū)域周圍的區(qū)域依然在使用中,那么這些釋放的區(qū)域依舊不能作為有效空間被分配給更大的數(shù)據(jù)分配操作.當(dāng)主存分配操作的大小頻繁發(fā)生變化時,外部碎片會變得十分嚴重[17].StanfordUniversity的研究人員發(fā)現(xiàn)主存碎片可能會占用超過50%的主存空間[18].與易失性主存不同的是,非易失主存中的數(shù)據(jù)將被一直保存下去,即使系統(tǒng)重啟也無法消除已經(jīng)存在的主存碎片,所以,碎片問題在非易失主存上將會變得更加嚴重.如果缺乏有效的碎片消除機制,這將會嚴重影響非易失主存的可用性和成本.高級編程語言,例如Java或者C#,嘗試采用垃圾回收的策略減少主存碎片,但是引入了較高的對象引用分析和程序中斷成本[19].此外,非易失主存的容量和寫延遲均高于基于DRAM的傳統(tǒng)主存,所以對象引用分析和程序中斷成本將更加嚴重.(4)編程安全性.由于非易失主存在內(nèi)存層次提供了數(shù)據(jù)持久性的保證,大量傳統(tǒng)程序錯誤在非6期pmalloc/pfreeanagementFilesystempmalloc/pfreepmalloc/pfreeanagementFilesystempmalloc/pfree表2非易失主存上的指針錯誤[20]Table2Thepointererrorsonnon-volatilemainmemory[20]PointertypesYes/NoPersistentpointer!volatiledataVolatilepointer!persistentdataYesIntra-heapYesInter-heapplicationsastructuresserspaceastructuresserspaceoftwaredelDistributedstoragesystemoryanagementoryanagementKernelOperatingsystemadwriteadwritedwarersistentmemory圖3非易失主存的系統(tǒng)軟件層次Figure3Thesystemsoftwarelevelfornon-volatilemainmemory易失主存上會導(dǎo)致嚴重的問題.例如,多次釋放同一個對象、主存泄露等.更糟糕的是,任何一個系統(tǒng)崩潰會將這些程序錯誤永久性地保存下來,在系統(tǒng)重啟后依然可能導(dǎo)致系統(tǒng)出現(xiàn)崩潰,因而這些程序錯誤變得更加危險.此外,非易失主存還可能引入一些新的指針錯誤.表2[20]說明了非易失主存上可能存在的指針錯誤類型:(1)當(dāng)應(yīng)用程序使用持久性指針指向易失性數(shù)據(jù)時,系統(tǒng)重啟后易失性數(shù)據(jù)會丟失,這可能導(dǎo)致持久性指針指向一個未知的數(shù)據(jù),產(chǎn)生野指針訪問的錯誤;(2)當(dāng)應(yīng)用程序使用某個持久性堆結(jié)構(gòu)中的指針指向另一個持久性堆結(jié)構(gòu)的數(shù)據(jù)時,系統(tǒng)重啟后另一個持久性堆結(jié)構(gòu)的地址可能會發(fā)生變化,這同樣可能導(dǎo)致野指針訪問的錯誤.因此,非易失主存需要設(shè)計保證安全性的編程模型和保障機制,有效避免程序員編程過程中引入的軟件錯誤.2.2非易失主存的系統(tǒng)軟件層次需要解決的問題非易失主存的特性對現(xiàn)有存儲系統(tǒng)的構(gòu)建帶來巨大的挑戰(zhàn).近年來,基于非易失主存的系統(tǒng)軟件研究得到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注.如圖3所示,在系統(tǒng)軟件的設(shè)計上,研究者們嘗試從以下5個方面解決非易失主存帶來的挑戰(zhàn).(1)非易失主存的空間管理,主要解決3個問題:(a)支持上層應(yīng)用以用戶態(tài)的主存接口直接訪問持久性數(shù)據(jù),減小傳統(tǒng)持久化路徑上的軟件棧開銷,發(fā)揮出非易失主存良好的性能;(b)保證持久性主存分配/釋放操作的一致性,避免出現(xiàn)主存泄露和多次分配/釋放同一個地址等問題;(c)設(shè)計主存碎片處理機制,提高非易失主存的空間利用率,降低系統(tǒng)的成本.(2)非易失主存的編程模型,主要解決3個問題:(a)提供自管理的編程接口,保證程序執(zhí)行過程中程序數(shù)據(jù)的持久性和一致性,減小軟件棧開銷;(b)設(shè)計高效的事務(wù)機制,減小日志機制引入的一致舒繼武等:非易失主存的系統(tǒng)軟件研究進展性開銷;(c)設(shè)計可靠的編程模型和保障機制,減少用戶編程過程中可能引入的編程錯誤.(3)非易失主存的數(shù)據(jù)結(jié)構(gòu),主要解決一致性開銷過高的問題.索引數(shù)據(jù)結(jié)構(gòu)是影響存儲系統(tǒng)性能的關(guān)鍵模塊,然而持久性索引結(jié)構(gòu)需要保證操作的一致性,過高的一致性開銷會嚴重降低系統(tǒng)的性能,這對索引結(jié)構(gòu)的設(shè)計提出了新的挑戰(zhàn).(4)非易失主存的文件系統(tǒng),主要用于降低內(nèi)核軟件棧引入的開銷.為屏蔽不同文件系統(tǒng)的差異性,內(nèi)核引入了虛擬文件系統(tǒng)(virtualilesystem,VFS)對文件系統(tǒng)進行統(tǒng)一抽象,并提供了標(biāo)準化的訪問接口.但是,VFS維護的元數(shù)據(jù)緩存、數(shù)據(jù)頁緩存,以及厚重的軟件層嚴重影響系統(tǒng)性能.(5)非易失主存的分布式存儲系統(tǒng),主要解決傳統(tǒng)分布式系統(tǒng)軟件性能低下的問題.傳統(tǒng)分布式系統(tǒng)軟件棧厚重,數(shù)據(jù)冗余拷貝現(xiàn)象嚴重,協(xié)議復(fù)雜,且通用的分布式架構(gòu)在新硬件下難以擴展.3非易失主存的空間管理非易失主存空間管理主要涉及軟件接口設(shè)計、分配/釋放操作的一致性和主存碎片處理機制等3方面的研究工作.3.1軟件接口設(shè)計現(xiàn)有的研究工作主要通過兩種方式將非易失主存集成到傳統(tǒng)的計算機系統(tǒng)中:字節(jié)尋址的文件系統(tǒng)[21]和持久性堆結(jié)構(gòu)[1013,20,2226].字節(jié)尋址的文件系統(tǒng)通過文件目錄樹組織非易失主存空間,支持通過POSIX接口訪問非易失主存中的持久性數(shù)據(jù).這種方法可以繼承來自文件系統(tǒng)的所有功能,例如分層的命名系統(tǒng)、完善的共享保護機制和可擴展的元數(shù)據(jù)結(jié)構(gòu)等.然而,文件系統(tǒng)會引入昂貴的軟件棧開銷,包括系統(tǒng)調(diào)用、塊接口訪問開銷等.此外,文件系統(tǒng)是針對塊設(shè)備設(shè)計的,難以高效地利用處理器緩存和頁表轉(zhuǎn)換緩沖區(qū).因此,直接使用文件系統(tǒng)的方式會引入較高的軟件棧開銷,難以發(fā)揮出非易失主存性能的優(yōu)勢,并且嚴重限制主存訪問操作的靈活性,例如指針操作等.為了降低軟件棧開銷,研究人員設(shè)計了持久性堆結(jié)構(gòu).相比文件系統(tǒng),持久性堆結(jié)構(gòu)直接將非易失主存設(shè)備映射到進程地址空間中,消除了持久性數(shù)據(jù)在塊設(shè)備和虛擬主存地址之間的序列化開銷.在傳統(tǒng)易失性主存中,應(yīng)用程序通過malloc/free編程接口動態(tài)分配主存,然后通過CPUload/store指令在用戶態(tài)訪問主存數(shù)據(jù).在非易失主存中,持久性堆結(jié)構(gòu)同樣為程序員提供了諸如pmalloc/pfree的用戶態(tài)主存分配接口,為上層應(yīng)用程序提供對持久性數(shù)據(jù)的直接訪問功能.然而,與傳統(tǒng)易失性主存不同,除了提供主存分配和釋放功能,非易失主存的空間管理還承載著其他功能.(1)命名系統(tǒng)和權(quán)限管理機制.非易失主存提供主存層次的數(shù)據(jù)持久性,這要求系統(tǒng)即使在重啟后,也可以通過特定的命名規(guī)則定位到對應(yīng)的持久性數(shù)據(jù).此外,用戶可以對持久性數(shù)據(jù)進行權(quán)限管理,控制持久性數(shù)據(jù)的共享范圍.(2)易失性/持久性切換機制.非易失主存具有高于DRAM的集成度,解決了主存容量擴展性有限的問題.因此,非易失主存不僅可以作為持久性存儲用于存放持久性數(shù)據(jù),而且當(dāng)易失性主存容量不足時可以作為易失性主存用于存放易失性數(shù)據(jù).3.1.1命名系統(tǒng)和權(quán)限管理機制現(xiàn)有的研究工作主要通過以下兩個方面提供命名系統(tǒng)和共享保護機制.(1)基于原生堆的持久性堆結(jié)構(gòu).漢陽大學(xué)設(shè)計了基于原生堆的持久性堆結(jié)構(gòu)HEAPO[25].它為持久性堆結(jié)構(gòu)預(yù)留了極大的虛擬地址空間(例如32TB),并將非易失主存設(shè)備映射到這塊虛擬地址空6期ttressspaceNon-volatilemainmemoryttressspaceNon-volatilemainmemoryStartaddressFixedrootStartaddressObjectoffsetMemoryMemorymappedfilelelettObjectaddressfilestartaddressobjectoffset圖4PMDK的組織結(jié)構(gòu)Figure4ThearchitectureofPMDK間中.它利用現(xiàn)有的Linux內(nèi)存管理算法(伙伴算法)管理非易失主存空間.對于每一個分配的對象,它按照頁粒度(4KB)進行分配,并將其綁定在某個固定的進程虛擬地址上.HEAPO為每個對象分配了一個對象名,并在內(nèi)核態(tài)利用字典樹維護命名空間,在用戶態(tài)利用Hash表維護字典樹的緩存,從而實現(xiàn)了命名系統(tǒng).同樣,HEAPO為每個對象配置了訪問權(quán)限控制:任何一個進程在訪問一個對象時,都需要通過命名系統(tǒng)找到對象的位置,并檢查是否有權(quán)限訪問這個對象.(2)基于主存映射文件的持久性堆結(jié)構(gòu).雖然基于原生堆的持久性堆結(jié)構(gòu)支持命名系統(tǒng)和權(quán)限管理機制,但是4KB大小的對象分配粒度可能導(dǎo)致較低的空間利用率,并且每個新分配的對象都會引發(fā)較高的內(nèi)核態(tài)操作開銷.目前的文件系統(tǒng),例如ext4[27]和PMFS[21],支持應(yīng)用對持久性數(shù)據(jù)的直接訪問(directaccess,DAX),即避免了將持久性數(shù)據(jù)拷貝到DRAM中的額外開銷.應(yīng)用通過mmap接口,將對應(yīng)的非易失主存區(qū)域以文件的方式映射到某個特定的虛擬主存地址,然后通過用戶態(tài)的主存訪問接口訪問數(shù)據(jù),文件系統(tǒng)并不會對持久性堆結(jié)構(gòu)的性能產(chǎn)生太大的影響.在系統(tǒng)重啟后,用戶同樣將文件通過mmap接口映射到進程地址空間中,就可以繼續(xù)執(zhí)行正常的操作.通過上述方式,非易失主存利用文件系統(tǒng)提供命名系統(tǒng)和權(quán)限控制機制,簡化了持久性堆結(jié)構(gòu)的設(shè)計.目前,大量系統(tǒng)都持久性內(nèi)存開發(fā)庫(persistentmemorydevelopmentkit,PMDK)[12]是由Intel公司設(shè)計的新型編程模型(之前被命名為NVML).它利用基于主存映射文件的持久性堆結(jié)構(gòu),使程序能夠在用戶態(tài)訪問非易失主存的持久性數(shù)據(jù).圖4描述了PMDK的空間組織結(jié)構(gòu),它通過主存映射文件的方式,將一塊非易失主存映射到進程的某塊虛擬地址空間,然后在用戶態(tài)對這塊主存空間進行管理.上層應(yīng)用通過PMDK的分配接口申請相應(yīng)大小的持久性對象,并用持久性指針指向分配到的對象.因為系統(tǒng)在重啟后可能會將相同的非易失主存文件映射到不同的虛擬地址,所以PMDK中的持久性指針需要兩個變量:所在文件的ID,通過它可以找到文件映射到虛擬地址空間的起始地址;對象在文件中的偏移量.此外,PMDK在每個文件上都預(yù)留了一個固定地址的根指針.基于上述信息,系統(tǒng)在重啟后可以通過固定地址的根指針,找到其他合法對象所在的位置.舒繼武等:非易失主存的系統(tǒng)軟件研究進展3.1.2易失性/持久性切換機制當(dāng)非易失主存作為持久性存儲設(shè)備時,不論是文件系統(tǒng)還是持久性堆結(jié)構(gòu),目前的研究工作都需要依賴虛擬文件系統(tǒng)(VFS)將非易失主存映射到進程的地址空間,上層應(yīng)用可以通過主存訪問接口訪問非易失主存上的數(shù)據(jù).然而,當(dāng)易失性主存的容量不足時,非易失主存無法直接作為易失性主存使用.現(xiàn)有的工作缺乏將非易失主存切換成不同主存類型的功能,從而導(dǎo)致當(dāng)易失性主存容量不足時主存數(shù)據(jù)頻繁被交換到外存中,嚴重影響應(yīng)用程序的性能.此外,因為文件系統(tǒng)的元數(shù)據(jù)(inode或者superblock)是針對塊設(shè)備設(shè)計的.即使系統(tǒng)利用VFS構(gòu)建持久性堆結(jié)構(gòu)滿足易失性應(yīng)用的容量需求,VFS也會因為較高的處理器緩存和頁表轉(zhuǎn)換檢測緩沖區(qū)的缺失率帶來較高的軟件開銷[28].為了解決上述問題,GeorgiaInstituteofTechnology提出了pVM[28].傳統(tǒng)易失性主存是由虛擬內(nèi)存(virtualmemory,VM)管理的.pVM通過修改VM,將非易失主存抽象成為一個非一致性存儲器訪問架構(gòu)(nonuniformmemoryaccessarchitecture,NUMA)節(jié)點,實現(xiàn)了應(yīng)用透明的自動內(nèi)存容量擴展功能.因為pVM無需文件系統(tǒng)的支持,所以它保留了VM子系統(tǒng)在處理器緩存和頁表轉(zhuǎn)換檢測緩存中良好的命中率,提高了系統(tǒng)的性能.3.2分配/釋放操作的一致性非易失主存的空間管理主要包含分配和釋放操作.在系統(tǒng)執(zhí)行主存分配/釋放操作的過程中,系統(tǒng)錯誤(例如斷電或者程序崩潰)可能導(dǎo)致操作處于不一致的非法狀態(tài),從而導(dǎo)致系統(tǒng)重啟后出現(xiàn)主存泄露或者野指針訪問等錯誤.下文以分配操作為例,說明分配操作可能導(dǎo)致的一致性問題.分配操作主要包含兩個持久化操作:修改并持久化分配器的元數(shù)據(jù),用于表示這塊主存區(qū)域已經(jīng)被分配;上層應(yīng)用使用持久性指針指向分配到的主存區(qū)域,從而在系統(tǒng)重啟或崩潰后避免這塊區(qū)域丟失.非易失主存的分配操作需要保證上述兩個持久化操作的原子性,否則會導(dǎo)致內(nèi)部錯誤和外部錯誤[22].內(nèi)部錯誤指的是分配器元數(shù)據(jù)的錯誤,它可能導(dǎo)致同一個主存區(qū)域被多次分配或者某塊主存區(qū)域泄漏.外部錯誤指的是上層應(yīng)用沒有使用持久化指針指向分配到的數(shù)據(jù)區(qū)域,導(dǎo)致這塊區(qū)域泄漏或者出現(xiàn)野指針錯誤.因此,非易失主存的空間管理機制需要保證分配/釋放操作的一致性.值得注意的是,數(shù)據(jù)本身的一致性將由上層應(yīng)用來保證,這將在第4節(jié)中詳細說明.為了解決這個問題,很多研究工作提出了基于事務(wù)機制的主存分配接口,例如PMDK[12],NVMDIRECT[26],Mnemosyne[11]和NV-Heaps[20]等.它們利用事務(wù)機制保證兩個持久化操作的原子性,從而確保分配/釋放操作的一致性.然而,事務(wù)機制往往利用redo/undo日志機制保證事務(wù)的一致性.日志機制需要在修改某個數(shù)據(jù)之前,先將新/舊數(shù)據(jù)持久化到日志中,這會帶來寫放大問題,引入了昂貴的持久化開銷.因此,如何降低主存分配/釋放操作的一致性開銷,成為了一個重要的研究問題.HassoPlattnerInstitute設(shè)計了nvmmalloc分配器[24].它將分配過程分為3個步驟:預(yù)留內(nèi)存、初始化和激活發(fā)布.它將前兩個步驟從事務(wù)過程中分離,從而降低了分配操作的事務(wù)開銷.然而,nvmmalloc使用了較為復(fù)雜的主存分配接口,與傳統(tǒng)主存分配器差異較大,并且依然依賴事務(wù)機制保證分配操作的一致性,產(chǎn)生較高的一致性開銷.惠普公司設(shè)計了Makalu分配器[22].如圖5所示,它基于一個重要的假設(shè):當(dāng)堆結(jié)構(gòu)處于一致性的狀態(tài)時,所有已分配的主存區(qū)域在系統(tǒng)重啟后可以通過一組已知的持久性根對象可達,其他不可達的主存區(qū)域均為未分配的區(qū)域.基于該假設(shè),它將分配器元數(shù)據(jù)分為關(guān)鍵元數(shù)據(jù)和輔助元數(shù)據(jù).關(guān)鍵元數(shù)據(jù)代表系統(tǒng)崩潰后無法恢復(fù)的元數(shù)據(jù),例如上層應(yīng)用的持久性指針和主存超級塊的切割信息;而6期Rootnode0Rootnode1Rootnode2otnode圖5合法對象從根節(jié)點可達Figure5Thelegalobjectsarereachablefromtherootnodes輔助元數(shù)據(jù)可以通過合法的關(guān)鍵元數(shù)據(jù)進行恢復(fù),例如分配器元數(shù)據(jù)中用于記錄哪些區(qū)域被分配的位圖信息.為了減小分配操作的一致性開銷.Makalu只將關(guān)鍵元數(shù)據(jù)維持在非易失主存中,而將輔助元數(shù)據(jù)維持在易失性主存中,并在系統(tǒng)重啟時對輔助元數(shù)據(jù)進行恢復(fù).當(dāng)系統(tǒng)執(zhí)行分配/釋放操作時,它只需要確保上層應(yīng)用修改持久性指針操作的原子性,而不需要確保修改分配元數(shù)據(jù)的原子性,從而避免了分配操作的事務(wù)開銷.當(dāng)系統(tǒng)重啟時,Makalu通過存放在固定地址的根對象集合,離線掃描整個非易失主存,從而找到所有已分配的主存區(qū)域,回收尚未分配的主存區(qū)域,有效地避免了主存泄漏問題.然而,雖然Makalu降低了分配/釋放操作的一致性開銷,但是它需要在系統(tǒng)重啟時掃描整個非易失主存,不可避免地引入了較高的恢復(fù)延遲.為了降低分配操作一致性開銷的同時提高系統(tǒng)恢復(fù)的性能,TechnischeUniversit¨atDresden設(shè)計了PAllocator分配器[23].對于小于16KB的主存分配操作,PAllocator在非易失主存的固定位置預(yù)留了恢復(fù)指針,用于記錄上層應(yīng)用的持久性指針地址,從而在更新分配器元數(shù)據(jù)時無需考慮持久性指針更新操作的原子性,減少分配操作的事務(wù)開銷.在系統(tǒng)恢復(fù)時,PAllocator只需要掃描恢復(fù)指針,就可以快速恢復(fù)這部分的分配器元數(shù)據(jù).對于大于16KB的主存分配操作,PAllocator利用基于混合主存的FPTree[29],降低系統(tǒng)恢復(fù)的開銷.FPTree通過只維護部分關(guān)鍵元數(shù)據(jù)的一致性,降低了更新元數(shù)據(jù)的一致性開銷.當(dāng)系統(tǒng)重啟時,PAllocator只需要掃描很小的非易失主存空間,得到合法的關(guān)鍵元數(shù)據(jù)就可以重建FPTree,從而有效地降低了系統(tǒng)的恢復(fù)開銷.3.3主存碎片處理機制與易失性主存不同,非易失主存的數(shù)據(jù)即使在系統(tǒng)關(guān)機后也會被保留下來,而主存碎片也同樣被保留下來.如果系統(tǒng)缺乏一種有效的主存碎片處理機制,主存碎片會持續(xù)積累,嚴重降低非易失主存的空間利用率.為了減少碎片,PMDK[12]針對不同大小的主存分配操作采用了不同的分配策略.對于小于256KB的分配操作,它采用分離適配策略:使用35種不同尺寸的分配類,將每個256KB的超級塊切割成多個更小的尺寸為8字節(jié)倍數(shù)的主存塊,滿足一定區(qū)間的主存分配操作.雖然細粒度的分離適配策略在一定程度上減少了小于256KB的分配操作所產(chǎn)生的主存碎片,但是大于256KB的分配操作依然易舒繼武等:非易失主存的系統(tǒng)軟件研究進展allocatedaAddresstranslation(a)omeaddressgaddressallocatedaAddresstranslation(a)omeaddressgaddress&aUnallocatedThelogstructurednonvolatilemainmemory圖6基于日志結(jié)構(gòu)的非易失主存Figure6Thelog-structurednon-volatilemainmemory于引入較高的主存碎片.為了解決這個問題,PAllocator[23]設(shè)計了去碎片化機制:當(dāng)主存分配器的連續(xù)空間無法響應(yīng)某個分配操作時,它首先定位到目前最大的空閑區(qū)域,然后通過文件系統(tǒng)的fallocate函數(shù)合并非易失主存的空洞區(qū)域,從而減少主存碎片.然而,PAllocator只能消除頁粒度的主存碎片,無法消除更細粒度的主存碎片.為了消除更細粒度的主存碎片,清華大學(xué)提出了LSNVMM[13].如圖6所示,LSNVMM將整個非易失主存組織成一個日志結(jié)構(gòu).對于所有分配操作,它將新數(shù)據(jù)直接添加到日志末尾,而不是將主存超級塊切割成固定大小的主存塊,從而消除了大部分的內(nèi)部碎片.此外,它通過將合法數(shù)據(jù)進行遷移,回收未被使用的主存空間,將其組織成更大的連續(xù)區(qū)域,達到了消除外部碎片的目的.并且,LSNVMM的碎片清理過程不需要中斷整個系統(tǒng)的正常運行,對整個系統(tǒng)的性能影響較低.3.4小結(jié)目前主流的持久性堆結(jié)構(gòu)借助于文件系統(tǒng),有效地解決了命名系統(tǒng)和權(quán)限控制的問題.其次,研究人員通過修改操作系統(tǒng)的虛擬主存管理,實現(xiàn)了非易失主存作為易失性主存的自動容量擴展功能.再次,研究人員通過減少需要保證一致性的關(guān)鍵元數(shù)據(jù),在保證可接受的系統(tǒng)恢復(fù)延遲前提下,降低了分配/釋放操作的一致性開銷.最后,研究人員通過細粒度的主存塊切割策略或者基于日志結(jié)構(gòu)的非易失主存組織結(jié)構(gòu),提高了主存的空間利用率.4非易失主存的編程模型非易失內(nèi)存提供了單層的數(shù)據(jù)存儲架構(gòu),應(yīng)用程序可以直接在內(nèi)存級實現(xiàn)數(shù)據(jù)的持久性存儲,這種新的存儲架構(gòu)避免了傳統(tǒng)存儲系統(tǒng)中將內(nèi)存格式的數(shù)據(jù)序列化存儲到外存的過程.因此,系統(tǒng)軟件需要提供新的編程模型,幫助程序員或開發(fā)者像管理易失性內(nèi)存一樣輕松地管理非易失內(nèi)存,同時提供全面的功能支持.4.1編程接口設(shè)計在傳統(tǒng)存儲系統(tǒng)中,易失性主存中的數(shù)據(jù)需要轉(zhuǎn)換成序列化的格式后才能寫回到外存中.而在字節(jié)尋址的非易失主存中,數(shù)據(jù)可以直接持久化在主存中,無需進行格式轉(zhuǎn)換.非易失主存改變了持久6期ockManagementUIApplicationApplicationplicationapserrawdevicesMDKanagementlibraryockManagementUIApplicationApplicationplicationapserrawdevicesMDKanagementlibraryadstorenelNVDIMMdriverFilesystemEMawareesystemppingrsistentmemorydwareNVDIMMsDR圖7SINA編程模型概述Figure7SINAprogrammingmodel性數(shù)據(jù)的存儲層次,上層應(yīng)用以訪問主存的方式訪問非易失主存上的持久性數(shù)據(jù).當(dāng)數(shù)據(jù)從處理器緩存寫回到非易失主存上時,數(shù)據(jù)就已經(jīng)持久化.然而,處理器緩存是硬件控制的,它會打亂數(shù)據(jù)寫回到非易失主存的順序,破壞了數(shù)據(jù)的可恢復(fù)性.因此,非易失主存的編程模型需要設(shè)計簡單通用的編程接口,提供應(yīng)用程序自管理的持久化功能,保證持久性數(shù)據(jù)的一致性.圖7展示了幾種可能的持久性內(nèi)存設(shè)備訪問模式.更具體的描述可參考文獻[30].Linux4.3及更高的版本已經(jīng)默認包含了NVDIMM驅(qū)動,持久性內(nèi)存將以一種設(shè)備的形式出現(xiàn)在/dev/pmem*.應(yīng)用程序可以直接打開該設(shè)備,然后進行裸設(shè)備讀寫形式訪問持久性內(nèi)存空間;當(dāng)然,程序員亦可在該設(shè)備上部署傳統(tǒng)的文件系統(tǒng),然后通過文件形式訪問持久性內(nèi)存空間.值得注意的是,裸設(shè)備訪問沒有任何一致性保障,其存儲的數(shù)據(jù)有丟失、不一致的風(fēng)險,而通過傳統(tǒng)文件系統(tǒng)訪問則要忍受額外的軟件開銷,性能損耗比較嚴重.目前,更為流行的方法是通過專用的持久性內(nèi)存文件系統(tǒng)管理持久性內(nèi)存空間,或通過新型的編程模型庫對其進行管理.研究者們近年來設(shè)計了新的編程模型,例如PMDK[12],NVMDIRECT[26],Mnemosyne[11]和NV-Heaps[20]等.PMDK是目前較為流行的非易失主存編程模型,它在用戶態(tài)提供了較為全面的功能支持,為上層程序員和開發(fā)者提供了工業(yè)界認可的編程接口.直接訪問持久性內(nèi)存將引入新的編程挑戰(zhàn),PMDK正是以此為出發(fā)點,為開發(fā)人員提供了libpmem,libpmemobj,libpmemblk,libpmemlog,libvmmalloc,libpmempool,librmem等功能庫,以解決一些實際的編程問題.PMDK支持現(xiàn)有的CPU硬件指令和現(xiàn)有的C/C++語言,不需要額外的硬件指令和編程語言支持.Algorithm1PMDK’stransactionalinterfaces1:TXBEGIN(pop){2:entry(TXNEW(structhashentry);3:DRW(entry)!key(key;4:DRW(entry)!value(value;5:}TXEND.如算法1所示,PMDK還提供了基于undo日志的事務(wù)接口,上層應(yīng)用可以高效穩(wěn)健地完成非易失主存上的更新操作.程序員通過TXNEW申請一塊主存區(qū)域,并通過DRW接口找到這個指針對應(yīng)的非易失主存地址.通過基于undo日志的事務(wù)機制,PMDK能保證TXBEGIN和TXEND之間舒繼武等:非易失主存的系統(tǒng)軟件研究進展ReducingpersistenceoverheadsistenceReducingpersistenceoverheadsistenceKilnMicro13]ASPLOSDUDETMASPLOS17]KaminoTX[Eurosys’17]HOPSASPLOS17]Hardware SoftwareHardwareEpochSOSP09]ingMnemosyneASPLOSHOPSingMnemosyneASPLOSHOPSASPLOS17]LOCICCD14] EagersyncASPLOS’16] ncorderingMicroDelegatedordering[Micro’16]itrecordReducingorderingoverhead圖8一致性優(yōu)化機制分類與對比Figure8Thecomparisonofdi?erentconsistencymechanism的代碼的原子性和一致性.Intel已經(jīng)在2019年4月正式發(fā)布其基于3D-XPoint技術(shù)的持久性內(nèi)存設(shè)備OptaneDCPersistentMemory.目前,其單條容量分別達到128,256和512GB.Optane持久性內(nèi)存可以工作在內(nèi)存模式(memorymode)和應(yīng)用直訪模式(APP-directmode)兩種模式下.其中,當(dāng)配置為內(nèi)存模式時,應(yīng)用程序和操作系統(tǒng)將其構(gòu)建為易失性內(nèi)存池,這與普通的DRAM使用模式的情況完全相同.在此模式下,DRAM充當(dāng)熱點訪問數(shù)據(jù)的緩存,而OptaneDC持久性內(nèi)存則提供大容量空間,應(yīng)用程序中不需要特定的編程手段,但是在系統(tǒng)斷電時不會持久性地存儲數(shù)據(jù).該模式適用于對內(nèi)存容量需求很大,但無需將數(shù)據(jù)立即持久化的一些應(yīng)用程序,例如內(nèi)存計算框架Spark等.在應(yīng)用直訪模式下,應(yīng)用程序和操作系統(tǒng)明確知道平臺中有兩種類型的內(nèi)存,并且可以指示對哪種類型的內(nèi)存進行數(shù)據(jù)讀取.內(nèi)存數(shù)據(jù)庫等需要及時持久化數(shù)據(jù)的應(yīng)用適用于使用該模式.為更好地管理持久性內(nèi)存設(shè)備,Intel還提供了ipmctl和ndctl兩個系統(tǒng)工具,用于靈活地切換持久性內(nèi)存的工作模式以及管理名字空間.4.2編程模型的一致性優(yōu)化機制編程模型需要支持系統(tǒng)在異常掉電或失效等故障出現(xiàn)后將保存在NVM的持久性數(shù)據(jù)恢復(fù)到一致的狀態(tài).為了達到這個目的,現(xiàn)有的系統(tǒng)往往采用redo或者undo日志的策略,即在修改某個數(shù)據(jù)之前先完成這個數(shù)據(jù)備份.然而,日志機制會引入額外的持久化開銷,此外,為了避免緩存的亂序執(zhí)行導(dǎo)致的不一致問題,編程模型往往需要調(diào)用cllush等處理器指令進行強制緩存行刷新,但它們會帶來昂貴的開銷.因此,編程模型需要設(shè)計低開銷的一致性優(yōu)化機制.在一致性的優(yōu)化機制上,目前分別有從軟件、硬件的角度出發(fā),分別考慮順序性和持久性的優(yōu)化方法,總結(jié)如圖8所示.(1)順序性方面的優(yōu)化機制.順序性指的是處理器數(shù)據(jù)需要根據(jù)數(shù)據(jù)依賴關(guān)系有序地持久化到非易失主存.現(xiàn)有的編程模型依賴cllush操作保證持久化操作的順序性.然而,多個cllush操作之間存在強依賴關(guān)系,后一個cllush操作必須等待前一個cllush操作執(zhí)行完成后才能接著執(zhí)行,這就產(chǎn)生了昂貴的堵塞開銷.(2)持久性方面的優(yōu)化機制.持久性指的是處理器數(shù)據(jù)從多級易失性處理器緩存替換到非易失主存,其中可能存在冗余的持久化開銷.例如,由于非易失主存只支持8字節(jié)原子寫操作[11],任何大于6期YXYBDBRSISTXSISTDTYchpersistencyPOCHBARRIERSTOREXPOCHBARRIERSTOREDPOCHBARRIEREYFigure9sistency 1Unnecessaryconstraint 2constraint 23344NEW_STRANDSTOREBEPOCH_BARRIERSTOREXNEW_STRANDSTOREDPOCHBARRIERSTOREYEpoch和Strand的對比ThecomparisonofEpochandStrand 2 8字節(jié)的寫操作都可能由于系統(tǒng)崩潰或者斷電處于不一致的中間狀態(tài).所以現(xiàn)有系統(tǒng)往往使用日志機制保證持久化操作的原子性,引入了額外的日志持久化開銷.4.2.1順序性方面的優(yōu)化機制為了降低順序性開銷對性能的影響,大量研究工作通過在處理器緩存中以硬件的方式提供順序性的支持,從而大幅降低軟件顯式順序性的開銷.Microsoft研究院提出增加新的硬件指令:epoch指令[31].該指令要求前一個epoch的數(shù)據(jù)必須在后一個epoch到達之前持久化完成.程序員通過epoch指令將程序劃分成多個執(zhí)行單元,這種機制利用硬件保證不同的執(zhí)行單元之間遵循持久化順序約束,而每個執(zhí)行單元內(nèi)可以通過對寫操作重排序來提高性能,從而通過硬件的順序化命令降低軟件順序化的開銷.與此類似,CLC[32]同樣在處理器緩存硬件中提供順序性,同時提供給程序狀態(tài)查詢的接口.雖然epoch指令支持每個執(zhí)行單元中持久化操作的異步提交,但每個執(zhí)行單元之間依然具有很強的順序依賴關(guān)系,因此性能的提升效果較為有限.清華大學(xué)提出了放松一致性機制LOC[33].LOC將預(yù)測執(zhí)行技術(shù)引入到處理器緩存的數(shù)據(jù)持久化管理中.LOC允許持久化的數(shù)據(jù)以重排序的方式刷回非易失主存,以降低順序化引發(fā)的帶寬浪費.LOC通過對數(shù)據(jù)日志的組織以及計數(shù)式提交協(xié)議等方式提供預(yù)測失敗后的事務(wù)回退.通過上述預(yù)測持久化技術(shù),LOC顯著降低了順序化的開銷.PTM[34]也采用了類似方式擴展CPU緩存,以提供一致性保證.然而,持久化指令依然使用了一種嚴格的持久性模型,它將持久化操作間的依賴關(guān)系強制等同于寫操作間的依賴關(guān)系.這導(dǎo)致原本沒有依賴關(guān)系的持久化操作(例如不同線程針對不同地址的持久化操作所產(chǎn)生的epoch指令)依然需要串行執(zhí)行,帶來過高的順序性開銷.為了解決這個問題,UniversityofMichigan提出了Strandpersistency機制[35],設(shè)計了放松的持久性模型.如圖9所示,該模型基于程序語義將I/O依賴關(guān)系分成多個并行線程,而并行線程之間無I/O依賴關(guān)系可并行執(zhí)行.Strandpersistency通過并行方式降低依賴順序性的開銷.此外,Intel公司于2014年設(shè)計了新的擴展指令[15],通過clwb指令既避免持久化指令之間的依賴關(guān)系,又避免寫回的緩存行數(shù)據(jù)失效,從而能夠供后續(xù)訪問繼續(xù)使用,減少緩存缺失操作帶來的性能影響.當(dāng)上層應(yīng)用需要保證持久化操作的順序時,它們可以通過內(nèi)存屏障指令(例如mfence)控制持久化操作的順序.此外,Intel公司還提出廢棄PCOMMIT指令,將其使命交由支持異步DRAM刷新(asynchronousDRAMrefresh,ADR)的平臺完成,進一步降低了編程模型中所需要的持久化開銷.UniversityofMichigan基于epoch,Strand和clwb這3種指令構(gòu)建了延遲提交事務(wù)機制DCT[36].傳統(tǒng)事務(wù)機制需要在事務(wù)提交后才能釋放更新數(shù)據(jù)的鎖,而DCT嘗試在修改數(shù)據(jù)后就釋放鎖,從而降低對其他沖突事務(wù)在準備undo日志項時的阻塞延遲.前面的工作主要是在處理器高速緩存層次控舒繼武等:非易失主存的系統(tǒng)軟件研究進展制順序約束關(guān)系.UniversityofMichigan隨后提出了委托順序化機制(delegatedordering),顯示地將偏序順序約束暴露給持久性主存控制器(PMcontroller)[37].持久性主存控制器管理和控制持久性主存讀寫操作的時序,對訪存物理地址分配到具體哪一個存儲體(bank)具有充分的認識,從而可以高效發(fā)揮內(nèi)存調(diào)度過程的靈活性,有效提高非易失主存的并發(fā)訪問能力.除了硬件方面的優(yōu)化策略,UniversityofWisconsin-Madison還通過軟件途徑為非易失主存設(shè)計了持久性主存系統(tǒng)Mnemosyne[21].它提出了兩種降低順序性開銷的軟件方法:Torn-bit方法和異步檢查點方法.Torn-bit在每個64比特數(shù)據(jù)塊中利用一個比特位標(biāo)識數(shù)據(jù)是否寫入.具體做法在每次寫入之前將所分配空間的Torn-bit的比特位清除.這樣在恢復(fù)時通過該比特位即可判斷數(shù)據(jù)是否已完成持久化.異步檢查點方法通過后臺的方式異步地將檢查點數(shù)據(jù)持久化至數(shù)據(jù)原有位置.在事務(wù)空閑時間較多時,異步檢查點方法可以充分利用后臺時間,而不影響程序的正常執(zhí)行.通過Torn-bit方法和異步檢查點方法,程序的順序性開銷得以降低.4.2.2持久性方面的優(yōu)化機制研究人員同樣通過硬件和軟件兩個角度降低持久性方面的開銷.從硬件角度,數(shù)據(jù)的持久化需要從處理器緩存的不同層級(如L1,L2等)刷回到持久性主存中.因而,在其中的部分或所有層次采用非易失性存儲器可以縮短持久化路徑,降低持久化開銷.Microsoft研究院提出了全系統(tǒng)持久化技術(shù)(wholesystempersistence,WSP)[38],它將所有處理器緩存均采用了非易失存儲器,并采用后備電源方式保證了在系統(tǒng)掉電后總線上的數(shù)據(jù)傳輸.UniversityofPennsylvania提出了Kiln[39],它僅在處理器末級緩存上使用了非易失性存儲器,通過在末級緩存上提供數(shù)據(jù)新版本的持久化,降低事務(wù)中持久化的開銷.這些做法需要在處理器的緩存層次中采用非易失性存儲器,需要對處理器硬件進行改造.由于部分非易失性內(nèi)存(例如PCM)寫入操作速度與數(shù)據(jù)保持力(retention)和可靠性呈反比關(guān)系.因此,在數(shù)據(jù)保持力和可靠性要求可以放松的場景下,可以采用快速的寫入策略.利用該特性,清華大學(xué)設(shè)計了DP2[40],它針對日志和數(shù)據(jù)分別采用了不同的寫入策略.由于日志部分的保持力要求較短,因而可以在犧牲部分數(shù)據(jù)保持力的前提下采用快速寫入策略,提高日志寫操作的性能.這種做法通過寫入速度調(diào)節(jié)可降低持久化開銷,但僅適用于特定的非易失性主存器件.在軟件方面,PMDK[12]使用了基于undo日志的事務(wù)機制:任何一個更新操作都需要先將舊數(shù)據(jù)持久化到日志中,然后才能修改舊數(shù)據(jù).然而,undo日志會導(dǎo)致每一次更新操作都引發(fā)昂貴的持久化指令和額外的寫操作,帶來了較高的持久性開銷.Mnemosyne[11]提供了一個基于redo日志的輕量級持久性事務(wù)接口,它只需要在事務(wù)提交階段將新修改的數(shù)據(jù)持久化到日志中,減少了持久化操作的開銷.然而,基于redo/undo日志的事務(wù)機制仍然需要先將數(shù)據(jù)持久化到日志中,然后再將數(shù)據(jù)持久化到原數(shù)據(jù)區(qū),這導(dǎo)致后者的持久性開銷出現(xiàn)在程序執(zhí)行的關(guān)鍵路徑上.針對這個問題,清華大學(xué)設(shè)計了BPPM[10](如圖10所示).因為日志已經(jīng)保證了事務(wù)提交數(shù)據(jù)的持久性,所以將數(shù)據(jù)從日志區(qū)寫回到原數(shù)據(jù)區(qū)的過程中,數(shù)據(jù)不需要立即持久化.只有當(dāng)日志空間不足時,它才將緩存中的數(shù)據(jù)持久化到非易失主存中,從而減少了持久化操作帶來的延遲.此外,它重新組織了日志結(jié)構(gòu),可以發(fā)現(xiàn)日志中尚未提交的數(shù)據(jù),從而允許事務(wù)在執(zhí)行過程中將尚未提交的數(shù)據(jù)直接持久化到日志中,避免了在CPU緩存中維護額外數(shù)據(jù)版本所帶來的開銷.之前的事務(wù)機制為了保證一致性,總是需要先將數(shù)據(jù)額外拷貝一份放在日志中,避免持久性數(shù)據(jù)在更新過程中因為系統(tǒng)崩潰等原因而不可恢復(fù).然而,數(shù)據(jù)拷貝過程往往發(fā)生事務(wù)的關(guān)鍵路徑上,產(chǎn)生了較高的拷貝延遲.UniversityofCalifornia,SanDiego提出了Kamino-TX[41],它維護了數(shù)據(jù)的額外副本,新數(shù)據(jù)可以直接更新在原數(shù)據(jù)區(qū),避免關(guān)鍵路徑上的日志拷貝延遲.此外,它通過對象粒度的6期22ABC44115533ABCaNon-volatilemainmemory圖10BPPM架構(gòu)圖[10]Figure10ThearchitectureofBPPM[10]鎖機制實現(xiàn)了異步的數(shù)據(jù)拷貝,只有將已更新對象同步到數(shù)據(jù)副本后才釋放該對象的鎖,從而避免了后續(xù)事務(wù)對同一對象的修改操作而導(dǎo)致的系統(tǒng)不一致性問題.最后,它通過只維護頻繁訪問的對象的數(shù)據(jù)副本,有效地降低了數(shù)據(jù)副本的存儲開銷.然而,Kamino-TX依然無法避免寫放大問題帶來的能耗和耐久性問題.清華大學(xué)提出了基于日志結(jié)構(gòu)的持久性事務(wù)主存系統(tǒng)LSNVMM[13],它將整個非易失主存組織成一個日志結(jié)構(gòu).對于所有分配操作,它將新數(shù)據(jù)直接添加到日志末尾,然后修改位于易失性主存中的地址映射表,無需再將新數(shù)據(jù)寫回到原數(shù)據(jù)區(qū),從而降低了事務(wù)的持久性開銷.4.3編程安全性保障機制NV-heaps[20]是UniversityofCalifornia,SanDiego開發(fā)的輕量級持久性對象系統(tǒng).它設(shè)計了一套靈活健壯的編程模型,以消除非易失主存上編程產(chǎn)生的錯誤.首先,它定義了指針錯誤,并通過指針類型檢查避免危險的指針問題.其次,它利用基于引用計數(shù)的引用完整性檢測,實現(xiàn)了自動垃圾回收機制,避免內(nèi)存泄漏等錯誤.NV-heaps的設(shè)計思想影響了后續(xù)眾多編程模型的設(shè)計,例如PMDK[12],NVMDIRECT[26]等.雖然NV-heaps的設(shè)計思想有效地避免了非易失主存編程過程中易于產(chǎn)生的編程錯誤,但是較為復(fù)雜的編程接口帶來了糟糕的編程體驗,增加了程序員的編程負擔(dān).為了解決這個問題,橡樹嶺國家實驗室設(shè)計了基于LLVM編譯器的靜態(tài)分析技術(shù)NVL-C[42].它支持與C語言相似的編程接口,并且能自動分析持久性指針引入的程序錯誤.它還利用引用計數(shù)自動避免了內(nèi)存泄露問題.此外,它在編譯過程中自動識別無需事務(wù)機制保護的變量,從而減小了事務(wù)開銷.4.4小結(jié)目前主流的非易失主存編程模型提供了簡單通用的事務(wù)接口,以保證應(yīng)用在更新持久性數(shù)據(jù)時數(shù)據(jù)的一致性和持久性.其次,研究人員通過軟硬件協(xié)同的方式,有效地降低了一致性機制在持久性和順序性方面的開銷.最后,研究人員通過合理的編程模型和編譯器技術(shù),提高了在非易失主存上編程的安全性.舒繼武等:非易失主存的系統(tǒng)軟件研究進展5248952489CountKeyvalue7interKeyvalue582947inter圖11無序的樹節(jié)點設(shè)計[44]Figure11Theunsortedtreenodedesign[44].(a)Sorted;(b)unsorted.5非易失主存的數(shù)據(jù)結(jié)構(gòu)單個鍵值的查詢/插入/更新/刪除操作和多個鍵值的范圍查找操作都是存儲系統(tǒng)中頻繁使用的操作.B+樹[43]同時支持單值和范圍查找操作,是基于外存的存儲系統(tǒng)中廣泛使用的有序索引結(jié)構(gòu),因此,近年來很多研究工作針對B+樹的特性設(shè)計了大量優(yōu)化機制.然而,B+樹的排序和平衡操作可能在非易失主存上觸發(fā)昂貴的持久化開銷.因此,研究人員在部分場景下也針對非易失主存的特性,對其他索引結(jié)構(gòu)(如Hash表等)進行優(yōu)化.其中,Hash表執(zhí)行范圍操作時需要掃描整個索引結(jié)構(gòu),這將導(dǎo)致十分糟糕的性能,但是它在單鍵操作場景下取得了良好的性能.下文將分別介紹B+樹和其他索引結(jié)構(gòu)的優(yōu)化機制.非易失主存上的數(shù)據(jù)結(jié)構(gòu)設(shè)計需要考慮以下幾個問題:(1)讀寫不對稱優(yōu)化機制.非易失主存的寫延遲遠高于讀延遲,并且存在耐久性方面的問題.傳統(tǒng)DRAM主存不存在讀寫不對稱的問題,因此數(shù)據(jù)結(jié)構(gòu)存在大量的寫操作,例如標(biāo)準B+樹中存在頻繁的排序?qū)懖僮?這些頻繁的寫操作在NVM上帶來嚴重的性能問題和磨損問題.所以如何設(shè)計優(yōu)化非易失主存上數(shù)據(jù)結(jié)構(gòu)的更新操作,降低寫開銷是一個重要問題.(2)一致性優(yōu)化機制.傳統(tǒng)內(nèi)存DRAM不存在持久性的問題,但是非易失主存的所有更新都會被持久化下來,如果突然斷電或者系統(tǒng)崩潰,就可能將不一致的狀態(tài)保留在非易失主存中,所以非易失主存上的索引結(jié)構(gòu)需要提供一致性的保證.雖然上述研究減少了B+樹的寫操作,但是它們無法保證B+樹在發(fā)生系統(tǒng)錯誤時數(shù)據(jù)的一致性.雖然持久性事務(wù)主存系統(tǒng)為應(yīng)用程序提供了一個通用性的一致性編程接口,但是基于日志的事務(wù)機制會引發(fā)額外的持久化開銷.如何設(shè)計優(yōu)化非易失主存上數(shù)據(jù)結(jié)構(gòu)的一致性保證機制,成為一個十分重要的研究問題.5.1讀寫不對稱優(yōu)化機制Intel和Microsoft公司提出了一種PCM友好的B+樹[44].他們發(fā)現(xiàn)因為PCM讀寫不對稱性的特點,B+樹的插入/刪除操作引發(fā)的排序操作會帶來昂貴的寫開銷,導(dǎo)致性能遠低于查詢操作.因此,如圖11所示,他們使用無序的樹節(jié)點結(jié)構(gòu),避免了插入和刪除操作中排序操作引入的持久化開銷,但是也增加了查詢操作的延遲.UniversityofPennsylvania發(fā)現(xiàn)無序的樹節(jié)點在分裂時會引發(fā)昂貴的排序操作[45].為了解決這個問題,他們提出了部分平衡的無序節(jié)點模式(sub-balancedunsortednodescheme):分裂操作以O(shè)(n)的時間復(fù)雜度找到中間那個鍵值對,然后分別將小于它的鍵值對和大于它的鍵值對移動到不同的分裂節(jié)點,從而避免了分裂操作帶來的排序開銷.另外,他們推遲了分裂操作對父節(jié)點的更新,將多個父節(jié)點的更新操作進行聚集后統(tǒng)一處理.PathHash[46]是華中科技大學(xué)針對非易失主存設(shè)計的新型持久性Hash表.他們發(fā)現(xiàn)現(xiàn)有的Hash沖突的處理制在非易失主存中會產(chǎn)生大量寫操作.因此,它設(shè)計了路徑Hash,通過位置共享技術(shù)(po-6期sitionsharing)避免了大量的Hash沖突,并且不會產(chǎn)生額外的寫操作.此外,它通過雙路徑Hash和路徑放縮技術(shù)優(yōu)化了Hash表的空間利用率和操作延遲.5.2數(shù)據(jù)結(jié)構(gòu)的一致性優(yōu)化機制針對B+樹的特點,研究人員通過系統(tǒng)提供的持久化原語,設(shè)計了更加精細的一致性更新策略.CDDS-Tree[47]是惠普實驗室針對非易失主存設(shè)計的一致性B+樹.它為每個數(shù)據(jù)項分配了一個版本號區(qū)間.更新操作為每個更新的數(shù)據(jù)項生成一個新的版本,并將其插入到樹節(jié)點的合適位置.針對刪除操作,CDDS-Tree通過版本號的設(shè)置便可輕松完成,且整個過程不影響舊數(shù)據(jù)項.在適當(dāng)?shù)臅r機,CDDS-Tree才會回收這些舊數(shù)據(jù)項,從而保證它在發(fā)生系統(tǒng)錯誤時能找到正確的數(shù)據(jù)版本.然而,基于版本號的一致性更新機制會引發(fā)嚴重的寫放大問題.因此,后續(xù)很多工作嘗試從不同方面減少B+樹的一致性開銷.中國科學(xué)院設(shè)計了wB+Tree[48].它同樣采用無序的樹節(jié)點,避免了排序操作帶來的一致性開銷.對于普通的插入/更新/刪除操作,它利用bitmap來保證它們的一致性.對于復(fù)雜的平衡操作,它利用日志機制來保證索引結(jié)構(gòu)在更新過程中一直有一個正確的數(shù)據(jù)版本.另外,wB+Tree還設(shè)計了間接排序的slot數(shù)組,支持在無序的樹節(jié)點上執(zhí)行二分查找操作.但是,維護日志和bitmap/slot數(shù)組會引入額外的持久化開銷.NV-Tree[49]是NanyangTechnologicalUniversity設(shè)計的保證局部一致性的B+樹.NV-Tree只保證葉節(jié)點的一致性,這是因為內(nèi)部節(jié)點只是用于加速葉節(jié)點的查找性能,它在系統(tǒng)崩潰時完全可以基于葉節(jié)點進行重構(gòu).所以,該方法降低了整個索引結(jié)構(gòu)的一致性開銷.它同樣采用了無序的葉節(jié)點,但是葉節(jié)點的查詢操作需要線性掃描整個節(jié)點的所有鍵值對.最后,它將所有內(nèi)部節(jié)點維護在一個連續(xù)的主存區(qū)域,提高了NV-Tree的空間局部性.然而,當(dāng)內(nèi)部節(jié)點數(shù)量溢出時,這會引入額外的重建開銷.FPTree[29]是TechnischeUniversit¨atDresden針對混合主存設(shè)計的B+樹.它將葉子結(jié)點存放在NVM上,內(nèi)部節(jié)點存放在DRAM上,避免了內(nèi)部節(jié)點的持久化開銷.此外,它為葉節(jié)點上每個無序的鍵值對配置了一個單字節(jié)的Hash項.在查找過程中,只有目標(biāo)值的Hash值與鍵值對的Hash值相同時,它才會訪問對應(yīng)的鍵值對,從而降低了葉子結(jié)點的順序查找開銷.FAST+FAIR[50]是蔚山國立科技大學(xué)設(shè)計的可容忍臨時不一致性的B+樹.它通過控制更新操作的持久化順序,實現(xiàn)了即使在系統(tǒng)崩潰后也能確保樹節(jié)點也處于一種可識別的不一致性狀態(tài),并通過這一技術(shù)避免了排序和平衡操作的日志開銷.此外,因為寫操作導(dǎo)致的樹節(jié)點不一致狀態(tài)是可以識別的,所以它還設(shè)計了lock-free的查找操作,避免了查找操作的鎖開銷.WORT[51]是蔚山國立科技大學(xué)設(shè)計的持久性基數(shù)樹.它是一種確定性的樹結(jié)構(gòu),不會引發(fā)排序和平衡操作的持久性開銷.它的所有操作都是原子性的,不會因為日志機制而產(chǎn)生過高的持久性開銷.此外,它通過保證一致性的路徑壓縮技術(shù),提升了基數(shù)樹的空間利用率.5.3其他優(yōu)化機制Hash表動態(tài)擴容.將Hash表應(yīng)用于非易失性內(nèi)存面臨的另一個挑戰(zhàn)是動態(tài)調(diào)整大小時開銷很大.隨著負載因子的增大,為了保證訪問性能和減少沖突,Hash表需要調(diào)整大小.傳統(tǒng)的方法一般需要分配一個大小為舊表兩倍的空間的新Hash表,然后把所有的鍵值對都重新Hash到新表中.這會造成大量的寫入操作,影響性能并增加非易失性內(nèi)存的磨損.Level-Hashing[52]是華中科技大學(xué)針對非易失主存設(shè)計的可動態(tài)擴容的持久性Hash表.該系統(tǒng)巧妙地提出了一種分層的Hash表方案,從而舒繼武等:非易失主存的系統(tǒng)軟件研究進展tupdatedeletetupdatedeletedeleteshtableBshtableeyvaluerecords圖12HiKV結(jié)構(gòu)[53]Figure12ThearchitectureofHiKV[53]實現(xiàn)了原地擴容,大大降低了額外的寫入操作.索引效率.HiKV[53]是中國科學(xué)院設(shè)計的一種混合索引結(jié)構(gòu).如圖12所示,它將B+樹存儲在DRAM上,Hash表存儲在NVM上.它利用持久性Hash表支持索引結(jié)構(gòu)的單鍵操作,從而顯著降低了持久性B+樹的寫開銷.因為Hash表是無序的,所以HiKV利用易失性B+樹支持范圍操作.然而在執(zhí)行范圍操作前,它需要堵塞后續(xù)的更新操作直到B+樹與Hash表具有相同的狀態(tài).因此,在那些具有較多更新操作和范圍操作的工作負載中,HiKV的性能可能會有所下降.5.4小結(jié)因為B+樹有效地支持單值和范圍操作,所以它被廣泛使用在傳統(tǒng)存儲系統(tǒng).研究人員針對非易失主存的特性,通過避免排序操作,有效地減少了傳統(tǒng)B+樹的持久化開銷.此外,它們通過選擇一致性或者控制持久化的順序等方式,降低了一致性開銷.因為B+樹的排序和平衡操作會引入較高的持久化開銷,研究人員在部分場景下也針對其他索引結(jié)構(gòu)做了大量優(yōu)化.6非易失主存的文件系統(tǒng)文件系統(tǒng)是操作系統(tǒng)中最基礎(chǔ)的模塊,它將設(shè)備存儲空間以文件的形式組織為可索引的文件目錄樹,從而方便用戶存取數(shù)據(jù).為兼容現(xiàn)有的應(yīng)用程序,將非易失內(nèi)存組織成文件系統(tǒng)是十分便捷的途徑.一種簡單的方法是直接使用現(xiàn)有的外存文件系統(tǒng)管理非易失內(nèi)存空間.例如,通過RamDisk將持久性內(nèi)存模擬成塊設(shè)備,從而兼容現(xiàn)有的外存文件系統(tǒng)(如Ext4,XFS,BtrFS等).通過這種方法,傳統(tǒng)文件系統(tǒng)無需作出任何修改,可直接構(gòu)建在非易失內(nèi)存模擬的RamDisk塊設(shè)備之上.RamDisk形式的傳統(tǒng)文件系統(tǒng)構(gòu)建方案