底

有我們自己設計的自動販賣機。 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中，我們的這些資訊並不多（最多幾千位元組），而且更新也不頻繁。
下面我們將其稱為上下文。

如果我們還記得本文的開頭，那麼確保可靠的資料儲存以及（如果可能的話）即使在硬體故障/資料損壞的情況下也能持續運作是非常重要的。

可以考慮哪些問題根源？

• 寫入/擦除操作期間斷電。這是屬於「撬棍無招」的範疇。
  訊息來自 討論 在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：

這裡一切都很簡單：知道了記錄的長度，我們就可以計算出下一個標頭的位址。因此，我們瀏覽標題，直到我們遇到充滿 0xff（空閒區域）的區域或頁面末尾。

選項2：

由於記錄長度可變，我們無法事先確定每頁需要多少筆記錄（以及標題）。您可以將標題和資料本身分佈在不同的頁面上，但我更喜歡不同的方法：我們將標題和資料都放在一個頁面上，但標題（大小恆定）來自頁面的開頭，並且資料（可變長度）來自末尾。一旦它們「相遇」（沒有足夠的可用空間用於新條目），我們就認為該頁面已完成。

選項3：

無需在標頭中儲存有關資料位置的長度或其他資訊；指示記錄邊界的標記就足夠了。然而，在寫入/讀取時必須對資料進行處理。
我會使用0xff作為標記（擦除後填充頁面），因此空閒區域肯定不會被視為資料。

比較表：

選項1
選項2
選項3

容錯性
-
+
+

密度
+
-
+

實施複雜度
*
**
**

選項1有一個致命的缺陷：如果任何一個標頭被損壞，則整個後續鏈都會被破壞。即使發生大規模損壞，其餘選項也允許您恢復一些資料。
但在這裡應該記住，我們決定以壓縮形式存儲數據，因此在“損壞”記錄後我們會丟失頁面上的所有數據，因此即使表中有負號，我們也不會考慮到這一點。

緊湊：

• 在第一個選項中，我們只需要在標頭中儲存長度；如果我們使用可變長度整數，那麼在大多數情況下我們可以用一個位元組來滿足；
• 在第二個選項中，我們需要儲存起始位址和長度；記錄必須是恆定大小，我估計每個記錄 4 個位元組（兩個位元組用於偏移量，兩個位元組用於長度）；
• 第三個選項只需要一個字元來指示錄音的開始，加上錄音本身會因為屏蔽而增加1-2%。一般來說，與第一個選項大致相同。

最初，我認為第二個選項是主要選項（甚至編寫了實作）。當我最終決定使用壓縮時我才放棄它。

也許有一天我仍然會使用類似的選項。例如，如果我必須處理往返地球和火星之間的船舶的數據存儲，那麼對於可靠性、宇宙輻射等會有完全不同的要求…

至於第三個選項：我給它兩顆星是因為它的實施難度，只是因為我不喜歡亂搞屏蔽、改變過程的長度等。是的，也許我有偏見，但我必須編寫程式碼——為什麼要強迫自己做一些你不喜歡的事情。

摘要： 由於效率和易於實現，我們選擇鏈形式的儲存選項「長度標頭-可變長度資料」。

使用位元字段監控寫入操作是否成功

我現在不記得我從哪裡得到這個想法，但它看起來像這樣：
對於每個條目，我們分配幾個位元來儲存標誌。
正如我們前面所說，擦除後所有位元都被 1 填充，我們可以將 1 更改為 0，但反之則不行。 因此，對於“標誌未設定”，我們使用 1，對於“標誌已設定”，我們使用 0。

將可變長度記錄放入快閃記憶體可能如下所示：

1. 設定“長度記錄已開始”標誌；
2. 記錄長度；
3. 設定「資料記錄已開始」標誌；
4. 我們記錄數據；
5. 設定“錄音結束”標誌。

此外，我們還有一個「發生錯誤」標誌，總共 4 位標誌。

在這種情況下，我們有兩個穩定狀態“1111”-錄製尚未開始和“1000”-錄製成功；如果記錄過程意外中斷，我們將收到中間狀態，然後我們可以偵測和處理這些狀態。

這種方法很有趣，但它只能防止突然斷電和類似的故障，這當然很重要，但這遠不是可能發生故障的唯一（甚至是主要原因）原因。

摘要： 讓我們繼續尋找好的解決方案。

校驗和

校驗和還可以確保（以合理的機率）我們正在準確地讀取應該寫入的內容。而且，與上面討論的位元字段不同，它們始終有效。

如果我們考慮上面討論的潛在問題來源列表，那麼校驗和就能夠識別錯誤，無論其來源為何 （也許，對於惡意的外星人來說，他們也可以偽造校驗和）.

因此，如果我們的目標是驗證資料是否完整，那麼校驗和就是一個好主意。

計算校驗和的演算法的選擇沒有引起任何問題 - CRC。一方面，數學特性使得 100% 捕獲某些類型的錯誤成為可能；另一方面，對於隨機數據，該演算法通常顯示的碰撞機率不會比理論極限大得多 。它可能不是最快的演算法，也不總是碰撞次數最少的演算法，但它有一個非常重要的品質：在我遇到的測試中，沒有任何模式明顯失敗。在這種情況下，穩定性是主要品質。

體積研究範例： 第1部分, 第2部分 （抱歉，連結到 narod.ru）.

然而，選擇校驗和的任務還沒有完成；CRC 是一個完整的校驗和系列。您需要確定長度，然後選擇一個多項式。

選擇校驗和長度並不像乍看那麼簡單。

讓我舉例說明：
讓我們計算每個位元組出現錯誤的機率 和理想的校驗和，讓我們計算每百萬筆記錄的平均錯誤數：

數據，位元組
校驗和，位元組
未偵測到的錯誤
錯誤偵測
誤報總數

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頁繼續記錄。

頁面內

在頁的開頭，儲存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)

我試著說明，我不知道結果有多清楚：

這裡黃色表示T字段，白色表示S字段，綠色L（壓縮資料的長度，以位元組為單位），藍色表示壓縮數據，紅色表示未寫入快閃記憶體的壓縮資料的最後位元組。

因此，我們可以在一個位元組中寫入最常見長度的記錄頭（壓縮形式最多為 63+5 位元組）。

每筆記錄之後都會儲存一個 CRC-32C 校驗和，其中將前一個校驗和的反轉值用作初始值（init）。

CRC具有「持續時間」的屬性，其計算公式如下（過程中加上或減去位元反轉）： .
也就是說，實際上我們計算了該頁上所有前一個位元組的標頭和資料的 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 上。

結論

正如你所看到的，最終格式變得很簡單 甚至無聊.

在一篇文章中很難反映我觀點的演變，但請相信我：最初我想創造一些複雜的、堅不可摧的東西，甚至能夠在近距離的核爆炸中倖存下來。然而，理性（我希望）仍然獲勝，優先事項逐漸轉向簡單和緊湊。

難道是我錯了？是的，當然。例如，很可能我們購買了一批低品質的微電路。或者由於某些其他原因，設備將無法滿足可靠性預期。

我有這方面的計畫嗎？我想，讀完這篇文章，你就不會懷疑有計畫了。甚至不是獨自一人。

稍微嚴肅一點的是，該格式既作為一種工作選項又作為“試用氣球”而開發。

目前，桌面上的一切都運作良好，實際上，有一天該解決方案將被部署 （約） 在數百台設備上，讓我們看看「戰鬥」操作中會發生什麼（幸運的是，我希望該格式可以讓您可靠地檢測故障；這樣您就可以收集完整的統計數據）。幾個月後就能下結論 （如果你運氣不好，甚至更早）.

如果根據使用結果發現嚴重問題需要改進，那麼我一定會寫出來。

文學

我不想列出一長串無聊的二手作品清單；畢竟，每個人都有Google。

在這裡，我決定留下一系列對我來說特別有趣的發現，但逐漸地它們直接遷移到文章的正文中，並且清單中保留了一個項目：

1. 效用 基因 來自作者 zlib。可以清晰顯示deflate/zlib/gzip壓縮包的內容。如果您必須處理 deflate（或 gzip）格式的內部結構，我強烈推薦它。

來源： www.habr.com