闪存循环位图的损耗均衡机制研究

刘智朋，罗洪元，阳小珊，邱全伟，郑 良

(1.中国电子科技集团公司第十五研究所国家电子计算机质量监督检验中心，北京100083;2.中国传媒大学存储实验室，北京100024)

0 引言

由于闪存 (flash memory)具有体积小、能耗低、零噪音、抗震动等优势，因此得到了广泛应用。在闪存中，页是数据读写的基本单位，块是数据擦除的基本单位。对于页来说，只有当包含它的整个物理块被擦除时，才可以重新写入。此外，闪存的物理块对擦除次数也有限制。对于SLC(single level cell)型闪存，在现有技术下的擦除次数为10万次，而MLC(multi-level cell)型闪存更少，一般为1 万次［1］。

为了将擦除写入操作平均分配到闪存中的物理块中，提高物理块的使用率，延长闪存的使用寿命，提出了损耗均衡机制。损耗均衡机制能够显著提高物理块的利用率，最终延长闪存设备的寿命，对闪存的设计和实际应用都具有重要指导意义。现有的闪存设备使用的大都是动态和静态两种损耗均衡机制，但由于它们在自身运行效率和提高块利用率方面的不足，因此如何弥补和改进原有机制就变得亟待解决了。

1 相关研究

1.1 闪存的寿命与损耗均衡机制的数学关系

闪存中的物理块的擦除次数决定着闪存寿命，我们通过如下的数学公式进行定量的分析

式中:Lifetime——闪存的寿命，单位是年。Cap——闪存的存储容量，常见的 NAND Flash［2］容量为 8～128MB。EC(erase cycle)——闪存物理块的擦除次数上限，或者说是擦除次数的期望值。Usa_Per-_D［3］是每天进行擦除写入的存储空间，那么Usa_P-er_D*365是一年进行擦除写入的存储空间的大小。Rate是在闪存中写入数据时，需要写空间与实际写空间的比值，全称为Write Amplification Rate［4］(写扩大倍数)，在闪存上进行连续写操作时，其Rate维持在1.1左右。

Util是闪存在使用过程时所有物理块实际擦除次数之和与期望擦除次数之和的百分比，即

式中:Ri——PBA i(Physical Block Address)的实际擦除次数，Rsum——所有物理块实际擦除次数之和;Ei——物理块PBA i的期望擦除次数［5］，Esum——所有物理块的期望擦除次数之和;n——闪存中物理块总量。由于特定型号、容量和应用的闪存，Cap、EC、Usa_Per_D和Rate都是不变的，所以根据式 (1)可知闪存的寿命和Util成正比。在式(2)中Esum是固定不变的，所以Util的值由Rsum决定。假设某闪存设备中，有25%的内容为动态内容 (经常被更新的数据)，75%为静态内容 (很少被更新的数据)。若不使用损耗均衡机制，系统会集中使用20%～30%的块进行数据写入操作，剩下70%～80%块的利用率就会降低。由于块的损耗不均衡关系，当20%～30%块的擦除次数达到上限时，70%～80%的块的擦除次数却很少，此时Rsum相应的就会很低。相反，如果在闪存中使用损耗均衡机制，那么Rsum就会增多，进而增大 Util的值，使块的利用率得到显著提高。

随着闪存擦除写入利用率的提高，闪存的寿命也会延长。由此可见，损耗均衡机制对于提高闪存的寿命具有重大意义。

1.2 损耗均衡技术现状与分析

现在主流的损耗均衡分为动态损耗均衡［6］和静态损耗均衡［6］两种。

动态损耗均衡机制是在所有空闲块中寻找擦除次数最小的进行写入，从而保证数据的擦除写入被均匀地分布到闪存的所有块中。动态损耗均衡主要回收动态数据块 (经常被更新的块)，而那些静态数据块 (很少被更新的块)，在动态损耗均衡过程中却没有被回收，因而造成动态数据块和静态数据块的擦除次数相差很大。因此，为了获得更好的损耗均衡，闪存中引入了静态损耗均衡机制。它会强制搬移静态数据到动态数据块中去，在更大程度上增加闪存的使用寿命和可靠性。然而，系统要花费大量的时间和资源寻找擦除次数最多和最少的块，而且在特定的时间内不能保证静态数据块的擦除。为了进一步提高闪存的损耗均衡的效果，研究和设计了循环位图损耗均衡机制。

本文中的损耗均衡机制分为动态写入和静态回收两个阶段。动态写入阶段利用动态控制指针追踪到空闲物理块对数据进行写入。静态回收阶段首先利用静态控制指针追踪含有静态数据的物理块 (记为PBA1)，然后找到活动频繁的物理块 (记为PBA2)，将PBA1中的内容复制到PBA2中，从而减少PBA2的损耗。新的损耗均衡机制的设计不仅可以免除寻找最大和最小擦除次数块所带来的时间和性能消耗，而且可以将擦除写入更加平均地分配到闪存物理块中，延长了闪存的寿命，使损耗均衡取得令人满意的效果。

2 基于循环位图的损耗均衡机制的设计

2.1 整体结构

本文提出的损耗均衡设计所基于的系统架构如图1所示。

图1 系统架构

应用系统通过系统接口向闪存设备发送读写操作命令，微处理器 (CPU)接收命令后通过闪存接口对闪存进行操作［7］。基于循环位图的损耗均衡机制主要是在控制器中加入一个管理单元。管理单元包括热点列表、循环位图、关系记录表、地址映射表和擦除计数表。这些图表相互配合，保证均衡损耗机制的实现。

管理单元中的图表存储在固定的闪存块中。在闪存设备接通电源时，它们从闪存块载入静态随机存储器 (Static RAM，SRAM)中，并在周期时期段或者断电时重新在闪存块中进行备份。

2.2 FTL

在传统的损耗均衡机制中，FTL［8］通过地址映射表(mapping address table，MAT)寻找逻辑地址 (logical block address，LBA)到物理地址 (physial block address，PBA)的映射，同时对闪存块进行擦除计数管理。块的擦除次数记录在擦除计数 (erase count table，ECT)中。

此文中的机制，在FTL中添加一个关系记录表 (relation note table，RNT)，它用来记录每个逻辑块和其所对应的多个物理块之间的连接关系。如图2所示。

图2 关系记录

使用图2中的PBA2进行简单说明。PBA2所对应的逻辑块为LBA0。某时刻当应用系统需要修改LBA0所对应的内容时，控制器就会在已经进行擦除操作的PBA7中记录更新的内容，然后在BNT中记录PBA2和PBA7之间的连接关系。当LBA0所对应的内容需要再次修改的时候，控制器就会继续在已经擦除的PBA10中记录更新的内容，并同时记录PBA2、PBA7和PBA10之间的连接关系。这样，在BNT中就构成了一个由PBA2、PBA7和PBA10组成的物理块链。其中，PBA2记为Block，PBA7和PBA10记为Junior_Block。

2.3 热点列表

热点列表［9］(hot list，HL)记录的是最近频繁被写入或者修改的逻辑块。当控制器完成数据写入的操作后，HL就会随之更新。根据物理块和逻辑块之间的对应关系，只需要随时检验HL，就可以通过表中的逻辑块找到擦除次数较多的物理块。图3所示的为某时刻闪存的 HL，其中LBA0是活动最频繁的逻辑块。

图3 热点列表

2.4 循环位图

循环位图是使用擦除标志位［10］(erase marked bit，EMB)判断物理块的擦除状态。EMB值为1表示块已经被擦除，EMB值为0表示块尚未进行擦除。这些块按照存储地址的升序组织，最后一块指向第一块。图4为某时刻闪存的循环位图。

循环位图是本机制的核心部分，可通过它找到空闲物理块和静态数据块，进行写入和擦除操作。

图4 循环位图

循环位图包括两个指针，分别为动态控制指针 (dynamic control pointer，dcp)和静态控制指针 (static control pointer，scp)。其中dcp始终指向循环位图中EMB为1的物理块即空闲物理块，而scp始终指向EMB为0的物理块即静态数据块。控制指针依照循环位图顺序查找，直到找到符合要求的物理块为止;如果查找到位图尾部，仍旧无法找到，那么跳转到位图首部继续按顺序查找，如此循环，直到找到为止。

2.5 机制设计

2.5.1 动态写入阶段

图5 动态写入阶段流程

如图5所示，如果控制器接收到外部应用的写入命令时，就会通过动态控制指针在循环位图中查找EMB为1的物理块Target_PBA，然后执行下面的操作:

(1)将数据写入Target_PBA中;

(2)将相应的物理块和逻辑块的映射关系写入地址映射表和关系记录表;

(3)更新热点列表即将物理块所对应的逻辑块写入其中;

(4)循环位图中动态控制指针对应的物理块Target_PBA的EMB改为0;同时dcp向前移动到下一个EMB为1的物理块上。

与动态损耗均衡机制中写入数据阶段相比，此机制不需要寻找擦除次数最小的物理块，只需要根据动态控制指针找到当前所指向的空闲物理块。因为指针在循环位图中移动，所以可以近似地认为物理块的利用率是大致相等的。

2.5.2 静态回收阶段

对于那些写入闪存并存储了相当长一段时间甚至无限期的数据，动态写入阶段无法起作用。此外，在动态写入阶段，空闲物理块会不断被消耗，直至闪存中没有空闲块提供数据的写入操作。基于此，本机制提出了静态回收阶段。

图6为损耗均衡机制静态回收阶段的流程图。

图6 静态回收阶段流程

主要流程如下:

(1)在热点列表中查找活动最频繁的逻辑块 (记为Hot_LBA)，通过MAT和RNT找到Hot_LBA

对应的物理块链。此时，物理块链中包含的物理块是活动较频繁的物理块。假设物理块链中有n个物理块，那么Source_PBA i(i=1，2，…，n)表示物理块链中第i个物理块;

(2)查找循环位图中动态控制指针所指向的物理块(记为Target_PBA);

(3)将物理块链中尾部块Source_PBA n的内容 (Hot_LBA所对应的最新内容)写入Target-PBA中，修改MAT和RNT中的对应关系，将循环位图中Target_PBA的EMB值改为0，位图中的dcp指向下一个EMB为1的物理块;

(4)下面的不等式用来判断物理块的擦除次数是否大于闪存中物理块的平均擦除次数

其中Ei表示闪存中第i个物理块的擦除次数。

如果不等式不成立，那么Source_PBA i需要进行擦除，然后处理下一个物理块Source_PBA(i+1)，直到物理块链中所有物理块操作完成。

如果不等式成立，scp所指向的物理块包含的内容为静态内容，记为Static_PBA。将Static_PBA中的数据转移到物理块Source_PBA i中，然后对其进行擦除操作。这个过程实现了把静态数据放入活动频繁的物理块中;

(5)对于第i+1个物理块即Source_PBA(i+1)，重复 (4)中的操作，直到物理块链中所有物理块操作完成。

静态回收阶段流程比较复杂，这里举例说明。

根据热点列表查找到活动最频繁的逻辑块 LBA0。LBA0对应的物理块链是PBA2、PBA7和PBA10组成的物理块链。此时，动态控制指针 dcp所指向的空闲块为PBA0，如图7(a)过程一中所示。

将含有最新更改过的内容的PBA10中的数据写入PBA0中，PBA0在位图中的EMB改为0，如图7(b)过程二中所示。

通过静态控制指针找到静态数据块PBA1。假设PBA2中的擦除次数大于平均擦除次数，那么将PBA1中数据迁移到PBA2中。对管理单元中的图表进行修改，如图7(c)过程三所示。物理链中剩下的PBA7和PBA10使用同样的方法处理。

3 性能分析

本机制通过在控制器中加入管理单元来控制损耗均衡机制的实现。在机制运行过程中，管理单元的图表，尤其是循环位图的管理在时间和空间上会产生额外损耗，但是和传统的损耗均衡机制相比，不需要查找擦除次数最大和最小的物理块，所以对闪存写入数据的速度没有影响。

为验证循环位图的损耗均衡机制的有效性和实用性，对其进行了性能分析。假设闪存设备的参数如表1所示，其中读写操作时间是微秒级的，两次写操作间隔时间是毫秒级的［11］。

闪存中有n个物理块，物理块链中的平均物理块为m个。假设某一时刻闪存中有an(0＜a＜1)个空闲物理块，(1-a)n个非空闲物理块，根据热点列表找到的物理块链中擦除次数大于平均擦除次数的个数是βm(0＜a＜1)。

图7 静态回收阶段过程

表1 参数值

在动态写入阶段，一个空闲物理块被消耗;在静态回收阶段，βm-1个空闲物理块会产生。为了使消耗和产生的空闲块达到平衡，需要控制静态回收阶段的启动时间和启动次数。假设写操作时间为t1，擦除操作时间为t2，两次写操作之间的间隔时间为t3，那么两次静态回收过程的间隔即静态回收的时间阈值t4为

那么由此得到静态数据块被回收的最长等待时间t5为

由此可知，物理块在特定时间t5内会进行擦除处理，避免了静态数据被长时间的存放。与静态损耗均衡机制和动态损耗均衡机制相比，静态数据块的回收不再依赖于最大与最小擦除次数，并且有固定的回收时间，避免了大量的静态块长久不能被擦除的状况。

假设某闪存设备中，有25%的内容为动态内容，75%为静态内容。那么，在特定处理时间内，通过性能分析得到的动态、静态和循环位图3种机制闪存空间利用率对比情况如图8所示。显然，和静态与动态损耗均衡机制相比，闪存循环位图的损耗均衡机制使物理块的擦除次数更加均衡，从而延长闪存的使用寿命。

图8 损耗均衡机制闪存空间利用率对比

4 结束语

此研究通过在闪存的系统架构中加入循环位图，研究和设计了一种新的损耗均衡机制。新的机制包含动态写入和静态回收两个阶段。二者相互配合、相互促进，从而使物理块的擦除次数更加均衡，延长了闪存的使用寿命，有一定的应用价值。

为了保证机制的有效性和实用性，该机制需要在闪存设备中进行大规模地应用，并对应用过程中收集到的测试数据进行分析和研究，从而进一步的优化和完善此机制。

［1］Marco A A Sanvido，Frank R Chu，Anand Kulkarni.NAND flash memory and its role in storage architectures［J］.Proceedings of the IEEE，2008，96(11):1864-1874.

［2］PAN Liyang，ZHU Jun.Flash memory technology and its development［J］.Microelectronics，2002，32(1):1-6(in Chinese).［潘立阳，朱钧.Flash存储器技术和发展 ［J］.微电子学，2002，32(1):1-6.］

［3］Alan ROlson，Denis JLanglois.Solid statedrives datareliability and lifetime ［EB/OL］.［2008-04-07］.http://www.csee.umbc.edu.

［4］ZHANG Dong.Discuss storage2-deep analysis of storage system ar-chitecture and the bottom principles［M］.Beijing:Tsinghua University Press，2011:50-60(in Chinese).［张冬.大话存储2-存储系统架构与底层原理极限剖析［M］.北京:清华大学出版社，2011:50-60.］

［5］Application note:Wear leveling in NAND flash memory［EB/OL］.［2007-07-01］.http://www.micron.com/.

［6］Wear-leveling techniques in NAND flash devices［EB/OL］.［2008-10-08］.http://www.micron.com/.

［7］Jeong-UK Kang，Jin-Soo Kim，Chanik Park，et al.A multi-channel architecture for high-performance NAND flash-based storage system［J］.Journal of Systems Architecture，2007，53(2007):644-658.

［8］CHANG Lipin，HUANGLichun.A low-cost wear-leveling algorithm for block-mapping solid-state disks［J］.ACM SIGPLAN Notices-LCTES＇10，2011，46(5):31-40.

［9］CHANG Lipin，CHEN Mingdar，HUANG Chienting.Flash memory device with wear-leveling mechanism and controlling method thereof［P］.US:2010/0115186，2010-05-06.

［10］WANG Weineng，NI Kai，MA Jianshe，et al.Static wear-leveling design of flash memory in multi-channel parallel access mode ［J］.JTsinghua Univ(Sci＆Tech)，2011，51(11):1616-1620(in Chinese).［王伟能，倪凯，马建设，等.多通道并行访问模式下的闪存静态损耗均衡设计［J］.清华大学学报 (自然科学版)，2011，51(11):1616-1620.

［11］Muthukumar Murugan，David H C Du Rejuvenator.A static wear leveling algorithm for NAND flash memory with minimized overhead［C］//IEEE 27th Symposium on Mass Storage Systems and Technologies，2011:1-12.