面向非易失內(nèi)存的數(shù)據(jù)一致性研究綜述

肖仁智 馮 丹, 胡燏翀 張曉祎 程良鋒

1(華中科技大學(xué)武漢光電國(guó)家研究中心 武漢 430074)2(華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 武漢 430074)3(深圳華中科技大學(xué)研究院 廣東深圳 518061)

隨著新型非易失內(nèi)存技術(shù)的發(fā)展，涌現(xiàn)出了眾多的非易失內(nèi)存存儲(chǔ)器，如相變內(nèi)存PCM[1]、自旋轉(zhuǎn)移力矩磁隨機(jī)存取存儲(chǔ)器STT-MRAM[2]、電阻式隨機(jī)存儲(chǔ)器ReRAM[3]以及憶阻器(memristor)[4]等，這些非易失內(nèi)存(non-volatile memory， NVM)以其非易失、低靜態(tài)功耗、高密度、字節(jié)尋址以及就地更新等特性受到了學(xué)術(shù)界和工業(yè)界的廣泛研究.NVM也被稱作存儲(chǔ)級(jí)內(nèi)存(storage-class memory， SCM)、持久內(nèi)存(persistent memory， PM)或非易失隨機(jī)訪問(wèn)內(nèi)存(non-volatile random access memory, NVRAM)，本文統(tǒng)一稱為NVM.由于這些優(yōu)良特性，NVM可以連接到內(nèi)存總線上，應(yīng)用程序可以通過(guò)loadstore指令來(lái)訪問(wèn)NVM上的數(shù)據(jù).因此,在未來(lái)的計(jì)算機(jī)系統(tǒng)中，采用NVM技術(shù)代替DRAM作主存或NVM與DRAM共同作為主存，這已被廣泛地討論并研究[5-15].如圖1所示，NVM構(gòu)建主存主要有3種類型[16]：僅NVM的單層主存、NVM和DRAM的混合主存以及DRAM作為NVM的緩存.NVM最獨(dú)特的特性是非易失性，即寫到NVM的數(shù)據(jù)在斷電時(shí)不丟失.之前的工作如BPFS[17]，PMFS[18]，NV-heaps[19]，Mnemosyne[20]，Quartz[21]等，假定NVM能夠保證8 B的原子寫，NVM的更新粒度為緩存行大小，通常為64 B.當(dāng)前的處理器架構(gòu)沒(méi)有提供有序的內(nèi)存寫原語(yǔ)[8].由于CPU緩存的易失性和NVM之間更新粒度不匹配，并且當(dāng)前處理器或內(nèi)存控制器可能重排序內(nèi)存寫以便進(jìn)一步優(yōu)化程序性能，所以當(dāng)系統(tǒng)故障時(shí)的部分更新可能導(dǎo)致不一致性情況的發(fā)生.因此NVM系統(tǒng)面臨的最棘手的問(wèn)題之一是數(shù)據(jù)一致性[22]，即系統(tǒng)在意外崩潰或斷電重啟之后數(shù)據(jù)的正確性.

Fig. 1 NVM builds three architectures ofmain memory[16]圖1 NVM構(gòu)建主存的3種結(jié)構(gòu)[16]

非易失內(nèi)存中數(shù)據(jù)一致性問(wèn)題已被廣泛地研究[8-14,17-18,23-28].由于NVM具有非易失特性，在系統(tǒng)故障時(shí)，保證易失性的CPU緩存和非易失內(nèi)存之間的數(shù)據(jù)一致性是必須的.NVM的一致性基本需求是確保內(nèi)存寫的持久性和順序性.然而，當(dāng)前處理器沒(méi)有保證有序的內(nèi)存寫操作原語(yǔ)，只提供了緩存行刷新(CLFLUSH)和內(nèi)存柵欄(MFENCE)指令.緩存行刷新指令CLFLUSH功能：給定一個(gè)內(nèi)存地址，CLFLUSH指令使得包含該內(nèi)存地址的緩存行失效，并且在系統(tǒng)中進(jìn)行廣播到所有的CPU核中；如果特定的緩存行是臟的，它將在失效前寫回內(nèi)存.內(nèi)存柵欄MFENCE功能：MFENCE指令保證在程序順序中的MFENCE之前發(fā)出的所有內(nèi)存讀取和內(nèi)存寫入比在MFENCE指令之后的任何讀取或?qū)懭胫白優(yōu)槿挚梢?即優(yōu)先寫入到非易失內(nèi)存中).但是，僅靠MFENCE指令不會(huì)寫回任何臟的緩存行.多個(gè)CLFLUSH指令可能并行執(zhí)行.然而，臟緩存行(dirty cache lines)可能以任意順序?qū)懟?為了確保2個(gè)臟緩存行的寫回順序，需要MFENCE指令來(lái)使得CLFLUSH刷新有序.因此，可以在CLFLUSH指令之間插入MFENCE指令以便確保臟的緩存行寫回順序[9].

然而，CLFLUSH和MFENCE的指令的序列化操作導(dǎo)致了大的開銷.另一個(gè)重要的方面是維持一致性的寫大小，假設(shè)NVM的故障原子寫(failure-atomic write)粒度為8 B，寫粒度小于8 B的更新，可以直接應(yīng)用原子8 B寫；但是當(dāng)NVM寫單元大于8 B時(shí)，需要依賴于傳統(tǒng)方法如日志或?qū)憰r(shí)拷貝(copy-on-write， COW)等機(jī)制維持?jǐn)?shù)據(jù)一致性.然而，日志或?qū)憰r(shí)拷貝(COW)機(jī)制存在雙倍寫問(wèn)題，這增加了緩存行刷新的開銷和大量的NVM寫操作[21].因此，我們需要在保證一致性的前提下盡量減少維護(hù)NVM中數(shù)據(jù)一致性帶來(lái)的開銷.

表1列舉了DRAM和3種新型非易失內(nèi)存器件的主要指標(biāo).從表1可以看出，NVM技術(shù)如PCM在密度和讀速度方面具有很好的優(yōu)勢(shì).然而非易失內(nèi)存NVM具有2方面局限性：1)有限的寫耐久性，比如PCM的寫耐久性為108～109擦除次數(shù)[29],在反復(fù)寫同一個(gè)存儲(chǔ)單元情況下，存儲(chǔ)器會(huì)很快失效；2)讀寫不對(duì)稱性，比如PCM寫延遲大于DRAM，PCM的寫延遲大約是DRAM的2～15倍,而讀延遲是DRAM的2～6倍[29].因此，除了減少NVM一致性開銷，還需要盡可能減少NVM的有限的寫入耐久性和讀寫不對(duì)稱的影響[5-7,30-31]，從而提高NVM系統(tǒng)的壽命和性能.

Table 1 Comparison of Features Between New Non-volatile Memory and Traditional Memory Devices[29]表1 新型非易失內(nèi)存與傳統(tǒng)易失性內(nèi)存器件的特征比較[29]

近年來(lái)，保證NVM數(shù)據(jù)一致性成為了NVM的研究熱點(diǎn)，無(wú)論是從基于NVM的持久索引、文件系統(tǒng)還是從持久性事務(wù)等方面均存在數(shù)據(jù)一致性問(wèn)題，并且已經(jīng)得到不少的研究和關(guān)注.鑒于PCM技術(shù)最成熟、容量也最大，而ReRAM實(shí)際容量小且處于實(shí)驗(yàn)室階段，因此，本文的主要關(guān)注點(diǎn)是如何使得基于以PCM為主的NVM系統(tǒng)面臨故障時(shí)，確保數(shù)據(jù)一致性的同時(shí)盡可能降低一致性維護(hù)帶來(lái)的額外開銷.

1 基于NVM的內(nèi)存索引的數(shù)據(jù)一致性研究

近年來(lái)，基于NVM的內(nèi)存索引的數(shù)據(jù)一致性工作得到了廣泛的關(guān)注和研究.B+Tree以及變體由于高效的范圍掃描操作和相對(duì)好的對(duì)數(shù)級(jí)查詢能力被廣泛應(yīng)用[9,11,15]，而散列索引[23-25,32-37]因?yàn)槌Ａ考?jí)的查詢時(shí)間而被廣泛應(yīng)用，基數(shù)樹[13,38]和紅黑樹[14]等樹結(jié)構(gòu)與NVM的結(jié)合也引發(fā)了關(guān)注和研究，不同內(nèi)存索引的混合以便充分發(fā)揮各自索引的優(yōu)勢(shì)而屏蔽各自索引的劣勢(shì)，比如HiKV[26]的數(shù)據(jù)一致性研究.接下來(lái)從Tree索引、散列索引以及混合索引等方面分別介紹相關(guān)的數(shù)據(jù)一致性工作.

1.1 基于Tree索引結(jié)構(gòu)的一致性研究

NVM和Tree索引結(jié)構(gòu)相結(jié)合的持久索引的一致性研究得到了廣泛關(guān)注[8-14].然而以PCM為主NVM具有有限的寫耐久性和讀寫不對(duì)稱性，在保證基于NVM的Tree索引結(jié)構(gòu)如B-Tree或B+Tree及其變體[8-12]、基數(shù)樹[13]以及紅黑樹[14]等的數(shù)據(jù)一致性的基本前提下，減少一致性開銷的同時(shí)需要盡量避免NVM寫以便延長(zhǎng)NVM壽命和提高索引結(jié)構(gòu)的整體讀寫性能.

針對(duì)當(dāng)前處理器或內(nèi)存控制器能夠重排序?qū)懖⑶姨幚砥鞑荒芴峁┯行虻膬?nèi)存寫原語(yǔ)操作問(wèn)題，伊利諾伊大學(xué)Venkataraman等人[8]提出了基于NVM的一致且持久的B-Tree變體CDDS B-Tree，它通過(guò)采用64 b無(wú)符號(hào)整數(shù)的版本化機(jī)制，當(dāng)CDDS B-Tree的一個(gè)樹節(jié)點(diǎn)更新時(shí)，它創(chuàng)建了更新條目的一個(gè)有版本信息的副本而不是原地重寫該條目，這保證了可恢復(fù)性和一致性.通過(guò)8 B原子更新而無(wú)需日志或?qū)憰r(shí)拷貝操作實(shí)現(xiàn)一致性保障.CDDS B-Tree的節(jié)點(diǎn)條目保持有序性以便支持折半查找提高讀性能.然而，有序的節(jié)點(diǎn)在插入或刪除階段帶來(lái)了許多條目移動(dòng)開銷，這導(dǎo)致了許多額外的NVM寫，從而降低了NVM的壽命.插入或刪除過(guò)程也遭受了許多死節(jié)點(diǎn)和死條目的影響.由于CDDS B-Tree調(diào)用了昂貴的MFENCE和CLFLUSH指令數(shù)量同節(jié)點(diǎn)內(nèi)需要重排序的條目數(shù)量相等，因此CDDS B-Tree的插入和搜索性能相對(duì)較差.最后需要注意的是CDDS B -Tree中的B -Tree指代的是將值僅存儲(chǔ)在葉子節(jié)點(diǎn)中的B+Tree.

針對(duì)撤銷-重做日志和影子技術(shù)確保一致性帶來(lái)的雙倍寫問(wèn)題，中國(guó)科學(xué)院計(jì)算技術(shù)研究所的Chen等人[9]在先前PCM友好的B+Trees的數(shù)據(jù)庫(kù)算法工作[16]基礎(chǔ)上，進(jìn)一步提出了基于NVM寫原子的B+Trees變體wB+-Trees，它通過(guò)bitmap的原子更新來(lái)提交絕大部分的改變，除了有時(shí)候當(dāng)葉子節(jié)點(diǎn)分裂時(shí)需要使用重做日志機(jī)制確保一致性，采用了僅追加更新的策略.wB+-Trees通過(guò)采用葉子節(jié)點(diǎn)條目的無(wú)序性來(lái)減少插入過(guò)程中寫次數(shù)，而刪除過(guò)程僅僅更新bitmap區(qū)域.為了確保好的搜索性能，wB+-Trees工作通過(guò)添加slot array來(lái)維持節(jié)點(diǎn)中索引條目的有序性，帶有slot array的非葉子節(jié)點(diǎn)支持折半查找，從而能夠提供O(logn)的查找性能.slot array存儲(chǔ)了鍵的有序索引，由于索引比實(shí)際的鍵和指針都小，幾個(gè)鍵索引可以通過(guò)8 B的原子寫操作進(jìn)行原子更新.wB+-Trees提出使用8 B的bitmap來(lái)更新節(jié)點(diǎn)容量，當(dāng)使用了bitmap時(shí)，wB+-Trees需要至少使用4個(gè)緩存行刷新，如果采用了slot array，那么緩存行的刷新數(shù)量可以降到2個(gè).雖然相對(duì)于CDDS B-Tree的緩存行刷新數(shù)急劇下降，但是B+tree帶來(lái)了間接開銷.然而，當(dāng)葉子節(jié)點(diǎn)分裂操作時(shí)依舊需要昂貴的日志機(jī)制或?qū)憰r(shí)拷貝來(lái)確保一致性，這帶來(lái)額外的NVM寫開銷.

針對(duì)CPU和內(nèi)存控制器可能會(huì)重排序內(nèi)存寫以及MFENCE&CLFLUSH指令帶來(lái)的顯著開銷等問(wèn)題，新加坡數(shù)據(jù)存儲(chǔ)研究所A-STAR的Yang等人[10]提出了基于NVM的一致且緩存優(yōu)化的B+Tree變體NV-Tree，它通過(guò)采用僅追加寫策略減少了昂貴的MFENCE和CLFLUSH指令數(shù)量.NV-Tree通過(guò)選擇執(zhí)行數(shù)據(jù)一致性來(lái)減少一致性開銷，即通過(guò)維持存放于NVM中的葉子節(jié)點(diǎn)等關(guān)鍵數(shù)據(jù)(critical data)的一致性保障，而對(duì)存放于DRAM中的中間節(jié)點(diǎn)(IN)的可重構(gòu)數(shù)據(jù)(reconstructable data)無(wú)需做一致性保證，因?yàn)閮?nèi)部節(jié)點(diǎn)可以通過(guò)一致性的葉子節(jié)點(diǎn)(LN)來(lái)重構(gòu).由于追加更新葉子節(jié)點(diǎn)策略以及只有葉子節(jié)點(diǎn)保存在NVM中，NV-Tree只需要2個(gè)緩存行刷新，其中一個(gè)用于條目(entry)更新，另一個(gè)用于條目數(shù)(nElements)的更新，結(jié)果性能得到了提升.同時(shí)也帶來(lái)了2個(gè)問(wèn)題：1)葉子節(jié)點(diǎn)依舊保持無(wú)序;2)內(nèi)部節(jié)點(diǎn)在系統(tǒng)故障時(shí)可能會(huì)丟失.通過(guò)保持葉子節(jié)點(diǎn)條目的無(wú)序性并進(jìn)行原子性的更新，而對(duì)內(nèi)部節(jié)點(diǎn)保持有序能夠支持好的搜索性能.最后是對(duì)內(nèi)部節(jié)點(diǎn)以緩存優(yōu)化的組織方式來(lái)提高緩存局部性，即具體采用連續(xù)的內(nèi)存空間，通過(guò)偏移(offset)而非指針來(lái)定位內(nèi)部節(jié)點(diǎn)，所有的節(jié)點(diǎn)都以緩存行對(duì)齊方式存儲(chǔ).然而，由于NV-Tree需要所有的內(nèi)部節(jié)點(diǎn)存儲(chǔ)在連續(xù)的內(nèi)存塊，那么每一個(gè)葉子節(jié)點(diǎn)的父節(jié)點(diǎn)的分裂操作將導(dǎo)致整個(gè)內(nèi)部節(jié)點(diǎn)的重構(gòu)操作.并且，NV-Tree在DRAM中保存內(nèi)部節(jié)點(diǎn)的方式在系統(tǒng)故障時(shí)需要一定的時(shí)間來(lái)恢復(fù).

針對(duì)NVM讀寫不對(duì)稱性問(wèn)題(主要是延遲方面)以及現(xiàn)有的B+Tree變體工作存在持久內(nèi)存泄露問(wèn)題以及數(shù)據(jù)恢復(fù)弱點(diǎn)，德國(guó)德累斯頓工業(yè)大學(xué)的Oukid等人[11]提出了基于NVM和DRAM混合內(nèi)存的持久并發(fā)B-Tree變體FPTree，它將內(nèi)部節(jié)點(diǎn)保存在易失性的DRAM中而葉子節(jié)點(diǎn)保存在非易失性的NVM中；FPTree通過(guò)一個(gè)字節(jié)指紋(fingerprints)來(lái)減少緩存行的刷新，指紋是每個(gè)葉子節(jié)點(diǎn)中鍵的1 B散列.在查找搜索鍵之前先掃描指紋來(lái)限制需要查找鍵的數(shù)量，結(jié)果降低了緩存行失效率；FPTree使得葉子節(jié)點(diǎn)中的條目無(wú)序，內(nèi)部節(jié)點(diǎn)中的條目保持有序.同NV-Tree一樣，F(xiàn)PTree也采用選擇持久化(selective persistence)機(jī)制降低數(shù)據(jù)一致性開銷，即將葉子節(jié)點(diǎn)等主要數(shù)據(jù)存儲(chǔ)在NVM中并保證葉子節(jié)點(diǎn)一致性，而將內(nèi)部節(jié)點(diǎn)等非主要數(shù)據(jù)存儲(chǔ)在DRAM中且不保證內(nèi)部節(jié)點(diǎn)一致性.通過(guò)選擇并發(fā)性機(jī)制即對(duì)內(nèi)部節(jié)點(diǎn)采用硬件事務(wù)內(nèi)存(HTM)而葉子節(jié)點(diǎn)采用細(xì)粒度鎖確保并發(fā)；最后通過(guò)持久性指針來(lái)解決內(nèi)存泄漏問(wèn)題.雖然FPTree顯示比NVTree更好的性能，但是當(dāng)系統(tǒng)故障時(shí)也需要重構(gòu)存放在DRAM中的內(nèi)部節(jié)點(diǎn).

針對(duì)易失性CPU緩存與NVM之間以緩存行粒度而非頁(yè)粒度作為數(shù)據(jù)傳輸單元，但是故障原子寫單元為8 B而非64 B的緩存行大小，該粒度不匹配問(wèn)題已經(jīng)引發(fā)了廣泛的研究，即基于塊的數(shù)據(jù)結(jié)構(gòu)如B+Tree重新設(shè)計(jì)以便匹配字節(jié)尋址的NVM.然而，各種B+Tree變體降低了B+Tree在NVM中的效率.韓國(guó)蔚山國(guó)家科學(xué)技術(shù)研究所(UNIST)Hwang等人[12]提出了基于NVM的可忍受瞬態(tài)不一致性的持久B+Tree變體FAST& FAIR，它通過(guò)采用插入過(guò)程故障原子移動(dòng)(failure-atomic shift, FAST)解決了粒度不匹配問(wèn)題，在FAST的8 B存儲(chǔ)(store)指令和故障原子的原地再平衡(failure-atomic in-place rebalance, FAIR)機(jī)制可以確保B+Tree從一致性狀態(tài)轉(zhuǎn)換到另一種一致性狀態(tài)；或者在寫線程更改樹節(jié)點(diǎn)不成功時(shí)，F(xiàn)AST中的8 B的存儲(chǔ)操作序列和FAIR算法可保證任何讀線程不會(huì)訪問(wèn)到不一致的樹節(jié)點(diǎn).通過(guò)讀操作容忍臨時(shí)的不一致性可以有效避免昂貴的寫時(shí)拷貝、日志機(jī)制，甚至讀取鎖存器的必要性，以便讀取事務(wù)可以是非阻塞的即無(wú)鎖查詢.

當(dāng)前基于NVM的Tree索引結(jié)構(gòu)一致性研究主要基于B-Tree或B+Tree變體，如CDDS B-Tree[8]，wB+Trees[9]，NV-Tree[10]，F(xiàn)PTree[11]，F(xiàn)AST&FAIR[12]等.然而也有研究開展了基于NVM的基數(shù)樹(radix tree)變體WORT[13]和紅黑樹CRB-Tree[14]的一致性工作研究.

針對(duì)當(dāng)前的處理器經(jīng)常以緩存行粒度重排序內(nèi)存寫操作并且需要采用MFENCE和CLFLUSH指令執(zhí)行內(nèi)存寫的有序性，但是MFENCE和CLFLUSH指令是引發(fā)性能下降的主要因素[9-11,39],韓國(guó)蔚山國(guó)家科學(xué)技術(shù)研究所(UNIST)的Lee等人[13]指出了現(xiàn)有NVM的B-Tree變體通過(guò)削弱原始B-Tree的某個(gè)關(guān)鍵特征如保持節(jié)點(diǎn)中鍵的有序性.此外，8 B原子更新寫不足以處理節(jié)點(diǎn)分裂涉及多個(gè)節(jié)點(diǎn)更新粒度，該分裂操作仍然需要日志機(jī)制保持一致性.而radix tree不需要鍵比較，并且插入或刪除操作僅需單個(gè)8 B更新操作而不再需要樹結(jié)構(gòu)的再平衡操作如B-Tree分裂或合并操作所引發(fā)的節(jié)點(diǎn)粒度更新，表明了基數(shù)樹(radix tree)比B -Tree更適用于NVM.由于原始基數(shù)樹已知糟糕的內(nèi)存利用率和緩存效率使其不能直接適應(yīng)NVM.為了克服這個(gè)局限，基數(shù)樹采用了路徑壓縮優(yōu)化，路徑壓縮將多個(gè)樹節(jié)點(diǎn)合并成單個(gè)節(jié)點(diǎn)以便形成唯一的搜索路徑.雖然路徑壓縮顯著地提升了基數(shù)樹的性能，但是它涉及節(jié)點(diǎn)分裂和合并操作是對(duì)NVM有害的.因此，韓國(guó)蔚山國(guó)立科學(xué)技術(shù)研究所(UNIST)的Lee等人[13]提出了基于NVM寫優(yōu)化的基數(shù)樹變體WORT，它通過(guò)采用8 B故障原子寫更新(failure-atomic write per update)而無(wú)需通過(guò)日志或?qū)憰r(shí)拷貝機(jī)制來(lái)確保一致性，并且所開發(fā)的故障原子路徑壓縮機(jī)制的基數(shù)樹不僅能夠確保故障一致性，而且同現(xiàn)有的路徑壓縮機(jī)制的基數(shù)樹有一樣的內(nèi)存節(jié)省效果.對(duì)于WORT中的節(jié)點(diǎn)分裂和合并操作，通過(guò)添加MFENCE和CLFLUSH持久操作確保故障原子寫的同時(shí)最小化NVM寫次數(shù)以及MFENCE和CLFLUSH指令操作次數(shù).文獻(xiàn)[13]表明了radix tree是適合于NVM的數(shù)據(jù)結(jié)構(gòu)，并且提出了優(yōu)化的radix tree變體WORT和WOART以及ART+COW，后2種是基于自適應(yīng)的基數(shù)樹(adaptive radix tree， ART)，ART[38]解決了搜索性能和節(jié)點(diǎn)利用率之間的平衡，通過(guò)采用自適應(yīng)的節(jié)點(diǎn)類型轉(zhuǎn)換能夠根據(jù)節(jié)點(diǎn)利用率來(lái)動(dòng)態(tài)地改變樹節(jié)點(diǎn)的大小，能夠進(jìn)一步提高基數(shù)樹(radix tree)的空間利用率.并且指出了ART中寫時(shí)拷貝開銷顯著地小于B -Tree及其變體中的寫時(shí)拷貝開銷.

針對(duì)大多數(shù)當(dāng)前的內(nèi)存數(shù)據(jù)結(jié)構(gòu)都會(huì)出現(xiàn)一致性問(wèn)題，新加坡數(shù)據(jù)存儲(chǔ)研究所A-STAR的Wang等人[14]首先將計(jì)算機(jī)系統(tǒng)中廣泛使用的重要內(nèi)存結(jié)構(gòu)紅黑樹(RB樹)引入基于NVM的系統(tǒng)，并開展了一致性研究工作.由于紅黑樹具有漫長(zhǎng)而復(fù)雜的更新過(guò)程，因此基于NVM的RB樹很容易出現(xiàn)不一致的問(wèn)題.他們提出了一種基于NVM的一致性紅黑樹CRB-Tree，其中包含一種名為cascade-versioning的新技術(shù).所提出的CRB-Tree具有2個(gè)特點(diǎn)：1)總是一致且可擴(kuò)展的；2)在系統(tǒng)崩潰之后不需要恢復(fù)過(guò)程.實(shí)驗(yàn)結(jié)果表明，基于NVM的CRB -Tree不僅獲得較低的空間開銷和數(shù)據(jù)一致性的目的，而且有著與普通易失性紅黑樹相當(dāng)?shù)男阅?

1.2 基于散列索引結(jié)構(gòu)的一致性研究

散列算法因其常量級(jí)的查詢性能而被廣泛使用[23-25,36-37].然而基于NVM的散列索引將面臨系統(tǒng)故障時(shí)數(shù)據(jù)一致性問(wèn)題.因?yàn)橛缮⒘兴饕逃械纳⒘袥_突問(wèn)題而造成過(guò)多的寫操作，所以需要在保證基于散列索引結(jié)構(gòu)的數(shù)據(jù)一致性的同時(shí)減少NVM的寫.美國(guó)NEC實(shí)驗(yàn)室的Debnath等人[36]提出了基于PCM寫友好的布谷鳥散列變體PFHT，PFHT提供了布谷鳥散列的優(yōu)勢(shì)，比如高效的內(nèi)存利用率以及保證的查詢時(shí)間；并且它通過(guò)限制主表剔除次數(shù)為1，顯著地減少了傳統(tǒng)布谷鳥散列算法因散列沖突導(dǎo)致的大量NVM寫.華中科技大學(xué)的Zuo等人[37]提出了一種基于NVM的成本高效的寫入友好路徑散列方案Path Hashing，它通過(guò)新穎的散列沖突解決方法位置共享技術(shù)，避免了插入和刪除過(guò)程中額外的NVM寫操作.雖然PFHT和Path Hashing都減少了NVM寫次數(shù)，但是它們都沒(méi)有保證數(shù)據(jù)的一致性.接下來(lái)將對(duì)現(xiàn)有的基于散列的一致性工作展開介紹如組散列(Group Hashing)[23]，Level Hashing[24]，NVLH[25].

針對(duì)先前的基于NVM的散列工作如PFHT和Path Hashing等既不考慮高速緩存行刷新(CLFLUSH)和內(nèi)存柵欄(MFENCE)的成本，也不維護(hù)系統(tǒng)在意外故障時(shí)的數(shù)據(jù)一致性,華中科技大學(xué)Zhang等人[23]首先提出了基于NVM的寫入高效且一致的散列方案為Group Hashing.組散列背后的基本思想是降低一致性成本，同時(shí)在出現(xiàn)意外系統(tǒng)故障時(shí)保證數(shù)據(jù)一致性.組散列主要貢獻(xiàn)有2個(gè)：1)使用8 B故障原子寫入來(lái)保證數(shù)據(jù)的一致性，從而消除了對(duì)NVM的雙倍寫入，因此降低了散列表結(jié)構(gòu)的一致性成本;2)為了提高CPU緩存效率，組散列利用了一種新穎的組共享(group sharing)技術(shù)，它將散列表分成組，并且在每個(gè)組中部署一個(gè)連續(xù)的內(nèi)存空間來(lái)處理散列沖突，從而減少CPU緩存缺失，因此組散列在請(qǐng)求延遲方面獲得更高的性能.

針對(duì)基于NVM的數(shù)據(jù)一致性和硬件限制的要求，最初為DRAM設(shè)計(jì)的傳統(tǒng)索引技術(shù)在NVM中變得低效.為了有效地索引NVM中的數(shù)據(jù)，華中科技大學(xué)Zuo等人[24]提出了一種基于NVM的寫優(yōu)化和高性能的散列索引方案Level Hashing，它具有低開銷的一致性保證和成本高效的resize操作.Level Hashing提供基于共享的2級(jí)(two-level)散列表，在最壞的情況下實(shí)現(xiàn)恒定的時(shí)間復(fù)雜度的搜索、插入、刪除以及更新操作，并且很少引起額外的NVM寫入.為了保證低開銷的一致性，Level Hashing利用無(wú)日志一致性方案進(jìn)行插入、刪除和resize操作，并采用機(jī)會(huì)無(wú)日志方案進(jìn)行更新操作.為了經(jīng)濟(jì)高效地調(diào)整此散列表的大小，Level Hashing利用了原地調(diào)整大小的方案，只需要重新傳輸13的桶(bucket)而不是整個(gè)表，因此減少重新散列的桶數(shù)并提高調(diào)整大小的性能.

針對(duì)現(xiàn)有的工作沒(méi)有研究線性散列的全面設(shè)計(jì)和優(yōu)化以便充分利用NVM，而基于NVM的線性散列算法需要保證數(shù)據(jù)的一致性,香港城市大學(xué)的Wan等人提出了基于NVM的持久且崩潰一致的線性散列NVLH[25].NVLH基于操作系統(tǒng)的直接訪問(wèn)(DAX)功能，允許應(yīng)用程序通過(guò)內(nèi)存映射直接訪問(wèn)NVM.NVLH通過(guò)高速緩存行刷新指令(CLFLUSH)或弱有序高速緩存行刷新指令(如Intel處理器上的CLFLUSHOPT和CLWB)和內(nèi)存柵欄(MFENCE)的組合來(lái)完成NVM數(shù)據(jù)更新的持久化.為了支持崩潰一致性(crash consistency)，NVLH采用基于撤銷日志(undo logging)的事務(wù)實(shí)現(xiàn)，在事務(wù)修改原始值(original values)之前將相應(yīng)的原始值存儲(chǔ)到undo日志中.

1.3 基于混合索引結(jié)構(gòu)的一致性研究

針對(duì)現(xiàn)有基于DRAM和NVM的混合內(nèi)存系統(tǒng)的鍵值存儲(chǔ)的索引設(shè)計(jì)未能充分利用混合內(nèi)存特定的性能特征，比如DRAM的快速寫入、NVM的慢寫入以及DRAM和NVM中的相似的讀性能.中國(guó)科學(xué)院計(jì)算技術(shù)研究所的Xia等人[26]提出了一個(gè)基于NVM和DRAM混合內(nèi)存的鍵值存儲(chǔ)HiKV，其核心思想是在混合內(nèi)存中構(gòu)建混合索引.為了有效支持豐富的鍵值操作，HiKV利用了散列索引和B+Tree索引的獨(dú)特優(yōu)點(diǎn).HiKV在NVM中構(gòu)建并保持散列索引，以保留其快速索引搜索的固有能力.HiKV在DRAM中構(gòu)建B+-Tree索引以支持范圍掃描，并避免長(zhǎng)時(shí)間NVM寫入以保持2個(gè)索引的一致性.此外，HiKV將差異并發(fā)方案應(yīng)用于混合索引，并采用有序?qū)懭胍恢滦詠?lái)確保崩潰一致性.

1.4 NVM內(nèi)存索引一致性研究小結(jié)

目前基于NVM的一致性持久索引主要有基于Tree索引結(jié)構(gòu)的研究(如CDDS B-Tree[8]，wB+Trees[9]，NV-Tree[10]，F(xiàn)PTree[11]，F(xiàn)AST&FAIR[12]，WORT[13]，CRB-Tree[14])和基于散列索引結(jié)構(gòu)研究(如Group Hashing[23]，Level Hashing[24]，NVLH[25])以及混合索引HiKV[26].已有研究HiKV[26]提出了B+Tree和散列的混合索引結(jié)構(gòu)，并對(duì)混合索引結(jié)構(gòu)實(shí)現(xiàn)了一致性.為了克服日志機(jī)制或?qū)憰r(shí)拷貝等雙倍寫開銷，許多工作均采用8 B故障原子寫方式確保一致性[8-13,23-24]，通過(guò)弱化B+Tree葉子節(jié)點(diǎn)中條目的有序性或減少散列沖突帶來(lái)的條目移動(dòng)[23-25,36]可以進(jìn)一步降低NVM寫；通過(guò)選擇持久化方式[10-11]可以減少一致性開銷；通過(guò)結(jié)合不同的數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)如混合索引[26]設(shè)計(jì)低開銷的一致性研究.

2 基于NVM的文件系統(tǒng)的數(shù)據(jù)一致性研究

傳統(tǒng)基于DRAM和磁盤的文件系統(tǒng)采用檢查點(diǎn)機(jī)制、Journaling技術(shù)、寫時(shí)拷貝或日志技術(shù)保障系統(tǒng)崩潰時(shí)的數(shù)據(jù)一致性.然而，NVM有著DRAM的性能和磁盤的持久性，學(xué)術(shù)界和工業(yè)界越來(lái)越多地開展基于NVM的文件系統(tǒng)研究[17-18,27-28,40-45].由于性能原因，當(dāng)今內(nèi)存控制器或CPU會(huì)重排序內(nèi)存寫操作，從而會(huì)造成NVM寫的不一致性情況發(fā)生.針對(duì)一致性問(wèn)題，我們從NVM作為直接內(nèi)存文件系統(tǒng)(如BPFS[17]，PMFS[18]，F(xiàn)CFS[27])、NVM和DRAM混合內(nèi)存文件系統(tǒng)(如NOVA[28]和HMVFS[43])以及NVM做元數(shù)據(jù)緩存方面文件系統(tǒng)(如FSMAC[44]和Fine-grained Metadata Journaling[45])的一致性工作展開論述.

2.1 基于NVM單層主存的文件系統(tǒng)數(shù)據(jù)一致性研究

針對(duì)傳統(tǒng)的shadow paging文件系統(tǒng)如ZFS和WAFL，對(duì)文件系統(tǒng)的更新會(huì)觸發(fā)從更改位置到文件系統(tǒng)樹根節(jié)點(diǎn)之間一連串的更新，即迭代更新問(wèn)題.微軟研究院Condit等人[17]提出了字節(jié)尋址持久內(nèi)存文件系統(tǒng)BPFS，采用DRAM模擬的字節(jié)尋址持久的PCM內(nèi)存技術(shù)能夠消除許多傳統(tǒng)易失和非易失存儲(chǔ)之間的不同，并且提出的短路影子分頁(yè)(short-circuit shadow paging， SCSP)新技術(shù)能夠提供細(xì)粒度的寫時(shí)拷貝并且提供文件系統(tǒng)的任何級(jí)別的小更新，SCSP技術(shù)克服了傳統(tǒng)的shadow paging技術(shù)帶來(lái)的從更改位置到文件系統(tǒng)樹根節(jié)點(diǎn)之間一連串的更新問(wèn)題，從而降低了更新的成本.SCSP技術(shù)通過(guò)2種簡(jiǎn)單的硬件原語(yǔ)使之成為可能：原子的8 B寫以及epoch barrier.原子的8 B寫(atomic 8-byte write)允許BPFS通過(guò)寫單值到NVM以便提交更改，從而文件系統(tǒng)數(shù)據(jù)在斷電或故障的時(shí)候不會(huì)造成不一致.而epoch barriers維護(hù)BPFS中NVM寫之間的順序性約束，同時(shí)BPFS依然可以使用L1和L2 Cache來(lái)提高性能.

針對(duì)傳統(tǒng)的基于磁盤的文件系統(tǒng)存在雙份拷貝開銷問(wèn)題，即：1)從塊設(shè)備(block device)到頁(yè)高速緩存(page cache)；2)從頁(yè)高速緩存到用戶緩沖(user buffer).Intel公司的Dulloor等人[18]提出了輕量級(jí)的持久內(nèi)存文件系統(tǒng)PMFS，它可以不通過(guò)塊層直接訪問(wèn)PM設(shè)備，并且它遵守POSIX接口以便支持傳統(tǒng)的應(yīng)用程序.該輕量級(jí)的文件系統(tǒng)以及優(yōu)化的內(nèi)存映射IO無(wú)需在DRAM和輔助存儲(chǔ)中拷貝數(shù)據(jù)，從而避免了雙倍拷貝開銷.然而，PMFS主要解決3個(gè)挑戰(zhàn)：1)有序性和持久性等一致性問(wèn)題；2)如何保護(hù)PM免受流浪寫；3)如何驗(yàn)證以及判斷一致性測(cè)試的正確性.PMFS利用處理器的分頁(yè)和內(nèi)存排序功能進(jìn)行優(yōu)化，例如細(xì)粒度日志(fine-grained logging)用于一致性；透明大頁(yè)面支持用于更快的內(nèi)存映射IO.為了提供強(qiáng)大的一致性保證，PMFS只需要一個(gè)簡(jiǎn)單的硬件原語(yǔ)pm_wbarrier，它用于提供軟件執(zhí)行寫PM的耐久性和有序性保證.最后，PMFS使用處理器的現(xiàn)有功能來(lái)保護(hù)PM免受流浪寫(stray writes)，從而提高可靠性.

針對(duì)現(xiàn)有的應(yīng)用程序的故障一致性更新(failure-consistent update)協(xié)議主要為磁盤存儲(chǔ)系統(tǒng)做優(yōu)化，然而這些協(xié)議的實(shí)現(xiàn)沒(méi)有全面理解底層文件系統(tǒng)的持久性，它們過(guò)多的數(shù)據(jù)拷貝導(dǎo)致面向NVM的文件系統(tǒng)面臨易錯(cuò)和較差性能的問(wèn)題，清華大學(xué)的Ou等人[27]提出了一種針對(duì)NVM優(yōu)化的新型文件系統(tǒng)FCFS，它提供了一系列易于使用的基于文件的接口，以便為應(yīng)用程序提供正確性和高性能，并且持久更新其數(shù)據(jù)到NVM.具體而言，F(xiàn)CFS基于一致性語(yǔ)義使應(yīng)用程序能夠有效且有選擇性地更新多個(gè)存儲(chǔ)在NVM的文件.為此，F(xiàn)CFS采用NVM優(yōu)化的寫優(yōu)先日志機(jī)制，通過(guò)充分利用NVM的字節(jié)可尋址性和高并發(fā)屬性來(lái)降低一致性成本，但是不依賴于頁(yè)面緩存層技術(shù).首先，混合細(xì)粒度日志(hybrid fine-grained logging)將文件系統(tǒng)元數(shù)據(jù)日志和數(shù)據(jù)日志分離，以避免錯(cuò)誤共享日志數(shù)據(jù)，并在復(fù)制成本和日志跟蹤開銷之間實(shí)現(xiàn)良好的權(quán)衡.文件系統(tǒng)元數(shù)據(jù)采用字節(jié)級(jí)回滾日志，從而消除高額的元數(shù)據(jù)索引開銷；而文件系統(tǒng)數(shù)據(jù)采用緩存行粒度的重做日志，以便平衡數(shù)據(jù)拷貝和索引開銷.其次，并行選擇性檢查點(diǎn)(concurrently selective checkpointing)允許并行執(zhí)行異步檢查點(diǎn)并使用最少的數(shù)據(jù)副本以提高其效率.

2.2 基于NVM-DRAM混合內(nèi)存文件系統(tǒng)數(shù)據(jù)一致性

針對(duì)于現(xiàn)有的NVM文件系統(tǒng)要么具有相似的軟件開銷，要么無(wú)法提供應(yīng)用程序所需的強(qiáng)一致性保證問(wèn)題，美國(guó)加州大學(xué)圣地亞哥分校的Xu等人[28]提出了一個(gè)基于混合易失和非易失內(nèi)存的日志結(jié)構(gòu)、POSIX文件系統(tǒng)NOVA，它擴(kuò)展LFS并充分利用NVM的優(yōu)勢(shì)，旨在最大限度地提高混合內(nèi)存系統(tǒng)的性能，同時(shí)提供強(qiáng)的一致性保證.NOVA采用傳統(tǒng)的日志結(jié)構(gòu)文件系統(tǒng)技術(shù)來(lái)利用NVM提供的快速隨機(jī)訪問(wèn).特別是，它為每個(gè)inode維護(hù)單獨(dú)的日志以提高并發(fā)性，并將文件數(shù)據(jù)存儲(chǔ)在日志之外，以最小化日志大小并降低垃圾收集成本.NOVA的日志提供元數(shù)據(jù)、數(shù)據(jù)和內(nèi)存映射(mmap)的原子性，日志結(jié)構(gòu)技術(shù)(log-structuring)用于單個(gè)日志結(jié)構(gòu)更新，輕量級(jí)日志結(jié)構(gòu)(journaling)用于多個(gè)日志結(jié)構(gòu)更新，寫時(shí)拷貝用于文件數(shù)據(jù).

針對(duì)基于NVM的內(nèi)存文件系統(tǒng)的現(xiàn)有方法側(cè)重于對(duì)內(nèi)存的低開銷訪問(wèn)，并且僅保證數(shù)據(jù)和元數(shù)據(jù)之間的一致性.上海交通大學(xué)的Zheng等人[43]提出了一種基于NVM和DRAM混合內(nèi)存的有效的版本控制文件系統(tǒng)HMVFS，它解決了基于NVM的內(nèi)存文件系統(tǒng)的連續(xù)快照之間一致性的問(wèn)題.HMVFS可以有效地實(shí)現(xiàn)容錯(cuò)，并且對(duì)IO性能的影響很小.為了強(qiáng)一致性保證，HMVFS采用分層文件系統(tǒng)樹(stratified file system tree， SFST)表示整個(gè)文件系統(tǒng)的快照，并且快照的原子性操作得到保證.HMVFS在故障恢復(fù)過(guò)程幾乎沒(méi)有redo或undo開銷.HMVFS充分利用NVM的字節(jié)尋址特性以字節(jié)粒度更新樹元數(shù)據(jù)，采用日志結(jié)構(gòu)的方式對(duì)文件更新避免了寫放大，提高了NVM的寫耐久性.

2.3 基于NVM的文件系統(tǒng)元數(shù)據(jù)緩存一致性工作

針對(duì)傳統(tǒng)文件系統(tǒng)將元數(shù)據(jù)存放在DRAM中并周期性地寫回磁盤，而元數(shù)據(jù)的更新頻繁并且每次只更新很小一部分.華中科技大學(xué)Chen等人[44]提出了一種基于NVM的文件系統(tǒng)元數(shù)據(jù)加速器FSMAC，通過(guò)有效地利用NVM的優(yōu)點(diǎn)來(lái)優(yōu)化元數(shù)據(jù)訪問(wèn).FSMAC解耦數(shù)據(jù)和元數(shù)據(jù)IO路徑，在運(yùn)行時(shí)將數(shù)據(jù)放在磁盤上而元數(shù)據(jù)放在NVM上.因此，從IO總線塊中訪問(wèn)數(shù)據(jù)，并且以字節(jié)尋址方式從內(nèi)存總線訪問(wèn)元數(shù)據(jù).元數(shù)據(jù)訪問(wèn)得到顯著加速，并且消除了元數(shù)據(jù)IO，因?yàn)镹VM中的元數(shù)據(jù)不再定期刷回磁盤.FSMAC引入了一種結(jié)合了細(xì)粒度版本控制和事務(wù)處理的輕量級(jí)一致性機(jī)制.

針對(duì)傳統(tǒng)日志機(jī)制以4KB的塊來(lái)存儲(chǔ)文件系統(tǒng)的元數(shù)據(jù)，從而造成了NVM空間的浪費(fèi)以及寫入放大問(wèn)題.新加坡數(shù)據(jù)存儲(chǔ)研究所A-STAR的Chen等人[45]提出了一種基于NVM的細(xì)粒度的元數(shù)據(jù)日志機(jī)制(fine-grained metadata journaling)，以充分利用低延遲字節(jié)可尋址的NVM，從而顯著降低傳統(tǒng)Journaling的開銷.新的日志格式采用128 B的inode大小粒度來(lái)順序記錄到NVM，通過(guò)對(duì)頭尾指針以8 B原子更新的方式標(biāo)志事務(wù)的結(jié)束.因此，由于減少了對(duì)NVM的有序?qū)懭肓浚梢詼p少日志記錄的開銷，但由于該日志機(jī)制只把元數(shù)據(jù)記錄到日志空間，所以并不能給文件系統(tǒng)帶來(lái)最強(qiáng)的一致性級(jí)別保證.

2.4 基于NVM文件系統(tǒng)數(shù)據(jù)一致性小結(jié)

充分利用NVM的字節(jié)尋址特性，BPFS提出細(xì)粒度的寫時(shí)拷貝機(jī)制，克服迭代更新問(wèn)題，因此減少了額外的NVM寫[17].為了平衡索引和數(shù)據(jù)拷貝開銷，F(xiàn)CFS對(duì)文件系統(tǒng)元數(shù)據(jù)和數(shù)據(jù)分別采用不同粒度的日志機(jī)制，如對(duì)元數(shù)據(jù)采用字節(jié)級(jí)回滾日志、對(duì)數(shù)據(jù)采用緩存行粒度重做日志[27].充分利用DRAM和NVM各自的優(yōu)勢(shì)，保障數(shù)據(jù)一致性的同時(shí)最大限度地提高混合內(nèi)存文件系統(tǒng)的性能[28,43].NOVA對(duì)不同的更新采用不同的一致性技術(shù)，即對(duì)單個(gè)日志結(jié)構(gòu)更新采用日志結(jié)構(gòu)技術(shù)，對(duì)多個(gè)日志結(jié)構(gòu)更新采用輕量級(jí)日志結(jié)構(gòu)，對(duì)文件數(shù)據(jù)更新采用寫時(shí)拷貝[28].HMVFS解決了連續(xù)快照間一致性，對(duì)元數(shù)據(jù)更新采用字節(jié)粒度，而對(duì)文件更新采用日志結(jié)構(gòu)方式[43].為了減少傳統(tǒng)文件系統(tǒng)元數(shù)據(jù)寫入放大問(wèn)題并提高元數(shù)據(jù)訪問(wèn)效率，采用NVM存儲(chǔ)元數(shù)據(jù)來(lái)優(yōu)化元數(shù)據(jù)的訪問(wèn)效率[44-45].總的來(lái)說(shuō)，面向NVM的文件系統(tǒng)可以有效地利用NVM的字節(jié)尋址特性，減少元數(shù)據(jù)管理開銷，對(duì)文件系統(tǒng)元數(shù)據(jù)和數(shù)據(jù)采用不同適配粒度的一致性機(jī)制，確保數(shù)據(jù)一致性的同時(shí)盡量減少NVM寫.

3 基于NVM的持久性事務(wù)的數(shù)據(jù)一致性研究

為保證NVM數(shù)據(jù)一致性的關(guān)鍵是要確保有序的持久化操作.不再考慮持久索引層面和文件系統(tǒng)層面可能相關(guān)工作，本節(jié)只從基于NVM的持久性事務(wù)層面的一致性相關(guān)文獻(xiàn)出發(fā)，并將這些文獻(xiàn)劃分為實(shí)現(xiàn)一致性的3個(gè)角度，分別為基于事務(wù)[19-20,46-53]、持久性模型[54-62]、檢查點(diǎn)[63-65]和日志機(jī)制[66-72].

3.1 基于事務(wù)的數(shù)據(jù)一致性研究

事務(wù)概念主要來(lái)自于數(shù)據(jù)庫(kù)，有ACID四大屬性，其中A，C，I，D分別代表原子性(atomicity)、一致性(consistency)、隔離性(isolation)以及持久性(durability).傳統(tǒng)事務(wù)是針對(duì)于CPU-DRAM-HDD架構(gòu)設(shè)計(jì)的，新型NVM具有DRAM的性能和磁盤的持久性，需要重新設(shè)計(jì)基于NVM的事務(wù)機(jī)制.保證NVM的事務(wù)中數(shù)據(jù)一致性依然要確保有序的持久化操作.基于新型編程接口的事務(wù)一致性研究現(xiàn)已開展，如NV-Heaps[19]和Mnemosyne[20].

針對(duì)易失性和非易失性區(qū)域之間指針安全錯(cuò)誤問(wèn)題，加州大學(xué)圣地亞哥分校的Coburn等人[19]提出了一個(gè)基于NVM的輕量級(jí)高性能的持久對(duì)象系統(tǒng)NV-Heaps，它提供了事務(wù)語(yǔ)義，同時(shí)防止了這些錯(cuò)誤并提供了易于使用和推理的持久性模型.為了指針安全，NV-Heaps提供了引用計(jì)數(shù)的NVM空間分配機(jī)制，并且它通過(guò)undo日志和事務(wù)內(nèi)存結(jié)合的方式提供數(shù)據(jù)一致性功能.

針對(duì)如何在NVM持久化數(shù)據(jù)并保證其數(shù)據(jù)一致性問(wèn)題，威斯康星大學(xué)麥迪遜分校的Volos等人[20]提出了一個(gè)基于NVM的簡(jiǎn)單的編程模型Mnemosyne.Mnemosyne解決了2個(gè)挑戰(zhàn)：如何創(chuàng)建和管理此類內(nèi)存，以及如何確保出現(xiàn)故障時(shí)的數(shù)據(jù)一致性.Mnemosyne通過(guò)內(nèi)存映射方式將NVM空間直接映射到用戶的地址空間中，用戶可以使用關(guān)鍵字“pstatic”對(duì)NVM空間中的數(shù)據(jù)進(jìn)行持久化定義或聲明.Mnemosyne同NV-Heaps一樣采用事務(wù)內(nèi)存結(jié)合日志的方式確保一致的更新.然而與NV-Heaps不同，Mnemosyne采用的是redo日志.

惠普實(shí)驗(yàn)室的Volos等人[46]發(fā)現(xiàn)現(xiàn)有的基于內(nèi)核的組件堆棧非常適合磁盤，不必要地限制了基于NVM的文件系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn).他們提出了一種靈活的文件系統(tǒng)架構(gòu)Aerie，利用攔截系統(tǒng)調(diào)用用戶庫(kù)libFS，直接讓用戶應(yīng)用程序訪問(wèn)NVM.為了避免直接訪問(wèn)模式下的并發(fā)訪問(wèn)和控制問(wèn)題，Aerie在用戶態(tài)實(shí)現(xiàn)了受信任的文件系統(tǒng)服務(wù)(trusted file-system service， TFS)提供并發(fā)訪問(wèn)和鎖機(jī)制.Aerie提供與Mnemosyne一樣的持久性原語(yǔ)和redo日志來(lái)提供數(shù)據(jù)一致性保證.

由于嚴(yán)格的持久性模型帶來(lái)了性能下降，基于NVM的降低順序性開銷的工作已經(jīng)展開[47,49].

針對(duì)遵守嚴(yán)格的持久性內(nèi)存寫入順序會(huì)顯著降低系統(tǒng)性能的問(wèn)題，清華大學(xué)的Lu等人[47]提出了一種基于NVM的松散順序一致性(LOC)的新機(jī)制，它滿足持久性內(nèi)存寫入的排序要求，其性能下降明顯低于最先進(jìn)的機(jī)制.LOC由2個(gè)關(guān)鍵技術(shù)組成：1)通過(guò)消除在事務(wù)結(jié)束時(shí)執(zhí)行持久性提交記錄寫入的需要，Eager Commit減少了事務(wù)中寫入的提交開銷.他們通過(guò)確保將必要的元數(shù)據(jù)信息靜態(tài)地以數(shù)據(jù)塊方式寫入內(nèi)存中來(lái)確定恢復(fù)期間所有已提交事務(wù)的狀態(tài)來(lái)實(shí)現(xiàn)此目的.2)Speculative Persistence通過(guò)允許推測(cè)性地寫入NVM來(lái)放寬事務(wù)之間的寫入順序.只有在關(guān)聯(lián)的事務(wù)提交后，才能使推測(cè)性寫入對(duì)軟件可見.要啟用此功能，LOC機(jī)制需要跟蹤已提交的事務(wù)ID并支持CPU緩存中的多版本控制.

針對(duì)現(xiàn)有事務(wù)更新對(duì)塊存儲(chǔ)的優(yōu)化而不適合字節(jié)尋址方式，英國(guó)愛丁堡大學(xué)的Chatzistergiou等人[48]提出了一種基于NVM的用戶模式庫(kù)方法REWIND，用于直接從使用命令式通用語(yǔ)言編寫的用戶代碼管理事務(wù)更新.REWIND依賴于支持自身可恢復(fù)操作的日志的自定義持久內(nèi)存數(shù)據(jù)結(jié)構(gòu).該方案還采用了非臨時(shí)更新、持久性內(nèi)存柵欄和輕量級(jí)日志記錄(lightweight logging)的組合確保數(shù)據(jù)一致性.

針對(duì)現(xiàn)有基于NVM的事務(wù)系統(tǒng)中有些不必要的順序性控制限制了事務(wù)系統(tǒng)的性能問(wèn)題，密歇根大學(xué)的Kolli等人[49]提出一種基于NVM的高效事務(wù)編程模型Eager Sync,通過(guò)推遲提交事務(wù)(deferring commit transactions)機(jī)制避免順序性約束帶來(lái)的關(guān)鍵路徑過(guò)長(zhǎng)問(wèn)題，其核心思想是一個(gè)事務(wù)在修改完數(shù)據(jù)之后釋放相應(yīng)的鎖，這樣可以減少順序性限制，從而提高事務(wù)系統(tǒng)的性能.

Intel公司的Doshi等人[50]提出了一個(gè)非侵入式內(nèi)存控制器，它使用后端操作來(lái)實(shí)現(xiàn)輕量級(jí)故障原子性WrAP.通過(guò)將同步持久內(nèi)存操作移動(dòng)到后臺(tái)，可以最大限度地降低性能開銷.該解決方案通過(guò)將隔離和并發(fā)驅(qū)動(dòng)的原子性與故障原子性和持久性分離，避免了昂貴的軟件干預(yù)，并且不需要更改前端緩存層次結(jié)構(gòu).

基于NVM的數(shù)據(jù)一致性需要有序的持久化操作.一致性開銷包含了順序化開銷和持久化開銷，如前面降低順序化開銷的工作[47,49]，降低持久化的開銷工作也已經(jīng)展開了研究[51-53].

針對(duì)現(xiàn)有事務(wù)系統(tǒng)采用撤消日志記錄(undo logging)或重做日志記錄(redo logging)來(lái)保證一致性，但undo logging和redo logging有各自的缺點(diǎn).清華大學(xué)的Liu等人[51]提出了基于NVM的崩潰一致的持久事務(wù)系統(tǒng)DudeTM，它結(jié)合撤消日志記錄和重做日志記錄方法以便充分利用undo和redo的優(yōu)點(diǎn)并且避免它們的不足.具體實(shí)現(xiàn)上，DudeTM使用影子DRAM將持久事務(wù)的執(zhí)行分解為3個(gè)完全異步的步驟(perform，persist，reproduce)，同時(shí)規(guī)避了undo logging的多次MFENCE操作以及redo logging的額外日志索引操作.DudeTM的優(yōu)點(diǎn)是只需要最少的內(nèi)存柵欄(MFENCE)和無(wú)需讀取內(nèi)存的指令.此外，DudeTM還可以支持現(xiàn)有的硬件事務(wù)內(nèi)存(HTM).

針對(duì)現(xiàn)有的原子性方法如undo logging和寫時(shí)拷貝COW都需要在關(guān)鍵路徑中產(chǎn)生額外的數(shù)據(jù)拷貝，從而顯著增加事務(wù)的延遲.加州大學(xué)圣地亞哥分校的Memaripour等人[52]提出了一種基于NVM的事務(wù)更新的新方法Kamino-Tx，而無(wú)需在關(guān)鍵路徑中復(fù)制任何數(shù)據(jù).Kamino-Tx提供原子就地更新，避免在關(guān)鍵路徑中創(chuàng)建數(shù)據(jù)項(xiàng)的拷貝，同時(shí)使用異步維護(hù)的數(shù)據(jù)項(xiàng)拷貝提供崩潰一致性.但Kamino-Tx必須克服2個(gè)重要的安全挑戰(zhàn)，并盡量減少NVM存儲(chǔ)開銷.他們提出了一種更動(dòng)態(tài)的方法來(lái)維護(hù)額外的數(shù)據(jù)副本，以減少存儲(chǔ)開銷.

美國(guó)威斯康星大學(xué)麥迪遜分校的Nalli等人[53]提出了一種放手持久化系統(tǒng)(hands-off persistence system, HOPS).基于NVM的應(yīng)用程序通過(guò)在寫入NVM之間插入排序點(diǎn)來(lái)確保持久性數(shù)據(jù)的一致性，從而允許構(gòu)建更高級(jí)別的事務(wù)機(jī)制.該工作提出了一個(gè)名為WHISPER的PM基準(zhǔn)套件，其中包括收集的10個(gè)NVM應(yīng)用程序，以涵蓋所有當(dāng)前的NVM接口如直接訪問(wèn)NVM、通過(guò)文件系統(tǒng)接口訪問(wèn)NVM以及通過(guò)使用NVM事務(wù)庫(kù)方式訪問(wèn)NVM.通過(guò)對(duì)WHISPER定量分析揭示了4個(gè)結(jié)論：1)NVM感知應(yīng)用程序只有4%的數(shù)據(jù)寫入NVM，其余寫入易失性內(nèi)存DRAM；2)軟件事務(wù)通常用5～50個(gè)有序點(diǎn)(ordering points)實(shí)現(xiàn)；3)75%的epoch更新恰好是一個(gè)64 B大小緩存行；4)80%的epoch取決于來(lái)自同一線程的先前的epoch，而少數(shù)epoch取決于來(lái)自其他線程的epoch.根據(jù)這些結(jié)論的分析，他們提出了HOPS來(lái)跟蹤硬件中NVM的更新.當(dāng)前的硬件設(shè)計(jì)要求應(yīng)用程序在每個(gè)epoch結(jié)束時(shí)強(qiáng)制刷新數(shù)據(jù)到NVM.HOPS為應(yīng)用程序提供高級(jí)ISA原語(yǔ)，并分離持久性和順序性約束.

3.2 基于持久性模型的數(shù)據(jù)一致性研究

基于NVM硬件的降低持久化的工作已經(jīng)展開了研究WSP[54]和Kiln[55].

針對(duì)基于NVM的用戶級(jí)持久堆需要大量修改應(yīng)用程序，并且仍然具有顯著的運(yùn)行開銷.微軟研究院劍橋部的Narayanan等人[54]提出了全系統(tǒng)持久性(WSP)作為替代方案.由于NVM技術(shù)允許內(nèi)存狀態(tài)近乎瞬時(shí)恢復(fù)而避免傳統(tǒng)基于DRAM-HDD系統(tǒng)的后端磁盤存儲(chǔ)恢復(fù)壓力，WSP針對(duì)的是所有內(nèi)存都是NVM的全內(nèi)存系統(tǒng)，它透明地恢復(fù)應(yīng)用程序的整個(gè)狀態(tài)，使故障顯示為掛起恢復(fù)事件.通過(guò)使用“故障時(shí)刷新(flush on fail)”消除了運(yùn)行時(shí)間開銷：處理器寄存器中的瞬態(tài)狀態(tài)和高速緩存僅在發(fā)生故障時(shí)使用系統(tǒng)電源的剩余能量刷新到NVM.

針對(duì)以前的基于NVM的設(shè)計(jì)使用日志記錄或?qū)憰r(shí)拷貝機(jī)制來(lái)更新持久性數(shù)據(jù)，然而系統(tǒng)性能大約是沒(méi)有持久性機(jī)制支持的系統(tǒng)的一半性能.賓夕法尼亞州立大學(xué)Zhao等人[55]提出了一種采用NVM作為高速緩存的LLC(last level cache)的NVM內(nèi)存系統(tǒng)Kiln，其性能非常接近沒(méi)有一致性支持的NVM內(nèi)存系統(tǒng).Kiln采用非易失性高速緩存和非易失性內(nèi)存來(lái)實(shí)現(xiàn)原子就地更新(atomic in-place updates)，嚴(yán)格控制NVM的寫入順序而無(wú)需日志或?qū)憰r(shí)拷貝機(jī)制.Kiln具有許多實(shí)際優(yōu)勢(shì)：簡(jiǎn)單直觀的抽象接口、微架構(gòu)級(jí)別優(yōu)化、從故障中快速恢復(fù)，以及消除對(duì)NVM的冗余寫入.雖然Kiln能夠在沒(méi)有l(wèi)ogging或copy-on-write機(jī)制的情況下實(shí)現(xiàn)一致性，并且它接近無(wú)一致性支持的原始NVM內(nèi)存系統(tǒng)，但是采用NVM作為L(zhǎng)LC cache需要傳統(tǒng)易失性緩存架構(gòu)做出大量的修改.

基于NVM控制器的有序性方面已經(jīng)展開了研究，如3.1節(jié)中WrAP[50]和接下來(lái)要講的2個(gè)工作分別是FIRM[56]和NVM Duet[57].

針對(duì)持久性內(nèi)存的應(yīng)用程序與傳統(tǒng)(非持久性)應(yīng)用程序具有非常不同的內(nèi)存訪問(wèn)特性，持久性應(yīng)用程序會(huì)帶來(lái)大量額外的寫，在傳統(tǒng)的內(nèi)存控制方案下讀寫分配的公平行和并行性效率都不能得到保證.賓夕法尼亞州立大學(xué)Zhao等人[56]提出了一種基于DRAM和NVM混合內(nèi)存的公平和高性能的內(nèi)存控制方案FIRM，該系統(tǒng)運(yùn)行持久性和非持久性應(yīng)用程序.FIRM包含3個(gè)主要想法:1)FIRM將請(qǐng)求源分類為非密集型、流式、隨機(jī)和持久性，并為每個(gè)請(qǐng)求源形成批量請(qǐng)求;2)FIRM跨多個(gè)bank的持久內(nèi)存更新，因此提高了bank級(jí)并行性，從而提高了持久內(nèi)存訪問(wèn)的存儲(chǔ)器帶寬利用率;3)FIRM以最小化總線周轉(zhuǎn)和寫入隊(duì)列排放的方式批量調(diào)度來(lái)自不同源的讀取和寫入請(qǐng)求.

針對(duì)未來(lái)NVM將同時(shí)扮演易失性工作內(nèi)存和持久性內(nèi)存的雙重角色，任何只考慮單一方面的統(tǒng)一架構(gòu)將得到次優(yōu)設(shè)計(jì).國(guó)立臺(tái)灣大學(xué)的Liu等人[57]提出了一種新穎的統(tǒng)一易失性工作內(nèi)存(working memory)和持久存儲(chǔ)(persistent store)內(nèi)存架構(gòu)NVM Duet，它為persistent store提供了所需的一致性和持久性保證，當(dāng)NVM作為易失性工作內(nèi)存時(shí)將放寬一致性和持久性約束，它采用跨層(cross-layer)設(shè)計(jì)方法來(lái)實(shí)現(xiàn)設(shè)計(jì)目標(biāo).NVM Duet包含一個(gè)硬件軟件接口，使內(nèi)存控制器能夠區(qū)分每次訪問(wèn)的用例，這是一種新穎的內(nèi)存調(diào)度程序，旨在充分利用地址流中存在的bank級(jí)并行性，同時(shí)遵循程序員指定的寫入順序.保證NVM作為persistent store的一致性以及雙保留PCM架構(gòu)，滿足持久內(nèi)存的持久性要求，同時(shí)放寬NVM作為易失性working memory的持久性要求，以換取寫延遲減少.

針對(duì)限制NVM寫入順序會(huì)限制NVM寫入并發(fā)性并降低吞吐量，從而使得需要新的內(nèi)存接口來(lái)最小化描述寫入約束并允許高性能和高并發(fā)數(shù)據(jù)結(jié)構(gòu).密歇根大學(xué)的Pelley等人[58]提出了一種新的持久內(nèi)存接口Strand Persistency，它建立在內(nèi)存一致性上.與內(nèi)存一致性類似，通過(guò)減少NVM寫入約束，寬松的持久性模型可大大提高系統(tǒng)吞吐量.Strand Persistency還概述了可能的內(nèi)存持久化模型的設(shè)計(jì)空間，并實(shí)現(xiàn)了2種持久性隊(duì)列.

針對(duì)當(dāng)前的持久性障礙將高速緩存行刷新添加到關(guān)鍵路徑導(dǎo)致大的緩存行刷新開銷，愛丁堡大學(xué)的Joshi等人[59]提出了有效的持久性障礙(efficient persist barrier)，可以減少關(guān)鍵路徑中發(fā)生的緩存行刷新次數(shù).為了確保持久狀態(tài)的一致性，需要從緩存中定期刷新臟緩存行，并按持久性模型指定的順序進(jìn)行持久化.Efficient persist barrier可以實(shí)現(xiàn)2種持久性模型：BEP(buffered epoch persistency);以及在具有硬件插入障礙的批量模式下的BSP(buffered strict persistency).

持久內(nèi)存系統(tǒng)要求持久有序約束以保證故障時(shí)數(shù)據(jù)的正確恢復(fù).基于軟件的持久性和易失性執(zhí)行相分離的方面已開展了研究[50,53,60-61].其中WrAP[50]和HOPS[53]已在3.1節(jié)中介紹過(guò)，接下來(lái)只介紹DPO[60]和TC.

針對(duì)當(dāng)前的內(nèi)存系統(tǒng)沒(méi)有提供有序內(nèi)存寫保證以及緊耦合強(qiáng)制執(zhí)行順序性和持久性寫入NVM對(duì)于許多可恢復(fù)軟件系統(tǒng)而言沒(méi)有必要.密歇根大學(xué)的Kolli等人[60]提出了一種基于NVM的委托持久化排序(delegated persistent ordering, DPO)，其中排序要求明確地傳達(dá)給NVM控制器，完全從易失性執(zhí)行和高速緩存管理中解耦NVM寫入排序特性.在ARMv7這種寬松內(nèi)存一致性模型系統(tǒng)中，委托排序(delegated ordering)實(shí)現(xiàn)了緩存嚴(yán)格持久性語(yǔ)義(relaxed consistency buffered strict persistency, RCBSP)，RCBSP將持久性排序從線程執(zhí)行中分離.委托排序明確地公開排序約束，它成功地將持久性強(qiáng)制執(zhí)行和緩存管理完全解耦.NVM內(nèi)存控制器接管持久性排序約束以便最大化提高調(diào)度的靈活性.

針對(duì)維持NVM的數(shù)據(jù)持久性方案要么產(chǎn)生很大的性能開銷，要么需要對(duì)現(xiàn)有架構(gòu)進(jìn)行大量修改.國(guó)立臺(tái)灣大學(xué)的Lai等人[61]提出了一種基于NVM的持久性內(nèi)存加速器設(shè)計(jì)，它通過(guò)硬件保證NVM數(shù)據(jù)的持久性，同時(shí)保持緩存層次結(jié)構(gòu)和內(nèi)存控制器操作不變.非易失性事務(wù)高速緩存(transaction cache, TC)與高速緩存層次結(jié)構(gòu)保持備用版本的數(shù)據(jù)更新，并且在不影響原始處理器執(zhí)行路徑的情況下鋪設(shè)新的持久路徑.在TC中采用先進(jìn)先出(FIFO)的隊(duì)列方式保證持久性內(nèi)存寫的有序性.TC的設(shè)計(jì)實(shí)現(xiàn)了接近沒(méi)有持久性保證的性能.

針對(duì)最近的工作提出了持久性模型作為內(nèi)存一致性的擴(kuò)展，以指定這種排序，那么考慮到持久存儲(chǔ)組的原子性和順序約束，是否有可能存在新的保證語(yǔ)言級(jí)持久性模型的分類.密歇根大學(xué)的Kolli等人[62]提出了一種基于NVM的C++11的語(yǔ)言級(jí)持久性模型ARP(acquire-release persistency).ARP擴(kuò)展了語(yǔ)言級(jí)內(nèi)存模型，保證了持久寫入的順序.他們描述如何將為ARP編寫的代碼編譯為最先進(jìn)的ISA級(jí)別持久性模型.然后，考慮對(duì)ISA級(jí)別持久性模型的增強(qiáng)，該模型可以區(qū)分正確同步所需的內(nèi)存一致性約束，但不需要正確的恢復(fù).

3.3 基于檢查點(diǎn)和日志機(jī)制的數(shù)據(jù)一致性研究

檢查點(diǎn)技術(shù)也是保障數(shù)據(jù)一致性的很好方式，每一次檢查點(diǎn)都被認(rèn)為系統(tǒng)一次有效的一致性狀態(tài).故障發(fā)生后，檢查點(diǎn)之后的數(shù)據(jù)更新都會(huì)被拋棄以便恢復(fù)到最近一次檢查點(diǎn)狀態(tài)，因此檢查點(diǎn)技術(shù)可以有效地減少檢查點(diǎn)之間數(shù)據(jù)一致性更新的數(shù)量.基于NVM的檢查點(diǎn)技術(shù)研究已經(jīng)開展了[63-65].基于軟件透明的崩潰一致性檢查點(diǎn)技術(shù)如ThyNVM[64]，NICO[65].

針對(duì)如何在下一代高端機(jī)器中使用非易失性內(nèi)存(NVM)來(lái)提供頻繁、低開銷的檢查點(diǎn).通過(guò)調(diào)整現(xiàn)有的多級(jí)檢查點(diǎn)技術(shù)，喬治亞理工學(xué)院的Kannan等人[63]設(shè)計(jì)了名為NVM檢查點(diǎn)(NVM-check-points)的新方法，可以在本地和遠(yuǎn)程節(jié)點(diǎn)NVM上有效地存儲(chǔ)檢查點(diǎn)，檢查點(diǎn)頻率由故障模型引導(dǎo).為了降低開銷，NVM檢查點(diǎn)減少了新的預(yù)復(fù)制機(jī)制所使用的NVM和互連帶寬，該機(jī)制在本地檢查點(diǎn)啟動(dòng)之前逐漸將檢查點(diǎn)數(shù)據(jù)從DRAM移動(dòng)到NVM.NVM-checkpoints通過(guò)限制在檢查點(diǎn)時(shí)移動(dòng)的瞬時(shí)數(shù)據(jù)量來(lái)減少本地檢查點(diǎn)成本，從而釋放應(yīng)用程序使用的帶寬.NVM-checkpoints將NVM視為內(nèi)存而不是RAM磁盤，因此可以推廣預(yù)復(fù)制以直接將數(shù)據(jù)移動(dòng)到遠(yuǎn)程N(yùn)VM.

針對(duì)基于NVM的系統(tǒng)需要在斷電或系統(tǒng)崩潰的情況下保證一致的內(nèi)存狀態(tài)(即崩潰一致性)，然而為了保證崩潰的一致性，大多數(shù)先前的工作需要依賴程序員區(qū)分持久和瞬態(tài)內(nèi)存數(shù)據(jù)，并且在更新持久內(nèi)存數(shù)據(jù)時(shí)使用專用軟件接口，從而使得持久內(nèi)存的采用可能會(huì)受到很大限制.清華大學(xué)Ren等人[64]提出了一種硬件輔助DRAM+NVM混合持久內(nèi)存設(shè)計(jì)ThyNVM(transparent hybrid NVM)，它支持混合內(nèi)存系統(tǒng)中內(nèi)存數(shù)據(jù)的軟件透明崩潰一致性.為了有效地實(shí)施崩潰一致性，他們?cè)O(shè)計(jì)了一種新的雙方案檢查點(diǎn)(dual-scheme checkpointing)機(jī)制，它有效地將檢查點(diǎn)時(shí)間與應(yīng)用程序執(zhí)行時(shí)間重疊.關(guān)鍵的新穎性是以協(xié)調(diào)的方式實(shí)現(xiàn)多粒度，即高速緩存行或頁(yè)粒度的數(shù)據(jù)檢查點(diǎn).由于檢查點(diǎn)導(dǎo)致的應(yīng)用程序停頓時(shí)間與用于檢查點(diǎn)的元數(shù)據(jù)的硬件存儲(chǔ)開銷之間存在折中，并且這兩者都由檢查點(diǎn)數(shù)據(jù)的粒度決定.為了獲得最佳權(quán)衡，ThyNVM使檢查點(diǎn)粒度適應(yīng)數(shù)據(jù)的寫入局部性特征，并協(xié)調(diào)多粒度更新的管理.

針對(duì)現(xiàn)有研究提出的具有軟件透明崩潰一致性保證的持久內(nèi)存設(shè)計(jì)，以減少程序員在利用NVM時(shí)的手動(dòng)努力，但由于創(chuàng)建檢查點(diǎn)導(dǎo)致的性能開銷，使得這些設(shè)計(jì)不是最理想的.華中科技大學(xué)的Wei等人[65]提出了一種基于NVM的非侵入式內(nèi)存控制器設(shè)計(jì)NICO，它使用后端操作來(lái)實(shí)現(xiàn)軟件透明的崩潰一致性，同時(shí)最小化檢查點(diǎn)開銷.通過(guò)將數(shù)據(jù)持久化操作移至后臺(tái)，NICO完全將數(shù)據(jù)持久化操作與易失性執(zhí)行和緩存管理分離.為了有效地實(shí)施崩潰一致性，NICO采用了一種輕量級(jí)的檢查點(diǎn)方案，在創(chuàng)建NVM數(shù)據(jù)的一致性快照(snapshot)時(shí)，只需要刷新和修改非常少量的數(shù)據(jù).

漢陽(yáng)大學(xué)的Hwang等人[66]開發(fā)了一個(gè)基于堆的持久對(duì)象存儲(chǔ)(HEAPO)來(lái)管理NVM中的持久對(duì)象.HEAPO定義了自己的持久堆布局、持久對(duì)象格式、命名空間組織、對(duì)象共享和保護(hù)機(jī)制，以及基于撤消日志的崩潰恢復(fù)，所有這些都是為NVM有效定制.HEAPO采用輕量級(jí)和靈活的層，以利用類似DRAM的NVM訪問(wèn)延遲.為了實(shí)現(xiàn)這一目標(biāo)，文獻(xiàn)[66]的作者開發(fā)了：1)NVM的本地管理層，以消除in-core和磁盤之間的元數(shù)據(jù)副本冗余；2)可擴(kuò)展對(duì)象格式；3)基于trie的全局命名空間和本地命名空間的緩存；4)靜態(tài)地址綁定；5)僅用于撤銷的崩潰恢復(fù)的最小日志機(jī)制.由于HEAPO庫(kù)使用鎖同步對(duì)共享對(duì)象元數(shù)據(jù)的訪問(wèn)，因此可以保證共享持久對(duì)象的更新一致性.HEAPO使用基于軟件的方法如CLFLUSH和MFENCE進(jìn)行NVM寫的有序性保證.

基于故障原子區(qū)(failure-atomic sections, FASEs)的鎖機(jī)制工作有Atlas[67]和JUSTDO logging[68].基于日志實(shí)現(xiàn)一致性工作有3.1節(jié)介紹的NV-Heaps，以及接下來(lái)將介紹的Atlas[67]，JUSTDO logging[68]，ATOM[69]，Proteus[70]，undo+redo logging[71]，EAPR[72]等.其中，采用undo日志的有Atlas，ATOM；基于redo日志的有3.1節(jié)介紹的Mnemosyne，結(jié)合undo和redo logging的工作有3.1節(jié)的DudeTM和下面的undo+redo logging工作，而JUSTDO logging是基于resumption的恢復(fù)方式.

針對(duì)如何確保NVM中數(shù)據(jù)在故障時(shí)的一致性.惠普實(shí)驗(yàn)室的Chakrabarti等人[67]提出了基于NVM日志的一致性鎖機(jī)制Atlas，它為基于鎖的代碼添加了持久性語(yǔ)義，通常允許即使在出現(xiàn)故障時(shí)也能自動(dòng)維護(hù)一個(gè)全局一致的狀態(tài).Atlas識(shí)別了現(xiàn)有的關(guān)鍵區(qū)代碼的故障原子區(qū)(failure-atomic sections, FASEs)并描述了一個(gè)基于undo日志的實(shí)現(xiàn)，可用于在故障后恢復(fù)一致性狀態(tài).對(duì)于嵌套鎖，只有先持久化內(nèi)部關(guān)鍵區(qū)后才能持久化外層關(guān)鍵區(qū).對(duì)于同步鎖，只有持久化所有關(guān)鍵區(qū)才算整個(gè)持久化完成.

針對(duì)基于NVM的數(shù)據(jù)在故障時(shí)不一致，傳統(tǒng)日志記錄(logging)方法需要將log從易失性CPU cache刷新到NVM導(dǎo)致了額外的時(shí)間和內(nèi)存開銷，而持久緩存(persistent cache)可以消除刷新的需要，但是傳統(tǒng)的undo或redo logging管理開銷依然存在.惠普實(shí)驗(yàn)室的Izraelevitz等人[68]提出了一種基于NVM的新的故障原子日志機(jī)制JUSTDO logging，可以大大減少日志的內(nèi)存占用，簡(jiǎn)化日志管理，并實(shí)現(xiàn)快速并行故障后恢復(fù).JUSTDO logging與傳統(tǒng)的undo和redo logging不同，不會(huì)舍棄在故障原子區(qū)(FASEs)中所做的更新，而是在最后一條store指令處重新執(zhí)行每個(gè)被中斷的FASE，直到執(zhí)行FASE完成.與Atlas一樣，JUSTDO logging將FASE定義為受一個(gè)或多個(gè)互斥鎖保護(hù)的最外層臨界區(qū).

針對(duì)通過(guò)用于撤銷日志(undo log)的流存儲(chǔ)(streaming stores)來(lái)進(jìn)行軟件日志(software logging)或依靠CLFLUSH和MFENCE組合的重做日志(redo log)等現(xiàn)有技術(shù)，它們浪費(fèi)了寶貴的執(zhí)行周期來(lái)實(shí)現(xiàn)日志記錄(logging).愛丁堡大學(xué)的Joshi等人[69]提出了一種基于NVM的撤消日志記錄(undo logging)的硬件日志管理器ATOM，它可以執(zhí)行關(guān)鍵路徑之外的logging操作.ATOM通過(guò)2種方式在硬件中透明地執(zhí)行日志記錄：1)將日志寫入與數(shù)據(jù)存儲(chǔ)耦合；2)在同一存儲(chǔ)控制器中共存數(shù)據(jù)及其相應(yīng)的日志條目.因此，ATOM不僅可以最大限度地減少數(shù)據(jù)移動(dòng)，而且可以在內(nèi)存控制器中執(zhí)行在關(guān)鍵路徑之外的日志到數(shù)據(jù)的排序約束.

針對(duì)基于NVM持久事務(wù)引入的高日志開銷，北卡羅來(lái)納州立大學(xué)的Shin等人[70]提出了一種基于NVM新的硬件日志記錄方法Proteus，它用于持久事務(wù)，實(shí)現(xiàn)了先前軟件和硬件方法的有利特性.與軟件一樣，Proteus沒(méi)有限制可用的事務(wù)或日志數(shù)量等硬件限制，而且像硬件一樣，它的開銷非常低.Proteus引入了2條新指令：log-load通過(guò)加載原始數(shù)據(jù)創(chuàng)建日志條目；log-flush將日志條目寫入NVM.Proteus主要在core內(nèi)添加硬件支持，以管理這些指令的執(zhí)行以及l(fā)ogging操作和數(shù)據(jù)更新之間的關(guān)鍵有序要求.Proteus通過(guò)明智的接口設(shè)計(jì)避免了對(duì)事務(wù)大小或數(shù)量的任何限制：軟件仍然可以控制分配日志區(qū)域，硬件可以將更新日志的成本保持在較低水平.

針對(duì)大多數(shù)先前的NVM設(shè)計(jì)通過(guò)仔細(xì)控制寫NVM順序帶來(lái)次優(yōu)性能的問(wèn)題，一些研究如軟件日志(software logging)或硬件日志(hardware logging)方案放松了這種寫控制，但這些方案要么需要在處理器中添加昂貴的NVM高速緩存，要么因?yàn)闊o(wú)法提供足夠的內(nèi)存讀帶寬給關(guān)鍵讀取操作而回退到低性能模式.加州大學(xué)圣克魯茲分校的Ogleari等人[71]提出了基于NVM的硬件撤銷+重做日志記錄方案undo+redo logging來(lái)放寬這種寫順序控制.該方案通過(guò)利用商業(yè)緩存中使用的回寫、寫分配策略來(lái)維護(hù)數(shù)據(jù)持久性.此外，他們?cè)谟布虚_發(fā)緩存強(qiáng)制回寫機(jī)制，以顯著降低強(qiáng)制寫入數(shù)據(jù)到NVM的性能和能量開銷.與軟件方法相比，undo+redo logging還提供了強(qiáng)大的一致性保證.

針對(duì)大多數(shù)現(xiàn)有的頁(yè)面置換方法都側(cè)重于延長(zhǎng)NVM內(nèi)存系統(tǒng)的使用壽命，而NVM內(nèi)存系統(tǒng)要么考慮能耗成本，要么處理由系統(tǒng)故障引起的一致性錯(cuò)誤，電子科技大學(xué)的Zhan等人[72]提出了一種基于NVM-DRAM混合主存儲(chǔ)系統(tǒng)的頁(yè)面替換方法稱為能量感知頁(yè)面替換EAPR，用于低功耗和一致性保證.EAPR利用頁(yè)面分組策略來(lái)提高NVM和DRAM之間的遷移效率.選擇頁(yè)面組根據(jù)其與能量相關(guān)的替代度進(jìn)行遷移.為保證頁(yè)面遷移過(guò)程的一致性，EAPR在頁(yè)面替換階段和事務(wù)提交階段設(shè)計(jì)了2種一致性保證方案.EAPR不是直接刪除日志，而是通過(guò)在提交應(yīng)用程序的事務(wù)之后修改日志的數(shù)據(jù)結(jié)構(gòu)來(lái)保證混合內(nèi)存系統(tǒng)的一致性.

3.4 小 結(jié)

數(shù)據(jù)一致性的2個(gè)基本要素是順序化和持久化，那么降低順序化開銷或持久化開銷也就等于降低了數(shù)據(jù)一致性維護(hù)開銷.降低軟件持久化開銷的工作有NV-Heaps[19]，Mnemosyne[20]，REWIND[48]，DudeTM[51]，Kamino-TX[52]，HOPS[53]，Heapo[66]等，降低硬件持久化開銷的工作有WSP[54]，Kiln[55]，Strand Persistency[58]，efficient persist barrier[59]，ARP[62]，ATOM[69]等，降低硬件順序化開銷的工作有LOC[47]，Eager Sync[49]，Strand Persistency[58]，DPO[60]等.基于檢查點(diǎn)機(jī)制的數(shù)據(jù)一致工作有NVM-checkpoints[63]，ThyNVM[64]，NICO[65]等，基于日志機(jī)制的數(shù)據(jù)一致性工作有Heapo[66]，JUSTDO logging[68]，undo+redo logging[71]等.總的來(lái)說(shuō)，面向NVM的持久性事務(wù)要減少數(shù)據(jù)一致性開銷，要么降低順序化開銷[47,49,58,60]，要么降低持久化開銷[19-20,48,51-55,58-59,62],考慮到NVM有限寫耐久性和讀寫不對(duì)稱性，需要確保NVM中數(shù)據(jù)一致性并減少NVM寫，從而提高面向NVM的持久性事務(wù)的性能.

4 基于NVM的數(shù)據(jù)一致性研究展望

非易失內(nèi)存NVM同時(shí)具有DRAM的性能和磁盤的非易失特性，由于保存在非易失內(nèi)存中的數(shù)據(jù)永久保存，因此傳統(tǒng)基于易失性DRAM的數(shù)據(jù)結(jié)構(gòu)需要重新設(shè)計(jì)以便充分利用NVM的非易失、低靜態(tài)功耗、高密度以及字節(jié)尋址等特性，需要確保NVM中數(shù)據(jù)一致性前提下并且盡量避免或減少NVM有限寫耐久性以及讀寫不對(duì)稱的影響.

4.1 持久索引層面

1) 混合內(nèi)存索引一致性

HiKV實(shí)現(xiàn)了散列和B+Tree混合索引的一致性研究，未來(lái)有可能會(huì)考慮紅黑樹、前綴樹、散列結(jié)構(gòu)、B-Tree或B+Tree及其變體等其他多種數(shù)據(jù)結(jié)構(gòu)的混合索引.混合索引的一致性研究需要保證一致性的同時(shí)最大化地利用各種數(shù)據(jù)結(jié)構(gòu)索引的優(yōu)勢(shì)并避免它們的不足.

2) 開發(fā)新的一致性的持久內(nèi)存索引

雖然Tree和散列2種數(shù)據(jù)結(jié)構(gòu)研究的比較多.未來(lái)也可能會(huì)出現(xiàn)更多的數(shù)據(jù)結(jié)構(gòu)與NVM結(jié)合做數(shù)據(jù)一致性研究工作，比如日志結(jié)構(gòu)合并樹(log-structured merge-tree，LSM-Tree)、跳表(skiplist)等.

3) NVM介質(zhì)內(nèi)部差異性的影響

由于NVM具有有限的寫入耐久性和讀寫延遲及能耗的不對(duì)稱性，需要我們?cè)诒ＷC數(shù)據(jù)一致性前提下，盡可能減少NVM系統(tǒng)的寫次數(shù)、延遲及能耗.因?yàn)楫?dāng)前基于NVM持久索引的一致性研究并未考慮底層存儲(chǔ)介質(zhì)單元的差異性，比如PCM存在SLC和MLC在可靠性和耐久性以及性能間的不同，所以基于PCM的內(nèi)存索引一致性研究需要進(jìn)一步設(shè)計(jì)針對(duì)特定介質(zhì)差異化引發(fā)對(duì)一致性機(jī)制的重新設(shè)計(jì).雖然當(dāng)前PCM最成熟，單片容量也最大，基于NVM的數(shù)據(jù)一致性工作主要針對(duì)PCM而設(shè)計(jì)，未來(lái)隨著ReRAM技術(shù)的進(jìn)一步發(fā)展成熟，那么基于ReRAM的一致性持久索引工作或許會(huì)得到眾多關(guān)注.

4.2 文件系統(tǒng)層面和持久性事務(wù)層面

大部分NVM數(shù)據(jù)一致性工作主要只考慮NVM的非易失和寫耐久性特性，很少考慮具體的底層存儲(chǔ)介質(zhì)如PCM分為SLC和MLC，而SLC PCM又存在寫0、寫1的延遲和能耗的不對(duì)稱性，SLC和MLC之間也有不同，那么如何結(jié)合具體底層存儲(chǔ)單元的數(shù)據(jù)一致性研究工作依然具有深入的研究空間.

1) NVM介質(zhì)內(nèi)部差異性對(duì)文件系統(tǒng)的影響

NVM在文件系統(tǒng)主要以3種方式存在：①NVM作為內(nèi)存設(shè)備，通過(guò)傳統(tǒng)VFS路徑的文件系統(tǒng)如BPFS[17]，PMFS[18]，F(xiàn)CFS[27]，NOVA[28]，SCMFS[40]，HiNFS[42]等；②NVM作為塊設(shè)備的文件系統(tǒng)如Shortcut-JFS[73]，On-demand Snapshot[74]等；③使用用戶庫(kù)方式繞過(guò)VFS直接訪問(wèn)NVM的文件系統(tǒng)如Aerie[46]等.NVM介質(zhì)內(nèi)部差異性將會(huì)影響原有針對(duì)NVM共性而設(shè)計(jì)的文件系統(tǒng)研究工作，需要重新設(shè)計(jì)新的一致性研究方案.

2) NVM介質(zhì)內(nèi)部差異性對(duì)持久性事務(wù)的影響

基于NVM的持久性事務(wù)一致性工作分別為降低持久化開銷和降低順序化開銷.降低NVM持久化開銷的工作有DudeTM[51]，Kamino-TX[52]，HOPS[53]，WSP[54]，Kiln[55]等，降低順序化的開銷工作的有Mnemosyne[20]，LOC[47]，Eager Sync[49]，HOPS[53]，Strand Persistency[58]，DPO[60]等.這些工作主要針對(duì)NVM共性設(shè)計(jì)，由于以PCM為主的NVM介質(zhì)存在內(nèi)部差異性，基于NVM的持久性事務(wù)的數(shù)據(jù)一致性研究需要針對(duì)不同的存儲(chǔ)介質(zhì)單元采用不同的策略保障一致性，同時(shí)盡可能提升NVM系統(tǒng)的性能和壽命并降低能耗和讀寫延遲.

5 總 結(jié)

以PCM為代表的非易失內(nèi)存(NVM)具有非易失、高密度以及低靜態(tài)功耗，使得NVM成為DRAM的有力替代者或與DRAM共同作為系統(tǒng)主存.新型存儲(chǔ)器給系統(tǒng)結(jié)構(gòu)和軟件設(shè)計(jì)帶來(lái)了新的機(jī)遇和挑戰(zhàn).由于現(xiàn)代處理器或內(nèi)存控制器可能會(huì)重排序內(nèi)存寫，因此，系統(tǒng)故障時(shí)的部分更新或重排序?qū)憰?huì)導(dǎo)致NVM中數(shù)據(jù)的不一致性問(wèn)題.當(dāng)前基于NVM的數(shù)據(jù)一致性被廣泛研究，我們從持久索引層面、文件系統(tǒng)層面和持久性事務(wù)等方面分別介紹了相關(guān)工作，并且給出了未來(lái)基于NVM數(shù)據(jù)一致性方面可能重要的研究發(fā)展方向.NVM固有的缺點(diǎn)如PCM讀寫延遲高、讀寫不對(duì)稱和有限的擦寫次數(shù)等，需要研究人員在性能和開銷之間尋找最佳的平衡點(diǎn).為了充分利用NVM實(shí)現(xiàn)更好的數(shù)據(jù)一致性，可能需要從應(yīng)用層、軟件層以及硬件層等多角度多層面協(xié)同設(shè)計(jì).