forhistorie

Der er automater af vores eget design. Inde i Raspberry Pi og nogle ledninger på et separat bord. En møntmodtager, en seddelmodtager, en bankterminal er tilsluttet... Alt styres af et selvskrevet program. Hele arbejdshistorikken skrives til en log på et flashdrev (MicroSD), som derefter overføres via internettet (ved hjælp af et USB-modem) til serveren, hvor det gemmes i en database. Salgsinformation indlæses i 1c, der er også en simpel webgrænseflade til overvågning mv.

Det vil sige, at journalen er afgørende - til regnskab (omsætning, salg osv.), overvågning (alle former for fejl og andre force majeure-forhold); Dette, kan man sige, er alle de oplysninger, vi har om denne maskine.

problem

Flash-drev viser sig at være meget upålidelige enheder. De fejler med misundelsesværdig regelmæssighed. Dette fører til både maskinens nedetid og (hvis loggen af ​​en eller anden grund ikke kunne overføres online) til tab af data.

Dette er ikke den første oplevelse med at bruge flash-drev, før dette var der et andet projekt med mere end hundrede enheder, hvor magasinet blev gemt på USB-flashdrev, der var også problemer med pålideligheden, til tider antallet af dem der fejlede i en måned var i snesevis. Vi prøvede forskellige flashdrev, herunder mærkevarer med SLC-hukommelse, og nogle modeller er mere pålidelige end andre, men udskiftning af flashdrev løste ikke problemet radikalt.

Advarsel! Langlæst! Hvis du ikke er interesseret i "hvorfor", men kun i "hvordan", kan du gå direkte Til sidst artikel.

beslutning

Det første, der kommer til at tænke på, er: forlad MicroSD, installer for eksempel en SSD, og ​​start fra den. Teoretisk muligt, sandsynligvis, men relativt dyrt og ikke så pålideligt (en USB-SATA-adapter er tilføjet; fejlstatistikker for budget-SSD'er er heller ikke opmuntrende).

USB HDD ligner heller ikke en særlig attraktiv løsning.

Derfor kom vi til denne mulighed: forlad opstart fra MicroSD, men brug dem i skrivebeskyttet tilstand, og gem operationsloggen (og anden information unik for et bestemt stykke hardware - serienummer, sensorkalibreringer osv.) et andet sted .

Emnet med skrivebeskyttet FS til hindbær er allerede blevet undersøgt inde og ude, jeg vil ikke dvæle ved implementeringsdetaljer i denne artikel (men hvis der er interesse, skriver jeg måske en miniartikel om dette emne). Det eneste punkt, jeg gerne vil bemærke, er, at både fra personlig erfaring og fra anmeldelser af dem, der allerede har implementeret det, er der en gevinst i pålidelighed. Ja, det er umuligt helt at slippe af med sammenbrud, men det er meget muligt at reducere deres hyppighed betydeligt. Og kortene er ved at blive samlet, hvilket gør udskiftningen meget lettere for servicepersonalet.

Hardwaren del

Der var ingen særlig tvivl om valget af hukommelsestype - NOR Flash.
Argumenter:

• simpel forbindelse (oftest SPI-bussen, som du allerede har erfaring med at bruge, så der er ikke forudset nogen hardwareproblemer);
• latterlig pris;
• standard driftsprotokol (implementeringen er allerede i Linux-kernen, hvis du ønsker det, kan du tage en tredjepart, som også er til stede, eller endda skrive din egen, heldigvis er alt enkelt);
• pålidelighed og ressource:
  fra et typisk datablad: data lagres i 20 år, 100000 slettecyklusser for hver blok;
  fra tredjepartskilder: ekstremt lav BER, postulerer ikke behov for fejlkorrektionskoder (nogle værker betragter ECC som NOR, men normalt betyder de stadig MLC NOR; dette sker også).

Lad os estimere kravene til volumen og ressourcer.

Jeg vil gerne have, at dataene er garanteret gemt i flere dage. Dette er nødvendigt, så salgshistorikken ikke går tabt i tilfælde af kommunikationsproblemer. Vi vil fokusere på 5 dage i denne periode (selv under hensyntagen til weekender og helligdage) problemet kan løses.

Vi indsamler i øjeblikket omkring 100 kb logfiler om dagen (3-4 tusinde poster), men gradvist vokser dette tal - detaljerne øges, nye begivenheder tilføjes. Plus, nogle gange er der bursts (nogle sensorer begynder for eksempel at spamme med falske positiver). Vi vil beregne for 10 tusinde poster 100 bytes hver - megabyte pr. dag.

I alt kommer der 5MB rene (velkomprimerede) data ud. Mere til dem (groft estimat) 1 MB servicedata.

Det vil sige, at vi har brug for en 8MB chip, hvis vi ikke bruger komprimering, eller 4MB, hvis vi bruger den. Ganske realistiske tal for denne type hukommelse.

Hvad angår ressourcen: Hvis vi planlægger, at hele hukommelsen ikke skal omskrives mere end én gang hver 5. dag, så får vi over 10 års tjeneste mindre end tusinde omskrivningscyklusser.
Lad mig minde dig om, at producenten lover hundrede tusinde.

Lidt om NOR vs NAND

I dag er NAND-hukommelse selvfølgelig meget mere populær, men jeg ville ikke bruge den til dette projekt: NAND kræver, i modsætning til NOR, nødvendigvis brugen af ​​fejlkorrektionskoder, en tabel med dårlige blokke osv., og også benene på NAND-chips normalt meget mere.

Ulemperne ved NOR omfatter:

• lille volumen (og følgelig høj pris pr. megabyte);
• lav kommunikationshastighed (hovedsageligt på grund af det faktum, at der bruges en seriel grænseflade, normalt SPI eller I2C);
• langsom sletning (afhængigt af blokstørrelsen tager det fra en brøkdel af et sekund til flere sekunder).

Det ser ud til, at der ikke er noget kritisk for os, så vi fortsætter.

Hvis detaljerne er interessante, er mikrokredsløbet valgt at25df321a (men dette er ligegyldigt, der er mange analoger på markedet, der er kompatible i pinout og kommandosystem; selvom vi ønsker at installere et mikrokredsløb fra en anden producent og/eller en anden størrelse, vil alt fungere uden at ændre kode).

Jeg bruger driveren indbygget i Linux-kernen; på Raspberry, takket være understøttelse af enhedstræ-overlay, er alt meget enkelt - du skal sætte det kompilerede overlay i /boot/overlays og ændre /boot/config.txt lidt.

Eksempel på dts-fil

For at være ærlig er jeg ikke sikker på, at det er skrevet uden fejl, men det virker.

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

Og endnu en linje i config.txt

dtoverlay=at25:spimaxfrequency=50000000

Jeg vil udelade beskrivelsen af ​​at forbinde chippen til Raspberry Pi. På den ene side er jeg ikke ekspert i elektronik, på den anden side er alt her banalt selv for mig: mikrokredsløbet har kun 8 ben, hvoraf vi skal bruge jord, strøm, SPI (CS, SI, SO, SCK ); niveauerne er de samme som for Raspberry Pi, der kræves ingen yderligere ledninger - bare tilslut de angivne 6 ben.

Formulering af problemet

Som sædvanlig gennemgår problemformuleringen flere iterationer, og det forekommer mig, at det er tid til den næste. Så lad os stoppe op, sammensætte det, der allerede er skrevet, og afklare de detaljer, der forbliver i skyggen.

Så vi har besluttet, at loggen vil blive gemt i SPI NOR Flash.

Hvad er NOR Flash for dem, der ikke ved det?

Dette er ikke-flygtig hukommelse, hvormed du kan udføre tre operationer:

1. Læsning:
   Den mest almindelige læsning: vi sender adressen og læser så mange bytes, som vi har brug for;
2. rekord:
   At skrive til NOR flash ligner en almindelig, men det har en særegenhed: du kan kun ændre 1 til 0, men ikke omvendt. For eksempel, hvis vi havde 0x55 i en hukommelsescelle, vil 0x0 allerede være gemt der efter at have skrevet 0x05f til den (se tabellen lige nedenfor);
3. Slette:
   Selvfølgelig skal vi være i stand til at udføre den modsatte operation - skift 0 til 1, det er præcis, hvad sletteoperationen er til. I modsætning til de to første fungerer den ikke med bytes, men med blokke (minimums sletteblok i den valgte chip er 4kb). Sletning ødelægger hele blokken og er den eneste måde at ændre 0 til 1. Når du arbejder med flashhukommelse, skal du derfor ofte justere datastrukturer til sletteblokgrænsen.
   Optagelse i NOR Flash:

Binære data

det var
01010101

Optaget
00001111

Er blevet
00000101

Selve loggen repræsenterer en sekvens af poster af variabel længde. Den typiske længde af en post er omkring 30 bytes (selvom der nogle gange forekommer poster, der er flere kilobytes lange). I dette tilfælde arbejder vi med dem blot som et sæt bytes, men hvis du er interesseret, bruges CBOR inde i posterne

Ud over loggen skal vi gemme nogle "indstillings"-oplysninger, både opdaterede og ikke: et bestemt enheds-id, sensorkalibreringer, et flag "enheden er midlertidigt deaktiveret" osv.
Disse oplysninger er et sæt nøgleværdiposter, der også er gemt i CBOR. Vi har ikke mange af disse oplysninger (højst et par kilobyte), og de opdateres sjældent.
I det følgende vil vi kalde det kontekst.

Hvis vi husker, hvor denne artikel begyndte, er det meget vigtigt at sikre pålidelig datalagring og om muligt kontinuerlig drift selv i tilfælde af hardwarefejl/datakorruption.

Hvilke kilder til problemer kan overvejes?

• Sluk under skrive/sletning. Dette er fra kategorien "der er intet trick mod koben."
  Oplysninger fra diskussioner på stackexchange: når strømmen er slukket, mens du arbejder med flash, fører både sletning (sat til 1) og skrivning (sat til 0) til udefineret adfærd: data kan skrives, delvist skrives (f.eks. har vi overført 10 bytes/80 bits , men endnu ikke kun 45 bit kan skrives), er det også muligt, at nogle af bits vil være i en "mellemliggende" tilstand (læsning kan producere både 0 og 1);
• Fejl i selve flashhukommelsen.
  BER, selv om den er meget lav, kan ikke være lig med nul;
• Bus fejl
  Data transmitteret via SPI er ikke beskyttet på nogen måde, både enkeltbitfejl og synkroniseringsfejl kan forekomme - tab eller indsættelse af bits (hvilket fører til massiv dataforvrængning);
• Andre fejl/fejl
  Fejl i koden, hindbærfejl, rumvæseninterferens...

Jeg har formuleret de krav, hvis opfyldelse efter min mening er nødvendig for at sikre pålidelighed:

• Optegnelser skal straks ind i flashhukommelsen, forsinkede skrivninger tages ikke i betragtning - hvis der opstår en fejl, skal den opdages og behandles så tidligt som muligt - systemet skal om muligt komme sig efter fejl.
  (et eksempel fra livet "hvordan det ikke burde være", som jeg tror alle er stødt på: efter en nødgenstart er filsystemet "brudt", og operativsystemet starter ikke)

Ideer, tilgange, refleksioner

Da jeg begyndte at tænke på dette problem, kom der en masse ideer gennem mit hoved, for eksempel:

• brug datakomprimering;
• brug smarte datastrukturer, for eksempel ved at gemme posthoveder adskilt fra selve posterne, så hvis der er en fejl i en post, kan du læse resten uden problemer;
• brug bitfelter til at kontrollere færdiggørelsen af ​​optagelsen, når strømmen er slukket;
• opbevare kontrolsummer for alt;
• bruge en eller anden form for støjbestandig kodning.

Nogle af disse ideer blev brugt, mens andre blev besluttet at blive opgivet. Lad os gå i rækkefølge.

Datakomprimering

Selve begivenhederne, som vi registrerer i journalen, er ret ens og kan gentages ("kastede en 5 rubelmønt", "trykte på knappen for at give vekslepenge", ...). Derfor bør kompression være ret effektiv.

Kompressionsomkostningerne er ubetydelige (vores processor er ret kraftig, selv den første Pi havde en kerne med en frekvens på 700 MHz, nuværende modeller har flere kerner med en frekvens på over en gigahertz), vekselkursen med lageret er lav (flere megabyte per sekund), er størrelsen af ​​posterne lille. Generelt, hvis komprimering har en indflydelse på ydeevnen, vil det kun være positivt. (helt ukritisk, siger bare). Plus, vi har ikke rigtig indlejret, men almindelig Linux - så implementeringen burde ikke kræve meget indsats (det er nok bare at linke biblioteket og bruge flere funktioner fra det).

Et stykke af loggen blev taget fra en fungerende enhed (1.7 MB, 70 tusinde indgange) og først kontrolleret for komprimerbarhed ved hjælp af gzip, lz4, lzop, bzip2, xz, zstd tilgængelig på computeren.

• gzip, xz, zstd viste lignende resultater (40Kb).
  Jeg var overrasket over, at den fashionable xz viste sig her på niveau med gzip eller zstd;
• lzip med standardindstillinger gav lidt dårligere resultater;
• lz4 og lzop viste ikke særlig gode resultater (150Kb);
• bzip2 viste et overraskende godt resultat (18Kb).

Så data er komprimeret meget godt.
Så (hvis vi ikke finder fatale fejl) vil der være kompression! Simpelthen fordi flere data kan passe på det samme flashdrev.

Lad os tænke på ulemperne.

Første problem: vi har allerede aftalt, at hver plade straks skal gå til flash. Typisk indsamler arkiveren data fra inputstrømmen, indtil den beslutter, at det er tid til at skrive i weekenden. Vi skal straks modtage en komprimeret datablok og gemme den i ikke-flygtig hukommelse.

Jeg ser tre måder:

1. Komprimer hver post ved hjælp af ordbogskomprimering i stedet for de algoritmer, der er diskuteret ovenfor.
   Det er en fuldstændig fungerende mulighed, men jeg kan ikke lide det. For at sikre et mere eller mindre anstændigt komprimeringsniveau skal ordbogen "skræddersyes" til specifikke data; enhver ændring vil føre til, at komprimeringsniveauet falder katastrofalt. Ja, problemet kan løses ved at oprette en ny version af ordbogen, men dette er en hovedpine - vi bliver nødt til at gemme alle versioner af ordbogen; i hver post skal vi angive, med hvilken version af ordbogen den blev komprimeret...
2. Komprimer hver post ved hjælp af "klassiske" algoritmer, men uafhængigt af de andre.
   De komprimeringsalgoritmer, der overvejes, er ikke designet til at fungere med poster af denne størrelse (tivis af bytes), komprimeringsforholdet vil klart være mindre end 1 (det vil sige at øge datavolumen i stedet for at komprimere);
3. Udfør FLUSH efter hver optagelse.
   Mange komprimeringsbiblioteker understøtter FLUSH. Dette er en kommando (eller en parameter til komprimeringsproceduren), ved modtagelse, som arkiveren danner en komprimeret strøm, så den kan bruges til at gendanne alle ukomprimerede data, der allerede er modtaget. Sådan en analog sync i filsystemer eller commit i sql.
   Det, der er vigtigt, er, at efterfølgende komprimeringsoperationer vil være i stand til at bruge den akkumulerede ordbog, og komprimeringsforholdet vil ikke lide så meget som i den tidligere version.

Jeg synes, det er indlysende, at jeg valgte den tredje mulighed, lad os se på det mere detaljeret.

Fundet god artikel om FLUSH i zlib.

Jeg lavede en knætest baseret på artiklen, tog 70 tusinde logposter fra en rigtig enhed med en sidestørrelse på 60Kb (vi vender tilbage til sidestørrelse senere) modtaget:

Indledende data
Kompression gzip -9 (ingen FLUSH)
zlib med Z_PARTIAL_FLUSH
zlib med Z_SYNC_FLUSH

Bind, KB
1692
40
352
604

Ved første øjekast er prisen, som FLUSH bidrager med, alt for høj, men i virkeligheden har vi ikke meget valg - enten ikke at komprimere overhovedet, eller at komprimere (og meget effektivt) med FLUSH. Vi må ikke glemme, at vi har 70 tusinde poster, redundansen introduceret af Z_PARTIAL_FLUSH er kun 4-5 bytes pr. post. Og kompressionsforholdet viste sig at være næsten 5:1, hvilket er mere end et fremragende resultat.

Det kan komme som en overraskelse, men Z_SYNC_FLUSH er faktisk en mere effektiv måde at lave FLUSH på

Når du bruger Z_SYNC_FLUSH, vil de sidste 4 bytes af hver post altid være 0x00, 0x00, 0xff, 0xff. Og hvis vi kender dem, så behøver vi ikke at gemme dem, så den endelige størrelse er kun 324Kb.

Artiklen jeg linkede til har en forklaring:

En ny type 0 blok med tomt indhold tilføjes.

En type 0 blok med tomt indhold består af:

• tre-bit blokhovedet;
• 0 til 7 bit lig med nul for at opnå byte-justering;
• fire-byte sekvensen 00 00 FF FF.

Som du nemt kan se, er der i den sidste blok før disse 4 bytes fra 3 til 10 nul bits. Praksis har dog vist, at der faktisk er mindst 10 nul bits.

Det viser sig, at sådanne korte datablokke normalt (altid?) er kodet ved hjælp af en blok af type 1 (fast blok), som nødvendigvis ender med 7 nul bit, hvilket giver i alt 10-17 garanterede nul bit (og resten vil være nul med en sandsynlighed på omkring 50 %).

Så på testdata er der i 100 % af tilfældene en nul byte før 0x00, 0x00, 0xff, 0xff, og i mere end en tredjedel af tilfældene er der to nul byte (Måske faktum er, at jeg bruger binær CBOR, og når jeg bruger tekst JSON, ville blokke af type 2 - dynamisk blok være mere almindelige, henholdsvis blokke uden yderligere nul bytes før 0x00, 0x00, 0xff, 0xff ville blive stødt på).

Ved hjælp af de tilgængelige testdata er det i alt muligt at passe ind i mindre end 250Kb komprimerede data.

Du kan spare lidt mere ved at lave lidt jonglering: for nu ignorerer vi tilstedeværelsen af ​​et par nul bits i slutningen af ​​blokken, et par bits i begyndelsen af ​​blokken ændrer sig heller ikke...
Men så tog jeg en viljestærk beslutning om at stoppe, ellers kunne jeg med denne hastighed ende med at udvikle mit eget arkiver.

I alt modtog jeg fra mine testdata 3-4 bytes pr. skrivning, kompressionsforholdet viste sig at være mere end 6:1. Jeg skal være ærlig: Jeg havde ikke forventet et sådant resultat; efter min mening er noget bedre end 2:1 allerede et resultat, der retfærdiggør brugen af ​​kompression.

Alt er fint, men zlib (deflatere) er stadig en arkaisk, velfortjent og lidt gammeldags kompressionsalgoritme. Alene det faktum, at de sidste 32Kb af den ukomprimerede datastrøm bruges som en ordbog, ser mærkeligt ud i dag (det vil sige, hvis en datablok er meget lig det, der var i inputstrømmen for 40Kb siden, så vil den begynde at blive arkiveret igen, og vil ikke referere til en tidligere hændelse). I fashionable moderne arkivere måles ordbogsstørrelsen ofte i megabyte frem for kilobyte.

Så vi fortsætter vores mini-studie af arkivarer.

Dernæst testede vi bzip2 (husk, uden FLUSH viste den et fantastisk kompressionsforhold på næsten 100:1). Desværre klarede det sig meget dårligt med FLUSH; størrelsen af ​​de komprimerede data viste sig at være større end de ukomprimerede data.

Mine antagelser om årsagerne til svigtet

Libbz2 tilbyder kun én flush-mulighed, som ser ud til at rydde ordbogen (analogt med Z_FULL_FLUSH i zlib); der er ikke tale om nogen effektiv komprimering efter dette.

Og den sidste, der blev testet, var zstd. Afhængigt af parametrene komprimerer den enten på gzip-niveau, men meget hurtigere eller bedre end gzip.

Ak, med FLUSH fungerede det ikke særlig godt: Størrelsen af ​​de komprimerede data var omkring 700Kb.

Я stillede et spørgsmål på projektets github-side modtog jeg et svar om, at du skulle regne med op til 10 bytes servicedata for hver blok af komprimerede data, hvilket er tæt på de opnåede resultater; der er ingen måde at indhente deflate.

Jeg besluttede at stoppe på dette tidspunkt i mine eksperimenter med arkivere (lad mig minde dig om, at xz, lzip, lzo, lz4 ikke viste sig selv på teststadiet uden FLUSH, og jeg overvejede ikke mere eksotiske kompressionsalgoritmer).

Lad os vende tilbage til arkiveringsproblemer.

Det andet (som de siger i rækkefølge, ikke i værdi) problem er, at de komprimerede data er en enkelt strøm, hvor der konstant er referencer til tidligere afsnit. Hvis en del af komprimerede data er beskadiget, mister vi således ikke kun den tilhørende blok af ukomprimerede data, men også alle efterfølgende.

Der er en tilgang til at løse dette problem:

1. Undgå at problemet opstår - tilføj redundans til de komprimerede data, som giver dig mulighed for at identificere og rette fejl; vi taler om dette senere;
2. Minimer konsekvenserne, hvis der opstår et problem
   Vi har allerede sagt tidligere, at du kan komprimere hver datablok uafhængigt, og problemet vil forsvinde af sig selv (skade på dataene i en blok vil kun føre til tab af data for denne blok). Dette er dog et ekstremt tilfælde, hvor datakomprimering vil være ineffektiv. Den modsatte yderlighed: brug alle 4 MB af vores chip som et enkelt arkiv, hvilket vil give os fremragende komprimering, men katastrofale konsekvenser i tilfælde af datakorruption.
   Ja, et kompromis er nødvendigt med hensyn til pålidelighed. Men vi skal huske, at vi udvikler et datalagringsformat til ikke-flygtig hukommelse med ekstremt lav BER og en erklæret datalagringsperiode på 20 år.

Under eksperimenterne opdagede jeg, at mere eller mindre mærkbare tab i komprimeringsniveauet begynder på blokke af komprimerede data mindre end 10 KB i størrelse.
Det blev tidligere nævnt, at den anvendte hukommelse er paged; jeg kan ikke se nogen grund til, at korrespondancen "én side - en blok med komprimerede data" ikke skulle bruges.

Det vil sige, at den mindste rimelige sidestørrelse er 16Kb (med forbehold for serviceoplysninger). Men en så lille sidestørrelse pålægger betydelige begrænsninger for den maksimale poststørrelse.

Selvom jeg endnu ikke forventer poster større end et par kilobyte i komprimeret form, besluttede jeg at bruge 32Kb sider (for i alt 128 sider pr. chip).

Sammendrag:

• Vi gemmer data komprimeret ved hjælp af zlib (deflate);
• For hver indtastning sætter vi Z_SYNC_FLUSH;
• For hver komprimeret post trimmer vi de efterfølgende bytes (f.eks. 0x00, 0x00, 0xff, 0xff); i overskriften angiver vi, hvor mange bytes vi skærer fra;
• Vi gemmer data på 32Kb sider; der er en enkelt strøm af komprimerede data inde på siden; På hver side starter vi komprimering igen.

Og før jeg afslutter med komprimering, vil jeg gerne henlede din opmærksomhed på, at vi kun har et par bytes komprimerede data pr. record, så det er ekstremt vigtigt ikke at puste serviceinformationen op, hver byte tæller her.

Lagring af dataoverskrifter

Da vi har poster af variabel længde, skal vi på en eller anden måde bestemme placeringen/grænserne for poster.

Jeg kender tre tilgange:

1. Alle poster gemmes i en kontinuerlig strøm, først er der en postheader, der indeholder længden, og derefter selve posten.
   I denne udførelsesform kan både overskrifter og data være af variabel længde.
   I det væsentlige får vi en enkelt-linket liste, der bruges hele tiden;
2. Overskrifter og selve posterne gemmes i separate strømme.
   Ved at bruge skæreborde med konstant længde sikrer vi, at skader på et skær ikke påvirker de andre.
   En lignende tilgang bruges for eksempel i mange filsystemer;
3. Poster gemmes i en kontinuerlig strøm, postgrænsen bestemmes af en bestemt markør (en karakter/sekvens af tegn, der er forbudt inden for datablokke). Hvis der er en markør inde i posten, så erstatter vi den med en sekvens (undslipper den).
   En lignende tilgang bruges for eksempel i PPP-protokollen.

Jeg vil illustrere.

Mulighed 1:

Alt er meget enkelt her: ved at kende længden af ​​posten, kan vi beregne adressen på den næste overskrift. Så vi bevæger os gennem overskrifterne, indtil vi støder på et område fyldt med 0xff (frit område) eller slutningen af ​​siden.

Mulighed 2:

På grund af den variable postlængde kan vi ikke på forhånd sige, hvor mange poster (og dermed headers) vi skal bruge pr. Du kan sprede overskrifterne og selve dataene på tværs af forskellige sider, men jeg foretrækker en anden tilgang: vi placerer både overskrifterne og dataene på én side, men overskrifterne (af konstant størrelse) kommer fra begyndelsen af ​​siden, og data (af variabel længde) kommer fra enden. Så snart de "mødes" (der er ikke nok ledig plads til en ny post), betragter vi denne side som komplet.

Mulighed 3:

Det er ikke nødvendigt at gemme længden eller andre oplysninger om placeringen af ​​dataene i overskriften; markører, der angiver grænserne for posterne, er nok. Dataene skal dog behandles ved skrivning/læsning.
Jeg ville bruge 0xff som markør (som fylder siden efter sletning), så det frie område vil bestemt ikke blive behandlet som data.

Sammenligningstabel:

Mulighed 1
Mulighed 2
Mulighed 3

Fejltolerance
—
+
+

tæthed
+
—
+

Implementeringskompleksitet
*
**
**

Mulighed 1 har en fatal fejl: Hvis nogen af ​​headerne er beskadiget, ødelægges hele den efterfølgende kæde. De resterende muligheder giver dig mulighed for at gendanne nogle data, selv i tilfælde af massiv skade.
Men her er det på sin plads at huske, at vi besluttede at gemme dataene i en komprimeret form, og så mister vi alle data på siden efter en "brudt" post, så selvom der er et minus i tabellen, gør vi det ikke tage hensyn til det.

Kompakthed:

• i den første mulighed skal vi kun gemme længden i overskriften; hvis vi bruger heltal med variabel længde, så kan vi i de fleste tilfælde klare os med en byte;
• i den anden mulighed skal vi gemme startadressen og længden; posten skal være en konstant størrelse, jeg anslår 4 bytes pr. post (to bytes for forskydningen og to bytes for længden);
• den tredje mulighed behøver kun et tegn for at indikere starten på optagelsen, plus at selve optagelsen vil stige med 1-2 % på grund af afskærmning. Generelt cirka paritet med den første mulighed.

Til at begynde med betragtede jeg den anden mulighed som den vigtigste (og skrev endda implementeringen). Jeg opgav det først, da jeg endelig besluttede at bruge komprimering.

Måske vil jeg en dag stadig bruge en lignende mulighed. Hvis jeg for eksempel skal beskæftige mig med datalagring for et skib, der sejler mellem Jorden og Mars, vil der være helt andre krav til pålidelighed, kosmisk stråling, ...

Med hensyn til den tredje mulighed: Jeg gav den to stjerner for vanskeligheden ved implementering, simpelthen fordi jeg ikke kan lide at rode rundt med afskærmning, ændre længden i processen osv. Ja, måske er jeg forudindtaget, men jeg bliver nødt til at skrive koden - hvorfor tvinge dig selv til at gøre noget, du ikke kan lide.

Sammendrag: Vi vælger opbevaringsmuligheden i form af kæder "header med længde - data af variabel længde" på grund af effektivitet og nem implementering.

Brug af bitfelter til at overvåge succesen med skriveoperationer

Jeg kan nu ikke huske hvor jeg fik ideen, men den ser sådan ud:
For hver indgang allokerer vi flere bits til at gemme flag.
Som vi sagde tidligere, efter sletning er alle bits fyldt med 1'ere, og vi kan ændre 1 til 0, men ikke omvendt. Så for "flaget er ikke sat" bruger vi 1, for "flaget er sat" bruger vi 0.

Sådan kan det se ud at sætte en rekord med variabel længde i flash:

1. Indstil flaget "længdeoptagelse er startet";
2. Optag længden;
3. Indstil "dataoptagelsen er startet"-flaget;
4. Vi registrerer data;
5. Indstil flaget "optagelse afsluttet".

Derudover vil vi have et "fejl opstod" flag, for i alt 4 bit flag.

I dette tilfælde har vi to stabile tilstande "1111" - optagelsen er ikke startet og "1000" - optagelsen var vellykket; i tilfælde af en uventet afbrydelse af optagelsesprocessen, vil vi modtage mellemtilstande, som vi så kan detektere og behandle.

Fremgangsmåden er interessant, men den beskytter kun mod pludselige strømafbrydelser og lignende fejl, hvilket selvfølgelig er vigtigt, men det er langt fra den eneste (eller endda hoved)årsagen til mulige fejl.

Sammendrag: Lad os gå videre i jagten på en god løsning.

Kontrolsummer

Kontrolsummer gør det også muligt at sikre sig (med rimelig sandsynlighed), at vi læser præcis, hvad der skulle have været skrevet. Og i modsætning til de bitfelter, der er diskuteret ovenfor, fungerer de altid.

Hvis vi overvejer listen over potentielle kilder til problemer, som vi diskuterede ovenfor, så er kontrolsummen i stand til at genkende en fejl uanset dens oprindelse (undtagen måske ondsindede rumvæsener - de kan også forfalske kontrolsummen).

Så hvis vores mål er at verificere, at dataene er intakte, er kontrolsummer en god idé.

Valget af algoritme til beregning af kontrolsummen rejste ingen spørgsmål - CRC. På den ene side gør matematiske egenskaber det muligt at fange visse typer fejl 100%; på den anden side viser denne algoritme på tilfældige data sædvanligvis sandsynligheden for kollisioner, der ikke er meget større end den teoretiske grænse. . Det er måske ikke den hurtigste algoritme, og det er heller ikke altid minimum i forhold til antallet af kollisioner, men det har en meget vigtig kvalitet: I de tests, jeg stødte på, var der ingen mønstre, hvor den klart fejlede. Stabilitet er hovedkvaliteten i dette tilfælde.

Eksempel på en volumetrisk undersøgelse: Part 1, Part 2 (links til narod.ru, undskyld).

Opgaven med at vælge en kontrolsum er dog ikke komplet; CRC er en hel familie af kontrolsummer. Du skal beslutte dig for længden og derefter vælge et polynomium.

At vælge kontrolsumlængden er ikke et så simpelt spørgsmål, som det ser ud til ved første øjekast.

Lad mig illustrere:
Lad os have sandsynligheden for en fejl i hver byte og en ideel kontrolsum, lad os beregne det gennemsnitlige antal fejl pr. million poster:

Data, byte
Kontrolsum, byte
Uopdagede fejl
Falske fejlregistreringer
Total falske positiver

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

Det ser ud til, at alt er enkelt - afhængig af længden af ​​de data, der beskyttes, skal du vælge længden af ​​kontrolsummen med et minimum af forkerte positive - og tricket er i bagagen.

Der opstår dog et problem med korte kontrolsummer: Selvom de er gode til at opdage enkeltbitfejl, kan de med ret stor sandsynlighed acceptere helt tilfældige data som korrekte. Der var allerede en artikel om Habré, der beskrev problem i det virkelige liv.

Derfor, for at gøre en tilfældig kontrolsum næsten umulig, skal du bruge kontrolsummer, der er 32 bit eller længere i længden. (for længder på mere end 64 bit bruges der typisk kryptografiske hash-funktioner).

På trods af det faktum, at jeg tidligere skrev, at vi med alle midler skal spare plads, vil vi stadig bruge en 32-bit kontrolsum (16 bit er ikke nok, sandsynligheden for en kollision er mere end 0.01%; og 24 bit, da de sige, er hverken her eller der).

Her kan der opstå en indvending: gemte vi hver byte, da vi valgte komprimering for nu at give 4 bytes på én gang? Ville det ikke være bedre ikke at komprimere eller tilføje en kontrolsum? Selvfølgelig ikke, ingen kompression betyder ikke, at vi ikke har brug for integritetskontrol.

Når vi vælger et polynomium, vil vi ikke genopfinde hjulet, men tage den nu populære CRC-32C.
Denne kode registrerer 6 bit fejl på pakker op til 22 bytes (måske det mest almindelige tilfælde for os), 4 bit fejl på pakker op til 655 bytes (også et almindeligt tilfælde for os), 2 eller et hvilket som helst ulige antal bitfejl på pakker af enhver rimelig længde.

Hvis nogen er interesseret i detaljerne

Wikipedia artikel om CRC.

Kode parametre crc-32c på Koopmans hjemmeside — måske den førende CRC-specialist på planeten.

В hans artikel Der er endnu en interessant kode, som giver lidt bedre parametre for de pakkelængder, der er relevante for os, men jeg anså ikke forskellen for væsentlig, og jeg var kompetent nok til at vælge tilpasset kode i stedet for den standard og velundersøgte.

Da vores data er komprimeret, opstår spørgsmålet: skal vi beregne kontrolsummen af ​​komprimerede eller ukomprimerede data?

Argumenter for at beregne kontrolsummen af ​​ukomprimerede data:

• Vi skal i sidste ende tjekke sikkerheden af ​​datalagring - så vi tjekker det direkte (samtidig vil eventuelle fejl i implementeringen af ​​komprimering/dekompression, skader forårsaget af ødelagt hukommelse osv. blive kontrolleret);
• Deflate-algoritmen i zlib har en ret moden implementering og bør ikke falder med "skæve" inputdata; desuden er den ofte i stand til selvstændigt at detektere fejl i inputstrømmen, hvilket reducerer den overordnede sandsynlighed for at undetektere en fejl (udførte en test med invertering af en enkelt bit i en kort post, zlib opdagede en fejl i omkring en tredjedel af tilfældene).

Argumenter mod at beregne kontrolsummen af ​​ukomprimerede data:

• CRC er "skræddersyet" specifikt til de få bitfejl, der er karakteristiske for flashhukommelse (en bitfejl i en komprimeret strøm kan forårsage en massiv ændring i outputstrømmen, hvorpå vi rent teoretisk kan "fange" en kollision);
• Jeg kan ikke rigtig lide ideen om at videregive potentielt ødelagte data til dekomprimeringen, Hvem vedhvordan han vil reagere.

I dette projekt besluttede jeg at afvige fra den almindeligt anerkendte praksis med at gemme en kontrolsum af ukomprimerede data.

Sammendrag: Vi bruger CRC-32C, vi beregner kontrolsummen fra dataene i den form, de er skrevet til at blinke (efter komprimering).

Redundans

Brugen af ​​redundant kodning eliminerer naturligvis ikke datatab, men det kan i væsentlig grad (ofte i mange størrelsesordener) reducere sandsynligheden for uopretteligt datatab.

Vi kan bruge forskellige typer redundans til at rette fejl.
Hamming-koder kan rette enkeltbitfejl, Reed-Solomon-tegnkoder, flere kopier af data kombineret med kontrolsummer eller kodninger som RAID-6 kan hjælpe med at gendanne data selv i tilfælde af massiv korruption.
I starten var jeg engageret i den udbredte brug af fejlbestandig kodning, men så indså jeg, at vi først skal have en idé om, hvilke fejl vi vil beskytte os mod, og derefter vælge kodning.

Vi sagde tidligere, at fejl skal fanges så hurtigt som muligt. På hvilke punkter kan vi støde på fejl?

1. Ufærdig optagelse (af en eller anden grund på optagelsestidspunktet blev strømmen slukket, hindbæret frøs, ...)
   Ak, i tilfælde af en sådan fejl, er der kun tilbage at ignorere ugyldige poster og betragte dataene som tabt;
2. Skrivefejl (af en eller anden grund var det, der blev skrevet til flashhukommelsen, ikke det, der blev skrevet)
   Vi kan straks opdage sådanne fejl, hvis vi laver en testlæsning umiddelbart efter optagelsen;
3. Forvrængning af data i hukommelsen under lagring;
4. Læsefejl
   For at rette det, hvis kontrolsummen ikke stemmer overens, er det nok at gentage læsningen flere gange.

Det vil sige, at kun fejl af den tredje type (spontan korruption af data under lagring) ikke kan rettes uden fejlbestandig kodning. Det ser ud til, at sådanne fejl stadig er yderst usandsynlige.

Sammendrag: det blev besluttet at opgive redundant kodning, men hvis operationen viser fejlen i denne beslutning, så vend tilbage til overvejelse af problemet (med allerede akkumulerede statistikker over fejl, som gør det muligt at vælge den optimale type kodning).

Andre

Naturligvis tillader artiklens format os ikke at retfærdiggøre hver eneste bit i formatet (og mine kræfter er allerede løbet op), så jeg vil kort gennemgå nogle punkter, der ikke er berørt tidligere.

• Det blev besluttet at gøre alle sider "lige"
  Det vil sige, at der ikke kommer specielle sider med metadata, separate tråde osv., men derimod en enkelt tråd, der omskriver alle sider på skift.
  Dette sikrer ensartet slid på siderne, ingen enkelt point of failure, og jeg kan bare lide det;
• Det er bydende nødvendigt at sørge for versionering af formatet.
  Et format uden et versionsnummer i overskriften er ondt!
  Det er nok at tilføje et felt med et bestemt magisk tal (signatur) til sidehovedet, som angiver versionen af ​​det anvendte format (Jeg tror ikke, at der i praksis vil være et dusin af dem);
• Brug en header med variabel længde til poster (som der er mange af), og prøv at gøre den 1 byte lang i de fleste tilfælde;
• For at kode længden af ​​overskriften og længden af ​​den trimmede del af den komprimerede post skal du bruge binære koder med variabel længde.

hjalp meget online generator Huffman koder. På få minutter var vi i stand til at vælge de nødvendige koder med variabel længde.

Beskrivelse af datalagringsformat

Byte rækkefølge

Felter, der er større end én byte, gemmes i big-endian-format (netværksbyterækkefølge), dvs. 0x1234 skrives som 0x12, 0x34.

Sideinddeling

Al flashhukommelse er opdelt i sider af samme størrelse.

Standardsidestørrelsen er 32Kb, men ikke mere end 1/4 af den samlede størrelse af hukommelseschippen (for en 4MB-chip opnås 128 sider).

Hver side gemmer data uafhængigt af de andre (det vil sige, data på én side refererer ikke til data på en anden side).

Alle sider er nummereret i naturlig rækkefølge (i stigende rækkefølge af adresser), startende med nummer 0 (side nul starter ved adresse 0, første side starter ved 32Kb, anden side starter ved 64Kb osv.)

Hukommelsechippen bruges som en cyklisk buffer (ringbuffer), det vil sige, at først skrivning går til sidenummer 0, derefter nummer 1, ..., når vi fylder den sidste side, starter en ny cyklus og optagelsen fortsætter fra side nul .

Inde på siden

I begyndelsen af ​​siden gemmes en 4-byte sidehoved, derefter en header checksum (CRC-32C), derefter gemmes poster i "header, data, checksum" formatet.

Sidetitlen (snavset grøn i diagrammet) består af:

• to-byte Magic Number-felt (også et tegn på formatversionen)
  for den aktuelle version af formatet er det beregnet som 0xed00 ⊕ номер страницы;
• to-byte tæller "Sideversion" (hukommelsesomskrivningscyklusnummer).

Indgange på siden gemmes i komprimeret form (deflateringsalgoritmen bruges). Alle poster på én side komprimeres i én tråd (en fælles ordbog bruges), og på hver ny side starter komprimeringen på ny. Det vil sige, at for at dekomprimere enhver post, kræves alle tidligere poster fra denne side (og kun denne).

Hver post vil blive komprimeret med Z_SYNC_FLUSH flaget, og i slutningen af ​​den komprimerede strøm vil der være 4 bytes 0x00, 0x00, 0xff, 0xff, muligvis efterfulgt af en eller to nul bytes mere.
Vi kasserer denne sekvens (4, 5 eller 6 bytes lang), når vi skriver til flashhukommelsen.

Posthovedet er 1, 2 eller 3 bytes, der lagrer:

• en bit (T), der angiver typen af ​​post: 0 - kontekst, 1 - log;
• et felt med variabel længde (S) fra 1 til 7 bit, der definerer længden af ​​headeren og "halen", der skal tilføjes til posten for dekompression;
• rekordlængde (L).

S værdi tabel:

S
Header længde, bytes
Kasseret ved skrivning, 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)

Jeg prøvede at illustrere, jeg ved ikke hvor tydeligt det blev:

Gul her angiver T-feltet, hvidt S-feltet, grønt L (længden af ​​de komprimerede data i bytes), blåt de komprimerede data, rødt de sidste bytes af de komprimerede data, der ikke er skrevet til flash-hukommelsen.

Således kan vi skrive postoverskrifter af den mest almindelige længde (op til 63+5 bytes i komprimeret form) i én byte.

Efter hver post lagres en CRC-32C kontrolsum, hvori den inverterede værdi af den foregående kontrolsum bruges som startværdi (init).

CRC har egenskaben "varighed", følgende formel virker (plus eller minus bit inversion i processen): .
Det vil sige, at vi faktisk beregner CRC for alle tidligere bytes af overskrifter og data på denne side.

Direkte efter kontrolsummen er overskriften på den næste post.

Headeren er designet på en sådan måde, at dens første byte altid er forskellig fra 0x00 og 0xff (hvis vi i stedet for den første byte i headeren støder på 0xff, betyder det, at dette er et ubrugt område; 0x00 signalerer en fejl).

Eksempel algoritmer

Læsning fra Flash-hukommelse

Enhver aflæsning kommer med en kontrolsum.
Hvis kontrolsummen ikke stemmer overens, gentages aflæsningen flere gange i håb om at læse de korrekte data.

(dette giver mening, Linux cachelagrer ikke læsninger fra NOR Flash, testet)

Skriv til flashhukommelsen

Vi registrerer dataene.
Lad os læse dem.

Hvis de aflæste data ikke stemmer overens med de skrevne data, udfylder vi området med nuller og signalerer en fejl.

Forberedelse af et nyt mikrokredsløb til drift

Til initialisering skrives en header med version 1 til den første (eller rettere nul) side.
Derefter skrives den indledende kontekst til denne side (indeholder maskinens UUID og standardindstillinger).

Det er det, flash-hukommelsen er klar til brug.

Indlæsning af maskinen

Ved indlæsning læses de første 8 bytes af hver side (header + CRC), sider med et ukendt magisk tal eller en forkert CRC ignoreres.
Fra de "korrekte" sider vælges sider med den maksimale version, og siden med det højeste antal tages fra dem.
Den første post læses, korrektheden af ​​CRC og tilstedeværelsen af ​​"kontekst"-flaget kontrolleres. Hvis alt er i orden, anses denne side for at være aktuel. Hvis ikke, ruller vi tilbage til den forrige, indtil vi finder en "live" side.
og på den fundne side læser vi alle posterne, dem som vi bruger med "kontekst"-flaget.
Gem zlib-ordbogen (den vil være nødvendig for at tilføje til denne side).

Det er det, overførslen er fuldført, konteksten er gendannet, du kan arbejde.

Tilføjelse af en journalpost

Vi komprimerer posten med den korrekte ordbog, specificerer Z_SYNC_FLUSH. Vi ser om den komprimerede post passer på den aktuelle side.
Hvis det ikke passer (eller der var CRC-fejl på siden), skal du starte en ny side (se nedenfor).
Vi skriver journalen og CRC ned. Hvis der opstår en fejl, skal du starte en ny side.

Ny side

Vi vælger en gratis side med minimumsantallet (vi betragter en gratisside som en side med en forkert kontrolsum i overskriften eller med en version mindre end den nuværende). Hvis der ikke er sådanne sider, skal du vælge siden med minimumsantallet blandt dem, der har en version svarende til den nuværende.
Vi sletter den valgte side. Vi tjekker indholdet med 0xff. Hvis der er noget galt, så tag den næste gratis side osv.
Vi skriver en overskrift på den slettede side, den første post er den aktuelle tilstand af konteksten, den næste er den uskrevne logpost (hvis der er en).

Formatanvendelighed

Efter min mening viste det sig at være et godt format til at gemme mere eller mindre komprimerbare informationsstrømme (almindelig tekst, JSON, MessagePack, CBOR, evt. protobuf) i NOR Flash.

Formatet er selvfølgelig "skræddersyet" til SLC NOR Flash.

Det bør ikke bruges med høje BER-medier såsom NAND eller MLC NOR (er sådan hukommelse overhovedet tilgængelig til salg? Jeg har kun set den nævnt i værker om rettelseskoder).

Desuden bør den ikke bruges med enheder, der har deres egen FTL: USB flash, SD, MicroSD osv (til en sådan hukommelse oprettede jeg et format med en sidestørrelse på 512 bytes, en signatur i begyndelsen af ​​hver side og unikke rekordnumre - nogle gange var det muligt at gendanne alle data fra et "fejl" flashdrev ved simpel sekventiel læsning).

Afhængigt af opgaverne kan formatet bruges uden ændringer på flashdrev fra 128Kbit (16Kb) til 1Gbit (128MB). Hvis det ønskes, kan du bruge det på større chips, men du skal nok justere sidestørrelsen (Men her dukker spørgsmålet om økonomisk gennemførlighed allerede op; prisen for store mængder NOR Flash er ikke opmuntrende).

Hvis nogen finder formatet interessant og vil bruge det i et åbent projekt, så skriv, jeg vil prøve at finde tiden, polere koden og poste den på github.

Konklusion

Som du kan se, viste formatet sig i sidste ende at være enkelt og endda kedeligt.

Det er svært at afspejle udviklingen af ​​mit synspunkt i en artikel, men tro mig: oprindeligt ønskede jeg at skabe noget sofistikeret, uforgængeligt, der er i stand til at overleve selv en atomeksplosion i umiddelbar nærhed. Men fornuften (håber jeg) vandt stadig, og gradvist skiftede prioriteterne mod enkelhed og kompakthed.

Kan det være, at jeg tog fejl? Ja sikkert. Det kan for eksempel godt vise sig, at vi har købt et parti mikrokredsløb af lav kvalitet. Eller af en eller anden grund vil udstyret ikke leve op til forventningerne til pålidelighed.

Har jeg en plan for dette? Jeg tror, ​​at du efter at have læst artiklen ikke er i tvivl om, at der er en plan. Og ikke engang alene.

På en lidt mere seriøs note blev formatet udviklet både som en funktionsmulighed og som en "prøveballon".

I øjeblikket fungerer alt på bordet fint, bogstaveligt talt den anden dag vil løsningen blive implementeret (rundt regnet) på hundredvis af enheder, lad os se, hvad der sker i "kamp"-operation (heldigvis håber jeg, at formatet giver dig mulighed for pålideligt at opdage fejl; så du kan indsamle fuld statistik). Om nogle måneder vil det være muligt at drage konklusioner (og hvis du er uheldig, endnu tidligere).

Hvis der, baseret på resultaterne af brugen, opdages alvorlige problemer, og der kræves forbedringer, så vil jeg helt sikkert skrive om det.

Litteratur

Jeg ønskede ikke at lave en lang kedelig liste over brugte værker; trods alt har alle Google.

Her besluttede jeg at efterlade en liste over resultater, der forekom mig særligt interessante, men efterhånden migrerede de direkte ind i artiklens tekst, og et punkt forblev på listen:

1. Hjælpeprogram infgen fra forfatteren zlib. Kan tydeligt vise indholdet af deflate/zlib/gzip-arkiver. Hvis du skal beskæftige dig med den interne struktur af deflate (eller gzip) formatet, kan jeg varmt anbefale det.

Kilde: www.habr.com