NAND损耗均衡综述

         现在随着手机，pad等等移动终端的爆发，NAND因为其非易失性、高性能、体积小等等优势成为移动终端首选的存储设备，现在NAND的市场基本被Samgsung,Toshiba,Hynix以及Micron所占领。随着移动设备对于高屏幕分辨率、高清视频、无损音乐的需求，对于NAND闪存的容量及速度要求进一步提高了。

         随着微细化的发展，NAND闪存的容量和速度也在增加，但是同时带来了一些负面的影响。微细化导致存储每比特数据所需的电子数减少，使得发生位反转(bit-filp)的几率提高，所以现在很多MLC类型的NAND闪存对于ECC的纠错都有最基本的要求。下图是Hynix的H27UBG8T2A对于第5位ID的说明：

微细化带来的第二个不利的影响是使得NAND闪存的寿命降低，从最初SLC的10万次降低到了MLC现在的1万次甚至几千次。

         我个人认为在未来一段时间内，NAND控制器的ECC模块和文件系统中的均衡损耗会成为NAND研究的两个主要方面。从苹果公司收购以色列闪存组件制造商Anobit这件事就可以看出一点端倪。

从根本上来分析的话，损耗管理策略一共分为两种类型：动态损耗均衡和静态损耗均衡。动态损耗均衡策略管理所有可用的空闲块，选择擦除次数最少的块用于下一次写操作。静态损耗管理则管理所有可用的可擦除块（空闲块、包含数据的数据块以及脏块），试图平衡所有可用块的损耗。当包含静态数据的可擦除块的擦除次数变的落后于其余块时，就需要启动一次数据搬运，将静态数据搬运到损耗严重的块中去。

损耗管理策略	优点	缺点
动态	1.最大化芯片寿命 2.健壮性强 3.更加有效的使用内存空间	1.控制器需要更多的开销 2.可能降低写性能 3.功耗大 4.实现比较复杂
静态	1.对于性能影响较低 2.比动态损耗管理实现比较简单	1.可能不会延长芯片寿命

Logfgren等人于2000年提出了一种简单的损耗管理机制，是由回收可擦除块触发的。在这种技术下，每一个可除块的头部管理信息中都包含一个擦除计数值（Erase counter）。当系统中损耗比较严重的可擦除块B被回收时，它的擦除计数值与系统中损耗最小的可擦除块A的计数值进行比较，如果其差值超过某一个预定阈值，那么就启动一次损耗迁移(wear-leveling relocation)。将损耗较小的擦除块A中的数据迁移到其余块中，同时将损耗严重的数据块B中的内容迁移到刚刚擦除的损耗较小的块 A中，最后将损耗严重的块回收。该损耗管理机制试图标识损耗严重的块和静态数据，然后将静态数据保存在这些损耗严重的可擦除块中。当然前提是假设损耗较小的块中的数据相对静态，将它们保存在损耗严重的可擦除块中可以降低这些可擦除块被回收的几率。将静态数据从损耗较小的可擦除块中迁移出去，可以提高这些可擦除块将来被回收的几率。

       很显然，任何依赖于擦除计数值的技术都受到断电的影响。如果系统在一个可擦除块刚刚被擦除但是还没有写入新的计数值时掉电，那么该可擦除块的计数值就会丢失。擦除操作越缓慢，这种风险就越高。

Marshall和Manning于早在1998年提出了一种来规避这种风险，将每一个可擦除块的计数值保存在另外一个可擦除块中。他们的系统在每一个可擦除块的头部保存一个擦除计数值。在回收某一个块i之前，该计数值会被拷贝到另外一个块j（j不等于i）中特别标记的部分。如果在回收的过程中掉电，块i的计数值也可以在系统重启后从块j中恢复出来。Assar等人于1996年发明了一种简单但是相对而言不太有效的方法，他们建议将一个可擦除块i的8比特的计数值保存在另外一个块j中。当可擦除块i每被擦除一次，计数值就被清除一位（注意Flash擦除中可以数据可以由1变为0，但是不可以由0变为1），因此保存在块j中的计数值可以不需要擦除而就得到更新。但是该技术并不能准确的评估系统中的每一个物理可擦除块的损耗情况，因为这些计数值会重新退回到某些状态（仅仅只有几个比特位）。

Jou和Jeppesen于1996年发明了一种技术一个具有上限的擦除计数值的方法，这个上限是正确但并不严格的。系统采用一种写前擦除的策略(earse before write)：当一个可擦除块被选中回收时，其中的内容被拷贝到另外一个块中，但是该块并不立即擦除，它被标记为候选擦除块，然后添加到内存中的链表中去。这个链表是根据可擦除块的擦除计数值来排列的。当系统需要一个空闲块时，这个链表中擦除计数值最少的可擦除块被选中擦除。如果在擦除的过程中系统掉电，该块的计数值就被设置为链表中计数值最小值。虽然这个计数值并不能准确的反映当前块的情况，但是从整体损耗评估的角度而言它是正确的，该技术通过延迟损耗严重块的擦除操作来平衡损耗。但是这种平衡性取决于系统中过剩块的数目，如果数目太少，损耗严重块的擦除并不能被延迟太久。

       Han于2000年提出了另外一种技术来解决该损耗问题，他利用擦除时间来进行损耗的评估，在一些Flash存储设备上，随着损耗的增加，擦除时间变得越来越长。Han的技术通过比较擦除时间来划分损耗等级。这种技术同时也避免了在内存保持擦除计数值。这种技术可以被用在数据迁移和空间分配中。由于没有详细的擦除计数值，系统只能在一个块被擦除之后才能评估它的损耗情况。但是该技术这种单纯的模式（没有擦除计数值）似乎没有太多的适用性。

       另一种解决损耗均衡的方法依赖于随机性而不是损耗的评估。Wood house于2001年提出了一种简单的随机优化的损耗管理技术。系统每进行100次垃圾回收就回收一个全部为有效数据的可擦除块（也就是每回收100个可擦除块，就进行一次数据迁移）。该技术有利于将损耗较小的块中的静态数据转移到损耗严重的可擦除块中。一旦该技术用于系统中，其对于回收有效性的影响要大于对损耗的影响。损耗不平衡现象仍然会发生。根据可擦除块中包含有效数据来进行候选回收块的选择，会使得一些含有少量有效数据的损耗较小块永远得不到回收。

       与此同时，Ban于2004年发明了一种健壮性更好的技术，他的技术类似于Lofgren，依赖于保留数据块。每一定数量的可擦除块被回收之后，系统随机的选择一个擦除块，将其中的内容搬运到保留数据块中，然后将这个可擦除块标记为新的保留块。这个均衡事件的触发可以是事前设置好的，比如每擦除1000次，也可以是随机的。随机时间触发可以保证即使只有少量的块被擦除时仍然会触发均衡事件。该技术的目的是使得系统中每一个块都可以得到公平随机的数据交换。这样的数据交换可以较少每一个块保持静态数据的时间。此外在这种技术下，整个系统的损耗是可以预期的。

 

参考文献：

1.Special issues in Flash  Special Issues in Flash.pdf   

2.Wear-leveling in Micron NAND Flash Memory Wear-leveling in Micron NAND flash Memory.pdf   

3.Algorithms and Data structure for Flash Memoies Algorithms_and_Data_Structures_for_Flash_Memories.pdf  

4. Wear-leveling techniques in NAND flash devices