一种基于逻辑页平均更新频率的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)
为什么固态硬盘恢复数据比较困难
固态硬盘恢复数据比较困难，主要是由于其独特的存储机制和数据管理方式，以及可能遇到的各种数据丢失原因。以下是对这一问题的详细分析：
一、存储机制差异
固态硬盘（SSD）与机械硬盘（HDD）在存储机制上存在显著差异。SSD使用NAND型闪存作为存储介质，数据以电荷的形式保存在半导体上。这种存储方式决定了SSD在数据恢复方面的固有难度：
电荷易失性：SSD中的数据存储在闪存单元中，当单元损坏时，电荷即消失，无法像HDD那样通过物理方式找回数据。
异地更新与闪存疲劳：SSD在写入数据时采用“异地更新”机制，频繁的擦除和重写操作会加速存储单元的磨损，导致“闪存疲劳”，进而增加数据恢复的难度。
二、数据管理方式
SSD的数据管理方式也增加了数据恢复的复杂性：
TRIM命令：为了提高性能和延长闪存的使用寿命，现代操作系统会使用TRIM命令通知SSD哪些数据块已经不再有效，可以擦除以便重复使用。一旦这些数据块被清除，原有的数据就难以恢复。
加密功能：许多SSD具备加密功能，以保护数据不被未授权访问。如果启用了加密，即便物理取出闪存芯片也无法直接读取数据，因为解密密钥通常存储在控制器中。
三、数据丢失原因多样
SSD数据丢失的原因多种多样，包括硬件故障、人为误操作、病毒攻击等，每种原因都可能导致不同的数据恢复难度：
硬件故障：如闪存芯片、主控芯片等硬件部件出现故障，可能导致硬盘无法正常读取和写入数据。这种情况下，数据恢复通常需要专业的硬件修复技术和设备。
人为误操作：如误删除、格式化等操作，虽然相对于硬件故障来说恢复难度较低，但仍需要专业的数据恢复软件或工具来辅助完成。
病毒攻击：病毒会破坏硬盘中的文件系统或加密数据，导致数据无法被正常访问。这种情况下，数据恢复需要先清除病毒并修复受损的文件系统或解密数据。
四、专业恢复服务的重要性
鉴于SSD数据恢复的复杂性，普通用户很难自行完成数据恢复工作。因此，在SSD数据丢失时，建议寻求专业的数据恢复服务。这些服务通常具备先进的硬件和软件设备以及专业的技术人员，能够针对不同类型的数据丢失原因提供有效的恢复方案。
固态硬盘恢复数据比较困难主要是由于其存储机制、数据管理方式以及数据丢失原因的多样性等因素共同作用的结果。在遇到SSD数据丢失问题时，建议保持冷静并尽快寻求专业的数据恢复服务。
相关问答
石家庄的县级市新乐市未来发展前景怎样?以下内容来自手机互动百科新乐市以下内容来自手机互动百科,版权归互动百科所有。新乐市是河北省石家庄市县级文化经济强市,为河北省重要的经济、文化、政治...
存储芯片和存储控制芯片哪个更强势?其实,我并没有理解强势的含义,不知道提问者想表达的是优势还是厉害的意思,姑且就按照优势来说吧。存储控制芯片主要是给存储芯片加上了一个控制芯片,所以说...
三星,索尼,夏普,LG.哪个屏幕更好?-ZOL问答硬件王者当然是三星啦,苹果的机芯和nand就是三星做的,LG的视网膜屏幕也是独家供...去外地几天抖音IP会更新吗?8050浏览8回答OPPOR9splus手机照片被删了,近来...
扫一扫微信交流