NAND Flash管理算法的设计及实现

O 引言
    Flash是一种非易失存储器，它在掉电条件下仍然能够长期保持数据。由于它具有容量大、速度快、功耗低、抗震性能好等优点，近几年在U盘、SD卡、SSD硬盘等各种移动存储设备中得到了广泛的应用。本文给出了一款性能优异、成本低廉可用于SD卡的NAND flash控制芯片的设计方法。(本方法也同样适用于其他存储设备。文中集中探讨了一种高效管理物理块的算法，包括逻辑物理地址映射以及spare区的定义，另外，还有双缓冲器优化读写的方法等。

1 Flash简介
1．1 SLC flash与MLC flash的比较
    从架构上，flash可以分为SLC(Single-Level-Cell) flash和MLC(Multi-Level-Cell)flash两种。和SLC Flash相比较，MLC flash的优点是面积小、成本低：缺点是出错率高，寿命短(SLC的每个block能够擦写100，000次，而MLC能够擦写10，000次)。由于MLC flash具有成本低的优势，而其出错率高的缺陷又可以通过ECC(Error Correction Code)纠错来有效解决，寿命短的问题也可以通过磨损均衡来弥补，因此，MLC flash的应用更加广泛，但在一些高端应用仍然会使SLCflash。本设计就是针对MLC flash，但是，本方法对SLC flash也能够处理。
1．2 NAND flash结构
    不同厂商不同型号的flash的结构都大同小异，图l所示是三星K9G8G08UOA型号的flash结构图，图l中的1个flash芯片包含4096个物理块(block)，每个物理块含有128个页(page)，每个页包含2112(2048+64)字节其中多出的64字节用于存放纠错码及其他信息用。

1．3 NAND flash的特点
    Flash可支持读(Read)操作、写(Program)操作和擦除(Erase)操作。其中读操作和写操作的基本单位是页，擦除操作的基本单位是块。对flash的写入操作只能在尚未写入的空闲页上进行，并且只能按照从低地址页到高地址页的顺序进行操作，而不能写了高地址页之后，再写低地址页。如果想要修改某个已经写过的页，只能先对整个物理块进行擦除，然后才能正确写入。

2 Flash管理算法
2．1 逻辑物理地址映射
    由于flash具有上述特点，因此，如果不采用逻辑物理地址映射，将会存在两个问题：其一是Flash中难免会有坏块，因而某些地址空间将是不可用的；其二，Flash读写的基本单位是页，擦除的基本单位是块，故在同一个页的两次写之间，就必须要进行一次擦除操作，而擦除会擦除掉整个块，这样，为了避免其他页的数据丢失，就得先把这些页中的数据暂存到其他地方备份起来，之后再和新数据一起重新写回到该块中，因此，整个过程会比较复杂，而且会造成速度降低。这样，一般都需要对flash加入逻辑物理地址映射管理算法，该算法的逻辑地址和物理地址的对应关系是变动的。
2．2 两级地址映射
    为了减少更新数据时原有数据的搬移，提高写操作的速度，本文提出了采用两级地址映射的机制，也就是在块级别逻辑物理地址映射的基础上引入页级别上的逻辑物理地址映射。一个逻辑块对应一个或两个物理块(称为母块和子块)，逻辑块中的逻辑页对应一或两个物理块中的某个面。图2所示是其地址解析示意图。

    在读写时，首先应将逻辑地址分为逻辑块地址和逻辑页地址，再根据块映射表将逻辑块地址映射到物理块地址，然后读取母块和子块中的sDare区，并据此建立页映射表，再根据逻辑页地址映射到物理页地址，从而完成从逻辑地址到物理地址的转换。其数据更新示意图如图3所示。

    当需要更新数据时，写入的策略可分为两种情况。首先，当子块仍然有空闲页时，可直接将数据写到子块中的下一个空闲页中，并在spare区中记录该块对应的子块、该物理块对应的逻辑块以及该物理页对应的逻辑页，这样，当重新上电时，就可以建立逻辑物理映射关系。其次，当母块和子块都写满时，需要从空块池中取出一个新的子块。如果允许一个逻辑块对应三个或更多的物理块，一方面管理起来比较复杂，另外也会造成空物理块紧缺，因此，可以考虑将母块或者子块释放掉，这样，母块或者子块中原有的有效数据就需要搬移到新子块中并将该母块或子块擦除再释放到空块池。出于速度的考虑，选择母块和子块有效页数较少的块进行数据转移并释放。
    实践证明，这样操作对写文件速度有明显提高，特别是写小文件时，其速度提升可达9．2倍。
2．3 SPARE区和ECC校验
    Flash中每个页里的每个字节都是没有任何差别的，物理上并没有data区和spare区的区别，具体怎样划分data区和spare区，可由用户自己决定。本设计采用的划分办法如图4所示，这样，每个扇区和一个spare区相连，故可方便连续读出，并进行校验纠错。

    图4中同时给出了Spare的区定义，其中两字节用于标识本物理块所对应的母块；两字节用于标识本物理块对应的逻辑块；一字节用于标识本物理页对应的逻辑页，一字节用于标识连续逻辑页数(表示上面连续逻辑页的个数，此域可以辅助加快建立页映射表的时间)，余下的10字节用于存放ECC，这样可以达到4字节错误的纠错能力。一般情况下，前面的4个字节是建立块地址映射表的关键，其次，后面两个字节则是建立页地址映射表的关键。
2．4 页映射表建立时间的优化
    因为建立页映射表需要读取母块和子块中各物理页spare区以判定该物理页对应的逻辑页，而每个物理页的读取都要花费大约50μs的时间。因此，如果对每个物理页都读取，建立页映射表就会比较费时。为了加快建立页映射表的速度，一般只希望能读取一个物理页，而免于读取其他若干页，以便加快建表速度。因为很多时候都是连续写，而连续的几个物理页在逻辑上也是连续的，因此可以考虑在spare区加入连续逻辑页号，这样，重新建表时，就可根据连续页号知道连续几个物理页对应的逻辑页，从而加快建表的速度。对于最佳情形，有时只需要读一个页就可以建立整个逻辑块的页映射表。图5所示是一种加快建表的示意图。

2．5 分区
    不同的flash，块数是不同的，其块映射表需要的RAM空间也不一样。对于当前主流flash，有的具有8192个块，如果对整个flash建表，需要的RAM空间将多达32KB，这样芯片成本就会比较高。一个可行的解决办法是对flash分区，比如1024个块为一个分区，每次只对一个分区进行建表，这样，RAM空间就可以降低到4KB。这样，随着将来flash容量的增加，块数即使再多，也能够用同样的方法处理，而不用增大RAM。

3 结束语
    本文介绍了一种针对MLC flash的优异管理算法及软件实现方法，并且已在SD卡上大规模商用。该算法只需简单配置就能支持市场上的各种flash，而且也兼容各种SD设备。同时RAM空间需求小，成本低，寿命长，兼容性好，扩展性强，flash空间利用率高，具有很高的商用价值。