背景

自社デザインの自動販売機もございます。 Raspberry Pi の内部と別のボード上のいくつかの配線。コインアクセプタ、紙幣アクセプタ、銀行端末が接続されており、すべてが自作のプログラムによって制御されています。作業履歴全体はフラッシュ ドライブ (MicroSD) 上のログに書き込まれ、インターネット (USB モデムを使用) 経由でサーバーに送信され、データベースに保存されます。販売情報は 1c にロードされ、監視などのための簡単な Web インターフェイスもあります。

つまり、仕訳帳は会計 (収益、売上など)、監視 (あらゆる種類の失敗やその他の不可抗力状況) にとって不可欠です。これが、このマシンについて私たちが知っているすべての情報であると言えるかもしれません。

問題

フラッシュ ドライブは、非常に信頼性の低いデバイスであることがわかります。彼らはうらやましいほど定期的に失敗します。これにより、マシンのダウンタイムと (何らかの理由でログをオンラインで転送できなかった場合) データ損失の両方が発生します。

フラッシュ ドライブを使用するのはこれが初めての経験ではありません。これより前には、雑誌が USB フラッシュ ドライブに保存されていた 100 台以上のデバイスを使用する別のプロジェクトがありました。信頼性にも問題があり、失敗したデバイスの数が多かったです。 1か月は数十でした。 SLC メモリを搭載したブランド品など、さまざまなフラッシュ ドライブを試しましたが、一部のモデルは他のモデルよりも信頼性が高くなりますが、フラッシュ ドライブを交換しても問題は根本的に解決されませんでした。

警告！ 長く読んでください！ 「なぜ」には興味がなく、「どのように」だけに興味がある場合は、そのまま進んでください。 最終的には 記事。

ソリューション

最初に思い浮かぶのは、MicroSD を放棄し、たとえば SSD を取り付けて、そこから起動することです。おそらく理論的には可能ですが、比較的高価で、信頼性もそれほど高くありません (USB-SATA アダプターが追加されます。低予算 SSD の障害統計も期待できるものではありません)。

USB HDD も、特に魅力的なソリューションとは思えません。

したがって、MicroSD からの起動はそのままにして、読み取り専用モードで使用し、操作ログ (および特定のハードウェアに固有のその他の情報 - シリアル番号、センサーのキャリブレーションなど) を別の場所に保存するというオプションにたどり着きました。 。

ラズベリーの読み取り専用 FS のトピックはすでに徹底的に研究されているため、この記事では実装の詳細については触れません。 (ただし、興味があれば、このトピックに関するミニ記事を書くかもしれません)。私が注意したい唯一の点は、個人的な経験からも、すでに導入した人のレビューからも、信頼性が向上しているということです。はい、故障を完全になくすことは不可能ですが、故障の頻度を大幅に減らすことはかなり可能です。また、カードは統合されつつあるため、サービス担当者による交換がはるかに簡単になります。

ハードウェア

メモリの種類である NOR フラッシュの選択に特に疑問はありませんでした。
引数：

• 簡単な接続 (ほとんどの場合、SPI バスを使用します。すでに使用経験があるため、ハードウェアの問題は発生しません)。
• とんでもない値段。
• 標準動作プロトコル (実装はすでに Linux カーネルに組み込まれています。必要に応じて、同様に存在するサードパーティ製のプロトコルを使用することも、独自のプロトコルを作成することもできます。幸いなことに、すべてが簡単です)。
• 信頼性とリソース:
  一般的なデータシートより: データは 20 年間保存され、ブロックごとに 100000 回の消去サイクルが行われます。
  サードパーティのソースから: BER が非常に低く、エラー訂正コードが不要であると想定されます。 (一部の作品では ECC を NOR とみなしますが、通常は依然として MLC NOR を意味します。これも起こります).

ボリュームとリソースの要件を見積もってみましょう。

データの数日間の保存を保証してほしい。これは、通信上の問題が発生した場合に販売履歴が失われないようにするために必要です。この期間中、5日間に焦点を当てます。 （土日祝日も考慮に入れます） 問題は解決できます。

現在、100 日あたり約 3 kb のログ (4 ～ 10 エントリ) を収集していますが、この数字は徐々に増加しており、詳細が増加し、新しいイベントが追加されています。さらに、バーストが発生することもあります (たとえば、一部のセンサーが誤検知でスパム送信を開始します)。 100 レコードについて、それぞれ XNUMX バイト、つまり XNUMX 日あたりメガバイトを計算します。

合計 5MB のクリーンな (適切に圧縮された) データが出力されます。もっと彼らに （おおまかな見積もり） 1MBのサービスデータ。

つまり、圧縮を使用しない場合は 8MB のチップが必要となり、圧縮を使用する場合は 4MB のチップが必要になります。このタイプのメモリでは非常に現実的な数値です。

リソースに関しては、メモリ全体が 5 日に 10 回以上書き換えられないと計画した場合、XNUMX 年間使用しても書き換えサイクルは XNUMX 回未満になります。
メーカーは10万個を約束していることを思い出させてください。

NOR と NAND について少し説明

Today, of course, NAND memory is much more popular, but I would not use it for this project: NAND, unlike NOR, necessarily requires the use of error correction codes, a table of bad blocks, etc., and also the legs of通常、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

チップとRaspberry Piの接続については説明を省略します。一方では、私はエレクトロニクスの専門家ではありませんが、他方では、ここにあることは私にとってさえありふれたものです。超小型回路には 8 本の脚しかなく、そのうちのグランド、電源、SPI (CS、SI、SO、SCK) が必要です。 );レベルは Raspberry Pi と同じで、追加の配線は必要ありません。指定された 6 つのピンを接続するだけです。

問題の定式化

いつものように、問題ステートメントは何度か反復され、次の反復の時期が来たように思えます。そこで、ここで立ち止まって、すでに書かれたことをまとめて、影に残っている詳細を明らかにしましょう。

そこで、ログを SPI NOR Flash に保存することにしました。

知らない人のために、NOR Flash とは何ですか?

これは、次の 3 つの操作を実行できる不揮発性メモリです。

1. 読む：
   最も一般的な読み取り: アドレスを送信し、必要なだけバイトを読み取ります。
2. 記録：
   NOR フラッシュへの書き込みは通常の書き込みのように見えますが、特徴が 1 つあります。0 から 0 への変更のみが可能で、その逆はできないということです。たとえば、メモリ セルに 55x0 があった場合、0x0f を書き込んだ後、05xXNUMX がすでにそこに格納されています。 (すぐ下の表を参照);
3. 消去：
   もちろん、逆の操作、つまり 0 を 1 に変更することができる必要があります。これがまさに消去操作の目的です。最初の 4 つとは異なり、バイトではなくブロックで動作します (選択したチップの最小消去ブロックは 0kb です)。消去はブロック全体を破壊し、1 を XNUMX に変更する唯一の方法です。したがって、フラッシュ メモリを使用する場合、多くの場合、データ構造を消去ブロックの境界に揃える必要があります。
   NOR フラッシュでの記録:

バイナリデータ

だった
01010101

録音済み
00001111

なった
00000101

ログ自体は、可変長のレコードのシーケンスを表します。レコードの長さは通常約 30 バイトです (ただし、レコードの長さが数キロバイトになる場合もあります)。 この場合、それらを単にバイトのセットとして扱いますが、興味がある場合は、レコード内で CBOR が使用されます。

ログに加えて、特定のデバイス ID、センサーの調整、「デバイスが一時的に無効になっている」フラグなど、更新されたものとそうでないものを含むいくつかの「設定」情報を保存する必要があります。
この情報はキーと値のレコードのセットであり、CBOR にも保存されていますが、この情報はそれほど多くはなく (せいぜい数キロバイト)、更新される頻度も低いです。
以下では、それをコンテキストと呼びます。

この記事の始まりを思い出してください。信頼性の高いデータ ストレージを確保し、可能であれば、ハードウェア障害やデータ破損が発生した場合でも継続的な運用を確保することが非常に重要です。

どのような問題の原因が考えられますか?

• 書き込み/消去操作中は電源をオフにしてください。これは「バールに対抗する術はない」というカテゴリーのものです。
  からの情報 議論 stackexchange: フラッシュの操作中に電源がオフになると、消去 (1 に設定) と書き込み (0 に設定) の両方が未定義の動作を引き起こします: データは書き込むことができ、部分的に書き込むことができます (たとえば、10 バイト/80 ビットを転送したとします) 、ただしまだ 45 ビットしか書き込むことができません）、一部のビットが「中間」状態になる可能性もあります（読み取りでは 0 と 1 の両方が生成される可能性があります）。
• フラッシュメモリ自体のエラー。
  BER は非常に低いですが、ゼロに等しくすることはできません。
• バスエラー
  SPI 経由で送信されるデータはいかなる方法でも保護されておらず、単一ビット エラーと同期エラーの両方が発生する可能性があります - ビットの損失または挿入 (大規模なデータ歪みにつながります)。
• その他のエラー/不具合
  コードのエラー、ラズベリーの不具合、エイリアンの干渉...

私は要件を策定しましたが、私の考えでは、信頼性を確保するにはその要件を満たすことが必要です。

• レコードは直ちにフラッシュ メモリに保存される必要があり、遅延書き込みは考慮されません。 - エラーが発生した場合は、できるだけ早く検出して処理する必要があります。 - 可能であれば、システムはエラーから回復する必要があります。
  (人生における「こうあるべきではない」例。誰もが遭遇したことがあると思います。緊急再起動後、ファイル システムが「壊れ」、オペレーティング システムが起動しなくなる)

アイデア、アプローチ、考察

この問題について考え始めたとき、次のような多くのアイデアが頭の中に浮かびました。

• データ圧縮を使用します。
• たとえば、レコード自体とは別にレコード ヘッダーを保存するなど、賢いデータ構造を使用して、レコードにエラーがあった場合でも問題なく残りを読み取ることができます。
• ビットフィールドを使用して、電源がオフになったときの記録の完了を制御します。
• すべてのチェックサムを保存します。
• 何らかの種類のノイズ耐性のあるコーディングを使用します。

これらのアイデアのいくつかは使用されましたが、他のアイデアは放棄されることが決定されました。順番に行きましょう。

データ圧縮

私たちが日記に記録する出来事自体は非常に類似しており、再現可能です（「5 ルーブル硬貨を投げた」、「おつりを渡すためにボタンを押した」など）。したがって、圧縮は非常に効果的であるはずです。

圧縮オーバーヘッドはわずかであり (当社のプロセッサは非常に強力で、最初の Pi でさえ周波数 700 MHz のコアが XNUMX つありましたが、現在のモデルには周波数 XNUMX ギガヘルツを超えるコアがいくつかあります)、ストレージとの交換レートは低くなります (数メガバイト/秒)、レコードのサイズは小さいです。一般に、圧縮がパフォーマンスに影響を与える場合、それはプラスの影響しかありません。 （まったく批判的ではなく、単に述べているだけです）。さらに、本物の組み込みではなく、通常の Linux を使用しているため、実装には多くの労力は必要ありません (ライブラリをリンクし、そこからいくつかの関数を使用するだけで十分です)。

動作中のデバイスからログの一部 (1.7 MB、70 エントリ) が取得され、最初にコンピューターで利用可能な gzip、lz4、lzop、bzip2、xz、zstd を使用して圧縮性がチェックされました。

• gzip、xz、zstd も同様の結果を示しました (40Kb)。
  ファッショナブルな xz が gzip または zstd のレベルでここに現れたことには驚きました。
• デフォルト設定の lzip では、若干悪い結果が得られました。
• lz4 と lzop はあまり良い結果を示しませんでした (150Kb)。
• bzip2 は驚くほど良い結果を示しました (18Kb)。

したがって、データは非常によく圧縮されています。
したがって、(致命的な欠陥が見つからなければ) 圧縮が行われることになります。より多くのデータを同じフラッシュドライブに保存できるためです。

デメリットについて考えてみましょう。

最初の問題: すべてのレコードが直ちにフラッシュされる必要があることにすでに同意しています。通常、アーカイバーは、週末に書き込みを行う時期が来たと判断するまで、入力ストリームからデータを収集します。データの圧縮ブロックを直ちに受信し、不揮発性メモリに保存する必要があります。

私は次の 3 つの方法を考えています。

1. 上で説明したアルゴリズムの代わりに辞書圧縮を使用して各レコードを圧縮します。
   これは完全に機能するオプションですが、私は好きではありません。 Для обеспечения более-менее приличного уровня сжатия словарь должен быть «заточен» под конкретные данные, любое изменение приведёт к тому, что уровень сжатия катастрофически падает. Да, проблема решается созданием новой версии словаря, но это же головная боль — нам нужно будет хранить все версии словаря;各エントリでは、どのバージョンの辞書で圧縮されたかを示す必要があります...
2. 「古典的な」アルゴリズムを使用して各レコードを圧縮しますが、他のレコードは独立して圧縮されます。
   検討中の圧縮アルゴリズムは、このサイズ (数十バイト) のレコードを処理するように設計されていないため、圧縮率は明らかに 1 未満になります (つまり、圧縮ではなくデータ量が増加します)。
3. 各記録後にフラッシュを実行します。
   多くの圧縮ライブラリは FLUSH をサポートしています。これはコマンド (または圧縮手順のパラメーター) であり、アーカイバーはこれを受信すると圧縮ストリームを形成し、復元に使用できるようにします。 すべて すでに受信した非圧縮データ。そんなアナログ sync ファイルシステム内、または commit SQLで。
   重要なことは、後続の圧縮操作で蓄積された辞書を使用できるようになり、圧縮率が以前のバージョンほど低下しないことです。

私が 3 番目のオプションを選択したのは明らかだと思います。詳しく見てみましょう。

見つかった 素晴らしい記事 zlibのFLUSHについて。

記事に基づいて膝テストを実行し、ページ サイズ 70Kb で実際のデバイスから 60 のログ エントリを取得しました。 (ページサイズについては後ほど説明します) 受け取った：

初期データ
圧縮 gzip -9 (フラッシュなし)
Z_PARTIAL_FLUSH を使用した zlib
Z_SYNC_FLUSH を使用した zlib

ボリューム、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 ブロックは次のもので構成されます。

• 3 ビットのブロックヘッダー。
• 0 ～ 7 ビットはゼロに等しく、バイト アラインメントを実現します。
• 00 バイトのシーケンス 00 XNUMX FF FF。

簡単にわかるように、これら 4 バイトの前の最後のブロックには 3 ～ 10 個のゼロ ビットがあります。ただし、実際には少なくとも 10 個のゼロ ビットがあることがわかっています。

このような短いデータ ブロックは、通常 (常に?) タイプ 1 のブロック (固定ブロック) を使用してエンコードされることがわかりました。このブロックは必ず 7 つのゼロ ビットで終わり、合計 10 ～ 17 の保証されたゼロ ビットになります (残りは約50%の確率でゼロになります）。

したがって、テスト データでは、100% の場合、0x00、0x00、0xff、0xff の前にゼロ バイトが XNUMX つあり、XNUMX 分の XNUMX 以上のケースで XNUMX つのゼロ バイトがあります。 (おそらく実際にはバイナリ CBOR を使用しており、テキスト JSON を使用する場合、タイプ 2 のブロック (ダイナミック ブロック) がより一般的であり、0x00、0x00、0xff、0xff の前に追加のゼロ バイトがないブロックが発生します).

利用可能なテスト データを使用すると、合計で 250Kb 未満の圧縮データに収めることができます。

ビットを調整することで、もう少し節約できます。今のところ、ブロックの終わりにあるいくつかのゼロビットの存在を無視します。ブロックの先頭にあるいくつかのビットも変更されません...
しかし、このままでは独自のアーカイバを開発することになるかもしれないので、やめようと強い意志を持ちました。

合計すると、書き込みごとに 3 ～ 4 バイトを受信したテスト データから、圧縮率は 6:1 を超えることが判明しました。正直に言うと、このような結果になるとは予想していませんでした。私の意見では、2:1 よりも優れたものはすでに圧縮の使用を正当化する結果になっています。

すべて問題ありませんが、zlib (deflate) は依然として古風で、当然のことであり、やや時代遅れの圧縮アルゴリズムです。非圧縮データ ストリームの最後の 32Kb が辞書として使用されるという単なる事実は、今日では奇妙に見えます (つまり、あるデータ ブロックが 40Kb 前の入力ストリームにあったものと非常によく似ている場合、そのデータ ブロックは再びアーカイブされ始めます)以前の出来事については言及しません）。最新のファッショナブルなアーカイバでは、辞書のサイズはキロバイトではなくメガバイトで測定されることがよくあります。

そこで私たちはアーカイバに関するミニ研究を続けます。

次に、bzip2 をテストしました (FLUSH を使用しないと、ほぼ 100:1 という素晴らしい圧縮率が示されたことを思い出してください)。残念ながら、FLUSH ではパフォーマンスが非常に悪く、圧縮データのサイズが非圧縮データよりも大きいことが判明しました。

失敗の理由についての私の推測

Libbz2 が提供するフラッシュ オプションは XNUMX つだけで、辞書をクリアするようです (zlib の Z_FULL_FLUSH に似ています)。これ以降は効果的な圧縮については言及されていません。

そして最後にテストされたのは zstd でした。パラメータに応じて、gzip レベルで圧縮しますが、gzip よりもはるかに高速か、より優れた圧縮が行われます。

残念ながら、FLUSH ではパフォーマンスがあまり良くありませんでした。圧縮データのサイズは約 700Kb でした。

Я 質問した プロジェクトの github ページで、圧縮データのブロックごとに最大 10 バイトのサービス データを考慮する必要があるという回答を受け取りましたが、これは得られた結果に近いものであり、deflate に追いつく方法はありません。

私はアーカイバーを使った実験をこの時点で中止することにしました (xz、lzip、lzo、lz4 は FLUSH なしのテスト段階でも表示されず、さらに特殊な圧縮アルゴリズムは考慮していませんでした)。

アーカイブの問題に戻りましょう。

2 番目の問題 (値ではなく順序の問題) は、圧縮データが単一のストリームであり、その中で常に前のセクションへの参照が存在することです。したがって、圧縮データのセクションが破損すると、関連する非圧縮データのブロックだけでなく、それ以降のブロックもすべて失われます。

この問題を解決するには、次のようなアプローチがあります。

1. 問題の発生を防止します。圧縮データに冗長性を追加します。これにより、エラーを特定して修正できるようになります。これについては後で説明します。
2. 問題が発生した場合の影響を最小限に抑える
   各データ ブロックを個別に圧縮できることはすでに述べましたが、問題は自然に解消されます (4 つのブロックのデータが損傷すると、そのブロックのデータのみが失われます)。 Однако, это крайний случай, при котором сжатие данных будет неэффективно.逆の極端: チップの XNUMXMB をすべて XNUMX つのアーカイブとして使用すると、優れた圧縮が可能になりますが、データ破損の場合は壊滅的な結果になります。
   はい、信頼性の点で妥協が必要です。しかし、私たちは BER が非常に低く、宣言されたデータ保存期間が 20 年である不揮発性メモリ用のデータ保存形式を開発していることを忘れてはなりません。

実験中に、サイズが 10 KB 未満の圧縮データのブロックで、多かれ少なかれ顕著な圧縮レベルの損失が始まることがわかりました。
使用されるメモリがページングされると前述しましたが、「1 ページと圧縮データの 1 ブロック」の対応関係を使用すべきではない理由はわかりません。

つまり、適切な最小ページ サイズは 16Kb (サービス情報用の予約を含む) です。ただし、ページ サイズがこのように小さいと、最大レコード サイズに重大な制限が課せられます。

圧縮形式で数キロバイトを超えるレコードはまだ期待していませんが、32 キロバイトのページ (チップごとに合計 128 ページ) を使用することにしました。

概要：

• データは zlib (deflate) を使用して圧縮して保存します。
• エントリごとに Z_SYNC_FLUSH を設定します。
• 圧縮されたレコードごとに、末尾のバイトをトリミングします。 (例: 0x00、0x00、0xff、0xff);ヘッダーでは、切り取るバイト数を示します。
• データは 32Kb ページに保存されます。ページ内には圧縮データの単一ストリームがあります。各ページで再び圧縮を開始します。

そして、圧縮を終える前に、レコードあたりの圧縮データは数バイトしかないという事実に注意していただきたいと思います。そのため、サービス情報を膨張させないことが非常に重要であり、ここではすべてのバイトが重要になります。

データヘッダーの保存

可変長のレコードがあるため、レコードの配置/境界を何らかの方法で決定する必要があります。

私は 3 つのアプローチを知っています。

1. すべてのレコードは連続ストリームに格納されます。最初に長さを含むレコード ヘッダーがあり、次にレコード自体が格納されます。
   この実施形態では、ヘッダとデータの両方を可変長にすることができる。
   基本的に、常に使用される単一リンクのリストを取得します。
2. ヘッダーとレコード自体は別のストリームに保存されます。
   一定の長さのヘッダーを使用することで、1 つのヘッダーの損傷が他のヘッダーに影響を与えないようにします。
   同様のアプローチは、たとえば多くのファイル システムで使用されています。
3. レコードは連続ストリームに格納され、レコードの境界は特定のマーカー (データ ブロック内で禁止されている文字または文字のシーケンス) によって決定されます。レコード内にマーカーがある場合は、それを何らかのシーケンスに置き換えます (エスケープします)。
   同様のアプローチは、たとえば PPP プロトコルでも使用されます。

説明します。

オプション1：

ここではすべてが非常に簡単です。レコードの長さがわかれば、次のヘッダーのアドレスを計算できます。したがって、0xff (空き領域) で満たされた領域またはページの終わりに到達するまで、見出しを移動します。

オプション2：

レコード長は可変であるため、ページごとに必要なレコード (したがってヘッダー) の数を事前に言うことはできません。ヘッダーとデータ自体を別のページに分散することもできますが、私は別のアプローチを好みます。ヘッダーとデータの両方を 1 つのページに配置しますが、ヘッダー (一定サイズ) はページの先頭から来て、 (可変長の) データは最後から来ます。これらが「一致」するとすぐに (新しいエントリを入力するための十分な空きスペースがなくなり)、このページは完成したと見なされます。

オプション3：

ヘッダー内のデータの位置に関する長さまたはその他の情報を保存する必要はなく、レコードの境界を示すマーカーで十分です。ただし、書き込み/読み取り時にはデータを処理する必要があります。
私は 0xff をマーカー (消去後にページを埋める) として使用するので、空き領域はデータとして扱われません。

比較表：

オプション1
オプション2
オプション3

許容誤差
-
+
+

コンパクトさ
+
-
+

実装の複雑さ
*
**
**

オプション 1 には致命的な欠陥があります。ヘッダーのいずれかが破損すると、後続のチェーン全体が破壊されます。残りのオプションを使用すると、大規模な損傷が発生した場合でも一部のデータを回復できます。
ただし、ここでは、データを圧縮形式で保存することにしたため、レコードが「壊れた」後はページ上のすべてのデータが失われるため、テーブルにマイナスがあっても、データは失われません。それを考慮に入れてください。

コンパクトさ：

• 最初のオプションでは、ヘッダーに長さのみを格納する必要があります。可変長の整数を使用する場合、ほとんどの場合、1 バイトで済みます。
• 4 番目のオプションでは、開始アドレスと長さを保存する必要があります。レコードは一定のサイズである必要があり、レコードごとに XNUMX バイトと見積もられます (オフセットに XNUMX バイト、長さに XNUMX バイト)。
• третьему варианту достаточно всего одного символа для обозначения начала записи, плюс сама запись из-за экранирования вырастет на 1-2%.一般に、最初のオプションとほぼ同等です。

当初、私は 2 番目のオプションを主なオプションとして検討しました (実装まで書きました)。最終的に圧縮を使用することに決めたときにのみ、それを放棄しました。

おそらくいつか私も同じようなオプションを使うことになるでしょう。たとえば、地球と火星の間を航行する船のデータ ストレージを扱う必要がある場合、信頼性、宇宙放射線などに関してまったく異なる要件が存在します。

3 番目のオプションについては、シールドをいじったり、プロセス内で長さを変更したりするのが好きではないため、実装の難しさを理由に星 2 つとしました。はい、おそらく私は偏見を持っているかもしれませんが、コードを書かなければなりません。なぜ気に入らないことを自分に強制する必要がありますか。

概要： 効率性と実装の容易さのため、「長さのあるヘッダー - 可変長のデータ」というチェーンの形式のストレージ オプションを選択します。

ビットフィールドを使用して書き込み操作の成功を監視する

どこでこのアイデアを思いついたのか今では覚えていませんが、次のような感じです。
各エントリに対して、フラグを格納するためにいくつかのビットを割り当てます。
前に述べたように、消去後はすべてのビットが 1 で埋められ、1 を 0 に変更することはできますが、その逆はできません。 したがって、「フラグが設定されていない」場合は 1 を使用し、「フラグが設定されている」場合は 0 を使用します。

可変長レコードをフラッシュに入れると次のようになります。

1. 「長さの記録が開始されました」フラグを設定します。
2. 長さを記録します。
3. 「データ記録が開始されました」フラグを設定します。
4. 私たちはデータを記録します。
5. 「録画終了」フラグを立てます。

さらに、「エラー発生」フラグがあり、合計 4 ビットのフラグになります。

この場合、「1111」 - 録音が開始されていない、「1000」 - 録音が成功したという XNUMX つの安定状態があります。記録プロセスが予期せず中断された場合は、中間状態を受け取り、それを検出して処理できます。

このアプローチは興味深いものですが、突然の停電や同様の障害から保護するだけであり、これはもちろん重要ですが、これが障害の可能性がある唯一の (または主な) 原因というわけではありません。

概要： 良い解決策を探して先に進みましょう。

チェックサム

チェックサムを使用すると、書き込まれるべき内容を正確に読み取っていることを (妥当な確率で) 確認することもできます。また、上で説明したビット フィールドとは異なり、常に機能します。

上で説明した潜在的な問題の原因のリストを考慮すると、チェックサムはエラーの原因に関係なくエラーを認識できます。 (おそらく、悪意のあるエイリアンは除きます - 彼らもチェックサムを偽造することができます).

したがって、データが損なわれていないことを確認することが目的である場合、チェックサムは素晴らしいアイデアです。

チェックサムを計算するアルゴリズムの選択 (CRC) には何の疑問も生じませんでした。 С одной стороны, математические свойства позволяют в 100% ловить ошибки некоторых типов, с другой — на случайных данных обычно этот алгоритм показывает вероятность коллизий не сильно больше теоретического предела 。これは最速のアルゴリズムではないかもしれませんし、衝突の数の点で常に最小であるわけでもありませんが、非常に重要な性質を持っています。私が遭遇したテストでは、明らかに失敗するパターンはありませんでした。この場合、安定性が主な品質です。

体積調査の例: パート1, パート2 (narod.ru へのリンク、申し訳ありません).

ただし、チェックサムを選択するタスクは完了していません。CRC はチェックサムのファミリー全体です。長さを決定してから、多項式を選択する必要があります。

チェックサムの長さの選択は、一見したように見えるほど簡単な問題ではありません。

説明しましょう:
各バイトのエラーの確率を調べてみましょう 理想的なチェックサムを求めて、100 万レコードあたりの平均エラー数を計算してみましょう。

データ、バイト
チェックサム、バイト
検出されないエラー
誤ったエラー検出
合計誤検知数

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

すべてが単純であるように思えます。保護されるデータの長さに応じて、誤った正の値が最小限になるチェックサムの長さを選択します。そして、その秘訣はバッグの中にあります。

Однако, с короткими контрольными суммами возникает проблема: они, хоть и хорошо обнаруживают единичные битовые ошибки, могут с достаточно большой вероятностью принять за верные совершенно случайные данные.ハブレに関する記事がすでにありました。 実生活における問題.

したがって、ランダムなチェックサムの一致をほぼ不可能にするには、32 ビット以上の長さのチェックサムを使用する必要があります。 (64 ビットを超える長さの場合は、通常、暗号化ハッシュ関数が使用されます).

スペースを必ず節約する必要があると以前に書きましたが、それでも 32 ビットのチェックサムを使用します (16 ビットでは十分ではなく、衝突の確率は 0.01% を超えます。また、24 ビットも使用します)。ここにもあそこにもいないと言う）。

ここで反論が生じるかもしれません。一度に 4 バイトを与えるために、圧縮を選択したときにすべてのバイトを保存したのでしょうか?圧縮したりチェックサムを付加したりしない方が良いのではないでしょうか？もちろんそうではありません、圧縮はありません 意味ではありません、整合性チェックは必要ないということです。

多項式を選択するときは、車輪の再発明ではなく、現在人気のある CRC-32C を採用します。
このコードは、最大 6 バイトのパケットの 22 ビット エラー (おそらく当社にとって最も一般的なケース)、最大 4 バイトのパケットの 655 ビット エラー (これも当社にとって一般的なケース)、パケットの 2 ビットまたは任意の奇数のビット エラーを検出します。 of any reasonable length.

詳細に興味のある方がいらっしゃいましたら

ウィキペディアの記事 CRCについて。

コードパラメータ crc-32c на コープマンのウェブサイト — おそらく、地球上で最も有力な CRC 専門家です。

В 彼の記事 がある 別の興味深いコードこれは、私たちに関連するパケット長に対してわずかに優れたパラメーターを提供しますが、私はその違いが重要であるとは考えず、十分に研究された標準コードの代わりにカスタムコードを選択するのに十分な能力を持っていました。

また、データは圧縮されているため、圧縮データと非圧縮データのチェックサムを計算する必要があるか?という疑問が生じます。

非圧縮データのチェックサムの計算を支持する議論:

• 最終的にはデータ ストレージの安全性をチェックする必要があるため、直接チェックします (同時に、圧縮/解凍の実装で起こり得るエラー、メモリの破損などによる損傷もチェックされます)。
• zlib の deflate アルゴリズムはかなり成熟した実装になっており、 いけない 「曲がった」入力データが含まれる可能性があり、さらに、多くの場合、入力ストリーム内のエラーを個別に検出できるため、エラーが検出されない全体的な確率が減少します (短いレコード内の 1 ビットを反転してテストを実行し、zlib がエラーを検出しました)ケースの約 3 分の 1 で）。

非圧縮データのチェックサムの計算に対する反論:

• CRC は、フラッシュ メモリの特徴である数ビット エラーに特化して「調整」されています (圧縮ストリーム内のビット エラーは出力ストリームに大きな変化を引き起こす可能性があり、純粋に理論的には衝突を「キャッチ」できます)。
• 私は壊れている可能性のあるデータを解凍プログラムに渡すという考えがあまり好きではありません。 知るか彼がどう反応するか。

このプロジェクトでは、非圧縮データのチェックサムを保存するという一般に受け入れられている慣行から逸脱することにしました。

概要： CRC-32C を使用し、フラッシュに書き込まれる形式のデータ (圧縮後) からチェックサムを計算します。

冗長性

もちろん、冗長コーディングを使用してもデータ損失がなくなるわけではありませんが、回復不能なデータ損失の可能性を大幅に (多くの場合、何桁も) 減らすことができます。

さまざまな種類の冗長性を使用してエラーを修正できます。
ハミング コードはシングル ビット エラーを修正でき、リードソロモン文字コード、チェックサムと組み合わせたデータの複数のコピー、または RAID-6 などのエンコーディングは、大規模な破損が発生した場合でもデータを回復するのに役立ちます。
当初、私はエラー耐性のあるコーディングの普及に尽力していましたが、まずどのようなエラーから身を守りたいかを考えてから、コーディングを選択する必要があることに気づきました。

エラーはできるだけ早く検出する必要があると前述しました。どの時点でエラーが発生する可能性がありますか?

1. 録音が完了していない（録音時に何らかの理由で電源が切れた、Raspberry がフリーズした、...）
   悲しいことに、このようなエラーが発生した場合、残るのは無効なレコードを無視し、データが失われたと考えることだけです。
2. 書き込みエラー（何らかの理由で、フラッシュメモリに書き込まれた内容と書き込まれた内容が異なる）
   記録直後にテスト読み取りを実行すると、このようなエラーをすぐに検出できます。
3. 保存中のメモリ内のデータの歪み。
4. 読み取りエラー
   チェックサムが一致しない場合は、読み取りを数回繰り返すだけで修正できます。

つまり、3 番目のタイプのエラー (保存中のデータの自然破損) だけは、エラー耐性のあるコーディングなしでは訂正できません。このようなエラーが発生する可能性はまだ非常に低いようです。

概要： 冗長コーディングを放棄することが決定されましたが、運用でこの決定の誤りが示された場合は、問題の検討に戻ります（失敗に関する統計がすでに蓄積されているため、最適なタイプのコーディングを選択できます）。

他の

もちろん、記事の形式上、あらゆる部分を正当化することはできません。 (もう体力も尽きた), そこで、先ほど触れなかったいくつかの点について簡単に説明します。

• すべてのページを「平等」にすることが決定されました
  つまり、メタデータを含む特別なページや個別のスレッドなどは存在せず、代わりに単一のスレッドがすべてのページを順番に書き換えます。
  これにより、ページの磨耗が均等になり、単一障害点がなくなり、とても気に入っています。
• 形式のバージョン管理を提供することが不可欠です。
  ヘッダーにバージョン番号のないフォーマットは邪悪です。
  特定のマジック ナンバー (署名) を持つフィールドをページ ヘッダーに追加するだけで十分です。これは、使用されている形式のバージョンを示します。 (実際には十数個も存在しないと思います);
• レコード (多数あります) には可変長ヘッダーを使用し、ほとんどの場合長さが 1 バイトになるようにします。
• 圧縮レコードのヘッダーの長さとトリミングされた部分の長さをエンコードするには、可変長バイナリ コードを使用します。

とても助かりました オンラインジェネレーター ハフマン符号。 Буквально за несколько минут удалось подобрать нужные коды переменной длины.

データ保存形式の説明

バイトオーダー

0 バイトより大きいフィールドは、ビッグ エンディアン形式 (ネットワーク バイト オーダー) で保存されます。つまり、1234x0 は 12x0、34xXNUMX として書き込まれます。

ページネーション

すべてのフラッシュ メモリは同じサイズのページに分割されます。

デフォルトのページ サイズは 32Kb ですが、メモリ チップの合計サイズの 1/4 を超えません (4MB チップの場合、128 ページが取得されます)。

各ページは、他のページとは独立してデータを格納します (つまり、あるページのデータは別のページのデータを参照しません)。

すべてのページには、番号 0 から始まる自然順序 (アドレスの昇順) で番号が付けられます (ページ 0 はアドレス 32 から始まり、最初のページは 64Kb から始まり、XNUMX 番目のページは XNUMXKb から始まります)。

メモリ チップは循環バッファ (リング バッファ) として使用されます。つまり、最初にページ番号 0 に書き込み、次にページ番号 1 に書き込みが行われ、最後のページがいっぱいになると、新しいサイクルが開始され、ページ XNUMX から記録が継続されます。 。

ページ内

ページの先頭には 4 バイトのページ ヘッダーが格納され、次にヘッダー チェックサム (CRC-32C) が格納され、その後、レコードが「ヘッダー、データ、チェックサム」形式で格納されます。

ページ タイトル (図の汚れた緑色) は次の内容で構成されます。

• 2 バイトのマジック ナンバー フィールド (フォーマット バージョンの記号でもあります)
  形式の現在のバージョンでは、次のように計算されます。 0xed00 ⊕ номер страницы;
• 2バイトカウンタ「ページバージョン」（メモリ書き換えサイクル数）。

ページ上のエントリは圧縮形式で保存されます (deflate アルゴリズムが使用されます)。 1 ページ上のすべてのレコードは 1 つのスレッドで圧縮され (共通の辞書が使用されます)、新しいページごとに圧縮が新たに開始されます。つまり、レコードを解凍するには、このページの以前のすべてのレコード (およびこのページのみ) が必要です。

各レコードは Z_SYNC_FLUSH フラグを使用して圧縮され、圧縮ストリームの最後には 4 バイト 0x00、0x00、0xff、0xff が存在し、その前にさらに XNUMX バイトまたは XNUMX バイトのゼロ バイトが続く可能性があります。
フラッシュ メモリに書き込むときに、このシーケンス (4、5、または 6 バイト長) を破棄します。

レコード ヘッダーは 1、2、または 3 バイトで、次のものを格納します。

• レコードのタイプを示す 0 ビット (T): 1 - コンテキスト、XNUMX - ログ。
• 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)

説明してみましたが、どの程度明確に判明したかはわかりません。

ここで、黄色は T フィールド、白は S フィールド、緑の L (バイト単位の圧縮データの長さ)、青は圧縮データ、赤はフラッシュ メモリに書き込まれない圧縮データの最後のバイトを示します。

したがって、最も一般的な長さ (圧縮形式で最大 63+5 バイト) のレコード ヘッダーを XNUMX バイトで書き込むことができます。

各レコードの後に​​ CRC-32C チェックサムが保存され、前のチェックサムの反転値が初期値 (init) として使用されます。

CRC には「期間」という特性があり、次の式が機能します (プロセス内でプラスまたはマイナスのビット反転が行われます)。 .
つまり、実際には、このページのヘッダーとデータの前のすべてのバイトの CRC を計算します。

チェックサムのすぐ後には、次のレコードのヘッダーがあります。

ヘッダーは、その最初のバイトが常に 0x00 と 0xff とは異なるように設計されています (ヘッダーの最初のバイトの代わりに 0xff が見つかった場合、これはこれが未使用領域であることを意味します。0x00 はエラーを示します)。

アルゴリズムの例

フラッシュメモリからの読み出し

すべての読み取りにはチェックサムチェックが含まれます。
チェックサムが一致しない場合は、正しいデータを読み取るために読み取りが数回繰り返されます。

(これは当然のことですが、Linux は NOR フラッシュからの読み取りをキャッシュしません (テスト済み)

フラッシュメモリへの書き込み

データを記録します。
読んでみましょう。

読み取ったデータが書き込まれたデータと一致しない場合は、領域をゼロで埋めてエラーを通知します。

新しいマイクロ回路の動作準備

初期化では、バージョン 1 のヘッダーが最初の (またはゼロの) ページに書き込まれます。
その後、初期コンテキストがこのページに書き込まれます (マシンの UUID とデフォルト設定が含まれます)。

以上で、フラッシュメモリを使用する準備が整いました。

マシンをロードする

ロード時に、各ページの最初の 8 バイト (ヘッダー + CRC) が読み取られ、不明なマジック ナンバーまたは不正な CRC を持つページは無視されます。
「正しい」ページから最大バージョンのページが選択され、その中から最大の番号のページが取得されます。
最初のレコードが読み取られ、CRC の正確さと「コンテキスト」フラグの存在がチェックされます。すべてが正常であれば、このページは最新のものとみなされます。そうでない場合は、「ライブ」ページが見つかるまで、前のページにロールバックします。
そして、見つかったページで、「context」フラグで使用するすべてのレコードを読み取ります。
zlib 辞書を保存します (このページに追加するために必要になります)。

以上で、ダウンロードが完了し、コンテキストが復元され、作業できるようになります。

仕訳帳エントリの追加

Z_SYNC_FLUSH を指定して、正しい辞書を使用してレコードを圧縮し、圧縮されたレコードが現在のページに収まるかどうかを確認します。
適合しない場合 (またはページに CRC エラーがあった場合)、新しいページを開始してください (以下を参照)。
レコードと CRC を書き留めます。エラーが発生した場合は、新しいページを開始してください。

新しいページ

最小番号の空きページを選択します (空きページとは、ヘッダーに不正なチェックサムがあるページ、または現在のバージョンより前のバージョンを持つページであると考えられます)。該当するページがない場合は、現在のバージョンと同じバージョンを持つページの中から最小番号のページを選択します。
選択したページを消去します。 0xffで内容を確認します。何か問題があった場合は、次の空きページなどに進んでください。
消去されたページにヘッダーを書き込みます。最初のエントリはコンテキストの現在の状態であり、次は未書き込みのログ エントリ (存在する場合) です。

フォーマットの適用性

私の意見では、これは、多かれ少なかれ圧縮可能な情報ストリーム (プレーン テキスト、JSON、MessagePack、CBOR、おそらく protobuf) を NOR Flash に保存するのに適した形式であることが判明しました。

もちろん、このフォーマットは SLC NOR フラッシュ用に「調整」されています。

NAND や MLC NOR などの高 BER メディアでは使用しないでください。 （そのようなメモリは販売されているのでしょうか？修正コードの作品でしか言及されていないのを見たことがあります）.

さらに、独自の FTL を持つデバイス (USB フラッシュ、SD、MicroSD など) では使用しないでください。 (そのようなメモリのために、私は 512 バイトのページ サイズ、各ページの先頭に署名、および一意のレコード番号を持つフォーマットを作成しました。場合によっては、単純なシーケンシャル読み取りによって「不具合のある」フラッシュ ドライブからすべてのデータを回復できることもありました).

タスクに応じて、128Kビット（16Kb）から1Gビット（128MB）までのフラッシュドライブでフォーマットを変更せずに使用できます。必要に応じて、より大きなチップでも使用できますが、おそらくページ サイズを調整する必要があります。 (しかし、ここですでに経済的実現可能性の問題が生じています。大容量 NOR フラッシュの価格は心強いものではありません).

誰かがこの形式に興味を持って、オープンなプロジェクトで使用したいと思ったら、書いてください。私は時間を見つけてコードを磨き、github に投稿します。

まとめ

ご覧のとおり、最終的にはシンプルな形式になりました そして退屈さえ.

私の視点の進化を記事に反映するのは難しいですが、信じてください。当初は、近くで核爆発が起きても生き残ることができる、洗練された、壊れないものを作りたかったのです。しかし、それでも理性が勝ち、優先順位は徐々にシンプルさとコンパクトさに移っていきました。

もしかして私が間違っていたのでしょうか？はい、確かに。たとえば、低品質のマイクロ回路を大量に購入したことが判明する可能性があります。または、他の何らかの理由で、機器が信頼性の期待を満たさない可能性があります。

これについての計画はありますか?この記事を読んだ後は、計画があることに疑いの余地はないと思います。そして一人でもありません。

もう少し深刻な話になりますが、このフォーマットは実用的なオプションと「トライアルバルーン」の両方として開発されました。

現時点では、テーブル上のすべてが正常に動作しています。文字通り先日、ソリューションがデプロイされる予定です （約） 数百台のデバイスで、「戦闘」操作で何が起こるかを見てみましょう (幸いなことに、この形式で障害を確実に検出できることを願っています。そうすれば完全な統計を収集できます)。数カ月もすれば結論が出せるだろう (運が悪ければもっと早くても).

使用した結果、重大な問題が発見され、改善が必要な場合は、必ず書き込みます。

文学

中古作品の長くて退屈なリストを作りたくなかったのは、誰もが Google を持っているからです。

ここで、私にとって特に興味深いと思われた調査結果のリストを残すことにしましたが、徐々に記事の本文に直接移行し、リストに 1 つの項目が残りました。

1. ユーティリティ インフゲン 著者zlibより。 deflate/zlib/gzip アーカイブの内容を明確に表示できます。 deflate (または gzip) 形式の内部構造を扱う必要がある場合は、これを強くお勧めします。

出所： habr.com