[原创]
用flash存储数据，你还想着用文件系统？不，你需要的是......wear leveling
PS：谢绝不打招呼，就悄悄行动的的转载君，如果你真的觉得很想转载，请与我联系～
1.引子： 我需要给程序增加一个 存储参数 的功能，因为参数较多，所以考虑采用flash存储器。相比于传统机械硬盘等存储设备，flash存储设备最大的区别就在于读写因为不能逐个字节字节进行，所以磨损平衡（wear levelling)等平衡算法变得特别重要。
特别提醒：本文只针对NOR Flash,如果你想知道或者分享NAND Flash的情形，请直接回复或者给我发邮箱。关于NAND Flash我尚未考虑但下一步会尝试。
最开始的时候，我本打算参考一个原有项目工程，使用文件系统，然而在进一步了解了 flash、文件系统这些概念之后。我发现，这套参数的存储不需要使用一般意义上的文件系统，只需要针对flash的特性在读写上进行一些优化即可，即与flash file system相比，我真正需要的可能是FTL，即Flash Translation Layer，
这篇文章将简单描述这个逐渐认识的过程、详细而扼要地介绍flash存储设备的读写特性，以及一些其他一般存储都需要的数据校验，掉电保护等常见功能，重点在于如何为单片机这种相对简单应用场合选择一种合适的简化的实现方式。
本帖最后由 辛昕 于 2015-8-1 16:41 编辑
对于磨损均衡可以搜索关键字，冷热均衡，双池均衡，三池均衡等
2作为一个数据实例：交流电表DLT645协议
这是国内电网交流电表普遍采用的DLT645协议（2007版）中的一小部分参数（选择它们是以其不怎么涉及领域专业术语,可能更容易被理解）。它们被组织成一份以 4字节数据标识（Id号）索引的固定字长 数据表。尽管它采用了8421-BCD码格式，但对于编程这只是一个编码转换的过程，并不是太大不了的事情。
抽象起来，它可以描述成如下通用格式：【4字节id】【xx xx ... xx】
因此对于用存储器存取，实质上，没什么特别的，就只是写入4字节id+相应数据就可以了（实际上设计时，可能还要相应的增加数据头数据尾）。 本帖最后由 辛昕 于 2015-8-1 16:47 编辑
3.基于Flash存储器特性读写遇到的问题：
Flash的一个重要特性是，写入数据之前，写入的区域必须首先被擦除过，但擦除的单位不是字节，而是块（sector)，而大多数的flash芯片，这个块的大小，小则 256字节，512字节，大可以到几十K字节乃至几M。
特别的，flash分两类，一类是NOR Flash，也是本文论述的对象，另一类是NAND Flash，我们这里不关心太多其他细节，提及它只是要说明，其中，NOR可以字节写入，而NAND要块写入。
NOR Flash的擦除次数大概是十万次，超过这个次数以后，读写操作的数据就不可靠了，而NAND Flash好些，可以有一百万次，这听着好像很多，但实际用起来，很可能也就是一两年使用寿命，这种性能连家用级消费品都不能接受，就更别提企业级，工业应用不买账了。
在这种情况下，我们就不能像平时操作 AT24CXX等 EEPROM芯片那样简单地在任意地址读出/写入任意长度的数据，即，无法简单地直接地实现随机存取。
flash存储器直接随机存取的巨大代价
为了更好说明直接随机存取的代价有多大，我们简要描述一下这个过程。
比如，我们已经在 0x00001023这个地址写入字节0x32;下一次但我们又要改写这个字节为另一个数值的时候，我们不能直接改写这个内容，而要擦除它所在的整个片区，假如这个片区是256字节（几乎是最小假设）。而这个片区原来还有其他数据，不能丢失，于是我们必须首先用另一个空间存储这256个字节的数据——然而，在一个程序里，使用256字节的随机变量，有时可能是不能负担的（更进一步说，很多时候，一个flash片区远远不止256个字节），于是我们很自然的会想到用另一个flash块来暂存。
于是，这就又是另一个上述过程的重复，当然，为了避免递归死循环，我们不会用一个有用的片区做这个临时缓存，而是专门开辟一个区专用于临时缓冲数据。
回到前面的暂存数据，由于一个块的容量一般很大，超出了一个程序能容忍的堆栈深度，所以，这个过程想必是一次一次进行的，比如说要复制256个字节过去，总是一次64字节64字节的复制，然后，我们在这个过程里，定位到要改写的数据，在这个过程里改写数据。
最后，我们把原来的片区擦除了，再把数据写回来，这个过程，又是一个一次64字节一次64字节地写回来。
简单总结一下这个过程里的开销
1.一个临时片区，而且为了保证足够大，至少不能比使用中的任何一个片区小，否则就没法完整备份一个片区了，而大多数flash，内部的片区都不一定等大，当然，在使用过程中，我们可以根据实际存储的数据大小情况，选择适当的片区分配方案，减少浪费。
然而，不管如何，这一个临时片区是浪费定了。
2.这个过程里，需要一个不小的局部数组用来传递数据，当然这个数组的大小和你搬运sector数据需要使用的次数是成反比的——简单的说，要么你占用空间，要么你占用时间。
但不管如何，这里都花了大量时间复制，而这根本就不是你要的最终效果。
3.擦除一个片区也是很花时间的。当然这个视乎片区大小，小的片区可能在几十上百ms左右完成，大的片区可能足足要几秒甚至几十秒。
4.这么任性地擦擦擦，很快就会擦废了芯片。
5.这是最要命的，刚刚，我们只不过是进行了一个字节的字节改写。
前面我特意花了这么多文字详细描述这个过程，只想说明：这个看起来很直接很不错的方法，非常不现实。
本帖最后由 辛昕 于 2015-8-1 16:48 编辑
4.一个更实际的flash读写方案：wear-leveling
从前面的分析我们已经知道了，直接随机存取是不可取的。但是我们又确实要不断改变同一个参数的数值，那我们该怎么办呢？
我们很自然的会想到，不擦除原先写下的数据，而是继续在其他已擦除过的位置写新的数据（查找时靠数据里带上id等信息来分辨即可）。事实上，这种很自然而然的想法，正是flash读写驱动中的一种名字生僻的关键思路：磨损平衡，即wear-leveling；这个名词的翻译不一，说英文反而更多人知道。
4-1.关于wear leveling
简单解释就是，wear leveling使用一种算法在写Flash的时候，不反复只写同一个片区，而是均匀的使用片上所有片区，以提高整体的使用寿命，做个简单的例子就是说，假如一个系统里，按照其使用频率，假如NOR Flash的十万次可靠擦除可以使用1年，假如采用磨损平衡算法，平均使用完片上所有的（假如是十二个）片区，而寿命则从一年提升至12年。这个例子虽然因为过于简单而使这种估算不一定正确，但事实上，现在商用的flash存储设备大多就是使用这个方法来提高寿命的。
我在搜索资料时，在著名的StackOverflow论坛上看到一个回答，让我深受启发，现在原文摘录如下。
该帖子名字：What free tiniest flash file system could you advice for embedded system?（你能推荐什么最轻量的自由的flash文件系统？）这也正是我想提出的问题。
这个帖子回复的数量不多，而最后一个也是最长的一个，给了我关键性启发。我摘录原文如下，并试图翻译其中直接相关的部分：
answeredJun 23 '10 at 1:41 RBerteig（回答者）
On a NOR flash, especially one that also contains my boot code and application, I generally avoid the overhead of a formal file system. Instead, I store each "interesting" object starting at an erase block boundary, and beginning with a header structure that at minimum holds the object size and a checksum. Adding a name or resource ID to the header is a natural extension.
在一个NOR Flash上，特别是包含我的boot代码和应用的存储器上，我一般避免在上面使用一个正式的文件系统，相反，我把所有我感兴趣的对象，从一个已经擦除的块开始的地址开始存储，数据前我一般我会加上数据头结构体，它一般至少包含有这个数据块大小和一个校验码，而加上一个名字或者一个资源id号也是很自然的扩充信息。（这种一直往前写的方法，事实上前几天晚上我在eeworld开发板置换群里询求一个方案时，哥们!!!...袁<ayrw@163.com> 也提到这种思路。）
The boot loader looks for a valid application by verifying the checksum before using the block. Similarly, other resources can be confirmed to be valid before use.
Boot载入代码时，会通过检查使用到的数据块的校验码去寻找一个合法的应用程序，类似的，其他的资源（前面提到的那些保存的数据）也可以在使用前通过（这种方式）校验确认正确。
It also makes it easy for a firmware update utility to validate the object before erasing and programming it to the FLASH.
这可使得使用固件升级工具在擦除和对FLASH编程之前，去校验数据正确与否。（译者注：这过程很类似于我们使用JFLASH等工具直接烧入字库等大数据块）
A pool of small resources might be best handled by wrapping it in a container for flashing. If the runtime resources support it, I would be tempted to use ZIP to wrap the files, wrapping the image of the ZIP archive in a size and checksum header and storing it at an erase block boundary. If you can't afford the decompression runtime, it is still possible to use ZIP with uncompressed files, or to use a simpler format such as tar.
（这一段涉及压缩之类的提法，我对此很陌生，而它也和我追寻的问题关系不大，所以我不勉强翻译）
Naturally, the situation is very different for a NAND flash. There, I would strongly recommend picking an established (commercial or open source) filesystem designed for the quirks of NAND flash.
当然，但使用一个NAND flash时，情况非常不一样，这个时候，我强烈推荐使用一个已经写好的专门用来对付NAND flash的古怪特性的文件系统（哈哈，nand flash也躺抢了），不管是商业的还是开源的。
本帖最后由 辛昕 于 2015-8-1 16:52 编辑
5.整理方案
如前所述，最开始我的想法很简单，我想通过寻找一个文件系统来完成这件事，那样就省了我很多麻烦。不仅不需要我自己实现，甚至不需要我去考虑我需要完成什么可能需要但我现在因为没实际使用而想不到的问题。
但是，在我大量搜索和看了各类英文wiki页面，关键词从 文件系统 到 flash文件系统，到flash Transaction Layer(FTL),还知道了TrueFFS之类的文件系统。但我没有找到相关的源码或者文档.......
直到我看到上述那个StackOverflow的回答时，我才意识到：够了。
最核心的，我需要一个 wear-leveling 的实现方案，前面的回答似乎很完美很简单，然而，它遗漏了一个很关键的部分：如何快速查找到特定id的最新记录？也就是说，它完成了写的部分，却没有提供读的部分，而偏偏这两者是需要相互促成的。
这也是我自己要完成的部分。当然，这个回答里也包含了一些其他内容，比如数据校验，回答者使用了很简单的校验码的方法。而同时我也意识到，其实一旦实现了这种方案，掉电保护也就完成了——因为任何时候，至少有可靠正确的数据已经牢靠存储着，尽管可能丧失了最新要存的数据（而这种事情，除非有可靠的后备电源，否则，是根本不可能通过任何手段修复的，因为这是物理问题）， 但如同微软启动界面的那个选项“ 恢复到最近一次正确配置”。
5-1不断往前写很简单，但读却麻烦了
前面提到 使用顺序写入方式实现磨损平衡，这个方法相比常见的内存映射方案中的地址映射表，简单至极，但不足之处，缺乏一个方法来记录某id的最新记录出现在哪个地址。
可能的解决方法优缺点分析：
1.从尾部逆向搜索
即从最后写的位置开始搜索，逐个逐个读出（flash读是一个很快的过程，同时不需要任何附带动作，没任何代价。）然后根据id等数据头信息判断是否要找的参数，最先找到的必然就是最后写入的最新数据。
缺点：在最差情况下，可能要搜索所有已写的数据项，非常耗时；
其次，也因此每次搜索时间非常不均匀；
相对来说，我认为这是最大的障碍，因为这如同rtos中使用的动态分配算法，寻找可用内存耗时不均匀将严重破坏实时性。
2.使用eeprom等，记录最新地址
这几乎是最直接的方式，而且不需要任何解释。
缺点：需要增加eeprom设备，在某些情况下，还非常划不来——记录地址一般也是4字节，而很多数据项本身也就是4字节甚至更少的2字节乃至1字节，这时候你会觉得我还用什么flash啊？
3.使用记录的方法2：
用flash隔离出一个 日志区，但实际上这无法回避覆盖问题，和不使用面临的问题一样；
5-2.希望得到的一种方法
可以找到一个较好的分配方式，使用某种运算方式，把id和写向的地址（范围控制在一个扇区范围内）产生关联，即使产生碎片也可以。从而避免长期不定的搜索 或者 记录 需求。
接下来，我觉得除了在github之类的地方寻找类似的源码来参考，并选择一个在复杂度和各方面开销、性能方面之间较好平衡的方案来完成这个算法。
本帖最后由 辛昕 于 2015-8-1 16:57 编辑
如果您觉得我的回复/帖子/博文有价值，感谢您的打赏（v0.91）
https://home.eeworld.com.cn/my/space-uid-115166-blogid-260329.html
当然请不要对这个感到太刺眼，随喜随喜。有钱捧钱场，没钱捧人场也是完全可以滴～～
更多的是欢迎你来交流交流想法。
不管如何如果你有啥想问的想说的请不要犹豫给我写邮件。
当然，更加欢迎你直接回复帖子。
如果你有什么对这个东西更深入的需求也请和我联系（推荐发帖如果您愿意公开的话）
我将在24h内给予回应。
本帖最后由 辛昕 于 2015-8-1 17:03 编辑
棍哥好厉害
首先纠正一个问题，现在市面上的NAND FLASH有三种，SLC/MLC/TLC，其中擦写次数依次递减，稳定性也依次递减，SLC大约10w+次，MLC5000+次（datasheet数据一般较为保守），SLC500+次，没有你说的百万次。一般的ssd用的都是MLC，好的u盘用的也是MLC，差的u盘用TLC或者黑片,看着容量不小但是价格很便宜那就要注意了。另一个错误是即使是现在的MLC擦写只有5000次，ssd也能轻松做到质保三年，好的质保五年，还是只换不修，保质期内只要用坏给你换新的。
看到这个文章很是高兴，因为论坛竟然有人研究起了FTL，我曾经问过一些在嵌入式设备使用NAND 的人，是怎样做的，他们的回答是只用了坏块管理，对于FTL的映射、垃圾回收、磨损均衡都没有涉及，这个也是可能的，比如进行环形文件的写入，只需要依次写入即可，不用考虑映射和垃圾回收，对于磨损均衡更谈不上，因为环形写入已经接近绝对均衡了。
当我对他们谈起FLASH管理也被鄙视了一顿，他们很不屑的认为不应该有FTL这个东西的存在，我也懒得跟这些人理论。因为我感觉他们就是土炮。
对于norflash一般没有FTL可言，FTL针对NAND FLASH更多。
对于FTL的研究，各个ssd厂家都是保密的，我们无从得知，论文倒是有不少，但是基本上大同小异，看一篇就不需要再看其他的了，有价值的不多。网络信息比较少。
对于FTL，现在一般有三种算法，block mapping、page mapping、hybric mapping。对于block mapping，映射简单，所需的资源较少，垃圾回收压力较大；对于page mapping，映射逻辑简单，所需资源较大，回收压力较小。对于hybric mapping则对以上两种算法做了折中，映射较为复杂，垃圾回收压力一般，所需资源较少。
对于速度性能来说，三种算法的空盘的顺序读基本上完全取决于硬件带宽，因为对于顺序读的算法就是查找映射表，时间复杂度O(1)，对于随机读写，可以简单地认为block mapping最差，hybric次之，page mapping最好，当然这也不是绝对的，有些优化也可能使hybric的随机性能高于 page mapping。
对于一款SSD或者u盘来说，做的这些映射还远远不够，因为有了映射表，掉电之后还要进行映射的重建，还有垃圾回收，当盘写满之后，速度掉落的很厉害，磨损均衡相对来说逻辑上很简单实现，而且效果也比较好。磨损均衡又分为静态磨损均衡和动态磨损均衡。
如果说到FTL那么可以简单地认为是SSD算法或者u盘算法了。
嵌入式设备的开发如果涉及到FTL耗费的时间精力那就太大了，毕竟我们有了eMMC，eMMC将FTL和FLASH做到了一起，这个使用起来相当方便。
另外说一个对于NAND flash相当重要相当有用的东西，spare空间。
说起来真不是一两句能够说清楚的，总的来说，FTL有那么几部分，映射、坏块管理、垃圾回收、重建、磨损均衡、还有掉电管理。这个掉电管理和你说的norflash操作回滚可是两回事，因为ssd一般有ddr做缓存，掉电时脏数要么抛弃要么回写
对于norflash的操作回滚，只有norflash底层的设计还是不够的，需要和上层结合才能够做好，这个操作就相对简单一点了
京公网安备 11010802033920号
