基于NAND Flash存储器的磨损均衡DP算法优化

2019-06-17薛镭

计算机应用与软件 2019年6期

薛镭

(中国船舶重工集团公司第七一五研究所浙江杭州 310023)

0 引言

用NAND Flash作为存储媒介，具有体积小、功耗低、速度快等特点，广泛受到青睐，在手机、平板电脑、数码相机等电子产品中均有运用[1]。NAND Flash不能被复写，写之前需要做擦除操作。NAND Flash读写操作的基本单位是页。其中包含最新数据的页被称为有效页(新数据被称为有效数据)，包含旧数据的页被称为无效页或脏页，脏页经过擦除操作后成为空闲页，才可以重新写入数据。NAND Flash擦除操作的基本单位是块(如1个块包含多个页)，块的擦除次数是有限的(根据不同颗粒类型如TLC/MLC/SLC等，一般几千次到100万次之间)，如果出现块的擦除次数达到了上限，NAND Flash的性能将大幅下降[2]。

经常使用读写的数据称为热数据,很少被读写到的数据称为冷数据，冷数据和热数据将导致存储在NAND介质上的数据块的读写擦除计数出现严重不平衡。为了保持NAND Flash性能的稳定，必须提出一种方法使每个块的擦除操作尽可能均衡，这种方法就是磨损均衡算法。

Chang[3]提出的双池算法是目前众多磨损均衡算法中较为主流的算法。相比其他算法而言，该算法主要解决了“冷块”几乎不被处理和磨损控制水平较低的问题，达到了预期的磨损均衡效果。本文在双池算法的基础上，保留磨损控制的策略，针对其不足之处提出进一步优化的方案，并通过仿真实验进行验证分析，期望保留较高磨损控制水平，缩短磨损均衡过程，减少页复制次数，使NAND Flash的使用寿命进一步提高。

1 双池算法

1.1 算法原理

该算法首先将NAND Flash块随机地分配到“冷池”和“热池”中，随着数据的更新，算法将存放冷热数据的NAND Flash块分别存入“冷池”和“热池”中。如果“热池”中的某些块的被擦除次数大于某个阈值，这些块的数据将被将换到“冷池”中擦除次数最少的闪存块中。

比如NAND Flash一共有1 024个块，系统初始化时，给“冷池”分配序号为奇数的块，给“热池”分配序号为偶数的块如图1所示。“冷池”NAND Flash块表A和“热池”NAND Flash块表B分别包含512条表项，每个表现有32个字节，包含：块序号(4 Bytes)+擦除次数(4 Bytes)+有效页比例(4 Bytes)+修改时间(16 Bytes)+回收权值(4 Bytes)，则表A和表B大小分别为16 KB，一共32 KB。

图1 双池算法磨损均衡

以MLC颗粒的NAND Flash为例，假设每个块擦除最大次数为3 000次，设定降温阈值为2 000次。当系统扫描表B中第一个(块号m)擦除次数大于2 000的块时，系统扫描表A中擦写次数最小的块(块号n)，将块号m中的数据与块号n中的数据对换。

1.2 块搜索策略

双池算法搜索的块搜索策略采用的是排序算法，根据DP算法描述的一次“热块”降温过程，搜索时间包括扫描表A查找擦写次数最小的块时间开销+ 扫描表B查找第一个擦写次数阈值的块开销。

扫描表A或表B在空间复杂度最低并且排序稳定的前提下，查找或插入表A和表B中一个节点的最坏时间复杂度为O(N)，每次查找操作时间为10 μs。按照最大时间计算：DPT1=0.01 ms×512×2=10.24 ms。

1.3 垃圾回收策略

双池算法选用CAT[4]算法(Cost-Age-time Algorithm)作为垃圾回收策略。CAT算法的权重计算公式如下，选择权重最小的块进行回收。

(1)

式中:age表示此块最后一次修改的时间；u表示块有效页比例；CT表示块的擦除次数。

这种策略优点是综合考虑了块擦除次数、有效页比例、块最后一次修改时间等3个因素，垃圾回收效果较好；缺点是只考虑物理块最后一次修改时间，不能真实反映物理块年龄，同时对块表的更新操作及页的复制操作频繁，系统开销大。

双池算法占用的空间资源包括块信息表占用资源+块搜索占用资源+垃圾回收策略占用资源。其中块信息表占用资源包含所有块完整的信息，块搜索占用资源包含所有块的擦除次数信息，垃圾回收策略占用资源包含所有块的权值信息。按照最大空间复杂度计算：

DPS1=32 Byte×1 024+4 Byte×1 024×2=40 KB。

2 优先搜索树算法

2.1 算法原理

在优先搜索树(简称PST算法)中，每个树的节点由基索引和堆索引来标识。优先搜索树是一个依赖于基索引的搜索树，并附加一个类堆属性即一个节点的堆索引不会小于其子节点的堆索引，任意一个节点的左子节点基索引也都不大于右子节点基索引。

块节点(16 Bytes)=块序号(基索引4 Bytes)+擦除次数(堆索引4 Bytes)+有效页比例(附加信息4 Bytes)+回收权值(附加信息4 Bytes)。

比如NAND Flash一共有1 024个块，则整个索引表的大小为32 KB。系统初始化时，搜索算法从块序号为0的块按照块序号(即基索引)开始搜索，这个搜索树是个二叉树却是不对称的，如图2所示。

图2 优先搜索树算法

初始化完成后，所有节点扫描完成后形成二叉树Cm树。因此，根据这个二叉树磨均衡操作的过程就是不断从非对称向对称结构进行调整的过程。

2.2 块搜索策略

还是以MLC颗粒的NAND Flash为例，假设每个块擦除最大次数为3 000次，设定降温阈值为2 000次。当系统从Cm树块序号为0的块开始查找第一个擦除次数大于2 000 的NAND Flash块(块号p)，然后从Cm树块序号为0的块开始查找擦除次数最小的块(块号q)，将块号p中的数据与块号q中的数据对换，并根据擦除次数调整Cm树中节点p和q的位置。降温一个“热池”NAND Flash块数据开销：

PSTT1= 查找块p的时间+查找块q的时间

Cm二叉树查找或插入一个节点最坏时间复杂度为O(log2N)，每次查找操作时间为10 μs。

按照最大时间计算：

PSTT1=0.01 ms×log21 024×2 =0.2 ms

2.3 垃圾回收策略

基于优先搜索树的垃圾回收策略不再考虑每个块的最后一次修改时间，而是将当前块的擦除次数与最大擦除次数的差距作为考虑因素，权重计算如下：

(2)

式中：u表示有效页比例,CT表示当前块擦除次数，CTmax表示最大擦除次数。

这种策略减少了一个权重因子，公平地考虑擦除次数与有效页比例对于磨损均衡的影响，使得回收操作不受块更新时间因素的干扰，同时也减少了权重计算开销。

优先搜索树算法占用的空间资源包括块信息表占用资源+块搜索占用资源+垃圾回收策略占用资源。其中块信息表占用资源包含所有块完整的信息，块搜索占用资源包含所有块的擦除次数信息，垃圾回收策略占用资源包含所有块的权值信息。按照最大空间复杂度计算：

PSTS1=16 Byte×1 024+4 Byte×1 024×2=

24 KB。

2.4 算法比较

相对于DP算法的耗费的系统资源、时间开销也大为降低，如表1所示。

表1 算法比较

3 实验分析

本文使用FlashSim[5]实验平台对设计的算法进行性能分析。

3.1 实验环境

FlashSim是一款开源的、事件驱动的、模块化的基于C++的SSD模拟器，内置了多种FTL策略，能够提供响应时间、能耗的模拟及许多额外的统计信息。

FlashSim分为两部分，软件部分和硬件部分。硬件部分模拟SSD固态盘，其内部结构与SSD的实际结构有着很好的映射关系。FlashSim模拟器硬件部分由处理器、RAM、总线和flash芯片组成如图3所示。

图3 FlashSim模拟器硬件结构

设置FlashSim模拟器硬件部分Nand flash芯片参数如表2所示。

FlashSim模拟器软件部分模拟FTL功能，运行在调试电脑Ubuntu 10.04的Linux系统上，整个实验平台如图4所示。

图4 实验平台

设置FlashSim模拟器软件部分实验参数如表3所示。

表3 实验参数

3.2 实验数据

为了模拟出真实环境下的算法性能，输入文件的选择主要来源于企业级宽频谱的工作负载[6]。我们采用了两种测试文件，分别是Financial、Web search。这两种负载文件特性如表4所示。

表4 实验数据

对于Financial文件数据，是以写为主，具有很强的时间局限性，对于Web search，其主要是读操作的踪迹数。通过下载的测试源数据包，其中有两份Financial测试数据(分别称为F1、F2)和三份Web Search测试数据(分别称之为W1、W2、W3)，对于这五份数据都作为实验的测试数据源。