摘  要： 隨著閃存技術(shù)的發(fā)展和閃存容量的不斷增大，閃存存儲(chǔ)被廣泛應(yīng)用，給閃存數(shù)據(jù)庫(kù)管理帶來(lái)機(jī)遇和挑戰(zhàn)。因?yàn)殚W存和磁盤(pán)讀寫(xiě)方式不同，讀寫(xiě)性能也有差別，所以對(duì)于閃存緩沖區(qū)的管理成為一個(gè)亟待解決的問(wèn)題。為了提高閃存的訪問(wèn)性能，緩沖區(qū)置換算法在保證命中率的同時(shí)要盡量減少寫(xiě)和擦除操作的次數(shù)。對(duì)主流的閃存數(shù)據(jù)庫(kù)緩沖區(qū)置換算法進(jìn)行分析，比較了幾種算法的優(yōu)點(diǎn)和不足，并給出了未來(lái)研究的方向。

　　關(guān)鍵詞： 閃存；閃存數(shù)據(jù)庫(kù)；緩沖區(qū)置換算法

0 引言

　　近年來(lái)，閃存存儲(chǔ)作為新一代的存儲(chǔ)介質(zhì)，憑借其存寫(xiě)速度快、功耗低、體積小、抗震等優(yōu)良特性，已經(jīng)被廣泛應(yīng)用在嵌入式系統(tǒng)、航空航天以及各種企業(yè)級(jí)的數(shù)據(jù)存儲(chǔ)系統(tǒng)中[1]。

　　由于閃存和磁盤(pán)在物理結(jié)構(gòu)、數(shù)據(jù)存取方式等方面存在明顯的差異，而現(xiàn)有的數(shù)據(jù)庫(kù)系統(tǒng)中的各類(lèi)數(shù)據(jù)結(jié)構(gòu)和算法都是針對(duì)磁盤(pán)專門(mén)開(kāi)發(fā)的，因此目前已有的基于磁盤(pán)的應(yīng)用（如文件系統(tǒng)等）無(wú)法直接支持閃存而充分發(fā)揮閃存存儲(chǔ)的優(yōu)越性[2]。因此，針對(duì)閃存存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法（如數(shù)據(jù)存儲(chǔ)、索引、緩沖區(qū)管理等）都很有研究的必要。其中緩沖區(qū)作為閃存數(shù)據(jù)庫(kù)的系統(tǒng)的核心組件，其替換算法更是一個(gè)比較熱門(mén)的研究問(wèn)題，受到深度的重視。

1 閃存及緩沖區(qū)管理算法

　　1.1 閃存存儲(chǔ)

　　閃存存儲(chǔ)器一般可以分為NOR型和NAND型兩種，其中NOR型閃存以字節(jié)為存取單位，按位進(jìn)行訪問(wèn)，讀速快，但擦除和寫(xiě)速較慢，主要用于存儲(chǔ)程序和少量數(shù)據(jù)。NAND型閃存以數(shù)據(jù)頁(yè)為存儲(chǔ)單位，容量較大，價(jià)格低，主要用于存儲(chǔ)數(shù)據(jù)。閃存硬盤(pán)中通常使用的是NAND型芯片。

　　閃存具備讀、寫(xiě)和擦除三種操作，頁(yè)是閃存讀寫(xiě)操作的基本單位，而擦除操作則是以塊為單位的。閃存與磁盤(pán)不同，具有異位更新的特點(diǎn)，即不能直接在某個(gè)有數(shù)據(jù)的數(shù)據(jù)頁(yè)上進(jìn)行寫(xiě)操作，必須先擦除才能寫(xiě)，即便是只更新數(shù)據(jù)塊中的一個(gè)數(shù)據(jù)頁(yè)也需要將整塊數(shù)據(jù)擦除。這樣頻繁的擦除操作可能會(huì)使閃存的性能變得不穩(wěn)定，故通常更新不會(huì)直接在原位上進(jìn)行，而是將寫(xiě)和擦除操作均勻地分布在所有的數(shù)據(jù)塊上。此外，閃存和磁盤(pán)在讀寫(xiě)上的差異也很大，兩者在I/O操作性能上的對(duì)比[3]如表1所示，閃存寫(xiě)的速度總是比讀的速度慢，在研究閃存數(shù)據(jù)庫(kù)緩沖區(qū)置換算法時(shí)，必須對(duì)讀寫(xiě)操作進(jìn)行區(qū)分，以便達(dá)到更好的性能。

　　1.2 緩沖區(qū)管理算法

　　當(dāng)系統(tǒng)發(fā)出讀寫(xiě)數(shù)據(jù)頁(yè)的請(qǐng)求時(shí)，緩沖區(qū)管理需要做如下處理：

　?。?）檢查頁(yè)表，判斷請(qǐng)求頁(yè)是否在緩沖區(qū)，若請(qǐng)求頁(yè)在緩沖區(qū)則訪問(wèn)命中，直接讀取所需數(shù)據(jù)并執(zhí)行對(duì)該頁(yè)的操作，否則訪問(wèn)脫靶（缺頁(yè)），執(zhí)行步驟（2）；

　?。?）檢查緩沖區(qū)是否已滿，若還存在可用空間則為請(qǐng)求頁(yè)分配空間，讀入請(qǐng)求頁(yè)執(zhí)行相關(guān)操作，否則執(zhí)行步驟（3）；

　?。?）按照某種置換策略選擇一頁(yè)作為置換頁(yè)，若該頁(yè)是只讀頁(yè)則直接置換出內(nèi)存，否則先將置換頁(yè)的內(nèi)容寫(xiě)回外存再讀入請(qǐng)求頁(yè)。

2 閃存的緩沖區(qū)置換算法

　　經(jīng)典的磁盤(pán)緩沖區(qū)替換算法主要是根據(jù)數(shù)據(jù)訪問(wèn)的頻度和最近性為設(shè)計(jì)原則，以追求高的訪問(wèn)命中率為主要目標(biāo)。閃存與傳統(tǒng)的磁盤(pán)不同，閃存的讀寫(xiě)代價(jià)是不對(duì)稱的，其隨機(jī)寫(xiě)的代價(jià)遠(yuǎn)遠(yuǎn)高于其連續(xù)寫(xiě)的代價(jià)，傳統(tǒng)的磁盤(pán)存儲(chǔ)緩沖區(qū)置換算法通常假設(shè)存儲(chǔ)設(shè)備具有相同的讀寫(xiě)延遲，這些特性決定了閃存的緩沖區(qū)置換算法必須對(duì)讀寫(xiě)操作進(jìn)行區(qū)分，在保證命中率的同時(shí)盡量減少寫(xiě)操作，更好地提升閃存的整體性能。目前，關(guān)于閃存的緩沖區(qū)管理策略，有不少學(xué)者對(duì)其做了相關(guān)的研究，也取得了一些成果，現(xiàn)有的閃存數(shù)據(jù)庫(kù)緩沖區(qū)替換策略主要分為基于頁(yè)級(jí)和基于塊級(jí)兩類(lèi)。

　　2.1 基于頁(yè)級(jí)的閃存緩沖區(qū)替換算法

　　2.1.1 CFLRU

　　CFLRU[4]是PARK S Y等人最先提出的一種面向閃存緩沖區(qū)的置換算法。該算法在LRU的基礎(chǔ)上充分考慮閃存讀寫(xiě)延遲的非對(duì)稱性，優(yōu)先替換出緩沖區(qū)的干凈頁(yè)，減少閃存寫(xiě)操作和擦除操作的次數(shù)，從而提高閃存的訪問(wèn)性能，獲得整體性能的提升。

　　CFLRU算法的基本思想是：把LRU鏈表分為工作區(qū)和替換區(qū)，工作區(qū)負(fù)責(zé)維護(hù)最近訪問(wèn)的數(shù)據(jù)頁(yè)，替換區(qū)則負(fù)責(zé)維護(hù)替換候選隊(duì)列，替換時(shí)總是優(yōu)先替換替換區(qū)中的干凈頁(yè)，若替換區(qū)沒(méi)有干凈頁(yè)，則選擇LRU鏈表尾部的第一個(gè)臟頁(yè)作為置換頁(yè)。在CF-LRU算法中替換區(qū)的大小是由窗口大小決定的。圖1是CFLRU的一個(gè)例子。假設(shè)緩沖區(qū)最多只能同時(shí)容納6個(gè)頁(yè)，大小為3。在某個(gè)時(shí)刻，一個(gè)訪問(wèn)請(qǐng)求p7到達(dá)，替換區(qū)中有干凈頁(yè)P(yáng)5則優(yōu)先替換出干凈頁(yè)，而不是替換LRU鏈表尾部的P6。

　　通過(guò)以上可以看出，CFLRU通過(guò)優(yōu)先替換出替換區(qū)的干凈頁(yè)，在一定程度上可以有效地減少對(duì)閃存的寫(xiě)和擦除操作，提升了性能。但還存在一些不足：（1）很難確定一個(gè)合適窗口大小的值來(lái)適應(yīng)不同的任務(wù)。大小直接影響了置換算法的效率，過(guò)大缺頁(yè)率則會(huì)增加，過(guò)小替換代價(jià)也會(huì)相應(yīng)地增加。（2）當(dāng)鏈表較長(zhǎng)時(shí)，查找干凈頁(yè)作為置換頁(yè)的代價(jià)會(huì)較高。由于算法在選擇置換頁(yè)時(shí)需要沿著鏈表反向查找干凈頁(yè)，當(dāng)鏈表較長(zhǎng)時(shí)查找代價(jià)會(huì)增加。（3）該算法沒(méi)有考慮數(shù)據(jù)頁(yè)的訪問(wèn)頻率，訪問(wèn)頻率作為數(shù)據(jù)頁(yè)的一個(gè)重要特征，若不考慮訪問(wèn)頻率過(guò)早地替換出頻率高的干凈頁(yè)和過(guò)晚替換出頻率低的數(shù)據(jù)頁(yè)都會(huì)增加訪問(wèn)的開(kāi)銷(xiāo)，降低替換的效率。

　　2.1.2 LRU-WSR

　　LRU-WSR[5]是一種對(duì)CFLRU改進(jìn)的面向閃存緩沖區(qū)的置換算法。該算法不僅考慮了臟頁(yè)的頻度，而且對(duì)臟頁(yè)的冷熱進(jìn)行區(qū)分，優(yōu)先替換出干凈頁(yè)和冷的臟頁(yè)，能夠有效避免冷臟頁(yè)長(zhǎng)期駐留內(nèi)存，減少寫(xiě)操作，提高訪問(wèn)效率。

　　LRU-WSR算法的基本思想是：為緩沖區(qū)數(shù)據(jù)頁(yè)設(shè)置一個(gè)冷熱標(biāo)識(shí)位，標(biāo)識(shí)位為1則表示該頁(yè)為冷頁(yè)，為0則表示該頁(yè)為非冷頁(yè)。算法在選擇置換頁(yè)時(shí)，首先檢查該頁(yè)是否是干凈頁(yè)或冷臟頁(yè)，是則直接替換。若該頁(yè)是非冷臟頁(yè)，則將標(biāo)識(shí)位置為1并把該頁(yè)移到MRU端，再對(duì)鏈表LRU端數(shù)據(jù)頁(yè)進(jìn)行判斷。當(dāng)訪問(wèn)臟頁(yè)時(shí)，則把標(biāo)識(shí)位改為0。圖2是一個(gè)LRU-WSR緩沖區(qū)置換策略示例，假設(shè)緩沖區(qū)最多只能同時(shí)容納6個(gè)頁(yè)，在某個(gè)時(shí)刻，一個(gè)順序訪問(wèn)請(qǐng)求p7、p1到達(dá)，則會(huì)替換出干凈頁(yè)P(yáng)1和冷臟頁(yè)P(yáng)2。

　　LRU-WSR算法運(yùn)用標(biāo)識(shí)冷標(biāo)識(shí)位的方法，區(qū)分臟頁(yè)的冷熱程度，在保證命中率的同時(shí)減少了寫(xiě)和擦除操作的次數(shù)，實(shí)驗(yàn)表明該算法較LRU、CFLRU等算法有較大的提升。雖然LRU-WSR有不錯(cuò)的性能，但仍存在一些不足，該算法只考慮了臟頁(yè)的冷熱屬性并沒(méi)有關(guān)注到干凈頁(yè)的冷熱屬性，干凈頁(yè)優(yōu)先被替換出去，可能會(huì)導(dǎo)致熱的干凈頁(yè)很快被置換出去而增加額外開(kāi)銷(xiāo)。在圖2的例子中若考慮到P1是熱的干凈頁(yè)，則優(yōu)先置換出冷臟頁(yè)P(yáng)2而不是熱干凈頁(yè)P(yáng)1，當(dāng)訪問(wèn)請(qǐng)求p1到達(dá)時(shí)則會(huì)直接命中，這樣就減少了操作次數(shù)。

　　2.1.3 AD-LRU

　　AD-LRU[6]是一種自適應(yīng)的面向閃存緩沖區(qū)的置換算法。算法根據(jù)最近性和頻度將緩沖區(qū)分為冷區(qū)和熱區(qū)兩個(gè)隊(duì)列，冷區(qū)存放只訪問(wèn)過(guò)一次的數(shù)據(jù)頁(yè)，而熱區(qū)則存放至少被訪問(wèn)過(guò)兩次的數(shù)據(jù)頁(yè)。冷熱區(qū)的大小是根據(jù)被引用頻度動(dòng)態(tài)調(diào)整的。當(dāng)需要置換時(shí)并不是一味地選擇冷區(qū)的數(shù)據(jù)頁(yè)，而是根據(jù)一個(gè)下界值min_lc來(lái)選擇的，當(dāng)冷區(qū)容量大于或等于min_lc時(shí)則選擇冷區(qū)進(jìn)行替換，相反則選擇熱區(qū)。

　　算法在選擇置換頁(yè)時(shí)，首先從冷區(qū)的LRU端開(kāi)始查找干凈頁(yè)，若存在則直接替換，若不存在則判斷冷區(qū)容量是否大于或等于min_lc，若大于等于則選擇冷區(qū)的頁(yè)面進(jìn)行替換，若冷區(qū)容量小于min_lc則選擇熱區(qū)臟頁(yè)。該算法綜合考慮了最近性、引用頻度等特性，既可以減少寫(xiě)的代價(jià)，而且還保持了高的命中率。但這種方法還是無(wú)法避免干凈頁(yè)剛讀入緩沖區(qū)就被替換的情況。

　　2.2 基于塊級(jí)的閃存緩沖區(qū)替換算法

　　考慮到頁(yè)級(jí)的置換策略可能會(huì)產(chǎn)生大量的存儲(chǔ)碎片而引發(fā)頻繁的寫(xiě)操作影響閃存的效率，學(xué)者們研究把緩沖區(qū)中相近的數(shù)據(jù)頁(yè)以聚簇的方式分組成塊，以塊為單位將數(shù)據(jù)批量地置換出內(nèi)存，以減少隨機(jī)寫(xiě)的次數(shù)。

　　2.2.1 FAB

　　FAB[7]是JO H等人提出的一種針對(duì)裝有閃存芯片的多媒體播放器、移動(dòng)電話等具有典型順序訪問(wèn)比較密集特性而設(shè)計(jì)的基于塊級(jí)的閃存緩沖區(qū)替換算法。該算法將緩沖區(qū)中的數(shù)據(jù)以數(shù)據(jù)塊的形式組織起來(lái)形成一個(gè)LRU鏈表（如圖3所示）每個(gè)塊包含了同屬于這個(gè)塊的數(shù)據(jù)頁(yè)，當(dāng)需要讀取、更新或插入新的數(shù)據(jù)頁(yè)時(shí)，則將該數(shù)據(jù)塊放到鏈表的頭部；當(dāng)需要置換時(shí)優(yōu)先選擇數(shù)據(jù)頁(yè)最多的塊進(jìn)行替換，若存在多個(gè)候選塊則選擇最近最少訪問(wèn)的塊（即鏈表尾部的塊）。

　　算法對(duì)屬于同一塊的數(shù)據(jù)頁(yè)進(jìn)行聚簇，并以優(yōu)先替換出數(shù)據(jù)頁(yè)最多的數(shù)據(jù)塊的方式來(lái)降低閃存的寫(xiě)和擦除操作次數(shù)，在某種程度上提高了閃存的整體性能。但該算法還存在一些不足，如當(dāng)請(qǐng)求為順序時(shí)，算法性能會(huì)較好，但當(dāng)請(qǐng)求為隨機(jī)時(shí)，算法的性能非常差，因此該算法只適用于順序訪問(wèn)。此外，F(xiàn)AB在選擇替換塊時(shí)沒(méi)有考慮時(shí)間局部性而是選擇數(shù)據(jù)頁(yè)最多的塊進(jìn)行替換，若緩沖區(qū)中有較多訪問(wèn)頻率較高但數(shù)據(jù)頁(yè)較少的塊時(shí)，算法的命中率就會(huì)有一定程度上的降低，影響整個(gè)I/O性能。

　　2.2.2 CLC

　　CLC[8]算法與FAB算法一樣，將所屬同一塊的數(shù)據(jù)頁(yè)聚集起來(lái)形成一個(gè)數(shù)據(jù)塊，并按一定的策略形成鏈表。與FAB不同的是，CLC同時(shí)考慮了替換塊的大小和訪問(wèn)頻率，優(yōu)先替換出訪問(wèn)頻率低且數(shù)據(jù)頁(yè)最多的數(shù)據(jù)塊。這種策略在保證命中率的同時(shí)減少了隨機(jī)寫(xiě)的次數(shù)，提高了閃存訪問(wèn)的性能。

　　算法把緩沖區(qū)分成Size-Dependent LRU（SDLRU）和Size-Independent LRU（SILRU）兩個(gè)鏈表，SDLRU存放訪問(wèn)頻率較低的數(shù)據(jù)塊，SILRU存放訪問(wèn)頻率較高的數(shù)據(jù)塊。當(dāng)有新的數(shù)據(jù)塊或某一數(shù)據(jù)塊被訪問(wèn)時(shí)則將該數(shù)據(jù)塊插入到SILRU的頭部；當(dāng)SILRU已滿且有新的數(shù)據(jù)塊時(shí)則需將SILRU鏈表中尾部的數(shù)據(jù)塊轉(zhuǎn)移到SDLRU中，然后把數(shù)據(jù)塊插入SILRU的頭部。通過(guò)這種方式可以把訪問(wèn)頻率高的數(shù)據(jù)存放在SILRU，訪問(wèn)頻率低的則存放在SDLRU中。當(dāng)SDLRU空間不足時(shí)，則優(yōu)先替換出頻率低且數(shù)據(jù)頁(yè)最多的數(shù)據(jù)塊。然而由于數(shù)據(jù)塊中數(shù)據(jù)頁(yè)的訪問(wèn)特性不同，有時(shí)若一個(gè)數(shù)據(jù)塊中只有少數(shù)數(shù)據(jù)頁(yè)經(jīng)常被訪問(wèn)，其他多數(shù)的數(shù)據(jù)頁(yè)雖然很少被訪問(wèn)也需要駐留在緩沖區(qū)，極易造成空間的浪費(fèi)。

3 結(jié)論

　　隨著軟硬件技術(shù)的發(fā)展，閃存存儲(chǔ)這種新型存儲(chǔ)設(shè)備的出現(xiàn)給數(shù)據(jù)管理性能的提升帶來(lái)了機(jī)遇和挑戰(zhàn)。應(yīng)用這種存儲(chǔ)解決海量數(shù)據(jù)管理是數(shù)據(jù)庫(kù)技術(shù)未來(lái)發(fā)展的主要方向。緩沖區(qū)管理是閃存技術(shù)的關(guān)鍵問(wèn)題，是閃存數(shù)據(jù)庫(kù)領(lǐng)域的一個(gè)研究熱點(diǎn)。目前基于緩沖區(qū)的管理策略主要有基于頁(yè)級(jí)和基于塊級(jí)兩類(lèi)，兩類(lèi)置換策略都是在保證緩沖區(qū)命中率的同時(shí)，盡量減少寫(xiě)和擦除操作的次數(shù)，進(jìn)而提高閃存的訪問(wèn)性能，但兩種策略都還存在一些不足，性能還有很大的提升空間。未來(lái)還可以從數(shù)據(jù)的訪問(wèn)特性以及硬件特性出發(fā)研究更高效的緩沖區(qū)置換策略，更好地提升閃存的訪問(wèn)性能。

　　參考文獻(xiàn)

　　[1] CHANG L P， KUO T W． Efficient management for large-scale flash memory storage with resource conservation[J]． IEEE Transactions on Storage， 2005，1（4）：381-418.

　　[2] 王江濤，賴文豫，孟小峰.閃存數(shù)據(jù)庫(kù)：現(xiàn)狀、技術(shù)與展望[J].計(jì)算機(jī)學(xué)報(bào)，2013，36（8）：1549-1567.

　　[3] LEE S W， MOON B． Design of Flash-based DBMS：An in page logging approach[A]. Beijing： Proceedings of the ACMSIGMOD International Conference[C]． 2007：55-66.

　　[4] PARK S Y， JUNG D， KANG J， et al． CFLRU： A replacement algorithm for flash-memory[C]. Proceedings of the International Conference on Compilers， Architecture and Synthesis for Embedded Systems， Seoul， 2006：234-241.

　　[5] JUNG H， SHIM H， PARK S， et al． LRU-WSR： integration of LRU and writes sequence reordering for Flash memory[J]． IEEE Transactions on Consumer Electronics， 2008，54（3）：1215-1223.

　　[6] Jin Peiquan， Qu Yi， HARDER T， et al． AD-LRU： An efficient buffer replacement algorithm for Flash-based databases[J]. Journal of Data & Knowledge Engineering， 2012，72（2）：83-102.

　　[7] JO H， KANG Ju， PARK S Y， et al. FAB： Flash-aware buffer management policy for portable media players[J]. IEEE Transactions on Consumer Electronics，2006，52（2）：485-493.

　　[8] KANG S， PARK S， JUNG H， et al． Performance trade-offs in using NVRAM write buffer for Flash memory-based storage devices[J]． IEEE Transactions on Computers， 2009，58（6）：744-758．