Tło

Mamy automaty sprzedażowe, które sami opracowaliśmy. Wewnątrz znajduje się Raspberry Pi oraz nieco dodatkowego okablowania na osobnej płycie. Podłączone są do nich monety, banknoty, terminal płatniczy… Całością zarządza autorski program. Cała historia działania zapisywana jest w dzienniku na pamięci flash (MicroSD), który następnie przesyłany jest przez internet (za pomocą modemu USB) na serwer, gdzie przechowywana jest w bazie danych. Informacje o sprzedaży są załadowane do 1C, mamy również prosty interfejs webowy do monitorowania itp.

Zatem dziennik jest niezwykle ważny — do ewidencji (są tam przychody, sprzedaż itd.), monitorowania (wszelkie awarie i inne sytuacje nadzwyczajne); można powiedzieć, że to cała informacja, jaką posiadamy o tym automacie.

Problem

Pamięci USB okazują się bardzo zawodnymi urządzeniami. Regularnie się psują. Prowadzi to zarówno do przestojów automatów, jak i (jeśli z jakiegoś powodu dziennik nie mógł być przesłany online) do utraty danych.

To już nie pierwsze doświadczenie z pamięciami USB, przedtem był inny projekt z ponad setką urządzeń, gdzie dziennik był przechowywany na pamięciach USB, również tam były problemy z niezawodnością, czasami liczba uszkodzonych w ciągu miesiąca wynosiła dziesiątki. Próbowaliśmy różnych pamięci, w tym markowych na pamięci SLC, tak, niektóre modele są bardziej niezawodne od innych, ale wymiana pamięci nie rozwiązała problemu w sposób drastyczny.

Uwaga! Longread! Jeśli nie interesuje cię „dlaczego”, a tylko „jak”, możesz od razu przejść na koniec artykułem.

Rozwiązanie

Pierwsza myśl, która przychodzi do głowy: zrezygnować z MicroSD, zainstalować np. SSD i ładować z niego. Teoretycznie to możliwe, ale względnie drogie i wcale nie tak niezawodne (dodaje się adapter USB-SATA; w budżetowych SSD statystyki awarii też nie napawają optymizmem).

USB HDD również nie wygląda na szczególnie atrakcyjne rozwiązanie.

Dlatego doszliśmy do takiego rozwiązania: pozostawić uruchamianie z MicroSD, ale używać ich w trybie tylko do odczytu, a dziennik działania (i inne unikalne dane dla konkretnego urządzenia — numer seryjny, kalibracje czujników, itd.) przechowywać gdzie indziej.

Temat systemu plików tylko do odczytu dla Raspberry Pi został już dokładnie zbadany, nie będę się zatrzymywał na szczegółach realizacji w tym artykule (ale jeśli będzie zainteresowanie — być może napiszę na ten temat mini-artykul). Jedna rzecz, którą warto zaznaczyć: zarówno z doświadczenia osobistego, jak i z opinii osób, które już wdrożyły, można zauważyć poprawę w niezawodności. Tak, całkowite wyeliminowanie awarii jest niemożliwe, ale znaczne zmniejszenie ich częstotliwości jest całkiem realne. Karty stają się również ujednolicone, co znacznie ułatwia ich wymianę dla personelu obsługującego.

Część sprzętowa

Nie było większych wątpliwości co do wyboru typu pamięci — NOR Flash.
Argumenty:

• proste podłączenie (najczęściej szyna SPI, z doświadczeniem w jej użyciu, więc ''problemów sprzętowych'' nie przewiduje się);
• niska cena;
• standardowy protokół pracy (realizacja już istnieje w jądrze Linuxa, w razie potrzeby można skorzystać z zewnętrznych, które też są dostępne, lub nawet napisać własne, co jest dość proste);
• niezawodność i trwałość:
  z typowego arkusza danych: dane są przechowywane przez 20 lat, 100000 cykli kasowania dla każdego bloku;
  z zewnętrznych źródeł: bardzo niski BER, postulowane jest brak konieczności stosowania kodów korekcji błędów. (w niektórych pracach omawia się ECC dla NOR, ale zazwyczaj ma się na myśli MLC NOR, co się zdarza).

Oszacujmy wymagania dotyczące objętości i trwałości.

Chcemy, aby dane były gwarantowane do przechowywania przez kilka dni. Potrzebne jest to, aby w przypadku jakichkolwiek problemów z komunikacją historia sprzedaży nie została utracona. Będziemy bazować na 5 dniach, w tym czasie (nawet przy uwzględnieniu weekendów i świąt) można rozwiązać problem.

Obecnie zbieramy około 100 KB dziennie w dzienniku (3-4 tysiące wpisów), ale ta liczba stopniowo rośnie — zwiększa się szczegółowość, dodawane są nowe wydarzenia. Poza tym czasami zdarzają się wzrosty (jakiś czujnik zaczyna generować fałszywe alarmy, na przykład). Planujemy na 10 tysięcy wpisów po 100 bajtów — megabajt na dzień.

W sumie wychodzi 5 MB ''czystych'' (dobrze kompresowalnych) danych. Do nich jeszcze (przybliżone oszacowanie) 1 MB danych systemowych.

To znaczy, że potrzebujemy układu o pojemności 8 MB, jeśli nie używamy kompresji, lub 4 MB, jeśli używamy. To całkiem realne liczby dla tego typu pamięci.

Jeśli chodzi o trwałość: jeśli zakładamy, że pamięć będzie zapisywana w całości nie częściej niż raz na 5 dni, to przez 10 lat użytkowania otrzymujemy mniej niż tysiąc cykli zapisu.
Przypominam, że producent obiecuje sto tysięcy.

Trochę o NOR vs NAND

Dzisiaj zdecydowanie bardziej popularna jest pamięć NAND, ale dla tego projektu nie wykorzystałbym jej: NAND, w przeciwieństwie do NOR, wymaga stosowania kodów korekcji błędów, tabeli uszkodzonych bloków itd., a nóżek w układach NAND zazwyczaj jest znacznie więcej.

Jako wady NOR można wskazać:

• małą pojemność (a co za tym idzie, wysoką cenę za megabajt);
• niską prędkość wymiany (w dużej mierze z powodu używania interfejsu szeregowego, zazwyczaj SPI lub I2C);
• wolne kasowanie (w zależności od rozmiaru bloku, trwa od ułamków sekundy do kilku sekund).

Wydaje się, że nie ma nic krytycznego dla nas, więc kontynuujemy.

Jeśli interesują szczegóły, wybrano układ at25df321a (zresztą, to nieistotne, na rynku jest mnóstwo analogów, zgodnych pod względem pinów i systemu komend; nawet jeśli zechcemy użyć układu innego producenta i/lub innej pojemności, wszystko zadziała bez zmiany kodu).

Używam wbudowanego w jądro Linux sterownika, na Raspberry dzięki wsparciu device tree overlay wszystko jest bardzo proste — wystarczy umieścić skompilowany overlay w /boot/overlays i nieco zmodyfikować /boot/config.txt.

Przykład pliku dts

Szczerze mówiąc, nie jestem pewien, czy jest napisany bez błędów, ale działa.

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

I jeszcze jedna linia w config.txt

dtoverlay=at25:spimaxfrequency=50000000

Opis samego połączenia układu z Raspberry Pi pomijam. Z jednej strony nie jestem specjalistą w elektronice, z drugiej — tu wszystko jest banalne nawet dla mnie: układ ma tylko 8 nóg, z których potrzebujemy ziemi, zasilania, SPI (CS, SI, SO, SCK); poziomy odpowiadają poziomom Raspberry Pi, żadnych dodatkowych elementów nie trzeba — wystarczy połączyć wskazane 6 styków.

Sformułowanie zadania

Jak zawsze, postawienie zadania odbywa się w kilku iteracjach, wydaje mi się, że nadszedł czas na kolejną. więc zatrzymajmy się, zbierzmy to, co zostało już napisane, i wyjaśnijmy pozostałe niejasne szczegóły.

Zatem ustaliliśmy, że dziennik będzie przechowywany w SPI NOR Flash.

Czym jest NOR Flash dla tych, którzy nie wiedzą

To pamięć nieulotna, z którą można wykonać trzy operacje:

1. Odczyt:
   Najzwyklejsze odczytanie: podajemy adres i odczytujemy tyle bajtów, ile potrzebujemy;
2. Zapis:
   Zapis do pamięci NOR flash wygląda jak zwykły, ale ma jedną szczególną cechę: można tylko zmieniać 1 na 0, ale nie odwrotnie. Na przykład, jeśli w komórce pamięci mieliśmy 0x55, to po zapisaniu 0x0f, będzie tam przechowywana 0x05. (patrz tabela nieco niżej);
3. Wymazywanie:
   Oczywiście, musimy umieć wykonywać również operację odwrotną — zmieniać 0 na 1, dokładnie w tym celu istnieje operacja wymazywania. W przeciwieństwie do pierwszych dwóch, operuje ona nie na bajtach, a na blokach (minimalny blok wymazywania w wybranej pamięci to 4kB). Operacja wymazywania niszczy cały blok i to jest jedyny sposób, aby zmienić 0 na 1. Dlatego podczas pracy z pamięcią flash często konieczne jest wyrównanie struktur danych do granicy bloku wymazywania.
   Zapis do pamięci NOR Flash:

Dane binarne

Było
01010101

Zapisano
00001111

Stało się
00000101

Sam dziennik stanowi sekwencję rekordów o zmiennej długości. Typowa długość rekordu wynosi około 30 bajtów (choć czasami zdarzają się też rekordy o długości kilku kilobajtów). W tym przypadku pracujemy z nimi po prostu jako z zestawem bajtów, ale, jeśli to interesuje, wewnątrz rekordów stosuje się CBOR.

Oprócz dziennika, musimy przechowywać pewne 'ustawienia' zarówno aktualizowane, jak i nie: pewien identyfikator urządzenia, kalibracje czujników, flaga 'urządzenie tymczasowo wyłączone' itd.
Te informacje stanowią zestaw rekordów klucz-wartość, również przechowywanych w CBOR. Mamy ich niewiele (maksymalnie kilka kilobajtów), aktualizują się one rzadko.
W dalszej części będziemy nazywać je kontekstem.

Jeśli przypomnimy sobie, od czego zaczęła się ten artykuł, bardzo ważne jest zapewnienie niezawodności przechowywania danych i, gdy to możliwe, nieprzerwanej pracy, nawet w przypadku awarii sprzętowych/uszkodzenia danych.

Jakie źródła problemów można rozważyć?

• Odłączenie zasilania w momencie operacji zapisu/wymazywania. To coś w rodzaju 'na złamanie nie ma sposobu'.
  Informacje z dyskusji na stackexchange: podczas odłączenia zasilania w trakcie pracy z pamięcią flash zarówno wymazywanie (ustawienie na 1), jak i zapis (ustawienie na 0) prowadzą do niezdefiniowanego zachowania: dane mogą zostać zapisane, zapisane częściowo (powiedzmy, przekazaliśmy 10 bajtów/80 bitów, a udało się zapisać tylko 45 bitów), nie wykluczone, że część bitów znajdzie się w 'przejściowym' stanie (odczyt może zwrócić zarówno 0, jak i 1);
• Błędy samej pamięci flash.
  BER, choć bardzo niski, nie może być równy zeru;
• Błędy na szynie
  Dane przesyłane przez SPI nie są w żaden sposób zabezpieczone, mogą wystąpić zarówno pojedyncze błędy bitowe, jak i błędy synchronizacji - utrata lub wstawianie bitów (co prowadzi do masowych zniekształceń danych);
• Inne błędy/usterki
  Błędy w kodzie, 'glitche' Raspberry, ingerencja obcych...

Sformułowałem wymagania, których spełnienie, moim zdaniem, jest niezbędne dla zapewnienia niezawodności:

• zapisy muszą trafiać do pamięci flash natychmiast, zapis opóźniony nie jest brany pod uwagę; - jeśli wystąpi błąd, powinien być wykrywany i przetwarzany jak najszybciej; - system powinien, jeśli to możliwe, przywracać działanie po błędach.
  (przykład z życia 'jak nie powinno być', z którym, myślę, wszyscy się spotkali: po awaryjnym restarcie 'zepsuł' się system plików i system operacyjny się nie uruchamia)

Pomysły, podejścia, refleksje

Gdy zacząłem myśleć nad tym zadaniem, w mojej głowie przewijało się mnóstwo pomysłów, na przykład:

• użycie kompresji danych;
• użycie sprytnych struktur danych, na przykład przechowywanie nagłówków zapisów oddzielnie od samych zapisów, aby w przypadku błędu w jakimś zapisie można było bez problemu odczytać pozostałe;
• użycie pól bitowych do kontroli zakończenia zapisu przy wyłączeniu zasilania;
• przechowywanie sum kontrolnych dla wszystkiego i wszędzie;
• użycie jakiegoś rodzaju kodowania odpornego na zakłócenia.

Część tych pomysłów została wykorzystana, część postanowiono odrzucić. Zróbmy to po kolei.

Kompresja danych

Same zdarzenia, które rejestrujemy w dzienniku, są dość jednorodne i powtarzalne ('wrzucono monetę 5 zł', 'naciśnięto przycisk wydania reszty', ...). Dlatego kompresja powinna okazać się dość efektywna.

Koszty związane z kompresją są nieistotne (nasz procesor jest wystarczająco mocny, nawet w pierwszym Pi było jedno rdzeń o częstotliwości 700 MHz, w aktualnych modelach kilka rdzeni o częstotliwości powyżej gigaherca), prędkość wymiany z pamięcią jest niska (kilka megabajtów na sekundę), a rozmiar zapisów jest niewielki. Ogólnie rzecz biorąc, jeśli kompresja będzie miała wpływ na wydajność, to tylko pozytywny (absolutnie niekrytyczne, po prostu stwierdzam). Mamy przecież zwykły system Linux, a nie prawdziwie wbudowany, więc realizacja nie powinna wymagać dużego wysiłku (wystarczy połączyć bibliotekę i użyć kilku jej funkcji).

Wzięto fragment logu z działającego urządzenia (1,7 MB, 70 tysięcy wpisów) i na początku sprawdzono jego kompresję przy pomocy dostępnych na komputerze gzip, lz4, lzop, bzip2, xz, zstd.

• gzip, xz, zstd pokazały podobne wyniki (40 KB).
  Zdziwiło mnie, że modny xz wypadł na poziomie gzip lub zstd;
• lzip z ustawieniami fabrycznymi dał nieco gorszy wynik;
• lz4 i lzop pokazały niezbyt dobre wyniki (150 KB);
• bzip2 pokazał zaskakująco dobry wynik (18 KB).

Tak więc dane kompresują się bardzo dobrze.
Więc (jeśli nie znajdziemy poważnych wad) kompresja będzie! Po prostu dlatego, że na tę samą pamięć USB zmieści się więcej danych.

Zastanówmy się nad wadami.

Pierwszy problem: już ustaliliśmy, że każdy wpis musi natychmiast trafić na pamięć USB. Zwykle kompresor gromadzi dane z strumienia wejściowego, aż zdecyduje, że czas pisać do wyjścia. Nam z kolei potrzebny jest natychmiast skompresowany blok danych, który musimy zapisać w pamięci nieulotnej.

Widzę trzy ścieżki:

1. Komprimir każde wpis za pomocą kompresji słownikowej zamiast wcześniej omówionych algorytmów.
   To całkiem realna opcja, ale mi się nie podoba. Aby zapewnić w miarę przyzwoity poziom kompresji, słownik musi być „dopasowany” do konkretnych danych; każda zmiana spowoduje katastrofalny spadek poziomu kompresji. Tak, problem można rozwiązać poprzez stworzenie nowej wersji słownika, ale to kłopot – będziemy musieli przechowywać wszystkie wersje słownika; w każdym wpisie musimy wskazać, z którą wersją słownika został skompresowany…
2. Kompresować cada wpis „klasycznymi” algorytmami, ale niezależnie od innych.
   Rozważane algorytmy kompresji nie są zaprojektowane do pracy z wpisami takiej wielkości (rzędu dziesiątek bajtów), współczynnik kompresji będzie wyraźnie mniejszy niż 1 (to znaczy zwiększenie objętości danych zamiast ich kompresji);
3. Dokonywać FLUSH po każdej wpisie.
   W wielu bibliotekach kompresji jest obsługa FLUSH. Jest to polecenie (lub parametr dla procesu kompresji), które po otrzymaniu sprawia, że kompresor tworzy skompresowany strumień w taki sposób, aby na jego podstawie można było odzyskać wszystkie rozpakowane dane, które zostały już uzyskane. Taki odpowiednik sync w systemach plikowych lub commit w sql.
   Ważne jest, że następne operacje kompresji będą mogły wykorzystać zgromadzony słownik, a stopień kompresji nie ucierpi tak bardzo jak w poprzedniej wersji.

Myślę, że oczywiste jest, że wybrałem trzecią opcję, zatrzymamy się na niej dokładniej.

Znaleziono świetny artykuł o FLUSH w zlib.

Wykonałem test w oparciu o artykuł, wzięłem 70 tysięcy wpisów dziennika z rzeczywistego urządzenia, przy rozmiarze strony wynoszącym 60KB (do rozmiaru strony wrócimy jeszcze) otrzymałem:

Dane źródłowe
Kompresja gzip -9 (bez FLUSH)
zlib z Z_PARTIAL_FLUSH
zlib z Z_SYNC_FLUSH

Objętość, KB
1692
40
352
604

Na pierwszy rzut oka koszt związany z FLUSH wydaje się niezwykle wysoki, jednak w rzeczywistości mamy niewielki wybór — albo wcale nie kompresować, albo kompresować (i to bardzo efektywnie) z FLUSH. Nie należy zapominać, że mamy 70 tysięcy wpisów, a nadmiar wprowadzany przez Z_PARTIAL_FLUSH wynosi zaledwie 4-5 bajtów na wpis. A współczynnik kompresji wyniósł prawie 5:1, co jest więcej niż doskonałym wynikiem.

Może się to wydawać zaskakujące, ale w rzeczywistości Z_SYNC_FLUSH jest bardziej efektywnym sposobem na wykonanie FLUSH

W przypadku użycia Z_SYNC_FLUSH 4 ostatnie bajty każdego wpisu będą zawsze 0x00, 0x00, 0xff, 0xff. A jeśli je znamy — możemy ich nie przechowywać, w ten sposób końcowy rozmiar wynosi tylko 324KB.

W artykule, do którego się odwołuję, jest wyjaśnienie:

Nowy blok typu 0 z pustą zawartością jest dołączany.

Blok typu 0 z pustą zawartością składa się z:

• nagłówka bloku o długości trzech bitów;
• 0 do 7 bitów równych zeru, aby osiągnąć wyrównanie bajtowe;
• czterobajtowej sekwencji 00 00 FF FF.

Jak łatwo zauważyć, przed tymi 4 bajtami w ostatnim bloku występuje od 3 do 10 zerowych bitów. Jednak praktyka pokazała, że rzeczywiście zera to przynajmniej 10.

Okazuje się, że tak krótkie bloki danych są zazwyczaj (zawsze?) kodowane za pomocą bloku typu 1 (blok stały), który zawsze kończy się 7 zerowymi bitami, co daje łącznie 10-17 gwarantowanych zerowych bitów (a pozostałe będą zerowe z prawdopodobieństwem około 50%).

Tak więc, w danych testowych w 100% przypadków przed 0x00, 0x00, 0xff, 0xff występuje jeden zerowy bajt, a w więcej niż jednej trzeciej przypadków — dwa zerowe bajty (możliwe, że wynika to z faktu, że używam binarnego CBOR, a przy użyciu tekstowego JSON częściej występowałyby bloki typu 2 — blok dynamiczny, a zatem występowałyby bloki bez dodatkowych zerowych bajtów przed 0x00, 0x00, 0xff, 0xff).

W sumie w dostępnych danych testowych można zmieścić się w mniej niż 250KB skompresowanych danych.

Można jeszcze trochę zaoszczędzić, zajmując się żonglowaniem bitami: obecnie ignorujemy obecność kilku zerowych bitów na końcu bloku, kilka bitów na początku bloku również się nie zmienia...
Ale w tym momencie podjąłem stanowczą decyzję, aby się zatrzymać, bo w takim tempie można dojść do stworzenia własnego archiwizatora.

W rezultacie, z moich danych testowych uzyskałem 3-4 bajty na zapis, współczynnik kompresji wyniósł ponad 6:1. Szczerze mówiąc, nie spodziewałem się takiego wyniku, moim zdaniem wszystko, co lepsze od 2:1 to już wynik, który uzasadnia użycie kompresji.

Wszystko świetnie, ale zlib (deflate) to jednak archaiczny, zasłużony i trochę staromodny algorytm kompresji. Już sama kwestia, że jako słownik wykorzystuje ostatnie 32 KB ze strumienia niekompresowanych danych, dzisiaj wydaje się dziwna (to znaczy, jeśli jakiś blok danych bardzo przypomina to, co było w strumieniu wejściowym 40 KB temu, będzie on zaczynał się archiwizować od nowa, a nie odnosił do wcześniejszego wystąpienia). W nowoczesnych archiwizatorach rozmiar słownika częściej mierzy się w megabajtach, a nie w kilobajtach.

Tak więc kontynuujemy nasze mini-badanie archiwizatorów.

Następnym testowanym był bzip2 (przypominam, bez FLUSH pokazał fantastyczny stopień kompresji, prawie 100:1). Niestety, z FLUSH pokazał się bardzo słabo, rozmiar skompresowanych danych okazał się większy niż niekompresowanych.

Moje przypuszczenia co do przyczyn niepowodzenia

Libbz2 oferuje tylko jedną opcję flush, która, jak się wydaje, oczyszcza słownik (analogicznie do Z_FULL_FLUSH w zlib), więc nie ma mowy o jakiejkolwiek efektywnej kompresji po tym.

A ostatnim testowanym był zstd. W zależności od parametrów kompresuje albo na poziomie gzip, ale dużo szybciej, albo lepiej niż gzip.

Niestety, z FLUSH i on pokazał się "niezbyt": rozmiar skompresowanych danych wyniósł około 700 KB.

Ja zadałem pytanie na stronie projektu w githubie, otrzymałem odpowiedź, że warto zakładać do 10 bajtów danych pomocniczych na każdy blok skompresowanych danych, co jest bliskie uzyskanym rezultatom, nie da się dogonić deflate.

Na tym postanowiłem zakończyć eksperymenty z archiwizatorami (przypominam, xz, lzip, lzo, lz4 nie spisały się jeszcze na etapie testów bez FLUSH, a rozważanie bardziej egzotycznych algorytmów kompresji nie miało sensu).

Wracamy do problemów archiwizacji.

Drugim (jak się mówi, w porządku, a nie według znaczenia) problemem jest to, że skompresowane dane są jedną ciągłą strumieniem, w którym ciągle występują odniesienia do wcześniejszych fragmentów. W ten sposób, w przypadku uszkodzenia jakiegoś fragmentu skompresowanych danych, tracimy nie tylko powiązany z nim blok nieskompresowanych danych, ale także wszystkie następne.

Istnieją podejścia do rozwiązania tego problemu:

1. Zapobiegać pojawieniu się problemu — dodawać do skompresowanych danych nadmiarowość, która pozwoli na identyfikację i poprawę błędów; o tym porozmawiamy później;
2. Minimalizować konsekwencje w przypadku wystąpienia problemu.
   Już wcześniej mówiliśmy, że możemy kompresować każdy blok danych niezależnie, wówczas problem zniknie sam w sobie (uszkodzenie danych jednego bloku spowoduje utratę danych tylko tego bloku). Jednak to skrajny przypadek, w którym kompresja danych będzie mało efektywna. Przeciwieństwem jest wykorzystanie całych 4 MB naszej pamięci jako jednego archiwum, co da nam doskonałą kompresję, ale katastrofalne konsekwencje w przypadku uszkodzenia danych.
   Tak, potrzebny jest kompromis z punktu widzenia niezawodności. Należy jednak pamiętać, że opracowujemy format przechowywania danych dla pamięci nieulotnej o ekstremalnie niskim BER i deklarowanym okresie przechowywania danych wynoszącym 20 lat.

W trakcie eksperymentów odkryłem, że bardziej zauważalne straty w poziomie kompresji zaczynają się dla bloków skompresowanych danych o rozmiarze poniżej 10 KB.
Wcześniej wspomniano, że używana pamięć ma organizację stronicową, nie widzę powodów, dla których nie warto korzystać z przystosowania „jedna strona — jeden blok skompresowanych danych”.

To znaczy, minimalny rozumny rozmiar strony wynosi 16 KB (z zapasem na informacje pomocnicze). Jednak tak mały rozmiar strony nakłada istotne ograniczenia na maksymalny rozmiar wpisu.

Chociaż nie przewiduję na razie wpisów większych niż kilka kilobajtów w skompresowanej postaci, zdecydowałem się na użycie stron o rozmiarze 32 KB (co daje łącznie 128 stron na układzie).

Podsumowanie:

• Dane przechowujemy w sposób skompresowany z użyciem zlib (deflate);
• Ustawiamy Z_SYNC_FLUSH dla każdego wpisu;
• Obcinamy końcowe bajty każdej skompresowanej notatki (np. 0x00, 0x00, 0xff, 0xff); w nagłówku podajemy, ile bajtów obcięliśmy;
• Dane przechowujemy w stronach o wielkości 32 KB; w obrębie strony idzie jednolity strumień skompresowanych danych; na każdej stronie kompresję rozpoczynamy od nowa.

I zanim zakończymy temat kompresji, chciałbym zwrócić uwagę, że skompresowanych danych uzyskujemy tylko kilka bajtów na zapis, dlatego niezwykle ważne jest, aby nie zwiększać danych pomocniczych, każdy bajt się liczy.

Przechowywanie nagłówków danych

Ponieważ mamy do czynienia z zapisami o zmiennej długości, musimy w jakiś sposób określić rozmieszczenie/granice zapisów.

Znam trzy podejścia:

1. Wszystkie zapisy są przechowywane w ciągłym strumieniu, najpierw znajduje się nagłówek zapisu, który zawiera długość, a następnie sam zapis.
   W tej opcji zarówno nagłówki, jak i dane mogą mieć zmienną długość.
   W zasadzie otrzymujemy pojedynczy powiązany list, który jest używany wszędzie;
2. Nagłówki i same zapisy są przechowywane w osobnych strumieniach.
   Korzystając z nagłówków stałej długości, osiągamy to, że uszkodzenie jednego nagłówka nie wpływa na pozostałe.
   Podobne podejście jest stosowane na przykład w wielu systemach plików;
3. Zapisy są przechowywane w ciągłym strumieniu, granice zapisu są określane na podstawie pewnego znacznika (znaku/sekwencji znaków, która jest zabroniona wewnątrz bloków danych). Jeśli w obrębie zapisu napotkamy znacznik, zastępujemy go pewną sekwencją (escape'ujemy go).
   Podobne podejście jest stosowane na przykład w protokole PPP.

Ilustruję.

Opcja 1:

Tu wszystko jest bardzo proste: znając długość zapisu, możemy obliczyć adres następnego nagłówka. Tak poruszamy się po nagłówkach, aż napotkamy obszar wypełniony 0xff (wolny obszar) lub koniec strony.

Opcja 2:

Z powodu zmiennej długości zapisu nie możemy z góry powiedzieć, ile zapisów (a więc i nagłówków) potrzebujemy na stronę. Można rozdzielić nagłówki i same dane na różne strony, ale bardziej podoba mi się inne podejście: zarówno nagłówki, jak i dane umieszczamy na jednej stronie, jednak nagłówki (stałej długości) są od początku strony, a dane (zmiennej długości) — od końca. Gdy się 'spotkają' (brakuje miejsca na nowy zapis) — uznajemy tę stronę za zapełnioną.

Wariant 3:

Nie ma potrzeby przechowywać w nagłówku długości lub innych informacji o lokalizacji danych; wystarczą znaczniki oznaczające granice wpisów. Jednak dane muszą być przetwarzane podczas zapisu/odczytu.
Jako znacznik użyłbym 0xff (które wypełnia stronę po wymazaniu), w ten sposób wolna przestrzeń na pewno nie będzie traktowana jako dane.

Tabela porównawcza:

Opcja 1
Opcja 2
Opcja 3

Odporność na błędy
—
+
+

Kompaktowość
+
—
+

Złożoność realizacji
*
**
**

Wariant 1 ma fatalny błąd: w przypadku uszkodzenia któregoś z nagłówków, cała następna sekwencja ulega zniszczeniu. Pozostałe warianty pozwalają na odzyskanie części danych nawet przy masowych uszkodzeniach.
Ale warto przypomnieć, że zdecydowaliśmy się przechowywać dane w skompresowanej formie, i tak tracimy wszystkie dane na stronie po uszkodzonej zapisanej, więc chociaż w tabeli widnieje minus, nie bierzemy go pod uwagę.

Kompaktowość:

• w pierwszym wariancie musimy przechowywać w nagłówku tylko długość; jeśli użyjemy zmiennych o zmiennej długości, to w większości przypadków możemy się ograniczyć do jednego bajta;
• w drugim wariancie musimy przechowywać adres początkowy i długość; zapis musi być stałej długości, oceniam to na 4 bajty na zapis (dwa bajty na przesunięcie i dwa bajty na długość);
• trzeci wariant potrzebuje tylko jednego symbolu do oznaczenia początku zapisu, a sama zapis z powodu escaped rośnie o 1-2%. Ogólnie całkowity parytet z pierwszym wariantem.

Początkowo rozważałem drugi wariant jako główny (i nawet napisałem jego realizację). Zrezygnowałem tylko wtedy, gdy ostatecznie zdecydowałem się na kompresję.

Może kiedyś jednak zdecyduję się na podobny wariant. Na przykład, jeśli będę musiał zajmować się przechowywaniem danych dla statku kursującego między Ziemią a Marsem — zupełnie inne wymagania dotyczące niezawodności, promieniowanie kosmiczne,…

Co do trzeciego wariantu: przyznałem mu dwie gwiazdki za złożoność realizacji, po prostu dlatego, że nie lubię bawić się w escaped, zmiana długości w trakcie itp. Tak, być może stronniczo, ale kod muszę pisać ja — po co zmuszać się do robienia czegoś, co się nie podoba.

Podsumowanie: wybieramy wariant przechowywania w postaci łańcuchów «nagłówek z długością — dane o zmiennej długości» ze względu na efektywność i prostotę realizacji.

Zastosowanie pól bitowych do kontrolowania sukcesu operacji zapisu

Już teraz nie pamiętam, gdzie podpatrzyłem ten pomysł, ale wygląda to mniej więcej tak:
Dla każdego wpisu rezerwujemy kilka bitów na przechowywanie flag.
Jak mówiliśmy wcześniej, po erase wszystkie bity są wypełnione 1, a my możemy zmieniać 1 na 0, ale nie odwrotnie. Zatem dla 'flaga nie ustawiona' używamy 1, dla 'flaga ustawiona' — 0.

Oto jak może wyglądać umieszczenie zmiennej długości w zapisach flash:

1. Ustalamy flagę 'rozpoczęcie zapisu długości';
2. Zapisujemy długość;
3. Ustalamy flagę 'rozpoczęcie zapisu danych';
4. Zapisujemy dane;
5. Ustalamy flagę 'zapis zakończony'.

Oprócz tego będziemy mieli flagę 'wystąpił błąd', co daje nam 4 bity flagowe.

W takim przypadku mamy dwa stabilne stany '1111' — zapis się nie rozpoczął i '1000' — zapis przebiegł pomyślnie; w przypadku niespodziewanego przerwania procesu zapisu uzyskamy stany pośrednie, które następnie będziemy mogli wykryć i przetworzyć.

Podejście jest ciekawe, ale chroni tylko przed niespodziewanym odcięciem zasilania i podobnymi awariami, co, oczywiście, jest ważne, jednak nie jest to jedyna (a nawet nie główna) przyczyna możliwych awarii.

Podsumowanie: Idziemy dalej w poszukiwaniu dobrego rozwiązania.

Sumy kontrolne

Sumy kontrolne również pozwalają upewnić się (z wystarczającym prawdopodobieństwem), że odczytujemy dokładnie to, co miało być zapisane. I, w przeciwieństwie do omówionych powyżej pól bitowych, działają one zawsze.

Jeśli rozważymy listę potencjalnych źródeł problemów, o których mówiliśmy wcześniej, to suma kontrolna jest w stanie rozpoznać błąd niezależnie od jego pochodzenia (z wyjątkiem może złowrogich kosmitów — ci mogą również sfałszować sumę kontrolną).

Więc jeśli naszym celem jest sprawdzenie, że dane są nienaruszone, sumy kontrolne to doskonały pomysł.

Wybór algorytmu obliczania sumy kontrolnej nie budził wątpliwości — CRC. Z jednej strony, właściwości matematyczne pozwalają na 100% wychwycenie błędów niektórych typów, z drugiej — na danych losowych zazwyczaj ten algorytm pokazuje prawdopodobieństwo kolizji niewiele większe od teoretycznego limitu. Niech to nie będzie najszybszy algorytm, ani zawsze minimalny pod względem liczby kolizji, ale ma on jedną bardzo ważną cechę: w testach, które przeprowadzałem, nie natrafiłem na wzorce, na których wyraźnie by zawiódł. Stabilność to kluczowa cecha w tym przypadku.

Przykład obszernego badania: część 1, Part 2 (linki do narod.ru, przepraszam).

Jednak wybór sumy kontrolnej nie jest zakończony, CRC to całe rodziny sum kontrolnych. Musimy zdecydować o długości, a następnie wybrać wielomian.

Wybór długości sumy kontrolnej nie jest tak prostym pytaniem, jak się wydaje na pierwszy rzut oka.

Ilustruję:
Niech prawdopodobieństwo błędu w każdym bajcie wynosi a idealna suma kontrolna, obliczmy średnią liczbę błędów na milion zapisów:

Dane, bajt
Suma kontrolna, bajt
Nieodkrytych błędów
Fałszywych wykryć błędów
Łącznie błędnych wykryć

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

Wydawałoby się, że wszystko jest proste — wybieraj w zależności od długości danych chronionych długość sumy kontrolnej z minimalną ilością błędnych wykryć — i sprawa jest załatwiona.

Jednak w przypadku krótkich sum kontrolnych pojawia się problem: choć dobrze wykrywają pojedyncze błędy bitowe, mogą z dość dużym prawdopodobieństwem uznać za prawidłowe całkowicie losowe dane. Na Habrze był już artykuł opisujący problem w realnym życiu.

Dlatego, aby uczynić przypadkowe dopasowanie sumy kontrolnej praktycznie niemożliwym, należy używać sum kontrolnych o długości 32 bitów i więcej (dla długości większych niż 64 bity zazwyczaj stosuje się kryptograficzne funkcje haszujące).

Pomimo że wcześniej pisałem, że trzeba oszczędzać miejsce za wszelką cenę, jednak użyjemy 32-bitowej sumy kontrolnej (16 bitów to za mało, prawdopodobieństwo kolizji jest większe niż 0.01%; a 24 bity, jak to się mówi, ani tu, ani tam).

Tu może pojawić się sprzeciw: czy naprawdę oszczędzaliśmy każdy bajt przy wyborze kompresji, aby teraz oddać 4 bajty naraz? Czy nie lepiej było nie kompresować i nie dodawać sumy kontrolnej? Oczywiście, że nie, brak kompresji nie oznacza, że kontrola integralności nie jest nam potrzebna.

Nie będziemy wynajdować roweru na wybór wielomianu, weźmiemy obecnie popularny CRC-32C.
Ten kod wykrywa 6 błędów bitowych w pakietach do 22 bajtów (to zapewne najczęstszy przypadek dla nas), 4 błędy bitowe w pakietach do 655 bajtów (też częsty przypadek dla nas), 2 lub jakąkolwiek nieparzystą liczbę błędów bitowych w pakietach o sensownej długości.

Jeśli kogoś interesują szczegóły

artykuł w Wikipedii na temat CRC.

Parametry kodu crc-32c na na stronie Kupmana — być może najważniejszego specjalisty w dziedzinie CRC na świecie.

W jego artykule jest jeszcze jeden interesujący kod, zapewniający nieco lepsze parametry dla istotnych dla nas długości pakietów, ale nie uznałem różnicy za istotną, a siebie za wystarczająco kompetentnego, aby wybrać niestandardowy kod zamiast standardowego i dobrze przebadanego.

Ponadto, ponieważ mamy dane skompresowane, pojawia się pytanie: czy obliczać sumę kontrolną dla danych skompresowanych, czy nieskompresowanych?

Argumenty 'za' obliczaniem sumy kontrolnej nieskompresowanych danych:

• w końcu musimy sprawdzić integralność przechowywanych danych — właśnie to bezpośrednio sprawdzamy (przy okazji będą również sprawdzone możliwe błędy w realizacji kompresji/dekompresji, uszkodzenia spowodowane uszkodzoną pamięcią itd.);
• algorytm deflate w zlib ma wystarczająco dojrzałą realizację i nie powinien zawodzić przy 'krzywych' danych wejściowych, co więcej, często potrafi samodzielnie wykrywać błędy w strumieniu wejściowym, zmniejszając ogólne prawdopodobieństwo niezauważenia błędu (przeprowadziłem test z inwersją pojedynczego bitu w krótkim zapisie, zlib wykrył błąd w około jednej trzeciej przypadków).

Argumenty 'przeciw' obliczaniu sumy kontrolnej nieskompresowanych danych:

• CRC jest 'dostosowane' właśnie do nielicznych błędów bitowych, które charakterystyczne są dla pamięci flash (błąd bitowy w skompresowanym strumieniu może spowodować masowe zmiany w strumieniu wyjściowym, na którym, teoretycznie, możemy 'uchwycić' kolizję);
• nie bardzo podoba mi się pomysł przesyłania dekompressorowi potencjalnie uszkodzonych danych, kto wie,jak on zareaguje.

W tym projekcie postanowiłem odstąpić od ogólnie przyjętej praktyki przechowywania sumy kontrolnej nieskompresowanych danych.

Podsumowanie: używamy CRC-32C, sumę kontrolną obliczamy z danych w takiej formie, w jakiej są zapisywane w pamięci flash (po kompresji).

Nadwyżka

Użycie nadmiarowego kodowania nie eliminuje oczywiście utraty danych, jednak może znacząco (często o wiele rzędów) zmniejszyć prawdopodobieństwo nieodwracalnej utraty danych.

Możemy stosować różne rodzaje nadmiarowości, aby naprawiać błędy.
Kody Hamming'a mogą naprawiać pojedyncze błędy bitowe, kody Reed-Solomon'a są symboliczne, a kilka kopii danych w połączeniu z sumami kontrolnymi czy kodowaniem typu RAID-6 mogą pomóc w odzyskaniu danych nawet w przypadku masowych uszkodzeń.
Początkowo byłem nastawiony na szerokie wykorzystanie kodowania odpornych na zakłócenia, ale potem zrozumiałem, że najpierw należy mieć wyobrażenie o tym, przed jakimi błędami chcemy się chronić, a później wybierać kodowanie.

Mówiliśmy wcześniej, że błędy należy identyfikować jak najszybciej. W jakich momentach możemy się spotkać z błędami?

1. Nieukończony zapis (z jakiegoś powodu zasilanie wyłączyło się w momencie zapisu, Raspberry zawiesił się, …)
   Niestety, w przypadku takiego błędu pozostaje tylko zignorować nieprawidłowe zapisy i uznać dane za utracone;
2. Błędy zapisu (z jakiegoś powodu do pamięci flash zapisano coś innego niż to, co zapisano)
   Takie błędy możemy od razu wykryć, jeśli bezpośrednio po zapisie dokonamy kontroli odczytu;
3. Zniekształcenie danych w pamięci w trakcie przechowywania;
4. Błędy odczytu
   Aby naprawić wystarczająco, w przypadku niezgodności sumy kontrolnej, wystarczy kilkakrotnie powtórzyć odczyt.

Oznacza to, że tylko błędy trzeciego typu (samoistne uszkodzenie danych podczas przechowywania) nie mogą być naprawione bez kodowania odpornych na zakłócenia. Uważam, że takie błędy są jednak niezwykle mało prawdopodobne.

Podsumowanie: postanowiono zrezygnować z nadmiarowego kodowania, ale jeśli eksploatacja wykaże błędność tej decyzji, to wrócimy do rozważenia tej kwestii (z już zgromadzoną statystyką o awariach, która pozwoli wybrać optymalny typ kodowania).

Inne

Oczywiście format artykułu nie pozwala uzasadnić każdego bitu w formacie (a ja już również straciłem siły), dlatego krótko przelotnie przejdę przez niektóre kwestie, które nie zostały wcześniej poruszone.

• Postanowiono, aby wszystkie strony były "równo uprawnione"
  Nie będzie specjalnych stron z metadanymi, oddzielnymi strumieniami itd., zamiast tego pojawi się jeden strumień, który przepisuje wszystkie strony kolejno.
  Zapewnia to równomierne zużycie stron, brak jednego punktu awarii, a po prostu się podoba;
• Należy wprowadzić wersjonowanie formatu.
  Format bez numeru wersji w nagłówku to zło!
  Wystarczy dodać do nagłówka strony pole z jakimś Magic Number (sygnaturą), które będzie wskazywać na używaną wersję formatu. (nie sądzę, aby w praktyce było ich nawet dziesięć);
• Używać zmiennej długości nagłówków dla rekordów (których jest bardzo dużo), starając się w większości przypadków uczynić je o długości 1 bajta;
• Do kodowania długości nagłówka i długości obcinanej części skompresowanego rekordu używać binarnych kodów zmiennej długości.

Bardzo pomógł generator online kodów Huffmana. Dosłownie w kilka minut udało się dopasować potrzebne kody zmiennej długości.

Opis formatu przechowywania danych

Kolejność bajtów

Pola większe niż jeden bajt są przechowywane w formacie big-endian (network byte order), co oznacza, że 0x1234 jest zapisywane jako 0x12, 0x34.

Podział na strony

Cała pamięć flash jest podzielona na strony o równej wielkości.

Domyślny rozmiar strony to 32 KB, ale nie więcej niż 1/4 całkowitego rozmiaru układu pamięci (dla układu 4 MB wypada 128 stron).

Każda strona przechowuje dane niezależnie od innych (to znaczy dane jednej strony nie odnoszą się do danych innej strony).

Wszystkie strony są ponumerowane w naturalnej kolejności (w porządku rosnącym adresów), zaczynając od numeru 0 (strona zerowa zaczyna się od adresu 0, pierwsza — od 32 KB, druga — od 64 KB itd.)

Układ pamięci jest używany jako bufor cykliczny (ring buffer), co oznacza, że najpierw zapis trafia do strony o numerze 0, potem do strony o numerze 1, …, kiedy wypełnimy ostatnią stronę, zaczyna się nowa pętla, a zapis kontynuuje się od strony zerowej.

Wewnątrz strony

Na początku strony znajduje się 4-bajtowy nagłówek strony, następnie suma kontrolna nagłówka (CRC-32C), a za nią przechowywane są zapisy w formacie „nagłówek, dane, suma kontrolna.”

Nagłówek strony (na schemacie w kolorze brudnozielonym) składa się z:

• dwubajtowego pola Magic Number (to także — oznaczenie wersji formatu)
  dla bieżącej wersji formatu jest uważany za 0xed00 ⊕ numer strony;
• dwubajtowego licznika «Wersja strony» (numer cyklu zapisu pamięci).

Wpisy na stronie przechowywane są w skompresowanej postaci (używany jest algorytm deflate). Wszystkie wpisy na jednej stronie kompresowane są w jednym strumieniu (stosuje się wspólny słownik), na każdej nowej stronie kompresja zaczyna się od nowa. Oznacza to, że do dekompresji dowolnego wpisu wymagane są wszystkie wcześniejsze wpisy z tej strony (i tylko z tej).

Każdy wpis zostanie skompresowany z flagą Z_SYNC_FLUSH, przy czym na końcu skompresowanego strumienia znajdują się 4 bajty 0x00, 0x00, 0xff, 0xff, poprzedzone, możliwie, jeszcze jednym lub dwoma zerowymi bajtami.
Tę sekwencję (o długości 4, 5 lub 6 bajtów) odrzucamy podczas zapisu do pamięci flash.

Nagłówek wpisu składa się z 1, 2 lub 3 bajtów, które przechowują:

• jeden bit (T), oznaczający typ wpisu: 0 — kontekst, 1 — dziennik;
• pole zmiennej długości (S) od 1 do 7 bitów, określające długość nagłówka i «ogon», który należy dodać do wpisu w celu dekompresji;
• długość wpisu (L).

Tabela wartości S:

S
Długość nagłówka, bajty
Odrzuca się przy zapisie, bajty

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)

Spróbowałem to zilustrować, nie wiem, jak dobrze to wyszło:

Żółtym tutaj oznaczone pole T, białym — pole S, zielonym L (długość skompresowanych danych w bajtach), niebieskim — skompresowane dane, czerwonym — końcowe bajty skompresowanych danych, które nie są zapisywane do pamięci flash.

W ten sposób nagłówki wpisów o najczęstszej długości (do 63+5 bajtów w skompresowanej postaci) będziemy mogli zapisać jednym bajtem.

Po każdym wpisie przechowywana jest suma kontrolna CRC-32C, której jako wartość początkowa (init) używane jest odwrócone wartość poprzedniej sumy kontrolnej.

CRC ma właściwość «ciągłości», działa (plus-minus inwersja bitów w procesie) taka formuła: .
Oznacza to, że faktycznie obliczamy CRC wszystkich poprzednich bajtów nagłówków i danych na tej stronie.

Bezpośrednio za sumą kontrolną znajduje się nagłówek następnego wpisu.

Nagłówek skonstruowany jest w taki sposób, że jego pierwszy bajt zawsze różni się od 0x00 i 0xff (jeśli zamiast pierwszego bajtu nagłówka spotykamy 0xff, to oznacza to nieużywaną przestrzeń; 0x00 sygnalizuje błąd).

Przykładowe algorytmy

Odwołanie do pamięci flash

Każde odczytanie odbywa się z weryfikacją sumy kontrolnej.
Jeśli suma kontrolna się nie zgadza, odczyt jest powtarzany kilka razy w nadziei na odczytanie poprawnych danych.

(to ma sens, Linux nie buforuje odczytu z NOR Flash, sprawdzone)

Zapisywanie do pamięci flash

Zapisujemy dane.
Odczytujemy je.

Jeśli odczytane dane nie zgadzają się z zapisanymi, wypełniamy obszar zerami i sygnalizujemy błąd.

Przygotowanie nowego układu do pracy

W celu inicjalizacji w pierwszą (a właściwie zerową) stronę zapisywany jest nagłówek z wersją 1.
Po tym do tej strony zapisywany jest początkowy kontekst (zawiera UUID automatu i domyślne ustawienia).

I wszystko, pamięć flash gotowa do pracy.

Ładowanie automatu

Podczas ładowania odczytywane są pierwsze 8 bajtów każdej strony (nagłówek + CRC), strony z nieznanym Magic Number lub błędnym CRC są ignorowane.
Z «poprawnych» stron wybierane są strony z maksymalną wersją, z nich wybrana jest strona o najwyższym numerze.
Odczytywana jest pierwsza wpis, sprawdzana jest poprawność CRC oraz obecność flagi «kontekst». Jeśli wszystko jest w porządku, ta strona uznawana jest za bieżącą. Jeśli nie, wracamy do poprzedniej, aż znajdziemy «żywą» stronę.
Na znalezionej stronie odczytujemy wszystkie wpisy, te oznaczone flagą «kontekst» stosujemy.
Zapisujemy słownik zlib (będzie potrzebny do dopisywania do tej strony).

I wszystko, ładowanie zakończone, kontekst odzyskany, można pracować.

Dodawanie wpisu do dziennika

Kompresujemy wpis z poprawnym słownikiem, wskazując Z_SYNC_FLUSH. Sprawdzamy, czy skompresowany wpis zmieści się na bieżącej stronie.
Jeśli się nie mieści (lub na stronie były błędy CRC) — zaczynamy nową stronę (patrz poniżej).
Zapisujemy wpis i CRC. Jeśli wystąpił błąd — zaczynamy nową stronę.

Nowa strona

Wybieramy wolną stronę z minimalnym numerem (wolną uznajemy stronę z błędną sumą kontrolną w nagłówku lub z wersją mniejszą niż bieżąca). Jeśli takich stron nie ma — wybieramy stronę z minimalnym numerem z tych, które mają wersję równą bieżącej.
Wybieramy stronę do wymazania. Porównujemy zawartość z 0xff. Jeśli coś jest nie tak, bierzemy następną wolną stronę itd.
Na wymazanej stronie zapisujemy nagłówek, pierwszym wpisem aktualny stan kontekstu, kolejnym — niezapisany wpis dziennika (jeśli taki istnieje).

Zastosowanie formatu

Moim zdaniem, to niezły format do przechowywania wszelkich bardziej lub mniej kompresowalnych strumieni informacji (zwykły tekst, JSON, MessagePack, CBOR, a może protobuf) w pamięci NOR Flash.

Oczywiście, format jest „dostosowany” do SLC NOR Flash.

Nie należy go używać z nośnikami o wysokim BER, np. NAND lub MLC NOR. (czy taka pamięć w ogóle jest dostępna w sprzedaży? Spotykałem się jedynie z odniesieniami w pracach na temat kodów korekcji).

Tym bardziej nie wolno go używać z urządzeniami, które mają własne FTL: USB flash, SD, MicroSD itd. (dla takiej pamięci stworzyłem format z rozmiarem strony 512 bajtów, sygnaturą na początku każdej strony i unikalnymi numerami zapisów — czasami z „zepsutego” pendrive'a udawało się prostym sekwencyjnym odczytem odzyskać wszystkie dane).

W zależności od zadań, format można bez zmian używać na pendrive'ach od 128 Kbit (16 KB) do 1 Gbit (128 MB). W razie potrzeby można go też wykorzystać na większych chipach, tylko prawdopodobnie trzeba dostosować rozmiar strony. (Ale tutaj pojawia się już pytanie o rentowność, cena dużych pamięci NOR Flash nie zachwyca).

Jeśli ktoś uznał format za interesujący i chciałby go wykorzystać w otwartym projekcie — piszcie, postaram się znaleźć czas, uporządkować kod i udostępnić na githubie.

Podsumowanie

Jak widać, ostatecznie format okazał się prosty. I nawet nudny..

W artykule trudno oddać ewolucję swojego punktu widzenia, ale uwierzcie: na początku chciałem stworzyć coś skomplikowanego, niezniszczalnego, zdolnego przetrwać nawet po wybuchu jądrowym w bezpośredniej bliskości. Jednak rozum (mam nadzieję) w końcu zwyciężył i stopniowo priorytety przesunęły się w stronę prostoty i kompaktowości.

Czy może się zdarzyć, że się myliłem? Tak, oczywiście. Może się okazać, na przykład, że zakupiliśmy partię wadliwych chipów. Lub z jakiegoś innego powodu sprzęt nie spełni oczekiwań dotyczących niezawodności.

Czy mam plan na tę ewentualność? Myślę, że po przeczytaniu artykułu nie Macie wątpliwości, że plan istnieje. I to nie jeden.

Jeśli spojrzeć na to nieco poważniej, format został opracowany jednocześnie jako opcja robocza i jako „testowe zgłoszenie”.

Na dzień dzisiejszy wszystko działa dobrze, dosłownie w ciągu kilku dni rozwiązanie będzie wdrożone. (około) na setkach urządzeń, zobaczymy, co się wydarzy w «bojowej» eksploatacji (na szczęście, mam nadzieję, że format pozwala na niezawodne wykrywanie awarii; więc uda się zebrać pełną statystykę). Po kilku miesiącach będzie można wyciągnąć wnioski (a jeśli nie będzie szczęścia — to i wcześniej).

Jeśli po zakończeniu użytkowania pojawią się poważne problemy i będą potrzebne poprawki, na pewno o tym napiszę.

Literatura

Nie chciałem tworzyć długiej, nudnej listy wykorzystanych prac, w końcu Google jest dostępny dla wszystkich.

Postanowiłem zostawić listę odkryć, które wydały mi się szczególnie interesujące, jednak stopniowo przeniosły się one bezpośrednio do tekstu artykułu, a w liście pozostał tylko jeden punkt:

1. Narzędzie infgen od autora zlib. Umie w zrozumiały sposób wyświetlać zawartość archiwów deflate/zlib/gzip. Jeśli musisz zgłębiać wewnętrzną budowę formatu deflate (lub gzip) — gorąco polecam.

Źródło: habr.com