Pas historia

Ka janë automate tregtare të zhvilluar vetë. Brenda ka Raspberry Pi dhe pak lidhje në një pllakë të veçantë. Janë të lidhura një pranues monedhash, një pranues bankar, një terminal bankar... Të gjitha kontrollohen nga një program të shkruar vetë. Historia e plotë e punës regjistrohet në një ditar në një flash drive (MicroSD), i cili pastaj transferohet përmes internetit (nëpërmjet një modemi USB) në një server ku ruhet në një database. Informacioni për shitjet ngarkohet në 1C, gjithashtu ka një ndërfaqe të thjeshtë në web për monitorim etj.

Pra, ditari është jetik — për llogaritje (aty ka të ardhurat, shitjet etj.), monitorim (të gjithë defektet e mundshme dhe rrethana të tjera të paparashikuara); mund të thuhet se kjo është e gjitha informacioni që ne kemi për këtë automat.

Problemi

Flash drive-t tregohen si disqe shumë të pasigurt. Ato dështojnë me një rregullshmëri të admirueshme. Kjo çon si në pezullimin e automateve, ashtu edhe (nëse për ndonjë arsye ditari nuk mund të dërgohet online) në humbjen e të dhënave.

Kjo nuk është hera e parë që përdorim flash drive, më parë kemi pasur një projekt tjetër me më shumë se njëqind pajisje, ku ditari ruhej në flash drive USB, aty gjithashtu ishin probleme me besueshmërinë, herë pas here numri i pajisjeve të prishura arrinte disa dhjetëra. Provuam flash drive të ndryshëm, përfshirë ato të markave me memorie SLC, disa modele ishin më të besueshme se të tjera, por zëvendësimi i flash drive-ve nuk e zgjidhi problemin në mënyrë radikale.

Kujdes! Një longread! Nëse ju nuk jeni të interesuar për "pse", por jeni vetëm të interesuar për "si", mund të shkoni menjëherë në fund të artikullit.

Zgjidhja

E para që më vije në mendje: të heqim dorë nga MicroSD, të vendosim, për shembull, SSD dhe të startojmë nga ai. Teorikisht është e mundur, ndoshta, por relativisht e shtrenjtë, dhe as nuk është aq e besueshme (shtohet një adapter USB-SATA; për SSD të lira statistikat e dështimeve gjithashtu nuk janë inkurajuese).

USB HDD gjithashtu nuk duket si një zgjidhje tërheqëse.

Prandaj erdhëm në këtë variant: lëvizni me MicroSD, por t’i përdorim ato në mënyrë read-only, dhe të ruajmë ditarin e punës (dhe informacione të tjera unike për pajisjen specifike — numri serial, kalibrimet e sensorëve, etj.) diku tjetër.

Tematika e sistemit të skedave read-only për Raspberry Pi është studiuar për së mbari, nuk do të ndalem në detajet e realizimit në këtë artikull. (por nëse ka interes — ndoshta do të shkruaj një mini-artikull mbi këtë temë). Një moment i vetëm që duam të theksojmë: si nga përvoja personale, ashtu edhe nga feedback-u i atyre që e kanë zbatuar, ka një fitim në besueshmëri. Po, nuk mund të eliminohemi plotësisht nga defektet, megjithatë reduktimi i frekuencës së tyre është plotësisht i realizueshëm. Dhe gjithashtu kartat bëhen të unifikuara, që e thjeshtojnë ndjeshëm zëvendësimin për personelin mbështetës.

Pjesa hardware

Nuk kishte dyshime të mëdha për tipusin e memories — NOR Flash.
Argumentet:

• lidhosje e thjeshtë (më shpesh autobusi SPI, përvoja e përdorimit të të cilit tashmë është, kështu që nuk parashikohet ndonjë problem "harduerike");
• çmim i qeshur;
• protokolli standard i punës (implementimi është tashmë në bërthamën e Linux, nëse dëshiron, mund të marrësh një palë të jashtme, që gjithashtu janë të pranishme, ose madje të shkruash të tuajën, pasi gjithçka është e thjeshtë);
• besueshmëria dhe burimi:
  nga fleta e të dhënave tipike: të dhënat ruhen për 20 vjet, 100000 cikle fshirje për secilën bllok;
  nga burime të jashtme: BER shumë i ulët, postulon se nuk është e nevojshme për kodet e korrigjimit të gabimeve (në disa punime shqyrtohet ECC për NOR, por zakonisht aty ku merret në konsideratë MLC NOR, ndodh edhe kjo).

Le ta llogarisim kërkesat për vëllimin dhe burimin.

Dëshirojmë që të dhënat të ruajten garantuar për disa ditë. Kjo është e nevojshme në mënyrë që në rast të ndonjë problemi me lidhjen, historia e shitjeve të mos humbasë. Do të orientoheni për 5 ditë, për këtë periudhë (madje duke marrë parasysh fundjavët dhe festat) mund të zgjidhet problemi.

Tani për tani mbledhim rreth 100 KB ditarin (3-4 mijë regjistrime) për ditë, por gradualisht ky numër po rritet — po rritet detajizimi, po shtohen ngjarje të reja. Për më tepër, ndonjëherë ka pikë të papritura (ndonjë sensor fillon të dërgojë alarmet e rreme, për shembull). Do të llogarisim për 10 mijë regjistrime me 100 byte — një megabajt në ditë.

Pra, gjithsej del 5 MB të dhënash të pastër (të kompresueshme) . Këtyre i shtohet (vlerësim i qartë) 1 MB të dhëna shërbimi.

Kjo do të thotë se na nevojitet një mikroçip prej 8 MB nëse nuk përdorim kompresimin, ose 4 MB nëse përdorim. Numra të realizueshëm për këtë tip memorjeje.

Sa i përket burimit: nëse ne e planifikojmë që memorja të riprogramohet tërë herë më pak se një herë në 5 ditë, atëherë për 10 vjet shërbimi ne marrim më pak se një mijë cikle riprogramimi.
Të kujtoj, prodhuesi premton njëqind mijë.

Një pak për NOR vs NAND

Sotiria, padyshim, është më e njohur memori NAND, por për këtë projekt nuk do ta përdorja: NAND, në krahasim me NOR, patjetër kërkon përdorimin e kodëve për korrigjimin e gabimeve, tabelave të bllokave me gabime etj., dhe zakonisht ka më shumë pinë.

Si disavantazhe të NOR mund të përmenden:

• kapacitet i vogël (dhe, për rrjedhojë, çmimi i lartë për megabajt);
• shpejtësi e ulët e transferimit (në shumë mënyra për shkak se përdoret një ndërfaqe seriale, zakonisht SPI ose I2C);
• fshirje e ngadaltë (varësisht nga madhësia e bllokut, merr nga pjesë të sekondës deri në disa sekonda).

Nuk duket se ka diçka kritike për ne, kështu që vazhdojmë.

Nëse jeni të interesuar për detajet, është zgjedhur çipi at25df321a (megjithatë, kjo nuk është thelbësore, në treg ka shumë analoge, të përputhshme për pinout dhe sistem komandash; madje edhe nëse dëshirojmë të vendosim një çip nga një prodhues tjetër dhe/ose me një kapacitet tjetër, do të funksionojë pa ndryshuar kodin).

Unë përdor drivin e integruar në kernelin e Linux, në Raspberry për shkak të mbështetjes të overlay të pemës së pajisjeve është shumë e thjeshtë — thjesht duhet të vendosni overlay të kompiluar në /boot/overlays dhe të modifikoni pak /boot/config.txt.

Shembuj i skedarit dts

Sinqerisht, nuk jam i sigurt se është shkruar pa gabime, por funksionon.

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

Dhe një rresht në config.txt

dtoverlay=at25:spimaxfrequency=50000000

Përshkrimin e lidhjes së çipit me Raspberry Pi e lë mënjanë. Në një anë, nuk jam specialist në elektronikë, në anën tjetër — këtu gjithçka është banale madje edhe për mua: çipi ka vetëm 8 pinë, nga të cilat na nevojiten toka, energjia, SPI (CS, SI, SO, SCK); nivelet përputhen me ato të Raspberry Pi, nuk kërkohet ndonjë lidhje shtesë — thjesht lidhni këto 6 kontakte.

Vendosja e detyrës

Si zakonisht, përcaktimi i detyrës kalon disa iteracione, më duket se ka ardhur koha për një tjetër. Pra, le të ndalojmë, të mbledhim bashkë atë që është shkruar tashmë, dhe të qartësojmë detajet e mbetura në hije.

Kështu, ne përcaktoi se regjistri do të ruhen në SPI NOR Flash.

Çfarë është NOR Flash për ata që nuk e dinë

Ky është një memories që nuk humb të dhënat, me të cilat mund të kryejmë tre operacione:

1. Leximi:
   Leximi më i zakonshëm: dërgojmë adresën dhe lexojmë aq bite sa na nevojitet;
2. Shkrimi:
   Shkrimi në NOR flash duket si e zakonshmja, por ka një veçori: mund të ndryshojmë vetëm 1 në 0, por jo anasjelltas. Për shembull, nëse kemi 0x55 në qelizën e memories, pas shkrimit të 0x0f, do të ruhet 0x05 (shih tabelën pak më poshtë);
3. Fshirja:
   Natyrisht, na nevojitet të dimë të bëjmë edhe operacionin e kundërt — të ndryshojmë 0 në 1, për këtë ekziston operacioni i fshirjes. Ndryshe nga dy të parët, ai punon jo me bite, por me blloqe (blloku më i vogël i fshirjes në çipin e zgjedhur është 4kb). Fshirja shkatërron të gjithë bllokun si tërësi dhe ky është mënyra e vetme për të ndryshuar 0 në 1. Prandaj, kur punojmë me flash, shpesh duhet të rregullojmë strukturat e të dhënave në kufirin e bllokut të fshirjes.
   Shkrimi në NOR Flash:

Të dhëna binare

Ishte
01010101

E shkruam
00001111

Nisi
00000101

Regjistri përbëhet nga një sërë shënimesh me gjatësi të ndryshueshme. Gjatësia mesatare e shënimit është rreth 30 bite (ndonëse ndonjëherë ndodhin shënime me gjatësi disa kilobajt). Në këtë rast, ne i trajtojmë ato thjesht si një grup bites, por, nëse jeni të interesuar, brenda shënimeve përdoret CBOR

Përveç regjistrit, na nevojitet të ruajmë disa informacione 'konfigurimi', si ato që përditësohen, ashtu edhe ato që nuk përditësohen: një ID aparati, kalibrimet e sensorëve, një flamur 'pajisja është përkohësisht e fikur', etj.
Këto informacione përbëjnë një grup shënimesh me çelës-vlerë, gjithashtu ruhen në CBOR. Këto informacione nuk janë shumë (maksimumi disa kilobajt), përditësohen jo shpesh.
Në të ardhmen do t'i referohemi asaj si konteksti.

Nëse kujtojmë nga filloi ky artikull, është shumë e rëndësishme të sigurohet besueshmëria e ruajtjes së të dhënave dhe, sa më shumë të jetë e mundur, funksionimi i pandërprerë edhe në rast të gabimeve të harduerit/dëmtimeve të të dhënave.

Cilat janë burimet e problemeve që mund të shqyrtohen?

• Ndryshimi i energjisë në momentin e operacioneve të write/erase. Kjo është diçka si 'nuk ka mjet për të kundërshtuar forcën'.
  Informacioni nga diskutime në stackexchange: në rastin e ndërprerjes së energjisë gjatë punës me flash, si fshirja (vendosja në 1), ashtu edhe shkrimi (vendosja në 0) çojnë në sjellje të paqartë: të dhënat mund të shkruhen, të shkruhen pjesërisht (p.sh., ne dërguam 10 bite/80 bit, dhe arritëm të shkruhen vetëm 45 bite), nuk përjashtohet as që disa bite të jenë në një gjendje 'mesatare' (leximi mund të japë si 0, ashtu edhe 1);
• Gabimet e flashes vetë.
  BER, edhe pse shumë i ulët, nuk mund të jetë i barabartë me zero;
• Gabimet në autobus
  Të dhënat e dërguara përmes SPI nuk janë të mbrojtura, mund të ndodhin si gabime individuale të bitëve, ashtu edhe gabime sinhronizimi — humbja ose shtimi i bitëve (çka çon në ndotjen masive të të dhënave);
• Gabime të tjera/gabime
  Gabimet në kod, "glitches" të Raspberry, ndërhyrja e alienëve...

Unë kam formuluar kërkesat që, sipas mendimit tim, janë të nevojshme për të siguruar besueshmërinë:

• të dhënat duhet të shkruhen menjëherë në memorie flash, regjistrimi i vonuar nuk merret parasysh; - nëse ndodhi një gabim, ai duhet të zbulohet dhe të përpunohen sa më shpejt të jetë e mundur; - sistemi duhet të rikthejë funksionimin pas gabimeve sa më shumë që të jetë e mundur.
  (një shembull në jetën reale "si nuk duhet të jetë", me të cilin mendoj se të gjithë janë përballur: pas një rindizjeje emergjente, sistemi i skedarëve u prish dhe sistemi operativ nuk ngarkohet)

Ide, qasje, mendime

Kur fillova të mendoja për këtë detyrë, në mendjen time kaluan një mori ide, për shembull:

• përdorimi i kompresimit të të dhënave;
• përdorimi i strukturave të dhënash të zgjuara, për shembull, ruajtja e titujve të regjistrimeve veçmas nga vetë regjistrimet, në mënyrë që, në rast gabimi në një regjistrim, të ishte e mundur të lexohej pa probleme të tjerat;
• përdorimi i fushave bit për të kontrolluar përfundimin e regjistrimit në rast ndërprerjeje të energjisë;
• ruajtja e kontrollorëve për gjithçka;
• përdorimi i ndonjë variante të kodimit të qëndresës ndaj ndërhyrjeve.

Disa nga këto ide u përdorën, të tjerat u hodhën poshtë. Le të shkojmë me radhë.

Kompresimi i të dhënave

Ngjarjet që ne regjistrojmë në ditar janë mjaft homogjene dhe të përsëritshme ("hodhëm monedhën 5 rubla", "klikuam butonin për kthimin e monedhës", ...). Prandaj, kompresimi duhet të jetë mjaft efektiv.

Shpenzimet për kompresim janë të papërfillshme (procesori ynë është mjaft i fortë, madje edhe në Pi-në e parë kishte një bërthamë me frekuencë 700MHz, në modelet aktuale disa bërthama me frekuencë mbi një gigahertz), shpejtësia e shkëmbimit me ruajtjen nuk është e lartë (disa megabajt në sekondë), madhësia e regjistrimeve është e vogël. Në përgjithësi, nëse kompresimi ndikon në performancë, do të jetë vetëm pozitiv. (absolutisht jo kritik, thjesht po e konstatoj). Për më tepër, nuk kemi një embedded të vërtetë, por një Linux të zakonshëm — kështu që realizimi nuk duhet të kërkojë shumë përpjekje (mjafton të lidhim bibliotekën dhe të përdorim disa funksione nga ajo).

U mor një copë logu nga një pajisje funksionale (1.7Mb, 70 mijë regjistrime) dhe fillimisht u kontrollua për kompresueshmëri me ndihmën e gzip, lz4, lzop, bzip2, xz, zstd që ishin në kompjuter.

• gzip, xz, zstd treguan rezultate të ngjashme (40Kb).
  Më befasoi që xz e modishme tregoi veten në të njëjtin nivel me gzip ose zstd;
• lzip me cilësime të parazgjedhura dha një rezultat pak më të dobët;
• lz4 dhe lzop treguan rezultat jo shumë të mirë (150Kb);
• bzip2 tregoi një rezultat befasues mirë (18Kb).

Pra, të dhënat kompresohen shumë mirë.
Pra, (nëse nuk gjejmë mangësi fatale) kompresimi për të qenë! Thjesht sepse do të ketë më shumë të dhëna në të njëjtën flash.

Le të mendojmë për disavantazhet.

Problemi i parë: ne tashmë u dakorduam se çdo regjistrim duhet të mbërrijë menjëherë në flash. Zakonisht, një arkivues grumbullon të dhëna nga rrjedha hyrëse deri sa të vendosë se është koha të shkruajë në daljen. Ne, megjithatë, na nevojitet të marrim menjëherë një bllok të dhënash të kompresuara dhe ta ruajmë ato në kujtesën jo të fikshme.

Unë shoh tri mundësi:

1. Të kompresojmë çdo regjistrim me ndihmën e kompresimit me fjalor në vend të algoritemeve të ndryshme të shqyrtuara më sipër.
   Një mundësi mjaft funksionale, por nuk më pëlqen. Për të siguruar një nivel më të pranueshëm kompresimi, fjalori duhet të jetë "i përshtatur" për të dhënat specifike, çdo ndryshim do të rezultojë në rënie katastrofike të nivelit të kompresimit. Po, problemi zgjidhet duke krijuar një version të ri të fjalorit, por kjo është një dhimbje koke — do të na duhen të gjithë versionet e fjalorit; çdo regjistrim do të duhet të tregojë me cilin version të fjalorit është kompresuar...
2. Të kompresojmë çdo regjistrim me algoritemet "klasike", por nga të tjera.
   Algoritmet e shqyrtuara për kompresim nuk janë të dizajnuara për punë me regjistrime të këtij përmasash (dhjetëra byte), koeficenti i kompresimit do të jetë dukshëm më pak se 1 (pra, një rritje e volumit të të dhënave në vend të kompresimit);
3. Të bëjmë FLUSH pas çdo regjistrimi.
   Në shumë biblioteka kompresimi ka mbështetje për FLUSH. Kjo është një komandë (ose parametr për procedurën e kompresimit), duke e marrë atë, arkivuesi formon një rrjedhë të kompresuar, në mënyrë që të jetë e mundur të rikthejë të gjitha të dhënat e pakompresuara, që tashmë janë marrë. Një analogji e tillë sync në sistemet e skedarëve ose commit në sql.
   E rëndësishme është që operacionet e ardhshme të kompresimit mund të përdorin fjalorin e akumuluar dhe niveli i kompresimit nuk do të vuajë aq shumë si në variantin e mëparshëm.

Mendoj se është e qartë se zgjodha variantin e tretë, le të ndalemi më shumë mbi të.

Gjeti artikull i shkëlqyer për FLUSH në zlib.

Kam përqendrova në një test të ngjashëm me artikuj, duke marrë 70 mijë regjistrime nga një pajisje reale, me një madhësi faqesh prej 60 KB. (për madhësinë e faqes ne do të kthehemi përsëri) kam marrë:

Të dhënat fillestare
Kompresimi gzip -9 (pa FLUSH)
zlib me Z_PARTIAL_FLUSH
zlib me Z_SYNC_FLUSH

Vëllimi, KB
1692
40
352
604

Në shikim të parë, çmimi që merret nga FLUSH duket shumë i lartë, megjithatë në të vërtetë kemi një zgjedhje të varfër — ose të mos kompresojmë fare, ose të kompresojmë (dhe mjaft efektivisht) me FLUSH. Nuk duhet harruar se kemi 70 mijë regjistrime, mbi 4-5 byte për regjistrim që sjell Z_PARTIAL_FLUSH. Dhe raporti i kompresimit rezultoi të ishte pothuajse 5:1, që është më shumë se një rezultat i shkëlqyer.

Mund të duket e papritur, por në të vërtetë Z_SYNC_FLUSH është një mënyrë më efikase për të bërë FLUSH.

Në rastin e përdorimit të Z_SYNC_FLUSH, 4 byte të fundit të çdo regjistrimi gjithmonë do të jenë 0x00, 0x00, 0xff, 0xff. Dhe nëse i dimë, mund t'i injorojmë, kështu që madhësia përfundimtare del të jetë vetëm 324 KB.

Në artikullin që citoj, ka një shpjegim:

Një bllok i ri tipi 0 me përmbajtje të zbrazët është shtuar.

Një bllok i tipit 0 me përmbajtje të zbrazët përbëhet nga:

• koka e bllokut tre-bit;
• 0 deri në 7 bit të barabartë me zero, për të arritur përputhjen e byte;
• sekuenca katër-byte 00 00 FF FF.

Siç është e lehtë të vërehet, në bllokun e fundit përpara këtyre 4 byte, ka nga 3 deri në 10 bitë zero. Megjithatë, praktika ka treguar se bitët zero në të vërtetë janë minimum 10.

Duket se blloqet kaq të shkurtra të të dhënave zakonisht ( gjithmonë?) kodohen me një bllok tipi 1 (bllok i fiksur), i cili domosdoshmërisht përfundon me 7 bitë zero, duke rezultuar me 10-17 bitë zero të garantuara (ndërsa të tjerët do të jenë zero me një probabilitet rreth 50%).

Pra, në të dhënat testuese, në 100% të rasteve përpara 0x00, 0x00, 0xff, 0xff ka një byte zero, dhe në më shumë se një të tretën e rasteve — dy byte zero. (ndoshta shkaku është se po përdor CBOR binar, dhe duke përdorur JSON tekstual do të haseshin më shpesh blloqet e tipit 2 — bllok dinamik, përkatësisht do të ndodhnin blloqe pa byte shtesë zero përpara 0x00, 0x00, 0xff, 0xff).

Përfundimisht, në të dhënat testuese të disponueshme mund të përfshihemi në më pak se 250 KB të dhënash të kompresuara.

Mund të kursej më shumë duke u marrë me manovrimin e bitëve: tani ne injorojmë praninë e disa bitëve zero në fund të bllokut, disa bitë në fillim të bllokut gjithashtu nuk ndryshojnë...
Por këtu mora një vendim të fortë për të ndalur, përndryshe me këtë ritëm mund të arrij në zhvillimin e arkivuesit tim.

Prandaj, nga të dhënat e mia testuese kam marrë 3-4 byte për regjistrim, raporti i kompresimit rezultoi më shumë se 6:1. Të jem i sinqertë: nuk prisja një rezultat të tillë, për mendimin tim, gjithçka që është më mirë se 2:1 — tashmë është një rezultat që justifikon përdorimin e kompresimit.

Të gjitha janë të shkëlqyera, por zlib (deflate) — megjithatë, është një algoritëm kompresimi i trashëguar dhe pak jashtë modes. Vetëm fakti se si fjalor përdoren 32KB të fundit nga stream-et e të dhënave të pathemeluar duket e çuditshme sot (dmth, nëse ndonjë bllok të dhënash është shumë i ngjashëm me atë që ishte në stream-in hyrës 40KB më parë, ai do të arkivohet përsëri, dhe nuk do të referohet në shfaqjen e mëparshme). Në arkivuesit modernë, madhësia e fjalorit shpesh matet në megabyte e jo në kilobyte.

Prandaj, vazhdojmë mini-studimin tonë mbi arkivuesit.

I fundit që kam provuar ishte bzip2 (kujdes, pa FLUSH ai tregoi një shkallë fantastike kompresimi, pothuajse 100:1). Fatin e keq, me FLUSH ai u tregua shumë keq, madhësia e të dhënave të kompresuara doli të ishte më e madhe se e pathemelura.

Dyshimet e mia për arsyet e dështimit

Libbz2 ofron vetëm një opsion flush, i cili duket se shfrynt fjalorin (analog i Z_FULL_FLUSH në zlib), nuk mund të flitet për ndonjë kompresim efektiv pas kësaj.

Dhe e fundit që provoj ishte zstd. Në varësi të parametrave, ai kompreson ose në nivelin e gzip, por shumë më shpejt, ose më mirë se gzip.

Fatin e keq, me FLUSH edhe ai tregoi se "nuk ishte shumë": madhësia e të dhënave të kompresuara doli rreth 700KB.

Unë i bëra një pyetje në faqen e projektit në github, mora përgjigje që duhet të marrësh deri në 10 byte të dhënash ndihmëse për çdo bllok të dhënash të kompresuara, që është afër rezultateve të marrë, nuk do të mund të arrihja deflate.

Në këtë pikë vendosa të ndal eksperimentet me arkivuesit (duke përmendur, xz, lzip, lzo, lz4 nuk treguan një performancë të mirë edhe në fazën e testimit pa FLUSH, dhe nuk vendosa të shqyrtoj algoritme më ekzotike të kompresimit).

Kthehemi në problemet e arkivimit.

Problemi i dytë (siç thuhet në renditje, e jo për rëndësi) është se të dhënat e kompresuara përbëjnë një stream të vetëm, në të cilin vazhdimisht ka referenca në pjesë të mëparshme. Pra, nëse ndonjë pjesë e të dhënave të kompresuara dëmtohet, humbasim jo vetëm blloqet e lidhura me të, por edhe të gjitha ato pasuese.

Ka qasje për zgjidhjen e këtij problemi:

1. Parandalimi i shfaqjes së problemeve — shtimi i tepërt në të dhënat e kompresuara, i cili do të lejojë identifikimin dhe rregullimin e gabimeve; për këtë do të flasim më vonë;
2. Minimizoni pasojat në rast se shfaqet një problem
   Kemi biseduar më parë se çdo bllok të dhënash mund të kompresohet në mënyrë të pavarur, kështu që problemi do të zhduket nga vetvetja (dëmtimi i të dhënave në një bllok do të çojë në humbjen e të dhënave vetëm në atë bllok). Megjithatë, kjo është një rast ekstrem, ku kompresimi i të dhënave do të jetë i paefektshëm. Ekstreme e kundërt: përdorimi i të gjitha 4MB të çipit tonë si një arkiv të vetëm, i cili do të na japë një kompresim të shkëlqyer, por pasoja katastrofike në rastin e dëmtimit të të dhënave.
   Po, është e nevojshme një kompromis nga ana e besueshmërisë. Por duhet të mbajmë parasysh se ne po zhvillojmë një format ruajtjeje për memorien që nuk ka nevojë për energji me një BER tepër të ulët dhe një periudhë ruajtjeje të deklaruar prej 20 vjetësh.

Gjatë eksperimentimeve, kam zbuluar se humbjet më të dukshme të nivelit të kompresimit fillojnë në blloqe të dhënash të kompresuara me madhësi më të vogël se 10 KB.
Kemi përmendur më parë se memoria e përdorur ka organizim sipas faqeve, nuk shoh arsye për të mos përdorur përputhjen 'një faqe — një bllok i dhënash të kompresuara'.

Pra, madhësia minimale e arsyeshme e faqes është 16 KB (me rezervë për informacionin shërbim). Megjithatë, një madhësi kaq të vogël faqe vë kufizime të rëndësishme mbi madhësinë maksimale të shënimeve.

Edhe pse aktualisht nuk parashikoj shënime më të mëdha se një kilobajt në formë të kompresuar, kam vendosur të përdor faqe me madhësi 32 KB (në total bëhen 128 faqe për çip).

Përmbledhje:

• Të dhënat i ruajmë të kompresuara me zlib (deflate);
• Për çdo shënim vendosim Z_SYNC_FLUSH;
• Çdo shënim të kompresuar i presim bajtët e fundit (p.sh., 0x00, 0x00, 0xff, 0xff); në krye tregojmë se sa bajtë kemi prerë;
• Të dhënat i ruajmë në faqe prej 32 KB; brenda faqes ka një rrjedhë të vetme të dhënash të kompresuara; në çdo faqe kompresimi fillojmë sërish.

Dhe, para se të përfundoj me kompresimin, do të doja të theksoj se të dhënat e kompresuara përbëjnë vetëm disa bajta për shënim, prandaj është jashtëzakonisht e rëndësishme të mos e fryjmë informacionin shërbim, çdo bajt këtu ka rëndësi.

Ruajtja e kryeshemes të të dhënave

Duke pasur parasysh se shënimet janë të gjatë variabile, na nevojitet një mënyrë për të përcaktuar vendosjen/kufijtë e shënimeve.

Njoh tri qasje:

1. Të gjitha shënimet ruhen në një rrjedhë të vazhdueshme, fillimisht është kryeza e shënimit që përmban gjatësi, dhe pastaj vjen vetë shënimi.
   Në këtë variant, dhe kryezat dhe të dhënat mund të kenë gjatësi variabile.
   Në thelb, rezulton një listë e lidhur njëdrejt, e cila përdoret shumë shpesh;
2. Kryezat dhe vetë shënimet ruhen në rrjedha të ndara.
   Duke përdorur kryezat me gjatësi të qëndrueshme, arrijmë që dëmtimi i një kryeze nuk ndikon në të tjerët.
   Një qasje e tillë përdoret, për shembull, në shumë sisteme skedash;
3. Shënimet ruhen në një rrjedhë të vazhdueshme, kufiri i shënimit përcaktohet nga një simbol (simbol/ose një sekuencë simbolesh, që janë të ndaluara brenda blloqeve të dhënash). Nëse brenda shënimit haset një simbol, atëherë ne e zëvendësojmë atë me një sekuencë të caktuar (e shënojmë).
   Një qasje e tillë përdoret, për shembull, në protokollin PPP.

Do ta ilustroj.

Opsioni 1:

Këtu gjithçka është shumë e thjeshtë: duke ditur gjatësi shënimi, mund të llogarisim adresën e kryeza tjetër. Kështu ne lëvizim përmes kryezave, derisa të hasim një zonë të mbushur me 0xff (zonë të lirë) ose fundin e faqes.

Opsioni 2:

Për shkak të gjatësi variabile të shënimeve nuk mund të themi paraprakisht se sa shënime (dhe pra sa kryeza) do të na nevojiten në një faqe. Mund të vendosim kryezat dhe të dhënat në faqet e ndryshme, por më pëlqen një qasje tjetër: si kryezat (me gjatësi të qëndrueshme) ajo fillon nga fillimi i faqes, ndërsa të dhënat (me gjatësi variabile) fillojnë nga fundi. Pasi ato të "takohen" (asgjesa e lirë nuk do të mjaftojë për një shënim të ri) ne e konsiderojmë këtë faqe si të plotë.

Opsioni 3:

Këtu nuk ka nevojë të ruajmë në kryezë gjatësi ose informacion tjetër mbi vendosjen e të dhënave, mjafton markat që tregojnë kufijtë e shënimeve. Megjithatë, të dhënat duhet të përpunohen gjatë shkrimit/lehtësimit.
Si një markë do të përdorja 0xff (me të cilin është mbushur faqa pas fshirjes), kështu që zona e lirë nuk do të interpretohet si të dhëna.

Tabela krahasuese:

Mundësia 1
Variant 2
Varianti 3

Qëndrueshmëria ndaj gabimeve
—
+
+

Kompaktësia
+
—
+

Vështirësia në realizim
*
**
**

Variantin 1 ka një defekt fatal: nëse dëmtohet ndonjë nga titujt, ne shkatërrojmë tërë zinxhiri pasues. Variantet e tjera lejojnë rikuperimin e pjesës së të dhënave edhe në rast dështimesh masive.
Megjithatë, është e rëndësishme të kujtojmë se ne vendosëm të ruajmë të dhënat në formë të kompresuar, kështu që ne e humbasim tërë informacionin në faqe pas një shkrimi të 'dëmtuar', kështu që, ndonëse në tabelë shfaqet një minus, ne nuk e konsiderojmë atë.

Kompaktësia:

• në variantin e parë na nevojitet të ruajmë vetëm gjatësinë në titull, dhe në qoftë se përdorim variabla me gjatësi të ndryshueshme, në shumicën e rasteve mund të përmbushim me një byte;
• në variantin e dytë na nevojitet të ruajmë adresën fillestare dhe gjatësinë; shkrimi duhet të ketë një madhësi të konstantë, e vlerësoj në 4 byte për shkrim (dy byte për deslocim, dhe dy byte për gjatësi);
• në variantin e tretë, na mjafton një simbol i vetëm për të treguar fillimin e shkrimit, plus shkrimi vetë për shkak të pakohësisë do të rritet me 1-2%. Si rezultat, ka një barazim të përafërt me variantin e parë.

Fillimisht, e konsiderova variantin e dytë si variantin kryesor (madje e shkrova dhe implementimin). E hoqa atë vetëm kur vendosa përfundimisht të përdor kompresimin.

Ndoshta, një ditë do ta përdor një variant të tillë. Për shembull, nëse duhet të merrem me ruajtjen e të dhënave për një anije që lundron midis Tokës dhe Marsit - kërkesa për besueshmëri është krejtësisht ndryshe, rrezatimi kozmik, ...

Sa i përket variantit të tretë: i kam dhënë dy yje për kompleksitetin e implementimit thjesht sepse nuk e dua të merrem me pakohësinë, ndryshimin e gjatësi gjatë procesit etj. Po, ndoshta është subjektiv, por kodi do të duhet të shkruhet nga unë - përse të detyroj veten të bëj diçka që nuk më pëlqen.

Përmbledhje: përzgjidhim variantin e ruajtjes në forma të lidhura 'titulli me gjatësi - të dhëna me gjatësi të ndryshueshme' për shkak të efikasitetit dhe thjeshtësisë së implementimit.

Përdorimi i fushave bit për kontrollin e suksesshëm të operacioneve të shkrimit

Tani nuk e mbaj mend se ku e pashë idenë, por duket më pak kështu:
Për çdo shkrim, ndajnë disa bit për ruajtjen e flamujve.
Siç thamë më parë, pas erase të gjithë bitët janë mbushur me 1, dhe ne mund të ndryshojmë 1 në 0, por jo përkundrazi. Pra, për 'flamujt e pa vendosur' përdorim 1, për 'flamujt e vendosur' - 0.

Ja si mund të duket vendosja e një shkrimi me gjatësi të ndryshueshme në flash:

1. Vendosim flamurin 'shkrimi i gjatë filloi';
2. Shkruajmë gjatësinë;
3. Vendosim flamurin 'shkrimi i të dhënave filloi';
4. Shkruajmë të dhënat;
5. Vendosim flamurin 'shkrimi përfundoi'.

Përveç kësaj, do të kemi flamurin 'ndodhi një gabim', në total 4 flamuj bit.

Në këtë rast, ne kemi dy gjendje të qëndrueshme '1111' - shkrimi nuk ka filluar dhe '1000' - shkrimi ka përfunduar me sukses; në rast të një ndërprerje të papritur të procesit të shkrimit do të marrim gjendje të ndërmjetme, të cilat ne më pas mund t'i zbulojmë dhe t'i trajtojmë.

Qasja është interesante, por ajo mbron vetëm nga fikja e papritur e energjisë dhe dështime të ngjashme, gjë që, natyrisht, është e rëndësishme, megjithatë, kjo nuk është arsyeja e vetme (dhe as kryesore) për dështimet e mundshme.

Përmbledhje: vazhdojmë në kërkimin e një zgjidhjeje të mirë.

Kontrolli i shumave

Kontrolli i shumave gjithashtu ofron mundësinë për të siguruar (me një probabilitet të mjaftueshëm) që po lexojmë pikërisht atë që duhej të ishte shkruar. Dhe, përkundrazi nga fushat e mësipërme, ato funksionojnë gjithmonë.

Nëse shqyrtojmë listën e burimeve të mundshme të problemeve, për të cilat folëm më lart, kontrolli i shumës është në gjendje të identifikojë një gabim pavarësisht nga origjina e saj (përveç ndoshta alienëve të keq, ata mund të fshehin edhe kontrollin e shumës).

Pra, nëse qëllimi ynë është të kontrollojmë se të dhënat janë të paprekura, kontrolli i shumës është një ide e shkëlqyer.

Zgjedhja e algoritmit të llogaritjes së kontrollit të shumës nuk kishte asnjë pyetje - CRC. Nga njëra anë, pronat matematikore lejojnë 100% të kapin gabimet e disa llojeve, nga ana tjetër - në të dhëna të rastësishme zakonisht ky algoritëm tregon një probabilitet kolizioni jo shumë më të lartë se kufiri teorik . Le të themi se nuk është algoritmi më i shpejtë, nuk është gjithmonë minimal në numrin e kolizioneve, por ka një cilësi shumë të rëndësishme: në testet që kam hasur, nuk kam gjetur modele që do të dështonin në mënyrë të dukshme. Qëndrueshmëria - kjo është cilësia kryesore në këtë rast.

Shembulli i një studimi të gjerë: pjesa 1, pjesa 2 (linket në narod.ru, faleminderit).

Megjithatë, detyra e zgjedhjes së kontrollit të shumës nuk mbaron, CRC - kjo është një familje e tërë e kontrolleve të shumës. Duhet të vendosim për gjatësi, dhe pastaj të zgjidhim polinomin.

Zgjedhja e gjatësi së kontrollit të shumës nuk është një çështje e tillë e thjeshtë siç duket në shikim të parë.

Do të ilustroj:
Le të supozojmë se kemi një probabilitet gabimi për çdo bajt dhe një checksum të përsosur, llogarisim numrin mesatar të gabimeve për një milion rekordesh:

Të dhënat, bajt
Checksum, bajt
Gabime të padeklaruara
Identifikime falsë të gabimeve
Totali i goditjeve të gabuara

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

Duket e thjeshtë – zgjidhni gjatësi të checksum-it në varësi të të dhënave që mbrohen me një minimum goditjesh të gabuara – dhe punët janë zgjidhur.

Megjithatë, me checksum-a të shkurtra paraqitet një problem: ato, përderisa zbulojnë gabime të vetme bajtësh mirë, mund të pranojnë si të sakta të dhëna krejtësisht të rastësishme me një probabilitet të konsiderueshëm. Në Habrë ka pasur një artikull që përshkruan problemin në jetën reale.

Prandaj, për ta bërë takimin rastësor me checksum më praktikisht të pamundur, duhet të përdoren checksum-a me gjatësi 32 bit dhe më shumë. (për gjatësi mbi 64 bit zakonisht përdoren funksione hash kriptografike).

Megjithëse më parë kam shkruar se duhet të kursejmë hapësirë me çdo kusht, do të përdorim një checksum 32-bit (16 bit është pak, probabiliteti i kolizionit është më shumë se 0.01%; dhe 24 bit, siç thonë, nuk shkon as këtu e as atje).

Këtu mund të ketë një kundërshtim: a është vërtet aq shumë kemi kursyer çdo bajt në përzgjedhjen e kompresimit, për ta dhënë tani 4 bajta menjëherë? A nuk do të ishte më mirë të mos kompresonim dhe të mos shtonim checksum-in? Sigurisht që jo, mungesa e kompresimit nuk do të thotë, se kontrolli i integritetit nuk është i nevojshëm për ne.

Për zgjedhjen e polinomëve nuk do të shpikim biçikletën, por do të marrim CRC-32C, që është tani i njohur.
Ky kod zbulohet 6 gabime bajti në paketa deri në 22 bajtë (ndoshta rasti më i zakonshëm për ne), 4 gabime bajti në paketa deri në 655 bajt (po ashtu rasti i zakonshëm), 2 ose çdo numër të çuditshëm gabimesh bajti në paketa të çdo gjatësie të arsyeshme.

Nëse ndokush është i interesuar për detajet

Artikulli në Wikipedia për CRC.

Parametrat e kodit crc-32c në në sitin e Kupmanit – ndoshta specialisti kryesor për CRC në planet.

Në artikulli i tij ka akoma një kod interesant, që ofron pak më shumë parametra për gjatësi paketa që janë të rëndësishme për ne, por nuk e kam konsideruar ndryshimin të konsiderueshëm, dhe mendoj që jam mjaft kompetent për të zgjedhur një kod të personalizuar në vend të një standardi dhe të studiuar mirë.

Gjithashtu, pasi të dhënat tona janë të kompresuara, lind pyetja: a duhet të llogarisim checksum-in mbi të dhënat e kompresuara apo të pakompresuara?

Argumentet "pro" llogaritjes së checksum-it mbi të dhënat e pakompresuara:

• ne përfundimisht na nevojitet të kontrollojmë ruajtjen e të dhënave – këtu e kontrollojmë direkt (në të njëjtën kohë do të kontrollohet gjithashtu se a ka pasur ndonjë gabim në realizimin e kompresimit/dekompresimit, dëmtime të shkaktuara nga një kujtesë me gabime etj.);
• algoritmi deflate në zlib ka një realizim mjaft të pjekur dhe nuk duhet të dështojë në rast të një të dhëne "të çuditshme", për më tepër, shpesh është në gjendje të zbulojë gabime në rrjedhën hyrëse, duke zvogëluar probabilitetin e përgjithshëm të moszbulimit të një gabimi (kam bërë një test me invertojnë e një bajti të vetëm në një shënim të shkurtër, zlib zbuloi gabimin në rreth një të tretën e rasteve).

Argumentet "kundër" llogaritjes së checksum-it mbi të dhënat e pakompresuara:

• CRC "është dizajnuar" pikërisht për gabime të pakta bajti, të cilat janë të zakonshme për kujtesën flash (një gabim bajti në një rrjedhë të kompresuar mund të sjellë një ndryshim masiv të rrjedhës dalëse, në të cilin, teoretikisht, mund të "kapim" një kolizion);
• nuk më pëlqen shumë ideja e dërgimit të të dhënave të mundshme të prishura në dekompresor, kush e di, si do të reagojë ai.

Në këtë projekt kam vendosur të largohesha nga praktika e zakonshme për ruajtjen e checksum-it mbi të dhënat e pakompresuara.

Përmbledhje: përdorim CRC-32C, dhe checksum-in e llogarisim mbi të dhënat në formën e tyre siç shkruhen në flash (pas kompresimit).

Mbivendosja

Përdorimi i kodimit të tepruar nuk e lejon, sigurisht, përjashtimin e humbjes së të dhënave, megjithatë, ai mund të zvogëlojë ndjeshëm (shpesh disa renditje) probabilitetin e humbjes së pakthyeshme të të dhënave.

Ne mund të përdorim lloje të ndryshme të tepricës për të korrigjuar gabimet.
Kodet e Hamming-ut mund të korrigjojnë gabime të vetme bajti, kodet e Reed-Solomonit janë simbolike, disa kopje të të dhënave së bashku me checksum-at ose kodimet si RAID-6 mund të ndihmojnë në rikuperimin e të dhënave edhe në rast të dëmtimeve masive.
Fillimisht planifikoja të përdorja gjerësisht kodimin të qëndrueshëm ndaj ndërhyrjeve, por më vonë kuptova se fillimisht duhet të kemi një ide se nga cilat gabime duam të mbrohemi, dhe pastaj të zgjedhim kodimin.

Kemi folur më parë se gabimet duhet të identifikohen sa më shpejt të jetë e mundur. Në cilat momente mund të përballemi me gabime?

1. Regjistrim i papërfunduar (për arsye të ndryshme, energjia është shkëputur gjatë regjistrimit, Raspberry është ngrirë, …)
   Me keqardhje, në rastin e një gabimi të tillë, mbeten vetëm të injorohen të dhënat e pavlefshme dhe të merren si të humbura;
2. Gabime regjistrimi (për arsye të ndryshme, në memorien flash është regjistruar diçka tjetër nga ajo që u regjistrua)
   Gabime të tilla mund të zbulojmë menjëherë, nëse pas regjistrimit bëjmë një lexim kontrollues;
3. Shkëputje të të dhënave në memorie gjatë ruajtjes;
4. Gabime leximi
   Për ta korrigjuar mjafton të përsërisim leximin disa herë në rast të mospërputhjes së checksum-it.

Pra, vetëm gabimet e tipit të tretë (dëmtim spontan i të dhënave gjatë ruajtjes) nuk mund të rregullohen pa kodim rezistent ndaj gabimeve. Mendoj se këto gabime janë shumë të pamundura.

Përmbledhje: u vendos që të heqim dorë nga kodimi i tepërt, por, nëse shfrytëzimi tregoi gabueshmërinë e këtij vendimi, atëherë do të kthehemi në shqyrtimin e këtij çështje (me statistikën e grumbulluar për dështime, e cila do të lejojë të përzgjedhim llojin optimal të kodimit).

Të tjera

Natyrisht, formati i artikullit nuk lejon të arsyetohet çdo bit në format (dhe edhe unë tashmë kam mbaruar forcën), prandaj do të kaloj hollësisht mbi disa pika, të pa përmendura më parë.

• Është vendosur të bëhen të gjitha faqet "të barabarta"
  Pra, nuk do të ketë faqe speciale me metadata, rrugë të veçanta etj., në vend të kësaj një rrjedhë e vetme, e cila regjistron të gjitha faqet njëra pas tjetrës.
  Kjo siguron konsum të barabartë të faqeve, mungesën e një pikë të vetme dështimi, dhe thjesht pëlqen;
• Patjetër që duhet të parashikohet versioni i formatit.
  Formati pa numër versioni në titull — është një e keqe!
  Mjafton të shtoni në titullin e faqes një fushë me një numër Magjik (nënshkrimi), i cili do të tregojë versionin e përdorur të formatit (nuk mendoj se në praktikë do të jenë më shumë se dhjetë);
• Të përdoren për regjistrimet (të cilat janë shumë) tituj variabël të gjatë, duke u përpjekur për shumicën e rasteve ta bëjmë atë me gjatësi 1 byte;
• Për kodimin e gjatë të titullit dhe gjatësi të pjesës së prerë të regjistrimit të ngjeshur, përdorni kode binarësh të gjatë variabël.

Më shumë ndihmoi generaatori online i kodimeve Huffman. Gjatë disa minutave arritëm të gjejmë kodet e nevojshme të gjatë variabël.

Përshkrimi i formatit të ruajtjes së të dhënave

Rendi i bajtëve

Fushat, të cilat janë më të mëdha se një byte, ruhen në formatin big-endian (rendi i bajtëve të rrjetit), që do të thotë 0x1234 regjistrohet si 0x12, 0x34.

Ndarja në faqe

Të gjithë memorien flash është e ndarë në faqe të barabarta.

Madhësia e faqes për default është 32Kb, por jo më shumë se 1/4 e madhësisë totale të çipit të memories (për një çip prej 4Mb rezulton 128 faqe).

Çdo faqe ruan të dhëna në mënyrë të pavarur nga të tjerat (do të thotë të dhënat e një faqe nuk referohen në të dhënat e një faqe tjetër).

Të gjitha faqet janë të numëruara në rendin e natyrshëm (në rritje të adresave), duke filluar nga numri 0 (faqja zero fillon me adresën 0, e para — me 32Kb, e dyta — me 64Kb etj.)

Çipi i memories përdoret si një buffer ciklik (ring buffer), do të thotë fillimisht regjistrimi shkon në faqen me numër 0, pastaj me numër 1,..., kur ne mbushim faqen përfundimtare, fillon një cikël i ri dhe regjistrimi vazhdon nga faqja zero.

Brenda faqes

Në fillim të faqes ruhen një titull prej 4 bajtësh, pastaj kontrolli i shumës (CRC-32C), më pas ruhen regjistrimet në formatin "titulli, të dhëna, kontrolli i shumës".

Titulli i faqes (në skemën e gjelbër të ndotur) përbëhet nga:

• një fushe dy bajtesh Magic Number (kjo është gjithashtu — shenja e versionit të formatit)
  për versionin aktual të formatit konsiderohet si 0xed00 ⊕ numri i faqes;
• një dy bajtesh numërues "Versioni i faqes" (numri i ciklit të ripërsëritjes së memories).

Regjistrimet në faqe ruhen në formë të ngjeshur (përdoret algoritmi deflate). Të gjitha regjistrimet në një faqe ngjeshen në një rrjedhë (përdoret një fjalor i përbashkët), në çdo faqe të re ngjeshja fillon nga e para. Pra, për dekompresimin e çdo regjistrimi kërkohen të gjitha regjistrimet e mëparshme nga kjo faqe (dhe vetëm nga kjo).

Çdo regjistrim ngjeshet me flagun Z_SYNC_FLUSH, në atë rast në fund të rrjedhës së ngjeshur gjenden 4 bajtë 0x00, 0x00, 0xff, 0xff, përpara, mundësisht, nga një ose dy bajtë zero.
Këtë sekuencë (me gjatësi 4, 5 ose 6 bajtë) ne e heqim kur regjistrojmë në memorien flash.

Titulli i regjistrimit përbëhet nga 1, 2 ose 3 bajtë, që ruajnë:

• një bit (T), që nënkupton tipin e regjistrimit: 0 — kontekst, 1 — ditar;
• një fushë me gjatësi të ndryshueshme (S) nga 1 deri në 7 bit, e cila përcakton gjatësi e titullit dhe "bishtin", që duhet të shtohet në regjistrim për dekompresim;
• gjatësinë e regjistrimit (L).

Tabela e vlerave S:

S
Gjatësia e titullit, bajtë
Heket gjatë regjistrimit, 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)

Përpiqem të ilustroj, nuk e di sa qartë ka dalë:

Me të verdhë është shënuar fusha T, me të bardhë fusha S, me të gjelbër L (gjatësia e të dhënave të kompresuara në byte), me të kaltër të dhënat e kompresuara, me të kuqe byte të fundit të të dhënave të kompresuara, të cilat nuk shkruhen në flash-memory.

Kështu, ne do të jemi në gjendje të regjistrojmë titujt e regjistrimeve me gjatësi më të zakonshme (deri 63+5 byte në formë të kompresuar) me një byte.

Pas çdo regjistrimi ruhet një checksum CRC-32C, ku vlefshmëria fillestare (init) është një vlerë e inversuar e kontrolles së mëparshme.

CRC ka pronën e "së vazhdimësisë", vepron (plus-minus invertimi i biteve në proces) një formulë të tillë: .
Pra, në thelb ne llogarisim CRC të gjithë byte të titujve dhe të dhënave të kësaj faqe.

Menjëherë pas checksum-it ndodhet titulli i regjistrimit të ardhshëm.

Titulli është ndërtuar në mënyrë që byte i pare të jetë gjithmonë ndryshe nga 0x00 dhe 0xff (nëse përballë byte të parë të titullit hasim 0xff, atëherë kjo është një zonë që nuk po përdoret; 0x00 e sinjalizon një gabim).

Algoritmet përkatës

Leximi nga flash-memory

Çdo lexim shoqërohet me verifikimin e checksum-it.
Nëse checksum-i nuk përputhet - leximi përsëritet disa herë në shpresë për të lexuar të dhënat e sakta.

(kjo ka kuptim, Linux nuk ruan leximin nga NOR Flash, e verifikuar)

Shkruaj në flash-memory

Regjistro bëj të dhënat.
Lexoj ato.

Nëse të dhënat e lexuara nuk përputhen me ato të regjistruara - mbushim zonën me zero dhe sinjalizojmë për një gabim.

Përgatitja e mikroçipëve të reja për punë

Për inicializim në faqen e parë (saktësisht zero) shkruhet një titull me versionin 1.
Pas kësaj, në këtë faqe shkruhet konteksti fillestar (përmban UUID të automatit dhe cilësimet e paracaktuara).

Kjo, flash-memory është gatshme për punë.

Ngarkimi i automatit

Me ngarkim lexohen 8 byte të parë të çdo faqe (titulli + CRC), faqet me numrin e Magic Number të panjohur ose CRC të gabuar injorohen.
Nga faqet "e sakta" përzgjidhen faqet me versionin më të lartë, nga ato merret faqja me numrin më të madh.
Lexo regjistrimin e parë, kontrollo saktësinë e CRC, praninë e flamurit "kontekst". Nëse gjithçka është në rregull - kjo faqe konsiderohet aktuale. Nëse jo - kthehemi në faqen e mëparshme, derisa të gjejmë një faqe "live".
Dhe në faqen e gjetur lexojmë të gjitha regjistrimet, ato me flamurin "kontekst" i zbatojmë.
Ruajmë fjalorin zlib (do të nevojitet për regjistrim të mëtejshëm në këtë faqe).

Kjo, ngarkimi përfundoi, konteksti u rikuperua, mund të punojmë.

Shtimi i regjistrimeve në ditar

Kompresojmë regjistrimin me fjalorin e duhur, duke указивал Z_SYNC_FLUSH. Shikojmë nëse regjistrimi i kompresuar po hyn në faqen aktuale.
Nëse nuk hyn (apo në faqe kishte gabime CRC) - fillojmë një faqe të re (shiko të mëposhtme).
Regjistro regjistrimin dhe CRC. Nëse ndodhi një gabim - fillojmë një faqe të re.

Faqe e re

Zgjidhim një faqe të lirë me numrin minimal (faqe e lirë e konsiderojmë faqen me checksum të gabuar në titull ose me version më të vogël se aktuali). Nëse nuk ka faqe të tilla - zgjedhim faqen me numrin minimal nga ata që kanë version të barabartë me atë aktual.
Bëjmë faqen e zgjedhur erase. Krahasojmë përmbajtjen me 0xff. Nëse diçka nuk është në rregull - marrim faqen tjetër të lirë, etj.
Në faqen e fshirë shkruajmë titullin, regjistrimi i parë është gjendja aktuale e kontekstit, regjistrimi i dytë është regjistrimi i pa regjistruar në ditar (nëse ka).

Përkufizimi i formatit

Sipas mendimit tim, doli një format i mirë për ruajtjen e çdo informate më shumë se sa e kompresueshme (teksti i thjeshtë, JSON, MessagePack, CBOR, ndoshta protobuf) në NOR Flash.

Sigurisht, formati është "i ngushtuar" për SLC NOR Flash.

Nuk duhet ta përdorni me mbajtës me BER të lartë, siç janë NAND ose MLC NOR (a ka një memory të tillë në shitje? Kam hasur vetëm përmendje në punime mbi kodet e korrigjimit).

Më shumë, nuk duhet ta përdorni me pajisje, që kanë FTL e tyre: USB flash, SD, MicroSD, etj. (për një memory të tillë kam bërë një format me madhësinë e faqes në 512 byte, me një nënshkrim në fillim të çdo faqe dhe numra unik regjistrimesh - ndonjëherë nga një flash i "korruptuar" arrija të rikuperoja të gjitha të dhënat përmes leximit sekondar).

Në varësi të detyrave formati mund të përdoret pa ndryshime në flash nga 128Kbit (16Kbyte) deri në 1Gbit (128Mbyte). Nëse dëshirohet, mund të përdoret edhe në çipe më të mëdhenj, thjesht ndoshta duhet të korrigjohet madhësia e faqes (Por këtu lind pyetja e qëllimshmërisë ekonomike, çmimi i NOR Flash me kapacitet të madh nuk është i kënaqshëm).

Nëse dikujt format i ka dukur interesant dhe dëshiron ta përdorë në një projekt të hapur - na shkruani, do të përpiqem të gjej kohë, të rregulloj kodin dhe ta publikoj në github.

Përfundimi

Siç e shohim, në fund formatit i doli të ishte i thjeshtë dhe madje i mërzitshëm.

Në artikull është e vështirë të pasqyrosh evolucionin e pikëpamjes time, por besoni: fillimisht doja të krijoja diçka të sofistikuar, të patundshme, e cila do të mbijetonte edhe pas një shpërthimi bërthamor në afërsi. Sidoqoftë, arsyetimi (shpresoj) në fund të fitoi dhe gradualisht prioritetet u zhvendosën drejt thjeshtësisë dhe kompaktësisë.

A mund të ndodhë që kam gabuar? Po, sigurisht. Mund të ndodhë, për shembull, që kemi blerë një koleksion çipash të dobët. Ose për ndonjë arsye tjetër pajisja nuk do të përmbushë pritshmëritë për besueshmëri.

A kam një plan për këtë rast? Mendoj se pas leximit të artikullit nuk keni dyshime se plani ekziston. Dhe madje jo vetëm një.

Në njëfarë mënyre, formati është zhvilluar njëkohësisht si një variant pune dhe si një 'top prova'.

Aktualisht, gjithçka funksionon mirë, përditësimi do të bëhet për disa ditë (për afërsisht) në qindra pajisje, do të shohim se çfarë do të ndodhë në 'ekspertizën' e vërtetë (falë, shpresoj, formatit që lejon të identifikohet me besueshmëri dështimi; kështu që do të arrijmë të mbledhim statistika të plota). Pas disa muajsh do të jetë e mundur të nxjerrim përfundime (nëse nuk kemi fat - atëherë edhe më herët).

Nëse pas përdorimit identifikohet ndonjë problem serioz dhe kërkohen rregullime, unë do të shkruaj patjetër për të.

Literatura

Nuk doja të përgatitja një listë të gjatë dhe të mërzitshme të punëve të përdorura, në fund të fundit, Google është për të gjithë.

Vendosa të lë një listë nxëniesh, të cilat më dukeshin veçanërisht interesante, megjithatë gradualisht ato kaluan drejtpërdrejt në tekstin e artikullit, dhe në listë mbeti vetëm një pikë:

1. Utilitari infgen nga autori zlib. Ajo tregon përmbajtjen e arkivave deflate/zlib/gzip në një formë të kuptueshme. Nëse ndiheni të detyruar të merreni me strukturën e brendshme të formatit deflate (ose gzip) - e rekomandoj me ngulm.

Burimi: habr.com