NAND閃存垃圾回收策略改進

胡 萍

（ 1.貴州大學(xué) 計算機科學(xué)與信息學(xué)院，貴州 貴陽 550025；2.銅仁學(xué)院 繼續(xù)教育部，貴州 銅仁 554300 ）

NAND閃存垃圾回收策略改進

胡 萍1，2

（ 1.貴州大學(xué) 計算機科學(xué)與信息學(xué)院，貴州 貴陽 550025；2.銅仁學(xué)院 繼續(xù)教育部，貴州 銅仁 554300 ）

閃存是取代磁盤成為主流存儲設(shè)備的首選，但由于閃存的特殊的硬件特征，閃存的存儲管理成為了目前研究的熱點。閃存在什么時候回收垃圾塊，怎樣回收，是使磨損均勻分布，延長設(shè)備壽命的重要策略。文章就目前的垃圾回收策略做了進一步改進，從而降低塊的選擇和數(shù)據(jù)轉(zhuǎn)移代價。

高垃圾塊； 有效數(shù)據(jù)； 回收； 能耗

1.引言

閃速存儲器，也稱為閃存（Flash）。與物理設(shè)備磁盤不同，閃存是電子設(shè)備，不需要花費大量的時間在機械尋道上。閃存以其高速的數(shù)據(jù)存儲速度、節(jié)能、噪聲小、抗震、體積小、斷電后數(shù)據(jù)不易失等優(yōu)勢，是取代磁盤成為主流存儲設(shè)備的首選。

當(dāng)前已有用閃存為主要介質(zhì)的固態(tài)硬盤被應(yīng)用到了電腦和一些儲存產(chǎn)品中，隨之而來的問題也出現(xiàn)了。經(jīng)常調(diào)用的程序存儲塊磨損相對大，使用較少的程序存儲塊磨損相對小，這就導(dǎo)致了磨損的不均勻，縮短設(shè)備壽命。良好的垃圾回收策略能讓塊與塊之間的擦除次數(shù)之差控制在合理范圍之內(nèi)，使數(shù)據(jù)塊得到均勻的磨損，盡可能地延長設(shè)備壽命，提高系統(tǒng)性能。本文基于NAND型芯片，對現(xiàn)有垃圾回收機制進行改良，降低數(shù)據(jù)轉(zhuǎn)移代價。

2.相關(guān)概念

在閃存中，每個物理塊都有一個值，當(dāng)物理塊上的所有頁都被擦除為空閑時，當(dāng)前塊可以寫入數(shù)據(jù)，該塊為空閑塊（Free）。當(dāng)對數(shù)據(jù)塊寫入沒有成功則該塊為臟塊（Dirty）。寫入成功的有效數(shù)據(jù)塊為干凈塊（Clean）。不能將數(shù)據(jù)寫入而只能讀出的塊為壞塊（Bad）。

閃存設(shè)備驅(qū)動層提供讀、寫、擦除操作。因為閃存特殊的硬件特征，數(shù)據(jù)是按頁（page）讀寫，按塊（block）為基本單位擦除。閃存不支持本地更新，要更新數(shù)據(jù)需將新數(shù)據(jù)存儲在空閑頁，而將原來存放數(shù)據(jù)的頁作無效記號，當(dāng)空閑頁少于一定數(shù)量就會激發(fā)垃圾回收機制，將無效的頁回收并以塊為單位進行擦除。

3.現(xiàn)有垃圾回收策略

現(xiàn)有的垃圾回收策略主要集中研究以下兩個問題：（1）什么時候回收，即在怎樣的條件下觸發(fā)回收；（2）怎樣回收，即如何選擇回收對象。

杜曄華等人提出的多片閃存系統(tǒng)垃圾回收器[1]在運作總建立計數(shù)器LRU鏈表，并在垃圾回收中構(gòu)建代價函數(shù)利用函數(shù)尋找到的三元組(j，k，l∈B)來選擇回收對象，由此得到遷移能耗代價最低的物理塊進行擦除。

邢春波[2]則認為垃圾回收條件是與空閑頁剩余量和剩余電量有緊密聯(lián)系的，并構(gòu)造了電量約束函數(shù)作為回收啟動條件。在垃圾塊的選擇上受三個因素影響：（1）有效頁數(shù)量；（2）回收塊所處片狀態(tài)；（3）塊擦除次數(shù)與時間。

4.塊的選擇與數(shù)據(jù)轉(zhuǎn)移修改

圖1 塊結(jié)構(gòu)圖

在垃圾塊的選擇上，加入磨損均衡的思想。因為閃存的數(shù)據(jù)塊頭中包含擦除標(biāo)志、數(shù)據(jù)有效標(biāo)志等，我們建立鏈表用于數(shù)據(jù)是否有效的狀態(tài)管理[4]。對于各個塊，按各塊數(shù)據(jù)有效頁數(shù)量插入到鏈表中。按這種方式管理，能防止數(shù)據(jù)塊的過冷或過熱。當(dāng)數(shù)據(jù)塊的無效頁數(shù)量達到設(shè)置閾值時，將此塊作為垃圾塊回收，在鏈表中將此塊清空，重新建立擦除后有效數(shù)據(jù)量，如圖1所示。

當(dāng)數(shù)據(jù)塊 1作為垃圾塊回收，還需要判斷的是該塊數(shù)據(jù)頭中的時間標(biāo)志Ti，若Ti-Ti-1大于平均時間差，則該塊作為優(yōu)先擦除塊[3]。Ti-Ti-1小于平均時間差，該則塊擦除操作頻繁，會造成該塊過熱，不將該塊作為垃圾塊回收。可把待擦除的垃圾塊上的有效數(shù)據(jù)轉(zhuǎn)移到該塊上。

i有效頁占用率，ti為擦除時間差，i為擦除次數(shù)。因此當(dāng)無效頁數(shù)據(jù)達到閾值時，啟動垃圾塊的回收過程如圖2。

圖2 回收過程

5.仿真

用VHDL語言搭建平臺，構(gòu)造大小為4M的內(nèi)存作為閃存模型，數(shù)據(jù)塊為256KB，扇區(qū)為512B，總共為16塊。防止閃存被寫滿，先留出部份數(shù)據(jù)塊作為數(shù)據(jù)轉(zhuǎn)移的目標(biāo)塊，當(dāng)不可預(yù)期的結(jié)果出現(xiàn)時，將有效數(shù)據(jù)轉(zhuǎn)移到這些塊上。仿真環(huán)境每頁讀取時間為10μs，寫入時間為200μs，擦除時間為2ms，讀取能耗為1.18μJ，寫入能耗為9.51μJ，擦除能耗為 16.5μJ，空閑頁功耗為 0.13mW。根據(jù)構(gòu)造的函數(shù)選擇垃圾塊，請求能耗與未改動之前降低了5.34%，回收能耗降低了9.62%，空閑頁能耗未發(fā)現(xiàn)明顯變化，數(shù)據(jù)轉(zhuǎn)移能耗降低2.63%。

6.總結(jié)

經(jīng)過仿真驗證，該改進策略對于能耗的降低是有效的。但垃圾回收策略的改進與更新策略，讀寫操作策略，磨損均衡策略是有著緊密聯(lián)系，僅僅從垃圾回收策略上入手是不夠的。冷熱數(shù)據(jù)的交換，磨損的均衡分布，讀寫操作策略也是研究NAND閃存存儲管理的幾個關(guān)鍵。

[1]Du Yehua, Cai Ming, Dong Jinxiang. A data affinity based garbage collector for multi-bank flash-memory storage system[J]. Journal of Huazhong University of Science and technology, 2007.

[2]邢春波.閃存磨損均衡算法研究[D].浙江工業(yè)大學(xué)，2008.

[3]CHIANG ML, LEE PCH. CHANG RC.F1ash Memory management For Lightweight Storage System[EB/0L]. http://www.iis.sinica.edu.tw/LIB/Teachreport/tr1988/tr98003.ps.gz

[4]CHlANG ML, LEE PCH, CHANG RC. C1eaning P01icie8 in Mobile Computers Using Flash Memory[J]. Joumal of Systems and software, 1999.

[5]張峻，樊曉椏，李松鶴.一種flash存儲器靜態(tài)負載平衡策略[J].計算機應(yīng)用，2006.

Improvement on NAND Flash Memory Garbage Collection Strategy

HU Ping1,2
( 1. College of Computer Science and Technology, Guizhou University, Guiyang, Guizhou 550025, China;2. Continuing Education Institute, Tongren University, Tongren, Guizhou 554300, China )

Flash memory is the first choice to replace the disk into the mainstream storage devices, but special hardware characteristics of flash memory. The flash-based storage management has become a current research focus.Flash dirty block when, and how recovery and wear are very important strategy. Further improve on the current dirty block recycle strategy, thereby reducing the cost of the block selection and data transfer.

High dirty block; valid data; recycle; Energy consumption

（責(zé)任校對 黎 帥）

TP333

A

1673-9639 (2012) 04-0141-03

2012-04-12

胡 萍（1983-），女，貴州銅仁人，研究方向：計算機應(yīng)用技術(shù)數(shù)據(jù)庫人事管理。

（責(zé)任編輯 印有家）