forhistorie

Det finnes salgsautomater av vårt eget design. Inne i Raspberry Pi og litt ledninger på et eget brett. En myntmottaker, en seddelmottaker, en bankterminal kobles sammen... Alt styres av et selvskrevet program. Hele arbeidshistorikken skrives til en logg på en flash-stasjon (MicroSD), som deretter overføres via Internett (ved hjelp av et USB-modem) til serveren, hvor den lagres i en database. Salgsinformasjon lastes inn i 1c, det er også et enkelt webgrensesnitt for overvåking osv.

Det vil si at journalen er viktig - for regnskap (inntekter, salg, etc.), overvåking (alle typer feil og andre force majeure-omstendigheter); Dette, kan man si, er all informasjonen vi har om denne maskinen.

problem

Flash-stasjoner viser seg å være svært upålitelige enheter. De mislykkes med misunnelsesverdig regelmessighet. Dette fører til både maskinstans og (hvis loggen av en eller annen grunn ikke kunne overføres online) til tap av data.

Dette er ikke den første erfaringen med å bruke flash-stasjoner, før dette var det et annet prosjekt med mer enn hundre enheter, hvor magasinet ble lagret på USB-flash-stasjoner, det var også problemer med påliteligheten, til tider antallet som feilet i en måned var i dusinvis. Vi prøvde forskjellige flash-stasjoner, inkludert merkede med SLC-minne, og noen modeller er mer pålitelige enn andre, men å erstatte flash-stasjoner løste ikke radikalt problemet.

Advarsel! Langlest! Hvis du ikke er interessert i "hvorfor", men bare i "hvordan", kan du gå rett Til slutt artikkelen.

beslutning

Det første du tenker på er: forlat MicroSD, installer for eksempel en SSD, og ​​start opp fra den. Teoretisk mulig, sannsynligvis, men relativt dyrt, og ikke så pålitelig (en USB-SATA-adapter er lagt til; feilstatistikk for budsjett-SSDer er heller ikke oppmuntrende).

USB HDD ser heller ikke ut som en spesielt attraktiv løsning.

Derfor kom vi til dette alternativet: la oppstart fra MicroSD, men bruk dem i skrivebeskyttet modus, og lagre operasjonsloggen (og annen informasjon unik for en bestemt maskinvare - serienummer, sensorkalibreringer, etc.) et annet sted .

Emnet for skrivebeskyttet FS for bringebær er allerede studert innvendig og utvendig, jeg vil ikke dvele ved implementeringsdetaljer i denne artikkelen (men hvis det er interesse, kanskje jeg skriver en miniartikkel om dette emnet). Det eneste poenget jeg vil merke meg er at både fra personlig erfaring og fra vurderinger av de som allerede har implementert det, er det en gevinst i pålitelighet. Ja, det er umulig å fullstendig kvitte seg med sammenbrudd, men det er fullt mulig å redusere frekvensen deres betydelig. Og kortene blir enhetlige, noe som gjør utskifting mye enklere for servicepersonell.

maskinvare

Det var ingen spesiell tvil om valg av minnetype – NOR Flash.
argumenter:

• enkel tilkobling (oftest SPI-bussen, som du allerede har erfaring med å bruke, så ingen maskinvareproblemer er forutsett);
• latterlig pris;
• standard driftsprotokoll (implementeringen er allerede i Linux-kjernen, hvis du ønsker det, kan du ta en tredjepart, som også er til stede, eller til og med skrive din egen, heldigvis er alt enkelt);
• pålitelighet og ressurs:
  fra et typisk datablad: data lagres i 20 år, 100000 XNUMX slettesykluser for hver blokk;
  fra tredjepartskilder: ekstremt lav BER, postulerer ikke behov for feilrettingskoder (noen verk vurderer ECC for NOR, men vanligvis betyr de fortsatt MLC NOR; dette skjer også).

La oss anslå kravene til volum og ressurs.

Jeg vil at dataene skal være garantert lagret i flere dager. Dette er nødvendig for at salgshistorikken ikke skal gå tapt ved eventuelle kommunikasjonsproblemer. Vi vil fokusere på 5 dager, i denne perioden (selv tatt i betraktning helger og helligdager) problemet kan løses.

Vi samler for tiden rundt 100 kb med logger per dag (3-4 tusen oppføringer), men gradvis vokser dette tallet - detaljene øker, nye hendelser blir lagt til. I tillegg er det noen ganger utbrudd (noen sensor begynner for eksempel å spamme med falske positiver). Vi vil beregne for 10 tusen poster 100 byte hver - megabyte per dag.

Totalt kommer 5MB med rene (godt komprimerte) data ut. Mer til dem (grovt anslag) 1 MB med tjenestedata.

Det vil si at vi trenger en 8MB-brikke hvis vi ikke bruker komprimering, eller 4MB hvis vi bruker den. Ganske realistiske tall for denne typen minne.

Når det gjelder ressursen: hvis vi planlegger at hele minnet ikke skal skrives om mer enn én gang hver 5. dag, får vi over 10 års tjeneste mindre enn tusen omskrivingssykluser.
La meg minne deg på at produsenten lover hundre tusen.

Litt om NOR vs NAND

I dag er selvfølgelig NAND-minne mye mer populært, men jeg ville ikke brukt det til dette prosjektet: NAND, i motsetning til NOR, krever nødvendigvis bruk av feilrettingskoder, en tabell over dårlige blokker osv., og også benene til NAND-brikker vanligvis mye mer.

Ulempene med NOR inkluderer:

• lite volum (og følgelig høy pris per megabyte);
• lav kommunikasjonshastighet (hovedsakelig på grunn av det faktum at det brukes et seriell grensesnitt, vanligvis SPI eller I2C);
• langsom sletting (avhengig av blokkstørrelsen, tar det fra en brøkdel av et sekund til flere sekunder).

Det ser ut til at det ikke er noe kritisk for oss, så vi fortsetter.

Hvis detaljene er interessante, er mikrokretsen valgt at25df321a (men dette er uviktig, det er mange analoger på markedet som er kompatible i pinout og kommandosystem; selv om vi ønsker å installere en mikrokrets fra en annen produsent og/eller en annen størrelse, vil alt fungere uten å endre kode).

Jeg bruker driveren innebygd i Linux-kjernen; på Raspberry, takket være støtte for enhetstreoverlegg, er alt veldig enkelt - du må legge det kompilerte overlegget i /boot/overlays og endre /boot/config.txt litt.

Eksempel på dts-fil

For å være ærlig er jeg ikke sikker på at det er skrevet uten feil, men det fungerer.

/*
 * 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 en annen linje i config.txt

dtoverlay=at25:spimaxfrequency=50000000

Jeg vil utelate beskrivelsen av å koble brikken til Raspberry Pi. På den ene siden er jeg ingen ekspert på elektronikk, på den andre siden er alt her banalt selv for meg: mikrokretsen har bare 8 ben, hvorav vi trenger jord, strøm, SPI (CS, SI, SO, SCK ); nivåene er de samme som for Raspberry Pi, ingen ekstra ledninger er nødvendig - bare koble til de angitte 6 pinnene.

Formulering av problemet

Som vanlig går problemformuleringen gjennom flere iterasjoner, og det virker for meg som om det er på tide med den neste. Så la oss stoppe opp, sette sammen det som allerede er skrevet, og avklare detaljene som forblir i skyggen.

Så vi har bestemt at loggen skal lagres i SPI NOR Flash.

Hva er NOR Flash for de som ikke vet?

Dette er ikke-flyktig minne som du kan gjøre tre operasjoner med:

1. Lesning:
   Den vanligste lesingen: vi overfører adressen og leser så mange byte vi trenger;
2. Запись:
   Å skrive til NOR flash ser ut som en vanlig en, men den har en særegenhet: du kan bare endre 1 til 0, men ikke omvendt. For eksempel, hvis vi hadde 0x55 i en minnecelle, vil 0x0 allerede være lagret der etter å ha skrevet 0x05f til den (se tabellen rett nedenfor);
3. Viske ut:
   Selvfølgelig må vi kunne gjøre den motsatte operasjonen - endre 0 til 1, det er akkurat dette sletteoperasjonen er til for. I motsetning til de to første, fungerer den ikke med byte, men med blokker (minste sletteblokk i den valgte brikken er 4kb). Slett ødelegger hele blokken og er den eneste måten å endre 0 til 1. Derfor, når du arbeider med flashminne, må du ofte justere datastrukturer til sletteblokkgrensen.
   Opptak i NOR Flash:

Binære data

det var
01010101

Innspilt
00001111

Har blitt
00000101

Selve loggen representerer en sekvens av poster med variabel lengde. Den typiske lengden på en post er omtrent 30 byte (selv om poster som er flere kilobyte lange noen ganger forekommer). I dette tilfellet jobber vi med dem ganske enkelt som et sett med byte, men hvis du er interessert, brukes CBOR inne i postene

I tillegg til loggen, må vi lagre noe "oppsett"-informasjon, både oppdatert og ikke: en viss enhets-ID, sensorkalibreringer, et "enhet er midlertidig deaktivert"-flagg, etc.
Denne informasjonen er et sett med nøkkelverdi-poster, også lagret i CBOR. Vi har ikke mye av denne informasjonen (høyst noen få kilobyte), og den oppdateres sjelden.
I det følgende vil vi kalle det kontekst.

Hvis vi husker hvor denne artikkelen begynte, er det svært viktig å sikre pålitelig datalagring og om mulig kontinuerlig drift selv ved maskinvarefeil/datakorrupsjon.

Hvilke kilder til problemer kan vurderes?

• Slå av under skrive-/sletteoperasjoner. Dette er fra kategorien "det er ingen triks mot brekkjern."
  Informasjon fra diskusjoner på stackexchange: når strømmen er slått av mens du arbeider med flash, fører både sletting (sett til 1) og skriv (sett til 0) til udefinert oppførsel: data kan skrives, delvis skrives (f.eks. overførte vi 10 byte/80 biter) , men ennå ikke bare 45 biter kan skrives), er det også mulig at noen av bitene vil være i en "mellomliggende" tilstand (lesing kan produsere både 0 og 1);
• Feil i selve flashminnet.
  BER, selv om den er veldig lav, kan ikke være lik null;
• Bussfeil
  Data som overføres via SPI er ikke beskyttet på noen måte; både enkeltbitfeil og synkroniseringsfeil kan oppstå - tap eller innsetting av biter (noe som fører til massiv dataforvrengning);
• Andre feil/feil
  Feil i koden, bringebærfeil, romveseninterferens...

Jeg har formulert kravene, hvis oppfyllelse etter min mening er nødvendig for å sikre pålitelighet:

• poster skal umiddelbart inn i flash-minnet, forsinket skriving vurderes ikke; - hvis det oppstår en feil, må den oppdages og behandles så tidlig som mulig; - systemet må om mulig komme seg etter feil.
  (et eksempel fra livet "hvordan det ikke burde være", som jeg tror alle har møtt: etter en nødstart er filsystemet "ødelagt" og operativsystemet starter ikke opp)

Ideer, tilnærminger, refleksjoner

Da jeg begynte å tenke på dette problemet, kom det mange ideer gjennom hodet mitt, for eksempel:

• bruk datakomprimering;
• bruk smarte datastrukturer, for eksempel ved å lagre posthoder separat fra selve postene, slik at hvis det er en feil i en post, kan du lese resten uten problemer;
• bruk bitfelt for å kontrollere fullføringen av opptak når strømmen er slått av;
• lagre sjekksummer for alt;
• bruk en eller annen type støybestandig koding.

Noen av disse ideene ble brukt, mens andre ble besluttet å bli forlatt. La oss gå i rekkefølge.

Datakomprimering

Selve hendelsene som vi registrerer i journalen er ganske like og repeterbare ("kastet en 5 rubelmynt", "trykket på knappen for å gi veksel", ...). Derfor bør kompresjon være ganske effektiv.

Komprimeringsoverheaden er ubetydelig (prosessoren vår er ganske kraftig, selv den første Pi-en hadde en kjerne med en frekvens på 700 MHz, nåværende modeller har flere kjerner med en frekvens på over en gigahertz), valutakursen med lagringen er lav (flere megabyte per sekund), er størrelsen på postene liten. Generelt, hvis komprimering har en innvirkning på ytelsen, vil det bare være positivt. (helt ukritisk, sier bare). I tillegg har vi ikke ekte innebygd, men vanlig Linux - så implementeringen bør ikke kreve mye innsats (det er nok å bare koble til biblioteket og bruke flere funksjoner fra det).

En del av loggen ble tatt fra en fungerende enhet (1.7 MB, 70 tusen oppføringer) og først sjekket for komprimerbarhet ved å bruke gzip, lz4, lzop, bzip2, xz, zstd tilgjengelig på datamaskinen.

• gzip, xz, zstd viste lignende resultater (40Kb).
  Jeg ble overrasket over at den fasjonable xz viste seg her på nivå med gzip eller zstd;
• lzip med standardinnstillinger ga litt dårligere resultater;
• lz4 og lzop viste ikke særlig gode resultater (150Kb);
• bzip2 viste et overraskende godt resultat (18Kb).

Så dataene er komprimert veldig bra.
Så (hvis vi ikke finner fatale feil) vil det være kompresjon! Ganske enkelt fordi mer data får plass på samme flash-stasjon.

La oss tenke på ulempene.

Første problem: vi har allerede blitt enige om at hver post umiddelbart må gå til blink. Vanligvis samler arkiveren inn data fra inndatastrømmen til den bestemmer seg for at det er på tide å skrive i helgen. Vi må umiddelbart motta en komprimert blokk med data og lagre den i ikke-flyktig minne.

Jeg ser tre måter:

1. Komprimer hver post ved å bruke ordbokkomprimering i stedet for algoritmene diskutert ovenfor.
   Det er et helt fungerende alternativ, men jeg liker det ikke. For å sikre et mer eller mindre anstendig komprimeringsnivå, må ordboken "skreddersys" til spesifikke data; enhver endring vil føre til at komprimeringsnivået faller katastrofalt. Ja, problemet kan løses ved å lage en ny versjon av ordboken, men dette er en hodepine - vi må lagre alle versjoner av ordboken; i hver oppføring må vi angi hvilken versjon av ordboken den ble komprimert med...
2. Komprimer hver post ved å bruke "klassiske" algoritmer, men uavhengig av de andre.
   Kompresjonsalgoritmene som vurderes er ikke designet for å fungere med poster av denne størrelsen (ti titalls byte), komprimeringsforholdet vil klart være mindre enn 1 (det vil si å øke datavolumet i stedet for å komprimere);
3. Gjør FLUSH etter hvert opptak.
   Mange komprimeringsbiblioteker har støtte for FLUSH. Dette er en kommando (eller en parameter til komprimeringsprosedyren), ved mottak som danner arkiveren en komprimert strøm slik at den kan brukes til å gjenopprette alle ukomprimerte data som allerede er mottatt. En slik analog sync i filsystemer eller commit i sql.
   Det som er viktig er at påfølgende komprimeringsoperasjoner vil kunne bruke den akkumulerte ordboken og komprimeringsforholdet vil ikke lide like mye som i forrige versjon.

Jeg tror det er åpenbart at jeg valgte det tredje alternativet, la oss se på det mer detaljert.

Funnet flott artikkel om FLUSH i zlib.

Jeg tok en knetest basert på artikkelen, tok 70 tusen loggoppføringer fra en ekte enhet, med en sidestørrelse på 60Kb (vi kommer tilbake til sidestørrelse senere) mottatt:

Innledende data
Komprimering gzip -9 (ingen FLUSH)
zlib med Z_PARTIAL_FLUSH
zlib med Z_SYNC_FLUSH

Volum, KB
1692
40
352
604

Ved første øyekast er prisen FLUSH bidrar med overdrevent høy, men i virkeligheten har vi lite valg - enten å ikke komprimere i det hele tatt, eller å komprimere (og veldig effektivt) med FLUSH. Vi må ikke glemme at vi har 70 tusen poster, redundansen introdusert av Z_PARTIAL_FLUSH er bare 4-5 byte per post. Og kompresjonsforholdet viste seg å være nesten 5:1, noe som er mer enn et utmerket resultat.

Det kan komme som en overraskelse, men Z_SYNC_FLUSH er faktisk en mer effektiv måte å gjøre FLUSH på

Når du bruker Z_SYNC_FLUSH, vil de siste 4 bytene av hver oppføring alltid være 0x00, 0x00, 0xff, 0xff. Og hvis vi kjenner dem, trenger vi ikke å lagre dem, så den endelige størrelsen er bare 324Kb.

Artikkelen jeg lenket til har en forklaring:

En ny type 0-blokk med tomt innhold er lagt til.

En type 0-blokk med tomt innhold består av:

• tre-bits blokkoverskriften;
• 0 til 7 biter lik null, for å oppnå bytejustering;
• fire-byte-sekvensen 00 00 FF FF.

Som du lett kan se, er det fra 4 til 3 nullbiter i den siste blokken før disse 10 bytene. Praksis har imidlertid vist at det faktisk er minst 10 nullbiter.

Det viser seg at slike korte datablokker vanligvis (alltid?) er kodet ved hjelp av en blokk av type 1 (fast blokk), som nødvendigvis ender med 7 nullbiter, og gir totalt 10-17 garanterte nullbiter (og resten vil være null med en sannsynlighet på ca. 50 %).

Så på testdata er det i 100 % av tilfellene en null byte før 0x00, 0x00, 0xff, 0xff, og i mer enn en tredjedel av tilfellene er det to null byte (kanskje faktum er at jeg bruker binær CBOR, og når jeg bruker tekst JSON, vil blokker av type 2 - dynamisk blokk være mer vanlig, henholdsvis blokker uten ytterligere null byte før 0x00, 0x00, 0xff, 0xff ville bli møtt).

Totalt, ved å bruke de tilgjengelige testdataene, er det mulig å passe inn i mindre enn 250Kb med komprimerte data.

Du kan spare litt mer ved å sjonglere litt: for nå ignorerer vi tilstedeværelsen av noen få nullbiter på slutten av blokken, noen få biter på begynnelsen av blokken endres heller ikke...
Men så tok jeg en viljesterk beslutning om å slutte, ellers kunne jeg med denne hastigheten ende opp med å utvikle min egen arkiver.

Totalt, fra testdataene mine, fikk jeg 3-4 byte per skriving, kompresjonsforholdet viste seg å være mer enn 6:1. Jeg skal være ærlig: Jeg forventet ikke et slikt resultat; etter min mening er noe bedre enn 2:1 allerede et resultat som rettferdiggjør bruken av komprimering.

Alt er bra, men zlib (deflate) er fortsatt en arkaisk, velfortjent og litt gammeldags komprimeringsalgoritme. Bare det faktum at de siste 32Kb av den ukomprimerte datastrømmen brukes som en ordbok ser merkelig ut i dag (det vil si at hvis en datablokk er veldig lik det som var i inngangsstrømmen for 40Kb siden, vil den begynne å bli arkivert igjen, og vil ikke referere til en tidligere forekomst). I fasjonable moderne arkivere blir ordbokstørrelsen ofte målt i megabyte i stedet for kilobyte.

Så vi fortsetter vår ministudie av arkivarer.

Deretter testet vi bzip2 (husk, uten FLUSH viste den et fantastisk kompresjonsforhold på nesten 100:1). Dessverre presterte det veldig dårlig med FLUSH; størrelsen på de komprimerte dataene viste seg å være større enn de ukomprimerte dataene.

Mine antagelser om årsakene til feilen

Libbz2 tilbyr bare ett flush-alternativ, som ser ut til å tømme ordboken (analogt med Z_FULL_FLUSH i zlib); det er ikke snakk om noen effektiv komprimering etter dette.

Og den siste som ble testet var zstd. Avhengig av parameterne, komprimerer den enten på nivået av gzip, men mye raskere, eller bedre enn gzip.

Dessverre, med FLUSH fungerte det ikke særlig bra: størrelsen på de komprimerte dataene var omtrent 700Kb.

Я stilte et spørsmål på prosjektets github-side fikk jeg et svar om at du burde regne med opptil 10 byte med tjenestedata for hver blokk med komprimerte data, som er nær de oppnådde resultatene; det er ingen måte å ta igjen deflater.

Jeg bestemte meg for å stoppe på dette tidspunktet i mine eksperimenter med arkivere (la meg minne deg på at xz, lzip, lzo, lz4 ikke viste seg selv på teststadiet uten FLUSH, og jeg vurderte ikke mer eksotiske komprimeringsalgoritmer).

La oss gå tilbake til arkiveringsproblemer.

Det andre (som de sier i rekkefølge, ikke i verdi) problemet er at de komprimerte dataene er en enkelt strøm, der det hele tiden er referanser til tidligere seksjoner. Derfor, hvis en del av komprimerte data blir skadet, mister vi ikke bare den tilhørende blokken med ukomprimerte data, men også alle påfølgende.

Det er en tilnærming for å løse dette problemet:

1. Forhindre at problemet oppstår - legg til redundans til de komprimerte dataene, som lar deg identifisere og korrigere feil; vi skal snakke om dette senere;
2. Minimer konsekvensene hvis det oppstår et problem
   Vi har allerede sagt tidligere at du kan komprimere hver datablokk uavhengig, og problemet vil forsvinne av seg selv (skade på dataene til en blokk vil føre til tap av data bare for denne blokken). Dette er imidlertid et ekstremt tilfelle der datakomprimering vil være ineffektiv. Den motsatte ytterligheten: bruk alle 4 MB av brikken vår som et enkelt arkiv, noe som vil gi oss utmerket komprimering, men katastrofale konsekvenser i tilfelle datakorrupsjon.
   Ja, det er nødvendig med et kompromiss når det gjelder pålitelighet. Men vi må huske at vi utvikler et datalagringsformat for ikke-flyktig minne med ekstremt lav BER og en deklarert datalagringsperiode på 20 år.

Under eksperimentene oppdaget jeg at mer eller mindre merkbare tap i komprimeringsnivået begynner på blokker med komprimerte data mindre enn 10 KB i størrelse.
Det ble tidligere nevnt at minnet som brukes er sidesøkt; jeg ser ingen grunn til at korrespondansen "én side - én blokk med komprimerte data" ikke skal brukes.

Det vil si at minimum rimelig sidestørrelse er 16Kb (med en reserve for serviceinformasjon). En så liten sidestørrelse pålegger imidlertid betydelige begrensninger på den maksimale poststørrelsen.

Selv om jeg ennå ikke forventer poster større enn noen få kilobyte i komprimert form, bestemte jeg meg for å bruke 32Kb-sider (for totalt 128 sider per brikke).

Oppsummering:

• Vi lagrer data komprimert ved hjelp av zlib (deflate);
• For hver oppføring setter vi Z_SYNC_FLUSH;
• For hver komprimerte post trimmer vi de etterfølgende bytene (f.eks. 0x00, 0x00, 0xff, 0xff); i overskriften angir vi hvor mange byte vi kuttet av;
• Vi lagrer data på 32Kb sider; det er en enkelt strøm av komprimerte data inne på siden; På hver side starter vi komprimering igjen.

Og før jeg avslutter med komprimering, vil jeg gjøre oppmerksom på at vi bare har noen få byte med komprimerte data per post, så det er ekstremt viktig å ikke blåse opp tjenesteinformasjonen, hver byte teller her.

Lagring av dataoverskrifter

Siden vi har poster med variabel lengde, må vi på en eller annen måte bestemme plasseringen/grensene for poster.

Jeg kjenner tre tilnærminger:

1. Alle poster lagres i en kontinuerlig strøm, først er det en postoverskrift som inneholder lengden, og deretter selve posten.
   I denne utførelsesformen kan både overskrifter og data være av variabel lengde.
   I hovedsak får vi en enkeltlenket liste som brukes hele tiden;
2. Overskrifter og selve postene lagres i separate strømmer.
   Ved å bruke overskrifter med konstant lengde sikrer vi at skade på en topptekst ikke påvirker de andre.
   En lignende tilnærming brukes for eksempel i mange filsystemer;
3. Poster lagres i en kontinuerlig strøm, postgrensen bestemmes av en bestemt markør (et tegn/sekvens av tegn som er forbudt innenfor datablokker). Hvis det er en markør inne i posten, erstatter vi den med en sekvens (unnslipper den).
   En lignende tilnærming brukes for eksempel i PPP-protokollen.

Jeg skal illustrere.

Alternativ 1:

Alt er veldig enkelt her: Når vi kjenner lengden på posten, kan vi beregne adressen til neste overskrift. Så vi går gjennom overskriftene til vi møter et område fylt med 0xff (fritt område) eller slutten av siden.

Alternativ 2:

På grunn av variabel postlengde kan vi ikke på forhånd si hvor mange poster (og dermed overskrifter) vi trenger per side. Du kan spre overskriftene og selve dataene på forskjellige sider, men jeg foretrekker en annen tilnærming: vi plasserer både overskriftene og dataene på én side, men overskriftene (av konstant størrelse) kommer fra begynnelsen av siden, og data (av variabel lengde) kommer fra slutten. Så snart de "møtes" (det er ikke nok ledig plass til en ny oppføring), anser vi denne siden som komplett.

Alternativ 3:

Det er ikke nødvendig å lagre lengden eller annen informasjon om plasseringen av dataene i overskriften; markører som indikerer grensene til postene er nok. Dataene må imidlertid behandles ved skriving/lesing.
Jeg ville brukt 0xff som markør (som fyller siden etter sletting), så det ledige området vil definitivt ikke bli behandlet som data.

Sammenligningstabell:

Alternativ 1
Alternativ 2
Alternativ 3

Feiltoleranse
-
+
+

tetthet
+
-
+

Kompleksiteten i implementeringen
*
**
**

Alternativ 1 har en fatal feil: Hvis noen av overskriftene er skadet, blir hele den påfølgende kjeden ødelagt. De gjenværende alternativene lar deg gjenopprette noen data selv i tilfelle massiv skade.
Men her er det på sin plass å huske at vi bestemte oss for å lagre dataene i en komprimert form, og så mister vi alle dataene på siden etter en "ødelagt" post, så selv om det er et minus i tabellen, gjør vi det ikke ta hensyn til det.

Kompakthet:

• i det første alternativet trenger vi bare å lagre lengden i overskriften; hvis vi bruker heltall med variabel lengde, kan vi i de fleste tilfeller klare oss med én byte;
• i det andre alternativet må vi lagre startadressen og lengden; posten må være en konstant størrelse, jeg anslår 4 byte per post (to byte for forskyvningen og to byte for lengden);
• det tredje alternativet trenger bare ett tegn for å indikere starten på opptaket, pluss at selve opptaket vil øke med 1-2 % på grunn av skjerming. Generelt omtrent paritet med det første alternativet.

Til å begynne med vurderte jeg det andre alternativet som det viktigste (og skrev til og med implementeringen). Jeg forlot det først da jeg endelig bestemte meg for å bruke komprimering.

Kanskje en dag vil jeg fortsatt bruke et lignende alternativ. Hvis jeg for eksempel må forholde meg til datalagring for et skip som reiser mellom Jorden og Mars, vil det være helt andre krav til pålitelighet, kosmisk stråling, ...

Når det gjelder det tredje alternativet: Jeg ga det to stjerner for vanskeligheten med å implementere rett og slett fordi jeg ikke liker å rote rundt med skjerming, endre lengden i prosessen osv. Ja, kanskje jeg er partisk, men jeg må skrive koden - hvorfor tvinge deg selv til å gjøre noe du ikke liker.

Oppsummering: Vi velger lagringsalternativet i form av kjeder "header med lengde - data av variabel lengde" på grunn av effektivitet og enkel implementering.

Bruke bitfelt for å overvåke suksessen til skriveoperasjoner

Jeg husker ikke nå hvor jeg fikk ideen, men den ser omtrent slik ut:
For hver oppføring tildeler vi flere biter for å lagre flagg.
Som vi sa tidligere, etter sletting er alle biter fylt med 1-er, og vi kan endre 1 til 0, men ikke omvendt. Så for "flagget er ikke satt" bruker vi 1, for "flagget er satt" bruker vi 0.

Slik kan det se ut å sette en plate med variabel lengde i flash:

1. Sett flagget "lengdeopptak har startet";
2. Registrer lengden;
3. Sett "dataopptaket har startet"-flagget;
4. Vi registrerer data;
5. Angi flagget "opptak avsluttet".

I tillegg vil vi ha et "feil oppstod"-flagg, for totalt 4-bits flagg.

I dette tilfellet har vi to stabile tilstander "1111" - opptaket har ikke startet og "1000" - opptaket var vellykket; i tilfelle et uventet avbrudd i opptaksprosessen vil vi motta mellomtilstander, som vi deretter kan oppdage og behandle.

Tilnærmingen er interessant, men den beskytter bare mot plutselige strømbrudd og lignende feil, noe som selvfølgelig er viktig, men dette er langt fra den eneste (eller til og med hoved) årsaken til mulige feil.

Oppsummering: La oss gå videre i jakten på en god løsning.

Sjekksummer

Sjekksummer gjør det også mulig å forsikre seg (med rimelig sannsynlighet) at vi leser nøyaktig det som skulle vært skrevet. Og i motsetning til bitfeltene som er omtalt ovenfor, fungerer de alltid.

Hvis vi vurderer listen over potensielle kilder til problemer som vi diskuterte ovenfor, er kontrollsummen i stand til å gjenkjenne en feil uavhengig av opprinnelsen (unntatt kanskje for ondsinnede romvesener - de kan også forfalske sjekksummen).

Så hvis målet vårt er å bekrefte at dataene er intakte, er kontrollsummer en god idé.

Valget av algoritme for å beregne kontrollsummen reiste ingen spørsmål - CRC. På den ene siden gjør matematiske egenskaper det mulig å fange visse typer feil 100 %; på den annen side, på tilfeldige data viser denne algoritmen vanligvis sannsynligheten for kollisjoner som ikke er mye større enn den teoretiske grensen . Det er kanskje ikke den raskeste algoritmen, og det er heller ikke alltid minimum når det gjelder antall kollisjoner, men den har en veldig viktig kvalitet: i testene jeg møtte var det ingen mønstre der den klart mislyktes. Stabilitet er hovedkvaliteten i dette tilfellet.

Eksempel på en volumetrisk studie: del 1, del 2 (lenker til narod.ru, beklager).

Oppgaven med å velge en sjekksum er imidlertid ikke fullført; CRC er en hel familie av sjekksummer. Du må bestemme lengden, og deretter velge et polynom.

Å velge sjekksumlengde er ikke et så enkelt spørsmål som det ser ut ved første øyekast.

La meg illustrere:
La oss ha sannsynligheten for en feil i hver byte og en ideell kontrollsum, la oss beregne gjennomsnittlig antall feil per million poster:

Data, byte
Sjekksum, byte
Uoppdagede feil
Falske feilregistreringer
Totalt 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 ut til at alt er enkelt - avhengig av lengden på dataene som beskyttes, velg lengden på sjekksummen med et minimum av feil positive - og trikset er i bagasjen.

Det oppstår imidlertid et problem med korte sjekksummer: selv om de er flinke til å oppdage enkeltbitfeil, kan de med ganske stor sannsynlighet godta helt tilfeldige data som korrekte. Det var allerede en artikkel om Habré som beskrev problem i det virkelige liv.

Derfor, for å gjøre en tilfeldig sjekksum-match nesten umulig, må du bruke sjekksummer som er 32 biter eller lengre. (for lengder større enn 64 biter brukes vanligvis kryptografiske hash-funksjoner).

Til tross for at jeg skrev tidligere at vi for all del må spare plass, vil vi fortsatt bruke en 32-bits kontrollsum (16 biter er ikke nok, sannsynligheten for en kollisjon er mer enn 0.01%; og 24 biter, ettersom de si, er verken her eller der).

En innvending kan dukke opp her: Lagret vi hver byte ved valg av komprimering for nå å gi 4 byte på en gang? Ville det ikke vært bedre å ikke komprimere eller legge til en kontrollsum? Selvfølgelig ikke, ingen kompresjon betyr ikke, at vi ikke trenger integritetskontroll.

Når vi velger et polynom, vil vi ikke finne opp hjulet på nytt, men ta den nå populære CRC-32C.
Denne koden oppdager 6 bits feil på pakker på opptil 22 byte (kanskje det vanligste tilfellet for oss), 4 bits feil på pakker på opptil 655 byte (også et vanlig tilfelle for oss), 2 eller et hvilket som helst oddetall bitfeil på pakker av enhver rimelig lengde.

Hvis noen er interessert i detaljene

Wikipedia-artikkel om CRC.

Kode parametere crc-32c på Koopmans nettsted - kanskje den ledende CRC-spesialisten på planeten.

В artikkelen hans det er en annen interessant kode, som gir litt bedre parametere for pakkelengdene som er relevante for oss, men jeg anså ikke forskjellen som betydelig, og jeg var kompetent nok til å velge tilpasset kode i stedet for den standard og godt undersøkte.

Siden våre data er komprimert, oppstår spørsmålet: skal vi beregne kontrollsummen for komprimerte eller ukomprimerte data?

Argumenter for å beregne kontrollsummen av ukomprimerte data:

• Vi må til syvende og sist sjekke sikkerheten til datalagring - så vi sjekker den direkte (samtidig vil mulige feil ved implementering av komprimering/dekompresjon, skade forårsaket av ødelagt minne, etc. bli sjekket);
• Deflate-algoritmen i zlib har en ganske moden implementering og burde ikke faller med "skjeve" inngangsdata; dessuten er den ofte i stand til uavhengig å oppdage feil i inngangsstrømmen, noe som reduserer den totale sannsynligheten for å ikke oppdage en feil (utførte en test med å invertere en enkelt bit i en kort post, zlib oppdaget en feil i omtrent en tredjedel av tilfellene).

Argumenter mot å beregne kontrollsummen av ukomprimerte data:

• CRC er "skreddersydd" spesifikt for de få bitfeilene som er karakteristiske for flashminne (en bitfeil i en komprimert strøm kan forårsake en massiv endring i utgangsstrømmen, som vi rent teoretisk kan "fange" en kollisjon på);
• Jeg liker egentlig ikke ideen om å sende potensielt ødelagte data til dekomprimeringen, Hvem vethvordan han vil reagere.

I dette prosjektet bestemte jeg meg for å avvike fra den allment aksepterte praksisen med å lagre en sjekksum av ukomprimerte data.

Oppsummering: Vi bruker CRC-32C, vi beregner kontrollsummen fra dataene i den formen de er skrevet til å blinke (etter komprimering).

Overflødighet

Bruken av redundant koding eliminerer selvfølgelig ikke tap av data, men det kan betydelig (ofte i mange størrelsesordener) redusere sannsynligheten for uopprettelig datatap.

Vi kan bruke ulike typer redundans for å rette opp feil.
Hamming-koder kan korrigere enkeltbitfeil, Reed-Solomon-tegnkoder, flere kopier av data kombinert med kontrollsummer, eller kodinger som RAID-6 kan hjelpe til med å gjenopprette data selv i tilfelle massiv korrupsjon.
I utgangspunktet var jeg forpliktet til den utbredte bruken av feilbestandig koding, men så innså jeg at vi først må ha en ide om hvilke feil vi ønsker å beskytte oss mot, og deretter velge koding.

Vi sa tidligere at feil må fanges opp så raskt som mulig. På hvilke punkter kan vi støte på feil?

1. Uferdig opptak (av en eller annen grunn på tidspunktet for innspillingen ble strømmen slått av, bringebæret frøs, ...)
   Akk, i tilfelle en slik feil gjenstår det bare å ignorere ugyldige poster og vurdere dataene som er tapt;
2. Skrivefeil (av en eller annen grunn var det som ble skrevet til flash-minnet ikke det som ble skrevet)
   Vi kan umiddelbart oppdage slike feil hvis vi gjør en testlesing umiddelbart etter opptak;
3. Forvrengning av data i minnet under lagring;
4. Lesefeil
   For å korrigere det, er det nok å gjenta avlesningen flere ganger i tilfelle kontrollsummismatch.

Det vil si at bare feil av den tredje typen (spontan korrupsjon av data under lagring) ikke kan rettes uten feilbestandig koding. Det ser ut til at slike feil fortsatt er ekstremt usannsynlige.

Oppsummering: det ble besluttet å forlate redundant koding, men hvis operasjonen viser feilen i denne avgjørelsen, gå tilbake til å vurdere problemet (med allerede akkumulert statistikk over feil, som lar deg velge den optimale typen koding).

Andre

Selvfølgelig tillater ikke formatet til artikkelen oss å rettferdiggjøre hver bit i formatet (og kreftene mine har allerede tatt slutt), så jeg skal kort gå gjennom noen punkter som ikke er berørt tidligere.

• Det ble besluttet å gjøre alle sider «like»
  Det vil si at det ikke blir noen spesielle sider med metadata, separate tråder osv., men i stedet en enkelt tråd som omskriver alle sider etter tur.
  Dette sikrer jevn slitasje på sidene, ingen enkelt feil, og jeg liker det;
• Det er viktig å sørge for versjonering av formatet.
  Et format uten et versjonsnummer i overskriften er ond!
  Det er nok å legge til et felt med et bestemt magisk nummer (signatur) til sideoverskriften, som vil indikere versjonen av formatet som brukes (Jeg tror ikke at det i praksis vil være et dusin av dem);
• Bruk en overskrift med variabel lengde for poster (som det er mange av), prøv å gjøre den 1 byte lang i de fleste tilfeller;
• For å kode lengden på overskriften og lengden på den trimmede delen av den komprimerte posten, bruk binære koder med variabel lengde.

Hjalp mye online generator Huffman-koder. På bare noen få minutter kunne vi velge de nødvendige kodene med variabel lengde.

Beskrivelse av datalagringsformat

Byte rekkefølge

Felt større enn én byte lagres i big-endian-format (nettverksbyte-rekkefølge), det vil si at 0x1234 skrives som 0x12, 0x34.

Paginering

Alt flashminne er delt inn i sider av samme størrelse.

Standard sidestørrelse er 32Kb, men ikke mer enn 1/4 av den totale størrelsen på minnebrikken (for en 4MB-brikke oppnås 128 sider).

Hver side lagrer data uavhengig av de andre (det vil si at data på én side ikke refererer til data på en annen side).

Alle sidene er nummerert i naturlig rekkefølge (i stigende rekkefølge av adresser), starter med nummer 0 (side null starter på adresse 0, første side starter på 32Kb, andre side starter på 64Kb osv.)

Minnebrikken brukes som en syklisk buffer (ringbuffer), det vil si at først skriving går til sidenummer 0, deretter nummer 1, ..., når vi fyller siste side starter en ny syklus og opptaket fortsetter fra side null .

Inne på siden

På begynnelsen av siden lagres en 4-byte sideoverskrift, deretter en overskriftssjekksum (CRC-32C), deretter lagres poster i "header, data, checksum"-formatet.

Sidetittelen (skitten grønn i diagrammet) består av:

• to-byte Magic Number-felt (også et tegn på formatversjonen)
  for gjeldende versjon av formatet det beregnes som 0xed00 ⊕ номер страницы;
• to-byte teller "Side versjon" (minne omskrive syklus nummer).

Oppføringer på siden lagres i komprimert form (deflate-algoritmen brukes). Alle poster på én side komprimeres i én tråd (en felles ordbok brukes), og på hver ny side starter komprimeringen på nytt. Det vil si at for å dekomprimere en post, kreves alle tidligere poster fra denne siden (og bare denne).

Hver post vil bli komprimert med Z_SYNC_FLUSH-flagget, og på slutten av den komprimerte strømmen vil det være 4 byte 0x00, 0x00, 0xff, 0xff, muligens etterfulgt av en eller to flere nullbyte.
Vi forkaster denne sekvensen (4, 5 eller 6 byte lang) når vi skriver til flashminne.

Oppføringshodet er 1, 2 eller 3 byte som lagrer:

• en bit (T) som indikerer typen post: 0 - kontekst, 1 - log;
• et felt med variabel lengde (S) fra 1 til 7 biter, som definerer lengden på overskriften og "halen" som må legges til posten for dekompresjon;
• rekordlengde (L).

S-verditabell:

S
Topptekstlengde, byte
Forkastet på skriv, 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øvde å illustrere, jeg vet ikke hvor tydelig det ble:

Gult her indikerer T-feltet, hvitt S-feltet, grønt L (lengden på de komprimerte dataene i byte), blå de komprimerte dataene, rødt de siste bytene til de komprimerte dataene som ikke er skrevet til flashminnet.

Dermed kan vi skrive posthoder av den vanligste lengden (opptil 63+5 byte i komprimert form) i en byte.

Etter hver post lagres en CRC-32C sjekksum, der den inverterte verdien av forrige sjekksum brukes som startverdi (init).

CRC har egenskapen "varighet", følgende formel fungerer (pluss eller minus bitinversjon i prosessen): .
Det vil si at vi faktisk beregner CRC for alle tidligere byte med overskrifter og data på denne siden.

Direkte etter kontrollsummen er overskriften til neste post.

Headeren er utformet på en slik måte at dens første byte alltid er forskjellig fra 0x00 og 0xff (hvis vi i stedet for den første byten i headeren møter 0xff, betyr dette at dette er et ubrukt område; 0x00 signaliserer en feil).

Eksempel algoritmer

Leser fra Flash-minne

Enhver avlesning kommer med en kontrollsum.
Hvis kontrollsummen ikke stemmer, gjentas avlesningen flere ganger i håp om å lese riktige data.

(dette er fornuftig, Linux cacher ikke lesinger fra NOR Flash, testet)

Skriv til flash-minnet

Vi registrerer dataene.
La oss lese dem.

Hvis de leste dataene ikke stemmer med de skrevne dataene, fyller vi området med nuller og signaliserer en feil.

Klargjøring av ny mikrokrets for drift

For initialisering skrives en header med versjon 1 til den første (eller snarere null) siden.
Etter det skrives den innledende konteksten til denne siden (inneholder UUID for maskinen og standardinnstillinger).

Det er det, flash-minnet er klart til bruk.

Laster maskinen

Ved lasting leses de første 8 bytene av hver side (overskrift + CRC), sider med et ukjent magisk nummer eller en feil CRC ignoreres.
Fra de "riktige" sidene velges sider med maksimal versjon, og siden med høyest nummer hentes fra dem.
Den første posten leses, riktigheten av CRC og tilstedeværelsen av "kontekst"-flagget kontrolleres. Hvis alt er i orden, anses denne siden som oppdatert. Hvis ikke, ruller vi tilbake til den forrige til vi finner en "live" side.
og på den funnet siden leser vi alle postene, de som vi bruker med "kontekst"-flagget.
Lagre zlib-ordboken (den vil være nødvendig for å legge til denne siden).

Det er det, nedlastingen er fullført, konteksten er gjenopprettet, du kan jobbe.

Legge til en journaloppføring

Vi komprimerer posten med riktig ordbok, spesifiserer Z_SYNC_FLUSH. Vi ser om den komprimerte posten passer på gjeldende side.
Hvis det ikke passer (eller det var CRC-feil på siden), start en ny side (se nedenfor).
Vi skriver ned posten og CRC. Hvis det oppstår en feil, start en ny side.

Ny side

Vi velger en gratisside med minimumsantallet (vi anser en gratisside som en side med feil kontrollsum i overskriften eller med en versjon mindre enn den gjeldende). Hvis det ikke finnes slike sider, velg siden med minimum antall fra de som har en versjon lik den gjeldende.
Vi sletter den valgte siden. Vi sjekker innholdet med 0xff. Hvis noe er galt, ta neste gratisside osv.
Vi skriver en overskrift på den slettede siden, den første oppføringen er den nåværende tilstanden til konteksten, den neste er den uskrevne loggoppføringen (hvis det er en).

Formatanvendbarhet

Etter min mening viste det seg å være et godt format for å lagre mer eller mindre komprimerbare informasjonsstrømmer (ren tekst, JSON, MessagePack, CBOR, evt. protobuf) i NOR Flash.

Selvfølgelig er formatet "skreddersydd" for SLC NOR Flash.

Den bør ikke brukes med høye BER-medier som NAND eller MLC NOR (er slikt minne i det hele tatt tilgjengelig for salg? Jeg har bare sett det nevnt i arbeider med korreksjonskoder).

Dessuten bør den ikke brukes med enheter som har sin egen FTL: USB-flash, SD, MicroSD, etc (for slikt minne opprettet jeg et format med en sidestørrelse på 512 byte, en signatur på begynnelsen av hver side og unike rekordnummer - noen ganger var det mulig å gjenopprette alle dataene fra en "feil" flash-stasjon ved enkel sekvensiell lesing).

Avhengig av oppgavene kan formatet brukes uten endringer på flash-stasjoner fra 128Kbit (16Kb) til 1Gbit (128MB). Om ønskelig kan du bruke den på større sjetonger, men du må sannsynligvis justere sidestørrelsen (Men her oppstår allerede spørsmålet om økonomisk gjennomførbarhet; prisen for stort volum NOR Flash er ikke oppmuntrende).

Hvis noen synes formatet er interessant og vil bruke det i et åpent prosjekt, skriv, jeg skal prøve å finne tiden, polere koden og legge den ut på github.

Konklusjon

Som du kan se, viste formatet seg til slutt å være enkelt og til og med kjedelig.

Det er vanskelig å gjenspeile utviklingen av mitt synspunkt i en artikkel, men tro meg: I utgangspunktet ønsket jeg å lage noe sofistikert, uforgjengelig, i stand til å overleve til og med en atomeksplosjon i umiddelbar nærhet. Men fornuften (håper jeg) vant fortsatt og gradvis ble prioriteringene skiftet mot enkelhet og kompakthet.

Kan det være at jeg tok feil? Ja sikkert. Det kan for eksempel godt vise seg at vi kjøpte et parti med mikrokretser av lav kvalitet. Eller av en annen grunn vil ikke utstyret oppfylle forventningene til pålitelighet.

Har jeg en plan for dette? Jeg tror at etter å ha lest artikkelen er du ikke i tvil om at det er en plan. Og ikke engang alene.

På et litt mer seriøst notat ble formatet utviklet både som et arbeidsalternativ og som en "prøveballong".

For øyeblikket fungerer alt på bordet bra, bokstavelig talt her om dagen vil løsningen bli distribuert (omtrent) på hundrevis av enheter, la oss se hva som skjer i "kamp" operasjon (heldigvis håper jeg formatet lar deg oppdage feil på en pålitelig måte; slik at du kan samle full statistikk). Om noen måneder vil det være mulig å trekke konklusjoner (og hvis du er uheldig, enda tidligere).

Hvis det, basert på resultatene av bruk, oppdages alvorlige problemer og det kreves forbedringer, vil jeg definitivt skrive om det.

Litteratur

Jeg ønsket ikke å lage en lang kjedelig liste over brukte verk; tross alt har alle Google.

Her bestemte jeg meg for å legge igjen en liste over funn som virket spesielt interessante for meg, men gradvis migrerte de direkte inn i artikkelens tekst, og ett element ble igjen på listen:

1. Nytte infgen fra forfatteren zlib. Kan tydelig vise innholdet i deflate/zlib/gzip-arkiver. Hvis du må forholde deg til den interne strukturen til deflate (eller gzip) formatet, anbefaler jeg det på det sterkeste.

Kilde: www.habr.com