Hintergrund

Wir haben eigens entwickelte Verkaufsautomaten. Im Inneren befindet sich ein Raspberry Pi sowie eine kleine Zusatzplatine. Angeschlossen sind ein Münzprüfer, ein Geldscheineinzug und ein Bankterminal... Alles wird von einer selbstgeschriebenen Software gesteuert. Sämtliche Betriebsdaten werden in einem Protokoll auf einem Flash-Speicher (MicroSD) gespeichert, das dann über das Internet (mithilfe eines USB-Modems) an einen Server übertragen wird, wo sie in einer Datenbank abgelegt werden. Verkaufsinformationen werden in 1C hochgeladen, zudem gibt es ein einfaches Web-Interface zur Überwachung usw.

Das Protokoll ist also von entscheidender Bedeutung – für die Buchführung (Einnahmen, Verkäufe usw.), die Überwachung (verschiedene Störungen und andere unvorhergesehene Ereignisse); man kann sagen, dies sind alle Informationen, die wir über diesen Automaten haben.

Das Problem

USB-Sticks erweisen sich als sehr unzuverlässige Geräte. Sie gehen mit bemerkenswerter Regelmäßigkeit kaputt. Dies führt sowohl zu Ausfällen der Automaten als auch (wenn aus bestimmten Gründen das Protokoll nicht online übertragen werden kann) zu Datenverlusten.

Dies ist nicht das erste Mal, dass ich USB-Sticks verwende. Zuvor hatte ich ein anderes Projekt mit über hundert Geräten, bei dem das Protokoll auf USB-Sticks gespeichert wurde. Auch dort gab es Probleme mit der Zuverlässigkeit; manchmal zählte die Anzahl der defekten Geräte im Monat in die Dutzende. Wir haben verschiedene Sticks ausprobiert, einschließlich Markenmodelle mit SLC-Speicher. Einige Modelle waren zuverlässiger als andere, aber der Austausch der Sticks hat das Problem nicht grundlegend gelöst.

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

Lösung

Das Erste, was mir in den Sinn kommt: auf MicroSD zu verzichten, stattdessen beispielsweise SSDs zu verwenden und von diesen zu booten. Theoretisch möglich, denke ich, aber relativ teuer und nicht so zuverlässig (ein USB-SATA-Adapter kommt hinzu; auch bei preiswerten SSDs ist die Ausfallrate nicht erfreulich).

USB-Festplatten scheinen ebenfalls keine besonders attraktive Lösung zu sein.

Deshalb sind wir zu folgender Option gekommen: Den Bootvorgang von der MicroSD beizubehalten, aber sie im read-only Modus zu verwenden und das Arbeitsprotokoll (sowie andere, für das jeweilige Gerät einzigartige Informationen – Seriennummer, Kalibrierungen der Sensoren usw.) an einem anderen Ort zu speichern.

Das Thema des schreibgeschützten Dateisystems für die Raspberry Pi wurde bereits ausführlich behandelt, daher möchte ich in diesem Artikel nicht auf die Details der Implementierung eingehen. (aber falls Interesse besteht, könnte ich vielleicht einen kleinen Artikel zu diesem Thema schreiben.)Ein einziger Punkt ist erwähnenswert: Sowohl aus persönlicher Erfahrung als auch aus Rückmeldungen von Nutzern, die bereits implementiert haben, gibt es einen Gewinn in der Zuverlässigkeit. Ja, es ist unmöglich, alle Ausfälle zu vermeiden, aber die Frequenz erheblich zu reduzieren – das ist durchaus realistisch. Außerdem werden die Karten einheitlich, was den Austausch für das Wartungspersonal deutlich vereinfacht.

Hardware

Bei der Auswahl des Speichertyps gab es keine besonderen Zweifel – NOR Flash.
Argumente:

• einfache Verbindung (in der Regel über den SPI-Bus, dessen Nutzungserfahrung bereits vorhanden ist, sodass keine 'Hardware'-Probleme zu erwarten sind);
• lächerlicher Preis;
• standardisiertes Protokoll (Implementierungen sind bereits im Linux-Kernel vorhanden, man kann auch externe Lösungen verwenden oder sogar eigene schreiben, da alles recht einfach ist);
• Zuverlässigkeit und Lebensdauer:
  aus einem typischen Datenblatt: Die Daten werden 20 Jahre lang gespeichert, 100.000 Löschzyklen für jeden Block;
  aus externen Quellen: extrem niedriger BER, es wird die Notwendigkeit von Fehlerkorrekturcodes postuliert (in einigen Arbeiten wird ECC für NOR behandelt, meistens ist jedoch MLC NOR gemeint, es kommt auch vor).

Lassen Sie uns die Anforderungen an Volumen und Ressourcen abschätzen.

Es ist wichtig, dass die Daten über mehrere Tage hinweg garantiert gespeichert werden. Dies ist notwendig, um sicherzustellen, dass im Falle von Kommunikationsproblemen die Verkaufsdaten nicht verloren gehen. Wir orientieren uns an 5 Tagen, in diesem Zeitraum (selbst unter Berücksichtigung von Wochenenden und Feiertagen) kann das Problem gelöst werden.

Derzeit sammeln wir täglich etwa 100 kB Log-Daten (3-4 Tausend Einträge), jedoch wächst diese Zahl allmählich — die Detailgenauigkeit nimmt zu, neue Ereignisse werden hinzugefügt. Außerdem gibt es manchmal Ausreißer (ein Sensor fängt an, falsche Alarme zu spammen, zum Beispiel). Wir rechnen mit 10.000 Einträgen zu 100 Byte — das sind ein Megabyte pro Tag.

Insgesamt kommen wir auf 5 MB an komprimierbaren (guten) Daten. Dazu kommen noch (grob geschätzt) 1 MB an Steuerdaten.

Das heißt, wir benötigen einen Chip mit 8 MB, wenn wir keine Komprimierung verwenden, oder 4 MB, wenn wir sie verwenden. Völlig realistische Zahlen für diesen Speichertyp.

Betrachtet man die Ressource: Wenn wir annehmen, dass der Speicher nicht häufiger als alle 5 Tage neu beschrieben wird, ergeben sich über 10 Jahre weniger als tausend Schreibzyklen.
Ich erinnere daran, dass der Hersteller hunderttausend verspricht.

Ein wenig über NOR vs NAND

Heutzutage ist NAND-Speicher natürlich deutlich beliebter, aber für dieses Projekt würde ich ihn nicht verwenden: NAND erfordert im Gegensatz zu NOR unbedingt die Verwendung von Fehlerkorrekturcodes, Defektlisten usw., und die Pins von NAND-Chips sind normalerweise auch deutlich zahlreicher.

Als Nachteile von NOR können aufgeführt werden:

• geringer Speicher (und damit ein hoher Preis pro Megabyte);
• nicht sehr hohe Übertragungsgeschwindigkeit (hauptsächlich wegen der Verwendung eines seriellen Interfaces, normalerweise SPI oder I2C);
• langsame Löschung (je nach Blockgröße dauert sie von wenigen Millisekunden bis zu mehreren Sekunden).

Scheinbar nichts Kritisches für uns, also machen wir weiter.

Falls weitere Details interessieren, wurde der Chip ausgewählt at25df321a (aber das ist unwesentlich, der Markt ist voll von Alternativen, die mit der Pinbelegung und dem Befehlssystem kompatibel sind; selbst wenn wir einen Chip eines anderen Herstellers und/oder in einem anderen Umfang installieren wollen, funktioniert alles ohne Änderung des Codes).

Ich verwende den im Linux-Kernel eingebetteten Treiber; auf Raspberry ist es dank der Unterstützung von Device Tree Overlays ganz einfach – man muss einfach das kompilierte Overlay in /boot/overlays legen und ein wenig /boot/config.txt modifizieren.

Beispiel für eine dts-Datei

Ehrlich gesagt bin ich mir nicht sicher, ob es ohne Fehler geschrieben ist, aber es funktioniert.

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

Und noch eine Zeile in config.txt

dtoverlay=at25:spimaxfrequency=50000000

Die Beschreibung der Verbindung des Chips mit dem Raspberry Pi lasse ich weg. Einerseits bin ich kein Elektronikexperte, andererseits ist es sogar für mich banaler: Der Chip hat nur 8 Pins, von denen wir Erde, Strom, SPI (CS, SI, SO, SCK) benötigen; die Pegel stimmen mit denen des Raspberry Pi überein, zusätzliche Verkabelung ist nicht erforderlich – einfach die angegebenen 6 Kontakte verbinden.

Problemstellung

Wie üblich erfolgt die Aufgabenstellung in mehreren Iterationen; ich glaube, jetzt ist es an der Zeit für die nächste. Also lasst uns innehalten, alles zusammenfassen, was bereits geschrieben wurde, und die verbliebenen Details klären.

Wir haben uns entschieden, dass das Protokoll im SPI NOR Flash gespeichert wird.

Was ist NOR Flash für diejenigen, die es nicht wissen?

Es handelt sich um nichtflüchtigen Speicher, mit dem drei Operationen durchgeführt werden können:

1. Lesen:
   Das ganz gewöhnliche Lesen: Wir geben die Adresse an und lesen so viele Bytes, wie wir benötigen;
2. Schreiben:
   Das Schreiben in NOR Flash sieht zwar gewöhnlich aus, hat aber eine Besonderheit: Man kann nur 1 in 0 ändern, aber nicht umgekehrt. Wenn in unserer Speicherzelle z.B. 0x55 stand, wird nach dem Schreiben von 0x0f dort 0x05 gespeichert. (siehe Tabelle etwas weiter unten);
3. Löschen:
   Natürlich müssen wir auch die umgekehrte Operation durchführen können – 0 in 1 ändern, dafür gibt es die Löschoperation. Im Gegensatz zu den ersten beiden operiert sie nicht mit Bytes, sondern mit Blöcken (der minimale Löschblock im gewählten Chip beträgt 4 KB). Das Löschen vernichtet den gesamten Block und ist der einzige Weg, 0 in 1 zu ändern. Daher muss man beim Arbeiten mit Flash-Speicher häufig die Datenstrukturen an die Grenze des Löschblocks anpassen.
   Schreiben in NOR Flash:

Binäre Daten

War
01010101

Geschrieben
00001111

Ist
00000101

Das Journal stellt eine Sequenz von variablen Länge dar. Die typische Länge eines Eintrags beträgt etwa 30 Bytes (obwohl es manchmal auch Einträge mit mehreren Kilobytes gibt). In diesem Fall arbeiten wir mit ihnen einfach als mit einem Byte-Array, aber, falls es interessiert, wird innerhalb der Einträge CBOR verwendet.

Neben dem Journal benötigen wir einige "Konfigurations"-Informationen, sowohl aktualisierbare als auch nicht: eine Art Geräte-ID, Kalibrierungen der Sensoren, ein Flag, dass "Gerät vorübergehend deaktiviert" ist, etc.
Diese Informationen stellen eine Reihe von Schlüssel-Wert-Paaren dar, die ebenfalls in CBOR gespeichert sind. Diese Informationen sind nicht sehr umfangreich (höchstens einige Kilobytes) und werden nicht häufig aktualisiert.
Im Folgenden werden wir sie Kontext nennen.

Wenn wir uns erinnern, womit dieser Artikel begann, ist es sehr wichtig, die Zuverlässigkeit der Datenspeicherung zu gewährleisten und, wenn möglich, einen ununterbrochenen Betrieb selbst im Falle von Hardwarefehlern/Datenbeschädigungen sicherzustellen.

Welche Problemquellen können wir betrachten?

• Stromausfälle während der Schreib-/Löschvorgänge. Das gehört zum Bereich "Gegen einen Schlag gibt es kein Mittel".
  Informationen aus Diskussion bei stackexchange: Wenn die Stromversorgung während der Arbeit mit Flash abgeschaltet wird, führen sowohl erase (Einstellung auf 1) als auch write (Einstellung auf 0) zu nicht definiertem Verhalten: Die Daten können vollständig, teilweise (zum Beispiel haben wir 10 Byte/80 Bit übergeben, aber es wurden nur 45 Bit geschrieben) oder möglicherweise in einem "Zwischen"-Zustand gespeichert werden (die Lesung kann sowohl 0 als auch 1 ausgeben);
• Fehler im Flash-Speicher selbst.
  BER ist zwar sehr niedrig, kann aber nicht null sein;
• Busfehler
  Die über SPI übermittelten Daten sind nicht geschützt, sodass sowohl einzelne Bitfehler als auch Synchronisationsfehler – das Verlieren oder Einfügen von Bits (was zu massiven Datenverzerrungen führt) – auftreten können;
• Andere Fehler/Störungen
  Codefehler, "Glitches" des Raspberry, das Eingreifen von Außerirdischen…

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

• Schreibvorgänge müssen sofort in den Flash-Speicher gelangen, verzögerte Schreibvorgänge werden nicht berücksichtigt; - wenn ein Fehler auftritt, sollte er so früh wie möglich erkannt und behandelt werden; - das System sollte nach Möglichkeit nach Fehlern wieder funktionsfähig gemacht werden.
  (Beispiel aus dem Leben, das wir alle kennen: Nach einem unerwarteten Neustart ist das Dateisystem beschädigt, und das Betriebssystem lässt sich nicht starten.)

Ideen, Ansätze, Überlegungen

Als ich begann, über dieses Problem nachzudenken, schossen mir viele Ideen durch den Kopf, zum Beispiel:

• Datenkompression verwenden;
• schlaue Datenstrukturen nutzen, zum Beispiel die Header separat von den Datensätzen zu speichern, damit man im Falle eines Fehlers in einem Datensatz die anderen problemlos lesen kann;
• Bitfelder zur Kontrolle der Vollständigkeit der Daten bei Stromausfall verwenden;
• Prüfziffern für alles speichern;
• irgendeine Art von fehlerresistenter Codierung einsetzen.

Ein Teil dieser Ideen wurde umgesetzt, andere wurden verworfen. Lassen Sie uns der Reihe nach vorgehen.

Datenkompression

Die Ereignisse, die wir im Protokoll festhalten, sind ziemlich gleichförmig und wiederholend ("5-Rubel-Münze geworfen", "Knopf für Rückgeld gedrückt", …). Daher sollte die Kompression recht effektiv sein.

Die Overheadkosten für die Kompression sind unbedeutend (unser Prozessor ist leistungsstark genug; selbst im ersten Pi hatte es einen Kern mit 700 MHz, während aktuelle Modelle mehrere Kerne mit über einem Gigahertz besitzen). Die Speicherübertragungsrate ist nicht hoch (einige Megabyte pro Sekunde) und die Datensatzgrößen sind gering. Insgesamt, auch wenn die Kompression die Leistung beeinflussen sollte, wird es nur einen positiven Effekt haben. (völlig unwichtig, nur eine Feststellung). Zudem verwenden wir kein echtes Embedded-System, sondern ein reguläres Linux — daher sollte die Implementierung nicht viel Aufwand erfordern (es genügt, die Bibliothek anzubinden und einige Funktionen daraus zu verwenden).

Ein Ausschnitt aus einem Log eines laufenden Geräts (1,7 MB, 70.000 Einträge) wurde genommen und zunächst auf Komprimierbarkeit mit den auf dem Computer verfügbaren Werkzeugen gzip, lz4, lzop, bzip2, xz, zstd getestet.

• gzip, xz, zstd zeigten ähnliche Ergebnisse (40 KB).
  Es war überraschend, dass das angesagte xz hier auf einem Niveau mit gzip oder zstd abschnitt;
• lzip mit den Standardeinstellungen lieferte ein etwas schlechteres Ergebnis;
• lz4 und lzop zeigten ein eher unbefriedigendes Ergebnis (150 KB);
• bzip2 zeigte überraschend gute Ergebnisse (18 KB).

Zusammenfassend lässt sich sagen, dass die Daten sehr gut komprimierbar sind.
Also, (sofern wir keine fatalen Mängel finden) wird es also eine Kompression geben! Einfach weil mehr Daten auf dasselbe Flash-Laufwerk passen.

Lassen Sie uns über die Nachteile nachdenken.

Das erste Problem: Wir haben bereits vereinbart, dass jeder Datensatz sofort auf das Flash-Speichergerät übertragen werden muss. Normalerweise sammelt ein Archivierungsprogramm Daten aus dem Eingangsstrom, bis es entscheidet, dass es Zeit ist, in den Ausgang zu schreiben. Wir hingegen benötigen sofort einen komprimierten Datenblock und müssen ihn im nichtflüchtigen Speicher ablegen.

Ich sehe drei Möglichkeiten:

1. Jeden Datensatz mit Hilfe von Wörterbuchkompression zu komprimieren, anstatt die oben besprochenen Algorithmen zu verwenden.
   Eine durchaus praktikable Option, die mir jedoch nicht zusagt. Um ein einigermaßen anständiges Kompressionsniveau zu gewährleisten, muss das Wörterbuch auf spezifische Daten abgestimmt sein; jede Veränderung würde zu einem katastrophalen Rückgang des Kompressionsniveaus führen. Ja, das Problem kann durch die Erstellung einer neuen Version des Wörterbuchs gelöst werden, aber das ist lästig — wir müssten alle Versionen des Wörterbuchs speichern; in jedem Datensatz müssten wir angeben, mit welcher Version des Wörterbuchs er komprimiert wurde...
2. Jeden Datensatz mit 'klassischen' Algorithmen zu komprimieren, jedoch unabhängig von anderen.
   Die in Betracht gezogenen Kompressionsalgorithmen sind nicht darauf ausgelegt, mit Datensätzen dieser Größe (Dutzende von Bytes) zu arbeiten, der Kompressionsfaktor wird eindeutig kleiner als 1 sein (was bedeutet, dass das Datenvolumen ansteigt statt sinkt);
3. Führen Sie nach jedem Datensatz ein FLUSH durch.
   Viele Kompressionsbibliotheken unterstützen FLUSH. Dies ist ein Befehl (oder ein Parameter für den Kompressionsprozess), der es dem Archivierungsprogramm ermöglicht, einen komprimierten Strom zu bilden, sodass auf dessen Grundlage alle unkomprimierten Daten, die bereits empfangen wurden, wiederhergestellt werden können. Dies istanalog zu sync in Dateisystemen oder commit in SQL.
   Wichtig ist, dass nachfolgende Komprimierungsoperationen das angehäufte Wörterbuch nutzen können und der Kompressionsgrad nicht so stark leidet wie im vorherigen Fall.

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

Es wurde ein ausgezeichneter Artikel über FLUSH in zlib gefunden.

Ich habe basierend auf dem Artikel einen Test durchgeführt, ich habe 70.000 Protokolleinträge von einem realen Gerät mit einer Seitengröße von 60 KB genommen (zur Seitengröße werden wir noch zurückkommen) erhalten:

Rohdaten
gzip-Kompression -9 (ohne FLUSH)
zlib mit Z_PARTIAL_FLUSH
zlib mit Z_SYNC_FLUSH

Größe, KB
1692
40
352
604

Auf den ersten Blick scheint der Preis, den FLUSH verlangt, übertrieben hoch zu sein, jedoch ist unsere Auswahl tatsächlich begrenzt – entweder gar nicht komprimieren oder effektiv mit FLUSH komprimieren. Man darf nicht vergessen, dass wir 70.000 Datensätze haben, und die durch Z_PARTIAL_FLUSH eingeführte Redundanz beträgt nur 4-5 Byte pro Datensatz. Und das Kompressionsverhältnis lag bei fast 5:1, was ein hervorragendes Ergebnis ist.

Es mag überraschend erscheinen, aber tatsächlich ist Z_SYNC_FLUSH ein effizienterer Weg, um FLUSH durchzuführen.

Im Fall der Verwendung von Z_SYNC_FLUSH werden die letzten 4 Bytes jedes Datensatzes immer 0x00, 0x00, 0xff, 0xff sein. Wenn wir diese kennen, können wir sie weglassen, wodurch die endgültige Größe nur 324 KB beträgt.

Der Artikel, auf den ich mich beziehe, enthält eine Erklärung:

Ein neuer Typ-0-Block mit leeren Inhalten wird angehängt.

Ein Typ-0-Block mit leeren Inhalten besteht aus:

• dem dreibitigen Blockkopf;
• 0 bis 7 Bits, die gleich null sind, um die Byte-Ausrichtung zu erreichen;
• der vier Byte langen Sequenz 00 00 FF FF.

Wie man leicht merkt, kommen im letzten Block vor diesen 4 Bytes zwischen 3 und 10 Null-Bits vor. Die Praxis hat jedoch gezeigt, dass es in Wirklichkeit mindestens 10 Null-Bits sind.

Es stellt sich heraus, dass so kurze Datenblöcke normalerweise (immer?) mit einem Block vom Typ 1 (fester Block) kodiert werden, der unbedingt mit 7 Null-Bits endet. Insgesamt erhalten wir 10-17 garantiert nullen Bits (und die restlichen werden mit einer Wahrscheinlichkeit von etwa 50% null sein).

Bei den Testdaten wird in 100% der Fälle vor 0x00, 0x00, 0xff, 0xff ein Null-Byte angezeigt, und in mehr als einem Drittel der Fälle — zwei Null-Bytes. (Vielleicht liegt es daran, dass ich binären CBOR verwende, während beim Einsatz von textuellem JSON häufiger Blöcke vom Typ 2 — dynamischer Block — vorkommen würden, entsprechend würden Blöcke ohne zusätzliche Null-Bytes vor 0x00, 0x00, 0xff, 0xff auftreten.).

Insgesamt kann man mit den vorhandenen Testdaten in weniger als 250KB komprimierten Daten auskommen.

Man kann noch etwas mehr sparen, indem man mit den Bits jongliert: Derzeit ignorieren wir die Existenz mehrerer Null-Bits am Ende des Blocks, einige Bits am Anfang des Blocks ändern sich ebenfalls nicht…
Aber hier habe ich die Entscheidung getroffen, aufzuhören, denn bei solchem Tempo könnte ich zur Entwicklung meines eigenen Archivierers gelangen.

Insgesamt habe ich aus meinen Testdaten 3-4 Bytes pro Aufzeichnung erhalten, und das Kompressionsverhältnis betrug mehr als 6:1. Ehrlich gesagt hatte ich nicht mit einem solchen Ergebnis gerechnet; meiner Meinung nach ist alles, was besser als 2:1 ist, bereits ein Ergebnis, das den Einsatz von Kompression rechtfertigt.

Alles prima, aber zlib (deflate) ist schließlich ein bewährter, wenn auch etwas altmodischer Kompressionsalgorithmus. Allein die Tatsache, dass die letzten 32 KB aus dem unkomprimierten Datenstrom als Wörterbuch verwendet werden, wirkt heute seltsam (das heißt, wenn ein Datenblock sehr ähnlich dem ist, was vor 40 KB im Eingangsstrom war, wird er neu archiviert und nicht auf den vorherigen Auftritt verwiesen). In modernen Komprimierungsprogrammen wird die Größe des Wörterbuchs häufiger in Megabytes und nicht in Kilobytes gemessen.

Lassen Sie uns also unsere kleine Untersuchung der Archivierungsprogramme fortsetzen.

Als Nächstes wurde bzip2 getestet (ich erinnere daran, dass es ohne FLUSH eine fantastische Kompressionsrate von fast 100:1 zeigte). Leider schnitt es mit FLUSH sehr schlecht ab, die Größe der komprimierten Daten war größer als die der unkomprimierten.

Meine Vermutungen über die Gründe für das Versagen

Libbz2 bietet nur eine Option für den Flush an, die anscheinend das Wörterbuch leert (ähnlich wie Z_FULL_FLUSH in zlib). Von einer effektiven Kompression danach kann man nicht sprechen.

Der letzte Test war mit zstd. Je nach Parametern komprimiert es entweder auf Gzip-Niveau, aber viel schneller, oder besser als Gzip.

Leider war das Ergebnis mit FLUSH nicht zufriedenstellend: Die komprimierten Daten lagen bei etwa 700 KB.

Ich habe eine Frage auf der Projektseite in Github gestellt und die Antwort erhalten, dass man mit bis zu 10 Byte Metadaten pro Block komprimierter Daten rechnen sollte, was den erhaltenen Ergebnissen nahe kommt. Deflate wird dadurch nicht eingeholt.

Damit habe ich beschlossen, meine Experimente mit Archivierern zu beenden (zur Erinnerung: xz, lzip, lzo, lz4 haben sich bereits in der Testphase ohne FLUSH nicht bewährt, und ich habe es nicht gewagt, exotischere Algorithmen zu betrachten).

Kehren wir zu den Problemen der Archivierung zurück.

Das zweite Problem (in der Reihenfolge, nicht in der Bedeutung) besteht darin, dass komprimierte Daten einen einheitlichen Stream darstellen, in dem ständig Verweise auf vorherige Abschnitte erfolgen. Daher verlieren wir bei einer Beschädigung eines Teils der komprimierten Daten nicht nur den zugehörigen Block unkomprimierter Daten, sondern auch alle nachfolgenden.

Es gibt Ansätze zur Lösung dieses Problems:

1. Probleme proaktiv zu vermeiden – durch Hinzufügen von Redundanz in die komprimierten Daten, die es ermöglicht, Fehler zu erkennen und zu beheben; dazu werden wir später mehr sagen;
2. Die Auswirkungen im Falle eines Problems zu minimieren.
   Wir haben bereits erwähnt, dass jeder Datenblock unabhängig komprimiert werden kann, wodurch das Problem von selbst gelöst wird (die Beschädigung der Daten eines Blocks führt nur zum Verlust dieser Blockdaten). Dies ist jedoch der Extremfall, bei dem die Datenkomprimierung ineffektiv ist. Das andere Extrem wäre, die gesamten 4 MB unseres Chips als ein einziges Archiv zu verwenden, was eine hervorragende Komprimierung bieten würde, jedoch katastrophale Folgen im Falle von Datenbeschädigung hätte.
   Ja, es ist notwendig, einen Kompromiss in Bezug auf die Zuverlässigkeit einzugehen. Aber wir müssen bedenken, dass wir ein Datenformat für nichtflüchtigen Speicher mit extrem niedrigem BER und einer angegebenen Datenhaltbarkeit von 20 Jahren entwickeln.

In den Experimenten habe ich festgestellt, dass merkliche Verluste des Kompressionsniveaus bei komprimierten Datenblöcken von weniger als 10 KB beginnen.
Es wurde bereits erwähnt, dass der verwendete Speicher seitenbasiert organisiert ist, und ich sehe keinen Grund, warum wir nicht das Verhältnis 'eine Seite - ein komprimierter Datenblock' verwenden sollten.

Das heißt, die minimal angemessene Seitengröße beträgt 16 KB (einschließlich Platz für Verwaltungsinformationen). Ein so kleines Seitenformat bringt jedoch erhebliche Einschränkungen für die maximale Datensatzgröße mit sich.

Obwohl ich momentan keine Datensätze von mehr als einem Kilobyte in komprimierter Form erwarte, habe ich beschlossen, Seiten mit einer Größe von 32 KB zu verwenden (insgesamt 128 Seiten pro Chip).

Zusammenfassung:

• Wir speichern die Daten komprimiert mit zlib (deflate);
• Für jeden Datensatz setzen wir Z_SYNC_FLUSH;
• Bei jedem komprimierten Datensatz schneiden wir die Endbytes ab (z.B. 0x00, 0x00, 0xff, 0xff); im Header geben wir an, wie viele Bytes wir entfernt haben;
• Die Daten werden in Seiten mit 32 KB gespeichert; innerhalb einer Seite gibt es einen kontinuierlichen Fluss komprimierter Daten; bei jeder Seite beginnen wir die Komprimierung erneut.

Und bevor wir mit der Komprimierung abschließen, möchte ich darauf hinweisen, dass wir nur mehrere Bytes komprimierter Daten pro Aufzeichnung erhalten, weshalb es äußerst wichtig ist, die Metadaten nicht aufzublähen; jeder Byte zählt hier.

Speicherung von Datenüberschriften

Da wir Aufzeichnungen variabler Länge haben, müssen wir irgendwie die Platzierung/Grenzen der Aufzeichnungen bestimmen.

Ich kenne drei Ansätze:

1. Alle Aufzeichnungen werden in einem kontinuierlichen Fluss gespeichert, zuerst kommt der Header der Aufzeichnung, der die Länge enthält, und dann die eigentliche Aufzeichnung.
   In dieser Variante können sowohl die Header als auch die Daten eine variable Länge haben.
   Im Wesentlichen haben wir eine einfach verkettete Liste, die häufig verwendet wird;
2. Die Header und die eigentlichen Aufzeichnungen werden in separaten Flüssen gespeichert.
   Durch die Verwendung von Headern fester Länge stellen wir sicher, dass die Beschädigung eines Headers die anderen nicht beeinflusst.
   Ein ähnlicher Ansatz wird beispielsweise in vielen Dateisystemen verwendet;
3. Die Einträge werden in einem kontinuierlichen Stream gespeichert, die Grenze eines Eintrags wird durch ein bestimmtes Marker (ein Zeichen/eine Zeichenfolge, die innerhalb von Datenblöcken nicht erlaubt ist) definiert. Wenn innerhalb eines Eintrags ein Marker auftaucht, wird dieser durch eine bestimmte Sequenz ersetzt (wir escapen ihn).
   Ein ähnlicher Ansatz wird beispielsweise im PPP-Protokoll verwendet.

Ich werde dies veranschaulichen.

Variante 1:

Hier ist alles ganz einfach: Wenn wir die Länge des Eintrags kennen, können wir die Adresse des nächsten Headers berechnen. So bewegen wir uns durch die Header, bis wir einen Bereich erreichen, der mit 0xff gefüllt ist (freien Bereich) oder das Ende der Seite.

Variante 2:

Aufgrund der variablen Eintragslänge können wir nicht im Voraus sagen, wie viele Einträge (und damit auch Header) wir auf die Seite benötigen. Wir könnten Header und Daten auf verschiedene Seiten verteilen, aber mir gefällt ein anderer Ansatz besser: Sowohl Header als auch Daten platzieren wir auf derselben Seite, wobei die Header (fester Größe) am Anfang der Seite stehen und die Daten (variabler Länge) vom Ende kommen. Sobald sie "aufeinandertreffen" (der freie Platz reicht nicht für einen neuen Eintrag) – betrachten wir diese Seite als voll.

Variante 3:

Es ist nicht notwendig, die Länge oder andere Informationen über den Datenstandort im Header zu speichern; Marker, die die Grenzen der Einträge anzeigen, sind ausreichend. Die Daten müssen jedoch beim Schreiben/Lesen verarbeitet werden.
Als Marker würde ich 0xff verwenden (das nach dem Löschen die Seite füllt), somit wird der freie Bereich nicht fälschlicherweise als Daten interpretiert.

Vergleichstabelle:

Option 1
Option 2
Option 3

Fehlerresistenz
—
+
+

Kompaktheit
+
—
+

Implementierungsaufwand
*
**
**

Option 1 hat einen gravierenden Nachteil: Bei einer Beschädigung eines der Header ist die gesamte nachfolgende Kette zerstört. Die anderen Optionen ermöglichen die Wiederherstellung eines Teils der Daten, selbst bei massiven Beschädigungen.
Es ist jedoch sinnvoll, sich daran zu erinnern, dass wir beschlossen haben, die Daten komprimiert zu speichern. Damit verlieren wir ohnehin alle Daten auf der Seite nach einem 'defekten' Eintrag. Auch wenn in der Tabelle ein Minus steht, berücksichtigen wir dies nicht.

Kompaktheit:

• Im ersten Ansatz müssen wir nur die Länge im Header speichern; wenn wir Variablen mit variabler Länge verwenden, können wir in den meisten Fällen mit nur einem Byte auskommen.
• Im zweiten Ansatz müssen wir die Anfangsadresse und die Länge speichern; der Datensatz sollte eine konstante Größe haben, ich schätze 4 Byte pro Datensatz (zwei Byte für den Offset und zwei Byte für die Länge);
• Für die dritte Variante genügt ein einziges Zeichen, um den Beginn des Datensatzes zu kennzeichnen, zusätzlich wird sich der Datensatz aufgrund der Escape-Codierung um 1-2% erhöhen. Insgesamt ein ziemlich ähnliches Verhältnis wie im ersten Ansatz.

Ursprünglich betrachtete ich die zweite Variante als Hauptoption (und habe sogar eine Implementierung geschrieben). Ich habe sie nur verworfen, als ich mich endgültig für die Nutzung von Kompression entschied.

Möglicherweise werde ich irgendwann eine ähnliche Variante verwenden. Zum Beispiel, wenn ich Daten für ein Schiff speichern muss, das zwischen der Erde und dem Mars pendelt – da gibt es ganz andere Anforderungen an die Zuverlässigkeit, Strahlung im Weltraum, …

Was die dritte Variante betrifft: Ich habe ihr zwei Sterne für die Komplexität der Implementierung gegeben, einfach weil ich nicht gerne mit Escape-Codierungen, der Änderung der Länge während des Prozesses usw. herumspiele. Ja, das ist vielleicht voreingenommen, aber ich bin es, der den Code schreiben muss – warum sollte ich mich zwingen, etwas zu tun, was mir nicht gefällt.

Zusammenfassung: Wir wählen die Speicherung in Form von Ketten 'Überschrift mit fester Länge - Daten variabler Länge' aufgrund der Effizienz und der einfachen Umsetzung.

Verwendung von Bitfeldern zur Kontrolle des Erfolgs von Schreiboperationen.

Ich erinnere mich nicht mehr, wo ich die Idee aufgeschnappt habe, aber es sieht etwa so aus:
Für jeden Eintrag reservieren wir einige Bits zur Speicherung von Flags.
Wie bereits erwähnt, sind nach dem Löschen alle Bits mit 1 gefüllt, und wir können 1 in 0 ändern, aber nicht umgekehrt. Für 'Flag nicht gesetzt' verwenden wir 1, für 'Flag gesetzt' - 0.

So könnte die Speicherung eines variablen Längeneintrags im Flash aussehen:

1. Wir setzen das Flag 'Schreiben von Länge begonnen';
2. Wir schreiben die Länge;
3. Wir setzen das Flag 'Schreiben von Daten begonnen';
4. Wir schreiben die Daten;
5. Wir setzen das Flag 'Schreiben abgeschlossen'.

Zusätzlich haben wir ein Flag 'Fehler aufgetreten', insgesamt also 4 Bit-Flags.

In diesem Fall haben wir zwei stabile Zustände '1111' - Schreiben nicht begonnen und '1000' - Schreiben war erfolgreich; bei einer unerwarteten Unterbrechung des Schreibprozesses erhalten wir Zwischenzustände, die wir später erkennen und bearbeiten können.

Der Ansatz ist interessant, schützt jedoch nur vor plötzlichem Stromausfall und ähnlichen Störungen, was natürlich wichtig ist, aber bei weitem nicht der einzige (und sogar nicht der Haupt-) Grund für mögliche Ausfälle.

Zusammenfassung: Lassen Sie uns weiter auf der Suche nach einer guten Lösung gehen.

Prüfziffern

Prüfziffern ermöglichen es zudem, mit ausreichender Wahrscheinlichkeit zu bestätigen, dass wir genau das lesen, was hätte aufgezeichnet werden sollen. Im Gegensatz zu den oben betrachteten Bitfeldern funktionieren sie immer.

Wenn wir die Liste potenzieller Problemquellen betrachten, die wir zuvor erwähnt haben, kann die Prüfziffer einen Fehler unabhängig von seiner Herkunft erkennen. (außer vielleicht schädlichen Außerirdischen – die können auch die Prüfziffer fälschen).

Wenn unser Ziel darin besteht, zu überprüfen, dass die Daten intakt sind, sind Prüfziffern eine ausgezeichnete Idee.

Die Auswahl des Algorithmus zur Berechnung der Prüfziffer war unkritisch – CRC. Einerseits ermöglichen die mathematischen Eigenschaften eine 100%ige Erkennung bestimmter Fehlerarten, andererseits zeigt dieser Algorithmus bei zufälligen Daten normalerweise eine Kollisionswahrscheinlichkeit, die kaum über dem theoretischen Limit liegt. Obwohl dies nicht der schnellste Algorithmus ist und nicht immer die minimalste Anzahl an Kollisionsfällen aufweist, hat er eine sehr wichtige Eigenschaft: In den Tests, die ich gesehen habe, sind mir keine Muster begegnet, bei denen er eindeutig versagt hat. Stabilität ist in diesem Fall das Hauptmerkmal.

Beispiel einer umfangreichen Untersuchung: Teil 1, Teil 2 (Links zu narod.ru, Entschuldigung).

Die Auswahl der Prüfziffer ist jedoch nicht abgeschlossen, CRC ist eine gesamte Familie von Prüfziffern. Es muss eine Länge festgelegt werden, bevor ein Polynom ausgewählt werden kann.

Die Wahl der Prüfziffernlänge ist nicht so einfach, wie es auf den ersten Blick scheint.

Ich illustriere das:
Nehmen wir an, die Fehlerwahrscheinlichkeit liegt bei jedem Byte und eine ideale Prüfziffer, berechnen wir die durchschnittliche Anzahl der Fehler pro Millionen Einträge:

Daten, Byte
Prüfziffer, Byte
Nicht erkannte Fehler
Falsche Fehlererkennung
Insgesamt falsche Auslösungen

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

Es scheint ganz einfach zu sein – wähle je nach Länge der zu schützenden Daten die Länge der Prüfziffer mit minimalen Fehlalarmen – und alles ist erledigt.

Allerdings gibt es bei kurzen Prüfziffern ein Problem: Sie erkennen zwar einzelne Bitfehler gut, könnten jedoch mit einer relativ hohen Wahrscheinlichkeit zufällige Daten als korrekt werten. Auf Habr gab es bereits einen Artikel, der dieses Thema behandelt hat. das Problem in der realen Welt.

Um zufällige Übereinstimmungen der Prüfziffer nahezu unmöglich zu machen, sollten Prüfziffern mit einer Länge von 32 Bit oder mehr verwendet werden. (Für Längen über 64 Bit werden normalerweise kryptographische Hash-Funktionen verwendet.).

Obwohl ich zuvor erwähnt habe, dass wir Platz sparen sollten, werden wir dennoch eine 32-Bit-Prüfziffer verwenden (16 Bit sind zu wenig, die Wahrscheinlichkeit einer Kollision liegt über 0,01%; und 24 Bit sind, wie man so sagt, weder Fisch noch Fleisch).

Hier könnte man einwenden: Haben wir jeden Byte beim Komprimieren gespart, nur um jetzt sofort 4 Bytes zu verlieren? Wäre es nicht besser gewesen, gar nicht zu komprimieren und keine Prüfziffer hinzuzufügen? Natürlich nicht, das Fehlen von Kompression bedeutet, dass die Integritätsprüfung für uns nicht notwendig ist.

Wir wollen kein Rad neu erfinden, wenn es um die Auswahl des Polynoms geht, also nehmen wir das derzeit beliebte CRC-32C.
Dieser Code erkennt 6 Bitfehler in Paketen bis zu 22 Bytes (wohl der häufigste Fall für uns), 4 Bitfehler in Paketen bis zu 655 Bytes (auch ein häufiges Szenario für uns) und 2 oder jede ungerade Anzahl von Bitfehlern in Paketen beliebiger sinnvoller Länge.

Falls jemand an den Details interessiert ist,

schaut euch den Wikipedia-Artikel über CRC an.

Die Parametrierung des crc-32c-Codes findet man auf Kupman’s Webseite, dem wohl führenden Spezialisten für CRC auf diesem Planeten.

In In seinem Artikel gibt es noch einen interessanten Code,der etwas bessere Parameter für die für uns relevanten Paketlängen bietet, aber ich halte den Unterschied nicht für entscheidend und erachte mich als kompetent genug, um einen benutzerdefinierten Code anstelle eines standardisierten und gut erforschten zu wählen.

Außerdem, da unsere Daten komprimiert sind, stellt sich die Frage: Soll die Prüfziffer auf komprimierten oder unkomprimierten Daten berechnet werden?

Argumente für die Berechnung von Prüfziffern für unkomprimierte Daten:

• Letztendlich müssen wir die Datenintegrität prüfen – genau das tun wir hier direkt (wobei gleichzeitig mögliche Fehler bei der Kompression/Dekompression und durch defekten Speicher überprüft werden);
• Der Deflate-Algorithmus in zlib hat eine recht ausgereifte Implementierung und sollte bei „fehlerhaften“ Eingabedaten nicht abstürzen; darüber hinaus ist er oft in der Lage, Fehler im Eingabestrom selbst zu erkennen, was die Wahrscheinlichkeit der unentdeckten Fehler verringert (ich habe einen Test mit der Umkehrung eines einzelnen Bits in einem kurzen Datensatz durchgeführt, zlib hat den Fehler in etwa einem Drittel der Fälle erkannt).

Argumente gegen die Berechnung von Prüfziffern für unkomprimierte Daten:

• CRC ist speziell für die wenigen Bitfehler ausgelegt, die typisch für Flash-Speicher sind (ein Bitfehler im komprimierten Strom kann massive Änderungen im Ausgangsstrom verursachen, wodurch wir theoretisch eine Kollision „erfassen“ können);
• Ich finde die Idee, dem Dekompressor potenziell fehlerhafte Daten zu übergeben, nicht besonders gut, wer weiß schon, wie er reagieren wird.

In diesem Projekt habe ich mich entschieden, von der gängigen Praxis abzuweichen, die Prüfziffer unkomprimierter Daten zu speichern.

Zusammenfassung: Wir verwenden CRC-32C, wobei die Prüfziffer von den Daten in der Form berechnet wird, in der sie im Flash gespeichert werden (nach der Kompression).

Redundanz

Der Einsatz von Redundanzkodierung kann zwar nicht verhindern, dass Daten verloren gehen, jedoch kann er die Wahrscheinlichkeit eines irreversiblen Datenverlusts erheblich (oft um viele Größenordnungen) verringern.

Wir können verschiedene Arten von Redundanz verwenden, um Fehler zu korrigieren.
Hamming-Codes können Einzelbitfehler korrigieren, Reed-Solomon-Codes sind zeichenbasiert, mehrere Datenkopien zusammen mit Prüfziffern oder Codes wie RAID-6 können helfen, Daten selbst im Falle massiver Beschädigungen wiederherzustellen.
Anfangs war ich auf eine breite Anwendung von fehlerresistenten Codierungen eingestellt, aber dann wurde mir klar, dass man zuerst verstehen muss, vor welchen Fehlern man sich schützen möchte, bevor man eine Codierung wählt.

Wir haben bereits vorher darüber gesprochen, dass Fehler so schnell wie möglich erkannt werden sollten. In welchen Situationen könnten wir auf Fehler stoßen?

1. Unvollständiger Eintrag (aus irgendwelchen Gründen wurde beim Schreiben die Stromversorgung unterbrochen, Raspberry ist abgestürzt, …)
   Leider bleibt bei einem solchen Fehler nur, ungültige Einträge zu ignorieren und die Daten als verloren zu betrachten;
2. Schreibfehler (aus irgendwelchen Gründen wurde nicht das geschrieben, was beabsichtigt war)
   Solche Fehler können wir sofort erkennen, wenn wir direkt nach dem Schreiben eine Kontrolllesung durchführen;
3. Datenverzerrung im Speicher während der Speicherung;
4. Lese-Fehler
   Um diesen zu beheben, reicht es aus, im Falle einer fehlerhaften Prüfziffer das Lesen mehrmals zu wiederholen.

Das heißt, nur Fehler des dritten Typs (selbstständige Datenbeschädigung während der Speicherung) können ohne fehlerresistente Codierung nicht behoben werden. Es ist jedoch anzunehmen, dass solche Fehler äußerst unwahrscheinlich sind.

Zusammenfassung: Es wurde beschlossen, auf überflüssige Codierung zu verzichten. Sollte sich in der Praxis herausstellen, dass diese Entscheidung fehlerhaft ist, wird die Frage erneut betrachtet (mit bereits gesammelten Statistiken über Ausfälle, die die Auswahl der optimalen Codierungsart ermöglichen).

Sonstiges

Natürlich erlaubt das Format des Artikels nicht, jeden einzelnen Bit im Format zu begründen. (und meine Kräfte sind auch bereits erschöpft), deshalb gehe ich kurz auf einige Punkte ein, die bisher nicht angesprochen wurden.

• Es wurde beschlossen, alle Seiten "gleichberechtigt" zu gestalten.
  Das bedeutet, es wird keine speziellen Seiten mit Metadaten, separaten Streams usw. geben, stattdessen einen einheitlichen Stream, der alle Seiten nacheinander überschreibt.
  Dies gewährleistet einen gleichmäßigen Verschleiß der Seiten, das Fehlen eines einzelnen Ausfallpunkts und es gefällt einfach;
• Es muss unbedingt eine Versionskontrolle des Formats eingeplant werden.
  Ein Format ohne Versionsnummer im Header ist schlecht!
  Es reicht, im Header der Seite ein Feld mit einer Art Magic Number (Signatur) hinzuzufügen, die auf die verwendete Formatversion hinweist. (ich glaube nicht, dass es in der Praxis sogar zehn davon geben wird);
• Für die Datensätze (von denen es sehr viele gibt) einen variabel langen Header verwenden, wobei man in den meisten Fällen eine Länge von 1 Byte anstrebt;
• Zum Kodieren der Headerlänge und der Länge des gekürzten Teils der kompakten Aufzeichnung sollten binäre variabel lange Codes verwendet werden.

Sehr hilfreich war der Online-Generator von Huffman-Codes. In nur wenigen Minuten gelang es, die benötigten variabel langen Codes zu finden.

Beschreibung des Datenformat-Speichers

Byte-Reihenfolge

Felder, die größer als ein Byte sind, werden im Big-Endian-Format (Netzwerk-Byte-Reihenfolge) gespeichert, das heißt 0x1234 wird als 0x12, 0x34 aufgezeichnet.

Seitenaufteilung

Der gesamte Flash-Speicher ist in Seiten gleicher Größe unterteilt.

Die Standardgröße der Seite beträgt 32 KB, jedoch nicht mehr als 1/4 der Gesamtgröße des Speicherchips (bei einem 4 MB-Chip ergibt dies 128 Seiten).

Jede Seite speichert Daten unabhängig von anderen Seiten (die Daten einer Seite verweisen nicht auf die Daten einer anderen Seite).

Alle Seiten sind in natürlicher Reihenfolge nummeriert (in aufsteigender Adressreihenfolge), beginnend mit der Nummer 0 (die Nullseite beginnt bei Adresse 0, die erste bei 32 KB, die zweite bei 64 KB usw.).

Der Speicherchip wird als zirkulärer Puffer (Ringpuffer) verwendet, das heißt, die Aufzeichnung beginnt zunächst in der Seite mit der Nummer 0, dann mit der Nummer 1, … wenn die letzte Seite gefüllt ist, beginnt ein neuer Zyklus und die Aufzeichnung wird mit der Nullseite fortgesetzt.

Innerhalb der Seite

Am Anfang der Seite befindet sich ein 4-Byte-Header, gefolgt von einer Prüfziffer des Headers (CRC-32C), dann werden die Einträge im Format „Header, Daten, Prüfziffer“ gespeichert.

Der Seitenheader (in schmutzig-grün auf dem Schema) besteht aus:

• einem zweibytepard Magic Number (auch bekannt als Versionsbezeichner des Formats)
  für die aktuelle Formatversion wird dies berechnet als 0xed00 ⊕ Seitenzahl;
• einem zweibytepard Zähler "Seitenversion" (Zahl des Speicherüberschreibungszyklus).

Die Einträge auf der Seite werden komprimiert gespeichert (es wird der deflate-Algorithmus verwendet). Alle Einträge auf einer Seite werden in einem Durchgang komprimiert (es wird ein gemeinsames Wörterbuch eingesetzt), und für jede neue Seite beginnt die Kompression erneut. Das bedeutet, dass zur Dekompression eines beliebigen Eintrags alle vorherigen Einträge von dieser Seite (und nur von dieser) erforderlich sind.

Jeder Eintrag wird mit dem Z_SYNC_FLUSH-Flag komprimiert, wobei am Ende des komprimierten Streams 4 Bytes 0x00, 0x00, 0xff, 0xff auftauchen, möglicherweise vorangestellt von einem oder zwei Nullbytes.
Diese Sequenz (mit einer Länge von 4, 5 oder 6 Bytes) wird bei der Speicherung im Flash-Speicher verworfen.

Der Eintragsheader besteht aus 1, 2 oder 3 Bytes, die Folgendes speichern:

• ein Bit (T), das den Typ des Eintrags anzeigt: 0 — Kontext, 1 — Journal;
• ein variabel langes Feld (S) von 1 bis 7 Bit, das die Länge des Headers und den "Schwanz" bestimmt, der zur Dekompression an den Eintrag angefügt werden muss;
• die Länge des Eintrags (L).

Tabelle der Werte S:

O
Länge des Headers in Byte
Wird beim Schreiben verworfen, Byte

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)

Ich habe versucht, dies zu veranschaulichen, bin mir jedoch nicht sicher, wie klar es geworden ist:

Gelb kennzeichnet hier das Feld T, Weiß das Feld S, Grün L (Länge der komprimierten Daten in Byte), Blau die komprimierten Daten und Rot die letzten Bytes der komprimierten Daten, die nicht in den Flash-Speicher geschrieben werden.

Somit können wir die Header von der häufigsten Länge (bis zu 63+5 Byte in komprimierter Form) mit einem Byte schreiben.

Nach jedem Eintrag wird eine CRC-32C-Prüfziffer gespeichert, bei der als Anfangswert (init) der umgekehrte Wert der vorherigen Prüfziffer verwendet wird.

CRC hat die Eigenschaft der "Fortführbarkeit"; es gilt (plus-minus Invertierung der Bits im Prozess) folgende Formel: .
Das heißt, wir berechnen tatsächlich die CRC aller vorherigen Bytes der Header und Daten auf dieser Seite.

Direkt hinter der Prüfziffer liegt der Header des nächsten Eintrags.

Der Header ist so konstruiert, dass sein erster Byte immer von 0x00 und 0xff verschieden ist (trifft man beim ersten Byte des Headers auf 0xff, handelt es sich um einen ungenutzten Bereich; 0x00 signalisiert einen Fehler).

Beispielhafte Algorithmen

Lesen aus dem Flash-Speicher

Jedes Lesen erfolgt mit einer Überprüfung der Prüfziffer.
Stimmt die Prüfziffer nicht überein, wird das Lesen mehrmals wiederholt, in der Hoffnung, die korrekten Daten zu erhalten.

(Das macht Sinn, Linux cached das Lesen aus NOR Flash nicht, bestätigt)

Schreiben in den Flash-Speicher

Wir schreiben die Daten.
Wir lesen sie.

Stimmen die gelesenen Daten nicht mit den geschriebenen überein, füllen wir den Bereich mit Nullen auf und signalisieren einen Fehler.

Vorbereitung des neuen Chips für den Betrieb

Zur Initialisierung wird im ersten (genauer gesagt nullten) Seiten eine Header mit Version 1 geschrieben.
Anschließend wird in diese Seite der Anfangskontext geschrieben (enthält die UUID des Geräts und die Standardkonfigurationen).

Alles, der Flash-Speicher ist bereit für den Betrieb.

Starten des Geräts

Beim Start werden die ersten 8 Bytes jeder Seite (Header + CRC) gelesen; Seiten mit unbekannter Magic Number oder fehlerhaftem CRC werden ignoriert.
Von den „richtigen“ Seiten werden die Seiten mit der höchsten Version ausgewählt; dabei wird die Seite mit der höchsten Nummer genommen.
Der erste Eintrag wird gelesen, die CRC-Korrektheit und das Vorhandensein des „Kontext“-Flags werden überprüft. Wenn alles in Ordnung ist, gilt diese Seite als aktuell. Andernfalls wird zur vorherigen Seite zurückgekehrt, bis eine „lebendige“ Seite gefunden wird.
Von der gefundenen Seite lesen wir alle Einträge und wenden die mit dem „Kontext“-Flag an.
Das zlib-Wörterbuch wird gespeichert (es wird zum Nachtragen auf dieser Seite benötigt).

Ladevorgang abgeschlossen, Kontext wiederhergestellt, die Arbeit kann beginnen.

Eintrag zum Protokoll hinzufügen

Wir komprimieren den Eintrag mit dem richtigen Wörterbuch und geben Z_SYNC_FLUSH an. Überprüfen, ob der komprimierte Eintrag auf die aktuelle Seite passt.
Wenn er nicht passt (oder wenn auf der Seite CRC-Fehler waren) – beginnen wir eine neue Seite (siehe unten).
Wir schreiben den Eintrag und die CRC. Wenn ein Fehler aufgetreten ist – beginnen wir eine neue Seite.

Neue Seite

Wir wählen die Seite mit der niedrigsten Nummer, die frei ist (frei ist eine Seite mit einer falschen Prüfziffer im Header oder mit einer Version, die kleiner ist als die aktuelle). Sollte es keine solchen Seiten geben, wählen wir die Seite mit der niedrigsten Nummer aus den Seiten, die die gleiche Version wie die aktuelle haben.
Wir markieren die ausgewählte Seite als gelöscht. Wir vergleichen den Inhalt mit 0xff. Wenn etwas nicht stimmt, wählen wir die nächste freie Seite usw.
Wir schreiben den Header auf die gelöschte Seite, die erste Eintragung ist der aktuelle Zustand des Kontextes, die nächste - ein ungeschriebener Journaleintrag (sofern vorhanden).

Anwendbarkeit des Formats

Meiner Meinung nach ist es ein brauchbares Format für die Speicherung beliebiger mehr oder weniger komprimierbarer Informationsströme (einfacher Text, JSON, MessagePack, CBOR, möglicherweise protobuf) im NOR Flash.

Natürlich ist das Format speziell für SLC NOR Flash optimiert.

Es sollte nicht mit Speichermedien mit hohem BER verwendet werden, wie z.B. NAND oder MLC NOR. (Gibt es solche Speicher eigentlich im Verkauf? Ich habe nur Erwähnungen in Arbeiten über Fehlerkorrektur gesehen.).

Zumal es nicht mit Geräten verwendet werden sollte, die ihre eigene FTL haben: USB-Flash, SD, MicroSD usw. (Für diesen Speicher habe ich ein Format mit einer Seitengröße von 512 Byte, einer Signatur zu Beginn jeder Seite und eindeutigen Eintragsnummern erstellt – manchmal gelang es, alle Daten durch einfaches sequentielles Lesen von einem »defekten« Flash-Laufwerk wiederherzustellen.).

Je nach Anforderungen kann das Format unverändert auf Flash-Laufwerken von 128 Kbit (16 Kb) bis 1 Gbit (128 Mb) verwendet werden. Bei Bedarf lässt es sich auch auf größeren Chips nutzen, allerdings müsste wahrscheinlich die Seitengröße angepasst werden. (Hier stellt sich jedoch die Frage der wirtschaftlichen Rentabilität, die Preise für große NOR-Flash-Bausteine sind nicht erfreulich.).

Wenn jemand das Format interessant findet und es in einem Open-Source-Projekt verwenden möchte – schreibt mir, ich werde versuchen, Zeit zu finden, den Code zu optimieren und auf GitHub hochzuladen.

Fazit

Wie man sieht, ist das Format am Ende einfach herausgekommen und sogar langweilig.

In dem Artikel ist es schwierig, die Evolution meiner Meinung widerzuspiegeln, aber glauben Sie mir: Zunächst wollte ich etwas Maßgeschneidertes, Unverwüstliches schaffen, das selbst nach einer nuklearen Explosion in unmittelbarer Nähe überleben kann. Doch der Verstand (hoffentlich) hat schließlich gesiegt und die Prioritäten haben sich allmählich auf Einfachheit und Kompaktheit verschoben.

Kann es sein, dass ich mich geirrt habe? Ja, natürlich. Es könnte durchaus passieren, dass wir beispielsweise eine Charge minderwertiger Chips gekauft haben. Oder aus einem anderen Grund die Ausrüstung die Erwartungen hinsichtlich der Zuverlässigkeit nicht erfüllt.

Habe ich einen Plan für diesen Fall? Ich denke, nach dem Lesen des Artikels werden Sie keinen Zweifel daran haben, dass es einen Plan gibt. Und sogar mehr als einen.

Wenn wir es etwas ernsthafter betrachten, wurde das Format sowohl als Arbeitsvariante als auch als "Versuch" entwickelt.

Im Moment läuft alles normal, in den nächsten Tagen wird die Lösung implementiert. (ungefähr) auf rund hundert Geräten, und wir werden sehen, wie es in der "Produktiveinsatz" läuft (zum Glück, hoffe ich, erlaubt das Format eine zuverlässige Fehlererkennung; so lässt sich vollständige Statistik sammeln). In ein paar Monaten können wir Schlussfolgerungen ziehen. (wenn wir Pech haben, auch früher).

Sollten sich nach der Nutzung ernsthafte Probleme zeigen und Anpassungen erforderlich sein, werde ich unbedingt darüber berichten.

Literatur

Ich wollte keine lange, langweilige Liste verwendeter Arbeiten erstellen. Schließlich hat jeder Google.

Hier habe ich beschlossen, eine Liste von Entdeckungen zu führen, die mir besonders interessant erschienen. Im Laufe der Zeit sind sie jedoch direkt in den Text des Artikels eingeflossen, und es blieb nur ein Punkt in der Liste:

1. Dienstprogramm infgen vom Autor zlib. Es kann den Inhalt von deflate/zlib/gzip-Archiven in verständlicher Form anzeigen. Wenn Sie sich mit der internen Struktur des deflate- (oder gzip-) Formats beschäftigen müssen, empfehle ich es dringend.

Quelle: habr.com