基于閃存的混合存儲(chǔ)系統(tǒng)緩沖區(qū)管理算法

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

（1.貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院，貴州 貴陽(yáng)550025；2.貴州星辰科技開(kāi)發(fā)有限公司，貴州貴陽(yáng)550025）

0 引 言

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

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

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

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

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

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

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

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

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

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

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

為了便于描述，對(duì)本文所涉及的若干符號(hào)給出了定義，見(jiàn)表1。

表1 本文所用符號(hào)及其意義說(shuō)明

2 自適應(yīng)存儲(chǔ)方法

2.1 算法概述

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

2.2 自適應(yīng)的域間選擇策略

干凈頁(yè)域的代價(jià)和臟頁(yè)域的代價(jià)分別為式（1）、（2）

式中：Lcf的代價(jià)記——Clcf，代價(jià)計(jì)算如式（3）

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

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

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

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

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

2.4 DLSB算法描述

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

表2 DLSB算法

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

表3 EvitctPage過(guò)程

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

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

圖2 存取模式對(duì)I/O性能的影響

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

4 結(jié)束語(yǔ)

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

［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的多層次存儲(chǔ)結(jié)構(gòu)研究與實(shí)現(xiàn)［D］.長(zhǎng)沙：國(guó)防科技大學(xué)，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.