王光忠，王翰虎，2，陳 梅，馬 丹

（1.貴州大學 計算機科學與信息學院，貴州 貴陽550025；2.貴州星辰科技開發(fā)有限公司，貴州貴陽550025）

0 引 言

基于閃存和傳統(tǒng)磁盤的混合存儲系統(tǒng)已經(jīng)成為DBMS存儲層的高效存儲模式。它充分利用閃存和磁盤各自的特點，即閃存高速的隨機讀和磁盤快速的順序?qū)懀行岣吡薉BMS存儲層的I/O效率［2，6］。針對混合存儲的研究，國內(nèi)外研究主要集中在混合存儲系統(tǒng)的頁遷移算法和緩存區(qū)管理算法兩方面［1－8］。對于混合存儲的緩沖區(qū)管理，文獻［3］提出了一種動態(tài)的T/C LRU緩沖區(qū)管理算法。該算法根據(jù)閃存和磁盤數(shù)據(jù)頁訪問代價的不對稱性，優(yōu)先置換代價低的數(shù)據(jù)頁，從而提高I/O的存取效率。但算法僅從簡單的頁代價比較進行置換，卻忽視低代價數(shù)據(jù)頁頻繁置換產(chǎn)生的I/O代價。文獻 ［4］提出以閃存作為NVC（nonvolatile cache）金字塔式的多級緩沖區(qū)管理，通過閃存提高I/O的存取效率。但由于對I/O存取過多的集中在閃存上，縮短了閃存的使用壽命，無法均衡閃存和磁盤的I/O流量。

本文提出了一種自適應緩沖區(qū)管理算法DLSB（divded layer self－adaptive buffer management policy）。它根據(jù)數(shù)據(jù)頁讀寫操作的邏輯代價和物理代價對數(shù)據(jù)頁進行自適應的域間選擇和域內(nèi)置換，較好的適應了數(shù)據(jù)頁序列存取模式變化，有效的提高混合存儲系統(tǒng)的I/O存取效率。

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

閃存主要有NOR和NAND兩種。NOR型閃存以字節(jié)作為存取單位，容量小、價格高，適宜存儲程序。NAND閃存以頁作為存取單位，具有更大的容量和更高的寫入速度，因此更適合用于大容量存儲［9，15］。目前的混合存儲系統(tǒng)多針對NAND閃存。

基于NAND類型的閃存由若干閃存塊組成，每塊由固定的閃存頁組成。以頁為單位進行讀寫操作。讀寫速度不對稱，讀的速度比寫的速度快。寫入閃存的數(shù)據(jù)頁不支持原位更新，數(shù)據(jù)頁的刪除操作將導致所在塊的刪除，塊的刪除次數(shù)有限。和磁盤相比，具有許多不同于磁盤的特性，即讀寫代價不對稱、不支持及時更新、以塊為單位擦除（block－erasing）、塊擦除次數(shù)有限。

以閃存作為DBMS的存儲系統(tǒng)中，針對閃存的特點，提出了許多高效的緩沖區(qū)管理算法。比較經(jīng)典的有ACR［10］、BPLRU［11］、CFLRU［12］、CFDC［13］、LRU－WSR［14］等 算 法，其中ACR算法針對閃存讀寫代價的不對稱性，從邏輯和物理兩個層面進行代價的評估，最終確定緩沖區(qū)的置換頁，較好的適應不同數(shù)據(jù)頁讀寫序列的存取模式。

在閃存和磁盤的混合存儲系統(tǒng)中，文獻 ［2］提出一種動態(tài)的緩沖區(qū)管理算法T/C LRU。該算法把緩沖區(qū)從邏輯上劃分為時間區(qū)和代價區(qū)，時間區(qū)里有一個LRU緩沖隊列，最近訪問的數(shù)據(jù)頁或者頻繁訪問的數(shù)據(jù)頁，根據(jù)時間戳在時間區(qū)的LRU中排列；代價區(qū)里有4個LRU緩沖隊列，并按照數(shù)據(jù)頁置換代價升序排列。時間區(qū)和代價區(qū)的大小根據(jù)磁盤的命中率和閃存的缺頁率代價之比進行劃分，即根據(jù)磁盤命中頁的代價大于閃存缺頁產(chǎn)生的代價進行動態(tài)調(diào)整。代價區(qū)中數(shù)據(jù)頁置換按照Lcf＜Lcd＜Ldd＜Ldf順序，對代價區(qū)中的數(shù)據(jù)頁進行置換。

當數(shù)據(jù)頁命中，如果在時間區(qū)LRU中，把數(shù)據(jù)頁插入到MRU位置，重新加上時間戳。如果在代價區(qū)中，從相應的LRU中取出數(shù)據(jù)頁重新插入到時間區(qū)MRU位置，并重新加上時間戳，把時間區(qū)LRU的數(shù)據(jù)頁置換插入到代價區(qū)相應的LRU隊列中。

當數(shù)據(jù)頁未命中，置換時間區(qū)中的數(shù)據(jù)頁到代價區(qū)中相應的LRU中，把數(shù)據(jù)頁插入到時間區(qū)的MUR位置。而代價區(qū)中數(shù)據(jù)頁的置換，按照 Cfread＜Cmread＜Cmwrite＜Cfwirte的順序進行數(shù)據(jù)頁的置換。

T/C LRU根據(jù)閃存的缺頁率和磁盤的命中率比較，動態(tài)調(diào)整時間區(qū)和代價區(qū)的大小，降低了I/O訪問開銷。但忽視了閃存和磁盤干凈數(shù)據(jù)頁的頻繁置換產(chǎn)生的I/O代價。并且隨著存取模式的變化，需要重新調(diào)整時間區(qū)和代價區(qū)的大小，從而嚴重制約了算法的自適應性。

針對T/C LRU算法的缺點，本文提出了一種分層自適應 的 緩 沖 區(qū) 算 法 DLSB（divded layer self－adaptive buffer management policy）。

為了便于描述，對本文所涉及的若干符號給出了定義，見表1。

表1 本文所用符號及其意義說明

2 自適應存儲方法

2.1 算法概述

我們提出的自適應緩沖區(qū)算法DLSB，根據(jù)緩沖區(qū)中數(shù)據(jù)頁邏輯和物理操作代價，自適應地選擇代價最小的數(shù)據(jù)域和數(shù)據(jù)頁進行置換。算法把緩沖區(qū)邏輯劃分為干凈頁域Lc和臟頁域Ld。每個數(shù)據(jù)域中的數(shù)據(jù)頁根據(jù)存儲介質(zhì)類型分為閃存隊列和磁盤隊列。假定緩沖區(qū)可以存放S個數(shù)據(jù)頁，則Lc＝｜Lcf＋Lcd｜＝B表示干凈頁域的數(shù)據(jù)頁，Ld＝｜Ldf＋Ldd｜＝S－B表示臟頁域的數(shù)據(jù)頁。當緩沖區(qū)未滿或數(shù)據(jù)頁命中時，計算域和域內(nèi)隊列的邏輯和物理操作代價，調(diào)整域中閃存隊列和磁盤隊列的理想數(shù)據(jù)頁容量。當數(shù)據(jù)頁不在緩沖區(qū)時，自適應地調(diào)整干凈頁域和臟頁域的代價比，選擇代價最優(yōu)的置換域。在選擇的置換域中，根據(jù)可容納的理想數(shù)據(jù)頁容量與隊列中實際數(shù)據(jù)頁容量進行比較。當閃存隊列實際值大于理想的閃存隊列值時，選擇閃存隊列中的數(shù)據(jù)頁作為置換頁。反之選擇磁盤隊列的數(shù)據(jù)頁進行置換。

2.2 自適應的域間選擇策略

干凈頁域的代價和臟頁域的代價分別為式（1）、（2）

式中：Lcf的代價記——Clcf，代價計算如式（3）

式中：S/N——一個有N頁大小的文件，對該文件中某個數(shù)據(jù)頁的邏輯操作在緩沖區(qū)中命中的概率。1－S/N——一個邏輯操作被轉(zhuǎn)換為物理操作的概率。同理Lcd、Ldf、Ldd的代價——Clcd、Cldf、Cldd，其代價計算分別為

如果緩沖區(qū)滿且當前請求的數(shù)據(jù)頁P不在緩沖區(qū)中，根據(jù)Lc域和Ld域的大小和其過去一段時間內(nèi)數(shù)據(jù)頁置換所付出的代價比例（式（7））進行選擇。若｜Lc｜＝B＜βS，則Ld過大，選擇Ld作為置換域；反之Lc作為置換域

通過對數(shù)據(jù)頁邏輯和物理操作代價的計算，使得對干凈頁域和臟頁域的自適應選擇能很好的適應數(shù)據(jù)頁讀寫序列的模式變化。

2.3 自適應的域內(nèi)數(shù)據(jù)頁置換策略

對于數(shù)據(jù)域中閃存數(shù)據(jù)頁和磁盤數(shù)據(jù)頁的置換，采用了一種自適應的隊列代價優(yōu)化算法。對干凈頁域中的兩個LRU隊列，即Lcf和Lcd，隊列大小為｜Lcf｜＋｜Lcd｜＝B，0≤｜Lcf｜≤B，0≤｜Lcd｜≤B。用參數(shù)δ（0≤δ≤B）表示Lcf可以包含的干凈閃存頁的理想值。當數(shù)據(jù)頁P在Lcf隊列中命中，根據(jù)公式δ＝min（δ＋Cfr＊（｜Lcd｜÷｜Lcf｜），B）增加δ值。Cfr＊（｜Lcd｜÷｜Lcf｜）表示命中Lcf隊列中的閃存隊列后與磁盤隊列的代價比。反之數(shù)據(jù)頁在Lcd命中，δ＝max（δ－Cdr＊（｜Lcf｜÷｜Lcd｜），0）減少δ值。當實際的｜Lcf｜＞δ，則從Lcf中置換頁，相反則從Lcd中置換頁。同理，臟頁域中的頁置換也采用相同的算法。

2.4 DLSB算法描述

如表2所示，1－12行描述了數(shù)據(jù)頁在緩沖區(qū)中命中的情況。1－7行中，數(shù)據(jù)頁P在干凈頁域中命中，操作類型是讀，則根據(jù)數(shù)據(jù)頁類型移動到相應隊列的MRU位置，增加相應的邏輯操作次數(shù)，

表2 DLSB算法

并且調(diào)整干凈頁域中閃存和磁盤的LRU可容納的理想數(shù)據(jù)頁大小δ。8－12行描述臟頁域命中，同干凈頁域一樣調(diào)整相應邏輯操作次數(shù)和可容納的理想數(shù)據(jù)頁大小η。13－16行描述了數(shù)據(jù)頁未命中的情況，如果緩沖區(qū)已滿，調(diào)用過程EvitctPage置換相應數(shù)據(jù)頁，并根據(jù)數(shù)據(jù)頁來自閃存或者是磁盤調(diào)整邏輯操作次數(shù)和物理操作次數(shù)，將相應數(shù)據(jù)頁插入到相應的LRU隊列的MRU位置。

表3 EvitctPage過程

表3中EvitctPage過程描述了對緩沖區(qū)中數(shù)據(jù)頁的置換過程。1－2行根據(jù)干凈頁域和臟頁域邏輯代價和物理代價的計算，自適應調(diào)整參數(shù)β，最終確定置換域。根據(jù)域中的LRU隊列的實際大小和理想?yún)?shù)δ、η比較，確定相應數(shù)據(jù)頁的置換。

3－6行描述臟頁域中的數(shù)據(jù)頁的置換以及相應的物理操作次數(shù)，7－11行描述干凈頁域中數(shù)據(jù)頁的置換。

3 實驗與結(jié)果分析

3.1 實驗環(huán)境

本實驗使用的硬件配置為：Intel Core 2P4Duo CPU 2.83GHz，2GB內(nèi)存，Intel X25－V 40G的SSD硬盤和2個Maxtor Diamond Max 6L300 300G的磁盤 。實驗環(huán)境采用文獻 ［2］混合存儲系統(tǒng)，對LRU、T/C LRU、DLSB算法進行比較。

3.2 實驗結(jié)果分析

實驗結(jié)果如圖1，圖2所示。圖1中顯示了緩沖區(qū)大小對3種算法在混合存儲系統(tǒng)中I/O訪問開銷的影響（這3種算法均執(zhí)行一個15萬次的頁請求序列來進行測試，讀寫請求數(shù)目之比為8：2，閃存和磁盤存儲的讀寫數(shù)據(jù)頁各占50%），其中圖1（a）和圖1（b）分別比較了3種算法的寫操作次數(shù)和訪問開銷。如圖1所示，傳統(tǒng)的LRU算法對混合存儲磁盤的寫操作和訪問開銷很大。圖1（a）中，T/C LRU算法寫操作次數(shù)明顯低于DLAB，同時圖1（b）中的訪問開銷卻高于DLSB，接近于LRU的訪問開銷。這是因為T/C LRU算法只注重于簡單的數(shù)據(jù)頁代價比較，沒有考慮到數(shù)據(jù)頁頻繁訪問的代價。

圖1 緩沖區(qū)大小對I/O性能的影響

圖2 存取模式對I/O性能的影響

圖2顯示了在不同的數(shù)據(jù)流中，不同的存取模式對3種算法在混合存儲系統(tǒng)中I/O訪問開銷的影響（緩沖區(qū)為10M，頁請問請求為15萬次）。如圖3所示，DLAB算法在數(shù)據(jù)頁的寫操作次數(shù)和訪問開銷方面顯著優(yōu)于LRU和T/C LRU算法。隨著讀寫請求比例的減少，T/C LRU算法可置換的干凈的磁盤頁和閃存頁所占比例逐漸降低，緩沖區(qū)中可用于優(yōu)先置換的干凈頁越來越少，T/C LRU算法性能逐漸下降。同時DLAB算法在讀寫比例減少的情況下，由于基于代價的自適應性，對數(shù)據(jù)頁的置換沒有優(yōu)先級別的劃分，因此寫操作次數(shù)和訪問開銷顯著優(yōu)于另外兩種算法。

4 結(jié)束語

本文提出一種針對混合存儲系統(tǒng)的自適應緩沖區(qū)管理算法DLSB。通過對數(shù)據(jù)頁邏輯操作和物理操作的代價考慮，選擇代價最優(yōu)的數(shù)據(jù)域，較好的適應不同數(shù)據(jù)流的訪問負載。同時，通過域中隊列實際容量和隊列理想容量的比較，最終確定置換的數(shù)據(jù)頁，降低了對干凈數(shù)據(jù)頁的頻繁置換。實驗結(jié)果表明，與LRU和T/C LRU相比，DLSB顯著降低了混合存儲系統(tǒng)的I/O訪問開銷。今后的研究工作，將進一步完善DLSB算法中閃存臟頁的置換效率，提高閃存的使用壽命和混合存儲系統(tǒng)的I/O訪問效率。

［1］CHEN Zhiguang.Research and implementation on introducing flash into multi－level storage archtecture ［D］.Changsha：National University of Defend Technology，2009：20－30（in Chinese）.［陳志廣.引入flash的多層次存儲結(jié)構研究與實現(xiàn)［D］.長沙：國防科技大學，2009：22－30.］

［2］Koltsidas I，Viglas S D.Flashing up the storage layer［C］.Proceeding of the 34th Conference on VLDB.New York：ACM，2008：514－524.

［3］Marsh B，Douglis F，Krishnan P.Flash memoryfile caching for mobile computers ［C］.Hawaii，USA：Proceeding of the 27th Hawaii International Conference on System Sciences，2005.

［4］Panabaker R，Hybrid Hard.Ready DriveTMTechnology：Improving performance and power for Windows vista mobile PCs［C］.Porc of Microsoft WinHEC，2006.

［5］Bisson T，Brandt S，Long D.A hybrid disk－aware spin－down algorithm with I/O subsystem support ［C］.Proc of the 26th IEEE International Performance Computing and Communications Conference.New Orleans，Louisiana，USA，2007：11－13.

［6］Kim Young Jin，LEE Sung Jin，ZHANG Kangwon，et al.I/O performance optimization techniques for hybrid hard disk－based mobile consumer devices ［J］.IEEE Computer，2007，53（4）：1469－1476.

［7］Wikipedia.Hybriddrive ［EB/OL］.http：//en.wikipadia.org/wiki/Hybrid＿drive，2011.

［8］Kim Young Jin，Kwon Kwon Teak，Jihong Kim.Energy－efficient file placement techniques for heterogeneous mobile storage systems ［C］.Proceedings of the 6th ACM IEEE International Conference on Embedded Software，2006.

［9］LEE Sang Won，Bongki Moon.Design of flash－based DBMS：An in－page logging approach［C］.Proceedings of the ACM SIGMOD International Conference on Management of Data，2007.

［10］TANG Xian.ACR：An adaptive cost－aware buffer replacement algorithm for flash storage devices ［C］.Eleventh International Conference on Mobile Management，2010.

［11］Hyojun Kin.BPLRU：A buffer management scheme for improving random writes in flash storage ［C］.6th USENIX Conference on File and Storage Technologies USENIX Association，2008：239－252.

［12］Park Seon Yeong，Dawoon Jung.CFLRU：A replacement algorithm for flash memory ［C］.IEEE Transactions on Consumer Electronics，2006.

［13］YI Ou，Theo Harder，JIN Peiquan.CFDC－A flash－aware replacement policy for database buffer management ［C］.Proceedings of the Fisth International Workshop on Data Management on New Hardware.Rhode－Island，ACM，2009：15－20.

［14］Jung H，Shim H，Park S，et al.LRU－WSR：Integration of LRU and writes sequence reordering for flash memory ［J］.IEEE Trans on Consumer Electronics：2008：1215－1223.

［15］WU C H，KUO T W.An adaptive tow－level management for the flash translation layer in embedded systems ［C］.Proc of the IEEE/ACM International Conference on Computer－Aided Design，2006：601－606.