一种基于逻辑页平均更新频率的NAND闪存垃圾回收算法

NAND闪存具有体积小、抗震性能好、功耗低、无运行噪声、存取速度快、便携性好等特点，同时还具有远超传统机械硬盘的读写速度。因此，NAND闪存在各种电子产品中被广泛应用，如手机、U盘、固态硬盘[1-5]。

NAND闪存具有如下特点：

(1)NAND闪存的读写操作以页(page)为单位，擦除操作以块(block)为单位。NAND闪存的写操作耗时远大于读操作，擦除操作耗时远大于写操作。

(2)NAND闪存具有“写前擦除”的特点，即在进行重复写操作之前，必须先对写入的存储区进行擦除操作。

(3)NAND闪存具有“异地更新”的特点。NAND闪存在对一个页进行数据更新时，需要先将要更新的数据写入新的空闲页，然后将原数据页标为无效页。

(4)NAND闪存具有有限的块擦除次数。当某个块的擦除次数超过一定值时，该块将无法进行数据存储，成为“坏块”。

NAND闪存中，会根据情况启动回收块选择策略，对满足回收块选择策略要求的块进行擦除操作，用以回收无效页所占的存储空间，得到足够的空闲空间来进行数据更新操作。

在设计垃圾回收算法时应将减少垃圾回收代价、提高垃圾回收效率作为主要考虑点。同时，还要尽可能使每个物理块均衡地参与到擦除操作中，从而提升闪存磨损均衡程度、延长使用寿命。

MICHAEL W等提出了GR(Greedy)算法[6]。GR算法选择有效页最少的块进行回收。该算法的拷贝代价小，可回收较多的无效页空间。其特点是算法实现简单，回收效率较高。然而，当且仅当文件更新频率均匀时，磨损均衡效果较好。若数据更新频率相差较大，块之间的擦除次数差别较大，磨损均衡效果较差。

KAWAGUCHI A等提出了CB(Cost-Benefit)算法[7]。该算法采用age×(1-u)/2u公式进行回收块选择，其值最大的块将被选择成为回收块。其中u表示有效页在单个块中的比例，即物理块更新的时间差，age表示块的年龄。该算法考虑了块的年龄，因此获得比GR算法更好的效果。

CHIANG M L等提出了CAT(Cost-Age-Times)算法[8]。该算法采用age×(1-u)/(2u×n)公式进行回收块选择。其中u表示单个块中的有效页比例，age表示块的年龄，n表示块擦除次数。该算法在CB基础上考虑了块擦除次数，比CB具有更好的磨损均衡效果。

Yan Hua等提出了FaGC(File-aware Garbage Collection)算法[9]。该算法沿用GR算法的回收块选择策略，且根据逻辑页更新频率进行冷热数据的划分。数据冷热分离时，冷数据分配到擦除次数最多的块，而热数据则分配到擦除次数最少的块。

石乐健等提出了一种基于物理块年龄和逻辑页热度的磨损均衡算法GCbAH(GC based Age and Hot)[10]。该算法选择无效页年龄和最大的块作为回收块。同时，采用了与FaGC不同的热度计算公式来进行冷热数据的划分。在回收时，使用热数据回收策略回收热块，使用冷数据回收策略回收冷块。

综上所述，相较于GR、CB、CAT等经典算法，FaGC和GCbAH考虑了逻辑页的冷热分离，进一步减少了垃圾回收代价，取得了更好的磨损均衡效果。但是，FaGC和GCbAH均采用固定的预设阈值来作为判定冷热数据的标准，并不能准确反映逻辑页的冷热程度。针对这个问题，本文提出了一种基于逻辑页平均更新频率的闪存垃圾回收算法AUFbGC(Average Update Frequency based Garbage Collection Algorithm)。该算法采用了一种新的热度计算公式，并采用逻辑页平均更新频率取代固定阈值作为冷热数据的判定依据，取得了更好的效果。

1 算法描述

1.1 算法原理

NAND闪存进行垃圾回收时有如下操作：

(1)根据回收块选择策略，进行回收块选择；

(2)拷贝回收块中的有效数据至空闲块；

(3)将被拷贝的有效数据所对应的原数据页标记为无效页；

(4)对选中的回收块进行擦除操作；

(5)回收块被擦除后成为空闲块。

如图1所示，AUFbGC算法选择无效页年龄和最大的块作为回收块，根据热度计算公式和新的冷热判定依据，对回收块的有效数据进行冷热分离，并将有效数据存入擦除次数最少的空闲块中。

和垃圾回收过程类似，AUFbGC算法在进行数据异地更新时也采用了冷热分离策略以获得更好的磨损均衡效果。

AUFbGC算法主要包括三种策略：回收块选择策略、冷热数据分离策略和空闲块分配策略。

1.2 回收块选择策略

AUFbGC算法在挑选回收块时有两种策略：采用无效页年龄和选择策略[10-11]和自适应最冷块选择策略[9]。

其中，n为物理块中的无效页数目，agei为物理块中第i页变为无效页的时长。CwA即物理块中无效页的年龄和。CwA值最大的块将被选择成为回收块。采用年龄和进行选择可以兼顾无效页比例高的块和有少量无效页但长期未被回收的块，可获得更好的磨损均衡效果。

同时，算法采用一种自适应策略对最冷块进行回收。自适应最冷块回收策略启动条件如下：

其中，Twl是先前被设置好用于控制磨损均衡程度的阈值，emax是所有块的最大擦除次数，emin是所有块的最小擦除次数。当emax和emin之间的差值增大，Terase值越小，冷块选择策略越容易被调用。若Terase值小于零，则将Terase置零。当一个块的擦除次数超过Terase值时，最冷块回收策略被调用。该策略将选择有最小擦除次数的块作为回收块，以增加选中有较低更新频率的逻辑页的块的几率。如果有多个块具有最小擦除次数，则选择其中含有最少有效页的块作为回收块。在每次冷块回收策略被调用时，Terase值会被计算和更新。

1.3 数据热度定义

在热度判定上，FaGC以更新频率作为判定数据热度的标准，大于预先设置的特定阈值则为热数据，反之则为冷数据。

GCbAH通过上一次判定的热度与热度调节因子相乘作为本次热度的计算标准。当逻辑页两次更新操作的时间差值大于特定值时，逻辑页热度被强制归零，因此不能细分部分数据的冷热程度。此外，GCbAH也采用预先设置的特定阈值作为判断冷热数据的标准。

AUFbGC算法采用更新频率作为衡量冷热数据的指标[12]，每个逻辑页的更新频率可通过如下公式进行计算。

其中，CurrentT是当前时间，IWTi是该逻辑页i的初始写入时间。UPDCi是逻辑页i的更新次数。因此，FREQi代表逻辑页i写操作的更新间隔。

衡量冷热数据的标准如下：

其中，n是物理块的总数，CurrentT是当前时间，AllocT是编号为i的块被分配使用时的时间，ui是该块中有效页的百分比。因此AverFi代表有效页的平均更新频率。而每当回收块选择策略选中回收块后，平均更新频率AverFi会被立刻计算。

当逻辑页的更新频率FREQi小于平均更新频率AverFi，则该逻辑页包含的数据是为热数据；当逻辑页更新频率时间FREQi大于平均更新频率时间AverFi，则为冷数据。

1.4 算法步骤

使用无效页年龄和与自适应最冷块回收策略选择到回收块之后，根据回收块中有效页对应的热度对数据进行冷热分离，具体步骤如下：

(1)根据逻辑页i的当前更新时间CurrentT和初始写入时间IWTi及更新次数UPDCi，根据式(3)得到该逻辑页的更新频率FREQi。

(2)若逻辑页的更新频率FREQi小于平均更新频率AverFi，则该逻辑页包含的数据为热数据；反之则为冷数据；

(3)将数据根据热度进行冷热分离，具有相似热度的有效页将会被存入同一个物理块；

(4)修改更新次数UPDCi，用于下一次热度的计算和更新操作。

2 实验及分析

2.1 实验环境

实验中使用VMware和Ubuntu 12.04平台，使用QEMU搭建嵌入式Linux仿真环境，使用NANDSim来模拟NAND闪存，基于NAND闪存专用文件系统YAFFS2进行测试。

测试程序随机生成16 KB到1 024 KB大小的测试文件，所有测试文件总量占NAND闪存容量的90%。创建文件后，按照齐夫分布[13]对其中15%的文件进行更新操作。

实验中，NAND闪存容量被设置为64 MB，包含512个物理块，由512×64个页组成，其中每个页为2 048 B。为了公平对比不同算法，实验时YAFFS2文件系统的缓存功能被关闭，且都采用aggressive模式以完成垃圾回收。自适应最冷块回收策略采用的阈值和FaGC、GCbAH算法完全一样。

2.2 算法性能分析

本文将AUFbGC算法与GR、CB、CAT、FaGC及GCbAH算法在垃圾回收代价和磨损均衡效果两个方面进行了比对。其中，垃圾回收代价主要考虑块总擦除次数、页总拷贝次数这两个指标，磨损均衡效果主要考虑块最大最小擦除次数差值、块擦除次数标准差这两个指标。同时，通过擦除次数分布图也可直观地观察不同算法的磨损均衡效果。

从图2和图3中可以看出FaGC、GCbAH和AUFbGC算法获得了相对更小的块总擦除次数和页总拷贝次数。这是由于GR、CB、CAT算法中未考虑冷热数据分离，而FaGC、GCbAH和AUFbGC考虑了较为准确的基于逻辑页的冷热分离。在这三种算法当中，FaGC和GCbAH在数据热度进行定义时，均通过与事先设定的阈值进行比较，以划分冷热数据。AUFbGC算法有更准确的热度计算公式和判据，可将热度相近的逻辑页更加准确地放在同一个空闲块中。由于热度相近，这些逻辑页有更大可能同时被更新而变为无效，从而使该数据块有尽可能少的有效页，最终减少有效页拷贝次数和块擦除次数。

在磨损均衡方面，从图4对比中不难看出，GR算法的物理块擦除次数最为分散，CB、CAT算法次之。FaGC、GCbAH和AUFbGC算法相对集中地分布在一个较小区域。其中，AUFbGC算法得到了较为良好的磨损均衡效果，擦除次数分布集中，且分布在较低值。

不同算法的块最大最小擦除次数差值如图5所示，不同算法的擦除次数标准差如图6所示。从图5和图6中可以得出，FaGC、GCbAH和AUFbGC算法在磨损均衡方面相对GR、CB、CAT有更优异的表现。一方面，FaGC、GCbAH和AUFbGC算法获得了远小于GR、CB、CAT算法的块最大最小擦除次数差值；另一方面，这三种算法的擦除次数标准差呈收敛趋势。这是因为GR算法仅考虑回收有效页最少的物理块，未考虑磨损均衡。尽管CB算法考虑了物理块的年龄和有效页的比例，CAT算法在CB算法的基础上增添了块擦除次数的考量，但CB、CAT算法既没有考虑冷热数据分离，对最冷块的回收也不及时。FaGC、GCbAH和AUFbGC算法均采用了冷热数据分离和自适应最冷块回收策略，因此取得了更好的磨损均衡效果。同时，在这三种算法中，FaGC在回收块选择策略上沿用了GR算法，而GCbAH和AUFbGC算法的无效页年龄和回收块选择策略可兼顾对无效页比例高及无效页比例不高但是很长时间未被回收的物理块的回收，让回收块的选择更加均衡。相较于GCbAH算法，AUFbGC算法在定义数据热度时采用动态变化的平均更新频率取代固定阈值作为比较标准，对冷热数据的划分更准确，分类效果更好，且AUFbGC算法不断地将有效数据分配至擦除次数最少的块，以减少不同块擦除次数的差异。因此，AUFbGC算法的磨损均衡效果最好。

3 结论

针对NAND闪存的特点，提出一种基于逻辑页平均更新频率的NAND闪存垃圾回收算法AUFbGC。该算法在FaGC和GCbAH算法基础之上，重新定义了数据热度计算公式和冷热判断依据。实验结果表明，相较于GR、CB、CAT、FaGC和GCbAH算法，AUFbGC算法在NAND闪存垃圾回收代价和磨损均衡方面均取得了更好的效果。

参考文献

[1] KIM J，KIM J M，NOH S H，et al.A space-efficient flash translation layer for CompactFlash systems[J].IEEE Transactions on Consumer Electronics，2002，48(2)：366-375.

[2] 白石，廖学良，胡事民.HFB:一种闪存上的块页混合缓存管理方法[J].清华大学学报(自然科学版)，2012(5)：688-693.

[3] CHEN R，LIN M.Energy-aware buffer management scheme for NAND and flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics，2015，61(4)：484-490.

[4] JIN X，JUNG S，SONG Y H.Write-aware buffer management policy for performance and durability enhancement in NAND flash memory[J].IEEE Transactions on Consumer Electronics，2010，56(4)：2393-2399.

[5] LEE S，JUNG S，SONG Y H.An efficient use of PRAM for an enhancement in the performance and durability of NAND storage systems[J].IEEE Transactions on Consumer Electronics，2012，58(3)：825-833.

[6] WU M.The architecture of eNVy，a non-volatile, main memory storage system[C].The Workshop on Workstation Operating Systems.IEEE，1994：116-118.

[7] KAWAGUCHI A，NISHIOKA S，MOTODA H.A flash-memory based file system[C].USENIX 1995 Technical Conference Proceedings.USENIX Association，1994：13-13.

[8] CHIANG M L，CHANG R C.Cleaning policies in mobile computers using flash memory[J].Journal of Systems & Software，1999，48(3)：213-231.

[9] Yan Hua，Yao Qian.An efficient file-aware garbage collection algorithm for NAND Flash-based consumer[J].IEEE Transactions on Consumer Electronics，2014，60(4)：623-627.

[10] 石乐健，严华.考虑物理块年龄和逻辑页热度的NAND闪存磨损均衡算法[J].小型微型计算机系统，2015，36(11)：2618-2621.

[11] KWON O，KOH K，LEE J，et al.FeGC：an efficient garbage collection scheme for flash memory based storage systems[J].Journal of Systems & Software，2011，84(9)：1507-1523.

[12] HWANG S H，CHOI J H，KWAK J W.Migration cost sensitive garbage collection technique for non-volatile memory systems[J].IEICE Transactions on Information & Systems，2016，99(12)：3177-3180.

[13] LIN M，CHEN S.Efficient and intelligent garbage collection policy for NAND flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics，2013，59(3)：538-543.

作者信息：

黄敏媛，严 华

(四川大学 电子信息学院，四川 成都610065)

3D闪存只讲堆叠层数不谈制程工艺的背后

在我们打开一个固态硬盘的产品信息页面时，总是能看到"采用3D NAND闪存"这样的介绍。大家是否想过，为什么3D结构会取代制程微缩成为闪存的发展方向？

15nm制程成为2D与3D闪存的分水岭，在15nm之后闪存不再像CPU那样继续向更先进的10nm、7nm制程迈进。是什么样的原因使得更先进的半导体制程与NAND闪存无缘？现在的3D闪存到底又是什么制程节点制造的？

TLC转折点

各种闪存新技术的出现，本质上都是为了降低每GB容量的成本。NAND闪存相比内存有一个优势，它在一个单元里可以存储多个比特(bit)的数据。这是制程微缩之外的另一种扩容量、降成本手段。当发展到TLC（3bit/cell）后，遇上麻烦了。

闪存单元的FG浮栅结构就像一个可以存储电子的桶，其中容纳的电子数量会影响到闪存单元的读取阈值电压Vth。在TLC中为了表达3比特数据已经需要用到8种不同的阈值电压，如果发展到QLC的4bit/cell结构，更需要区分出16种阈值电压，这就像蝇头小楷一样难以看清。

电子危机

制程微缩的过程进一步加剧了闪存危机，新制程的FG浮栅结构中能容纳的电子总数不断下降，发展到一个非常危险的水平。下图中的红线是过去BCH纠错技术下的可用界限，除非改变闪存结构，否则制程微缩将难以为继：制造出的闪存单元会因为能够容纳的电子数量太少而极其容易出错。

3D闪存架构提出

3D闪存就是攻城狮们找到的新结构出路。早在2007年，东芝就首次提出BiCS三维闪存结构，成功地解决了当代的发展难题。目前市场上在售的固态硬盘几乎全部使用了3D闪存。

3D闪存并不是简单地把闪存单元从平面堆叠成立体状态，而是涉及了基础的结构变化。下图为东芝BiCS三维闪存与传统平面闪存的结构对比。

最终结果使得闪存单元之间的间隙变大、读写干扰得到降低。同时，Charge Trap取代了传统的Floating Gate结构，有力地提升了闪存单元"抓住"电子的能力，降低了漏电速度。

3D闪存的制程信息

很多地方说3D闪存之所以更耐用，是因为使用了更老的制造工艺。这一点其实只适用于初代的3D NAND，40nm的制程使得初代的3D闪存非常昂贵，没有达到扩容量、降成本的初衷。

尽管闪存原厂都不再透露3D闪存的具体制程信息，TechInsights的分析报告还是给出了我们想要的答案：目前的64层堆叠、96层堆叠技术使用的都是19/20 nm制造工艺。

3D闪存的未来

现在3D闪存已经在固态硬盘当中大为普及，未来还会有4D闪存吗？其实4D概念去年就有闪存厂商提出，不过"4D"只是将闪存中的外围电路拿出来，置于存储单元阵列的下方，属于3D工艺的一个小改进。

目前的主流3D闪存拥有64层堆叠层数，东芝在去年率先宣布96层3D TLC。在即将到来的下个节点是96层堆叠与QLC的结合，东芝的96层BiCS4已实现1.33Tb/die的存储密度，如果以8die封装来计算，每个闪存颗粒就可以提供高达1.33TB的海量存储空间，手机和固态硬盘的容量即将迎来又一次爆发式增长。

相关问答

NAND闪存NANDFLASH的中文翻译为nand闪存。

NAND闪存是一种比硬盘驱动器更好的存储设备,在不超过4GB的低容量应用中表现得尤为明显。随着人们持续追求功耗更低、重量更轻和性能更佳的产品,NAND被证明极具...

3DV-NAND这是作为闪存芯片(NAND)制造的新技术,3DV-NAND主要从结构方面对闪存芯片进行了改进。在之前的闪存芯片中,采用的都是2D平面设计的存储单元(Cell)...

这问题也能问的出来,不就是成本降低了嘛。这问题也能问的出来,不就是成本降低了嘛。

来自瑞士的电动车近日,瑞士电动车制造商Microlino宣布他们已经开始新一阶段的测试工作。他们称,该车正在测试全新的Microlino2.0平台以及改进过的悬挂系统...

NAND是闪存芯片,掉电后数据不会消失DRAM用于内存,掉电后数据会丢失,速度快NAND是闪存芯片,掉电后数据不会消失DRAM用于内存,掉电后数据会丢失,速度快

SDXC规范仍然基于NAND闪存技术,这主要是由于NAND闪存拥有增大页容量的功能(NAND闪存的读取写入的容量单位都是“页”),因为NAND闪存的工作原理是闪存页的容量越...

3DNAND是相较于2DNAND而言的,而2DNAND其实也就是闪存颗粒,又称闪存,是一种非易失性存储器,即在断电的情况下依旧可以保存已经写入的数据,而且是以固定的区块...

分别是单层存储单元(没个单元只存储1bit的数据),多层(其实也就是双层)存储单元,三层存储单元。slc存储速度最快,可擦写次数最多,成本最高,三者依次...

U盘闪存总量,就是你这个U盘的真实的总容量。闪存就是U盘的介质,U盘的更正式一些的名称应该叫“闪存盘”。所以,闪存总量,就是U盘的总容量。真实的总...