閃存數據庫緩沖區置換算法綜述

鄭　開（西南大學 應用技術學院，重慶 401147）

閃存數據庫緩沖區置換算法綜述

鄭開
（西南大學 應用技術學院，重慶 401147）

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

閃存；閃存數據庫；緩沖區置換算法

0　引言

近年來，閃存存儲作為新一代的存儲介質，憑借其存寫速度快、功耗低、體積小、抗震等優良特性，已經被廣泛應用在嵌入式系統、航空航天以及各種企業級的數據存儲系統中［1］。

由于閃存和磁盤在物理結構、數據存取方式等方面存在明顯的差異，而現有的數據庫系統中的各類數據結構和算法都是針對磁盤專門開發的，因此目前已有的基于磁盤的應用（如文件系統等）無法直接支持閃存而充分發揮閃存存儲的優越性［2］。因此，針對閃存存儲的數據結構和算法（如數據存儲、索引、緩沖區管理等）都很有研究的必要。其中緩沖區作為閃存數據庫的系統的核心組件，其替換算法更是一個比較熱門的研究問題，受到深度的重視。

1　閃存及緩沖區管理算法

1.1閃存存儲

閃存存儲器一般可以分為NOR型和NAND型兩種，其中NOR型閃存以字節為存取單位，按位進行訪問，讀速快，但擦除和寫速較慢，主要用于存儲程序和少量數據。NAND型閃存以數據頁為存儲單位，容量較大，價格低，主要用于存儲數據。閃存硬盤中通常使用的是NAND型芯片。

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

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

1.2緩沖區管理算法

當系統發出讀寫數據頁的請求時，緩沖區管理需要做如下處理：

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

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

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

2　閃存的緩沖區置換算法

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

2.1基于頁級的閃存緩沖區替換算法

2.1.1CFLRU

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

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

圖1　CFLRU緩沖區置換策略示例

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

2.1.2LRU-WSR

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

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

圖2　LRU-WSR緩沖區置換策略示例

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

2.1.3AD-LRU

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

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

2.2基于塊級的閃存緩沖區替換算法

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

2.2.1FAB

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

圖3　FAB緩沖區鏈表結構圖

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

2.2.2CLC

CLC［8］算法與 FAB算法一樣，將所屬同一塊的數據頁聚集起來形成一個數據塊，并按一定的策略形成鏈表。與FAB不同的是，CLC同時考慮了替換塊的大小和訪問頻率，優先替換出訪問頻率低且數據頁最多的數據塊。這種策略在保證命中率的同時減少了隨機寫的次數，提高了閃存訪問的性能。

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

3　結論

隨著軟硬件技術的發展，閃存存儲這種新型存儲設備的出現給數據管理性能的提升帶來了機遇和挑戰。應用這種存儲解決海量數據管理是數據庫技術未來發展的主要方向。緩沖區管理是閃存技術的關鍵問題，是閃存數據庫領域的一個研究熱點。目前基于緩沖區的管理策略主要有基于頁級和基于塊級兩類，兩類置換策略都是在保證緩沖區命中率的同時，盡量減少寫和擦除操作的次數，進而提高閃存的訪問性能，但兩種策略都還存在一些不足，性能還有很大的提升空間。未來還可以從數據的訪問特性以及硬件特性出發研究更高效的緩沖區置換策略，更好地提升閃存的訪問性能。

［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］王江濤，賴文豫，孟小峰.閃存數據庫：現狀、技術與展望［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 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-），女，碩士，助理實驗師，主要研究方向：數據庫與智能檢索技術。