陳玉標(biāo)，李建中，高 宏

（哈爾濱工業(yè)大學(xué) 海量數(shù)據(jù)計(jì)算研究中心，哈爾濱 150001）

0 引 言

近些年，處理器和傳統(tǒng)磁盤之間的性能代溝越來越大，外存儲(chǔ)器的性能成為很多外存索引和算法的瓶頸。加之大數(shù)據(jù)時(shí)代的到來，使得該瓶頸缺點(diǎn)愈加明顯。隨著閃存和固態(tài)盤的出現(xiàn)，大大縮減處理器和外存存儲(chǔ)器之間的代溝。由于閃存和固態(tài)盤的存儲(chǔ)機(jī)理完全不同于磁盤，很多基于磁盤的優(yōu)化研究不再有效。因而，近年來閃存存儲(chǔ)設(shè)備已經(jīng)引起大家強(qiáng)烈的興趣和廣泛研究，基于閃存和固態(tài)盤的數(shù)據(jù)管理也成為一個(gè)熱門的研究領(lǐng)域。

早些年，數(shù)據(jù)管理系統(tǒng)中的索引和算法主要是針對磁盤的I／O 特性進(jìn)行設(shè)計(jì)和優(yōu)化。由于閃存介質(zhì)和磁盤存儲(chǔ)的原理完全不同，因而擁有完全不同的I／O 特性。磁盤又叫機(jī)械硬盤，其以磁作為存儲(chǔ)介質(zhì)，因而包含讀寫磁介質(zhì)的磁頭和驅(qū)動(dòng)磁頭的轉(zhuǎn)動(dòng)裝置。當(dāng)讀寫數(shù)據(jù)時(shí)，需要先將磁頭指向讀寫的目標(biāo)地址，這個(gè)過程叫做尋道，即通過轉(zhuǎn)動(dòng)盤片和移動(dòng)磁頭來定位數(shù)據(jù)在磁盤中的位置。然后，讀取該位置的數(shù)據(jù)或?qū)?shù)據(jù)寫進(jìn)該位置。根據(jù)上述磁盤讀寫的過程很容易看出，磁盤讀寫對于順序讀寫性能會(huì)比較好。當(dāng)遇到隨機(jī)讀寫時(shí)，大量的時(shí)間花費(fèi)在尋道過程中，從而導(dǎo)致隨機(jī)讀寫帶寬極劇下降。閃存作為一種半導(dǎo)體電子設(shè)備，其內(nèi)部不包含任何機(jī)械部件，完全靠電路控制來進(jìn)行數(shù)據(jù)讀寫操作，避免了磁盤的缺點(diǎn)。因而，之前基于磁盤I／O 特點(diǎn)做的優(yōu)化工作不再有效，在閃存固態(tài)盤上需要被重新設(shè)計(jì)和研究。相對于磁盤，閃存擁有以下特點(diǎn)：

（1）讀寫延遲低：閃存是純粹的電子器件，內(nèi)部所有操作都是由電路實(shí)現(xiàn)。因而閃存讀寫延遲很低，且讀寫延遲和尋址的位置無關(guān)。因而，對于閃存沒有緩存的芯片，順序讀寫和隨機(jī)讀寫延遲相同。

（2）讀寫單元頁：頁是閃存芯片操作的最小物理讀寫單元。所有上層的大塊讀寫最終在閃存芯片層面都會(huì)分解成頁物理單元進(jìn)行操作。閃存內(nèi)一個(gè)塊中包含很多頁，但頁的寫并不是隨意的。已經(jīng)寫過的頁是不能進(jìn)行寫的，寫前必須進(jìn)行擦除操作；有些MLC、TLC、QLC 多層結(jié)構(gòu)的閃存芯片，要求上層頁寫過之后，才能寫下層頁；而另外一些閃存芯片寫塊中，必須前序的頁都寫過才能進(jìn)行下一個(gè)位置頁的寫入等。當(dāng)然，由于真實(shí)的閃存設(shè)備上層都會(huì)配置一個(gè)FTL（閃存翻譯層），通過異步讀寫，重新映射的方法，可以完全對用戶隱藏這些限制。

（3）讀寫不對稱：閃存設(shè)備的存儲(chǔ)單元的寫操作采用ISPP 技術(shù)，不斷對存儲(chǔ)單元進(jìn)行加電壓來進(jìn)行充電，直到達(dá)到指定電位。因而，該過程很費(fèi)時(shí)。而讀過程，只需要獲取存儲(chǔ)單元的電位大小即可，因而很迅速。因而，閃存的讀操作和寫操作之間的延遲相差會(huì)比較大，這就是閃存的讀寫不對稱。

（4）寫前擦除機(jī)制：由于閃存存儲(chǔ)單元的寫操作是一個(gè)充電過程，且充的是電子。因而，即將被寫的存儲(chǔ)單元為了確保寫入成功，在此之前必須釋放所有電子。閃存引入一個(gè)批量的放電操作，叫做擦除。擦除的延遲很高，如果按照磁盤的更新方式，對所有數(shù)據(jù)進(jìn)行“就地更新”，那么就會(huì)對已經(jīng)寫過的數(shù)據(jù)頁進(jìn)行寫。由于寫前擦除機(jī)制，延遲會(huì)非常大。為了優(yōu)化寫操作，閃存引入“異地更新”策略。即每次對數(shù)據(jù)頁進(jìn)行修改重寫，都會(huì)尋找一個(gè)新的空白頁進(jìn)行寫入操作。其會(huì)在閃存上設(shè)計(jì)一個(gè)閃存翻譯層（FTL），實(shí)時(shí)保持虛擬地址到物理地址的映射。這樣看來，對于上層用戶來說，寫的還是同一虛擬地址頁，但實(shí)際寫的是不同的物理地址。

（5）擦除粒度大：閃存為擦除的單元稱為塊，塊要比頁大很多。如圖1 所示，1 塊（block）包含256頁（page）。即這里擦除一塊就會(huì)對塊內(nèi)256 頁進(jìn)行擦除。擦除之后的頁都是待寫頁。如果塊內(nèi)已經(jīng)被寫頁，又有寫操作需求，就還需要重新對整個(gè)塊進(jìn)行擦除。每個(gè)塊都有自己的壽命，擦除次數(shù)是有限制的。超過次數(shù)限制的塊，塊內(nèi)數(shù)據(jù)就會(huì)降低安全性。

圖1 閃存包結(jié)構(gòu)圖Fig.1 The architecture of flash package

閃存的特點(diǎn)中有些是優(yōu)點(diǎn)，有些是缺點(diǎn)和限制。目前，基于閃存的數(shù)據(jù)管理技術(shù)已經(jīng)取得了不錯(cuò)的進(jìn)展，其整體的思路都是想辦法去發(fā)揮閃存的優(yōu)勢（如隨機(jī)讀），盡量避免其缺點(diǎn)（如時(shí)間成本高和壽命縮減的擦除操作）。為此本文將按照閃存上數(shù)據(jù)管理各個(gè)研究方向分別進(jìn)行歸納整理。

1 閃存存儲(chǔ)系統(tǒng)

大數(shù)據(jù)時(shí)代到來，對于存儲(chǔ)系統(tǒng)的要求越來越高。對于這些存儲(chǔ)系統(tǒng)，性能和耗能這兩項(xiàng)指標(biāo)都至關(guān)重要。由于閃存和固態(tài)盤性能高且耗能低，因而被考慮應(yīng)用于存儲(chǔ)系統(tǒng)平臺(tái)。FAWN［1］是一個(gè)key－value 存儲(chǔ)系統(tǒng)，其用一些低能耗的處理器和低能耗的閃存設(shè)備搭配，來平衡計(jì)算和I／O 能力，使得整體分布式數(shù)據(jù)處理平臺(tái)耗能變低。內(nèi)存很珍貴，且成本耗能非常高，于是在Google Fusion Tables［2］系統(tǒng)中，動(dòng)態(tài)配置固態(tài)盤作為內(nèi)存的拓展。為了更充分地開發(fā)閃存存儲(chǔ)的性能，Gordon［3］實(shí)現(xiàn)了一種新的flash 翻譯層，其能針對數(shù)據(jù)密集型工作負(fù)載和大型閃存存儲(chǔ)數(shù)組，充分發(fā)揮閃存性能。這些存儲(chǔ)系統(tǒng)平臺(tái)都是直接利用閃存低能耗和高讀寫帶寬的特點(diǎn)直接對其進(jìn)行優(yōu)化。

2 閃存文件系統(tǒng)

文件系統(tǒng)作為上層應(yīng)用和底層存儲(chǔ)之間的關(guān)鍵環(huán)節(jié)，對于其優(yōu)化具有重要意義。早前，有放棄索引結(jié)構(gòu)的極端方式。如，Pilot［4］直接通過一個(gè)64 位的UID 來進(jìn)行數(shù)據(jù)訪問和定位，其明顯的缺點(diǎn)就是對于代價(jià)更高的寫操作表現(xiàn)會(huì)非常差。

2.1 日志結(jié)構(gòu)

主流文件系統(tǒng)，從磁盤開始主要采用日志結(jié)構(gòu)。日志結(jié)構(gòu)的文件系統(tǒng)主要分為兩種類型：一種是日記方式［5－8］，另外一種是日志方式［9］。日志結(jié)構(gòu)的文件系統(tǒng)對于隨機(jī)寫性能表現(xiàn)良好，但隨機(jī)寫在閃存存儲(chǔ)器上依然是個(gè)痛點(diǎn)，因而基于日志結(jié)構(gòu)的閃存文件系統(tǒng)也應(yīng)運(yùn)而生。其中基于日記方式的文件系統(tǒng)有JFTL［10］和JFFS［11］。JFFS 直接在閃存上根據(jù)閃存特性，建立最簡單的日記系統(tǒng)；而JFTL 將日記系統(tǒng)建立在FTL 上，為保證數(shù)據(jù)一致性，將會(huì)同時(shí)修改在閃存日記區(qū)域和數(shù)據(jù)區(qū)域記錄。由于閃存塊的壽命有限，壞塊對于閃存的性能和可靠性影響比較大，因而如何去保證閃存塊內(nèi)的磨損均衡至關(guān)重要。SFS［12］通過記錄塊的使用情況，并采用對冷熱數(shù)據(jù)分組的辦法來實(shí)現(xiàn)磨損均衡的目的。F2FS［13］雖也采用冷熱數(shù)據(jù)分組的方式，但其會(huì)根據(jù)文件和數(shù)據(jù)的類型來進(jìn)行分組，以避免粒度小、頻繁而代價(jià)高昂的元數(shù)據(jù)寫操作。

2.2 對象存儲(chǔ)和其它

除此之外，考慮數(shù)據(jù)特點(diǎn)，為了解決和處理數(shù)據(jù)的離散單元問題，基于對象存儲(chǔ)的閃存文件系統(tǒng)的OFSS［14］應(yīng)運(yùn)而生，其主要考慮將存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)和閃存存儲(chǔ)器內(nèi)部結(jié)構(gòu)相適應(yīng)?？紤]到閃存讀寫不對稱特點(diǎn)，ReconFS［15］嘗試去設(shè)計(jì)持久性的目錄樹來平衡讀寫的性能。針對固態(tài)盤內(nèi)部并行性，ParaFS［16］在固態(tài)盤內(nèi)部各個(gè)環(huán)節(jié)，利用加速內(nèi)部并行性來提高文件系統(tǒng)性能。

2.3 開源項(xiàng)目

目前，最主流的開源項(xiàng)目是Yaffs［17］和JFFS［11］，被廣泛應(yīng)用和采納的文件系統(tǒng)，都已被閃嵌入到Linux 內(nèi)核中，對于閃存文件系統(tǒng)的開發(fā)學(xué)習(xí)具有重要推動(dòng)作用。

3 閃存轉(zhuǎn)換層

閃存翻譯層（FTL）是固態(tài)盤內(nèi)部最核心的組件，主要負(fù)責(zé)邏輯地址到物理地址的映射、垃圾回收、磨損均衡、斷電恢復(fù)等。通過實(shí)現(xiàn)上述功能，其隱藏了固態(tài)盤內(nèi)部的結(jié)構(gòu)，讓用戶可以像磁盤一樣使用固態(tài)盤。由于FTL 的表現(xiàn)直接影響著整個(gè)固態(tài)盤的數(shù)據(jù)和性能，因此FTL 作為固態(tài)盤企業(yè)的核心資產(chǎn)，屬于商業(yè)機(jī)密，但在學(xué)術(shù)界對FTL 進(jìn)行了詳細(xì)的研究。

3.1 同質(zhì)固態(tài)盤FT

按照映射單元，可以將FTL 分為：頁級(jí)別FTL、塊級(jí)別FTL、混合FTL 和變長映射FTL 4 種類型。頁級(jí)別FTL 能將請求的邏輯頁面映射到閃存空間中的任何物理頁面。因此，該映射機(jī)制很靈活，具有很高的閃存頁面利用率。其代表性工作在文獻(xiàn)［18－20］中有所體現(xiàn)。塊級(jí)別FTL 是將請求的邏輯塊映射到閃存空間中的任意物理塊。頁尋址是塊地址加上偏移量來獲得，這樣做的優(yōu)點(diǎn)是映射表會(huì)小很多，占用更少的內(nèi)存，減少固態(tài)盤的制作成本；缺點(diǎn)是會(huì)造成閃存空間的浪費(fèi)，以及垃圾回收代價(jià)增加。其代表性工作在文獻(xiàn)［21－22］中有所體現(xiàn)?；旌系腇TL，結(jié)合頁級(jí)別映射和塊級(jí)別映射的優(yōu)點(diǎn)，使得FTL即具備頁級(jí)別映射靈活性的特點(diǎn)，又具備塊級(jí)別映射表小的優(yōu)點(diǎn)。實(shí)現(xiàn)方式是將固態(tài)盤內(nèi)的塊分為數(shù)據(jù)塊和日志塊兩類，數(shù)據(jù)塊采用塊映射保存數(shù)據(jù)，日志塊采用頁映射保存更新信息。由于日志塊占整體固態(tài)盤的比例很低，因而頁映射表很小。LAST［23］、BAST［24］、A－SAST［25］、SAST［26］、SuperBlock－FTL［27］均采用混合FTL 設(shè)計(jì)。

無論頁級(jí)別映射或塊級(jí)別映射，均是定長映射。而對于多媒體場景，大部分訪問是大批量順序?qū)懖僮鳎ㄩL映射會(huì)帶來映射表的冗余。因而文獻(xiàn)［28］提出一種變長的映射機(jī)制，來實(shí)現(xiàn)映射粒度的動(dòng)態(tài)調(diào)整。這種映射的缺點(diǎn)，就是FTL 的邏輯地址到物理地址翻譯速度會(huì)很慢。

3.2 混合固態(tài)盤FTL

一般情況下，默認(rèn)固態(tài)盤內(nèi)部閃存介質(zhì)是單一的。例如：閃存均采用MLC 固態(tài)盤，面向同類型閃存的FTL 統(tǒng)稱為同質(zhì)固態(tài)盤FTL。SLC與MLC、TLC、QLC 相比，優(yōu)點(diǎn)是讀寫速度快、能耗低，缺點(diǎn)是數(shù)據(jù)密度低和單價(jià)高。為了合理的利用其特點(diǎn)，對應(yīng)多類型閃存介質(zhì)的FTL 稱為混合固態(tài)盤FTL。實(shí)際上MLC、TLC 和QLC 可以通過更改設(shè)置讓其當(dāng)作SLC 使用。因而，混合固態(tài)盤可以分為兩種類型，一種稱為硬劃分固態(tài)盤，即固態(tài)盤內(nèi)部同時(shí)包含SLC和其它多層閃存介質(zhì)；另外一種稱為軟劃分固態(tài)盤，即雖然固態(tài)盤內(nèi)部只有一種閃存介質(zhì)，但是可以通過更改設(shè)置，讓固態(tài)盤內(nèi)部的多層閃存的一部分當(dāng)作SLC使用。硬化分的FTL算法有CFTL［29］、ComboFTL［30］和DPAFTL［31］等。CFTL、ComboFTL和DPAFTL 將冷熱數(shù)據(jù)分別存儲(chǔ)在MLC 和SLC 上，用來優(yōu)化整體性能。軟劃分固態(tài)盤有TLC－FTL［32］、HFTL［33］。冷熱數(shù)據(jù)一般是按照訪問頻數(shù)來進(jìn)行分類，而TLC－FTL 和HFTL 是采用訪問數(shù)據(jù)的大小進(jìn)行分類，其在固態(tài)盤內(nèi)部維護(hù)一個(gè)SLC 的環(huán)形緩沖區(qū)，當(dāng)有較小的寫到來時(shí)，就將其放進(jìn)改寫區(qū)域，通過維護(hù)一個(gè)熱數(shù)據(jù)識(shí)別方法來控制SLC 到非SLC區(qū)域數(shù)據(jù)的遷移。

3.3 雙模式FTL

固態(tài)盤的FTL 要同時(shí)兼顧讀寫操作的性能，但一些應(yīng)用只有讀操作或者寫操作。文獻(xiàn)［34］首次提出雙模式FTL 的概念。雙模式FTL 一般包括兩種模式：一是支持隨機(jī)讀操作、順序讀操作，禁止隨機(jī)寫操作但支持順序?qū)懖僮?，能為隨機(jī)讀、順序讀和順序?qū)懱峁┳顑?yōu)的性能保證；二是支持隨機(jī)寫操作，但不能保證提供最優(yōu)的性能。根據(jù)不同的應(yīng)用場景可以設(shè)置FTL模式，來實(shí)現(xiàn)固態(tài)盤性能的最大化。

3.4 內(nèi)部并行性加速

為了利用固態(tài)盤內(nèi)部并行性來加速固態(tài)盤內(nèi)部的讀寫操作，基于DFTL 改進(jìn)的Parallel－DFT［35］被提出。其提出了一個(gè)創(chuàng)新的IO 調(diào)度策略，與DFTL一起工作以打破DFTL 數(shù)據(jù)訪問地址轉(zhuǎn)換操作的耦合，并行地安排DFTL 地址轉(zhuǎn)換和數(shù)據(jù)訪問操作，允許固態(tài)盤使其閃存訪問通道資源，兩種類型的操作都是完全并行的。

4 閃存數(shù)據(jù)庫日志

閃存數(shù)據(jù)庫的管理通常采用頁管理，有時(shí)候也會(huì)采用日志管理的方式［36］。由于閃存的更新都是異步更新，因而如果能跳過FTL在固態(tài)盤內(nèi)部進(jìn)行優(yōu)化，便可以將所有更新過程中的歷史物理頁直接當(dāng)作日志記錄。這種方式對于寫操作性能優(yōu)秀，但是讀成本代價(jià)很高。大部分情況下，閃存數(shù)據(jù)庫的日志主要用于系統(tǒng)恢復(fù)［37］。但也有一些直接在閃存上通過日志的方式建立索引結(jié)構(gòu)，比如：B樹［38－39］。

5 閃存數(shù)據(jù)庫緩沖區(qū)

在內(nèi)存中設(shè)置緩沖區(qū)，將經(jīng)常被訪問或最有可能即將被訪問的數(shù)據(jù)放進(jìn)緩沖區(qū)中，可以明顯地減少I／O，提升系統(tǒng)整體的性能表現(xiàn)。因而對于閃存緩沖區(qū)的優(yōu)化具有重要意義。

5.1 經(jīng)典緩沖策略

早期的緩沖區(qū)研究工作，主要考慮閃存讀寫不對稱的特點(diǎn)進(jìn)行優(yōu)化［40－42］。緩沖區(qū)維護(hù)能減少I／O的基本原理，是操作系統(tǒng)中數(shù)據(jù)訪問的空間局域性和時(shí)間局部性，其是超越存儲(chǔ)介質(zhì)特性的存在，因而很多閃存固態(tài)盤上的緩沖區(qū)維護(hù)算法繼承了磁盤緩沖區(qū)的策略。如：CFLRU［43］、LRU－WSR［44］和CCFLRU［45］就是繼承經(jīng)典的LRU 緩沖區(qū)策略改進(jìn)的算法。而LIRS［46］不僅考慮LRU 策略的時(shí)間臨近性，還加入了訪問頻數(shù)來加入緩沖區(qū)的維護(hù)策略。LIRS－WSR［47］想著重優(yōu)化減少寫操作，維護(hù)臟頁頻數(shù)，并對頻數(shù)進(jìn)行排序，通過延遲頻數(shù)高的逐出策略盡可能少的進(jìn)行寫操作。

5.2 自適應(yīng)緩沖區(qū)

上述這些緩沖區(qū)算法都是基于寫代價(jià)比讀代價(jià)高的特點(diǎn)進(jìn)行設(shè)計(jì)，但不同閃存設(shè)備的讀寫代價(jià)比往往不同。因而，能夠自動(dòng)適應(yīng)不同類型閃存的緩沖區(qū)維護(hù)算法就變的非常必要。CASE［48］通過動(dòng)態(tài)維護(hù)干凈頁鏈表和臟頁鏈表長度，來自適應(yīng)獲取不同讀寫代價(jià)比閃存設(shè)備的最佳配置。ACR［49］和CRAW－C［50］也依據(jù)該思路進(jìn)行優(yōu)化。不同的是，ACR 不僅能自適應(yīng)不同的閃存環(huán)境，還能自適應(yīng)不同的讀寫訪問模式，而CRAW－C 是針對壓縮的文件系統(tǒng)環(huán)境設(shè)計(jì)。

5.3 寫合并緩沖區(qū)

頻繁細(xì)粒度的寫除了延遲代價(jià)高之外，還會(huì)造成閃存固態(tài)盤內(nèi)部的垃圾回收。垃圾回收成本很高，會(huì)造成大量的塊合并和擦除操作。為了減少塊擦除操作的次數(shù)，F(xiàn)AB［51］和BPLRU［52］采用塊作為緩沖區(qū)的替換單元來達(dá)到此目的。另外，基于已有的CFLRU，加入寫聚集的策略，CFLRU 的優(yōu)化版本CFDC［53］被提出。

6 閃存數(shù)據(jù)索引

索引是數(shù)據(jù)管理系統(tǒng)中最重要的組織工具，優(yōu)秀的索引能大大提升數(shù)據(jù)訪問的性能。下面將介紹閃存上具有代表性的幾個(gè)重要索引結(jié)構(gòu)的優(yōu)化研究。

6.1 B－樹優(yōu)化

B 樹和B＋樹在更新結(jié)構(gòu)時(shí)，會(huì)涉及大量的更新。一般情況下該索引存儲(chǔ)在文件中，和閃存介質(zhì)之間隔著一個(gè)FTL 層，其結(jié)果便是更新的寫放大極其嚴(yán)重。因而，文獻(xiàn)［54－56］直接在閃存介質(zhì)上基于日志的思想建立一個(gè)B 樹，這樣就能讓B 樹很好的支持頻繁且細(xì)粒度的更新操作。B 樹能夠有效的支持隨機(jī)查詢，但是對于順序查詢效果較差。因而，實(shí)際數(shù)據(jù)管理工具采用的核心數(shù)據(jù)結(jié)構(gòu)往往是B＋樹。對于閃存B＋樹的優(yōu)化，文獻(xiàn)［57］主要考慮很好的利用固態(tài)盤內(nèi)部的內(nèi)存資源，一部分內(nèi)存緩存B＋樹頁子結(jié)點(diǎn)，另外一部分緩存更新請求，對更新操作采用延遲滿足的策略來實(shí)現(xiàn)B＋樹更新過程較少的寫操作。

6.2 μ 樹優(yōu)化

傳統(tǒng)的B 樹和B＋樹每個(gè)結(jié)點(diǎn)的扇出都是相同的，而μ 樹［58］采用一種從根結(jié)點(diǎn)往下，每一層扇出以2 為倍數(shù)遞增式增加的方式，將一棵樹存儲(chǔ)到閃存的一頁上。當(dāng)樹內(nèi)有更改時(shí)，直接再存儲(chǔ)一頁。這樣做的情況下，在小數(shù)據(jù)規(guī)模維護(hù)時(shí)，任何一次更新最多對于索引只更新1 頁。優(yōu)點(diǎn)是能夠減少更新時(shí)寫的頁數(shù)量，缺點(diǎn)是同樣的數(shù)據(jù)需要的索引存儲(chǔ)空間會(huì)增大。相比之下，在更新比較頻繁的情況下，該索引表現(xiàn)會(huì)非常優(yōu)秀。

6.3 FD 樹優(yōu)化

基于B＋樹，F(xiàn)D 樹［59］采用和LSM 樹類似的思想，將其作為頭部索引，在其下方加了兩層有序段。其每一層都有一定的容量，容量階梯式增加，當(dāng)上一層滿時(shí)與下一層合并。這樣能有效減少隨機(jī)寫帶來的寫放大。LA－tree［60］采取了類似的惰性更新的思想，區(qū)別是其通過一個(gè)級(jí)聯(lián)的緩沖區(qū)，在緩沖區(qū)內(nèi)優(yōu)化合并更新操作，來減少更新帶來的寫代價(jià)。

6.4 哈希索引優(yōu)化

哈希索引也是數(shù)據(jù)管理系統(tǒng)中一個(gè)重要的索引結(jié)構(gòu)，很多基本操作都需要基于該索引完成。但是，哈希索引對于閃存介質(zhì)而言具有天然的不適應(yīng)性。因?yàn)槠涓挛恢镁请S機(jī)的，且哈希更新細(xì)粒度的操作居多，因而會(huì)帶來巨大的寫放大效果。對于插入更新操作，SAL－HASH［61］采用和LSM 樹類似的思路，通過多層合并，盡量減少隨機(jī)寫帶來的寫放大。MicroHash［62］主要的優(yōu)化思路是消除時(shí)間和能耗代價(jià)高昂的隨機(jī)刪除操作，通過索引和數(shù)據(jù)的調(diào)整，讓刪除以塊的形式進(jìn)行，以達(dá)到對哈希索引的性能和能耗進(jìn)行的優(yōu)化。

7 閃存數(shù)據(jù)庫查詢處理

查詢過程的優(yōu)化和存儲(chǔ)模式是直接相關(guān)的，因而這里將先介紹閃存數(shù)據(jù)庫的頁存儲(chǔ)模式，然后介紹基于該存儲(chǔ)模式的經(jīng)典的連接研究工作。

7.1 頁存儲(chǔ)模式

閃存頁數(shù)據(jù)的存儲(chǔ)主要有3 種模式：NSM（行式數(shù)據(jù)存儲(chǔ)）、DSM（列式數(shù)據(jù)存儲(chǔ)）、PAX（混合數(shù)據(jù)存儲(chǔ)）。PAX 實(shí)際上就是在NSM 頁內(nèi)部采用類似于DSM 的組織方式。連接操作往往只需要讀取、輸出和連接列相關(guān)的屬性值，不需要處理所有的列屬性值。連接操作是樹查詢中的核心算法，閃存連接算法RARE－join［63］基于PAX 存儲(chǔ)模式，其只選擇和查詢結(jié)果相關(guān)的列屬性，減少中間結(jié)果的生成來加速整個(gè)連接過程。缺點(diǎn)是相對于NSM 和DSM，PAX 維護(hù)成本較高。

7.2 連接算法優(yōu)化

傳統(tǒng)的連接算法，基于磁盤主要考慮的是減少代價(jià)很高的隨機(jī)讀寫，增加順序讀寫的比例。但是這種優(yōu)化在支持快速隨機(jī)讀寫的閃存上并沒有明顯的優(yōu)化效果。因而，基于PAX 存儲(chǔ)模式的Digest－Join［64］嘗試發(fā)揮閃存的快速隨機(jī)讀寫，來加速連接操作執(zhí)行。Digest－Join 分為兩個(gè)階段，第一階段生成摘要表，第二階段通過隨機(jī)讀來連接。難點(diǎn)是第二階段最小化頁的讀數(shù)據(jù)量的NP 復(fù)雜度“頁抓取問題”。Digest－Join 采取啟發(fā)式的方法來解決該問題。SubJoin［65］根據(jù)連接列進(jìn)行排序形成連接子表，然后進(jìn)行連接。SubJoin 對于每個(gè)子表連接中的屬性進(jìn)行DSM 列存儲(chǔ)，需要連接的屬性數(shù)據(jù)均從原始數(shù)據(jù)中獲取。這樣做，就是用順序?qū)懱娲S機(jī)讀操作，從固態(tài)盤的性能角度看，性能上有所提升。

8 混合存儲(chǔ)系統(tǒng)

固態(tài)盤雖然具有很好的性能優(yōu)勢，但其價(jià)格依然相對比較高，且固態(tài)盤壽命有限。數(shù)據(jù)訪問往往具有時(shí)間局部性和空間局部性，因而一種思路就是將固態(tài)盤作為內(nèi)存和磁盤之間緩存。固態(tài)盤能有效的支持隨機(jī)讀寫，且相對于磁盤讀寫帶寬高很多，磁盤順序讀寫帶寬表現(xiàn)良好，因而另外一種思路就是結(jié)合兩者的優(yōu)點(diǎn)，將數(shù)據(jù)合理地分配在兩種存儲(chǔ)介質(zhì)上，以實(shí)現(xiàn)存儲(chǔ)系統(tǒng)的提升。

文獻(xiàn)［66－67］嘗試將固態(tài)盤作為內(nèi)存和磁盤之間的擴(kuò)展緩存，來改善存儲(chǔ)系統(tǒng)整體的I／O 性能表現(xiàn)。文獻(xiàn)［68］以延長固態(tài)盤壽命為目的，結(jié)合磁盤順序?qū)懶阅鼙憩F(xiàn)良好的特點(diǎn)，將磁盤作為固態(tài)盤的寫緩存，這樣就能對寫操作進(jìn)行進(jìn)一步的處理合并，減少數(shù)據(jù)最終寫到固態(tài)盤的寫放大，減少寫帶來的擦除操作，達(dá)到延長固態(tài)盤壽命的目的。實(shí)際數(shù)據(jù)管理中，不同數(shù)據(jù)訪問的模式存在不同特點(diǎn)，有些數(shù)據(jù)會(huì)被經(jīng)常訪問，有些訪問頻數(shù)比較少，有些數(shù)據(jù)是更新密集型，有些是讀密集型等等。如果能識(shí)別出這些數(shù)據(jù)，能夠合理的分配到固態(tài)盤和磁盤上，就能讓存儲(chǔ)系統(tǒng)的整體性能接近純固態(tài)盤的存儲(chǔ)性能。I－CASH［69］嘗試識(shí)別出寫密集的數(shù)據(jù)，并將其修改成以日志的方式存儲(chǔ)在磁盤上，以減少固態(tài)盤的寫操作。對于磁盤固態(tài)盤混合存儲(chǔ)的環(huán)境，Hystor［70］設(shè)法尋找出影響整體性能關(guān)鍵的數(shù)據(jù)，將其放置到性能更優(yōu)異的固態(tài)盤上，以提高整體存儲(chǔ)系統(tǒng)的性能。

9 結(jié)束語

本文首先對閃存的特性進(jìn)行描述，然后分別對閃存數(shù)據(jù)管理各領(lǐng)域的研究情況進(jìn)行了詳細(xì)的介紹，分別指出基于閃存各類算法的優(yōu)化思路。概括來看，這些優(yōu)化思想主要分為4 大類：第一類，使用閃存的優(yōu)良特點(diǎn)直接進(jìn)行優(yōu)化；第二類，用成本更低的讀操作代替成本更高的寫操作；第三類，通過日志的策略，將寫操作順序化，以減少寫放大；第四類，通過懶惰執(zhí)行合并操作，以減少對閃存的寫放大?？偟膩碚f，目前幾乎所有的研究工作都主要是通過上述4 種思路，對閃存上的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行優(yōu)化。