Hintergrund

Es gibt Automaten nach eigenem Design. Im Raspberry Pi und ein bisschen Umreifen auf einem separaten Brett. Ein Münzprüfer, ein Geldscheinprüfer, ein Bankautomat sind angeschlossen ... Ein selbst geschriebenes Programm verwaltet alles. Die gesamte Geschichte der Arbeit wird auf einem Flash-Laufwerk (MicroSD) in das Journal geschrieben, das dann über das Internet (unter Verwendung eines USB-Modems) an den Server übertragen und dort der Datenbank hinzugefügt wird. Verkaufsinformationen werden in 1s geladen, es gibt auch ein einfaches Webinterface zum Überwachen usw.

Das heißt, das Magazin ist von entscheidender Bedeutung - für die Buchhaltung (dort Einnahmen, Verkäufe usw.), die Überwachung (alle Arten von Fehlern und andere Umstände höherer Gewalt); das können Sie sagen, alle Informationen, die wir über diese Maschine haben.

Das problem

Flash-Laufwerke zeigen sich als sehr unzuverlässige Geräte. Sie scheitern mit beneidenswerter Regelmäßigkeit. Dies führt sowohl zu Maschinenausfällen als auch (falls das Journal aus irgendeinem Grund nicht online übertragen werden konnte) zu Datenverlust.

Dies ist nicht die erste Erfahrung mit der Verwendung von Flash-Laufwerken, bevor es ein weiteres Projekt mit mehr als hundert Geräten gab, in denen das Magazin auf USB-Flash-Laufwerken gespeichert war, gab es auch Probleme mit der Zuverlässigkeit, wenn die Anzahl der Ausfälle pro Monat bei zehn lag. Wir haben verschiedene Flash-Laufwerke ausprobiert, darunter auch Marken-Laufwerke mit SLC-Speicher. Einige Modelle sind zuverlässiger als andere, aber das Ersetzen von Flash-Laufwerken hat das Problem nicht radikal gelöst.

Achtung! Longrid! Wenn Sie sich nicht für das Warum interessieren, sondern nur für das Wie, können Sie sofort zum Ende des Artikels gehen.

Lösung

Das erste, was mir in den Sinn kommt: MicroSD verlassen, zum Beispiel SSD einsetzen und davon booten. Theoretisch ist dies wahrscheinlich möglich, aber relativ teuer und nicht so zuverlässig (ein USB-SATA-Adapter wird hinzugefügt; bei Budget-SSDs ist die Ausfallstatistik ebenfalls nicht gut).

USB HDD sieht auch nicht besonders attraktiv aus.

Aus diesem Grund haben wir diese Option gewählt: Verlassen Sie den Download von MicroSD, verwenden Sie sie jedoch im schreibgeschützten Modus, und speichern Sie das Betriebsprotokoll (und andere Informationen, die nur für eine bestimmte Hardwarekomponente gelten - Seriennummer, Sensorkalibrierungen usw.) an einer anderen Stelle.

Das Thema Nur-Lese-FS für Himbeeren wurde bereits eingehend untersucht. Ich werde nicht auf die Implementierungsdetails in diesem Artikel eingehen (aber wenn Interesse besteht, schreibe ich möglicherweise einen Mini-Artikel zu diesem Thema) . Der einzige Punkt, den ich erwähnen möchte: sowohl aus persönlicher Erfahrung als auch aus Bewertungen, die bereits einen Gewinn an Zuverlässigkeit erzielt haben, ist. Ja, es ist unmöglich, Ausfälle vollständig zu beseitigen, aber es ist durchaus möglich, deren Häufigkeit erheblich zu verringern. Ja, und die Karten werden vereinheitlicht, was den Austausch für das Wartungspersonal erheblich vereinfacht.

Hardware

Es gab keinen Zweifel an der Wahl des Speichertyps - NOR Flash.
Argumente:

• einfache Verbindung (am häufigsten der SPI-Bus, dessen Erfahrung bereits vorhanden ist, sodass keine "Eisen" -Probleme zu erwarten sind);
• lächerlicher Preis;
• Standard-Betriebsprotokoll (die Implementierung ist bereits im Linux-Kernel, wenn Sie möchten, können Sie einen Dritten mitnehmen, der ebenfalls vorhanden ist, oder sogar Ihren eigenen schreiben, der Vorteil ist einfach);
• Zuverlässigkeit und Ressource:
  aus einem typischen Datenblatt: Daten werden 20 Jahre lang gespeichert, 100.000 Löschzyklen für jeden Block;
  aus Quellen von Drittanbietern: Extrem niedrige BER, es wird postuliert, dass keine Fehlerkorrekturcodes erforderlich sind (in einigen Veröffentlichungen wird ECC für NOR berücksichtigt, aber normalerweise ist MLC NOR dort gemeint, es passiert) .

Lassen Sie uns den Bedarf an Volumen und Ressourcen abschätzen.

Ich möchte die Garantie haben, Daten für mehrere Tage zu speichern. Dies ist notwendig, damit bei Problemen mit der Verbindung die Verkaufshistorie nicht verloren geht. Wir konzentrieren uns auf 5 Tage, in diesem Zeitraum (auch unter Berücksichtigung von Wochenenden und Feiertagen) können wir das Problem lösen.

Wir tippen derzeit ungefähr 100 KB Zeitschriften pro Tag (3-4.000 Datensätze), aber allmählich nimmt diese Zahl zu - die Detaillierung nimmt zu, neue Ereignisse werden hinzugefügt. Außerdem kommt es manchmal zu Bursts (einige Sensoren senden beispielsweise Spam-Mails mit False-Positives). Wir werden zehntausend Datensätze von 100 Bytes - Megabytes pro Tag berechnen.

Es werden insgesamt 5 MB saubere (gut komprimierbare) Daten ausgegeben. Sie auch (grobe Schätzung) 1 MB Service-Daten.

Das heißt, wir benötigen einen 8-MB-Mikrochip, wenn Sie keine Komprimierung verwenden, oder 4 MB, wenn Sie ihn verwenden. Ganz reelle Zahlen für diesen Speichertyp.

Was die Ressource betrifft: Wenn wir vorhaben, dass der gesamte Speicher nicht mehr als einmal alle 5 Tage neu geschrieben wird, erhalten wir in 10 Dienstjahren weniger als tausend Überschreibzyklen.
Ich erinnere mich, der Hersteller verspricht hunderttausend.

Wenn die Details interessant sind, wurde der at25df321a- Chip ausgewählt (dies ist jedoch unerheblich, es gibt viele Analoga auf dem Markt, die mit der Steckerbelegung und dem Befehlssystem kompatibel sind; selbst wenn wir den Chip von einem anderen Hersteller und / oder einer anderen Lautstärke verwenden möchten, funktioniert alles, ohne den Code zu ändern) .

Ich verwende den im Linux-Kernel integrierten Treiber unter Raspberry. Dank der Unterstützung für Gerätebaum-Overlays ist alles sehr einfach. Sie müssen das kompilierte Overlay in / boot / oversays einfügen und /boot/config.txt ein wenig ändern.

/* * 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 

Ich werde die Beschreibung des Verbindens des Chips mit dem Himbeer-Pi weglassen. Einerseits bin ich kein Experte für Elektronik, andererseits ist auch für mich alles trivial: Die Mikroschaltung hat nur 8 Beine, von denen wir Masse, Leistung, SPI (CS, SI, SO, SCK) benötigen; Stufen stimmen mit denen von Raspberry Pi überein, es ist keine zusätzliche Bindung erforderlich - schließen Sie einfach die angegebenen 6 Kontakte an.

Erklärung des Problems

Wie üblich durchläuft die Formulierung des Problems mehrere Iterationen, es scheint mir, dass die Zeit für die nächste gekommen ist. Also hören wir auf, fassen zusammen, was bereits geschrieben wurde, und klären die im Schatten verbleibenden Details.

Daher haben wir beschlossen, dass das Protokoll in SPI NOR Flash gespeichert wird.

Das Journal selbst repräsentiert eine Folge von Datensätzen variabler Länge. Eine typische Aufzeichnungslänge beträgt ungefähr 30 Bytes (obwohl manchmal Aufzeichnungen mit einer Länge von mehreren Kilobytes vorkommen). In diesem Fall arbeiten wir mit ihnen wie mit einer Reihe von Bytes. Wenn Sie jedoch interessiert sind, wird CBOR in den Datensätzen verwendet.

Zusätzlich zum Journal müssen einige aktualisierte „Tuning“ -Informationen gespeichert werden: eine bestimmte Geräte-ID, Sensorkalibrierung, das Flag „Gerät ist vorübergehend deaktiviert“ usw.
Bei diesen Informationen handelt es sich um eine Reihe von Schlüsselwertdatensätzen, die ebenfalls in CBOR gespeichert sind. Wir haben nicht viel von diesen Informationen (maximal einige Kilobyte), sie werden nur selten aktualisiert.
In Zukunft werden wir es Kontext nennen.

Wenn Sie sich erinnern, wo dieser Artikel begonnen hat, ist es sehr wichtig, die Zuverlässigkeit der Datenspeicherung und, wenn möglich, den Dauerbetrieb auch bei Hardwareausfällen / Datenkorruption sicherzustellen.

Welche Problemquellen können berücksichtigt werden?

• Während Schreib- / Löschvorgängen ausschalten. Dies ist aus der Kategorie "gegen Schrott kein Empfang".
  Informationen aus der Diskussion zum Stack-Austausch: Wenn die Stromversorgung ausgeschaltet wird, während mit Flash gearbeitet wird, führt das Löschen (Einstellung auf 1) und Schreiben (Einstellung auf 0) zu undefiniertem Verhalten: Daten können geschrieben, teilweise geschrieben werden (dh wir haben 10 Byte / 80 Bit übertragen) , und nur 45 Bits können aufgezeichnet werden), ist es auch möglich, dass sich einige der Bits im "Zwischen" -Zustand befinden (Lesen kann entweder 0 oder 1 ergeben);
• Fehler im Flash-Speicher selbst.
  BER ist zwar sehr niedrig, kann aber nicht gleich Null sein.
• Busfehler
  Die über SPI übertragenen Daten sind in keiner Weise geschützt, es kann durchaus zu Einzelbitfehlern oder Synchronisationsfehlern kommen - Verlust oder Einfügung von Bits (was zu massiven Datenverzerrungen führt);
• Sonstige Fehler / Ausfälle
  Fehler im Code, Himbeer "Pannen", Alien Intervention ...

Ich habe Anforderungen formuliert, deren Erfüllung meiner Meinung nach notwendig ist, um die Zuverlässigkeit zu gewährleisten:

• Aufzeichnungen sollten sofort in den Flash-Speicher geschrieben werden, anstehende Aufzeichnungen werden nicht berücksichtigt. - Wenn ein Fehler auftritt, sollte er so schnell wie möglich erkannt und verarbeitet werden. - Das System sollte nach Möglichkeit eine Fehlerbehebung durchführen.
  (Ein Beispiel aus dem Leben "wie es nicht sein sollte", das sich meiner Meinung nach alle getroffen haben: Nach einem Notfall-Neustart ist das Dateisystem "kaputt" und das Betriebssystem bootet nicht.)

Ideen, Ansätze, Gedanken

Als ich über diese Aufgabe nachdachte, schoss mir ein paar Ideen durch den Kopf, zum Beispiel:

• Verwenden Sie die Datenkomprimierung
• Verwenden Sie knifflige Datenstrukturen, und speichern Sie beispielsweise Datensatzheader getrennt von den Datensätzen, damit Sie den Rest problemlos lesen können, wenn in einem Datensatz ein Fehler auftritt.
• Verwenden Sie Bitfelder, um die Vollständigkeit der Aufzeichnung beim Ausschalten zu kontrollieren.
• Speichern Sie Prüfsummen für alles und alles;
• Verwenden Sie eine Art fehlerkorrigierende Codierung.

Einige dieser Ideen wurden verwendet, andere abgelehnt. Gehen wir in Ordnung.

Datenkomprimierung

Die Ereignisse, die wir im Tagebuch selbst aufzeichnen, sind ziemlich gleich und wiederholbar ("warf eine Münze von 5 Rubel", "klickte auf die Schaltfläche" Zustellung ändern ", ...). Daher sollte die Komprimierung sehr effektiv sein.

Der Overhead für die Komprimierung ist unbedeutend (der Prozessor, den wir haben, ist ziemlich leistungsfähig, selbst auf dem ersten Pi gab es einen Kern mit einer Frequenz von 700 MHz, auf aktuellen Modellen gab es mehrere Kerne mit einer Frequenz von mehr als einem Gigahertz), die Geschwindigkeit des Austauschs mit dem Speicher ist gering (mehrere Megabyte pro Sekunde), die Aufzeichnungsgröße ist gering. Wenn sich die Komprimierung auf die Leistung auswirkt, ist dies im Allgemeinen nur positiv (absolut unkritisch, nur mit Angabe) . Außerdem haben wir kein echtes eingebettetes, sondern gewöhnliches Linux - daher sollte die Implementierung keinen großen Aufwand erfordern (verknüpfen Sie einfach die Bibliothek und verwenden Sie mehrere Funktionen daraus).

Ein Stück des Protokolls wurde aus dem Arbeitsgerät entnommen (1,7 MB, 70.000 Datensätze) und zunächst mit den auf dem Computer verfügbaren gzip, lz4, lzop, bzip2, xz, zstd auf Komprimierbarkeit überprüft.

• gzip, xz, zstd zeigten ähnliche Ergebnisse (40 KB).
  Ich war überrascht, dass sich das modische xz hier auf der gzip- oder zstd-Ebene zeigte.
• lzip mit Standardeinstellungen ergab ein etwas schlechteres Ergebnis;
• lz4 und lzop zeigten keine sehr guten Ergebnisse (150Kb);
• bzip2 zeigte überraschend gute Ergebnisse (18Kb).

Die Daten sind also sehr gut komprimiert.
Wenn wir also keine schwerwiegenden Fehler finden, sollte es zu einer Komprimierung kommen! Nur weil mehr Daten auf dasselbe Flash-Laufwerk passen.

Denken wir über die Mängel nach.

Das erste Problem: Wir haben uns bereits darauf geeinigt, dass jede Aufnahme sofort aufblitzen soll. Normalerweise sammelt der Archivierer Daten aus dem Eingabestream, bis er entscheidet, dass es Zeit ist, in die Ausgabe zu schreiben. Wir müssen sofort einen komprimierten Datenblock abrufen und nichtflüchtig speichern.

Ich sehe drei Möglichkeiten:

1. Komprimieren Sie jeden Eintrag mithilfe der Wörterbuchkomprimierung anstelle der oben beschriebenen Algorithmen.
   Es ist eine funktionierende Option, aber ich mag es nicht. Um eine mehr oder weniger gute Komprimierung zu gewährleisten, sollte das Wörterbuch für bestimmte Daten „geschärft“ werden. Jede Änderung führt dazu, dass die Komprimierungsstufe katastrophal abfällt. Ja, das Problem wird gelöst, indem eine neue Version des Wörterbuchs erstellt wird. Dies bereitet jedoch Kopfzerbrechen. Wir müssen alle Versionen des Wörterbuchs speichern. In jedem Eintrag müssen wir angeben, mit welcher Version des Wörterbuchs es komprimiert wurde ...
2. Komprimieren Sie jeden Eintrag mit "klassischen" Algorithmen, jedoch unabhängig von den anderen.
   Die betrachteten Komprimierungsalgorithmen sind nicht für die Arbeit mit Datensätzen dieser Größe (zehn Bytes) ausgelegt. Der Komprimierungskoeffizient ist eindeutig kleiner als 1 (dh eine Erhöhung der Datenmenge anstelle der Komprimierung).
3. FLUSH nach jeder Aufnahme.
   Viele Komprimierungsbibliotheken unterstützen FLUSH. Dies ist ein Befehl (oder ein Parameter für die Komprimierungsprozedur), bei dessen Empfang der Archivierer einen komprimierten Stream generiert, sodass auf seiner Basis alle unkomprimierten Daten wiederhergestellt werden können, die bereits empfangen wurden. Solch ein Analogon der sync in Dateisystemen oder Festschreibung in SQL.
   Was wichtig ist, nachfolgende Komprimierungsvorgänge können das akkumulierte Wörterbuch verwenden und das Komprimierungsverhältnis wird nicht so stark leiden wie in der vorherigen Version.

Ich denke, es ist offensichtlich, dass ich die dritte Option gewählt habe. Lassen Sie uns genauer darauf eingehen.

Es gab einen großartigen Artikel über FLUSH in zlib.

Ich habe einen motivierten Test basierend auf dem Artikel durchgeführt und 70.000 Tagebucheinträge von einem realen Gerät mit einer Seitengröße von 60 KB entnommen (wir kehren zur Seitengröße zurück) :

Auf den ersten Blick ist der von FLUSH eingeführte Preis übermäßig hoch, aber in Wirklichkeit haben wir eine schlechte Wahl - entweder überhaupt nicht zu komprimieren oder mit FLUSH (und sehr effizient) zu komprimieren. Vergessen Sie nicht, dass wir 70.000 Datensätze haben. Die durch Z_PARTIAL_FLUSH eingeführte Redundanz beträgt nur 4-5 Bytes pro Datensatz. Und das Kompressionsverhältnis betrug fast 5: 1, was mehr als ein hervorragendes Ergebnis ist.

Insgesamt habe ich 3-4 Bytes pro Datensatz aus meinen Testdaten erhalten, das Kompressionsverhältnis betrug mehr als 6: 1. Ehrlich gesagt habe ich nicht mit einem solchen Ergebnis gerechnet. Meiner Meinung nach ist alles, was besser als 2: 1 ist, bereits ein Ergebnis, das die Verwendung von Komprimierung rechtfertigt.

Alles ist in Ordnung, aber zlib (deflate) ist immer noch archaisch wohlverdienter und etwas altmodischer Kompressionsalgorithmus. Die bloße Tatsache, dass die letzten 32 KB aus dem unkomprimierten Datenstrom als Wörterbuch verwendet werden, sieht heute seltsam aus (dh, wenn ein Datenblock dem Datenstrom mit 40 KB sehr ähnlich ist, wird er erneut archiviert, jedoch nicht siehe den letzten Eintrag). In modisch Die Größe eines modernen Archivierungswörterbuchs wird häufig eher in Megabyte als in Kilobyte gemessen.

Also setzen wir unsere Mini-Studie der Archivare fort.

Als nächstes wurde bzip2 getestet (erinnere dich, ohne FLUSH zeigte es ein fantastisches Kompressionsverhältnis von fast 100: 1). Leider zeigte sich bei FLUSH sehr schlecht, dass die Größe der komprimierten Daten größer war als die der unkomprimierten.

Und zstd wurde als letztes getestet. Abhängig von den Parametern wird es entweder auf der Ebene von gzip komprimiert, aber viel schneller, oder gzip ist besser.

Leider hat er sich mit FLUSH als "nicht sehr" erwiesen: Die Größe der komprimierten Daten betrug etwa 700 KB.

Ich habe eine Frage auf der Projektseite in Github gestellt und eine Antwort erhalten, dass es sich lohnt, für jeden Block komprimierter Daten mit bis zu 10 Byte Servicedaten zu rechnen, was nahe an den Ergebnissen liegt. Das Abfangen von deflate funktioniert nicht.

Ich habe mich dazu entschlossen, in Experimenten mit Archiven damit aufzuhören (ich erinnere Sie daran, dass sich xz, lzip, lzo, lz4 im Teststadium nicht ohne FLUSH zeigten, aber exotischere Kompressionsalgorithmen nicht in Betracht zogen).

Wir kehren zu den Problemen der Archivierung zurück.

Das zweite (wie sie sagen, in der Reihenfolge, aber nicht im Wert) Problem - die komprimierten Daten sind ein einzelner Stream, in dem ständig an vorherige Abschnitte gesendet wird. Wenn also ein Abschnitt der komprimierten Daten beschädigt wird, verlieren wir nicht nur den Block der nicht komprimierten Daten, sondern auch alle nachfolgenden.

Es gibt einen Lösungsansatz für dieses Problem:

1. Verhindern Sie das Auftreten eines Problems - fügen Sie den komprimierten Daten Redundanz hinzu, um Fehler zu identifizieren und zu korrigieren. wir werden später darüber sprechen;
2. Minimieren Sie die Konsequenzen im Falle eines Problems
   Wir haben bereits früher gesagt, dass es möglich ist, jeden Datenblock einzeln zu komprimieren, und dass das Problem von selbst verschwindet (Datenkorruption eines Blocks führt nur zum Verlust von Daten dieses Blocks). Dies ist jedoch ein extremer Fall, in dem die Datenkomprimierung ineffizient ist. Das gegenteilige Extrem: Verwenden Sie alle 4 MB unseres Mikrokreislaufs als ein einziges Archiv, wodurch wir eine hervorragende Komprimierung erzielen, aber katastrophale Folgen im Falle einer Datenkorruption haben.
   Ja, ein Kompromiss hinsichtlich der Zuverlässigkeit ist erforderlich. Wir müssen jedoch bedenken, dass wir ein Datenspeicherformat für nichtflüchtigen Speicher mit einer extrem niedrigen BER und einer angegebenen Datenspeicherdauer von 20 Jahren entwickeln.

Im Verlauf der Experimente stellte ich fest, dass bei komprimierten Datenblöcken mit einer Größe von weniger als 10 KB mehr oder weniger spürbare Verluste im Komprimierungsgrad auftreten.
Es wurde bereits erwähnt, dass der verwendete Speicher eine Seitenorganisation hat. Ich sehe keinen Grund, warum Sie die Korrespondenz "eine Seite - ein Block komprimierter Daten" nicht verwenden sollten.

Das heißt, die minimale angemessene Seitengröße beträgt 16 KB (mit einer Spanne für Serviceinformationen). Eine so kleine Seitengröße führt jedoch zu erheblichen Einschränkungen der maximalen Aufzeichnungsgröße.

Obwohl ich immer noch keine komprimierten Aufzeichnungen von mehr Kilobyte-Einheiten erwarte, habe ich mich für die Verwendung von 32 KB-Seiten (insgesamt 128 Seiten pro Chip) entschieden.

Zusammenfassung:

• Wir speichern Daten, die mit zlib (deflate) komprimiert wurden.
• Setzen Sie für jeden Datensatz Z_SYNC_FLUSH;
• Für jeden komprimierten Datensatz werden die letzten Bytes abgeschnitten (z. B. 0x00, 0x00, 0xff, 0xff) . Geben Sie im Header an, wie viele Bytes wir schneiden.
• Wir speichern Daten auf 32-KB-Seiten. Innerhalb der Seite befindet sich ein einzelner Strom komprimierter Daten. Auf jeder Seite wird die Komprimierung erneut gestartet.

Und bevor ich mit der Komprimierung fertig bin, möchte ich darauf hinweisen, dass wir nur wenige Bytes an Schreibdaten erhalten. Daher ist es äußerst wichtig, die Serviceinformationen nicht zu vergrößern, da jedes Byte gezählt wird.

Speichern von Datenköpfen

Da wir Datensätze mit variabler Länge haben, müssen wir irgendwie den Ort / die Grenzen der Datensätze bestimmen.

Ich kenne drei Ansätze:

1. Alle Datensätze werden in einem fortlaufenden Stream gespeichert. Zuerst wird der Datensatzkopf mit der Länge und dann der Datensatz selbst angezeigt.
   In dieser Ausführungsform können sowohl die Header als auch die Daten eine variable Länge haben.
   Tatsächlich erhalten wir eine einfach verknüpfte Liste, die ständig verwendet wird.
2. Header und Datensätze selbst werden in separaten Streams gespeichert.
   Mit Headern konstanter Länge stellen wir sicher, dass Schäden an einem Header den Rest nicht beeinträchtigen.
   Ein ähnlicher Ansatz wird beispielsweise in vielen Dateisystemen verwendet.
3. Datensätze werden in einem kontinuierlichen Datenstrom gespeichert, die Grenze des Datensatzes wird durch einen Marker (Symbol / Zeichenfolge, die in Datenblöcken verboten ist / ist) festgelegt. Wenn ein Marker im Datensatz gefunden wird, ersetzen wir ihn durch eine bestimmte Sequenz (Escape-Zeichen).
   Ein ähnlicher Ansatz wird beispielsweise im PPP-Protokoll verwendet.

Ich werde es veranschaulichen.

Variante 1:

Hier ist alles ganz einfach: Wenn wir die Länge des Datensatzes kennen, können wir die Adresse des nächsten Headers berechnen. Also bewegen wir uns durch die Header, bis wir auf eine Region treffen, die mit 0xff (freie Region) oder dem Ende der Seite gefüllt ist.

Option 2:

Aufgrund der variablen Länge des Datensatzes können wir nicht im Voraus sagen, wie viele Datensätze (und damit die Überschriften) pro Seite wir benötigen. Sie können die Überschriften und die Daten selbst auf verschiedene Seiten verteilen, aber ich bevorzuge einen anderen Ansatz: Wir platzieren die Überschriften und die Daten auf derselben Seite, die Überschriften (mit konstanter Größe) befinden sich jedoch am Anfang der Seite und die Daten (mit variabler Länge) am Ende. Sobald sie sich "treffen" (es ist nicht genügend Speicherplatz für einen neuen Datensatz vorhanden) - betrachten wir diese Seite als voll.

Option 3:

Es ist nicht erforderlich, die Länge oder andere Informationen über den Speicherort der Daten im Header zu speichern. Es gibt genügend Markierungen, die die Grenzen der Datensätze angeben. Die Daten müssen jedoch während des Schreibens / Lesens verarbeitet werden.
Als Markierung würde ich 0xff verwenden (welches die Seite nach dem Löschen füllt), so dass der freie Bereich definitiv nicht als Daten behandelt wird.

Vergleichstabelle:

Option 1 hat einen schwerwiegenden Fehler: Wenn einer der Header beschädigt ist, wird unsere gesamte nachfolgende Kette zerstört. Mit anderen Optionen können Sie einen Teil der Daten auch bei massivem Schaden wiederherstellen.
Wir möchten jedoch daran erinnern, dass wir uns entschlossen haben, die Daten in komprimierter Form zu speichern, und daher alle Daten auf der Seite nach dem "kaputten" Datensatz verlieren, sodass wir dies nicht berücksichtigen, obwohl die Tabelle negativ ist.

Kompaktheit:

• In der ersten Version müssen wir nur die Länge im Header speichern. Wenn Ganzzahlen mit variabler Länge verwendet werden, können wir in den meisten Fällen mit einem Byte arbeiten.
• In der zweiten Option müssen wir die Startadresse und die Startlänge speichern. Der Datensatz sollte eine konstante Größe haben. Ich schätze 4 Bytes pro Datensatz (zwei Bytes pro Versatz und zwei Bytes pro Länge).
• Bei der dritten Option ist nur ein Zeichen ausreichend, um den Beginn der Aufzeichnung anzuzeigen, und die Aufzeichnung selbst wächst aufgrund der Überprüfung um 1 bis 2%. Im Allgemeinen ungefähre Parität mit der ersten Option.

( ). , .

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

: , , .. , , , — , .

: " — " - .

, , :
.
, 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. 
   .

( ) . , - .

: , , , ( , ).

Andere

, ( ) , , .

• ""
  - , .., , .
  , , ;
• .
  — !
  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.

Fazit

, .

, : - , , . , () - .

, ? , . , , . - .

? , , . .

, , " ".

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

, .

Literatur

, .

, , , :

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