把大象关冰箱的步骤 --- NAND FLASH控制器磨损管理算法芯片化硬实

把大象关冰箱的步骤 --- NAND FLASH控制器磨损管理算法芯片化硬实现

目前，存储领域包括eMMC，SATA SSD ,PCIe SSD等控制器是一个非常热门的领域。通常，由于NAND FLASH易于损坏的特性，因此需要控制器做额外的工作，才能满足商用可靠存储的需要。

存储控制器的所做的额外工作就是均衡磨损、坏块管理、以及逻辑地址到物理地址映射的管理。通常在存储控制器中需要集成CPU运行并运行相应的软件才能完成上述的功能，而随着存储性能的增加，则需要更高性能的CPU或者多核处理器以及高速的处理算法。

本文目的提出一种可以硬实现的均衡磨损，坏块管理，以及逻辑地址映射的算法，(可芯片化)。用于替代处理器的软件(FTL)实现，从总体上较CPU固件实现有较好的功耗比和高速性能的目标。

首先说明: NAND FLASH的管理说明：

1：NAND FLASH 只能按页写，且只能写干净的页。(一个页一旦写过就不能写第二次，除非被擦除)

2：NAND FLASH 能按页读，这个可以读多次。

3：NAND FLASH 只能按块擦。(一个块包含多个页)。

4：NAND FLASH的出错一般出现在写，和擦除时，如果NAND FLSAH的块在写或者擦除时，出错，则就不能再使用，内部内容需读出写入其他的位置。

5：如果NAND FLASH的管理中，如果重新改写同一地址，则原地址内容作废，逻辑映射一个新地址写入(原因见规则1)。

1：基本操作：读，写;

那么如何设计相应的硬实现算法：首先是考虑写操作，每次写都要写一个干净的地址。因此我们假设有一个模块，每次吐出一个新的干净页地址，那么每次写操作时，都申请从此模块申请一个新地址。

写NAND FLASH的步骤：(把大象关冰箱里的步骤)。

0：主机写入一个逻辑地址(LA logic address)中一个page的数据(PD pagedata)。

1：从地址分配器(FIFO)中申请一个干净页地址(PA physical address)，然后写到新的页地址中。(这个步骤前少一步，)

2：记录逻辑地址和物理地址的对应关系。(LA->PA)到映射表。这样完成写的流程。

下次读的时候，

0：主机读取一个逻辑地址(LA logic address)。

1：查找映射表，对应的映射表LA->PA，则读取PA的页数据(PD)。返回主机。这样就完成了读的流程。

这样考虑就是想法简单了，上图是正常的写流程。

由于写FLASH的步骤，首先要确定原有逻辑地址在映射表里是否存在，映射表相应的表项删除(删除的表项会重新擦除使用，否则很快就会写完)。

写NAND FLASH的步骤：

0：主机写入一个逻辑地址(LA logic address)中一个page的数据(PD pagedata)。

1：查看页地址中是否有相关的逻辑地址表项，如果有，则删除表项，否则直接到下一步。

2：从地址分配器(FIFO)中申请一个干净页地址(PA physical address)，

3：记录逻辑地址和物理地址的对应关系。(LA->PA)到映射表。

4：然后写到新的页地址中。

读NAND FLASH的步骤：

0：主机从一个逻辑地址(LA logic address)中一个page的数据(PD pagedata)。

1：在映射标的表项中，查找LAn的表项。

2：查找对应的物理地址(PAm)。

3：从PAm读出PD并返回主机。

2：擦除：擦除

从上述的机制来看，每次写操作时，都会占用一个PAGE，而假设原有的逻辑地址内部存储数据，则原有的逻辑地址对应的物理地址则被废弃，因此需要将这些物理地址重新擦除后重新使用。(否则FLASH写完一遍后，再也不能再写)。

另一问题，page按页来写，而擦除按照块来擦除，假设每个块有512个page。

按照上述机制，每个块都有512个page放入申请单元中，而这些page写操作时，被依次申请，也就是说，BLOCK中每个page都会被写满，当这些物理page被重新写时，则原有的page变成脏页，可以被擦除。但是前提是512个page的都凑齐。那擦除的情况分为两种，

情况1：一个块(block)中，所有的page都被写变成dirty后，可以擦除，放入地址分配器中。

情况2：地址分配器中剩余地址少于一定数量，则就考虑将那些仍然还有数据页部分有效的块(block)擦除，再进行分配。前提是，将数据页先读出换个地方存储。

对于情况1，可以类似数通领域的组片，每个被重复写的逻辑地址，就释放一个物理地址，收齐一个块中所有的物理地址(都被写过后，释放掉)，就可以重新擦除后，重新放置在地址分配器中。

对应情况1来说：其触发条件新的写入page，原有page被回收后，放入地址回收器中：

因此擦除的步骤可以分为：

1：获取被回收的物理地址PAn;

2：回收器检查PAn所在的BLOCK n，所有的page是否收齐(每个块用1bit标示，所有bit收齐为1时，可被回收)，如果收齐转入步骤3，否则置PAn已回收的标示。

3：通过NFC(NAND FLASH)擦除相应块。

4：释放地址(PAn … PAn+511)到地址分配器，供新的写请求申请。

对于情况2，其触发条件为，地址分配器中的可分配地址低于水位线(可用的地址少于一定数量)。

erase2.jpg

对于情况2来说：

1：地址分配器FIFO低于阈值，用于触发地址回收器。

2：地址回收器，查找还剩最少page没有收齐的BLOCK及相应的page(PAx，PAy，PAz)。

3：在映射表中，查找相应的物理地址所对应的逻辑地址;

4：通过地址分配器申请新的物理地址，并填写在原来的映射表中。

5：读取原物理位置的数据PD(X，Y，Z)。

6：将数据写入新的申请的物理地址中。(4，5，6可以串行执行，循环多次，将未收齐的地址读出)。

7：转移完毕后，擦除原来的块(BLOCK)。

8：将擦除后的块地址，写入地址分配器中。

完成后(就多出了接近一个BLOCK的地址空间，供上层应用写入)

3：坏块管理;

NAND FLASH在写或者擦除时，会出错，出错时，需要将此块标记成坏块，以后将不能使用。

因此坏块管理模块，需要记录所需要不能使用的坏块。因此我们讨论坏块出现的两种情况：

1：在擦除时，出错，则此block为坏块，坏块管理单元记录坏块。

2：在写某page出错，首先所在块(block)读出剩余的page，分配新的物理地址，更新映射表，同时对该块进行擦除，如果出错标记为坏块，如果有幸不出错，则可以重新将地址放入地址分配器。

对于情况1来说：操作相对简单;

对于情况2来说：坏块管理单元的操作较为复杂：

1：写操作，触发坏块管理单元工作。

2：写出错。坏块管理单元受到触发，记录当前的物理坏块的位置(M)。

3：同时将地址分配器中M坏块中的剩余地址读出，(禁止再向这些page中写入数据)。读出后，申请新的块中的page，将当前数据写入flash。

一种积极的处理方式如上图所示：

4：查找该block对应剩余物理地址所对应的逻辑地址。

5：申请新的物理地址并记录新的映射表。

6：读出物理块地址所对应的数据。

7：将数据写入新申请的物理地址。

注释：步骤4，5，6，7可以顺序执行，循环多次，取决于该block的已用的page的个数;

8：等搬完毕后，重新擦除该块(M);

9：如果擦除成功，则将地址重新放入分配池，否则该块丢弃。

另一种消极的方法：

在步骤3后，只需要记录当前块位置，将M坏块中的剩余地址读出后，放入地址回收器，等待该块剩余位置被重新写时，则该page被废弃，由地址分配器收齐所有地址后再进行擦除。

剩余步骤从8开始，直接擦除该块，擦除错误，直接废弃该块，擦除成功可重新放入地址分配器。

4：均衡磨损;

均衡磨损是NAND FLASH的基本功能，通过将可用的地址放入先入先出的地址分配器中，能够保证均衡磨损的效果。

如何将磨损程度最小的可用块，放入地址分配器(FIFO)，是本节讨论的要点?

这个问题转化为:设计均衡磨损管理模块，其功能将磨损程度最小的块，首先放入地址分分配器。

均衡管理模块需要将统计所有块的磨损次数，然后找到最小磨损的块。对于需要分配地址时，如果涉及到查找最小磨损块，则可能会影响写的效率。因此，涉及一个链表，将块的磨损次数按照次数的多少进行排序，如果磨损次数相同，则按照地址的大小排序。如此一来，则可以保证，则需要快速申请有效地址时，则可以按照链表的顺序，迅速将可用块地址放入地址分配器。

因此：对于均衡磨损来所，涉及到链表的生成和链表的读取;

对于初始化时，由于此时所有块都是可用的，因此其擦除次数可以都设置为1，此时课可以按照的地址的大小进行链表的链接。

对于地址回收器，来说如果已回收某块，(如上图中，地址回收器标示第4块已被回收)。触发均衡磨损管理模块，标示其收到已擦除的块。

将已擦除的块(第四块)擦除次数自加，标示为有效(可以将此块放入地址分配器)，

排序，建立新的链表。建立的过程一种方式是，查找到比其磨损次数多的块n0，比其磨损次数少的块n5,同时修改其上一块(pre block)和下一块(post block)。这样就建立了一条按照磨损次数由小到大的链表。(建链的过程可以通过设计最新擦除的次数块的cache，加大能够碰撞的几率，因为如果大块数据的写操作，其回收的块的磨损次数应该近似，写时申请page所在的块磨损次数就接近(我们按照由小到大的顺序放入的)，因此回收时，磨损次数也接近，因此cache对处理此种空间相关性大的算法，效率较高)。

那什么时候均衡管理模块将数据放入地址分配器中?

触发条件：当地址分配器中的FIFO低于设定的阈值，触发均衡管理模块开始工作。

将入口地址n3块放入地址分配器。(将块号转换为块中所有的512个page号(假设为每个块中有512个page)。

根据链表，将n5变为入口地址，等待下次触发条件，然后将 n5放入地址分配器。

这样，根据上述的算法，就可以使所有的块，均衡的磨损，保证所有块被擦除的次数一致。

5：总结一下;

回应开头，本文的目标是设计一种可以硬件(硬件描述语言)实现的NAND FLASH的均衡磨损的算法。替代CPU+软件的方式实现在当前较热门的存储控制器中。

(1)，所有的操作，都需要触发条件(读，写，擦除，坏块管理，均衡磨损)，其他时间可以模块可以休眠，因此功耗容易控制;预计比CPU有更好的能耗比(也跟实现相关)。

(2)硬件实现不取决于CPU的能力，特别是对于PCIe的NAND FLASH控制器来说，可以达到非常高的处理能力，瓶颈在NAND的读写擦除速率。

(3)缺点：设计中需要多个表项的管理。

分别是1：映射表，管理逻辑page地址和物理page地址的对应关系。

2：地址回收器中，block内page的回收表;(每个page需要1bit表示)。

3：均衡管理模块中的链表，存储所有块的磨损次数以及链表信息。

这些表项与NAND的大小有关系(是8G/16G/32G?),这些表项是按比例增加的，因此NAND，这些表项需要大块的RAM存储。

其次映射表的查找，同时需要设计CAM模块及操作，来加速表的查找。

如果在PCIe的控制器中，可以放在外部DRAM中，掉电检测时，存储在NAND中，加电时再将数据读出。如果没有外部DRAM，则就需要将映射表一部分放入NAND中，另一部分放入片内SRAM中，同时也会占用较多的SRAM。 同时需要不断的取出及存入NAND中(这个设计同时保证可靠性就是一个挑战)。

(4)：总结，此种算法应该适合应用于高速的NAND控制器中，替代高性能多核CPU来实现FTL。具有较高的能耗比与可行性。