NAND闪存垃圾回收策略改进

胡 萍

（ 1.贵州大学 计算机科学与信息学院，贵州 贵阳 550025；2.铜仁学院 继续教育部，贵州 铜仁 554300 ）

NAND闪存垃圾回收策略改进

胡 萍1，2

（ 1.贵州大学 计算机科学与信息学院，贵州 贵阳 550025；2.铜仁学院 继续教育部，贵州 铜仁 554300 ）

闪存是取代磁盘成为主流存储设备的首选，但由于闪存的特殊的硬件特征，闪存的存储管理成为了目前研究的热点。闪存在什么时候回收垃圾块，怎样回收，是使磨损均匀分布，延长设备寿命的重要策略。文章就目前的垃圾回收策略做了进一步改进，从而降低块的选择和数据转移代价。

高垃圾块； 有效数据； 回收； 能耗

1.引言

闪速存储器，也称为闪存（Flash）。与物理设备磁盘不同，闪存是电子设备，不需要花费大量的时间在机械寻道上。闪存以其高速的数据存储速度、节能、噪声小、抗震、体积小、断电后数据不易失等优势，是取代磁盘成为主流存储设备的首选。

当前已有用闪存为主要介质的固态硬盘被应用到了电脑和一些储存产品中，随之而来的问题也出现了。经常调用的程序存储块磨损相对大，使用较少的程序存储块磨损相对小，这就导致了磨损的不均匀，缩短设备寿命。良好的垃圾回收策略能让块与块之间的擦除次数之差控制在合理范围之内，使数据块得到均匀的磨损，尽可能地延长设备寿命，提高系统性能。本文基于NAND型芯片，对现有垃圾回收机制进行改良，降低数据转移代价。

2.相关概念

在闪存中，每个物理块都有一个值，当物理块上的所有页都被擦除为空闲时，当前块可以写入数据，该块为空闲块（Free）。当对数据块写入没有成功则该块为脏块（Dirty）。写入成功的有效数据块为干净块（Clean）。不能将数据写入而只能读出的块为坏块（Bad）。

闪存设备驱动层提供读、写、擦除操作。因为闪存特殊的硬件特征，数据是按页（page）读写，按块（block）为基本单位擦除。闪存不支持本地更新，要更新数据需将新数据存储在空闲页，而将原来存放数据的页作无效记号，当空闲页少于一定数量就会激发垃圾回收机制，将无效的页回收并以块为单位进行擦除。

3.现有垃圾回收策略

现有的垃圾回收策略主要集中研究以下两个问题：（1）什么时候回收，即在怎样的条件下触发回收；（2）怎样回收，即如何选择回收对象。

杜晔华等人提出的多片闪存系统垃圾回收器[1]在运作总建立计数器LRU链表，并在垃圾回收中构建代价函数利用函数寻找到的三元组(j，k，l∈B)来选择回收对象，由此得到迁移能耗代价最低的物理块进行擦除。

邢春波[2]则认为垃圾回收条件是与空闲页剩余量和剩余电量有紧密联系的，并构造了电量约束函数作为回收启动条件。在垃圾块的选择上受三个因素影响：（1）有效页数量；（2）回收块所处片状态；（3）块擦除次数与时间。

4.块的选择与数据转移修改

图1 块结构图

在垃圾块的选择上，加入磨损均衡的思想。因为闪存的数据块头中包含擦除标志、数据有效标志等，我们建立链表用于数据是否有效的状态管理[4]。对于各个块，按各块数据有效页数量插入到链表中。按这种方式管理，能防止数据块的过冷或过热。当数据块的无效页数量达到设置阈值时，将此块作为垃圾块回收，在链表中将此块清空，重新建立擦除后有效数据量，如图1所示。

当数据块 1作为垃圾块回收，还需要判断的是该块数据头中的时间标志Ti，若Ti-Ti-1大于平均时间差，则该块作为优先擦除块[3]。Ti-Ti-1小于平均时间差，该则块擦除操作频繁，会造成该块过热，不将该块作为垃圾块回收。可把待擦除的垃圾块上的有效数据转移到该块上。

i有效页占用率，ti为擦除时间差，i为擦除次数。因此当无效页数据达到阈值时，启动垃圾块的回收过程如图2。

图2 回收过程

5.仿真

用VHDL语言搭建平台，构造大小为4M的内存作为闪存模型，数据块为256KB，扇区为512B，总共为16块。防止闪存被写满，先留出部份数据块作为数据转移的目标块，当不可预期的结果出现时，将有效数据转移到这些块上。仿真环境每页读取时间为10μs，写入时间为200μs，擦除时间为2ms，读取能耗为1.18μJ，写入能耗为9.51μJ，擦除能耗为 16.5μJ，空闲页功耗为 0.13mW。根据构造的函数选择垃圾块，请求能耗与未改动之前降低了5.34%，回收能耗降低了9.62%，空闲页能耗未发现明显变化，数据转移能耗降低2.63%。

6.总结

经过仿真验证，该改进策略对于能耗的降低是有效的。但垃圾回收策略的改进与更新策略，读写操作策略，磨损均衡策略是有着紧密联系，仅仅从垃圾回收策略上入手是不够的。冷热数据的交换，磨损的均衡分布，读写操作策略也是研究NAND闪存存储管理的几个关键。

[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].浙江工业大学，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存储器静态负载平衡策略[J].计算机应用，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

（责任校对 黎 帅）

TP333

A

1673-9639 (2012) 04-0141-03

2012-04-12

胡 萍（1983-），女，贵州铜仁人，研究方向：计算机应用技术数据库人事管理。

（责任编辑 印有家）