Flash磨损均衡

flash 原理和部分名称

package 是存储芯片，即带有电连接器的小黑色矩形。
dies 每个package包含一个或多个die（例如一个、两个或四个）。die 是可以独立执行命令或报告状态的最小单元。
planes每个芯片包含一个或多个planes （通常为一或两个）。每个planes上都可以进行相同的并发操作，但有一些限制。
blocks 每个planes包含若干个block ，block是可以擦除的最小单位。
pages每个block包含若干个 page，page是可进行编程（即写入）的最小单位。

磨损均衡可实现的底层原理是（同一个块）一次擦除，多次写入。

擦除是将任意内容改成0xff，即全1状态。
你可以对一个page执行多次写入，但是需要注意的是写入仅能将1改成0，无法将0改成1。

EEPROM可以单字节（或者四字节）写，而FLASH只能按整个blocks擦除，另外EEPROM一般有100万次的读写寿命，而FLASH只有10万次；

一些简单实现的Demo

这些demo只是头脑风暴的一些实现，仅仅是一个思路，具体实现还需要完善很多的细节。

draw.io 源文件

数据长度固定

数据长度固定，使用bitmap记录数据状态。

数据长度可变

一些高性能的磨损均衡算法 SSD Wear Leveling

Flash采取异地更新的策略 ,更新的数据会被放到别的物理页上,而不是覆盖原来的数据。包含新版本数据的页被称为有效页,新版本数据被称为有效数据。包含旧版本数据的页被称为无效页，或称为脏页，脏页经过擦除操作后成为空闲页，才可以重新写入数据。因为Flash是以块为单位执行擦除的，因此需要将脏页所在块上的所有物理页都擦除，在擦除之前需要检查此块上是否存在有效页，如果存在就必须先转移到其他块上。因为每个Flash块的擦除次数有限，一般是在10 万次到100万次之间，只要有块的擦除次数达到了上限，Flash数据存储的性能将下降。所以必须想办法，使擦除操作平均作用在每个Flash块上，这种方法就是磨损均衡(wear-leveling)算法。

我们在应用Flash时，实际上访问的是Flash的逻辑地址，在逻辑地址和物理地址之间，存在着映射关系。数据更新后只需改变映射表中物理页的地址，并将原版本数据所在的物理页标为无效。对于经常被更新的数据块，我们称之为“热”数据块，对长期得不到更新的数据块，称之为“冷”数据块。数据块经常更新的话，就会经常被擦除，而长期不更行的数据块，不会出现脏页而被擦除，其擦除次数会明显少于存放着经常被更新数据的块。如何实现“冷热”数据存放位置的交换是磨损均衡处理中需要考虑的问题。

目前常用的磨损均衡算法大致分为两类，一类是随机性算法，一类是确定性算法。

对于随机性算法，其原理为：在每次写或擦除操作后，按照某一概率来触发磨损均衡处理。按照均匀分布的概率，随机选择某个块执行擦除操作。不论块上放的是“冷”数据还是“热”数据,让每个块得到相等的擦除机会。最后将选中块上的有效数据复制到空块后擦除此块。将数据移动到哪个空闲块上,也是随机选择,因为没有记录块的擦除情况,存在将“冷”数据又移动到一个“冷”块上的情况,结果此块并没有增加擦除次数, 这种情况尤其会发生在有大量“冷”数据的系统里。
对于确定性算法，又分为周期性和全局性两种，其中周期性算法的原理为：将Flash的寿命看做是一个接一个的磨损均衡周期组成的。在一个处理周期中，达到规定的擦除次数的块在这一轮周期中将不会被选中，这样可使各个块都达到相同的擦除次数，再开始下一个擦除周期。通过调整Flash块的规定擦除次数，可以使整个Flash能够达到理想的磨损均衡。全局性算法的原理为：不划分处理周期，在一个全局范围内控制块的磨损均衡。当任何两个块的擦除次数之差超过一个给定的阈值时，或者当某块的擦除次数超过了所有块的平均擦除次数时，启动磨损均衡处理，将擦除次数少的块上的数据和擦除次数多的块上的数据进行交换。如果块上存放的是“冷”数据，即数据很少被更新，则该块上的数据不易变脏，很少得到擦除的机会。相反，如果该块上存放的是“热”数据，则该块上的数据经常被更新，经常得到擦除脏数据的机会。根据这个原理来交换“冷热”数据，从而实现磨损均衡。

对比两类磨损均衡算法，可以看出：随机性算法的效果受随机因素影响较大，在擦除前，并不知道各个块被擦除的情况，同时对逻辑页的随机性请求并不能做到完全等概率，所以虽然随机性算法是等概率地选择处理页，但每个块的擦除次数并不能达到等概率分布，不能达到很好的磨损均衡效果。确定性算法因记录了物理块的擦除次数，故在处理中可根据这些信息来作出调整决策，各块基本达到了相近的擦除次数，磨损均衡的效果明显好于随机性算法。但这是在消耗大量内存开销的基础上实现的。

根据以上讨论的情况，可以看出，必须结合两类算法的优势，来实现效果较好的磨损均衡处理，才能既保证Flash的读写速度，又能保证Flash的使用寿命，这将是决定固态存储能否全面战胜机械硬盘的关键之战。