鄭　開（西南大學(xué) 應(yīng)用技術(shù)學(xué)院，重慶 401147）

閃存數(shù)據(jù)庫緩沖區(qū)置換算法綜述

鄭開
（西南大學(xué) 應(yīng)用技術(shù)學(xué)院，重慶 401147）

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

閃存；閃存數(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é)為存取單位，按位進(jìn)行訪問，讀速快，但擦除和寫速較慢，主要用于存儲程序和少量數(shù)據(jù)。NAND型閃存以數(shù)據(jù)頁為存儲單位，容量較大，價格低，主要用于存儲數(shù)據(jù)。閃存硬盤中通常使用的是NAND型芯片。

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

表1　閃存與磁盤I/O性能對比

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

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

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

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

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

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

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

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

2.1.1CFLRU

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

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

圖1　CFLRU緩沖區(qū)置換策略示例

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

2.1.2LRU-WSR

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

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

圖2　LRU-WSR緩沖區(qū)置換策略示例

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

2.1.3AD-LRU

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

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

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

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

2.2.1FAB

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

圖3　FAB緩沖區(qū)鏈表結(jié)構(gòu)圖

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

2.2.2CLC

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ù)塊。當(dāng)有新的數(shù)據(jù)塊或某一數(shù)據(jù)塊被訪問時則將該數(shù)據(jù)塊插入到SILRU的頭部；當(dāng)SILRU已滿且有新的數(shù)據(jù)塊時則需將 SILRU鏈表中尾部的數(shù)據(jù)塊轉(zhuǎn)移到 SDLRU中，然后把數(shù)據(jù)塊插入SILRU的頭部。通過這種方式可以把訪問頻率高的數(shù)據(jù)存放在 SILRU，訪問頻率低的則存放在SDLRU中。當(dāng)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ù)，進(jìn)而提高閃存的訪問性能，但兩種策略都還存在一些不足，性能還有很大的提升空間。未來還可以從數(shù)據(jù)的訪問特性以及硬件特性出發(fā)研究更高效的緩沖區(qū)置換策略，更好地提升閃存的訪問性能。

［1］CHANG L P，KUO T W.Efficient management for largescale flashmemorystorage withresource conservation［J］.IEEE Transactions on Storage，2005，1（4）：381-418.

［2］王江濤，賴文豫，孟小峰.閃存數(shù)據(jù)庫：現(xiàn)狀、技術(shù)與展望［J］.計算機學(xué)報，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 efficientbuffer replacementalgorithm 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 policyfor portablemediaplayers［J］.IEEETransactions onConsumer 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.

Buffer replacement algorithm for Flash-based database

Zheng Kai
（College of Applied Technology，Southwest University，Chongqing 401147，China）

With the development of Flash memory，the Flash memory is widely used，which takes opportunity and challenge to the management of Flash-based database.As the Flash memory is different from the magnetic disk in the way of read and write，as well as the performance of read and write，it is urgent to provide efficient buffer management for Flash memory.In order to improve the Flash memory access performance，buffer replacement algorithm should reduce the number of write/erase operations and retain a highbuffer hit ratio.This paper analyzes the mainalgorithmof buffer replacement for Flash-baseddatabase，compares the advantages and disadvantages of the algorithm，and gives future research directions.

Flash memory；Flash-based database；buffer replacement algorithm

TP392

A

1674-7720（2015）06-0007-03

2014-10-31）

鄭開（1988-），女，碩士，助理實驗師，主要研究方向：數(shù)據(jù)庫與智能檢索技術(shù)。