石 偉 汪東升，2

1（清華大學(xué)計算機(jī)科學(xué)與技術(shù)系 北京 100084）2（清華信息科學(xué)與技術(shù)國家實(shí)驗(yàn)室（籌） 北京 100084）（shiwei09＠m(xù)ails．tsinghua．edu．cn）

基于非易失存儲器的事務(wù)存儲系統(tǒng)綜述

石 偉1汪東升1，2

1（清華大學(xué)計算機(jī)科學(xué)與技術(shù)系 北京 100084）2（清華信息科學(xué)與技術(shù)國家實(shí)驗(yàn)室（籌） 北京 100084）（shiwei09＠m(xù)ails．tsinghua．edu．cn）

隨著非易失存儲器的出現(xiàn)和廣泛使用，存儲體系結(jié)構(gòu)正在發(fā)生根本改變．傳統(tǒng)數(shù)據(jù)庫系統(tǒng)與文件系統(tǒng)事務(wù)處理技術(shù)大多基于磁盤設(shè)備，設(shè)計之初并未考慮非易失存儲器特性．為了充分利用非易失存儲器特性，縮小計算機(jī)系統(tǒng)的I?O性能與CPU處理性能之間的差距，基于非易失存儲器的事務(wù)存儲系統(tǒng)與技術(shù)成為了研究熱點(diǎn)．首先討論了軟件層事務(wù)處理技術(shù)的現(xiàn)狀，分別介紹了傳統(tǒng)數(shù)據(jù)庫系統(tǒng)與文件系統(tǒng)事務(wù)處理常用技術(shù)；然后依據(jù)閃存和相變內(nèi)存進(jìn)行劃分，對現(xiàn)有基于非易失存儲器的事務(wù)存儲系統(tǒng)與技術(shù)進(jìn)行了討論；最后給出了基于非易失存儲器的事務(wù)存儲系統(tǒng)研究展望．在基于閃存的事務(wù)存儲相關(guān)研究中，首先分析了使用傳統(tǒng)設(shè)備接口閃存設(shè)備加速事務(wù)處理的系統(tǒng)設(shè)計，然后重點(diǎn)分析了基于專用事務(wù)接口的事務(wù)閃存存儲系統(tǒng)研究，并對基于閃存的事務(wù)存儲系統(tǒng)不同研究進(jìn)行了比較．在基于相變內(nèi)存的事務(wù)存儲相關(guān)研究中，分別分析并比較了相變內(nèi)存在主存環(huán)境和外存環(huán)境提供事務(wù)處理的技術(shù)，重點(diǎn)討論了日志與緩存融合技術(shù)、細(xì)粒度日志技術(shù)等關(guān)鍵問題．

非易失性存儲器；閃存；相變存儲器；事務(wù)處理；事務(wù)存儲系統(tǒng)；I?O棧

Fig．1 Current states of development of RRAM，MRAM and PCM［21］．圖1 RRAM，MRAM，PCM目前發(fā)展?fàn)顟B(tài)

事務(wù)作為一個抽象概念，最早在數(shù)據(jù)庫領(lǐng)域中被提出［1－3］，表示具有原子性（atomicity）、一致性（consistency）、隔離性（isolation）和持久性（durability），也即ACID特性的一組數(shù)據(jù)庫操作．這一抽象概念主要用于保證數(shù)據(jù)庫正常工作時對共享存儲資源的隔離性以及異常崩潰后的數(shù)據(jù)正確性．為了在系統(tǒng)或進(jìn)程崩潰等異常情況下保證事務(wù)特性，Mohan等人［4］提出了ARIES算法，使用了寫前日志（write－ahead logging，WAL）方法將數(shù)據(jù)寫入數(shù)據(jù)庫．文件系統(tǒng)相比數(shù)據(jù)庫系統(tǒng)對事務(wù)的概念進(jìn)行了簡化，只保證異常情況發(fā)生后恢復(fù)數(shù)據(jù)的一致性，采用的技術(shù)一般包括日志（journaling）［56］、影子頁（shadow paging）［7］以及軟更新（soft update）［8］技術(shù)．此外，事務(wù)概念也被擴(kuò)展到計算機(jī)體系結(jié)構(gòu)和編譯領(lǐng)域以解決多核共享內(nèi)存體系結(jié)構(gòu)下并行程序內(nèi)存訪問隔離性等問題［9－10］．

數(shù)據(jù)庫系統(tǒng)和文件系統(tǒng)中的事務(wù)處理技術(shù)經(jīng)過不斷的發(fā)展，出現(xiàn)了很多在特定場景下的高效事務(wù)機(jī)制保證算法；另一方面，由于底層存儲介質(zhì)從磁帶、軟盤到磁盤的不斷發(fā)展，事務(wù)處理技術(shù)也不斷地被改進(jìn)以適應(yīng)底層存儲設(shè)備的變化．

近年來，隨著以閃存為主的非易失存儲器（nonvolatile memory，NVM）芯片存儲密度的提升與價格的下降，具有不同設(shè)備接口、基于非易失性存儲器的高性能存儲設(shè)備層出不窮．除了已經(jīng)量產(chǎn)的閃存之外，目前即將投入量產(chǎn)以及仍處于實(shí)驗(yàn)階段的新型非易失存儲介質(zhì)還包括相變存儲器（phase change memory，PCM）［1115］、阻變存儲器（resistive RAM，RRAM或ReRAM）［16－18］及磁存儲器（magnetic RAM，MRAM）［19－20］等．圖1是研究機(jī)構(gòu)Gartner在2013年半導(dǎo)體與電子研究報告中給出的幾種新型非易失存儲器目前的發(fā)展?fàn)顟B(tài)．從圖1可以看出，相變存儲器目前即將量產(chǎn)，但阻變存儲器和磁存儲器根據(jù)其調(diào)研距離實(shí)用化還有大約5～10年的時間．這些非易失存儲器正在從根本上改變由磁介質(zhì)構(gòu)成的傳統(tǒng)存儲體系結(jié)構(gòu)，并進(jìn)一步縮小計算機(jī)系統(tǒng)的I?O性能與CPU處理性能之間的差距．本文中討論的非易失存儲器主要包括目前已經(jīng)量產(chǎn)并被廣泛使用的閃存存儲器以及即將量產(chǎn)的相變存儲器．

對于包括閃存和相變內(nèi)存在內(nèi)的非易失存儲介質(zhì)，其自身存儲特性以及構(gòu)成存儲設(shè)備后內(nèi)部工作機(jī)制與傳統(tǒng)存儲設(shè)備存在本質(zhì)差異．例如閃存具有異地更新（out－of－place update）特性、相變內(nèi)存具有字節(jié)尋址（byte－addressed）特性，而現(xiàn)有的數(shù)據(jù)庫系統(tǒng)與文件系統(tǒng)事務(wù)處理技術(shù)大部分基于磁盤設(shè)備進(jìn)行設(shè)計，并沒有充分利用這些特性，這導(dǎo)致現(xiàn)有的軟件層事務(wù)處理技術(shù)運(yùn)行在非易失存儲設(shè)備上時會造成重復(fù)設(shè)計、性能較低以及寫放大（write amplification）等問題．

本文首先對傳統(tǒng)軟件層事務(wù)處理技術(shù)進(jìn)行了介紹；接著，依據(jù)已被廣泛使用的閃存和即將量產(chǎn)的相變內(nèi)存進(jìn)行劃分，對基于新型非易失存儲器的事務(wù)存儲系統(tǒng)與技術(shù)相關(guān)研究進(jìn)行了討論；最后給出了非易失存儲器在事務(wù)存儲系統(tǒng)中應(yīng)用的研究展望．

1 軟件層事務(wù)處理技術(shù)現(xiàn)狀

軟件層事務(wù)處理技術(shù)一直是研究的熱點(diǎn)，由于這類技術(shù)應(yīng)用在系統(tǒng)I?O棧的不同層，其技術(shù)細(xì)節(jié)不盡相同，按照應(yīng)用場景的不同可以分為數(shù)據(jù)庫系統(tǒng)事務(wù)處理技術(shù)以及文件系統(tǒng)事務(wù)處理技術(shù)．其中，文件系統(tǒng)事務(wù)處理技術(shù)一般只保證一致性和持久性，對原子性和隔離性不做強(qiáng)制要求．

1．1 數(shù)據(jù)庫系統(tǒng)事務(wù)處理技術(shù)

1．1．1 ARIES

在傳統(tǒng)的關(guān)系型數(shù)據(jù)庫中，一個數(shù)據(jù)庫事務(wù)通常包含若干條SQL語句，這些SQL語句經(jīng)過數(shù)據(jù)庫邏輯層的翻譯之后，表現(xiàn)為對底層大量數(shù)據(jù)塊的讀取和寫入操作．事務(wù)處理技術(shù)正是保證這些底層塊設(shè)備數(shù)據(jù)塊的變化，要么全部體現(xiàn)在數(shù)據(jù)庫中，要么由于事務(wù)被中止（abort）或回滾（rollback）而在數(shù)據(jù)庫中沒有體現(xiàn)，而不存在只修改了部分?jǐn)?shù)據(jù)塊的中間狀態(tài)．通常，數(shù)據(jù)庫中的事務(wù)處理機(jī)制由存儲引擎負(fù)責(zé)．

數(shù)據(jù)庫存儲引擎正常運(yùn)行時，為上層提供事務(wù)支持并不困難．但是，當(dāng)數(shù)據(jù)庫系統(tǒng)崩潰甚至主機(jī)斷電時，由于系統(tǒng)緩存甚至磁盤緩沖區(qū)中的數(shù)據(jù)丟失，底層存儲設(shè)備上的數(shù)據(jù)信息在崩潰后的狀態(tài)并不確定．要保證系統(tǒng)崩潰后恢復(fù)的數(shù)據(jù)仍然滿足事務(wù)的ACID特性，需要在系統(tǒng)崩潰后數(shù)據(jù)恢復(fù)時進(jìn)行大量的額外工作．

IBM的研究人員Mohan等人［4］提出了ARIES（algorithm for recovery and isolation exploiting semantics）恢復(fù)算法，用以在異常情況保證數(shù)據(jù)庫的事務(wù)機(jī)制．ARIES使用單獨(dú)劃分的一塊磁盤區(qū)域作為日志區(qū)域，在將數(shù)據(jù)寫入到數(shù)據(jù)庫之前，首先將新數(shù)據(jù)以及舊數(shù)據(jù)一并寫入到日志區(qū)域中，并使用事務(wù)標(biāo)識加上標(biāo)簽．當(dāng)日志區(qū)域大小達(dá)到某一閾值或每隔一定時間后，日志區(qū)域中的數(shù)據(jù)塊被刷入到數(shù)據(jù)庫中并設(shè)置檢查點(diǎn)（checkpoint），檢查點(diǎn)信息中包含當(dāng)前系統(tǒng)中運(yùn)行的事務(wù)狀態(tài)．

如圖2所示，當(dāng)系統(tǒng)異常崩潰后，恢復(fù)分3步進(jìn)行：分析（analysis）、重做（redo）和撤銷（undo）．首先對檢查點(diǎn)后的日志區(qū)域進(jìn)行分析，結(jié)合檢查點(diǎn)信息，得到系統(tǒng)崩潰時系統(tǒng)中所有事務(wù)的狀態(tài)；第2步重做操作將所有可能的在系統(tǒng)崩潰時還未寫入數(shù)據(jù)庫的數(shù)據(jù)塊重新寫入；最后，使用日志中存有的舊數(shù)據(jù)覆蓋未提交事務(wù)的數(shù)據(jù)進(jìn)行撤銷操作．通過這種寫前日志（WAL）的方法，ARIES保證在異常情況發(fā)生后可以根據(jù)日志及檢查點(diǎn)信息將數(shù)據(jù)庫恢復(fù)到滿足事務(wù)語義的狀態(tài)．

Fig．2 The three passes of ARIES restart［22］．圖2 ARIES重啟后恢復(fù)的3步工作

使用ARIES算法保證事務(wù)語義時，數(shù)據(jù)在寫入數(shù)據(jù)庫之前，需先寫入到日志區(qū)域中，造成了額外的寫操作．在性能上，雖然ARIES造成了重復(fù)寫入，但是由于將原先對數(shù)據(jù)庫的隨機(jī)寫轉(zhuǎn)化為了對日志區(qū)域的連續(xù)寫入，同時檢查點(diǎn)寫入在后臺進(jìn)行．由于磁盤設(shè)備隨機(jī)I?O性能遠(yuǎn)遠(yuǎn)低于連續(xù)I?O性能，所以對于磁盤設(shè)備，ARIES雖然存在額外寫但卻帶來了性能提升．在目前主流數(shù)據(jù)庫中，MySQL InnoDB存儲引擎［23］、PostgreSQL［24］、SQL Server［25］以及Oracle［26］均采用類似ARIES的事務(wù)處理機(jī)制．

1．1．2 嵌入式數(shù)據(jù)庫中的事務(wù)處理技術(shù)

隨著移動設(shè)備的流行，嵌入式數(shù)據(jù)庫在各種移動端應(yīng)用中廣泛流行．相比傳統(tǒng)關(guān)系型數(shù)據(jù)庫，嵌入式數(shù)據(jù)庫更加輕量，同時處于文件系統(tǒng)層之上．

如圖3所示，在目前應(yīng)用最為廣泛的嵌入式數(shù)據(jù)庫SQLite中，使用2種不同的日志模式保證數(shù)據(jù)處理的事務(wù)性．一種稱為回滾模式（rollback mode），另一種稱為寫前日志模式（WAL mode）．

由于處于文件系統(tǒng)層之上，這2種日志模式均使用文件系統(tǒng)提供的fsync調(diào)用，并假設(shè)fsync具有原子性．圖3還詳細(xì)說明了SQLite的2種事務(wù)處理模式的具體流程，在回滾模式下，SQLite對數(shù)據(jù)庫文件進(jìn)行修改時，首先創(chuàng)建一個回滾文件，然后將數(shù)據(jù)庫文件被修改部分舊數(shù)據(jù)先寫入回滾文件，繼而對數(shù)據(jù)庫文件進(jìn)行修改，最后刪除回滾文件．寫前日志模式則與ARIES非常相似，不同的是，這里寫前日志是以文件的形式而不是磁盤區(qū)域的形式存在．

1．2 文件系統(tǒng)事務(wù)處理技術(shù)

文件系統(tǒng)在系統(tǒng)I?O棧中處于核心的位置，向上負(fù)責(zé)處理應(yīng)用層的各種系統(tǒng)調(diào)用，向下負(fù)責(zé)管理底層塊設(shè)備．通常情況下，由于單個文件系統(tǒng)調(diào)用涉及到對許多底層數(shù)據(jù)塊的操作，在系統(tǒng)崩潰等異常情況下操作可能會被中斷．文件系統(tǒng)同一時刻可能處理著大量并發(fā)的文件系統(tǒng)調(diào)用，所以異常情況可能會造成大量文件系統(tǒng)調(diào)用處于未完成的狀態(tài)，這會給文件系統(tǒng)帶來嚴(yán)重的一致性問題．

為了解決文件系統(tǒng)在系統(tǒng)崩潰等異常情況下的一致性問題，數(shù)據(jù)庫系統(tǒng)事務(wù)概念被引入到文件系統(tǒng)中并被進(jìn)行了簡化．文件系統(tǒng)將一個或多個系統(tǒng)調(diào)用封裝成一個事務(wù)，但是由于文件系統(tǒng)并不需要強(qiáng)制保證原子性和隔離性，所以文件系統(tǒng)中事務(wù)是一種弱事務(wù)．為了實(shí)現(xiàn)這種弱事務(wù)，目前主流文件系統(tǒng)使用的方法大致可以分為3類：日志、影子頁和軟更新．

1．2．1 日志

日志（journaling）借鑒了ARIES算法中的寫前日志（WAL），同樣也在底層塊設(shè)備上使用單獨(dú)的區(qū)域作為日志區(qū)域，為了避免覆蓋舊數(shù)據(jù)，先將數(shù)據(jù)寫入到日志區(qū)域，而后再將數(shù)據(jù)寫入到文件系統(tǒng)中．與寫前日志不同的是，文件系統(tǒng)日志通常提供不同的日志級別，以Ext3文件系統(tǒng)為例，可以選擇日志級別為寫回（writeback）、順序（ordered）和數(shù)據(jù)（data），由弱到強(qiáng)分別表示不作任何日志、只對元數(shù)據(jù)進(jìn)行日志以及對元數(shù)據(jù)和數(shù)據(jù)進(jìn)行日志，缺省選項(xiàng)為順序．當(dāng)日志級別為順序時，可以保證元數(shù)據(jù)一致性；而選擇日志級別為數(shù)據(jù)時，可以保證數(shù)據(jù)的版本一致性．使用日志技術(shù)的文件系統(tǒng)包括Ext3?4［6］，NTFS［28］，ReiserFS［28］，XFS［5］等．

Fig．3 SQLite journal modes［27］．圖3 SQLite不同日志模式

1．2．2 影子頁

影子頁是虛擬視圖技術(shù)的一種實(shí)現(xiàn)，采用了對數(shù)據(jù)異地更新之后更新元數(shù)據(jù)的策略．文件系統(tǒng)在對數(shù)據(jù)進(jìn)行修改時，并不直接對該數(shù)據(jù)進(jìn)行本地更新（in－place update），而是將新數(shù)據(jù)寫入到別的地方，即避免數(shù)據(jù)覆蓋．除了新寫入的數(shù)據(jù)之外，與新數(shù)據(jù)相關(guān)的文件系統(tǒng)元數(shù)據(jù)也需要修改，由于文件系統(tǒng)在塊設(shè)備上是一個樹形結(jié)構(gòu)，所以由底向上一層層地異地寫入新的數(shù)據(jù)，直到修改樹根部分最后一個指針數(shù)據(jù)塊，完成對新數(shù)據(jù)的寫入．由于在寫入最后一個指針數(shù)據(jù)塊之前，文件系統(tǒng)并沒有任何的改變，而寫入之后，則本次寫操作完成．使用影子頁技術(shù)的文件系統(tǒng)包括ZFS［29］和Brtfs［30］等．

1．2．3 軟更新

軟更新首先分析文件系統(tǒng)調(diào)用涉及到的所有數(shù)據(jù)塊之間的依賴關(guān)系，而后將數(shù)據(jù)塊按照一定順序?qū)懭?，這個順序可以保證異常中斷后已經(jīng)寫入的數(shù)據(jù)或者元數(shù)據(jù)與文件系統(tǒng)其他元數(shù)據(jù)一致．在具體實(shí)現(xiàn)中，為了保證這一點(diǎn)，在涉及到依賴沖突時，需要進(jìn)行回滾（roll back）或者前滾（roll forward）操作．在Unix的快速文件系統(tǒng)（FFS）中實(shí)現(xiàn)軟更新時，可以將性能提升到內(nèi)存文件系統(tǒng)的級別［8，31］．但是在文件系統(tǒng)中實(shí)現(xiàn)軟更新嚴(yán)格的順序規(guī)則非常困難，目前使用軟更新技術(shù)的有FreeBSD的UFS［32］文件系統(tǒng)．

1．2．4 其他技術(shù)

近年來，在文件系統(tǒng)事務(wù)處理研究中出現(xiàn)了很多新技術(shù)．紐約大學(xué)的Spillane等人［33］提出了一種事務(wù)型文件系統(tǒng)Valor，向上層直接提供強(qiáng)事務(wù)原語．在具體實(shí)現(xiàn)中，Valor使用了類寫前日志技術(shù)避免對舊數(shù)據(jù)的覆蓋寫，在虛擬文件系統(tǒng)（virtual file system，VFS）中加入了事務(wù)鎖機(jī)制，保證了文件系統(tǒng)調(diào)用之間的隔離性．使用Valor提供的接口，上層軟件可以在文件系統(tǒng)層實(shí)現(xiàn)嚴(yán)格的ACID事務(wù)邏輯．此外，威斯康辛大學(xué)的Wisdom小組的研究人員提出了基于反向指針的文件系統(tǒng)NoFS［34］以及快速恢復(fù)文件系統(tǒng)一致性的算法Ffsck［35］．NoFS在傳統(tǒng)文件系統(tǒng)樹狀結(jié)構(gòu)中加入反向指針，包括目錄樹i節(jié)點(diǎn)（inode）之間的反向指針以及數(shù)據(jù)塊與i節(jié)點(diǎn)之間的反向指針．當(dāng)文件系統(tǒng)操作由于系統(tǒng)崩潰或斷電等原因被中斷后，NoFS可以通過正常的文件系統(tǒng)數(shù)據(jù)塊指針以及額外的反向指針對文件系統(tǒng)一致性進(jìn)行驗(yàn)證，并恢復(fù)到一致狀態(tài)．Ffsck則通過在文件系統(tǒng)所管理的底層塊設(shè)備上設(shè)置新的間接區(qū)域（indirect region）存放文件間接塊（indirect blocks）以及目錄數(shù)據(jù)塊，恢復(fù)時順序讀取間接區(qū)域內(nèi)的數(shù)據(jù)塊進(jìn)行驗(yàn)證，從而提高了恢復(fù)速度．

1．3 小 結(jié)

數(shù)據(jù)庫系統(tǒng)正常運(yùn)行時，事務(wù)處理機(jī)制負(fù)責(zé)事務(wù)間的數(shù)據(jù)隔離，并保證對舊數(shù)據(jù)的保護(hù)．當(dāng)斷電、系統(tǒng)崩潰或進(jìn)程崩潰等異常狀態(tài)發(fā)生后，事務(wù)處理機(jī)制需要中止未完成的事務(wù)，使用原先的舊數(shù)據(jù)清除沒有完成的事務(wù)，從而在底層存儲設(shè)備中將被故障中斷的事務(wù)狀態(tài)清理干凈．

數(shù)據(jù)庫系統(tǒng)主要采用基于寫前日志的技術(shù)，首先將新數(shù)據(jù)寫入到日志區(qū)域中，避免了對舊數(shù)據(jù)的覆蓋，當(dāng)事務(wù)提交后，再次寫入到數(shù)據(jù)庫中．這樣的設(shè)計可以將隨機(jī)寫入轉(zhuǎn)換為對日志區(qū)域的順序?qū)?，對于磁盤友好，但由于接近1∶1的額外的寫操作，對閃存設(shè)備卻會造成壽命問題．

與數(shù)據(jù)庫系統(tǒng)相比，文件系統(tǒng)本身并不負(fù)責(zé)數(shù)據(jù)隔離，而是由操作系統(tǒng)提供的文件鎖機(jī)制提供隔離性．文件系統(tǒng)主要保證在斷電或者系統(tǒng)崩潰等異常狀態(tài)后的數(shù)據(jù)一致性，現(xiàn)有的文件系統(tǒng)主要采用的是日志、影子頁和軟更新等技術(shù)．日志和影子頁技術(shù)避免了對數(shù)據(jù)進(jìn)行覆蓋寫，軟更新則使用復(fù)雜的依賴性保證數(shù)據(jù)一致性．日志技術(shù)也在一定程度上造成了對底層設(shè)備的重復(fù)寫入．

2 基于閃存的事務(wù)存儲系統(tǒng)與技術(shù)

由閃存芯片組成的固態(tài)硬盤（solid－state drive，SSD）等閃存設(shè)備由于內(nèi)部并行性等原因使得其I?O性能無論是帶寬還是延遲相比磁盤都有顯著地提升．為了兼容已有系統(tǒng)，固態(tài)硬盤大多采用傳統(tǒng)磁盤設(shè)備接口，但是在內(nèi)部工作原理上，閃存設(shè)備與磁盤設(shè)備有本質(zhì)區(qū)別，傳統(tǒng)的設(shè)備接口限制了閃存設(shè)備特性在事務(wù)處理技術(shù)上的發(fā)揮．

本節(jié)從2方面介紹基于閃存的事務(wù)存儲系統(tǒng)與技術(shù)，首先介紹的是使用傳統(tǒng)接口的閃存設(shè)備進(jìn)行事務(wù)處理加速技術(shù)；接著介紹打破接口限制、擴(kuò)展現(xiàn)有設(shè)備接口，利用軟硬件協(xié)同的閃存事務(wù)處理系統(tǒng)．

2．1 閃存設(shè)備特性

閃存作為一種持久化的可擦除編程存儲器，主要分為NOR閃存與NAND閃存．NOR閃存存儲單元使用NOR邏輯門，支持字節(jié)粒度的讀寫以及片上執(zhí)行（execute on chip），程序可以在NOR閃存芯片內(nèi)執(zhí)行；NAND閃存則使用NAND邏輯門作為存儲單元并支持以頁（page）為單位的讀寫．與NOR閃存相比，NAND閃存具有存儲密度高、成本低等優(yōu)點(diǎn)，因而被廣泛使用在存儲領(lǐng)域．NAND閃存根據(jù)單元存儲密度不同被分為SLC（single－level cell），MLC（multi－level cell）和TLC（triple－level cell）閃存［36－37］．下文中所討論的閃存如無特殊說明，均為NAND閃存．

NAND閃存的編程為單向編程，當(dāng)電子被注入到存儲單元后，即表示從狀態(tài)“1”寫為狀態(tài)“0”，但不支持從狀態(tài)“0”寫為狀態(tài)“1”．NAND閃存在重新寫入一個頁面之前，需要進(jìn)行擦除（erase）操作．與讀、寫不同的是，NAND閃存擦除單位為塊（block）．通常，閃存頁的大小為4KB或更大，而閃存塊包含256個或更多閃存頁．每個閃存頁除了數(shù)據(jù)區(qū)之外，根據(jù)頁空間大小還包含64～256B不等的頁帶外區(qū)域（out－of－band area，OOB）用于存放ECC、邏輯頁地址等信息．閃存的各個操作之間延遲相差較大，單個頁讀操作平均延遲為25μs，寫操作平均延遲為200μs，但是擦除操作的平均延遲長達(dá)1．5ms［38］．此外NAND閃存擦除操作有限，SLC閃存可擦寫100 000次左右，MLC可擦寫約10 000次，但TLC僅可擦寫約1 000次［39－40］．

為避免擦除操作造成的延遲并使擦除操作對上層透明從而兼容傳統(tǒng)設(shè)備接口，閃存采用異地更新（out－of－place update）的策略對頁面進(jìn)行重寫，并引入了一層重定向（indirection）向上層軟件提供統(tǒng)一的邏輯地址空間．當(dāng)對某個邏輯頁重新寫入數(shù)據(jù)時，首先分配一個空白物理頁并寫入數(shù)據(jù)，之后邏輯頁被映射到新寫入的物理頁，原先所指向的物理頁被標(biāo)記為無效頁面，并被定期地進(jìn)行垃圾回收（garbage collection，GC）．在閃存設(shè)備中，管理邏輯地址到物理地址映射的這一層重定向被稱為閃存轉(zhuǎn)換層（flash translation layer，F(xiàn)TL）．除了地址映射，閃存轉(zhuǎn)換層還負(fù)責(zé)垃圾回收以及磨損均衡等機(jī)制．根據(jù)不同的設(shè)計，閃存轉(zhuǎn)換層可以被實(shí)現(xiàn)在閃存設(shè)備固件中，也可以被實(shí)現(xiàn)在閃存設(shè)備驅(qū)動中．

對于事務(wù)處理，得益于閃存設(shè)備本身的高性能，使用傳統(tǒng)接口的閃存設(shè)備可得到一定程度的性能提升，但是這并沒有發(fā)揮出閃存設(shè)備全部的能力．目前主流的數(shù)據(jù)庫系統(tǒng)與文件系統(tǒng)是基于磁盤塊設(shè)備進(jìn)行設(shè)計并優(yōu)化的，而閃存設(shè)備由于內(nèi)部閃存轉(zhuǎn)換層的存在，在內(nèi)部機(jī)制上與磁盤設(shè)備完全不同，這使得針對磁盤設(shè)計的事務(wù)存儲技術(shù)沒有充分利用閃存設(shè)備的特點(diǎn)．現(xiàn)有在基于傳統(tǒng)接口閃存設(shè)備上構(gòu)建的事務(wù)存儲系統(tǒng)存在的不足主要體現(xiàn)在以下3方面：

1）設(shè)計冗余

事務(wù)處理中的寫前日志技術(shù)及虛擬視圖技術(shù)本質(zhì)上是為了保護(hù)活動事務(wù)原有數(shù)據(jù)不被覆蓋，這樣在事務(wù)主動撤銷或者由于錯誤造成的回滾時可以將所修改的數(shù)據(jù)恢復(fù)到原有狀態(tài)．而閃存設(shè)備的異地更新特性與軟件層事務(wù)處理機(jī)制保護(hù)舊數(shù)據(jù)的設(shè)計有異曲同工之處．這樣，異地更新這一設(shè)計同時出現(xiàn)在了閃存轉(zhuǎn)換層以及軟件層事務(wù)處理技術(shù)中．雖然這2處異地更新的目地和效果均不相同，但2處異地更新存在設(shè)計上的冗余，增加了數(shù)據(jù)管理和存儲的開銷，同時也可能造成性能優(yōu)化策略存在沖突．

2）策略沖突

與設(shè)計冗余相比，策略沖突造成的問題更加嚴(yán)重．以日志文件系統(tǒng)為例，在寫文件之前，首先將寫入的數(shù)據(jù)與修改的文件元數(shù)據(jù)寫入存儲設(shè)備日志區(qū)域中，這種基于磁盤設(shè)計的寫入策略無形中增加了一倍以上的數(shù)據(jù)寫入量，會對閃存設(shè)備壽命造成損害．

3）協(xié)同缺失

傳統(tǒng)存儲設(shè)備接口相對簡單，沒有協(xié)同分工的能力．閃存設(shè)備內(nèi)部具有一定的處理能力，邏輯較復(fù)雜，由于傳統(tǒng)設(shè)備接口的限制，閃存設(shè)備內(nèi)部特性完全對上層系統(tǒng)透明．內(nèi)部透明性使得閃存設(shè)備可以替換磁盤設(shè)備并兼容遺留系統(tǒng)軟件，但同時也完全杜絕了軟硬件協(xié)同分工的可能性，將全部工作集中在軟件層，沒有充分利用設(shè)備性能進(jìn)行協(xié)同處理．

傳統(tǒng)接口閃存設(shè)備使用包括SATA，SAS等在內(nèi)的現(xiàn)有磁盤接口，事務(wù)處理機(jī)制中簡單使用傳統(tǒng)接口閃存設(shè)備替換磁盤不能充分發(fā)揮閃存設(shè)備異地更新的特性，因而研究人員對現(xiàn)有閃存設(shè)備接口進(jìn)行了擴(kuò)展，提出了擴(kuò)展接口閃存設(shè)備用于事務(wù)處理．?dāng)U展接口閃存設(shè)備在內(nèi)部將閃存異地更新特性與事務(wù)處理技術(shù)相整合，并以接口的形式對軟件層開放，軟件層可以直接使用由設(shè)備提供的事務(wù)處理接口進(jìn)行事務(wù)處理，從而利用軟硬件協(xié)同的方式提升事務(wù)處理系統(tǒng)的整體性能．

接下來的2小節(jié)中，首先將介紹相對簡單的基于傳統(tǒng)接口的閃存設(shè)備事務(wù)處理相關(guān)研究，接著重點(diǎn)介紹需要對設(shè)備接口進(jìn)行擴(kuò)充的基于專用事務(wù)接口的事務(wù)閃存存儲系統(tǒng)．

2．2 基于傳統(tǒng)接口的閃存設(shè)備事務(wù)處理

基于傳統(tǒng)接口的閃存設(shè)備，包括USB閃存盤以及SATA，SAS固態(tài)硬盤相比磁盤具有較好的I?O性能．在傳統(tǒng)事務(wù)處理技術(shù)中，數(shù)據(jù)緩沖區(qū)（data buffer）在內(nèi)存中緩存最近被數(shù)據(jù)庫訪問的塊設(shè)備數(shù)據(jù)，日志緩沖區(qū)（log buffer）在內(nèi)存中緩存事務(wù)產(chǎn)生的日志數(shù)據(jù)．對于這2個緩沖區(qū)，都可以使用閃存設(shè)備進(jìn)行數(shù)據(jù)持久化以加速事務(wù)處理．

2．2．1 基于USB閃存盤的FlashLogging［41］

Intel的研究人員提出的FlashLogging技術(shù)，使用了大量USB閃存盤并發(fā)處理日志I?O請求，提高了同步日志處理的性能，從而提高了系統(tǒng)的事務(wù)處理能力．

FlashLogging使用生產(chǎn)者消費(fèi)者模式進(jìn)行設(shè)計，內(nèi)存中的日志緩沖作為生產(chǎn)者，不同的USB閃存設(shè)備作為消費(fèi)者．任意時刻內(nèi)存日志緩沖區(qū)需要寫入日志數(shù)據(jù)時，只要在系統(tǒng)掛載的USB閃存盤中找到空閑的寫入，繼而再將數(shù)據(jù)寫入到磁盤中．由于多個閃存盤提高了日志寫入的并發(fā)性，從而提高了事務(wù)吞吐．但是在恢復(fù)時，F(xiàn)lashLogging需要掃描所有的USB閃存盤，所以恢復(fù)代價也較大．

2．2．2 混合存儲事務(wù)處理

雖然閃存設(shè)備具有較高性能，但是相比磁盤成本也較高，混合存儲事務(wù)處理技術(shù)的研究目的在于充分發(fā)揮閃存設(shè)備的高性能與磁盤設(shè)備的大容量，做到高效融合．滑鐵盧大學(xué)的研究人員提出了使用磁盤（hard disk drive，HDD）和SSD的混合型存儲系統(tǒng)對MySQL InnoDB存儲引擎事務(wù)處理機(jī)制進(jìn)行加速的設(shè)計［42］，并在此基礎(chǔ)上提出了基于讀寫代價的數(shù)據(jù)庫緩沖區(qū)調(diào)整算法，將緩沖區(qū)數(shù)據(jù)根據(jù)讀寫代價分別存放于HDD和SSD中，以獲得盡可能多的性能收益．

圖4是混合存儲系統(tǒng)事務(wù)處理的結(jié)構(gòu)圖，由于數(shù)據(jù)庫緩沖區(qū)中的數(shù)據(jù)被寫回到SSD之后再讀取比寫回HDD再讀取的成本要低，但是SSD的空間相對較小，所以將性能收益更高的數(shù)據(jù)放置在SSD上可以更加有效地提升整體性能．為了衡量緩沖區(qū)中的每個頁p存放到SSD上的潛在性能收益B（p），緩沖區(qū)調(diào)整算法采用了下列公式進(jìn)行量化：

其中，r（p）和w（p）分別代表頁p曾經(jīng)被寫和讀的次數(shù)，RD和RS分別代表硬盤和SSD的讀該頁需要的時間，而WD和WS分別代表硬盤和SSD寫該頁需要的時間．由于硬盤讀寫時間與工作負(fù)載相關(guān)，所以采用了平均值代替．

Fig．4 Hybrid storage system for DBMS［42］．圖4 混合存儲數(shù)據(jù)庫系統(tǒng)

上述方法應(yīng)用于混合存儲系統(tǒng)可以有效地提升數(shù)據(jù)庫系統(tǒng)的事務(wù)處理性能，同時有效利用了磁盤的大容量．但是由于其本質(zhì)上是將讀寫次數(shù)較多的頁緩存于固態(tài)硬盤中，從一定程度上將會造成閃存設(shè)備的寫磨損加?。?/p>

2．2．3 多用戶環(huán)境的固態(tài)硬盤事務(wù)處理

威斯康辛大學(xué)和NEC公司研究人員對多租戶（multi－tenant）環(huán)境下使用固態(tài)硬盤事務(wù)處理的3種不同設(shè)計進(jìn)行了性能測試［43］．與磁盤設(shè)備不同的是，當(dāng)使用固態(tài)硬盤作為介質(zhì)時，使用虛擬化技術(shù)提供多租戶的用例事務(wù)處理性能沒有明顯下降．

由于虛擬化技術(shù)提供多租戶的用例環(huán)境下，每個虛擬機(jī)均有其各自的數(shù)據(jù)庫管理系統(tǒng)以及操作系統(tǒng)，這時不管日志I?O還是數(shù)據(jù)I?O均為隨機(jī)讀寫，在磁盤環(huán)境下，隨機(jī)讀寫相比非虛擬化單個數(shù)據(jù)庫設(shè)計以及非虛擬化多個數(shù)據(jù)庫設(shè)計的日志順序I?O均有較大的性能損失；固態(tài)硬盤環(huán)境下隨機(jī)I?O與順序I?O的性能相差沒有磁盤那么大，因此，基于閃存固態(tài)硬盤和虛擬化技術(shù)的多租戶事務(wù)處理設(shè)計可以提供良好的性能．這也證明了在云計算環(huán)境下，基于隔離虛擬機(jī)的多租戶事務(wù)存儲系統(tǒng)使用閃存設(shè)備處理更具有優(yōu)勢．

2．3 擴(kuò)展現(xiàn)有設(shè)備接口的事務(wù)閃存存儲系統(tǒng)

使用基于傳統(tǒng)接口的閃存設(shè)備固然可以提高事務(wù)處理的性能，但是仍然沒有充分發(fā)揮閃存的優(yōu)勢．為了將閃存自身的異地更新特性應(yīng)用于事務(wù)處理技術(shù)中，現(xiàn)有閃存設(shè)備的接口必須得到擴(kuò)展，從而可以將一部分的工作交給硬件，通過軟硬件協(xié)同的方式實(shí)現(xiàn)更加高效的事務(wù)處理．

這類研究，從接口類型來看，可以分為提供數(shù)據(jù)庫的ACID事務(wù)接口，或提供日志文件系統(tǒng)的一致性接口．從提交協(xié)議上來看，可以分為鏈?zhǔn)教峤粎f(xié)議、滑動窗口以及依據(jù)事務(wù)拓?fù)潢P(guān)系的有向無環(huán)式提交協(xié)議．雖然具體的實(shí)現(xiàn)技術(shù)各異，但是所有研究都致力于提供更高效的閃存設(shè)備事務(wù)處理以及更快速的恢復(fù)．

2．3．1 基于閃存設(shè)備FTL的事務(wù)存儲系統(tǒng)

Park等人［44］提出的AtomicWriteFTL是最早使用閃存設(shè)備異地更新特性提供事務(wù)支持的研究．AtomicWriteFTL提供了額外的設(shè)備接口：Atomic－WriteStart（）和AtomicWriteCommit（），分別用于開始一個事務(wù)以及提交一個事務(wù)，并修改了FAT文件系統(tǒng)使用這2個接口．當(dāng)FAT文件系統(tǒng)在實(shí)現(xiàn)文件系統(tǒng)調(diào)用時需要同時對多個數(shù)據(jù)塊進(jìn)行修改時，就使用上述設(shè)備接口進(jìn)行處理．AtomicWrite－Start（）被調(diào)用時，生成一個隨機(jī)的事務(wù)id，并存放到每個頁的OOB區(qū)域中．AtomicWriteCommit（）被調(diào)用時，一個提交記錄被寫入持久化層中．

AtomicWriteFTL由于研究時間較早，并未考慮大容量閃存設(shè)備的恢復(fù)以及對數(shù)據(jù)庫事務(wù)的支持等問題．同時該工作直接修改了FAT文件系統(tǒng)，而沒有修改系統(tǒng)塊設(shè)備緩存，這使得要使用設(shè)備提供的事務(wù)接口就必須將文件系統(tǒng)以同步的方式掛載，也造成了性能問題．

在AtomicWriteFTL的基礎(chǔ)上，韓國成均館大學(xué)和首爾大學(xué)的研究人員提出了一個事務(wù)型閃存轉(zhuǎn)換層X－FTL［27］，并以移動設(shè)備上大量應(yīng)用的嵌入式數(shù)據(jù)庫軟件SQLite作為上層應(yīng)用進(jìn)行接口設(shè)計．在外部設(shè)備接口上，如表1所示，X－FTL修改了SATA接口的讀寫命令，增加了一個代表事務(wù)標(biāo)識的參數(shù)；此外還新增加了commit和abort命令．

如圖5所示，與傳統(tǒng)閃存轉(zhuǎn)換層相比，X－FTL新增了事務(wù)頁映射表（transactional page mapping table，X－L2P）用于存放未提交事務(wù)中的邏輯頁的映射信息，并在事務(wù)提交后將事務(wù)頁映射表信息寫入到閃存轉(zhuǎn)換層地址映射表中．與AtomicWriteFTL相比，X－FTL沒有使用閃存頁OOB區(qū)域而是在閃存設(shè)備中開辟新的區(qū)域存放未提交的事務(wù)頁映射信息．

Table 1 X－FTL Extended SATA Interface［27］表1 X－FTL擴(kuò)展SATA接口

Fig．5 X－FTL architecture：a FTL for transactional atomicity［27］．圖5 X－FTL體系結(jié)構(gòu)：一種提供事務(wù)原子性的FTL

在X－FTL中，雖然數(shù)據(jù)頁本身并沒有被寫入2次，但是對于X－L2P表中的映射信息仍然被寫入了2次．AtomicWriteFTL與X－FTL都是在現(xiàn)有閃存轉(zhuǎn)換層基礎(chǔ)上增加新的模塊，而不需要對現(xiàn)有FTL做任何的變動．

國內(nèi)中國人民大學(xué)的研究人員提出的MixSL［45］同樣也是一種基于現(xiàn)有MLC閃存設(shè)備FTL的事務(wù)提交模型．與X－FTL類似，MixSL在內(nèi)存中使用一個Transaction Table用以追蹤事務(wù)狀態(tài)，同時使用一個Δ－Mapping Table存放事務(wù)中新增的映射信息．當(dāng)故障恢復(fù)時，MixSL掃描日志數(shù)據(jù)頁OOB區(qū)域存放的事務(wù)信息丟棄掉未完成的數(shù)據(jù)頁．

2．3．2 基于鏈?zhǔn)教峤粎f(xié)議的TxFlash［46］

微軟的研究人員提出了基于鏈表的事務(wù)閃存存儲系統(tǒng)TxFlash以及其提交協(xié)議簡單環(huán)狀提交（simple cyclic commit，SCC）和反向指針環(huán)狀提交（back pointer cyclic commit，BPCC）［46］．TxFlash利用閃存頁OOB存放事務(wù)中下一個頁的物理地址作為單向鏈表指針，事務(wù)的最后一頁的OOB區(qū)域中存放事務(wù)首頁的物理地址，因此一個事務(wù)中的數(shù)據(jù)頁形成了環(huán)．異常發(fā)生后，恢復(fù)時首先掃描所有的頁，如果某些頁根據(jù)其OOB中的指針構(gòu)成環(huán)狀結(jié)構(gòu)，那么表示該事務(wù)已經(jīng)提交，否則表示未提交并丟棄該事務(wù)所有的頁．由于閃存垃圾回收操作可能會破壞這種環(huán)狀結(jié)構(gòu)，為了區(qū)分破壞的環(huán)狀結(jié)構(gòu)是由垃圾回收還是未提交事務(wù)造成的，SCC協(xié)議在寫入數(shù)據(jù)頁時強(qiáng)制擦除該數(shù)據(jù)頁之前的未提交版本以及其所依賴的頁，但是引入的擦除操作會影響整體寫入性能，因此在SCC協(xié)議的基礎(chǔ)上提出了BPCC協(xié)議，BPCC中每個頁除了有指向下一頁的指針之外，還包含該邏輯頁上一個已提交版本的地址作為反向指針．這樣如果某個頁既沒有反向指針指入，又處于一個被破壞的環(huán)狀鏈表中，則這一個頁屬于某個未提交事務(wù)，需要被垃圾回收．

TxFlash的2種提交協(xié)議SCC和BPCC對頁面擦除時機(jī)存在限制，同時具有較大開銷．為了解決該問題，浸會大學(xué)和南洋理工大學(xué)的研究人員在TxFlash的基礎(chǔ)上提出了Flag Commit協(xié)議［47］．Flag Commit協(xié)議基于SLC閃存支持指針的原地修改，在擦除已提交事務(wù)中的頁面時，原地修改OOB區(qū)域內(nèi)的指針即可與未提交事務(wù)相區(qū)分，從而避免了SCC和BPCC由于指針依賴說帶來的額外擦除開銷，但Flag Commit協(xié)議僅限于SLC閃存，而無法應(yīng)用于常用的MLC閃存中．

此外，TxFlash的恢復(fù)基于全盤掃描，離線時間過長，印度理工學(xué)院的研究人員提出了一種基于TxFlash的提交協(xié)議QRCC（quick recovery cyclic commit）［48］，將每個事務(wù)的首頁存放在閃存設(shè)備的一個順序結(jié)構(gòu)中．這樣在恢復(fù)時，只需要依據(jù)這一結(jié)構(gòu)進(jìn)行事務(wù)狀態(tài)檢查，從而實(shí)現(xiàn)了TxFlash的恢復(fù)加速．

2．3．3 對FTL進(jìn)行修改的事務(wù)閃存存儲系統(tǒng)

除了基于已有FTL設(shè)計事務(wù)閃存存儲系統(tǒng)之外，俄亥俄州立大學(xué)以及FusionIO公司的研究人員合作，對FTL層進(jìn)行了修改，提出了Atomic－Write［49］的設(shè)計，直接由FTL層提供事務(wù)支持，并在FusionIO公司的產(chǎn)品中被廣泛使用［50］．與三星、Intel等公司基于設(shè)備的（device－based）固態(tài)硬盤（SSD）等不同的是，F(xiàn)usionIO面向企業(yè)提供基于主機(jī)的（host－based）固態(tài)存儲系統(tǒng)（solid state storage，SSS），由軟件層提供閃存轉(zhuǎn)換層、磨損均衡和垃圾回收等功能．與AtomicWriteFTL和X－FTL相比，Atomic－Write對上層提供的專用事務(wù)處理接口相似，但直接修改基于日志FTL以實(shí)現(xiàn)這些接口，圖6是其內(nèi)部結(jié)構(gòu)圖：

Fig．6 Implementing Atomic－Write within a log based FTL［49］．圖6 在基于日志FTL中實(shí)現(xiàn)Atomic－Write

為了將增加事務(wù)處理對系統(tǒng)性能的影響控制在最小范圍，Atomic－Write在閃存轉(zhuǎn)換層的映射信息中增加了一位，當(dāng)這一位為“1”時，表示當(dāng)前頁是一個事務(wù)的最后一頁．同時，每個時刻最多有一個正在寫入的原子寫．在系統(tǒng)崩潰等異常情況后，由后向前掃描映射信息日志，在遇到第一個標(biāo)志位為“1”的映射信息之前，丟棄到所有的標(biāo)志位為“0”的映射信息，也即丟棄掉最后一個未完成的原子寫．Atomic－Write實(shí)現(xiàn)基礎(chǔ)是日志FTL，同時為了支持事務(wù)處理僅額外寫入了1b信息，在不涉及到并發(fā)性的前提下性能較優(yōu)．但是同一時刻，Atomic－Write最多只有一個寫入中的事務(wù)，限制了底層閃存設(shè)備的并發(fā)性．FusionIO將這一設(shè)計實(shí)現(xiàn)在其商業(yè)產(chǎn)品Atomic Series的ioMemory中，同時提供MySQL InnoDB存儲引擎擴(kuò)展以使用這些事務(wù)處理接口．

2．3．4 基于滑動窗口的LightTx［51］

在事務(wù)處理機(jī)制中，事務(wù)的隔離性一般由軟件層的鎖機(jī)制負(fù)責(zé)，如果由設(shè)備層提供，設(shè)備層一般只能提供串行（serializable）一種隔離性，也即一個事務(wù)完成后處理下一個事務(wù)，但是這限制了底層存儲設(shè)備的性能．為了解決這一問題，Lu等人［51］提出了基于滑動窗口的靈活輕量事務(wù)閃存LightTx，支持事務(wù)的3種不同隔離級別：嚴(yán)格隔離（strict isolation）、無頁沖突（no－page－conflict）和串行（serializable），并由軟件層決定具體的隔離級別．在內(nèi)部結(jié)構(gòu)上，LightTx將閃存設(shè)備根據(jù)事務(wù)所處不同的生命周期劃分為4個滑動窗口，分別為已完成區(qū)域（checkpointed zone）、待定窗口（pending window）、更新窗口（updating window）和空閑區(qū)域（free zone）．任意時刻，正在更新的事務(wù)只存在于待定窗口與更新窗口中．LightTx采用頁面技術(shù)的方式在恢復(fù)時判斷事務(wù)是否提交，事務(wù)的最后一個頁面的OOB區(qū)域?yàn)槭聞?wù)中頁總數(shù)，否則為0．當(dāng)系統(tǒng)崩潰恢復(fù)時，只需要對待定窗口和更新窗口區(qū)域進(jìn)行掃描和驗(yàn)證，從而減少了存儲系統(tǒng)離線恢復(fù)時間．

圖7是采用LightTx事務(wù)恢復(fù)協(xié)議的事務(wù)閃存設(shè)備的狀態(tài)快照示例，當(dāng)故障發(fā)生后，掃描更新窗口和待定窗口根據(jù)頁面OOB中的信息可以判定Tx6，Tx9，Tx10為未提交事務(wù)，需要被進(jìn)行垃圾回收，其余事務(wù)的FTL層數(shù)據(jù)則要被再次寫入．2．3．5 基于有向無環(huán)提交協(xié)議的M bius［52］

Fig．7 Zone－based transaction state tracking［51］．圖7 基于窗口事務(wù)狀態(tài)跟蹤圖

事務(wù)閃存設(shè)備除了需要寫入事務(wù)數(shù)據(jù)之外，與一般的閃存設(shè)備一樣，也需要保證FTL層的映射數(shù)據(jù)被持久化．清華大學(xué)的研究人員基于開源硬件OpenSSD設(shè)計并實(shí)現(xiàn)了名叫M bius的事務(wù)閃存設(shè)備，M bius將FTL映射數(shù)據(jù)與事務(wù)元數(shù)據(jù)相結(jié)合的方式持久化事務(wù)元數(shù)據(jù)．M bius將事務(wù)分為靜態(tài)事務(wù)（static transaction）與動態(tài)事務(wù)（dynamic transaction），靜態(tài)事務(wù)主要指事務(wù)所有待寫入的頁都已經(jīng)在內(nèi)存中，和多個頁的原子寫比較接近，而動態(tài)事務(wù)指事務(wù)開始時待寫入的頁還沒有確定，需要等待計算．通常文件系統(tǒng)緩存處理數(shù)據(jù)的方式是靜態(tài)事務(wù)式的，但是關(guān)系型數(shù)據(jù)庫中的多個SQL語句組成的事務(wù)是動態(tài)事務(wù)．對于靜態(tài)事務(wù)，由于事務(wù)所有的寫入頁已經(jīng)確定，M bius會實(shí)現(xiàn)分配物理頁，一個事務(wù)所分配的所有頁的映射信息以及事務(wù)信息被記錄到一個被稱為Atom的閃存頁中，所有的Atom被維護(hù)在一個稱為Atom Log Area的區(qū)域，在恢復(fù)時使用有向無環(huán)圖提交協(xié)議快速檢查；而對于動態(tài)事務(wù)，M bius采用鏈表式的方式進(jìn)行寫入．

有向無環(huán)提交協(xié)議的關(guān)鍵在于當(dāng)前事務(wù)的提交記錄寫入到后續(xù)的事務(wù)中，于是在Atom Log Area形成了后續(xù)Atom指向之前Atom的拓?fù)浣Y(jié)構(gòu)．恢復(fù)時，對Atom Log Area從后向前進(jìn)行掃描，如果某Atom被之前Atom所指向，這該Atom代表的事務(wù)已提交．否則需要進(jìn)一步進(jìn)行檢查，讀取Atom內(nèi)的映射信息，訪問所有的物理頁，如果物理頁中事務(wù)id與Atom中的id均吻合，則表示該事務(wù)已完成，否則表示該事務(wù)未完成，需要進(jìn)行垃圾回收．

2．4 小 結(jié)

基于閃存的事務(wù)存儲系統(tǒng)按照接口技術(shù)的不同可以分成2類，一類系統(tǒng)直接使用現(xiàn)有接口閃存設(shè)備，包括USB接口或諸如SATA，SAS接口在內(nèi)的磁盤接口閃存設(shè)備．這類系統(tǒng)的設(shè)計目標(biāo)主要圍繞著利用這些閃存設(shè)備比傳統(tǒng)磁盤更優(yōu)的I?O性能加速事務(wù)處理．另一類系統(tǒng)則對現(xiàn)有設(shè)備接口進(jìn)行擴(kuò)展，利用閃存異地更新特性，將寫前日志的功能實(shí)現(xiàn)在閃存設(shè)備內(nèi)部，對上層軟件提供不同類型的事務(wù)處理接口，避免了重復(fù)設(shè)計造成的冗余I?O等問題，提升了性能．

閃存設(shè)備接口的局限性被越來越多的研究人員所關(guān)注，例如北京大學(xué)和百度公司的研究人員提出了將閃存設(shè)備通道直接暴露給軟件層的設(shè)計［53］，在這樣的存儲架構(gòu)之上，直接使用閃存硬件更高效地實(shí)現(xiàn)了LSM樹（log－structured merge－tree）型結(jié)構(gòu)．

擴(kuò)展閃存設(shè)備接口進(jìn)行事務(wù)處理的技術(shù)與直接利用閃存設(shè)備I?O性能進(jìn)行事務(wù)處理加速的技術(shù)相比更加復(fù)雜，也是目前學(xué)術(shù)界和工業(yè)界研究的主要方向，這類系統(tǒng)也被稱為事務(wù)閃存存儲系統(tǒng)．

事務(wù)閃存存儲系統(tǒng)分別在系統(tǒng)開銷、離線恢復(fù)時間、設(shè)備接口和事務(wù)隔離性等方面考慮事務(wù)處理邏輯的實(shí)現(xiàn)．這些設(shè)計可以被實(shí)現(xiàn)在閃存設(shè)備的固件層，也可以實(shí)現(xiàn)在系統(tǒng)軟件層或設(shè)備驅(qū)動層．通過這樣的設(shè)計，可以充分發(fā)揮閃存異地更新的特性，減少了不必要的數(shù)據(jù)寫入量．以日志文件系統(tǒng)為例，在日志模式下，系統(tǒng)調(diào)用的首先被寫入連續(xù)的日志區(qū)域，接著被寫入磁盤實(shí)際位置，數(shù)據(jù)寫入量WT為：

其中，WJ為磁盤日志寫入量，WD為磁盤數(shù)據(jù)寫入量，在嚴(yán)格一致性條件下，WJ和WD數(shù)據(jù)量大致相同，由于WD是有效的數(shù)據(jù)變化量，所以寫放大率達(dá)到1∶1．但是對事務(wù)閃存存儲系統(tǒng)，WJ的寫入量可以通過閃存異地更新特性避免，閃存中的舊數(shù)據(jù)頁在沒有被垃圾回收之前，可以作為日志使用，從而減少了日志部分的寫入．

表2是現(xiàn)有的基于閃存的事務(wù)存儲系統(tǒng)與技術(shù)比較，其中FlashLogging，Hybrid Buffer，Multitenant直接使用現(xiàn)有接口的閃存設(shè)備從不同的角度對事務(wù)處理進(jìn)行優(yōu)化，其余則均為擴(kuò)展接口的事務(wù)閃存存儲系統(tǒng)．AtomicWriteFTL和X－FTL在閃存設(shè)備已有FTL之上進(jìn)行設(shè)計，不需要對FTL進(jìn)行改動，但是對于故障后恢復(fù)，不僅僅需要對事務(wù)邏輯進(jìn)行恢復(fù)，而且需要對FTL本身進(jìn)行恢復(fù)．MixSL在設(shè)計上與X－FTL較為接近，但是沒有說明其具體使用的設(shè)備接口．Atomic－Write?FusionIO的事務(wù)閃存設(shè)計基于日志FTL做了最小改動，只增加了一位代表事務(wù)的最后一頁，但是這也限制了事務(wù)處理的并行性，沒有充分利用底層閃存IO能力．TxFlash和Flag Commit基于鏈?zhǔn)教峤粎f(xié)議，但恢復(fù)時需要進(jìn)行全盤掃描，離線時間過長．LightTx基于滑動窗口，運(yùn)行時代價較小，但恢復(fù)時同樣需要掃描一定范圍內(nèi)的閃存并進(jìn)行驗(yàn)證．M bius支持2種接口并且恢復(fù)時離線時間較短，但是對于大量小事務(wù)，由于需要額外寫入Atom頁，處理代價較大．

Table 2 Comparison of Flash－Based Transactional Storage Systems and Technologies表2 基于閃存的事務(wù)存儲系統(tǒng)與技術(shù)比較

3 基于相變存儲器的事務(wù)存儲系統(tǒng)與技術(shù)

除了已經(jīng)被廣泛使用的閃存之外，相變存儲器作為另一種即將投入使用的存儲介質(zhì)，也漸漸成為了事務(wù)存儲系統(tǒng)中研究的熱點(diǎn)．

相變存儲器（PCM）作為一種新型非易失存儲介質(zhì)，具有高密度、字節(jié)尋址、高性能讀寫等特點(diǎn)；此外與閃存相比，沒有高延遲的擦除操作．由于這些優(yōu)點(diǎn)，PCM在存儲體系結(jié)構(gòu)上通常有2類不同的使用方式：1）與主存同級，如圖8所示，獨(dú)立構(gòu)成主存或和DRAM構(gòu)成混合型主存；2）與外存同級，構(gòu)成固態(tài)硬盤，使用高性能結(jié)構(gòu)作為可字節(jié)尋址的外存設(shè)備．在這2種不同的體系結(jié)構(gòu)下，PCM均可以被用于支持高性能的事務(wù)處理．

Fig．8 PCM memory architecture alternatives［54］．圖8 PCM作為主存的不同存儲體系結(jié)構(gòu)

3．1 相變存儲器構(gòu)建主存環(huán)境下的事務(wù)處理技術(shù)

相變存儲器在構(gòu)建主存環(huán)境下實(shí)現(xiàn)高效事務(wù)處理主要依靠于日志與緩存融合技術(shù)．緩存是存儲系統(tǒng)高效運(yùn)行所必須的，而日志則是事務(wù)處理技術(shù)帶來的額外開銷．當(dāng)主存非易失時，緩存和日志之間的界限變得模糊，將日志與緩存融合可以利用系統(tǒng)緩存直接作為事務(wù)日志，從而更加高效．

浸會大學(xué)和南洋理工學(xué)院的研究人員提出了基于PCM與DRAM混合主存體系結(jié)構(gòu)下的事務(wù)日志處理技術(shù)PCMLogging［54］．PCMLogging基于PCM與DRAM混合主存體系結(jié)構(gòu)進(jìn)行設(shè)計，其核心思想是利用PCM的非易失特性將數(shù)據(jù)緩沖區(qū)與日志緩沖區(qū)合二為一，這樣當(dāng)數(shù)據(jù)被寫入到非易失的數(shù)據(jù)緩沖區(qū)后，也可以作為崩潰后的恢復(fù)日志使用．

PCMLogging使用了映射表（mapping table，MT）、空閑頁位圖（free page bitmap）和反向指針（inverse mapping）3個結(jié)構(gòu)對PCM進(jìn)行管理．其中映射表是內(nèi)存管理單元（memory management unit，MMU）中內(nèi)存邏輯地址到物理地址映射的一部分，空閑頁位圖用于分配空閑PCM頁，反向指針用于在系統(tǒng)啟動時重建映射表．ActiveTxList中存放當(dāng)前活動狀態(tài)的事務(wù)標(biāo)識XID，在事務(wù)將其所有臟頁刷入到PCM中之后，ActiveTxList中的相應(yīng)XID會被移除．PCM頁元數(shù)據(jù)區(qū)域中XID字段代表最近一次修改該頁的事務(wù)標(biāo)識．當(dāng)系統(tǒng)以外崩潰后恢復(fù)時，首先掃描ActiveTxList，丟棄未完成的事務(wù)數(shù)據(jù)，并將完成的事務(wù)數(shù)據(jù)保存并在適當(dāng)時候刷新到外存中．

CMLogging在DRAM和PCM中使用額外的數(shù)據(jù)結(jié)構(gòu)記錄事務(wù)的狀態(tài)，并在故障恢復(fù)時依據(jù)這些狀態(tài)信息丟棄未提交事務(wù)的數(shù)據(jù)．通過將數(shù)據(jù)緩存與日志緩存相結(jié)合的方法，避免了事務(wù)處理中數(shù)據(jù)的2遍寫入．

與PCMLogging相似，韓國梨花女子大學(xué)的研究人員提出了在PCM主存環(huán)境將文件系統(tǒng)日志與操作系統(tǒng)頁緩存合二為一的文件系統(tǒng)事務(wù)處理方法UBJ（union of buffer cache and journaling）［55］．

如圖9所示，通過這樣的整合，首先系統(tǒng)更新頁緩存時即完成了對日志的修改，減少了不必要的I?O；其次，與內(nèi)存總線相比，不同接口的外存設(shè)備均具有較大的延遲和較小的帶寬，UBJ將原先文件系統(tǒng)日志部分的寫入控制在了內(nèi)存這一層，而不必要和外存進(jìn)行交互，從而提高了性能．

Fig．9 Commit process comparing［55］．圖9 不同內(nèi)存體系結(jié)構(gòu)下的提交過程對比

Fig．10 Overview of Kiln persistent memory design［56］．圖10 非易失內(nèi)存體系結(jié)構(gòu)Kiln

如圖10所示，匹茲堡大學(xué)、HP、IBM、AMD和Google的研究人員合作提出了另外一種基于PCM的內(nèi)存體系結(jié)構(gòu)Kiln［56］，用于支持事務(wù)處理．

Kiln在思想上與UBJ較為相似，與UBJ在內(nèi)存這一層融合了頁緩存和日志不同的是，Kiln在處理器緩存中增加了一層非易失緩存，將處理器高速緩存與日志區(qū)域融合．這種在存儲體系結(jié)構(gòu)中縱向的PCM布局有2個好處：1）不需要維護(hù)任何事務(wù)狀態(tài)，直接利用存儲體系結(jié)構(gòu)中數(shù)據(jù)的縱向冗余提供日志功能，代價很小；2）將原先寫日志部分的I?O控制在處理器內(nèi)部互聯(lián)中，減少了使用內(nèi)存總線的I?O次數(shù)，從而提高了性能．

圖10還對Kiln與傳統(tǒng)塊設(shè)備與混合內(nèi)存體系結(jié)構(gòu)下的事務(wù)處理機(jī)制進(jìn)行了對比．可以看出，Kiln使用了縱向結(jié)構(gòu)的日志布局，并將日志融入到存儲體系結(jié)構(gòu)中，將持久化日志放在離處理器更近的位置，避免使用代價較高的內(nèi)存總線去持久化日志數(shù)據(jù)，從而提高系統(tǒng)性能．但是Kiln對于事務(wù)的大小有一定的限制，必須要能存放于處理器的NV Cache中．

此外，清華大學(xué)的Lu等人［57］提出了應(yīng)用于非易失內(nèi)存環(huán)境下的LOC（loose－ordering consistency）技術(shù)對事務(wù)處理寫前日志方法的性能進(jìn)行提升．LOC中主要使用了名為Eager Commit和Speculative Persistence的2種技術(shù)，Eager Commit使用事務(wù)狀態(tài)表（transaction state table，TxST）對事務(wù)狀態(tài)進(jìn)行記錄，從而在事務(wù)提交后，不需要寫入額外的提交日志，從而提高性能；Speculative Persistence指的是控制軟件對于寫入內(nèi)存數(shù)據(jù)的可見性，消除了事物間寫入的強(qiáng)制順序性要求，從而提高性能．

除了應(yīng)用在單節(jié)點(diǎn)事務(wù)處理環(huán)境下之外，PCM也被設(shè)計應(yīng)用在多核、分布式事務(wù)處理環(huán)境．與傳統(tǒng)的易失性DRAM主存相比，事務(wù)處理技術(shù)中的日志方法在非易失內(nèi)存環(huán)境下會被根本改變．相比傳統(tǒng)方法，在非易失內(nèi)存中，事務(wù)不需要強(qiáng)制進(jìn)行提交前刷新（flush－before－commit）．在這樣的背景下，多倫多大學(xué)的研究人員提出了在非易失內(nèi)存環(huán)境多核多通道（multicore and multi－socket）硬件中使用分布式日志（distributed logging）技術(shù)提升系統(tǒng)事務(wù)處理能力［58］．多核多通道的非一致性內(nèi)存訪問（NUMA）體系結(jié)構(gòu)下，分布式日志技術(shù)會造成處理器親和度（processor affinity）問題，也即處理器同時訪問本地和遠(yuǎn)端的內(nèi)存數(shù)據(jù)頁時會產(chǎn)生競爭．為了解決這一問題，分布式日志方法使用了事務(wù)級日志空間劃分，對每一個處理器維護(hù)一個本地的日志，當(dāng)事務(wù)完成之后，在這些本地的日志之間設(shè)置數(shù)據(jù)檢查點(diǎn)（checkpoint）．通過使用事務(wù)級日志空間劃分內(nèi)存，分布式日志技術(shù)消除了大部分處理器在進(jìn)行日志時對內(nèi)存頁的競爭，性能得到了約3倍的提升．

3．2 相變存儲器構(gòu)建外存環(huán)境下的事務(wù)處理技術(shù)

目前相變內(nèi)存芯片的I?O性能稍遜于DRAM，所以也出現(xiàn)了一些使用PCM作為外存、利用其高性能和字節(jié)尋址等特性提升事務(wù)處理能力的技術(shù)，這類技術(shù)可以稱為細(xì)粒度日志技術(shù)．

傳統(tǒng)的外存塊設(shè)備記錄日志時，即使只有少量改動，相關(guān)塊也將被整個寫入到日志區(qū)域．加州大學(xué)圣地亞哥分校的研究人員使用PCM作為介質(zhì)構(gòu)造了PCIe接口的固態(tài)存儲設(shè)備Moneta［59］，提出了基于Moneta的事務(wù)處理技術(shù)可編輯原子寫（editable atomic write，EAW）［60］．與傳統(tǒng)的事務(wù)日志處理技術(shù)相比，由于PCM的字節(jié)尋址特性，使得EAW可以在硬件層實(shí)現(xiàn)對事務(wù)日志的提交前修改，這樣在對某個頁進(jìn)行重復(fù)修改時日志中只有一份數(shù)據(jù)拷貝．EAW從PCM介質(zhì)特性出發(fā)，設(shè)計了一種完全不同于傳統(tǒng)塊設(shè)備外存的事務(wù)日志技術(shù)并將其實(shí)現(xiàn)在設(shè)備中，從而提高了存儲設(shè)備的事務(wù)處理能力．

3．3 小 結(jié)

PCM作為主存使用時，主要利用了PCM的非易失特性，主要有日志與緩存融合技術(shù)，使用非易失的緩存實(shí)現(xiàn)事務(wù)日志的功能，從而減少了日志部分的開銷．

PCM主存進(jìn)行事務(wù)處理具有2點(diǎn)優(yōu)勢：1）將緩沖區(qū)與日志區(qū)合并，從而減少不必要的日志I?O；2）內(nèi)存層恢復(fù)，在恢復(fù)時直接利用PCM中的信息重建事務(wù)狀態(tài)表，丟棄未完成的事務(wù)信息，而不需要和外存進(jìn)行交互．

PCM介質(zhì)構(gòu)建外存設(shè)備時，利用其字節(jié)尋址的特性可以減少對相同數(shù)據(jù)塊進(jìn)行修改的日志I?O，從而提高了事務(wù)處理能力．這類技術(shù)被稱為細(xì)粒度日志技術(shù)，相比塊設(shè)備而言，細(xì)粒度日志技術(shù)可以以字節(jié)為單位進(jìn)行日志寫入和讀取，避免了塊對齊造成的不必要的寫入，從而提升系統(tǒng)性能．

Table 3 Comparison of PCM－Based Transactional Storage Class Memory Systems表3 基于PCM的事務(wù)存儲系統(tǒng)比較

表3對現(xiàn)有的基于PCM的事務(wù)存儲系統(tǒng)和技術(shù)進(jìn)行了比較，從中可以看出，PCM事務(wù)處理主要應(yīng)用在主存環(huán)境，前5種技術(shù)均為PCM在主存環(huán)境下的事務(wù)處理應(yīng)用．其中Kiln較為特殊，還將PCM應(yīng)用于L3Cache，從處理器到主存就開始保證事務(wù)性持久化．在恢復(fù)時間上，LOC由于采用事務(wù)狀態(tài)表進(jìn)行查詢，避免了掃描，從而縮短了恢復(fù)時間．Distributed Logging技術(shù)采用全PCM主存解決了多核環(huán)境下持久化層與核之間的親和度問題，降低了內(nèi)存中的數(shù)據(jù)頁競爭，提升了效率．

4 研究展望

縱觀存儲工業(yè)發(fā)展史，從磁帶設(shè)備、軟盤到光介質(zhì)再到磁盤，新的數(shù)據(jù)存儲介質(zhì)往往會給I?O棧帶來革命性的影響．事務(wù)存儲技術(shù)作為存儲領(lǐng)域最為重要的關(guān)鍵技術(shù)之一，幾乎被應(yīng)用于所有的數(shù)據(jù)庫系統(tǒng)與文件系統(tǒng)．隨著閃存等非易失存儲介質(zhì)的廣泛應(yīng)用，存儲體系結(jié)構(gòu)正面臨著大的變革，因此在新型存儲體系結(jié)構(gòu)下研究事務(wù)存儲技術(shù)的需求變得極為迫切．目前基于閃存的事務(wù)存儲系統(tǒng)已經(jīng)開始嶄露頭角，基于PCM的事務(wù)存儲系統(tǒng)也已走出實(shí)驗(yàn)階段．展望未來，針對目前非易失存儲器應(yīng)用于事務(wù)處理技術(shù)所面臨的問題，以下4個方面仍然需要進(jìn)一步探索與研究．

4．1 事務(wù)存儲接口

閃存的量產(chǎn)使得閃存設(shè)備已經(jīng)被廣泛應(yīng)用于傳統(tǒng)存儲體系結(jié)構(gòu)的緩存層和持久化層．按照設(shè)備所處的不同層級，也擁有不同的設(shè)備接口，包括傳統(tǒng)的SATA，SCSI，SAS等磁盤接口，也包括PCIe和NVMe等新型設(shè)備接口，甚至還包括內(nèi)存模塊DIMM接口．PCM設(shè)備也根據(jù)其處在I?O棧不同位置使用不同的設(shè)備接口．基于非易失存儲器的事務(wù)存儲系統(tǒng)核心在于利用介質(zhì)特性提升事務(wù)處理能力，因而設(shè)備接口必須將這種能力暴露給系統(tǒng)軟件層，但是如此眾多的設(shè)備接口使得非易失存儲設(shè)備很難提供統(tǒng)一的事務(wù)處理接口，從而存在適用性問題．

對于已有的一些事務(wù)接口，也存在著許多問題．由于事務(wù)應(yīng)用于不同存儲系統(tǒng)時，對ACID要求并不相同，例如文件系統(tǒng)事務(wù)一般要弱于數(shù)據(jù)庫事務(wù)，但是已有的事務(wù)接口并不能體現(xiàn)出這種差別；此外，對于事務(wù)中隔離性、一致性等特性，也存在著多種不同的級別，現(xiàn)有的事務(wù)接口對于這些不同級別也不能進(jìn)行區(qū)分．因此，如何提供高適用性且支持不同特性事務(wù)的設(shè)備接口是值得研究的問題．

4．2 數(shù)據(jù)可用性

存儲系統(tǒng)最為關(guān)鍵的指標(biāo)莫過于數(shù)據(jù)可用性（availability），對于事務(wù)處理系統(tǒng)而言則尤為重要．譬如銀行系統(tǒng)內(nèi)的事務(wù)代表著金錢的流動，關(guān)系著社會穩(wěn)定．?dāng)?shù)據(jù)可用性在事務(wù)處理中具體而言，可以細(xì)化為2類問題：1）系統(tǒng)正常工作時的數(shù)據(jù)可用性；2）系統(tǒng)遇到故障后的快速恢復(fù)．

在大數(shù)據(jù)時代，數(shù)據(jù)量成為了事務(wù)存儲系統(tǒng)快速故障恢復(fù)（failover）的主要障礙，全盤掃描式的恢復(fù)會導(dǎo)致較長數(shù)據(jù)離線時間，如何高效迅速的故障恢復(fù)將會成為研究的重點(diǎn)．

4．3 系統(tǒng)可擴(kuò)展性

隨著數(shù)據(jù)量規(guī)模的不斷增長，基于非易失存儲器的事務(wù)存儲系統(tǒng)的可擴(kuò)展性問題也日益突出．在宏觀上，可擴(kuò)展性體現(xiàn)在事務(wù)處理技術(shù)高效應(yīng)用于分布式環(huán)境下；在微觀上，則是保證多核環(huán)境下事務(wù)處理能力可擴(kuò)展．

分布式環(huán)境下如何利用非易失存儲器特性提供高效的事務(wù)處理是研究的關(guān)鍵，目前的分布式事務(wù)處理技術(shù)主要使用2PC（two phase commitment protocol）2階段提交協(xié)議［61］，在該提交協(xié)議里，事務(wù)提交被分為請求階段與提交階段，但是分階段提交的開銷較大，如果利用非易失存儲器異地更新的特性，2PC之類的分布式事務(wù)提交協(xié)議是否可以優(yōu)化可能成為研究的熱點(diǎn)，例如在閃存設(shè)備環(huán)境中首先寫入各節(jié)點(diǎn)，而后判斷，避免等待協(xié)調(diào)所耗費(fèi)的時間，同時由于閃存異地更新特性，可以方便地進(jìn)行回滾．此外，多核背景下的分布式處理技術(shù)中存在處理器親和度等問題，需要探索分配日志工作的方法．4．4 數(shù)據(jù)可靠性

各類新興的非易失存儲器由于工藝和技術(shù)上的限制，存在著壽命有限、錯誤率高等問題，如何保證新介質(zhì)對數(shù)據(jù)的可靠持久化，必然會成為研究的熱點(diǎn)．這類問題的研究方向一般圍繞著糾刪碼和軟件層的數(shù)據(jù)冗余備份展開．

事務(wù)存儲系統(tǒng)是提供高可靠性的保證，因此其本身的可靠性問題必將成為研究的熱點(diǎn)．閃存以及PCM等非易失存儲器相比磁盤，呈現(xiàn)出極為不同的可靠性特征．例如閃存中存在FTL層，而FTL中的映射數(shù)據(jù)本身的可靠性也需要保證，與磁盤設(shè)備相比，這大大增加了整體可靠性問題．目前的非易失事務(wù)存儲系統(tǒng)的設(shè)計大多基于底層設(shè)備是可靠的這一假設(shè)，并沒有考慮設(shè)備本身出現(xiàn)可靠性問題的情況．通過進(jìn)一步分析新型非易失存儲介質(zhì)的可靠性特征，并依據(jù)這些特征對事務(wù)存儲系統(tǒng)進(jìn)行改造，才能為上層軟件提供更高的可靠性保證．

5 總 結(jié)

隨著閃存的廣泛應(yīng)用以及PCM，MRAM，RRAM等非易失存儲器的涌現(xiàn)，存儲體系結(jié)構(gòu)正面臨著巨大的變化．這些非易失存儲器各有特點(diǎn)，例如閃存設(shè)備具有異地更新特性、PCM設(shè)備具有字節(jié)尋址特性，如何利用這些特性對I?O棧進(jìn)行重新設(shè)計已經(jīng)成為存儲系統(tǒng)研究的重點(diǎn)．

事務(wù)這一概念由圖靈獎得主James Gray提出，目前已被廣泛應(yīng)用于各種存儲系統(tǒng)中以提供原子性、一致性、隔離性和持久性．目前，各種存儲系統(tǒng)中已有的事務(wù)處理技術(shù)大多基于傳統(tǒng)磁盤設(shè)備，沒有充分利用閃存和PCM等非易失存儲設(shè)備的特點(diǎn)，造成了性能損失等問題．

本文從事務(wù)處理技術(shù)應(yīng)用于新型存儲體系結(jié)構(gòu)的角度出發(fā)，對操作系統(tǒng)、數(shù)據(jù)庫以及體系結(jié)構(gòu)領(lǐng)域出現(xiàn)的新的事務(wù)存儲系統(tǒng)和相關(guān)技術(shù)進(jìn)行了研究和分析．這些工作分別處于存儲體系結(jié)構(gòu)不同層，使用的介質(zhì)也主要分為已經(jīng)量產(chǎn)的閃存和即將量產(chǎn)的PCM．在事務(wù)閃存存儲系統(tǒng)中，大多數(shù)工作利用閃存設(shè)備原生的異地更新特性避免了軟件層不必要的工作，快速恢復(fù)和可擴(kuò)展性問題是目前的研究熱點(diǎn)．在PCM事務(wù)存儲系統(tǒng)中，主要利用了PCM在體系結(jié)構(gòu)中的位置，將日志與系統(tǒng)緩存相結(jié)合，避免了重復(fù)I?O，此外也有工作利用PCM的直接尋址，提供細(xì)粒度的日志，從而提高性能．

綜合現(xiàn)有的研究情況，目前基于閃存的事務(wù)存儲系統(tǒng)處于起步階段，已經(jīng)出現(xiàn)了FusionIO公司的ioDrive等系列產(chǎn)品為上層提供原子寫原語，但是各類事務(wù)閃存存儲系統(tǒng)的接口較為復(fù)雜且不統(tǒng)一，此外隨著閃存設(shè)備容量的增長，離線恢復(fù)時間和其他可擴(kuò)展性問題亟需解決．而基于PCM的事務(wù)存儲系統(tǒng)則還處于實(shí)驗(yàn)階段，并且需要從體系結(jié)構(gòu)、系統(tǒng)軟件以及應(yīng)用程序等多方面共同考慮和設(shè)計．此外，例如MRAM和RRAM等非易失存儲器也即將走出實(shí)驗(yàn)室，如何在事務(wù)存儲系統(tǒng)中利用這些介質(zhì)自身的特點(diǎn)也將成為研究的熱點(diǎn)．

［1］Gray J．Notes on Data Base Operating Systems［M］．London：Springer，1978：393 481

［2］Gray J．The transaction concept：Virtues and limitations［C］??Proc of the 7th Int Conf on Very Large Data Bases（VLDB）．San Francisco，CA：Morgan Kaufmann，1981：144 154

［3］Gray J，Reuter A．Transaction Processing：Concepts and Techniques［M］．San Francisco，CA：Morgan Kaufmann，1992：1070

［4］Mohan C，Haderle D，Lindsay B，et al．ARIES：A transaction recovery method supporting fine－granularity locking and partial rollbacks using write－ahead logging［J］．ACM Trans on Database System，1992，17（1）：94 162

［5］Sweeney A，Doucette D，Hu W，et al．Scalability in the XFS file system［C］??Proc of the 2nd USENIX Annual Technical Conf（USENIX ATC）．Berkeley，CA：USENIX Association，1996：167 181

［6］Tweedie S C．Journaling the Linux ext2fs filesystem［C］?? Proc of the 4th Annual Linux Expo．Berkeley，CA：Linux Expo，1998

［7］Hitz D，Lau J，Malcolm M A．File system design for an NFS file server appliance［C］??Proc of the USENIX Winter 1994 Technical Conf（WTEC）．Berkeley，CA：USENIX Association，1994：19 19

［8］Ganger G R，Patt Y N．Metadata update performance in file systems［C］??Proc of the 1st USENIX Conf on Operating Systems Design and Implementation（OSDI）．Berkeley，CA：USENIX Association，1994：5 14

［9］Peng Lin，Xie Lunguo，Zhang Xiaoqiang．Transactional memory system［J］．Journal of Computer Research and Development，2009，46（8）：1386 1398（in Chinese）（彭林，謝倫國，張小強(qiáng)．事務(wù)存儲系統(tǒng)［J］．計算機(jī)研究與發(fā)展，2009，46（8）：1386 1398）

［10］Herlihy M，Eliot J，Moss B．Transactional memory：Architectural support for lock－free data structures［C］??Proc of the 20th Annual Int Symp on Computer Architecture（ISCA）．New York：ACM，1993：289 300

［11］Xia Fei，Jiang Dejun，Xiong Jin，et al．A survey of phase change memory systems［J］．Journal of Computer Science and Technology，2015，30（1）：121 144

［12］Zhang Hongbin，F(xiàn)an Jie，Shu Jiwu，et al．Summary of storage system and technology based on phase change memory［J］．Journal of Computer Research and Development，2014，51（8）：1647 1662（in Chinese）（張鴻斌，范捷，舒繼武，等．基于相變存儲器的存儲系統(tǒng)與技術(shù)綜述［J］．計算機(jī)研究與發(fā)展，2014，51（8）：1647 1662）

［13］Qureshi M，Gurumurthi S，Rajendran B．Phase Change Memory：From Devices to Systems［M］．New York：Morgan Claypool Publishers，2011

［14］Qureshi M，Srinivasan V，Rivers J．Scalable high performance main memory system using phase－change memory technology［C］??Proc of the 36th Annual Int Symp on Computer Architecture（ISCA）．New York：ACM，2009：24 33

［15］Wu Zhangling，Jin Peiquan，Yue Lihua，et al．A survey on PCM－based big data storage and management［J］．Journal of Computer Research and Development，2015，52（2）：343 361（in Chinese）（吳章玲，金培權(quán)，岳麗華，等．基于PCM的大數(shù)據(jù)存儲與管理研究綜述［J］．計算機(jī)研究與發(fā)展，2015，52（2）：343 361）

［16］Zangeneh M，Joshi A．Design and optimization of nonvolatile multibit 1T1Rresistive RAM［J］．IEEE Trans on Very Large Scale Integration（VLSI）Systems，2014，22（8）：1815 1828

［17］Sheu S S，Cheng K H，Chang M F，et al．Fast－write resistive RAM（RRAM）for embedded applications［J］．IEEE Design ＆Test of Computers，2011，28（1）：64 71

［18］Tsunoda K，Kinoshita K，Noshiro H，et al．Low power and high speed switching of Ti－doped NiO ReRAM under the unipolar voltage source of less than 3V［C］??Proc of IEEE Int Electron Devices Meeting（IEDM）．Piscataway，NJ：IEEE，2007：767 770

［19］Andre T，Nahas J，Subramanian C，et al．A 4－Mb 0．18μm 1T1MTJ toggle MRAM with balanced three input sensing scheme and locally mirrored unidirectional write drivers［J］．IEEE Journal of Solid－State Circuits，2005，40（1）：301 309

［20］Senni S，Torres L，Sassatelli G，et al．Exploration of magnetic RAM based memory hierarchy for multicore architecture［C］??Proc of 2014IEEE Computer Society Annual Symp on VLSI（ISVLSI）．Piscataway，NJ：IEEE，2014：248 251

［21］Gartner Inc．Hype cycle for semiconductors and electronics technologies［EB?OL］．［2015－04－21］．https：??www．gartner．com?doc?2795317?hype－cycle－semiconductors－electronics－tech nologies

［22］Franklin M．Concurrency control and recovery［M］??The Computer Science and Engineering Handbook．Boca Raton，F(xiàn)L：CRC Press，1997：1058 1077

［23］Hall C，Bonnet P．Getting priorities straight：Improving Linux support for database I?O［C］??Proc of the 31st Int Conf on Very Large Data Bases（VLDB）．New York：ACM，2005：1116 1127

［24］Herzog R．PostgreSQL—The Linux of databases［J］．Linux Journal，1998，（46）：1 9

［25］Lomet D，Barga R，Mokbel M，et al．Immortal DB：Transaction time support for SQL server［C］??Proc of the 24th ACM SIGMOD Int Conf on Management of Data．New York：ACM，2005：939 941

［26］Lahiri T，Ganesh A，Weiss R，et al．Fast－Start：Quick fault recovery in oracle［C］??Proc of the 20th ACM SIGMOD Int Conf on Management of Data．New York：ACM，2001：593 598

［27］Kang W，Lee S，Moon B，et al．X－FTL：Transactional FTL for SQLite databases［C］??Proc of the 32nd ACM SIGMOD Int Conf on Management of Data．New York：ACM，2013：97 108

［28］Prabhakaran V，Arpaci－Dusseau A C，Arpaci－Dusseau R H．Analysis and evolution of journaling file systems［C］??Proc of the 11th USENIX Annual Technical Conf（USENIX ATC）．Berkeley，CA：USENIX Association，2005：105 120

［29］Powell H．ZFS and Btrfs：A quick introduction to modern filesystems［J］．Linux Journal，2012，（95）：218 223

［30］Rodeh O，Bacik J，Mason C．BTRFS：The Linux B－Tree filesystem［J］．ACM Trans on Storage，2013，9（3）：1 9

［31］Ganger G R，Mckusick M K，Soules C A N，et al．Soft updates：A solution to the metadata update problem in file systems［J］．ACM Trans on Computer System，2000，18（2）：127 153

［32］Stein C A，Howard J H，Seltzer M I．Unifying file system protection［C］??Proc of the 7th USENIX Annual Technical Conf（USENIX ATC）．Berkeley，CA：USENIX Association，2001：79 90

［33］Spillane R，Gaikwad S，Chinni M，et al．Enabling transactional file access via lightweight kernel extensions［C］??Proc of the 7th USENIX Conf on File and Storage Technologies（FAST）．Berkeley，CA：USENIX Association，2009：29 42

［34］Chidambaram V，Sharma T，Arpaci－Dusseau A C，et al．Consistency without ordering［C］??Proc of the 10th USENIX Conf on File and Storage Technologies（FAST）．Berkeley，CA：USENIX Association，2012：9 21

［35］Ma A，Dragga C，Arpaci－Dusseau A，et al．Ffsck：The fast file－system checker［J］．ACM Trans on Storage（TOS），2014，10（1）：2 14

［36］Detlev R．Flash Memories，Economic Principles of Performance，Cost and Reliability Optimization［M］．Berlin：Springer，2014

［37］Lu Youyou，Shu Jiwu．Survey on flash－based storage systems［J］．Journal of Computer Research and Development，2013，50（1）：49 59（in Chinese）（陸游游，舒繼武．閃存存儲系統(tǒng)綜述［J］．計算機(jī)研究與發(fā)展，2013，50（1）：49 59）

［38］Agrawal N，Prabhakaran V，Wobber T，et al．Design tradeoffs for SSD performance［C］??Proc of the 14th USENIX Annual Technical Conf（USENIX ATC）．Berkeley，CA：USENIX Association，2008：57 70

［39］Boboila S，Desnoyers P．Write endurance in flash drives：Measurements and analysis［C］??Proc of the 8th USENIX Conf on File and Storage Technologies（FAST）．Berkeley，CA：USENIX Association，2010：9 21

［40］Grupp L M，Caulfield A M，Coburn J，et al．Characterizing flash memory：Anomalies，observations，and applications［C］??Proc of the 42nd Annual IEEE?ACM Int Symp on Microarchitecture Conf（MICRO）．Piscataway，NJ：IEEE，2009：24 33

［41］Chen S．FlashLogging：Exploiting flash devices for synchronous logging performance［C］??Proc of the 28th ACM SIGMOD Int Conf on Management of Data．New York：ACM，2009：73 86

［42］Liu X，Salem K．Hybrid storage management for database systems［C］??Proc of the 32nd ACM SIGMOD Int Conf on Management of Data．New York：ACM，2013：541 552

［43］Zhang N，Tatemura J，Patel J，et al．Re－evaluating designs for multi－tenant OLTP workloads on SSD－basedI?O subsystems［C］??Proc of the 33rd ACM SIGMOD Int Conf on Management of Data．New York：ACM，2014：1383 1394

［44］Park S，Ji H Y，Seong Y O．Atomic write FTL for robust flash file system［C］??Proc of the 9th Int Symp on Consumer Electronics（ISCE）．Piscataway，NJ：IEEE，2005：155 160

［45］Fan Y，Meng X．MixSL：An efficient transaction recovery model in flash－based DBMS［G］??LNCS 7923：Proc of the 14th Int Conf on Web－Age Information Management．Berlin：Springer，2013：393 404

［46］Prabhakaran V，Rodeheffer T L，Zhou L．Transactional flash［C］??Proc of the 8th USENIX Conf on Operating Systems Design and Implementation（OSDI）．Berkeley，CA：USENIX Association，2008：147 160

［47］On S T，Xu J，Choi B，et al．Flag commit：Supporting efficient transaction recovery in flash－based DBMSs［J］．IEEE Trans on Knowledge and Data Engineering，2012，24（9）：1624 1639

［48］Kulkarni N，Gopinath K．Quick recovery in transactional flash［C］??Proc of 2013IEEE Int Conf on Electronics，Computing and Communication Technologies（CONECCT）．Piscataway，NJ：IEEE，2013：1 6

［49］Xiangyong O，Nellans D，Wipfel R，et al．Beyond block I?O：Rethinking traditional storage primitives［C］??Proc of the 17th IEEE Int Symp on High Performance Computer Architecture（HPCA）．Piscataway，NJ：IEEE，2011：301 311

［50］FusionIO Inc．In a battle of hardware，software innovation comes out on top［EB?OL］．FusionIO Research Center Blog，［2014－04－26］．http：??www．fusionio．com?blog?in－a－battle－ofhardware－software－innovation－comes－out－on－top

［51］Lu Youyou，Shu Jiwu，Guo Jia，et al．LightTx：A lightweight transactional design in flash－based SSDs to support flexible transactions［C］??Proc of the 31st IEEE Int Conf on Computer Design（ICCD）．Piscataway，NJ：IEEE，2013：115 122

［52］Shi Wei，Wang Dongsheng，Wang Zhanye，et al．M bius：A high performance transactional SSD with rich primitives［C］??Proc of the 30th Symp on Mass Storage Systems and Technologies（MSST）．Piscataway，NJ：IEEE，2014：1 11

［53］Wang Peng，Sun Guangyu，Jiang Song，et al．An efficient design and implementation of LSM－tree based key－value store on open－channel SSD［C］??Proc of the 9th European Conf on Computer Systems（EuroSys）．New York：ACM，2014：1 14

［54］Gao S，Xu J，He B，et al．PCMLogging：Reducing transaction logging overhead with PCM［C］??Proc of the 20th ACM Int Conf on Information and Knowledge Management（CIKM）．New York：ACM，2011：2401 2404

［55］Lee E，Bahn H，Noh S H．Unioning of the buffer cache and journaling layers with non－volatile memory［C］??Proc of the 11th USENIX Conf on File and Storage Technologies（FAST）．Berkeley，CA：USENIX Association，2013：73 80

［56］Zhao J，Li S，Yoon D H，et al．Kiln：Closing the performance gap between systems with and without persistence support［C］??Proc of the 46th Annual IEEE? ACM Int Symp on Microarchitecture（MICRO）．Piscataway，NJ：IEEE，2013：421 432

［57］Lu Youyou，Shu Jiwu，Sun Long，et al．Loose－ordering consistency for persistent memory［C］??Proc of the 32nd IEEE Int Conf on Computer Design（ICCD）．Piscataway，NJ：IEEE，2014：216 223

［58］Wang T，Johnson R．Scalable logging through emerging nonvolatile memory［C］??Proc of the 40th Int Conf on Very Large Data Bases（VLDB）．New York：ACM，2014：865 876

［59］Caulfield A M，De A，Coburn J，et al．Moneta：A highperformance storage array architecture for next－generation，non－volatile memories［C］??Proc of the 43rd Annual IEEE? ACM Int Symp on Microarchitecture（MICRO）．Piscataway，NJ：IEEE，2010：385 395

［60］Coburn J，Bunker T，Schwarz M，et al．From ARIES to MARS：Transaction support for next－generation，solid－state drives［C］??Proc of the 24th ACM Symp on Operating Systems Principles（SOSP）．New York：ACM，2013：197 212

［61］Mohan C，Lindsay B．Efficient commit protocols for the tree of processes model of distributed transactions［J］．SIGOPS Operating System Review，1985，19（2）：40 52

Shi Wei，born in 1988．PhD．Member of China Computer Federation．His research interests include flash－based storage and file systems．

Wang Dongsheng，born in 1966．PhD，professor and PhD supervisor．Senior member of China Computer Federation，member of IEEE．His research interests include computer architecture，high performance computing，storage and file systems，and network security（wds＠tsinghua．edu．cn）．

Survey on Transactional Storage Systems Based on Non－Volatile Memory

Shi Wei1and Wang Dongsheng1，21（Department of Computer Science and Technology，Tsinghua University，Beijing100084）2（Tsinghua National Laboratory for Information Science and Technology（TNLIST），Beijing100084）

With the emergence and further widespread use of non－volatile memory，the storage architecture is undergoing fundamental change．Transaction processing technologies in traditional database systems and file systems are mostly designed for rotating disks while they cannot take full advantage of new features of non－volatile memory．To take full advantage of the non－volatile memory characteristics and narrow the gap between system I?O performance and CPU processing performance，transactional storage systems and technologies designed based on non－volatile memory have gained focus and great popularity．In this paper，current status of the software layer transaction processing technologies，which are used in traditional database systems and file systems，are addressed in brief firstly．Then based on the division of non－volatile memory which includes flash and phase－change memory，the existing transactional storage systems based on non－volatile memory are discussed．Finally，the research works are summarized and the possible research directions are pointed out．Among the discussion，for the research of transactional flash－based storage systems，analysis of the optimization of transaction processing technologies using traditional host interface flash storage devices is given first，followed by analysis and comparison of the characteristics of the transaction flash storage systems using dedicated transactional interfaces．For the research of transactional PCM－based transactional storage systems，using PCM in both main memory and external storage environment for transaction processing is analyzed and compared，and the key technologies including the combination of log and cache and fine－grained logging are discussed．

non－volatile memory；flash memory；phase change memory（PCM）；transaction processing；transactional storage system；I?O stack

TP302．1

2014－12－10；

2015－05－18

國家自然科學(xué)基金項(xiàng)目（61373025，61303002）；國家“八六三”高技術(shù)研究發(fā)展計劃基金項(xiàng)目（2012AA010905）This work was supported by the National Natural Science Foundation of China（61373025，61303002）and the National High Technology Research and Development Program of China（863Program）（2012AA010905）．