pravěk

Existují prodejní automaty vlastní konstrukce. Uvnitř Raspberry Pi a nějaká kabeláž na samostatné desce. Připojen je mincovník, akceptor bankovek, bankovní terminál... Vše je řízeno samostatně psaným programem. Celá historie práce je zapsána do logu na flash disku (MicroSD), který je následně přenášen přes internet (pomocí USB modemu) na server, kde je uložen v databázi. Do 1c se načítají prodejní informace, nechybí ani jednoduché webové rozhraní pro sledování atp.

To znamená, že deník je životně důležitý – pro účetnictví (tržby, tržby atd.), sledování (všechny druhy poruch a jiných okolností vyšší moci); Dalo by se říci, že toto jsou všechny informace, které o tomto stroji máme.

problém

Flash disky se ukazují jako velmi nespolehlivá zařízení. Selhávají se záviděníhodnou pravidelností. To vede jak k prostojům stroje, tak (pokud z nějakého důvodu nelze protokol přenést online) ke ztrátě dat.

Není to první zkušenost s používáním flash disků, před tím tu byl jiný projekt s více než stovkou zařízení, kde byl časopis uložen na USB flash disky, problémy byly i se spolehlivostí, chvílemi přibývalo těch, které selhaly v měsíc byl v desítkách. Vyzkoušeli jsme různé flash disky včetně značkových s pamětí SLC a některé modely jsou spolehlivější než jiné, ale výměna flash disků problém radikálně nevyřešila.

Varování! Longread! Pokud vás nezajímá „proč“, ale pouze „jak“, můžete jít rovnou Na konci články.

rozhodnutí

První, co vás napadne, je: opustit MicroSD, nainstalovat například SSD a bootovat z něj. Teoreticky možné, pravděpodobně, ale relativně drahé a ne tak spolehlivé (je přidán adaptér USB-SATA; statistiky selhání u levných SSD také nejsou povzbudivé).

USB HDD také nevypadá jako zvlášť atraktivní řešení.

Proto jsme došli k této možnosti: ponechat bootování z MicroSD, ale používat je v režimu pouze pro čtení a uložit provozní protokol (a další informace jedinečné pro konkrétní kus hardwaru - sériové číslo, kalibrace senzorů atd.) někde jinde .

Téma read-only FS pro maliny již bylo nastudováno zevnitř i zvenku, v tomto článku se nebudu zdržovat implementačními detaily (ale pokud bude zájem, možná napíšu miničlánek na toto téma). Jediný bod, který bych chtěl poznamenat, je, že jak z osobních zkušeností, tak z recenzí těch, kteří to již implementovali, dochází ke zvýšení spolehlivosti. Ano, není možné se poruch úplně zbavit, ale výrazné snížení jejich frekvence je docela možné. A karty se sjednocují, což velmi usnadňuje výměnu pro obsluhu.

Hardware

O volbě typu paměti – NOR Flash – nebylo pochyb.
Argumenty:

• jednoduché připojení (nejčastěji sběrnice SPI, se kterou již máte zkušenosti, takže se nepředpokládají žádné hardwarové problémy);
• směšná cena;
• standardní operační protokol (implementace je již v linuxovém jádře, pokud chcete, můžete si vzít nějaký třetí strany, který je také přítomen, nebo dokonce napsat svůj vlastní, naštěstí je vše jednoduché);
• spolehlivost a zdroje:
  z typického datového listu: data jsou uložena po dobu 20 let, 100000 XNUMX cyklů vymazání pro každý blok;
  ze zdrojů třetích stran: extrémně nízké BER, předpokládá, že nejsou potřeba kódy pro opravu chyb (některé práce zvažují ECC pro NOR, ale obvykle stále znamenají MLC NOR; to se také stává).

Pojďme odhadnout požadavky na objem a zdroje.

Chtěl bych, aby bylo zaručeno, že data budou uložena několik dní. Je to nutné, aby se v případě jakýchkoli problémů s komunikací neztratila historie prodeje. V tomto období se zaměříme na 5 dní (i s přihlédnutím k víkendům a svátkům) problém lze vyřešit.

Aktuálně sbíráme cca 100kb logů denně (3-4 tisíce záznamů), ale postupně toto číslo roste - přibývá detailů, přibývají nové události. Navíc někdy dochází k výbuchům (některý senzor začne spamovat s falešně pozitivními výsledky, například). Vypočítáme pro 10 tisíc záznamů 100 bajtů každý - megabajtů za den.

Celkem vyjde 5 MB čistých (dobře komprimovaných) dat. Více k nim (Hrubý odhad) 1 MB servisních dat.

To znamená, že potřebujeme 8 MB čip, pokud nepoužíváme kompresi, nebo 4 MB, pokud ji používáme. Docela realistická čísla pro tento typ paměti.

Pokud jde o zdroj: pokud plánujeme, že se celá paměť bude přepisovat maximálně jednou za 5 dní, pak za 10 let služby dostaneme méně než tisíc přepisovacích cyklů.
Připomínám, že výrobce slibuje sto tisíc.

Něco málo o NOR vs NAND

Dnes je samozřejmě mnohem populárnější paměť NAND, ale pro tento projekt bych ji nepoužil: NAND na rozdíl od NOR nutně vyžaduje použití kódů pro opravu chyb, tabulku špatných bloků atd. a také nohy NAND čipy obvykle mnohem více.

Nevýhody NOR zahrnují:

• malý objem (a tedy vysoká cena za megabajt);
• nízká komunikační rychlost (z velké části kvůli tomu, že se používá sériové rozhraní, obvykle SPI nebo I2C);
• pomalé mazání (v závislosti na velikosti bloku trvá zlomek sekundy až několik sekund).

Zdá se, že pro nás není nic kritického, takže pokračujeme.

Pokud jsou detaily zajímavé, byl vybrán mikroobvod at25df321a (to je však nedůležité, na trhu je spousta analogů, které jsou kompatibilní v pinout a příkazovém systému; i když chceme nainstalovat mikroobvod od jiného výrobce a/nebo jiné velikosti, vše bude fungovat bez změny kód).

Ovladač používám zabudovaný v linuxovém jádře, na Raspberry je díky podpoře překryvů stromu zařízení vše velmi jednoduché - zkompilovaný překryv je potřeba vložit do /boot/overlays a mírně upravit /boot/config.txt.

Příklad souboru dts

Abych byl upřímný, nejsem si jistý, že je to napsané bez chyb, ale funguje to.

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

A další řádek v config.txt

dtoverlay=at25:spimaxfrequency=50000000

Popis připojení čipu k Raspberry Pi vynechám. Na jednu stranu nejsem odborník na elektroniku, na druhou stranu je tu i pro mě všechno banální: mikroobvod má pouze 8 nohou, z nichž potřebujeme uzemnění, napájení, SPI (CS, SI, SO, SCK ); úrovně jsou stejné jako u Raspberry Pi, není potřeba žádná další kabeláž - stačí připojit uvedených 6 pinů.

Formulace problému

Jako obvykle prochází problémové prohlášení několika iteracemi a zdá se mi, že je čas na další. Pojďme se tedy zastavit, dát dohromady to, co již bylo napsáno, a ujasnit si detaily, které zůstávají ve stínu.

Proto jsme se rozhodli, že protokol bude uložen ve SPI NOR Flash.

Co je NOR Flash pro ty, kteří nevědí?

Jedná se o energeticky nezávislou paměť, se kterou můžete provádět tři operace:

1. Čtení:
   Nejběžnější čtení: přeneseme adresu a přečteme tolik bajtů, kolik potřebujeme;
2. Záznam:
   Zápis do NOR flash vypadá jako běžný, ale má jednu zvláštnost: změnit lze pouze 1 na 0, ale ne naopak. Pokud bychom například měli v paměťové buňce 0x55, tak po zapsání 0x0f do ní již bude uloženo 0x05 (viz tabulka níže);
3. Vymazat:
   Samozřejmě musíme umět opačnou operaci – změnit 0 na 1, přesně k tomu slouží operace mazání. Na rozdíl od prvních dvou neoperuje s byty, ale s bloky (minimální výmazový blok ve zvoleném čipu je 4 kb). Erase zničí celý blok a je to jediný způsob, jak změnit 0 na 1. Proto při práci s pamětí flash často musíte zarovnat datové struktury na hranici bloku mazání.
   Záznam v NOR Flash:

Binární data

Byl
01010101

Zaznamenáno
00001111

Stal se
00000101

Samotný protokol představuje sekvenci záznamů různé délky. Typická délka záznamu je asi 30 bajtů (ačkoli se někdy vyskytují záznamy o délce několika kilobajtů). V tomto případě s nimi pracujeme jednoduše jako se sadou bajtů, ale v případě zájmu se uvnitř záznamů používá CBOR

Kromě protokolu musíme uložit některé informace o „nastavení“, aktualizované i neaktualizované: určité ID zařízení, kalibrace senzoru, příznak „zařízení je dočasně zakázáno“ atd.
Tyto informace jsou sadou záznamů párů klíč–hodnota, které jsou také uloženy v CBOR. Těchto informací nemáme mnoho (maximálně několik kilobajtů) a aktualizujeme je zřídka.
V následujícím budeme tomu říkat kontext.

Pokud si pamatujeme, kde tento článek začal, je velmi důležité zajistit spolehlivé úložiště dat a pokud možno nepřetržitý provoz i v případě selhání hardwaru/poškození dat.

Jaké zdroje problémů lze považovat?

• Vypněte během operací zápisu/mazání. Toto je z kategorie „neexistuje žádný trik proti páčidlu“.
  Informace od diskuse na stackexchange: když je napájení při práci s flashem vypnuto, mazání (nastaveno na 1) i zápis (nastaveno na 0) vede k nedefinovanému chování: data lze zapisovat, částečně zapisovat (řekněme, přenesli jsme 10 bajtů/80 bitů , ale zatím nelze zapsat pouze 45 bitů), je také možné, že některé bity budou v „mezilehlém“ stavu (čtení může produkovat 0 i 1);
• Chyby v samotné flash paměti.
  BER, i když je velmi nízká, nemůže být rovna nule;
• Chyby autobusu
  Data přenášená přes SPI nejsou nijak chráněna, může docházet k chybám jednotlivých bitů i chybám synchronizace - ztráta nebo vkládání bitů (což vede k masivnímu zkreslení dat);
• Jiné chyby/závady
  Chyby v kódu, závady Raspberry, rušení mimozemšťanů...

Formuloval jsem požadavky, jejichž splnění je dle mého názoru nezbytné pro zajištění spolehlivosti:

• záznamy musí jít do flash paměti okamžitě, nebere se v úvahu zpožděný zápis; - pokud dojde k chybě, musí být detekována a zpracována co nejdříve; - systém se musí pokud možno zotavit z chyb.
  (příklad ze života „jak by to nemělo být“, se kterým se myslím setkal každý: po nouzovém restartu je souborový systém „rozbitý“ a operační systém nenaběhne)

Nápady, přístupy, úvahy

Když jsem o tomto problému začal přemýšlet, hlavou mi problesklo mnoho nápadů, například:

• používat kompresi dat;
• používejte chytré datové struktury, například ukládejte hlavičky záznamů odděleně od záznamů samotných, takže pokud je v některém záznamu chyba, můžete bez problémů přečíst zbytek;
• použijte bitová pole k ovládání dokončení záznamu při vypnutí napájení;
• ukládat kontrolní součty pro všechno;
• použijte nějaký typ kódování odolného proti hluku.

Některé z těchto nápadů byly použity, zatímco jiné bylo rozhodnuto opustit. Jdeme popořadě.

Komprese dat

Samotné události, které zaznamenáváme v deníku, jsou dosti podobné a opakovatelné („hození 5 rublové mince“, „stisknutí tlačítka pro rozdávání“, ...). Komprese by tedy měla být docela účinná.

Kompresní režie je zanedbatelná (náš procesor je poměrně výkonný, i první Pi měl jedno jádro s frekvencí 700 MHz, současné modely mají několik jader s frekvencí přes gigahertz), směnný kurz s úložištěm je nízký (několik megabajtů za sekundu), velikost záznamů je malá. Obecně platí, že pokud má komprese vliv na výkon, bude to pouze pozitivní. (naprosto nekritické, jen konstatuji). Navíc nemáme skutečný embedded, ale běžný Linux - implementace by tedy neměla vyžadovat velké úsilí (stačí pouze propojit knihovnu a používat z ní několik funkcí).

Část protokolu byla odebrána z funkčního zařízení (1.7 MB, 70 tisíc záznamů) a nejprve byla zkontrolována komprimovatelnost pomocí gzip, lz4, lzop, bzip2, xz, zstd dostupných v počítači.

• gzip, xz, zstd ukázaly podobné výsledky (40 kB).
  Překvapilo mě, že módní xz se zde projevilo na úrovni gzip nebo zstd;
• lzip s výchozím nastavením dával mírně horší výsledky;
• lz4 a lzop nevykázaly příliš dobré výsledky (150Kb);
• bzip2 ukázal překvapivě dobrý výsledek (18 kb).

Data jsou tedy komprimována velmi dobře.
Takže (pokud nenajdeme fatální nedostatky) dojde ke kompresi! Jednoduše proto, že se na jeden flash disk vejde více dat.

Zamysleme se nad nevýhodami.

První problém: už jsme se dohodli, že každá deska musí jít okamžitě flashnout. Archivátor obvykle shromažďuje data ze vstupního toku, dokud se nerozhodne, že je čas zapisovat o víkendu. Musíme okamžitě přijmout komprimovaný blok dat a uložit je do energeticky nezávislé paměti.

Vidím tři způsoby:

1. Komprimujte každý záznam pomocí slovníkové komprese namísto výše uvedených algoritmů.
   Je to zcela funkční varianta, ale nelíbí se mi. Aby byla zajištěna více či méně slušná úroveň komprese, musí být slovník „ušit na míru“ konkrétním datům, jakákoli změna povede ke katastrofálnímu poklesu úrovně komprese. Ano, problém lze vyřešit vytvořením nové verze slovníku, ale to je bolest hlavy - budeme muset uložit všechny verze slovníku; v každém záznamu budeme muset uvést, jakou verzí slovníku byl komprimován...
2. Komprimujte každý záznam pomocí „klasických“ algoritmů, ale nezávisle na ostatních.
   Uvažované kompresní algoritmy nejsou navrženy tak, aby pracovaly se záznamy této velikosti (desítky bajtů), kompresní poměr bude jednoznačně menší než 1 (to znamená zvýšení objemu dat místo komprese);
3. Proveďte FLUSH po každém záznamu.
   Mnoho kompresních knihoven podporuje FLUSH. Toto je příkaz (nebo parametr procedury komprese), po jehož přijetí archivátor vytvoří komprimovaný proud, který lze použít k obnovení vše nekomprimovaná data, která již byla přijata. Takový analog sync v souborových systémech popř commit v sql.
   Důležité je, že následné operace komprese budou moci využívat nashromážděný slovník a kompresní poměr neutrpí tolik jako v předchozí verzi.

Myslím, že je zřejmé, že jsem zvolil třetí možnost, pojďme se na to podívat podrobněji.

Nalezeno skvělý článek o FLUSH ve zlib.

Udělal jsem test kolena na základě článku, vzal jsem 70 tisíc záznamů protokolu ze skutečného zařízení s velikostí stránky 60 kb (k velikosti stránky se vrátíme později) obdržel:

Počáteční data
Komprese gzip -9 (bez FLUSH)
zlib s Z_PARTIAL_FLUSH
zlib s Z_SYNC_FLUSH

Objem, kB
1692
40
352
604

Na první pohled je cena za FLUSH přehnaně vysoká, ale ve skutečnosti nemáme moc na výběr - buď nekomprimovat vůbec, nebo komprimovat (a velmi efektivně) pomocí FLUSH. Nesmíme zapomenout, že máme 70 tisíc záznamů, redundance zavedená Z_PARTIAL_FLUSH je pouze 4-5 bajtů na záznam. A kompresní poměr vyšel téměř na 5:1, což je více než výborný výsledek.

Může to být překvapení, ale Z_SYNC_FLUSH je ve skutečnosti efektivnější způsob, jak provést FLUSH

Při použití Z_SYNC_FLUSH budou poslední 4 bajty každé položky vždy 0x00, 0x00, 0xff, 0xff. A pokud je známe, nemusíme je ukládat, takže konečná velikost je pouze 324 Kb.

Článek, na který jsem odkazoval, má vysvětlení:

Je připojen nový blok typu 0 s prázdným obsahem.

Blok typu 0 s prázdným obsahem se skládá z:

• záhlaví tříbitového bloku;
• 0 až 7 bitů rovných nule pro dosažení zarovnání bajtů;
• čtyřbajtová sekvence 00 00 FF FF.

Jak můžete snadno vidět, v posledním bloku před těmito 4 byty je od 3 do 10 nulových bitů. Praxe však ukázala, že ve skutečnosti existuje alespoň 10 nulových bitů.

Ukazuje se, že takto krátké bloky dat jsou obvykle (vždy?) kódovány pomocí bloku typu 1 (pevný blok), který nutně končí 7 nulovými bity, což dává celkem 10-17 garantovaných nulových bitů (a zbytek bude být nula s pravděpodobností asi 50%).

Takže na testovacích datech je ve 100 % případů jeden nulový bajt před 0x00, 0x00, 0xff, 0xff a ve více než třetině případů jsou dva nulové bajty (možná je fakt, že používám binární CBOR a při použití textového JSON by byly častější bloky typu 2 - dynamický blok, respektive bloky bez dalších nula bajtů před 0x00, 0x00, 0xff, 0xff).

Celkově je možné s využitím dostupných testovacích dat vejít do méně než 250 Kb komprimovaných dat.

Trochu více můžete ušetřit žonglováním s bity: prozatím ignorujeme přítomnost několika nulových bitů na konci bloku, několik bitů na začátku bloku se také nemění...
Ale pak jsem se rázně rozhodl přestat, jinak bych tímto tempem mohl skončit vývojem vlastního archivátoru.

Celkově z mých testovacích dat jsem dostal 3-4 bajty na zápis, kompresní poměr se ukázal být více než 6:1. Budu upřímný: takový výsledek jsem neočekával, podle mého názoru cokoliv lepšího než 2:1 je již výsledek, který ospravedlňuje použití komprese.

Všechno je v pořádku, ale zlib (deflate) je stále archaický, zasloužený a mírně zastaralý kompresní algoritmus. Už jen to, že se posledních 32Kb nekomprimovaného datového toku používá jako slovník, dnes vypadá divně (tedy pokud je nějaký datový blok velmi podobný tomu, co byl ve vstupním toku před 40Kb, tak se začne znovu archivovat, a nebude odkazovat na předchozí výskyt). V moderních moderních archivátorech se velikost slovníku často měří spíše v megabajtech než v kilobajtech.

Pokračujeme tedy v naší ministudii archivářů.

Dále jsme testovali bzip2 (nezapomeňte, že bez FLUSH ukazoval fantastický kompresní poměr téměř 100:1). Bohužel to s FLUSH fungovalo velmi špatně; velikost komprimovaných dat se ukázala být větší než nekomprimovaná data.

Moje domněnky o důvodech neúspěchu

Libbz2 nabízí pouze jednu možnost vyprázdnění, což vypadá, že vyčistí slovník (analogicky jako Z_FULL_FLUSH ve zlib), poté se o nějaké efektivní kompresi nemluví.

A poslední testovaný byl zstd. V závislosti na parametrech se komprimuje buď na úrovni gzip, ale mnohem rychleji, nebo lépe než gzip.

Bohužel, s FLUSH to nefungovalo příliš dobře: velikost komprimovaných dat byla asi 700 kb.

Я položil otázku na stránce github projektu jsem dostal odpověď, že byste měli počítat až s 10 bajty servisních dat pro každý blok komprimovaných dat, což se blíží získaným výsledkům; neexistuje způsob, jak dohnat deflaci.

Rozhodl jsem se zastavit v tomto bodě své experimenty s archivátory (připomenu, že xz, lzip, lzo, lz4 se neprojevily ani ve fázi testování bez FLUSH a o exotičtějších kompresních algoritmech jsem neuvažoval).

Vraťme se k problémům s archivací.

Druhý (jak se říká v pořadí, nikoli hodnotově) problém je v tom, že komprimovaná data tvoří jeden stream, ve kterém jsou neustále odkazy na předchozí sekce. Dojde-li tedy k poškození části komprimovaných dat, ztratíme nejen související blok nekomprimovaných dat, ale i všechna následující.

Existuje přístup k vyřešení tohoto problému:

1. Zabraňte výskytu problému – přidejte do komprimovaných dat redundanci, která vám umožní identifikovat a opravit chyby; o tom budeme mluvit později;
2. Minimalizujte následky, pokud se vyskytne problém
   Již dříve jsme řekli, že můžete komprimovat každý datový blok nezávisle a problém zmizí sám od sebe (poškození dat jednoho bloku povede ke ztrátě dat pouze pro tento blok). Toto je však extrémní případ, kdy bude komprese dat neúčinná. Opačný extrém: použít všechny 4 MB našeho čipu jako jeden archiv, což nám poskytne vynikající kompresi, ale katastrofální následky v případě poškození dat.
   Ano, z hlediska spolehlivosti je potřeba kompromis. Musíme si ale uvědomit, že vyvíjíme formát pro ukládání dat pro energeticky nezávislé paměti s extrémně nízkou BER a deklarovanou dobou ukládání dat 20 let.

Během experimentů jsem zjistil, že více či méně znatelné ztráty v úrovni komprese začínají na blocích komprimovaných dat o velikosti menší než 10 KB.
Již dříve bylo zmíněno, že používaná paměť je stránkována, nevidím důvod, proč by se neměla používat korespondence „jedna stránka – jeden blok komprimovaných dat“.

To znamená, že minimální rozumná velikost stránky je 16 Kb (s rezervou pro servisní informace). Tak malá velikost stránky však ukládá významná omezení maximální velikosti záznamu.

Přestože zatím neočekávám záznamy větší než několik kilobajtů v komprimované podobě, rozhodl jsem se použít 32Kb stránky (celkem 128 stránek na čip).

Shrnutí:

• Data ukládáme komprimovaná pomocí zlib (deflate);
• Pro každý záznam nastavíme Z_SYNC_FLUSH;
• U každého komprimovaného záznamu ořízneme koncové bajty (např. 0x00, 0x00, 0xff, 0xff); v záhlaví uvedeme, kolik bajtů jsme odřízli;
• Data ukládáme na 32Kb stránkách; uvnitř stránky je jediný proud komprimovaných dat; Na každé stránce začneme znovu komprimovat.

A než skončíme s kompresí, rád bych vás upozornil na skutečnost, že máme pouze několik bajtů komprimovaných dat na záznam, takže je nesmírně důležité nenafouknout servisní informace, každý bajt se zde počítá.

Ukládání datových záhlaví

Vzhledem k tomu, že máme záznamy proměnné délky, musíme nějak určit umístění/hranice záznamů.

Znám tři přístupy:

1. Všechny záznamy jsou uloženy v nepřetržitém proudu, nejprve je hlavička záznamu obsahující délku a poté záznam samotný.
   V tomto provedení mohou mít záhlaví i data proměnnou délku.
   V podstatě získáme jednoduše propojený seznam, který se používá neustále;
2. Záhlaví a samotné záznamy jsou uloženy v samostatných proudech.
   Použitím hlaviček konstantní délky zajistíme, že poškození jedné hlavičky neovlivní ostatní.
   Podobný přístup se používá například v mnoha souborových systémech;
3. Záznamy jsou ukládány v nepřetržitém proudu, hranice záznamu je určena určitou značkou (znak/sekvence znaků, která je v rámci datových bloků zakázána). Pokud je uvnitř záznamu značka, pak ji nahradíme nějakou sekvencí (escapujeme ji).
   Podobný přístup je použit například v protokolu PPP.

Budu ilustrovat.

Možnost 1:

Zde je vše velmi jednoduché: když známe délku záznamu, můžeme vypočítat adresu další hlavičky. Pohybujeme se tedy mezi nadpisy, dokud nenarazíme na oblast vyplněnou 0xff (volná oblast) nebo na konec stránky.

Možnost 2:

Vzhledem k variabilní délce záznamu nemůžeme předem říci, kolik záznamů (a potažmo záhlaví) budeme na stránku potřebovat. Záhlaví a samotná data můžete rozložit na různé stránky, ale já preferuji jiný přístup: záhlaví i data umístíme na jednu stránku, ale záhlaví (stejné velikosti) pocházejí ze začátku stránky a data (proměnné délky) pocházejí z konce. Jakmile se „sejdou“ (není dostatek volného místa pro nový záznam), považujeme tuto stránku za dokončenou.

Možnost 3:

Do hlavičky není potřeba ukládat délku ani další informace o umístění dat, stačí značky označující hranice záznamů. Při zápisu/čtení však musí být data zpracována.
Jako fix bych použil 0xff (který po smazání vyplní stránku), takže s volnou plochou se rozhodně nebude zacházet jako s daty.

Srovnávací tabulka:

Možnost 1
Možnost 2
Možnost 3

Tolerance chyb
-
+
+

Kompaktnost
+
-
+

Složitost implementace
*
**
**

Možnost 1 má fatální chybu: pokud je některá z hlaviček poškozena, je zničen celý následující řetězec. Zbývající možnosti umožňují obnovit některá data i v případě masivního poškození.
Zde je ale vhodné připomenout, že jsme se rozhodli data ukládat v komprimované podobě, a tak po „přerušeném“ záznamu ztratíme všechna data na stránce, takže i když je v tabulce mínus, ne vzít to v úvahu.

Kompaktnost:

• v první volbě potřebujeme do hlavičky uložit pouze délku, pokud použijeme celá čísla s proměnnou délkou, pak si ve většině případů vystačíme s jedním bajtem;
• ve druhé možnosti musíme uložit počáteční adresu a délku; záznam musí mít konstantní velikost, odhaduji 4 bajty na záznam (dva bajty pro offset a dva bajty pro délku);
• třetí možnost potřebuje pouze jeden znak pro označení začátku záznamu, plus samotný záznam se zvýší o 1-2% kvůli stínění. Obecně platí, že přibližně stejná jako u první možnosti.

Zpočátku jsem považoval druhou možnost za hlavní (a dokonce jsem napsal implementaci). Opustil jsem to, až když jsem se konečně rozhodl použít kompresi.

Možná někdy ještě využiji podobnou možnost. Pokud mám například řešit ukládání dat pro loď cestující mezi Zemí a Marsem, budou zde zcela jiné požadavky na spolehlivost, kosmické záření, ...

Pokud jde o třetí možnost: dal jsem tomu dvě hvězdy za obtížnost implementace jednoduše proto, že se mi nebaví motat se kolem stínění, měnit délku v procesu atd. Ano, možná jsem zaujatý, ale budu muset napsat kód – proč se nutit dělat něco, co se vám nelíbí.

Shrnutí: Volbu uložení ve formě řetězců „záhlaví s délkou - data proměnné délky“ volíme z důvodu efektivity a snadnosti implementace.

Použití bitových polí ke sledování úspěšnosti operací zápisu

Už si nevzpomínám, kde mě to napadlo, ale vypadá to asi takto:
Pro každý záznam alokujeme několik bitů pro uložení příznaků.
Jak jsme řekli dříve, po vymazání jsou všechny bity vyplněny 1s a můžeme změnit 1 na 0, ale ne naopak. Takže pro „příznak není nastaven“ použijeme 1, pro „příznak je nastaven“ použijeme 0.

Vložení záznamu s proměnnou délkou do flash může vypadat následovně:

1. Nastavte příznak „délka nahrávání začala“;
2. Zaznamenejte délku;
3. Nastavte příznak „záznam dat byl zahájen“;
4. Zaznamenáváme data;
5. Nastavte příznak „záznam skončil“.

Kromě toho budeme mít příznak „došlo k chybě“, celkem 4 bitové příznaky.

V tomto případě máme dva stabilní stavy „1111“ – nahrávání nezačalo a „1000“ – nahrávání bylo úspěšné; v případě nečekaného přerušení procesu záznamu obdržíme mezistavy, které pak můžeme detekovat a zpracovat.

Přístup je zajímavý, ale chrání pouze před náhlými výpadky proudu a podobnými poruchami, což je samozřejmě důležité, ale není to zdaleka jediný (nebo dokonce hlavní) důvod možných poruch.

Shrnutí: Pojďme dál hledat dobré řešení.

Kontrolní součty

Kontrolní součty také umožňují ujistit se (s rozumnou pravděpodobností), že čteme přesně to, co mělo být napsáno. A na rozdíl od bitových polí diskutovaných výše vždy fungují.

Pokud vezmeme v úvahu seznam potenciálních zdrojů problémů, které jsme probrali výše, pak je kontrolní součet schopen rozpoznat chybu bez ohledu na její původ (snad kromě škodlivých mimozemšťanů - ti mohou také zfalšovat kontrolní součet).

Pokud je tedy naším cílem ověřit, zda jsou data neporušená, kontrolní součty jsou skvělý nápad.

Volba algoritmu pro výpočet kontrolního součtu nevyvolala žádné otázky - CRC. Na jedné straně matematické vlastnosti umožňují 100% zachytit určité typy chyb, na druhé straně na náhodných datech tento algoritmus obvykle ukazuje pravděpodobnost kolizí ne o moc větší, než je teoretická mez . Možná to není nejrychlejší algoritmus, ani to není vždy minimum z hlediska počtu kolizí, ale má velmi důležitou kvalitu: v testech, se kterými jsem se setkal, nebyly žádné vzory, ve kterých by jednoznačně selhal. Stabilita je v tomto případě hlavní kvalita.

Příklad objemové studie: Část 1, Část 2 (odkazy na narod.ru, omlouvám se).

Úkol výběru kontrolního součtu však není úplný, CRC je celá rodina kontrolních součtů. Musíte se rozhodnout o délce a poté zvolit polynom.

Volba délky kontrolního součtu není tak jednoduchá otázka, jak se na první pohled zdá.

Dovolte mi ilustrovat:
Mějme pravděpodobnost chyby v každém bajtu a ideální kontrolní součet, spočítejme si průměrný počet chyb na milion záznamů:

Data, byte
Kontrolní součet, bajt
Neodhalené chyby
Falešná detekce chyb
Celkem falešně pozitivní

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

Zdálo by se, že vše je jednoduché - v závislosti na délce chráněných dat zvolte délku kontrolního součtu s minimem nesprávných kladných hodnot - a trik je v pytli.

S krátkými kontrolními součty však nastává problém: jsou sice dobré v odhalování jednotlivých bitových chyb, ale dokážou s poměrně vysokou pravděpodobností přijmout jako správná zcela náhodná data. Popisoval už článek o Habrém problém v reálném životě.

Proto, aby byla náhodná shoda kontrolního součtu téměř nemožná, musíte použít kontrolní součty o délce 32 bitů nebo delší. (pro délky větší než 64 bitů se obvykle používají kryptografické hašovací funkce).

Navzdory tomu, že jsem již dříve psal, že musíme všemi prostředky šetřit místo, budeme stále používat 32bitový kontrolní součet (16 bitů nestačí, pravděpodobnost kolize je více než 0.01 %; a 24 bitů, protože řekněme, nejsou ani tady, ani tam) .

Zde může být námitka: ušetřili jsme každý bajt při výběru komprese, abychom nyní dali 4 bajty najednou? Nebylo by lepší nekomprimovat ani nepřidávat kontrolní součet? Samozřejmě ne, žádná komprese neznamená to, že nepotřebujeme kontrolu integrity.

Při výběru polynomu nebudeme znovu vymýšlet kolo, ale vezmeme nyní populární CRC-32C.
Tento kód detekuje 6bitové chyby na paketech do 22 bajtů (u nás možná nejběžnější případ), 4bitové chyby na paketech do 655 bajtů (pro nás také běžný případ), 2 nebo libovolný lichý počet bitových chyb na paketech jakékoli přiměřené délky.

Pokud někoho zajímají podrobnosti

Článek na Wikipedii o CRC.

Parametry kódu crc-32c na Web společnosti Koopman — možná přední specialista na CRC na planetě.

В jeho článek je další zajímavý kód, který poskytuje o něco lepší parametry pro délky paketů, které jsou pro nás relevantní, ale rozdíl jsem nepovažoval za významný a byl jsem dostatečně kompetentní vybrat vlastní kód místo standardního a dobře prozkoumaného.

Protože jsou naše data komprimovaná, vyvstává otázka: měli bychom vypočítat kontrolní součet komprimovaných nebo nekomprimovaných dat?

Argumenty ve prospěch výpočtu kontrolního součtu nekomprimovaných dat:

• Bezpečnost datových úložišť musíme v konečném důsledku zkontrolovat – kontrolujeme ji tedy přímo (zároveň budou zkontrolovány případné chyby při provádění komprese/dekomprese, poškození způsobená rozbitou pamětí atd.);
• Algoritmus deflate v zlib má poměrně vyspělou implementaci a by neměl padat s „křivými“ vstupními daty, navíc je často schopen samostatně detekovat chyby ve vstupním toku, čímž snižuje celkovou pravděpodobnost neodhalení chyby (proveden test s invertováním jediného bitu v krátkém záznamu, zlib detekoval chybu asi ve třetině případů).

Argumenty proti výpočtu kontrolního součtu nekomprimovaných dat:

• CRC je „šité na míru“ speciálně pro pár bitových chyb, které jsou charakteristické pro flash paměti (bitová chyba v komprimovaném toku může způsobit masivní změnu výstupního toku, na kterém čistě teoreticky můžeme „chytit“ kolizi);
• Moc se mi nelíbí myšlenka předávání potenciálně poškozených dat do dekompresoru, kdo víjak bude reagovat.

V tomto projektu jsem se rozhodl odchýlit od obecně přijímané praxe ukládání kontrolního součtu nekomprimovaných dat.

Shrnutí: Používáme CRC-32C, kontrolní součet vypočítáme z dat v podobě, v jaké jsou zapsány na flash (po kompresi).

Redundance

Použití redundantního kódování samozřejmě neeliminuje ztrátu dat, může však výrazně (často o mnoho řádů) snížit pravděpodobnost nevratné ztráty dat.

K opravě chyb můžeme použít různé typy redundance.
Hammingovy kódy mohou opravit jednotlivé bitové chyby, kódy znaků Reed-Solomon, více kopií dat v kombinaci s kontrolními součty nebo kódování jako RAID-6 mohou pomoci obnovit data i v případě masivního poškození.
Zpočátku jsem se zavázal k širokému používání kódování odolného proti chybám, ale pak jsem si uvědomil, že nejprve musíme mít představu o tom, před jakými chybami se chceme chránit, a pak zvolit kódování.

Již dříve jsme řekli, že chyby je třeba zachytit co nejrychleji. V jakých bodech se můžeme setkat s chybami?

1. Nedokončené nahrávání (z nějakého důvodu bylo v době nahrávání vypnuto napájení, Raspberry zamrzl, ...)
   Bohužel v případě takové chyby nezbývá než neplatné záznamy ignorovat a považovat data za ztracená;
2. Chyby zápisu (z nějakého důvodu to, co bylo zapsáno do paměti flash, nebylo to, co bylo zapsáno)
   Takové chyby můžeme okamžitě odhalit, pokud provedeme testovací čtení ihned po záznamu;
3. Zkreslení dat v paměti během ukládání;
4. Chyby při čtení
   Pro opravu, pokud kontrolní součet nesouhlasí, stačí čtení několikrát zopakovat.

To znamená, že pouze chyby třetího typu (spontánní poškození dat během ukládání) nelze opravit bez kódování odolného proti chybám. Zdá se, že takové chyby jsou stále velmi nepravděpodobné.

Shrnutí: bylo rozhodnuto opustit redundantní kódování, ale pokud provoz ukáže chybu tohoto rozhodnutí, vraťte se k posouzení problému (s již nashromážděnými statistikami o poruchách, které umožní zvolit optimální typ kódování).

ostatní

Formát článku nám samozřejmě neumožňuje ospravedlnit každý kousek formátu (a moje síly už došly), takže stručně přejdu k některým bodům, o kterých jsme se dříve nedotkli.

• Bylo rozhodnuto učinit všechny stránky „rovnými“
  To znamená, že nebudou existovat žádné speciální stránky s metadaty, samostatnými vlákny atd., ale místo toho jediné vlákno, které postupně přepisuje všechny stránky.
  To zajišťuje rovnoměrné opotřebení stránek, žádný jediný bod selhání, a to se mi líbí;
• Je nutné poskytnout verzi formátu.
  Formát bez čísla verze v záhlaví je zlý!
  Do záhlaví stránky stačí přidat pole s určitým magickým číslem (podpis), které bude udávat verzi použitého formátu (Nemyslím si, že v praxi jich bude ani tucet);
• Pro záznamy (kterých je hodně) použijte hlavičku s proměnnou délkou a snažte se, aby byla ve většině případů dlouhá 1 bajt;
• Chcete-li zakódovat délku záhlaví a délku oříznuté části komprimovaného záznamu, použijte binární kódy s proměnnou délkou.

Hodně pomohl online generátor Huffmanovy kódy. Během několika minut jsme byli schopni vybrat požadované kódy proměnné délky.

Popis formátu ukládání dat

Pořadí bajtů

Pole větší než jeden bajt jsou uložena ve formátu big-endian (síťové pořadí bajtů), to znamená, že 0x1234 je zapsáno jako 0x12, 0x34.

Stránkování

Veškerá flash paměť je rozdělena na stránky stejné velikosti.

Výchozí velikost stránky je 32 Kb, ale ne více než 1/4 celkové velikosti paměťového čipu (pro čip 4 MB se získá 128 stránek).

Každá stránka ukládá data nezávisle na ostatních (to znamená, že data na jedné stránce neodkazují na data na jiné stránce).

Všechny stránky jsou číslovány v přirozeném pořadí (ve vzestupném pořadí adres), počínaje číslem 0 (stránka nula začíná na adrese 0, první stránka začíná na 32 Kb, druhá stránka začíná na 64 Kb atd.)

Paměťový čip se používá jako cyklická vyrovnávací paměť (ring buffer), to znamená, že nejprve se zapisuje na stránku číslo 0, poté číslo 1, ..., když zaplníme poslední stránku, začne nový cyklus a nahrávání pokračuje od stránky nula .

Uvnitř stránky

Na začátku stránky je uloženo 4bajtové záhlaví stránky, poté kontrolní součet záhlaví (CRC-32C), poté jsou záznamy uloženy ve formátu „záhlaví, data, kontrolní součet“.

Titulek stránky (na obrázku špinavě zelený) se skládá z:

• dvoubajtové pole magického čísla (také označení verze formátu)
  pro aktuální verzi formátu se počítá jako 0xed00 ⊕ номер страницы;
• dvoubajtový čítač „Verze stránky“ (číslo cyklu přepisování paměti).

Záznamy na stránce jsou uloženy v komprimované podobě (používá se deflační algoritmus). Všechny záznamy na jedné stránce jsou komprimovány v jednom vláknu (používá se běžný slovník) a na každé nové stránce začíná komprese znovu. To znamená, že pro dekomprimaci jakéhokoli záznamu jsou vyžadovány všechny předchozí záznamy z této stránky (a pouze tato).

Každý záznam bude komprimován příznakem Z_SYNC_FLUSH a na konci komprimovaného toku budou 4 bajty 0x00, 0x00, 0xff, 0xff, před kterými může být jeden nebo dva další nulové bajty.
Tuto sekvenci (4, 5 nebo 6 bajtů dlouhou) při zápisu do flash paměti zahazujeme.

Záhlaví záznamu je 1, 2 nebo 3 bajty a ukládá:

• jeden bit (T) udávající typ záznamu: 0 - kontext, 1 - log;
• pole s proměnnou délkou (S) od 1 do 7 bitů, definující délku záhlaví a „ocasu“, které musí být přidány k záznamu pro dekompresi;
• délka záznamu (L).

Tabulka hodnot S:

S
Délka záhlaví, bajty
Zahozeno při zápisu, 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)

Snažil jsem se ilustrovat, nevím, jak jasně to dopadlo:

Žlutá zde označuje pole T, bílá pole S, zelená L (délka komprimovaných dat v bajtech), modrá komprimovaná data, červená konečné bajty komprimovaných dat, která se nezapisují do paměti flash.

Do jednoho bytu tak můžeme zapisovat hlavičky záznamů nejběžnější délky (až 63+5 bytů v komprimované podobě).

Po každém záznamu je uložen kontrolní součet CRC-32C, ve kterém je jako počáteční hodnota (init) použita převrácená hodnota předchozího kontrolního součtu.

CRC má vlastnost „trvání“, funguje následující vzorec (plus nebo mínus bitová inverze v procesu): .
To znamená, že ve skutečnosti vypočítáme CRC všech předchozích bajtů záhlaví a dat na této stránce.

Přímo za kontrolním součtem je záhlaví dalšího záznamu.

Hlavička je navržena tak, že její první bajt je vždy jiný než 0x00 a 0xff (pokud místo prvního bajtu hlavičky narazíme na 0xff, pak to znamená, že se jedná o nevyužitou oblast; 0x00 signalizuje chybu).

Příklad algoritmů

Čtení z paměti Flash

Jakékoli čtení přichází s kontrolou kontrolního součtu.
Pokud se kontrolní součet neshoduje, čtení se několikrát opakuje v naději, že přečtete správná data.

(to dává smysl, Linux neukládá do mezipaměti čtení z NOR Flash, testováno)

Zápis do flash paměti

Data zaznamenáváme.
Pojďme si je přečíst.

Pokud se přečtená data neshodují se zapsanými, vyplníme oblast nulami a signalizujeme chybu.

Příprava nového mikroobvodu k provozu

Pro inicializaci se na první (nebo spíše nulovou) stránku zapíše hlavička s verzí 1.
Poté se na tuto stránku zapíše počáteční kontext (obsahuje UUID stroje a výchozí nastavení).

To je vše, flash paměť je připravena k použití.

Načítání stroje

Při načítání se přečte prvních 8 bajtů každé stránky (záhlaví + CRC), stránky s neznámým magickým číslem nebo nesprávným CRC jsou ignorovány.
Ze „správných“ stránek se vyberou stránky s maximální verzí a z nich se převezme stránka s nejvyšším číslem.
Načte se první záznam, zkontroluje se správnost CRC a přítomnost příznaku „kontext“. Pokud je vše v pořádku, je tato stránka považována za aktuální. Pokud ne, vrátíme se zpět k předchozí, dokud nenajdeme „živou“ stránku.
a na nalezené stránce čteme všechny záznamy, ty, které používáme s příznakem „kontext“.
Uložte slovník zlib (bude potřeba pro přidání na tuto stránku).

To je vše, stahování je dokončeno, kontext je obnoven, můžete pracovat.

Přidání položky deníku

Záznam zkomprimujeme pomocí správného slovníku s uvedením Z_SYNC_FLUSH a uvidíme, zda se zkomprimovaný záznam vejde na aktuální stránku.
Pokud se nevejde (nebo byly na stránce chyby CRC), založte novou stránku (viz níže).
Zapisujeme záznam a CRC. Pokud dojde k chybě, začněte novou stránku.

Nová stránka

Volnou stránku vybereme s minimálním počtem (za volnou stránku považujeme stránku s nesprávným kontrolním součtem v záhlaví nebo s verzí menší než aktuální). Pokud žádné takové stránky neexistují, vyberte stránku s minimálním počtem z těch, které mají verzi rovnou té aktuální.
Vybranou stránku vymažeme. Obsah zkontrolujeme pomocí 0xff. Pokud je něco špatně, vezměte si další bezplatnou stránku atd.
Na vymazanou stránku napíšeme hlavičku, první záznam je aktuální stav kontextu, další je nezapsaný záznam logu (pokud existuje).

Použitelnost formátu

Dle mého názoru se ukázal jako dobrý formát pro ukládání jakýchkoliv více či méně komprimovatelných informačních toků (prostý text, JSON, MessagePack, CBOR, případně protobuf) v NOR Flash.

Formát je samozřejmě „šitý na míru“ pro SLC NOR Flash.

Nemělo by se používat s médii s vysokou BER, jako je NAND nebo MLC NOR (je taková paměť vůbec k dispozici na prodej? Viděl jsem ji zmíněnou pouze v pracích o opravných kódech).

Navíc by se neměl používat se zařízeními, která mají vlastní FTL: USB flash, SD, MicroSD atd (pro takovou paměť jsem vytvořil formát s velikostí stránky 512 bajtů, podpisem na začátku každé stránky a jedinečnými čísly záznamů - někdy bylo možné obnovit všechna data z „pokazeného“ flash disku jednoduchým sekvenčním čtením).

V závislosti na úlohách lze formát použít beze změn na flash discích od 128Kbit (16Kb) do 1Gbit (128MB). Pokud chcete, můžete jej použít na větší čipy, ale pravděpodobně budete muset upravit velikost stránky (Tady však již vyvstává otázka ekonomické proveditelnosti, cena za velkoobjemový NOR Flash není povzbudivá).

Pokud někoho formát zaujme a bude ho chtít použít v otevřeném projektu, napište, já se pokusím najít čas, vypilovat kód a dát to na github.

Závěr

Jak vidíte, formát se nakonec ukázal jako jednoduchý a dokonce nudné.

Je těžké reflektovat vývoj mého pohledu v článku, ale věřte mi: původně jsem chtěl vytvořit něco sofistikovaného, ​​nezničitelného, ​​schopného přežít i jaderný výbuch v těsné blízkosti. Nicméně rozum (doufám) stále zvítězil a postupně se priority posunuly směrem k jednoduchosti a kompaktnosti.

Je možné, že jsem se mýlil? Ano jistě. Může se například ukázat, že jsme zakoupili dávku nekvalitních mikroobvodů. Nebo z nějakého jiného důvodu zařízení nesplňuje očekávání spolehlivosti.

Mám na to plán? Myslím, že po přečtení článku nepochybujete, že nějaký plán existuje. A dokonce ne sám.

O něco vážnější je, že formát byl vyvinut jako pracovní možnost i jako „zkušební balón“.

V tuto chvíli vše na stole funguje dobře, doslova druhý den bude řešení nasazeno (přibližně) na stovkách zařízení se podívejme, co se stane v „bojovém“ provozu (naštěstí doufám, že vám formát umožňuje spolehlivě detekovat selhání; takže můžete sbírat úplné statistiky). Za pár měsíců bude možné dělat závěry (a když budete mít smůlu, tak i dříve).

Pokud se na základě výsledků používání objeví vážné problémy a budou zapotřebí vylepšení, pak o tom určitě napíšu.

Literatura

Nechtěl jsem dělat dlouhý nudný seznam použitých děl, Google má přece každý.

Zde jsem se rozhodl zanechat seznam nálezů, které se mi zdály obzvlášť zajímavé, ale postupně migrovaly přímo do textu článku a na seznamu zůstala jedna položka:

1. Užitečnost infgen od autora zlib. Dokáže jasně zobrazit obsah archivů deflate/zlib/gzip. Pokud musíte řešit vnitřní strukturu formátu deflate (nebo gzip), vřele doporučuji.

Zdroj: www.habr.com