主持人 > 博客 > 管理 > 我在 NOR 闪存中实现环形缓冲区

我在 NOR 闪存中实现环形缓冲区

史前

有我们自己设计的自动售货机。 Raspberry Pi 内部和单独板上的一些接线。 连接硬币接收器、纸币接收器、银行终端……一切都由自己编写的程序控制。 整个工作历史记录被写入闪存驱动器 (MicroSD) 上的日志中，然后通过互联网（使用 USB 调制解调器）传输到服务器，并存储在数据库中。 销售信息加载到1c中，还有一个简单的Web界面用于监控等。

即日记账至关重要——用于会计（收入、销售额等）、监控（各种故障等不可抗力情况）； 有人可能会说，这就是我们掌握的有关这台机器的所有信息。

问题

闪存驱动器本身就是非常不可靠的设备。 他们失败的频率令人羡慕。 这会导致机器停机和（如果由于某种原因日志无法在线传输）数据丢失。

这已经不是第一次使用闪存盘了，在此之前还有一个项目有一百多台设备，杂志都存储在U盘上，也存在可靠性问题，有时失败的数量也很多。一个月有几十个。 我们尝试了不同的闪存驱动器，包括带有SLC内存的品牌闪存驱动器，有些型号比其他型号更可靠，但更换闪存驱动器并没有从根本上解决问题。

警告！ 长读！ 如果你对“为什么”不感兴趣，只对“如何”感兴趣，你可以直接进入 到底 文章。

解

首先想到的是：放弃 MicroSD，安装 SSD，然后从它启动。 理论上是可能的，但相对昂贵，而且不太可靠（添加了 USB-SATA 适配器；预算 SSD 的故障统计数据也不令人鼓舞）。

USB HDD 看起来也不是一个特别有吸引力的解决方案。

因此，我们做出了这个选择：保留从 MicroSD 启动，但以只读模式使用它们，并将操作日志（以及特定硬件特有的其他信息 - 序列号、传感器校准等）存储在其他地方。

树莓派只读文件系统的主题已经被彻底研究过，我不会在本文中详细讨论实现细节 （但如果有兴趣，也许我会写一篇关于这个主题的小文章）。 我想指出的唯一一点是，无论是从个人经验还是从已经实施的人的评论来看，可靠性都有所提高。 是的，完全消除故障是不可能的，但显着降低故障频率是很有可能的。 而且卡片正在变得统一，这使得服务人员的更换变得更加容易。

硬件部分

对于内存类型——NOR Flash 的选择没有特别的疑问。
参数：

  • 简单的连接（最常见的是 SPI 总线，您已经有使用经验，因此不会出现硬件问题）；
  • 荒谬的价格；
  • 标准操作协议（该实现已经在Linux内核中，如果您愿意，您可以使用第三方的协议，该协议也存在，甚至可以编写您自己的协议，幸运的是一切都很简单）；
  • 可靠性和资源：
    从典型的数据表来看：数据存储20年，每个块100000次擦除周期；
    来自第三方来源：BER 极低，假设不需要纠错码 （有些作品认为 ECC 代表 NOR，但通常它们仍然表示 MLC NOR；这种情况也会发生）.

让我们估计一下数量和资源的需求。

我希望数据能保证保存几天。 这是必要的，以便在出现任何通信问题时，销售历史记录不会丢失。 我们重点关注5天，这期间 （即使考虑到周末和节假日） 问题是可以解决的。

目前，我们每天收集约 100kb 的日志（3-4 个条目），但这个数字正在逐渐增长 - 细节不断增加，新事件不断添加。 另外，有时会出现突发情况（例如，某些传感器开始发送误报的垃圾邮件）。 我们将计算 10 条记录，每条记录 100 字节 - 每天兆字节。

总共产生了 5MB 的干净（压缩良好）数据。 更多给他们 （粗略估算） 1MB 服务数据。

也就是说，如果不使用压缩，我们需要 8MB 芯片，如果使用压缩，则需要 4MB。 对于这种类型的内存来说，这是相当现实的数字。

至于资源：如果我们计划整个内存每 5 天重写一次不超过一次，那么超过 10 年的服务，我们得到的重写周期将少于一千次。
提醒一下，厂家承诺十万。

关于 NOR 与 NAND 的一些知识

当然，如今 NAND 内存更加流行，但我不会在这个项目中使用它：NAND 与 NOR 不同，必然需要使用纠错码、坏块表等，而且还需要使用 NAND 内存。 NAND芯片通常要多得多。

NOR 的缺点包括：

  • 体积小（因此，每兆字节的价格较高）；
  • 通信速度低（很大程度上是由于使用串行接口，通常是SPI或I2C）；
  • 缓慢擦除（根据块大小，需要几分之一秒到几秒）。

看来对我们来说没有什么重要的事情，所以我们继续。

如果细节有趣，则已选择微电路 at25df321a （然而，这并不重要，市场上有很多在引脚排列和命令系统方面兼容的类似物；即使我们想安装来自不同制造商和/或不同尺寸的微电路，一切都可以正常工作，而无需更改代码）.

我使用 Linux 内核内置的驱动程序；在 Raspberry 上，由于设备树覆盖支持，一切都非常简单 - 您需要将编译后的覆盖放在 /boot/overlays 中，并稍微修改 /boot/config.txt。

示例 dts 文件

说实话，我不确定它写得是否没有错误，但它确实有效。

/*
 * Device tree overlay for at25 at spi0.1
 */

/dts-v1/;
/plugin/;

/ {
    compatible = "brcm,bcm2835", "brcm,bcm2836", "brcm,bcm2708", "brcm,bcm2709"; 

    /* disable spi-dev for spi0.1 */
    fragment@0 {
        target = <&spi0>;
        __overlay__ {
            status = "okay";
            spidev@1{
                status = "disabled";
            };
        };
    };

    /* the spi config of the at25 */
    fragment@1 {
        target = <&spi0>;
        __overlay__ {
            #address-cells = <1>;
            #size-cells = <0>;
            flash: m25p80@1 {
                    compatible = "atmel,at25df321a";
                    reg = <1>;
                    spi-max-frequency = <50000000>;

                    /* default to false:
                    m25p,fast-read ;
                    */
            };
        };
    };

    __overrides__ {
        spimaxfrequency = <&flash>,"spi-max-frequency:0";
        fastread = <&flash>,"m25p,fast-read?";
    };
};

config.txt 中的另一行

dtoverlay=at25:spimaxfrequency=50000000

我将省略将芯片连接到树莓派的描述。 一方面，我不是电子专家，另一方面，这里的一切即使对我来说也很平庸：微电路只有 8 个引脚，其中我们需要接地、电源、SPI（CS、SI、SO、 SCK）； 电平与 Raspberry Pi 的电平相同，无需额外接线 - 只需连接所示的 6 个引脚即可。

制定问题

像往常一样，问题陈述会经历多次迭代，在我看来，是时候进行下一次迭代了。 因此，让我们停下来，将已经写下的内容放在一起，并澄清仍然隐藏在阴影中的细节。

因此，我们决定将日志存储在SPI NOR Flash中。

对于那些不知道的人来说，NOR Flash 是什么？

这是非易失性存储器，您可以用它执行三种操作：

  1. 阅读：
    最常见的读取：我们传输地址并读取所需数量的字节；
  2. 记录：
    写入 NOR 闪存看起来与常规写入类似，但它有一个特点：只能将 1 更改为 0，反之则不行。 例如，如果我们在一个存储单元中有0x55，那么在写入0x0f之后，0x05将已经被存储在那里 （见下表）;
  3. 删除：
    当然，我们需要能够执行相反的操作——将0更改为1，这正是擦除操作的目的。 与前两者不同的是，它不是以字节为单位进行操作，而是以块为单位（所选芯片中的最小擦除块为4kb）。 擦除会破坏整个块，并且是将 0 更改为 1 的唯一方法。因此，在使用闪存时，您通常必须将数据结构与擦除块边界对齐。
    在 NOR Flash 中记录：

二进制数据

这是
01010101

已录制
00001111

它成了
00000101

日志本身代表可变长度的记录序列。 记录的典型长度约为 30 字节（尽管有时会出现长度为几千字节的记录）。 在本例中，我们只是将它们作为一组字节进行处理，但是，如果您感兴趣，可以在记录内使用 CBOR

除了日志之外，我们还需要存储一些“设置”信息，包括更新的和未更新的：某个设备 ID、传感器校准、“设备暂时禁用”标志等。
这些信息是一组键值记录，也存储在CBOR中，我们的这些信息并不多（最多几千字节），而且更新也不频繁。
下面我们将其称为上下文。

如果我们还记得本文的开头，那么确保可靠的数据存储以及（如果可能的话）即使在硬件故障/数据损坏的情况下也能持续运行是非常重要的。

可以考虑哪些问题根源？

  • 写/擦除操作期间断电。 这是属于“撬棍无招”的范畴。
    信息来自 讨论 on stackexchange：在使用闪存时关闭电源时，擦除（设置为 1）和写入（设置为 0）都会导致未定义的行为：数据可以写入，部分写入（例如，我们传输 10 字节/80 位） ，但还不能只写入 45 位），也有可能某些位将处于“中间”状态（读取可以同时产生 0 和 1）；
  • 闪存本身的错误。
    BER虽然很低，但不能等于XNUMX；
  • 总线错误
    通过 SPI 传输的数据不受任何方式的保护；单位错误和同步错误都可能发生 - 位丢失或插入（这会导致大量数据失真）；
  • 其他错误/故障
    代码错误、Raspberry 故障、外来干扰……

我已经制定了要求，我认为满足这些要求对于确保可靠性是必要的：

  • 记录必须立即进入闪存，不考虑延迟写入； - 如果发生错误，必须尽早检测和处理； - 如果可能，系统必须从错误中恢复。
    （生活中的一个“不应该这样”的例子，我想每个人都遇到过：紧急重启后，文件系统“损坏”，操作系统无法启动）

想法、方法、反思

当我开始思考这个问题时，我的脑海里闪过很多想法，例如：

  • 使用数据压缩；
  • 使用巧妙的数据结构，例如，将记录头与记录本身分开存储，这样，如果任何记录出现错误，您可以毫无问题地读取其余记录；
  • 使用位域来控制断电时记录的完成；
  • 存储所有内容的校验和；
  • 使用某种类型的抗噪声编码。

其中一些想法被采用，而另一些则被决定放弃。 我们按顺序走吧。

数据压缩

我们在日志中记录的事件本身非常相似且可重复（“扔了一枚 5 卢布的硬币”、“按下了找零的按钮”……）。 因此，压缩应该是相当有效的。

压缩开销微不足道（我们的处理器非常强大，即使是第一个Pi也有一个频率为700 MHz的核心，当前型号有几个频率超过千兆赫的核心），与存储的交换率较低（几个兆字节每秒），记录的大小很小。 一般来说，如果压缩对性能有影响，那么它只会是积极的。 （绝对不批判，只是陈述）。 另外，我们没有真正的嵌入式，而是常规的 Linux - 因此实现不需要太多的努力（只需链接库并使用其中的几个函数就足够了）。

从工作设备中取出一段日志（1.7 MB，70 个条目），并首先使用计算机上可用的 gzip、lz4、lzop、bzip2、xz、zstd 检查可压缩性。

  • gzip、xz、zstd 显示类似的结果 (40Kb)。
    令我惊讶的是，时尚的 xz 在 gzip 或 zstd 级别上出现了；
  • 使用默认设置的 lzip 结果稍差；
  • lz4 和 lzop 的结果不是很好（150Kb）；
  • bzip2 显示出令人惊讶的好结果（18Kb）。

因此，数据被很好地压缩。
所以（如果我们没有发现致命的缺陷）就会有压缩！ 仅仅是因为同一个闪存驱动器上可以容纳更多数据。

让我们考虑一下缺点。

第一个问题：我们已经同意每条记录必须立即转入闪存。 通常，归档器从输入流收集数据，直到它决定在周末进行写入为止。 我们需要立即接收压缩数据块并将其存储在非易失性存储器中。

我看到三种方法：

  1. 使用字典压缩而不是上面讨论的算法来压缩每个记录。
    这是一个完全可行的选择，但我不喜欢它。 为了确保或多或少合适的压缩级别，字典必须针对特定数据进行“定制”；任何更改都将导致压缩级别灾难性下降。 是的，可以通过创建新版本的字典来解决这个问题，但这很令人头痛——我们需要存储所有版本的字典； 在每个条目中，我们需要指出它是用哪个版本的字典压缩的......
  2. 使用“经典”算法压缩每个记录，但独立于其他算法。
    正在考虑的压缩算法不适用于这种大小（数十字节）的记录，压缩率显然会小于1（即增加数据量而不是压缩）；
  3. 每次录音后进行 FLUSH。
    许多压缩库都支持 FLUSH。 这是一个命令（或压缩过程的参数），归档器收到该命令后形成一个压缩流，以便可以使用它来恢复 所有 已收到的未压缩数据。 这样一个类似物 sync 在文件系统或 commit 在 SQL 中。
    重要的是，后续的压缩操作将能够使用累积的字典，并且压缩率不会像之前的版本那样受到太大影响。

我认为很明显我选择了第三个选项，让我们更详细地看看它。

成立 好文章 关于 zlib 中的 FLUSH。

我根据文章做了膝盖测试，从真机上取了70万条日志，页面大小为60Kb （我们稍后会回到页面大小） 已收到：

初始数据
压缩 gzip -9（无 FLUSH）
zlib 与 Z_PARTIAL_FLUSH
zlib 与 Z_SYNC_FLUSH

容量，KB
1692
40
352
604

乍一看，FLUSH 带来的代价过高，但实际上我们别无选择——要么根本不压缩，要么用 FLUSH 压缩（而且非常有效）。 我们不能忘记，我们有 70 万条记录，Z_PARTIAL_FLUSH 引入的冗余仅为每条记录 4-5 个字节。 压缩比接近 5:1，这是一个非常好的结果。

这可能会让人感到惊讶，但 Z_SYNC_FLUSH 实际上是一种更有效的 FLUSH 方法

当使用 Z_SYNC_FLUSH 时，每个条目的最后 4 个字节将始终为 0x00、0x00、0xff、0xff。 如果我们知道它们，那么我们就不必存储它们，所以最终的大小只有 324Kb。

我链接的文章有一个解释：

附加一个带有空内容的新类型 0 块。

具有空内容的 0 型块由以下部分组成：

  • 三位块头；
  • 0到7位等于XNUMX，实现字节对齐；
  • 四字节序列 00 00 FF FF。

正如您所看到的，在这 4 个字节之前的最后一个块中有 3 到 10 个零位。 然而实践表明，实际上至少有10个零位。

事实证明，这样短的数据块通常（总是？）使用类型 1 的块（固定块）进行编码，该块必然以 7 个零位结尾，总共提供 10-17 个保证的零位（其余的将为零的概率约为 50%）。

因此，在测试数据上，100%的情况下，0x00、0x00、0xff、0xff之前有一个零字节，而超过三分之一的情况下有两个零字节 （也许事实是我使用二进制 CBOR，并且当使用文本 JSON 时，类型 2 的块 - 动态块会更常见，分别会遇到在 0x00、0x00、0xff、0xff 之前没有附加零字节的块）.

总的来说，使用可用的测试数据，可以容纳小于 250Kb 的压缩数据。

您可以通过进行位杂耍来节省更多：现在我们忽略块末尾的一些零位的存在，块开头的一些位也不会改变......
但后来我坚定地决定停止，否则按照这个速度我最终可能会开发自己的存档器。

总的来说，根据我的测试数据，每次写入收到 3-4 个字节，压缩比超过 6:1。 老实说：我没想到会出现这样的结果；在我看来，任何比 2:1 更好的结果都已经证明了使用压缩的合理性。

一切都很好，但 zlib（deflate）仍然是一种古老的、当之无愧的、略显过时的压缩算法。 未压缩数据流的最后 32Kb 被用作字典这一事实在今天看起来很奇怪（也就是说，如果某个数据块与 40Kb 前输入流中的数据非常相似，那么它将再次开始归档，并且不会引用以前发生的情况）。 在时尚的现代归档器中，字典大小通常以兆字节而不是千字节为单位。

因此，我们继续对归档器进行小型研究。

接下来我们测试了 bzip2（请记住，在没有 FLUSH 的情况下，它显示出几乎 100:1 的出色压缩比）。 不幸的是，它在 FLUSH 中的表现非常差；压缩数据的大小比未压缩数据的大小要大。

我对失败原因的假设

Libbz2 仅提供一个刷新选项，该选项似乎会清除字典（类似于 zlib 中的 Z_FULL_FLUSH）；在此之后没有谈论任何有效的压缩。

最后一个要测试的是zstd。 根据参数的不同，它可以在 gzip 级别进行压缩，但比 gzip 更快或更好。

唉，FLUSH 的表现并不是很好：压缩数据的大小约为 700Kb。

Я 问了一个问题 在项目的github页面上，我收到了一个答案，你应该指望每块压缩数据最多有10字节的服务数据，这与获得的结果很接近；没有办法赶上deflate。

我决定在我的归档器实验中停止（让我提醒你，xz、lzip、lzo、lz4 即使在没有 FLUSH 的测试阶段也没有表现出来，而且我没有考虑更奇特的压缩算法）。

让我们回到归档问题。

第二个问题（正如他们所说的顺序，而不是价值）是压缩数据是单个流，其中不断引用前面的部分。 因此，如果压缩数据的一部分被损坏，我们不仅会丢失相关的未压缩数据块，还会丢失所有后续数据块。

有一个方法可以解决这个问题：

  1. 防止问题发生——向压缩数据添加冗余，这将使您能够识别并纠正错误； 我们稍后再讨论这个；
  2. 如果出现问题，尽量减少后果
    前面我们已经说过，你可以独立压缩每个数据块，问题就会自行消失（损坏一个块的数据，只会导致该块的数据丢失）。 然而，这是一种极端情况，数据压缩将无效。 相反的极端：将我们芯片的所有 4MB 用作单个存档，这将为我们提供出色的压缩效果，但如果数据损坏，则会带来灾难性的后果。
    是的，在可靠性方面需要做出妥协。 但我们必须记住，我们正在开发一种用于非易失性存储器的数据存储格式，具有极低的 BER，并且声明数据存储期限为 20 年。

在实验过程中，我发现压缩级别或多或少明显的损失始于大小小于 10 KB 的压缩数据块。
前面提到所使用的内存是分页的；我看不出为什么不应该使用“一页 - 一个压缩数据块”对应关系。

即，最小合理页面大小为 16Kb（保留服务信息）。 然而，如此小的页面大小对最大记录大小施加了很大的限制。

尽管我还不期望压缩形式的记录大于几千字节，但我决定使用 32Kb 页面（每个芯片总共 128 页）。

总结：

  • 我们存储使用 zlib (deflate) 压缩的数据；
  • 对于每个条目，我们设置 Z_SYNC_FLUSH；
  • 对于每个压缩记录，我们修剪尾随字节 （例如 0x00、0x00、0xff、0xff）; 在标头中，我们指出我们切断了多少字节；
  • 我们将数据存储在 32Kb 页中； 页面内有单个压缩数据流； 在每个页面上我们再次开始压缩。

而且，在完成压缩之前，我想提请您注意这样一个事实：每个记录只有几个字节的压缩数据，因此不要夸大服务信息非常重要，这里每个字节都很重要。

存储数据头

由于我们有可变长度的记录，因此我们需要以某种方式确定记录的位置/边界。

我知道三种方法：

  1. 所有记录都存储在连续流中，首先有一个包含长度的记录头，然后是记录本身。
    在该实施例中，报头和数据都可以是可变长度的。
    本质上，我们得到了一个一直使用的单链表；
  2. 标头和记录本身存储在单独的流中。
    通过使用恒定长度的标头，我们可以确保一个标头的损坏不会影响其他标头。
    例如，许多文件系统都使用类似的方法；
  3. 记录存储在连续的流中，记录边界由某个标记（数据块内禁止的字符/字符序列）确定。 如果记录中有标记，那么我们用一些序列替换它（转义它）。
    例如，PPP 协议中使用了类似的方法。

我会举例说明。

选项1：
我在 NOR 闪存中实现环形缓冲区
这里一切都很简单：知道了记录的长度，我们就可以计算出下一个标头的地址。 因此，我们浏览标题，直到遇到充满 0xff（空闲区域）的区域或页面末尾。

选项2：
我在 NOR 闪存中实现环形缓冲区
由于记录长度可变，我们无法提前确定每页需要多少条记录（以及标题）。 您可以将标题和数据本身分布在不同的页面上，但我更喜欢不同的方法：我们将标题和数据都放在一个页面上，但标题（大小恒定）来自页面的开头，并且数据（可变长度）来自末尾。 一旦它们“相遇”（没有足够的可用空间用于新条目），我们就认为该页面已完成。

选项3：
我在 NOR 闪存中实现环形缓冲区
无需在标头中存储有关数据位置的长度或其他信息；指示记录边界的标记就足够了。 然而，在写入/读取时必须对数据进行处理。
我会使用0xff作为标记（擦除后填充页面），因此空闲区域肯定不会被视为数据。

比较表：

选项1
选项2
选项3

容错
-
+
+

密度
+
-
+

实施的复杂性
*
**
**

选项1有一个致命的缺陷：如果任何一个标头被损坏，则整个后续链都会被破坏。 即使发生大规模损坏，其余选项也允许您恢复一些数据。
但在这里应该记住，我们决定以压缩形式存储数据，因此在“损坏”记录后我们会丢失页面上的所有数据，因此即使表中有负号，我们也不会考虑到这一点。

紧凑：

  • 在第一个选项中，我们只需要在标头中存储长度；如果我们使用可变长度整数，那么在大多数情况下我们可以用一个字节来满足；
  • 在第二个选项中，我们需要存储起始地址和长度； 记录必须是恒定大小，我估计每个记录 4 个字节（两个字节用于偏移量，两个字节用于长度）；
  • 第三个选项只需要一个字符来指示录音的开始，加上录音本身会因为屏蔽而增加1-2%。 一般来说，与第一个选项大致相同。

最初，我认为第二个选项是主要选项（甚至编写了实现）。 当我最终决定使用压缩时我才放弃它。

也许有一天我仍然会使用类似的选项。 例如，如果我必须处理一艘往返于地球和火星之间的船舶的数据存储，那么对于可靠性、宇宙辐射等会有完全不同的要求……

至于第三个选项：我给它两颗星是因为它的实施难度，只是因为我不喜欢乱搞屏蔽、改变过程的长度等。 是的，也许我有偏见，但我必须编写代码——为什么要强迫自己做一些你不喜欢的事情。

总结： 由于效率和易于实现，我们选择链形式的存储选项“长度标头-可变长度数据”。

使用位字段监控写入操作是否成功

我现在不记得我从哪里得到这个想法，但它看起来像这样：
对于每个条目，我们分配几个位来存储标志。
正如我们前面所说，擦除后所有位都被 1 填充，我们可以将 1 更改为 0，但反之则不行。 因此，对于“标志未设置”，我们使用 1，对于“标志已设置”，我们使用 0。

将可变长度记录放入闪存可能如下所示：

  1. 设置“长度记录已开始”标志；
  2. 记录长度；
  3. 设置“数据记录已开始”标志；
  4. 我们记录数据；
  5. 设置“录音结束”标志。

此外，我们还有一个“发生错误”标志，总共 4 位标志。

在这种情况下，我们有两个稳定状态“1111”-录制尚未开始和“1000”-录制成功； 如果记录过程意外中断，我们将收到中间状态，然后我们可以检测和处理这些状态。

这种方法很有趣，但它只能防止突然断电和类似的故障，这当然很重要，但这远不是可能发生故障的唯一（甚至是主要原因）原因。

总结： 让我们继续寻找好的解决方案。

校验和

校验和还可以确保（以合理的概率）我们正在准确地读取应该写入的内容。 而且，与上面讨论的位字段不同，它们始终有效。

如果我们考虑上面讨论的潜在问题来源列表，那么校验和就能够识别错误，无论其来源如何 （也许，对于恶意的外星人来说，他们也可以伪造校验和）.

因此，如果我们的目标是验证数据是否完整，那么校验和是一个好主意。

计算校验和的算法的选择没有引起任何问题 - CRC。 一方面，数学特性使得 100% 捕获某些类型的错误成为可能；另一方面，对于随机数据，该算法通常显示的碰撞概率不会比理论极限大很多 我在 NOR 闪存中实现环形缓冲区。 它可能不是最快的算法，也不总是碰撞次数最少的算法，但它有一个非常重要的品质：在我遇到的测试中，没有任何模式明显失败。 在这种情况下，稳定性是主要品质。

体积研究示例： 部分1, 部分2 （链接到 narod.ru，抱歉）.

然而，选择校验和的任务还没有完成；CRC 是一个完整的校验和系列。 您需要确定长度，然后选择一个多项式。

选择校验和长度并不像乍看起来那么简单。

让我举例说明：
让我们计算每个字节出现错误的概率 我在 NOR 闪存中实现环形缓冲区 和理想的校验和，让我们计算每百万条记录的平均错误数：

数据，字节
校验和，字节
未检测到的错误
错误检测
误报总数

1
0
1000
0
1000

1
1
4
999
1003

1
2
≈0
1997
1997

1
4
≈0
3990
3990

10
0
9955
0
9955

10
1
39
990
1029

10
2
≈0
1979
1979

10
4
≈0
3954
3954

1000
0
632305
0
632305

1000
1
2470
368
2838

1000
2
10
735
745

1000
4
≈0
1469
1469

看起来一切都很简单 - 根据受保护数据的长度，选择错误肯定最少的校验和长度 - 技巧就在袋中。

然而，短校验和会出现一个问题：尽管它们擅长检测单位错误，但它们可以以相当高的概率接受完全随机的数据作为正确的数据。 已经有一篇关于 Habré 的文章描述了 现实生活中的问题.

因此，要使随机校验和匹配几乎不可能，您需要使用长度为 32 位或更长的校验和。 （对于长度大于64位，通常使用加密哈希函数）.

尽管我之前写过我们需要通过各种方式节省空间，但我们仍然会使用 32 位校验和（16 位还不够，冲突的概率超过 0.01%；而 24 位，因为它们说，既不在这里也不在那里）。

这里可能会出现一个反对意见：我们在选择压缩时是否保存了每个字节，以便现在一次提供 4 个字节？ 不压缩或添加校验和不是更好吗？ 当然不是，没有压缩 并不意味着，我们不需要完整性检查。

在选择多项式时，我们不会重新发明轮子，而是采取现在流行的CRC-32C。
此代码可检测最多 6 字节的数据包上的 22 位错误（可能是我们最常见的情况）、最多 4 字节的数据包上的 655 位错误（这也是我们的常见情况）、数据包上的 2 个或任何奇数个位错误任何合理的长度。

如果有人对细节感兴趣

维基百科文章 关于CRC。

代码参数crc-32c 上 考夫曼网站 — 也许是地球上领先的 CRC 专家。

В 他的文章 有 另一个有趣的代码，它为与我们相关的数据包长度提供了稍微更好的参数，但我认为差异并不显着，并且我有足够的能力选择自定义代码而不是标准且经过充分研究的代码。

另外，由于我们的数据是压缩的，因此出现了问题：我们应该计算压缩数据还是未压缩数据的校验和？

支持计算未压缩数据校验和的论点：

  • 我们最终需要检查数据存储的安全性——所以我们直接检查（同时会检查压缩/解压执行中可能出现的错误、内存损坏造成的损坏等）；
  • zlib中的deflate算法有相当成熟的实现 不应该 与“弯曲”的输入数据有关；此外，它通常能够独立检测输入流中的错误，从而降低未检测到错误的总体概率（通过反转短记录中的单个位进行测试，zlib 检测到错误）大约三分之一的情况）。

反对计算未压缩数据校验和的论点：

  • CRC 是专门针对闪存特有的少数位错误而“定制”的（压缩流中的位错误可能会导致输出流发生巨大变化，纯粹从理论上讲，我们可以“捕获”冲突）；
  • 我真的不喜欢将可能损坏的数据传递给解压缩器的想法， 谁知道他会如何反应。

在这个项目中，我决定偏离存储未压缩数据校验和的普遍接受的做法。

总结： 我们使用 CRC-32C，根据写入闪存（压缩后）的数据形式计算校验和。

冗余

当然，使用冗余编码并不能消除数据丢失，但是，它可以显着（通常是多个数量级）降低不可恢复的数据丢失的可能性。

我们可以使用不同类型的冗余来纠正错误。
汉明码可以纠正单位错误，里德-所罗门字符代码、与校验和相结合的多个数据副本或 RAID-6 等编码可以帮助恢复数据，即使在发生大规模损坏的情况下也是如此。
最初，我致力于广泛使用防错编码，但后来我意识到，我们首先需要了解我们想要保护自己免受哪些错误的影响，然后再选择编码。

我们之前说过，需要尽快捕获错误。 我们在什么时候会遇到错误？

  1. 未完成的录音（由于某种原因，录音时电源被关闭，Raspberry 冻结了，...）
    唉，如果发生这样的错误，剩下的就是忽略无效记录并考虑数据丢失；
  2. 写入错误（由于某种原因，写入闪存的内容与实际写入的内容不同）
    如果我们在录制后立即进行测试读取，我们可以立即检测到此类错误；
  3. 内存中的数据在存储过程中发生失真；
  4. 读取错误
    为了纠正它，如果校验和不匹配，重复读取几次就足够了。

也就是说，只有第三种类型的错误（存储过程中数据的自发损坏）在没有抗错编码的情况下无法被纠正。 看来这样的错误还是极不可能发生的。

总结： 决定放弃冗余编码，但如果操作显示该决定是错误的，则返回到对该问题的考虑（已经积累了失败的统计数据，这将允许选择最佳的编码类型）。

其他

当然，文章的格式不允许我们证明格式中的每一位都是合理的 （而我的力气已经耗尽了），所以我将简要回顾一下之前未提及的一些要点。

  • 决定让所有页面“平等”
    也就是说，不会有带有元数据的特殊页面、单独的线程等，而是由单个线程依次重写所有页面。
    这确保了页面的均匀磨损，没有单点故障，我就是喜欢它；
  • 必须提供格式的版本控制。
    标头中没有版本号的格式是邪恶的！
    在页眉中添加一个具有特定幻数（签名）的字段就足够了，该字段将指示所使用格式的版本 （我认为实际上不会有十几个）;
  • 对记录（有很多）使用可变长度标头，在大多数情况下尝试使其长度为 1 个字节；
  • 要对压缩记录的标头长度和修剪部分的长度进行编码，请使用可变长度二进制代码。

帮助了很多 在线生成器 霍夫曼编码。 在短短几分钟内，我们就能够选择所需的可变长度代码。

数据存储格式说明

字节顺序

大于0字节的字段采用big-endian格式（网络字节序）存储，即1234x0写为12x0、34xXNUMX。

分页

所有闪存都分为大小相等的页。

默认页面大小为32Kb，但不超过内存芯片总大小的1/4（对于4MB芯片，获得128个页面）。

每个页面独立于其他页面存储数据（即，一个页面上的数据不引用另一页面上的数据）。

所有页面均按自然顺序（按地址升序）编号，从数字 0 开始（第 0 页从地址 32 开始，第一页从 64Kb 开始，第二页从 XNUMXKb 开始，依此类推）

内存芯片用作循环缓冲区（环形缓冲区），即首先写入第0页，然后第1页，……，当我们写满最后一页时，新的循环开始，从第XNUMX页继续记录。

页面内

我在 NOR 闪存中实现环形缓冲区
在页的开头，存储4字节的页头，然后是页头校验和(CRC-32C)，然后以“页头、数据、校验和”的格式存储记录。

页面标题（图中为脏绿色）包含：

  • 两字节幻数字段（也是格式版本的标志）
    对于格式的当前版本，其计算方式为 0xed00 ⊕ номер страницы;
  • 两字节计数器“页面版本”（内存重写周期数）。

页面上的条目以压缩形式存储（使用 deflate 算法）。 一页上的所有记录都在一个线程中压缩（使用通用字典），并且在每个新页面上重新开始压缩。 也就是说，要解压缩任何记录，需要该页面的所有先前记录（并且仅此一条）。

每个记录都将使用 Z_SYNC_FLUSH 标志进行压缩，并且在压缩流的末尾将有 4 个字节 0x00、0x00、0xff、0xff，前面可能还有一两个零字节。
当写入闪存时，我们会丢弃该序列（4、5 或 6 字节长）。

记录头为 1、2 或 3 个字节，存储：

  • 一位（T）指示记录类型：0 - 上下文，1 - 日志；
  • 1 到 7 位的可变长度字段 (S)，定义必须添加到记录以进行解压缩的标头和“尾部”的长度；
  • 记录长度（L）。

S值表：

S
标头长度，字节
写入时丢弃，字节

0
1
5分(00 00 00 ff ff)

10
1
6分(00 00 00 00 ff ff)

110
2
4分(00 00 ff ff)

1110
2
5分(00 00 00 ff ff)

11110
2
6分(00 00 00 00 ff ff)

1111100
3
4分(00 00 ff ff)

1111101
3
5分(00 00 00 ff ff)

1111110
3
6分(00 00 00 00 ff ff)

我试图说明，我不知道结果有多清楚：
我在 NOR 闪存中实现环形缓冲区
这里黄色表示T字段，白色表示S字段，绿色L（压缩数据的长度，以字节为单位），蓝色表示压缩数据，红色表示未写入闪存的压缩数据的最后字节。

因此，我们可以在一个字节中写入最常见长度的记录头（压缩形式最多为 63+5 字节）。

每条记录之后都会存储一个 CRC-32C 校验和，其中将前一个校验和的反转值用作初始值（init）。

CRC具有“持续时间”的属性，其计算公式如下（过程中加上或减去位反转）： 我在 NOR 闪存中实现环形缓冲区.
也就是说，实际上我们计算了该页上所有前一个字节的标头和数据的 CRC。

紧跟在校验和之后的是下一条记录的标头。

标头的设计方式使其第一个字节始终不同于 0x00 和 0xff（如果我们遇到的不是标头的第一个字节 0xff，则意味着这是一个未使用的区域；0x00 表示错误）。

算法示例

从闪存读取

任何读数都带有校验和检查。
如果校验和不匹配，则重复读取多次，希望读取到正确的数据。

（这是有道理的，Linux 不会缓存从 NOR Flash 读取的数据，经过测试）

写入闪存

我们记录数据。
让我们来读读它们。

如果读取的数据与写入的数据不匹配，我们将用零填充该区域并发出错误信号。

准备新的微电路以供操作

为了初始化，版本 1 的标头被写入第一页（或者更确切地说零页）。
之后，初始上下文将写入此页面（包含计算机的 UUID 和默认设置）。

就这样，闪存就可以使用了。

装载机器

加载时，读取每页的前 8 个字节（标头 + CRC），忽略具有未知幻数或不正确 CRC 的页面。
从“正确”的页面中，选择具有最大版本的页面，并从中取出具有最高版本号的页面。
读取第一条记录，检查 CRC 的正确性以及“上下文”标志是否存在。 如果一切正常，则该页面被视为当前页面。 如果没有，我们回滚到上一页，直到找到“实时”页面。
在找到的页面上，我们读取所有记录，即那些与“上下文”标志一起使用的记录。
保存 zlib 字典（添加到此页面时需要它）。

就这样，下载完成，上下文恢复，可以工作了。

添加日记条目

我们使用正确的字典压缩记录，指定Z_SYNC_FLUSH。我们看看压缩的记录是否适合当前页面。
如果不适合（或者页面上存在 CRC 错误），请开始一个新页面（见下文）。
我们记下记录和CRC。 如果发生错误，则开始新页面。

新一页

我们选择一个具有最小数量的空闲页面（我们认为空闲页面是标头中校验和不正确或版本低于当前版本的页面）。 如果没有这样的页面，则从版本等于当前版本的页面中选择编号最小的页面。
我们删除选定的页面。 我们用0xff检查内容。 如果出现问题，请获取下一个空闲页面，依此类推。
我们在擦除的页面上写入一个标头，第一个条目是上下文的当前状态，下一个是未写入的日志条目（如果有的话）。

格式适用性

在我看来，它是在 NOR Flash 中存储任何或多或少可压缩信息流（纯文本、JSON、MessagePack、CBOR，可能是 protobuf）的良好格式。

当然，该格式是为SLC NOR Flash“量身定制”的。

它不应该与高 BER 介质（例如 NAND 或 MLC NOR）一起使用 （这样的内存还有卖吗？我只在修正码的著作中看到过）.

此外，它不应该与有自己的 FTL 的设备一起使用：USB 闪存、SD、MicroSD 等 （对于这样的内存，我创建了一种页面大小为 512 字节的格式，每页开头都有一个签名和唯一的记录号 - 有时可以通过简单的顺序读取从“故障”闪存驱动器中恢复所有数据）.

根据任务的不同，该格式可以在 128Kbit (16Kb) 到 1Gbit (128MB) 的闪存驱动器上使用，无需更改。 如果需要，您可以在更大的芯片上使用它，但您可能需要调整页面大小 （但这里已经出现了经济可行性的问题；大容量NOR Flash的价格并不令人鼓舞）.

如果有人发现这种格式很有趣并且想在开放项目中使用它，请写下来，我会尽力找到时间，完善代码并将其发布到 github 上。

结论

正如你所看到的，最终格式变得很简单 甚至无聊.

在一篇文章中很难反映我观点的演变，但请相信我：最初我想创造一些复杂的、坚不可摧的东西，甚至能够在近距离的核爆炸中幸存下来。 然而，理性（我希望）仍然获胜，并且优先事项逐渐转向简单和紧凑。

难道是我错了？ 是的，当然。 例如，很可能我们购买了一批低质量的微电路。 或者由于某些其他原因，设备将无法满足可靠性预期。

我有这方面的计划吗？ 我想，读完这篇文章，你就不会怀疑有一个计划了。 甚至不是独自一人。

稍微严肃一点的是，该格式既作为一种工作选项又作为“试用气球”而开发。

目前，桌面上的一切都运行良好，实际上，有一天该解决方案将被部署 （大约） 在数百台设备上，让我们看看“战斗”操作中会发生什么（幸运的是，我希望该格式可以让您可靠地检测故障；这样您就可以收集完整的统计数据）。 几个月后就能得出结论 （如果你运气不好，甚至更早）.

如果根据使用结果发现严重问题需要改进，那么我一定会写出来。

文学

我不想列出一长串乏味的二手作品清单；毕竟，每个人都有谷歌。

在这里，我决定留下一系列对我来说特别有趣的发现，但逐渐地它们直接迁移到文章的正文中，并且列表中保留了一个项目：

  1. 效用 基因 来自作者 zlib。 可以清晰显示deflate/zlib/gzip压缩包的内容。 如果您必须处理 deflate（或 gzip）格式的内部结构，我强烈推荐它。

来源： habr.com

添加评论