背景知识

有我们自己设计的自动售货机。 在Raspberry Pi的内部，并且在单独的板上有一些捆扎带。 一个硬币接收器，一个纸币接收器，一个银行终端被连接起来。一个自写的程序管理着所有东西。 作品的全部历史记录都记录在USB闪存驱动器（MicroSD）上的杂志上，然后通过Internet（使用USB调制解调器）传输到服务器，然后将其添加到数据库中。 销售信息以1s加载，还有一个简单的Web界面，用于监控等。

也就是说，杂志对于会计（有收入，销售等），监控（各种故障和其他不可抗力情况）至关重要。 您可以说，这是我们拥有的有关该机器的所有信息。

问题

闪存驱动器显示为非常不可靠的设备。 他们以令人羡慕的规律性失败。 这既导致机器停机，又导致（如果由于某种原因无法在线传输日志）数据丢失。

这不是使用闪存驱动器的第一次体验，在此之前，还有另一个项目将一百多个设备存储在USB闪存驱动器中，还存在可靠性问题，有时每月的故障次数为数十次。 我们尝试了不同的闪存驱动器，包括SLC内存上的品牌闪存驱动器，某些型号比其他型号更可靠，但是更换闪存驱动器并不能从根本上解决问题。

注意！ 隆里德！ 如果您对“为什么”不感兴趣，而仅对“如何”感兴趣，则可以立即转到文章末尾 。

解决方案

首先想到的是：放弃MicroSD，放入SSD，然后从中启动。 从理论上讲，这是可能的，但可能相对昂贵，而且不够可靠（添加了USB-SATA适配器；在预算有限的SSD上，故障统计也不理想）。

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

因此，我们选择了以下选项：保留从MicroSD下载的内容，但以只读模式使用它们，并将操作日志（以及特定硬件特有的其他信息-序列号，传感器校准等）存储在其他位置。

覆盆子只读FS的主题已经被广泛研究，我不会在本文中详细介绍实现的细节（但是，如果有兴趣的话，也许我会写一个关于该主题的迷你文章） 。 我要指出的唯一一点是：从个人经验和已经实现可靠性方面获得的评论来看。 是的，不可能完全消除故障，但是有可能大大减少故障发生的频率。 是的，并且卡变得统一了，这极大地简化了维护人员的更换。

硬体

毫无疑问，内存类型的选择-NOR Flash。
参数：

• 简单的连接（最常用的是SPI总线，已经有使用经验，因此不会出现“铁”问题）；
• 荒谬的价格
• 标准操作协议（该实现已在Linux内核中，如果需要，您可以使用也存在的第三方，甚至编写自己的第三方，好处很简单）；
• 可靠性和资源：
  根据典型的数据表：数据存储20年，每个块100,000个擦除周期；
  来自第三方的消息：BER极低，假设不需要纠错码（在某些论文中考虑了NOR的ECC，但通常是MLC NOR的意思） 。

让我们估算数量和资源需求。

我想保证可以保存几天的数据。 这是必要的，以便在连接出现任何问题时不会丢失销售历史记录。 我们将专注于5天，在此期间（即使考虑到周末和节假日），我们也可以解决问题。

现在，我们每天要输入约100kb的杂志（3-4千条记录），但是这个数字正在逐渐增加-详细信息在增加，新事件也在增加。 另外，有时还会爆发（例如，某些传感器以误报的形式开始发送垃圾邮件）。 我们将每天计算100字节-兆字节的1万条记录。

总共出现5 MB的干净（可压缩）数据。 他们还（粗略估计） 1MB的服务数据。

也就是说，如果您不使用压缩功能，则需要一个8MB的芯片，如果您不使用压缩功能，则需要4MB的芯片。 这种类型的内存相当实数。

至于资源：如果我们计划每5天不超过一次重写整个内存，那么在使用10年后，我们将获得不到一千次的重写周期。
我记得，制造商承诺十万。

如果细节令人感兴趣，则选择了at25df321a芯片（但是，这无关紧要，市场上有许多与引脚和命令系统兼容的类似物;即使我们想将芯片从另一个制造商和/或另一个体积放进去，也可以在不更改代码的情况下工作） 。

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

/* * 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?"; }; }; 

 dtoverlay=at25:spimaxfrequency=50000000 

我将省略将芯片连接到Raspberry Pi的描述。 一方面，我不是电子学专家，另一方面，即使对我来说，一切也微不足道：微电路只有8条支脚，其中我们需要接地，电源，SPI（CS，SI，SO，SCK）； 级别与Raspberry Pi的级别一致，不需要其他绑定-只需连接指定的6个触点即可。

问题陈述

像往常一样，问题的提出经历了多次迭代，在我看来，下一次迭代的时机已到。 因此，让我们停下来，汇总已写的内容，并弄清阴影中剩余的细节。

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

日志本身代表一系列可变长度的记录。 典型的记录长度约为30个字节（尽管有时会记录几千个字节）。 在这种情况下，我们就像处理一组字节一样使用它们，但是，如果您有兴趣，可以在记录内使用CBOR。

除了日志之外，我们还需要存储一些“调整”信息，无论是否已更新：某个设备ID，传感器校准，“设备被暂时禁用”标志等。
此信息是一组键值记录，也存储在CBOR中，我们没有太多此类信息（最大几千字节），因此不经常更新。
将来，我们将其称为上下文。

如果您想起本文开始的地方，那么即使在发生硬件故障/数据损坏的情况下，确保数据存储的可靠性以及在可能的情况下连续运行也非常重要。

可以考虑哪些问题来源？

• 在写/擦除操作期间关闭电源。 这是来自“反对废品收货”的类别。
  来自堆栈交换讨论的信息：使用闪存工作时关闭电源时，擦除（设置为1），写入（设置为0）会导致未定义的行为：数据可以被写入，也可以部分写入（例如，我们传输了10字节/ 80位，并且仅记录了45个位），其中某些位也可能处于“中间”状态（读取会产生0或1）；
• 闪存本身的错误。
  BER虽然很低，但不能等于零。
• 巴士错误
  通过SPI传输的数据没有受到任何保护，很可能会发生单位错误或同步错误-丢失或插入位（导致大量数据失真）；
• 其他错误/失败
  代码错误，Raspberry“故障”，外星人干预...

我制定了一些要求，我认为必须满足这些要求才能确保可靠性：

• 记录应立即写入闪存，不考虑挂起的记录；-如果发生错误，应尽快对其进行检测和处理；-如果可能，系统应从错误中恢复。
  （我想，每个人都遇到过这样的例子：“紧急情况”，紧急重启后，文件系统“崩溃”，操作系统无法启动）

想法，方法，思想

当我开始考虑此任务时，我的脑海中浮现出许多想法，例如：

• 使用数据压缩
• 使用棘手的数据结构，例如，将记录标题与记录本身分开存储，这样，如果记录中发生错误，则可以读取其余记录而不会出现任何问题；
• 当电源关闭时，使用位域控制记录的完整性；
• 存储所有内容的校验和；
• 使用某种纠错编码。

其中一些想法被使用，有些决定被拒绝。 让我们去吧。

资料压缩

我们在日记本中记录的事件是完全相同且可重复的（“投了5卢布硬币”，“单击了更改交付按钮”，...）。 因此，压缩应该非常有效。

压缩的开销微不足道（我们拥有的处理器非常强大，即使在第一个Pi上也有一个核心频率为700 MHz，在当前型号上有几个核心的频率超过了千兆赫），与存储的交换速度很低（每秒几兆字节），记录大小很小。 通常，如果压缩会影响性能，则仅是肯定的（绝对不重要，仅说明一下） 。 另外，我们没有真正的嵌入式系统，而是普通的Linux-因此实现不需要太多工作（只需链接库并使用其中的几个功能）。

从工作设备中提取了一部分日志（1.7 MB，7万条记录），并使用计算机上提供的gzip，lz4，lzop，bzip2，xz，zstd首先检查了压缩性。

• gzip，xz，zstd显示了相似的结果（40Kb）。
  令我惊讶的是，时尚的xz在gzip或zstd级别显示了出来。
• 使用默认设置的lzip给出的结果稍差一些；
• lz4和lzop显示的效果不是很好（150Kb）；
• bzip2显示出令人惊讶的良好结果（18Kb）。

因此，数据压缩得很好。
因此（如果我们没有发现致命的缺陷）应该进行压缩！ 只是因为更多数据可以容纳在同一闪存驱动器上。

让我们考虑一下这些缺陷。

第一个问题：我们已经同意，每条记录应立即刷新。 通常，存档器会从输入流中收集数据，直到决定是时候写入输出为止。 我们需要立即获取压缩的数据块并将其保存在非易失性存储器中。

我看到三种方式：

1. 使用字典压缩而不是上面讨论的算法来压缩每个条目。
   这是一个可行的选择，但我不喜欢它。 为了确保大致适当的压缩水平，应针对特定数据对字典进行“锐化”，任何更改都将导致压缩水平灾难性地下降。 是的，可以通过创建字典的新版本来解决问题，但这令人头疼-我们将需要存储字典的所有版本； 在每个条目中，我们将需要指出它是用哪个版本的字典压缩的...
2. 使用“经典”算法压缩每个条目，但与其他算法无关。
   所考虑的压缩算法不适用于这种大小（数十个字节）的记录，压缩系数显然小于1（即，数据量增加而不是压缩）；
3. 每次录音后都要冲洗。
   许多压缩库都支持FLUSH。 这是一个命令（或压缩过程的参数），存档器在接收到该命令时会生成压缩流，以便可以基于其恢复所有已接收的未压缩数据。 在文件系统或sql中进行sync此类模拟。
   重要的是，后续的压缩操作将能够使用累积的词典，并且压缩率不会像以前的版本那样受苦。

我认为很明显，我选择了第三个选项，让我们对其进行更详细的介绍。

zlib中有一篇很棒的关于FLUSH的文章 。

我根据该文章进行了动机测试，从一个真实的设备中获取了7万条日记条目，页面大小为60Kb （我们将返回页面大小） ：

乍一看，FLUSH引入的价格过高，但实际上我们的选择很差-要么根本不压缩，要么用FLUSH压缩（非常有效）。 不要忘记我们有7万条记录，Z_PARTIAL_FLUSH引入的冗余每个记录只有4-5个字节。 压缩比几乎达到5：1，这比出色的结果还要好。

总的来说，我从测试数据中得到每条记录3-4个字节，压缩率大于6：1。 老实说，我没有指望得到这样的结果，我认为所有优于2：1的结果都已经证明使用压缩是合理的。

一切都很好，但是zlib（放气）仍然 古老的 当之无愧的老式压缩算法。 今天，将未压缩的数据流中的最后32Kb用作字典这一纯粹的事实看起来很奇怪（也就是说，如果某个数据块与输入流40Kb中的数据块非常相似，它将开始再次存档，但不会被存档）请参阅过去的条目）。 在 时髦的 现代档案大小词典通常以兆字节而不是千字节为单位。

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

接下来测试了bzip2（回想一下，没有FLUSH，它显示了惊人的压缩率，几乎为100：1）。 FL，使用FLUSH时，其显示效果非常差，压缩数据的大小大于未压缩数据的大小。

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

las，使用FLUSH证明他“不是很好”：压缩数据的大小约为700Kb。

我在github上的项目页面上问了一个问题 ，我收到了一个答案，它值得指望每个压缩数据块最多包含10个字节的服务数据，这接近结果，捕获deflate不起作用。

我决定在与存档程序进行的实验中停止此操作（我想提醒您，即使在没有FLUSH的测试阶段，xz，lzip，lzo，lz4也不显示自己的位置，但我没有考虑更多的外来压缩算法）。

我们回到存档的问题。

第二个问题（正如他们说的那样，但不是价值问题）-压缩数据是单个流，其中不断向前几部分发送数据。 因此，当压缩数据的一部分损坏时，我们不仅会丢失与之关联的未压缩数据块，还会丢失所有后续数据块。

有一种解决此问题的方法：

1. 防止出现问题-向压缩数据添加冗余，这将允许识别和纠正错误； 我们稍后再讨论；
2. 出现问题时将后果降到最低
   前面我们已经说过，可以独立地压缩每个数据块，并且问题将自行消失（一个块的数据损坏将导致仅该块的数据丢失）。 但是，在极端情况下，数据压缩效率很低。 相反的极端情况：将我们所有4MB的微电路用作单个存档，这将为我们提供出色的压缩效果，但在数据损坏的情况下带来灾难性后果。
   是的，在可靠性方面需要折衷。 但是我们必须记住，我们正在为非易失性存储器开发一种数据存储格式，它具有极低的BER和声明的20年的数据存储期。

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

也就是说，最小合理页面大小为16Kb（有一定的服务信息余量）。 但是，如此小的页面大小对最大记录大小施加了很大的限制。

尽管我仍然不希望以压缩形式记录更多单位的千字节，但我还是决定使用32KB页（每个芯片总共128页）。

总结：

• 我们存储使用zlib（deflate）压缩的数据；
• 对于每个记录，设置Z_SYNC_FLUSH;
• 对于每个压缩的记录，我们都会修剪最后的字节（例如0x00、0x00、0xff，0xff） ； 标头中指出我们削减了多少个字节；
• 我们将数据存储在32Kb页面中； 页面内只有一个压缩数据流； 在每个页面上，我们再次开始压缩。

并且，在完成压缩之前，我想提请注意一个事实，即我们仅获得几个字节的写数据，因此，不要虚增服务信息，每个字节都要计数，这一点非常重要。

存储数据头

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

我知道三种方法：

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

我会举例说明。

选项1：

一切都非常简单：知道记录的长度，我们可以计算下一个标头的地址。 因此，我们遍历标题，直到遇到填充有0xff的区域（自由区域）或页面的末尾。

选项2：

由于记录长度的变化，我们无法提前说出每页需要多少条记录（因此还有标题）。 您可以将标头和数据本身散布到不同的页面中，但是我更喜欢另一种方法：我们将标头和数据放在同一页上，但是，标头（大小固定）来自页面的开头，数据（长度可变）来自结尾。 他们“见面”（没有足够的可用空间来存储新记录）后，我们认为此页面已满。

选项3：

不需要在标题中存储有关数据位置的长度或其他信息，没有足够的标记指示记录的边界。 但是，在写入/读取时必须处理数据。
作为标记，我将使用0xff（擦除后会填满页面），因此，空闲区域绝对不会被视为数据。

比较表：

选项1有一个致命的缺陷：如果任何标头损坏，那么我们随后的整个链条都将被破坏。 其他选项使您即使受到严重破坏也可以恢复部分数据。
但是在这里应该回想一下，我们决定以压缩形式存储数据，因此我们在“破损”记录之后丢失了页面上的所有数据，因此即使表中有减号，我们也不会考虑。

紧凑性：

• 在第一个版本中，我们只需要在标头中存储长度，如果使用可变长度的整数，那么在大多数情况下，我们可以使用一个字节；
• 在第二个选项中，我们需要存储起始地址和长度； 记录应为恒定大小，我估计每条记录4个字节（每个偏移量两个字节，每个长度两个字节）；
• , - 1-2%. .

( ). , .

, - - . , , — , , ...

: , , .. , , , — , .

: " — " - .

, , :
.
, erase 1, 1 0, . " " 1, " " — 0.

flash:

1. “ ”;
2. ;
3. “ ”;
4. ;
5. “ ”.

, “ ”, 4 .

“1111” — “1000” — ; , .

, , , , , ( ) .

: .

( ) , . , , .

, , ( , , — ) .

, , , — .

— CRC. , 100% , — $$$2^{-n}$。 , , : , . — .

: 1 , 2 ( narod.ru, ) .

, CRC — . , .

, .

:
$$$10^{-3}$, :

, — — .

, : , , . , .

, , 32 ( 64 -) .

, , , - 32- (16 , 0.01%; 24 , , ).

: , 4 ? ? , , .

, CRC-32C.
6 22 (, c), 4 655 ( ), 2 .

, , : ?

"" :

• — ( /, , ..);
• deflate zlib "" , , , ( , zlib ).

"" :

• CRC "" , - ( , , , "" );
• , , .

.

: CRC-32C, , flash ( ).

, , , , ( ) .

, .
, - , RAID-6 .
, , , .

, . ?

1. ( - , Raspberry, ...)
   , ;
2. ( - flash- , )
   , ;
3. ;
4. 
   .

( ) . , - .

: , , , ( , ).

, ( ) , , .

• ""
  - , .., , .
  , , ;
• .
  — !
  Magic Number (), ( , ) ;
• ( ) , 1 ;
• .

- . .

Byte order

, , big-endian (network byte order), 0x1234 0x12, 0x34.

- .

32, , 1/4 ( 4 128 ).

( ).

( ), 0 ( 0, — 32, — 64 ..)

(ring buffer), 0, 1, ..., , .

4- , (CRC-32C), ", , ".

( -) :

• Magic Number ( — )
  0xed00 ⊕ ;
• " " ( ).

( deflate). ( ), . ( ).

Z_SYNC_FLUSH, 4 0x00, 0x00, 0xff, 0xff, , , .
( 4, 5 6 ) -.

1, 2 3 , :

• (T), : 0 — , 1 — ;
• (S) 1 7 , "", ;
• (L).

S:

, , :

T, — S, L ( ), — , — , -.

, ( 63+5 ) .

CRC-32C, (init) .

CRC "", (- ) : $$$CRC(init, A || B) = CRC(CRC(init, A), B)$.
CRC .

.

, 0x00 0xff ( 0xff, ; 0x00 ).

-

.
— - .

( , Linux NOR Flash, )

-

.
.

— .

( ) 1.
( UUID ).

, - .

8 ( + CRC), Magic Number CRC .
"" , , .
, CRC, "". — . — , "" .
, , "" .
zlib ( ).

, , , .

, Z_SYNC_FLUSH., .
( CRC) — (. ).
CRC. — .

( ). — , .
erase. 0xff. - — , ..
, , — ( ).

, - ( , JSON, MessagePack, CBOR, , protobuf) NOR Flash.

, "" SLC NOR Flash.

BER, NAND MLC NOR ( ? ) .

, , FTL: USB flash, SD, MicroSD, etc ( 512 , — "" ) .

128 (16) 1 (128). , , , ( , NOR Flash ) .

- , — , , github.

结论

, .

, : - , , . , () - .

, ? 当然可以 , , . - .

? , , . .

, , " ".

, () , , "" (, , ; ). ( — ) .

, .

文学作品

, .

, , , :

1. infgen zlib. deflate/zlib/gzip. deflate ( gzip) — .