摘 要： 隨著閃存技術(shù)的發(fā)展和閃存容量的不斷增大，閃存存儲被廣泛應(yīng)用，給閃存數(shù)據(jù)庫管理帶來機遇和挑戰(zhàn)。因為閃存和磁盤讀寫方式不同，讀寫性能也有差別，所以對于閃存緩沖區(qū)的管理成為一個亟待解決的問題。為了提高閃存的訪問性能，緩沖區(qū)置換算法在保證命中率的同時要盡量減少寫和擦除操作的次數(shù)。對主流的閃存數(shù)據(jù)庫緩沖區(qū)置換算法進行分析，比較了幾種算法的優(yōu)點和不足，并給出了未來研究的方向。
關(guān)鍵詞： 閃存；閃存數(shù)據(jù)庫；緩沖區(qū)置換算法
0 引言
近年來，閃存存儲作為新一代的存儲介質(zhì)，憑借其存寫速度快、功耗低、體積小、抗震等優(yōu)良特性，已經(jīng)被廣泛應(yīng)用在嵌入式系統(tǒng)、航空航天以及各種企業(yè)級的數(shù)據(jù)存儲系統(tǒng)中[1]。
由于閃存和磁盤在物理結(jié)構(gòu)、數(shù)據(jù)存取方式等方面存在明顯的差異，而現(xiàn)有的數(shù)據(jù)庫系統(tǒng)中的各類數(shù)據(jù)結(jié)構(gòu)和算法都是針對磁盤專門開發(fā)的，因此目前已有的基于磁盤的應(yīng)用（如文件系統(tǒng)等）無法直接支持閃存而充分發(fā)揮閃存存儲的優(yōu)越性[2]。因此，針對閃存存儲的數(shù)據(jù)結(jié)構(gòu)和算法（如數(shù)據(jù)存儲、索引、緩沖區(qū)管理等）都很有研究的必要。其中緩沖區(qū)作為閃存數(shù)據(jù)庫的系統(tǒng)的核心組件，其替換算法更是一個比較熱門的研究問題，受到深度的重視。
1 閃存及緩沖區(qū)管理算法
1.1 閃存存儲
閃存存儲器一般可以分為NOR型和NAND型兩種，其中NOR型閃存以字節(jié)為存取單位，按位進行訪問，讀速快，但擦除和寫速較慢，主要用于存儲程序和少量數(shù)據(jù)。NAND型閃存以數(shù)據(jù)頁為存儲單位，容量較大，價格低，主要用于存儲數(shù)據(jù)。閃存硬盤中通常使用的是NAND型芯片。
閃存具備讀、寫和擦除三種操作，頁是閃存讀寫操作的基本單位，而擦除操作則是以塊為單位的。閃存與磁盤不同，具有異位更新的特點，即不能直接在某個有數(shù)據(jù)的數(shù)據(jù)頁上進行寫操作，必須先擦除才能寫，即便是只更新數(shù)據(jù)塊中的一個數(shù)據(jù)頁也需要將整塊數(shù)據(jù)擦除。這樣頻繁的擦除操作可能會使閃存的性能變得不穩(wěn)定，故通常更新不會直接在原位上進行，而是將寫和擦除操作均勻地分布在所有的數(shù)據(jù)塊上。此外，閃存和磁盤在讀寫上的差異也很大，兩者在I/O操作性能上的對比[3]如表1所示，閃存寫的速度總是比讀的速度慢，在研究閃存數(shù)據(jù)庫緩沖區(qū)置換算法時，必須對讀寫操作進行區(qū)分，以便達到更好的性能。
1.2 緩沖區(qū)管理算法
當系統(tǒng)發(fā)出讀寫數(shù)據(jù)頁的請求時，緩沖區(qū)管理需要做如下處理：
（1）檢查頁表，判斷請求頁是否在緩沖區(qū)，若請求頁在緩沖區(qū)則訪問命中，直接讀取所需數(shù)據(jù)并執(zhí)行對該頁的操作，否則訪問脫靶（缺頁），執(zhí)行步驟（2）；
?。?）檢查緩沖區(qū)是否已滿，若還存在可用空間則為請求頁分配空間，讀入請求頁執(zhí)行相關(guān)操作，否則執(zhí)行步驟（3）；
（3）按照某種置換策略選擇一頁作為置換頁，若該頁是只讀頁則直接置換出內(nèi)存，否則先將置換頁的內(nèi)容寫回外存再讀入請求頁。
2 閃存的緩沖區(qū)置換算法
經(jīng)典的磁盤緩沖區(qū)替換算法主要是根據(jù)數(shù)據(jù)訪問的頻度和最近性為設(shè)計原則，以追求高的訪問命中率為主要目標。閃存與傳統(tǒng)的磁盤不同，閃存的讀寫代價是不對稱的，其隨機寫的代價遠遠高于其連續(xù)寫的代價，傳統(tǒng)的磁盤存儲緩沖區(qū)置換算法通常假設(shè)存儲設(shè)備具有相同的讀寫延遲，這些特性決定了閃存的緩沖區(qū)置換算法必須對讀寫操作進行區(qū)分，在保證命中率的同時盡量減少寫操作，更好地提升閃存的整體性能。目前，關(guān)于閃存的緩沖區(qū)管理策略，有不少學者對其做了相關(guān)的研究，也取得了一些成果，現(xiàn)有的閃存數(shù)據(jù)庫緩沖區(qū)替換策略主要分為基于頁級和基于塊級兩類。
2.1 基于頁級的閃存緩沖區(qū)替換算法
2.1.1 CFLRU
CFLRU[4]是PARK S Y等人最先提出的一種面向閃存緩沖區(qū)的置換算法。該算法在LRU的基礎(chǔ)上充分考慮閃存讀寫延遲的非對稱性，優(yōu)先替換出緩沖區(qū)的干凈頁，減少閃存寫操作和擦除操作的次數(shù)，從而提高閃存的訪問性能，獲得整體性能的提升。
CFLRU算法的基本思想是：把LRU鏈表分為工作區(qū)和替換區(qū)，工作區(qū)負責維護最近訪問的數(shù)據(jù)頁，替換區(qū)則負責維護替換候選隊列，替換時總是優(yōu)先替換替換區(qū)中的干凈頁，若替換區(qū)沒有干凈頁，則選擇LRU鏈表尾部的第一個臟頁作為置換頁。在CF-LRU算法中替換區(qū)的大小是由窗口大小決定的。圖1是CFLRU的一個例子。假設(shè)緩沖區(qū)最多只能同時容納6個頁，大小為3。在某個時刻，一個訪問請求p7到達，替換區(qū)中有干凈頁P5則優(yōu)先替換出干凈頁，而不是替換LRU鏈表尾部的P6。
通過以上可以看出，CFLRU通過優(yōu)先替換出替換區(qū)的干凈頁，在一定程度上可以有效地減少對閃存的寫和擦除操作，提升了性能。但還存在一些不足：（1）很難確定一個合適窗口大小的值來適應(yīng)不同的任務(wù)。大小直接影響了置換算法的效率，過大缺頁率則會增加，過小替換代價也會相應(yīng)地增加。（2）當鏈表較長時，查找干凈頁作為置換頁的代價會較高。由于算法在選擇置換頁時需要沿著鏈表反向查找干凈頁，當鏈表較長時查找代價會增加。（3）該算法沒有考慮數(shù)據(jù)頁的訪問頻率，訪問頻率作為數(shù)據(jù)頁的一個重要特征，若不考慮訪問頻率過早地替換出頻率高的干凈頁和過晚替換出頻率低的數(shù)據(jù)頁都會增加訪問的開銷，降低替換的效率。
2.1.2 LRU-WSR
LRU-WSR[5]是一種對CFLRU改進的面向閃存緩沖區(qū)的置換算法。該算法不僅考慮了臟頁的頻度，而且對臟頁的冷熱進行區(qū)分，優(yōu)先替換出干凈頁和冷的臟頁，能夠有效避免冷臟頁長期駐留內(nèi)存，減少寫操作，提高訪問效率。
LRU-WSR算法的基本思想是：為緩沖區(qū)數(shù)據(jù)頁設(shè)置一個冷熱標識位，標識位為1則表示該頁為冷頁，為0則表示該頁為非冷頁。算法在選擇置換頁時，首先檢查該頁是否是干凈頁或冷臟頁，是則直接替換。若該頁是非冷臟頁，則將標識位置為1并把該頁移到MRU端，再對鏈表LRU端數(shù)據(jù)頁進行判斷。當訪問臟頁時，則把標識位改為0。圖2是一個LRU-WSR緩沖區(qū)置換策略示例，假設(shè)緩沖區(qū)最多只能同時容納6個頁，在某個時刻，一個順序訪問請求p7、p1到達，則會替換出干凈頁P1和冷臟頁P2。
LRU-WSR算法運用標識冷標識位的方法，區(qū)分臟頁的冷熱程度，在保證命中率的同時減少了寫和擦除操作的次數(shù)，實驗表明該算法較LRU、CFLRU等算法有較大的提升。雖然LRU-WSR有不錯的性能，但仍存在一些不足，該算法只考慮了臟頁的冷熱屬性并沒有關(guān)注到干凈頁的冷熱屬性，干凈頁優(yōu)先被替換出去，可能會導致熱的干凈頁很快被置換出去而增加額外開銷。在圖2的例子中若考慮到P1是熱的干凈頁，則優(yōu)先置換出冷臟頁P2而不是熱干凈頁P1，當訪問請求p1到達時則會直接命中，這樣就減少了操作次數(shù)。
2.1.3 AD-LRU
AD-LRU[6]是一種自適應(yīng)的面向閃存緩沖區(qū)的置換算法。算法根據(jù)最近性和頻度將緩沖區(qū)分為冷區(qū)和熱區(qū)兩個隊列，冷區(qū)存放只訪問過一次的數(shù)據(jù)頁，而熱區(qū)則存放至少被訪問過兩次的數(shù)據(jù)頁。冷熱區(qū)的大小是根據(jù)被引用頻度動態(tài)調(diào)整的。當需要置換時并不是一味地選擇冷區(qū)的數(shù)據(jù)頁，而是根據(jù)一個下界值min_lc來選擇的，當冷區(qū)容量大于或等于min_lc時則選擇冷區(qū)進行替換，相反則選擇熱區(qū)。
算法在選擇置換頁時，首先從冷區(qū)的LRU端開始查找干凈頁，若存在則直接替換，若不存在則判斷冷區(qū)容量是否大于或等于min_lc，若大于等于則選擇冷區(qū)的頁面進行替換，若冷區(qū)容量小于min_lc則選擇熱區(qū)臟頁。該算法綜合考慮了最近性、引用頻度等特性，既可以減少寫的代價，而且還保持了高的命中率。但這種方法還是無法避免干凈頁剛讀入緩沖區(qū)就被替換的情況。
2.2 基于塊級的閃存緩沖區(qū)替換算法
考慮到頁級的置換策略可能會產(chǎn)生大量的存儲碎片而引發(fā)頻繁的寫操作影響閃存的效率，學者們研究把緩沖區(qū)中相近的數(shù)據(jù)頁以聚簇的方式分組成塊，以塊為單位將數(shù)據(jù)批量地置換出內(nèi)存，以減少隨機寫的次數(shù)。
2.2.1 FAB
FAB[7]是JO H等人提出的一種針對裝有閃存芯片的多媒體播放器、移動電話等具有典型順序訪問比較密集特性而設(shè)計的基于塊級的閃存緩沖區(qū)替換算法。該算法將緩沖區(qū)中的數(shù)據(jù)以數(shù)據(jù)塊的形式組織起來形成一個LRU鏈表（如圖3所示）每個塊包含了同屬于這個塊的數(shù)據(jù)頁，當需要讀取、更新或插入新的數(shù)據(jù)頁時，則將該數(shù)據(jù)塊放到鏈表的頭部；當需要置換時優(yōu)先選擇數(shù)據(jù)頁最多的塊進行替換，若存在多個候選塊則選擇最近最少訪問的塊（即鏈表尾部的塊）。
算法對屬于同一塊的數(shù)據(jù)頁進行聚簇，并以優(yōu)先替換出數(shù)據(jù)頁最多的數(shù)據(jù)塊的方式來降低閃存的寫和擦除操作次數(shù)，在某種程度上提高了閃存的整體性能。但該算法還存在一些不足，如當請求為順序時，算法性能會較好，但當請求為隨機時，算法的性能非常差，因此該算法只適用于順序訪問。此外，F(xiàn)AB在選擇替換塊時沒有考慮時間局部性而是選擇數(shù)據(jù)頁最多的塊進行替換，若緩沖區(qū)中有較多訪問頻率較高但數(shù)據(jù)頁較少的塊時，算法的命中率就會有一定程度上的降低，影響整個I/O性能。
2.2.2 CLC
CLC[8]算法與FAB算法一樣，將所屬同一塊的數(shù)據(jù)頁聚集起來形成一個數(shù)據(jù)塊，并按一定的策略形成鏈表。與FAB不同的是，CLC同時考慮了替換塊的大小和訪問頻率，優(yōu)先替換出訪問頻率低且數(shù)據(jù)頁最多的數(shù)據(jù)塊。這種策略在保證命中率的同時減少了隨機寫的次數(shù)，提高了閃存訪問的性能。
算法把緩沖區(qū)分成Size-Dependent LRU（SDLRU）和Size-Independent LRU（SILRU）兩個鏈表，SDLRU存放訪問頻率較低的數(shù)據(jù)塊，SILRU存放訪問頻率較高的數(shù)據(jù)塊。當有新的數(shù)據(jù)塊或某一數(shù)據(jù)塊被訪問時則將該數(shù)據(jù)塊插入到SILRU的頭部；當SILRU已滿且有新的數(shù)據(jù)塊時則需將SILRU鏈表中尾部的數(shù)據(jù)塊轉(zhuǎn)移到SDLRU中，然后把數(shù)據(jù)塊插入SILRU的頭部。通過這種方式可以把訪問頻率高的數(shù)據(jù)存放在SILRU，訪問頻率低的則存放在SDLRU中。當SDLRU空間不足時，則優(yōu)先替換出頻率低且數(shù)據(jù)頁最多的數(shù)據(jù)塊。然而由于數(shù)據(jù)塊中數(shù)據(jù)頁的訪問特性不同，有時若一個數(shù)據(jù)塊中只有少數(shù)數(shù)據(jù)頁經(jīng)常被訪問，其他多數(shù)的數(shù)據(jù)頁雖然很少被訪問也需要駐留在緩沖區(qū)，極易造成空間的浪費。
3 結(jié)論
隨著軟硬件技術(shù)的發(fā)展，閃存存儲這種新型存儲設(shè)備的出現(xiàn)給數(shù)據(jù)管理性能的提升帶來了機遇和挑戰(zhàn)。應(yīng)用這種存儲解決海量數(shù)據(jù)管理是數(shù)據(jù)庫技術(shù)未來發(fā)展的主要方向。緩沖區(qū)管理是閃存技術(shù)的關(guān)鍵問題，是閃存數(shù)據(jù)庫領(lǐng)域的一個研究熱點。目前基于緩沖區(qū)的管理策略主要有基于頁級和基于塊級兩類，兩類置換策略都是在保證緩沖區(qū)命中率的同時，盡量減少寫和擦除操作的次數(shù)，進而提高閃存的訪問性能，但兩種策略都還存在一些不足，性能還有很大的提升空間。未來還可以從數(shù)據(jù)的訪問特性以及硬件特性出發(fā)研究更高效的緩沖區(qū)置換策略，更好地提升閃存的訪問性能。
參考文獻
[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ù)庫：現(xiàn)狀、技術(shù)與展望[J].計算機學報，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．