parahistorinë

Ne kemi makina shitëse me dizajnin tonë. Brenda, ka një Raspberry Pi dhe disa pajisje në një pllakë të veçantë. Një pranues monedhash, një pranues kartëmonedhash dhe një bankomat janë të gjitha të lidhura. Një program i shkruar me porosi kontrollon gjithçka. I gjithë historiku i funksionimit regjistrohet në një regjistër në një flash drive (MicroSD), i cili më pas transmetohet në internet (nëpërmjet një modemi USB) në server, ku ruhet në një bazë të dhënash. Informacioni i shitjeve ngarkohet në 1C, dhe ekziston gjithashtu një ndërfaqe e thjeshtë në internet për monitorim, etj.

Kjo do të thotë, ditari është me rëndësi jetike për kontabilitetin (të ardhurat, shitjet, etj.), monitorimin (të gjitha llojet e dështimeve dhe rrethana të tjera të forcës madhore); ky, mund të thuhet, është i gjithë informacioni që kemi për këtë makinë.

problem

Disqet flash kanë rezultuar të jenë pajisje shumë të paqëndrueshme. Ato dështojnë me një rregullsi alarmuese. Kjo çon si në ndërprerje të funksionimit të makinës ashtu edhe (nëse për ndonjë arsye regjistri nuk mund të transmetohej në internet) në humbje të të dhënave.

Kjo nuk është përvoja jonë e parë me përdorimin e disqeve flash. Më parë kemi punuar në një projekt tjetër me mbi njëqind pajisje ku regjistri ruhej në disqe USB. Kishte gjithashtu probleme me besueshmërinë, me dhjetëra disqe që dështonin brenda një muaji ndonjëherë. Ne provuam disqe të ndryshme flash, duke përfshirë ato të markave të njohura me memorie SLC, dhe disa modele janë më të besueshme se të tjerat, por zëvendësimi i disqeve nuk e zgjidhi plotësisht problemin.

Kujdes! Lexim i gjatë! Nëse nuk të intereson "pse"-ja, por vetëm "si", mund të kalosh përpara. në fije artikull.

vendim

Gjëja e parë që të vjen ndërmend është të heqësh dorë nga karta MicroSD dhe, le të themi, të instalosh një SSD dhe të nisësh nga ajo. Teorikisht, ndoshta është e mundur, por është relativisht e shtrenjtë dhe jo veçanërisht e besueshme (kërkohet një përshtatës USB-në-SATA; shkalla e dështimeve për SSD-të me çmim të ulët është gjithashtu zhgënjyese).

As USB HDD nuk duket si një zgjidhje veçanërisht tërheqëse.

Pra, ne gjetëm këtë mundësi: lëreni nisjen nga MicroSD, por përdoreni ato në modalitetin vetëm për lexim dhe ruani regjistrin e operacioneve (dhe informacione të tjera unike për një pjesë specifike të pajisjeve - numrin serial, kalibrimet e sensorëve, etj.) diku tjetër.

Tema e FS vetëm për lexim për Raspberry Pi është studiuar tashmë plotësisht, nuk do të ndalem në detajet e zbatimit në këtë artikull. (por nëse ka interes, ndoshta do të shkruaj një mini-artikull mbi këtë temë)E vetmja gjë që dua të theksoj është se, bazuar si në përvojën personale ashtu edhe në reagimet nga ata që e kanë zbatuar tashmë, ka një rritje në besueshmëri. Ndërsa është e pamundur të eliminohen plotësisht prishjet, është plotësisht e mundur të zvogëlohet ndjeshëm frekuenca e tyre. Për më tepër, kartat po standardizohen, duke e bërë zëvendësimin shumë më të lehtë për personelin e mirëmbajtjes.

Pjesa hardware

Nuk kishte dyshime të veçanta në lidhje me zgjedhjen e llojit të memories - NOR Flash.
Argumentet:

• lidhje e thjeshtë (më shpesh autobusi SPI, i cili është përdorur tashmë, kështu që nuk priten probleme me harduerin);
• çmim qesharak;
• protokolli standard i funksionimit (zbatimi është tashmë në bërthamë) Linux, nëse dëshironi, mund të merrni një palë të tretë, të cilat janë gjithashtu të pranishme, ose edhe të shkruani vetë, për fat të mirë, gjithçka është e thjeshtë);
• besueshmëria dhe jeta e shërbimit:
  nga një fletë të dhënash tipike: të dhënat ruhen për 20 vjet, 100000 cikle fshirjeje për secilin bllok;
  nga burime të palëve të treta: BER jashtëzakonisht i ulët, nuk supozohet nevoja për kode korrigjimi gabimesh (Disa punime diskutojnë ECC për NOR, por zakonisht nënkuptojnë MLC NOR, dhe kjo ndodh gjithashtu).

Le të vlerësojmë kërkesat për vëllimin dhe burimet.

Do të donim të na garantohej ruajtja e të dhënave për disa ditë. Kjo është e nevojshme për t'u siguruar që historiku i shitjeve të mos humbasë në rast të ndonjë problemi me lidhjen. Synojmë 5 ditë. (madje duke marrë parasysh fundjavat dhe festat) problemi mund të zgjidhet.

Aktualisht ne grumbullojmë rreth 100 KB të dhënash regjistri në ditë (3-4 mijë hyrje), por kjo shifër po rritet gradualisht ndërsa niveli i detajeve rritet dhe shtohen ngjarje të reja. Për më tepër, ka rritje të herëpashershme (për shembull, kur një sensor fillon të na dërgojë rezultate pozitive të rreme). Ne do të llogarisim 10 hyrje me nga 100 bajt secila - një megabajt në ditë.

Totali është 5MB të dhëna të pastra (të kompresuara mirë). Dhe pastaj ka edhe (vlerësim i përafërt) 1 MB të dhëna shërbimi.

Kjo do të thotë që na duhet një çip 8MB pa kompresim, ose 4MB me kompresim. Këto janë shifra mjaft realiste për këtë lloj memorieje.

Sa i përket burimit: nëse planifikojmë që memoria të rishkruhet plotësisht jo më shumë se një herë në 5 ditë, atëherë gjatë 10 viteve të shërbimit marrim më pak se një mijë cikle rishkrimi.
Më lejoni t'ju kujtoj se prodhuesi premton njëqind mijë.

Pak rreth NOR kundrejt NAND

Memoria NAND është sigurisht më e popullarizuar këto ditë, por unë nuk do ta përdorja për këtë projekt: NAND, ndryshe nga NOR, kërkon kode korrigjimi gabimesh, tabela blloqesh të këqija, etj., dhe çipat NAND zakonisht kanë shumë më tepër kunja.

Disavantazhet e NOR përfshijnë:

• vëllim i vogël (dhe, në përputhje me rrethanat, çmim i lartë për megabajt);
• shpejtësi e ulët shkëmbimi (kryesisht për shkak të faktit se përdoret një ndërfaqe seriale, zakonisht SPI ose I2C);
• fshirje e ngadaltë (në varësi të madhësisë së bllokut, zgjat nga fraksione të sekondës deri në disa sekonda).

Duket sikur nuk ka asgjë kritike për ne, kështu që vazhdojmë.

Nëse jeni të interesuar për detajet, u zgjodh një mikroqark at25df321a (Megjithatë, kjo nuk ka rëndësi; ka shumë çipa të ngjashëm në treg që janë të pajtueshëm për sa i përket pinout dhe sistemit të komandës; edhe nëse duam të instalojmë një çip nga një prodhues i ndryshëm dhe/ose me një kapacitet të ndryshëm, gjithçka do të funksionojë pa ndryshuar kodin).

Unë përdor atë të integruar në kernel Linux Drajveri, në Raspberry, falë mbështetjes së mbivendosjes së pemës së pajisjes, gjithçka është shumë e thjeshtë - duhet të vendosni mbivendosjen e kompiluar në /boot/overlays dhe të modifikoni pak /boot/config.txt.

Shembull i një skedari dts

Të them të drejtën, nuk jam i sigurt në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 tjetër në config.txt

dtoverlay=at25:spimaxfrequency=50000000

Do ta anashkaloj lidhjen aktuale midis çipit dhe Raspberry Pi. Nga njëra anë, nuk jam ekspert i elektronikës, por nga ana tjetër, është mjaft e thjeshtë edhe për mua: çipi ka vetëm 8 kunja, nga të cilat na duhen tokëzimi, energjia dhe SPI (CS, SI, SO, SCK). Nivelet janë të njëjta me ato në Raspberry Pi dhe nuk kërkohet asnjë instalim shtesë - thjesht lidhni gjashtë kunjat e treguara.

Formulimi i problemit

Si zakonisht, formulimi i problemit kalon nëpër disa përsëritje dhe mendoj se është koha për një tjetër. Pra, le të ndalemi, të mbledhim së bashku atë që është shkruar tashmë dhe të sqarojmë çdo detaj të mbetur të paqartë.

Pra, kemi vendosur që regjistri do të ruhet në SPI NOR Flash.

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

Kjo është një memorie jo e paqëndrueshme që mund të përdoret për tre operacione:

1. Leximi:
   Leximi më i zakonshëm: ne e kalojmë adresën dhe lexojmë aq bajt sa na duhen;
2. regjistruar:
   Shkrimi në memorien NOR duket si një operacion i rregullt, por ka një veçori: mund ta ndryshosh vetëm 1 në 0, por jo anasjelltas. Për shembull, nëse do të kishim 0x55 në një qelizë memorieje, atëherë pasi të shkruajmë 0x0f në të, ajo tani do të përmbajë 0x05. (shih tabelën më poshtë);
3. Fshi:
   Sigurisht, ne gjithashtu duhet të jemi në gjendje të kryejmë operacionin e kundërt - ndryshimin e një 0 në një 1. Pikërisht për këtë shërben operacioni i fshirjes. Ndryshe nga dy të parat, ai vepron në blloqe në vend të bajteve (blloku minimal i fshirjes në çipin e zgjedhur është 4 KB). Fshirja shkatërron të gjithë bllokun, dhe kjo është e vetmja mënyrë për të ndryshuar një 0 në një 1. Prandaj, kur punohet me memorie flash, shpesh është e nevojshme të rreshtohen strukturat e të dhënave me një kufi blloku fshirjeje.
   Duke shkruar në NOR Flash:

Të dhëna binare

ajo ishte
01010101

Regjistruar
00001111

Becomeshtë bërë
00000101

Vetë regjistri është një sekuencë regjistrimesh me gjatësi të ndryshueshme. Një gjatësi tipike e regjistrimit është rreth 30 bajt (megjithëse ndonjëherë hasen regjistrime me gjatësi disa kilobajt). Në këtë rast, ne po punojmë me ta thjesht si një grup bajtesh, por nëse jeni të interesuar, CBOR përdoret brenda të dhënave.

Përveç regjistrit, duhet të ruajmë disa informacione "konfigurimi", si të përditësuara ashtu edhe jo: një ID të caktuar pajisjeje, kalibrimet e sensorëve, flamurin "pajisja është çaktivizuar përkohësisht", etj.
Ky informacion është një grup regjistrash çelës-vlerë, të ruajtura gjithashtu në CBOR. Ne nuk kemi shumë nga ky informacion (disa kilobajt në maksimum) dhe përditësohet rrallë.
Në të ardhmen do ta quajmë kontekst.

Nëse kujtojmë se si filloi ky artikull, është shumë e rëndësishme të sigurohet ruajtja e besueshme e të dhënave dhe, nëse është e mundur, funksionimi i pandërprerë edhe në rast të dështimeve të harduerit/korruptimit të të dhënave.

Cilat burime problemesh mund të merren në konsideratë?

• Ndërprerje të energjisë gjatë operacioneve të shkrimit/fshirjes. Ky është një rast "mungese mbrojtjeje kundër një leve".
  Informacion nga diskutime në stackexchange: kur energjia fiket gjatë punës me flash, si fshirja (e vendosur në 1) ashtu edhe shkrimi (e vendosur në 0) çojnë në sjellje të papërcaktuar: të dhënat mund të shkruhen, të shkruhen pjesërisht (le të themi, transferuam 10 bajt/80 bit, por u shkruan vetëm 45 bit), është gjithashtu e mundur që disa nga bit-at të përfundojnë në një gjendje "të ndërmjetme" (leximi mund të prodhojë 0 ose 1);
• Gabime në vetë memorien flash.
  BER, megjithëse shumë i ulët, nuk mund të jetë i barabartë me zero;
• Gabimet e autobusit
  Të dhënat e transmetuara nëpërmjet SPI-t nuk mbrohen në asnjë mënyrë; gabimet e bitit të vetëm dhe gabimet e sinkronizimit - humbja ose futja e biteve (gjë që çon në korruptim masiv të të dhënave) - mund të ndodhin fare mirë;
• Gabime/defekte të tjera
  Gabime në kod, "gabime" të Raspberry-t, ndërhyrje nga alienët...

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

• Të dhënat duhet të shkruhen menjëherë në memorien flash, vonesa në shkrim nuk merret në konsideratë; - nëse ndodh një gabim, ai duhet të zbulohet dhe përpunohet sa më shpejt të jetë e mundur; - sistemi duhet, sa herë që është e mundur, të rikuperohet nga gabimet.
  (Një shembull nga jeta reale se "si nuk duhet të jetë", të cilin mendoj se të gjithë e kanë hasur: pas një rinisjeje emergjente, sistemi i skedarëve "prishet" dhe sistemi operativ nuk niset)

Ide, qasje, reflektime

Kur fillova të mendoja për këtë problem, më erdhën në mendje një mori idesh, për shembull:

• përdorni kompresimin e të dhënave;
• përdorni struktura të zgjuara të të dhënave, të tilla si ruajtja e titujve të regjistrimeve veçmas nga vetë regjistrimet, në mënyrë që nëse ka një gabim në një regjistrim, pjesa tjetër të mund të lexohet pa probleme;
• përdorni fushat e biteve për të kontrolluar përfundimin e shkrimit kur energjia është e fikur;
• ruaj kontrollet për gjithçka dhe të gjithë;
• përdorni një formë të kodimit për korrigjimin e gabimeve.

Disa nga këto ide u përdorën, të tjerat u braktisën. Le t'i marrim me radhë.

Kompresimi i të dhënave

Ngjarjet që regjistrojmë në regjistër janë mjaft uniforme dhe të përsëritshme ("hedhja e një monedhe 5 rublash", "shtypja e butonit të ndërrimit", etj.). Prandaj, kompresimi duhet të jetë mjaft efektiv.

Mbingarkesa e kompresimit është e papërfillshme (procesori ynë është mjaft i fuqishëm; edhe Pi origjinal kishte një bërthamë të vetme 700 MHz, ndërsa modelet aktuale kanë bërthama të shumëfishta që funksionojnë me mbi një gigahertz), shpejtësia e transferimit të ruajtjes është e ulët (disa megabajt për sekondë) dhe madhësia e regjistrimit është e vogël. Në përgjithësi, nëse kompresimi ka ndonjë ndikim në performancë, ai do të jetë vetëm pozitiv. (absolutisht pa kritikë, thjesht po e them)Plus, ne nuk kemi një të vërtetë të integruar, por një të rregullt. Linux — kështu që zbatimi nuk duhet të kërkojë shumë përpjekje (mjafton të lidhësh bibliotekën dhe të përdorësh disa funksione prej saj).

Një pjesë e të dhënave të regjistrit u mor nga një pajisje funksionale (1.7 MB, 70 mijë hyrje) dhe së pari u kontrollua për kompresueshmëri duke përdorur gzip, lz4, lzop, bzip2, xz, zstd të disponueshme në kompjuter.

• gzip, xz, zstd treguan rezultate të ngjashme (40Kb).
  U habita që xz në modë u shfaq këtu në nivelin e gzip ose zstd;
• lzip me cilësimet fillestare dha rezultate pak më të këqija;
• lz4 dhe lzop nuk treguan rezultate shumë të mira (150Kb);
• bzip2 tregoi një rezultat çuditërisht të mirë (18Kb).

Pra, të dhënat kompresohen shumë mirë.
Pra, (përveç nëse gjejmë ndonjë të metë të rëndë), kompresimi do të jetë diçka e zakonshme! Thjesht sepse e njëjta memorie flash do të mbajë më shumë të dhëna.

Le të mendojmë për disavantazhet.

Problemi i parë: ne kemi rënë dakord që çdo shkrim duhet të shkruhet menjëherë në memorien flash. Zakonisht, një arkivues mbledh të dhëna nga rrjedha hyrëse derisa të vendosë se është koha për të shkruar në rrjedhën dalëse. Ne duhet të marrim menjëherë një bllok të kompresuar të dhënash dhe ta ruajmë atë në memorien jo të paqëndrueshme.

Unë shoh tre mënyra:

1. Kompresoni çdo regjistrim duke përdorur kompresimin e fjalorit në vend të algoritmeve të diskutuara më sipër.
   Është një opsion krejtësisht i zbatueshëm, por mua nuk më pëlqen. Për të arritur një nivel të mirë kompresimi, fjalori duhet të përshtatet sipas të dhënave specifike; çdo ndryshim do të rezultojë në një rënie katastrofike të kompresimit. Po, krijimi i një versioni të ri të fjalorit e zgjidh problemin, por kjo është një dhimbje koke e vërtetë - do të na duhej të ruanim të gjitha versionet e fjalorit; çdo hyrje do të duhej të tregonte se me cilin version të fjalorit është kompresuar...
2. Kompresoni çdo rekord duke përdorur algoritme "klasike", por në mënyrë të pavarur nga të tjerët.
   Algoritmet e kompresimit që po shqyrtohen nuk janë të dizajnuara për të punuar me të dhëna të kësaj madhësie (dhjetëra bajt); raporti i kompresimit do të jetë qartësisht më pak se 1 (domethënë, një rritje në vëllimin e të dhënave në vend të kompresimit);
3. Bëni një SHPËLARJE pas çdo hyrjeje.
   Shumë biblioteka kompresimi mbështesin FLUSH. Ky është një komandë (ose parametër për procedurën e kompresimit) që, pas marrjes, arkivuesi krijon një rrjedhë të kompresuar në mënyrë që të mund të përdoret për rikuperim. të gjithë të dhëna të pakompresuara që janë marrë tashmë. Ky analog sync në sistemet e skedarëve ose commit në SQL.
   Ajo që është e rëndësishme është që operacionet pasuese të kompresimit do të jenë në gjendje të përdorin fjalorin e akumuluar, dhe raporti i kompresimit nuk do të vuajë aq shumë sa në versionin e mëparshëm.

Mendoj se është e qartë që zgjodha opsionin e tretë, le ta shohim më në detaje.

Gjetur artikull i shkëlqyeshëm rreth FLUSH në zlib.

Bëra një provë të shpejtë bazuar në artikull, duke marrë 70 hyrje në regjistër nga një pajisje e vërtetë, me një madhësi faqeje prej 60 KB. (Do të kthehemi te madhësia e faqes më vonë) marrë:

Të dhënat fillestare
Kompresim 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ë, kostoja e FLUSH duket e tepërt, por në realitet, kemi një zgjedhje të kufizuar: ose aspak kompresim, ose kompresim (dhe mjaft efektiv) me FLUSH. Mbani mend se kemi 70 regjistrime, dhe redundanca e prezantuar nga Z_PARTIAL_FLUSH është vetëm 4-5 bajt për regjistrim. Dhe raporti i kompresimit doli të ishte pothuajse 5:1, që është më shumë se i shkëlqyer.

Mund të duket e habitshme, por Z_SYNC_FLUSH është në fakt një mënyrë më efikase për të bërë një FLUSH.

Kur përdorni Z_SYNC_FLUSH, katër bajtet e fundit të çdo regjistrimi do të jenë gjithmonë 0x00, 0x00, 0xff, 0xff. Nëse i dimë këto vlera, nuk kemi nevojë t'i ruajmë ato, kështu që madhësia përfundimtare është vetëm 324 KB.

Artikulli që e lidha e shpjegon këtë:

Shtohet një bllok i ri i tipit 0 me përmbajtje bosh.

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

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

Siç mund ta shihni, në bllokun e fundit, ka midis 3 dhe 10 bit zero para këtyre 4 bajteve. Megjithatë, përvoja ka treguar se në të vërtetë ka të paktën 10 bit zero.

Rezulton se blloqe të tilla të shkurtra të të dhënave zakonisht (gjithmonë?) kodohen duke përdorur një bllok të tipit 1 (bllok fiks), i cili gjithmonë përfundon me 7 bit zero, duke rezultuar në 10-17 bit zero të garantuar (dhe pjesa tjetër do të jetë zero me një probabilitet prej rreth 50%).

Pra, në të dhënat e testimit, në 100% të rasteve, para 0x00, 0x00, 0xff, 0xff ka një bajt zero, dhe në më shumë se një të tretën e rasteve, ka dy bajt zero. (ndoshta problemi është se unë po përdor CBOR binar, dhe nëse do të përdorja JSON tekstual, do të hasja më shpesh blloqe të tipit 2 - bllok dinamik, dhe për këtë arsye do të hasja blloqe pa zero bajt shtesë para 0x00, 0x00, 0xff, 0xff).

Në total, duke përdorur të dhënat e testimit në dispozicion, është e mundur të futen më pak se 250 KB të dhëna të kompresuara.

Mund të kursejmë edhe pak duke bërë pak xhonglim: tani injorojmë praninë e disa bit-ave zero në fund të një blloku, dhe disa bit-a në fillim të një blloku janë gjithashtu të pandryshuar…
Por këtu mora një vendim me vullnet të fortë për të ndaluar, përndryshe me këtë ritëm mund të përfundoja duke zhvilluar arkivuesin tim.

Në total, mora 3-4 bajt për regjistrim nga të dhënat e mia të testimit, duke rezultuar në një raport kompresimi mbi 6:1. Sinqerisht, nuk e prisja një rezultat të tillë; sipas mendimit tim, çdo gjë më e mirë se 2:1 është tashmë një rezultat që justifikon përdorimin e kompresimit.

Gjithçka është shkëlqyeshëm, por zlib (deflate) është ende një algoritëm kompresimi arkaik, i merituar dhe disi i modës së vjetër. Vetë fakti që përdor 32 KB-të e fundit të rrjedhës së të dhënave të pakompresuara si fjalor duket i çuditshëm sot (domethënë, nëse një bllok të dhënash është shumë i ngjashëm me atë që ishte në rrjedhën hyrëse 40 KB më parë, ai do të fillojë të kompresohet përsëri në vend që t'i referohet hyrjes së mëparshme). Në arkivuesit modernë, madhësia e fjalorit shpesh matet në megabajt në vend të kilobajtëve.

Pra, le të vazhdojmë mini-hulumtimin tonë të arkivistëve.

Më pas, provova bzip2 (mbani mend, pa FLUSH, tregoi një raport kompresimi fantastik, pothuajse 100:1). Fatkeqësisht, me FLUSH, performoi shumë dobët; të dhënat e kompresuara përfunduan duke qenë më të mëdha se ato të pakompresuara.

Supozimet e mia rreth arsyeve të dështimit

Libbz2 ofron vetëm një opsion pastrimi, i cili duket se e pastron fjalorin (analog me Z_FULL_FLUSH në zlib), kështu që nuk ka kuptim të flasim për ndonjë kompresim efektiv pas kësaj.

Dhe së fundmi, provova zstd. Në varësi të parametrave, kompresohet ose në nivelin e gzip, por shumë më shpejt, ose më mirë se gzip.

Fatkeqësisht, me FLUSH gjithashtu nuk funksionoi shumë mirë: madhësia e të dhënave të kompresuara ishte rreth 700 KB.

Я bëri një pyetje Në faqen Github të projektit, mora përgjigjen se duhet të priten deri në 10 bajt të dhënash shërbimi për secilin bllok të të dhënave të kompresuara, që është afër rezultateve të marra; nuk do të jetë e mundur të kapet niveli i deflatimit.

Në këtë pikë, vendosa të ndaloj eksperimentimin me arkivuesit (më lejoni t'ju kujtoj se xz, lzip, lzo dhe lz4 nuk treguan vlerën e tyre as në fazën e testimit pa FLUSH, dhe nuk mora në konsideratë algoritme më ekzotike të kompresimit).

Le të kthehemi te problemet e arkivimit.

Problemi i dytë (siç u tha në radhë, jo në rëndësi) është se të dhënat e kompresuara janë një rrjedhë e vetme që i referohet vazhdimisht seksioneve të mëparshme. Prandaj, nëse një seksion i të dhënave të kompresuara dëmtohet, ne humbasim jo vetëm bllokun e lidhur me të dhënat e pakompresuara, por edhe të gjitha blloqet pasuese.

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

1. Parandalimi i shfaqjes së problemeve do të thotë shtimi i tepricës në të dhënat e kompresuara për të lejuar zbulimin dhe korrigjimin e gabimeve; do ta diskutojmë këtë më vonë;
2. Minimizoni pasojat nëse ndodh një problem
   Ne kemi përmendur tashmë se çdo bllok i të dhënave mund të kompresohet në mënyrë të pavarur, gjë që do të eliminonte problemin (korruptimi i të dhënave në një bllok do të rezultonte vetëm në humbjen e atij blloku). Megjithatë, ky është një rast ekstrem, që e bën kompresimin e të dhënave joefektiv. Ekstremi i kundërt: përdorimi i të gjitha 4 MB të çipit tonë si një arkiv i vetëm, gjë që do të siguronte kompresim të shkëlqyer, por do të kishte pasoja katastrofike nëse ndodh korruptimi i të dhënave.
   Po, nevojitet një kompromis për sa i përket besueshmërisë. Por duhet të kujtojmë se po zhvillojmë një format të ruajtjes së të dhënave për memorien jo të paqëndrueshme me një BER jashtëzakonisht të ulët dhe një periudhë të deklaruar ruajtjeje të të dhënave prej 20 vjetësh.

Gjatë eksperimenteve të mia, zbulova se humbjet pak a shumë të dukshme në nivelin e kompresimit fillojnë me blloqe të të dhënave të kompresuara me madhësi më të vogël se 10 KB.
Më parë u përmend se memoria e përdorur është e bazuar në faqe, nuk shoh ndonjë arsye pse të mos përdorni përputhjen "një faqe - një bllok të dhënash të kompresuara".

Kjo do të thotë që madhësia minimale e arsyeshme e faqes është 16 KB (me disa mundësi për mbingarkesë). Megjithatë, një madhësi kaq e vogël e faqes vendos kufizime të rëndësishme në madhësinë maksimale të regjistrimit.

Edhe pse nuk pres të kem të dhëna më të mëdha se disa kilobajt në formë të kompresuar, vendosa të përdor faqe prej 32 KB (që më jep 128 faqe për çip).

Përmbledhje:

• Ne i ruajmë të dhënat e kompresuara duke përdorur zlib (deflate);
• Për çdo hyrje vendosim Z_SYNC_FLUSH;
• Për çdo rekord të kompresuar, ne shkurtojmë bajtet që vijnë pas. (për shembull, 0x00, 0x00, 0xff, 0xff); në kokë tregojmë se sa bajt i presim;
• Ne i ruajmë të dhënat në faqe prej 32 KB; brenda secilës faqe, ekziston një rrjedhë e vetme e të dhënave të kompresuara; kompresimi rifillon në secilën faqe.

Dhe, përpara se të përfundoj me kompresimin, do të doja të theksoja se marrim vetëm disa bajt të të dhënave të kompresuara për regjistrim, kështu që është jashtëzakonisht e rëndësishme të mos e ekzagjerojmë informacionin e shërbimit; çdo bajt llogaritet këtu.

Ruajtja e titujve të të dhënave

Meqenëse kemi regjistrime me gjatësi të ndryshueshme, duhet të përcaktojmë disi vendosjen/kufijtë e regjistrimeve.

Unë njoh tre qasje:

1. Të gjitha të dhënat ruhen në një rrjedhë të vazhdueshme, së pari vjen koka e të dhënave që përmban gjatësinë dhe pastaj vetë të dhënat.
   Në këtë variant, si header-at ashtu edhe të dhënat mund të jenë me gjatësi të ndryshueshme.
   Në thelb, marrim një listë të lidhur një herë që përdoret gjatë gjithë kohës;
2. Titujt dhe vetë regjistrimet ruhen në rrjedha të ndara.
   Duke përdorur header-a me gjatësi konstante, ne sigurohemi që korruptimi i një header-i të mos ndikojë te të tjerët.
   Një qasje e ngjashme përdoret, për shembull, në shumë sisteme skedarësh;
3. Regjistrimet ruhen në një rrjedhë të vazhdueshme, me një kufi regjistrimi të përcaktuar nga një shënues (një karakter ose sekuencë karakteresh që është e ndaluar brenda blloqeve të të dhënave). Nëse haset një shënues brenda një regjistrimi, ne e zëvendësojmë atë me një sekuencë të caktuar (escape it).
   Një qasje e ngjashme përdoret, për shembull, në protokollin PPP.

Më lejoni të ilustroj.

Opsioni 1:

Është shumë e thjeshtë: duke ditur gjatësinë e regjistrimit, mund të llogarisim adresën e kokës tjetër. Lëvizim nëpër kokëza derisa të hasim një zonë të mbushur me 0xff (hapësirë ​​të lirë) ose në fund të faqes.

Opsioni 2:

Për shkak të gjatësisë së ndryshueshme të regjistrimit, nuk mund të parashikojmë se sa regjistrime (dhe për rrjedhojë tituj) do të na duhen për faqe. Mund t'i ndajmë titujt dhe të dhënat nëpër faqe të ndryshme, por unë preferoj një qasje tjetër: i vendosim si titujt ashtu edhe të dhënat në një faqe të vetme, por titujt (me gjatësi konstante) fillojnë në krye të faqes, dhe të dhënat (me gjatësi të ndryshueshme) fillojnë në fund. Sapo ato "takohen" (nuk ka hapësirë ​​të mjaftueshme për një regjistrim të ri), e konsiderojmë faqen të plotë.

Opsioni 3:

Nuk ka nevojë të ruhet gjatësia ose informacione të tjera për vendndodhjen e të dhënave në kokë; shënuesit që tregojnë kufijtë e regjistrimeve janë të mjaftueshëm. Megjithatë, të dhënat duhet të përpunohen kur shkruhen/lexohen.
Do të përdorja 0xff (me të cilin mbushet faqja pas fshirjes) si shënues, në mënyrë që zona e lirë të mos trajtohet si e dhënë.

Tabela krahasuese:

Opsioni 1
Opsioni 2
Opsioni 3

Toleranca e gabimeve
-
+
+

densitet
+
-
+

Vështirësia e zbatimit
*
**
**

Opsioni 1 ka një të metë fatale: nëse ndonjë kokërr dëmtohet, i gjithë zinxhiri pasues shkatërrohet. Opsionet e tjera lejojnë rikuperimin e pjesshëm të të dhënave edhe në rast të dëmtimit të përhapur.
Por këtu është e përshtatshme të kujtojmë se vendosëm t'i ruanim të dhënat në formë të kompresuar, dhe gjithsesi i humbasim të gjitha të dhënat në faqe pas një regjistrimi "të prishur", kështu që edhe pse ka një minus në tabelë, ne nuk e marrim parasysh atë.

Kompaktësia:

• në opsionin e parë, na duhet vetëm të ruajmë gjatësinë në kokë; nëse përdorim numra të plotë me gjatësi të ndryshueshme, atëherë në shumicën e rasteve mund të ia dalim me një bajt;
• Në opsionin e dytë, duhet të ruajmë adresën fillestare dhe gjatësinë; regjistrimi duhet të jetë me një madhësi konstante, unë vlerësoj 4 bajt për regjistrim (dy bajt për zhvendosjen dhe dy bajt për gjatësinë);
• Opsioni i tretë kërkon vetëm një karakter për të treguar fillimin e një regjistrimi, plus vetë regjistrimi do të rritet në madhësi me 1-2% për shkak të escape-it. Në përgjithësi, është pak a shumë në të njëjtin nivel me opsionin e parë.

Fillimisht, e konsiderova opsionin e dytë si kryesor (dhe madje shkrova një implementim). E braktisa vetëm kur vendosa më në fund të përdor kompresimin.

Ndoshta do të përdor një opsion të ngjashëm një ditë. Për shembull, nëse më duhet të ruaj të dhëna për një anije kozmike që udhëton midis Tokës dhe Marsit - kërkesa krejtësisht të ndryshme besueshmërie, rrezatimi kozmik, ...

Sa i përket opsionit të tretë: i dhashë dy yje për kompleksitetin e implementimit thjesht sepse nuk më pëlqen të merrem me escape-in, ndryshimin e gjatësisë në mes të procesit, etj. Po, mund të jem i anshëm, por do të duhet ta shkruaj unë kodin - pse ta detyroj veten të bëj diçka që nuk më pëlqen.

Përmbledhje: Ne zgjedhim opsionin e ruajtjes në formën e zinxhirëve "header me gjatësi - të dhëna me gjatësi të ndryshueshme" për shkak të efikasitetit dhe lehtësisë së zbatimit të tij.

Përdorimi i fushave të biteve për të monitoruar suksesin e operacioneve të shkrimit

Nuk mbaj mend tani nga e mora idenë, por duket diçka si kjo:
Për çdo hyrje, ne ndajmë disa bit për të ruajtur flamujt.
Siç thamë më parë, pas fshirjes të gjitha bitët mbushen me 1, dhe ne mund ta ndryshojmë 1 në 0, por jo anasjelltas. Pra, për "flamuri nuk është vendosur" përdorim 1, për "flamuri është vendosur" përdorim 0.

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

1. Vendos flamurin "regjistrimi i gjatësisë filloi";
2. Ne shkruajmë gjatësinë;
3. Ne vendosëm flamurin "regjistrimi i të dhënave ka filluar";
4. Ne shkruajmë të dhëna;
5. Ne vendosëm flamurin "regjistrimi përfundoi".

Përveç kësaj, do të kemi një flamur "ndodhi një gabim", për një total prej 4 flamujsh bit.

Në këtë rast, kemi dy gjendje të qëndrueshme: "1111" (regjistrimi nuk ka filluar) dhe "1000" (regjistrimi ishte i suksesshëm). Në rast të një ndërprerjeje të papritur të procesit të regjistrimit, do të marrim gjendje të ndërmjetme, të cilat më pas mund t'i zbulojmë dhe përpunojmë.

Qasja është interesante, por mbron vetëm nga ndërprerjet e papritura të energjisë dhe dështimet e ngjashme, gjë që, natyrisht, është e rëndësishme, por kjo është larg nga arsyeja e vetme (dhe jo edhe kryesore) për dështimet e mundshme.

Përmbledhje: Le të vazhdojmë përpara në kërkim të një zgjidhjeje të mirë.

Tavolina kontrolli

Shumat e kontrollit ofrojnë gjithashtu një mënyrë për të verifikuar (me siguri të arsyeshme) se po lexojmë saktësisht atë që duhej të ishte shkruar. Dhe, ndryshe nga fushat e biteve të diskutuara më sipër, ato funksionojnë gjithmonë.

Nëse marrim në konsideratë listën e burimeve të mundshme të problemeve që diskutuam më sipër, shuma e kontrollit është e aftë të njohë një gabim pavarësisht nga origjina e tij. (me përjashtim, ndoshta, të të huajve keqdashës - edhe ata mund ta falsifikojnë shumën e kontrollit).

Pra, nëse qëllimi ynë është të verifikojmë që të dhënat janë të paprekura, shumat e kontrollit janë një ide e shkëlqyer.

Zgjedhja e algoritmit të llogaritjes së shumës së kontrollit ishte e drejtpërdrejtë - CRC. Nga njëra anë, vetitë e tij matematikore lejojnë zbulimin 100% të llojeve të caktuara të gabimeve; nga ana tjetër, në të dhëna të rastësishme, ky algoritëm zakonisht tregon një probabilitet përplasjeje që nuk është shumë më i lartë se limiti teorik. Mund të mos jetë algoritmi më i shpejtë, ose gjithmonë ai me më pak përplasje, por ka një cilësi shumë të rëndësishme: në testet që kam hasur, nuk kam hasur ndonjë model që e ka shkaktuar qartë dështimin e tij. Stabiliteti është cilësia kryesore këtu.

Shembull i një studimi vëllimor: Pjesa 1, Pjesa 2 (lidhje për narod.ru, më falni).

Megjithatë, detyra e zgjedhjes së një kontrolli nuk është e plotë; CRC është një familje e tërë kontrollesh. Duhet të vendosim për gjatësinë dhe pastaj të zgjedhim një polinom.

Zgjedhja e gjatësisë së kontrollit nuk është një çështje aq e thjeshtë sa duket në shikim të parë.

Më lejoni ta ilustroj:
Le të kemi probabilitetin e gabimit në secilin bajt dhe shumën ideale të kontrollit, le të llogarisim numrin mesatar të gabimeve për milion regjistrime:

Të dhëna, bajt
Shuma e kontrollit, bajt
Gabime të pazbuluara
Zbulimet e gabimeve të rreme
Numri total i përgjigjeve të pasakta

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

Do të dukej e thjeshtë: zgjidhni një gjatësi kontrolli me një minimum prej pozitivesh të rreme bazuar në gjatësinë e të dhënave që mbrohen, dhe keni mbaruar.

Megjithatë, shumat e shkurtra të kontrollit paraqesin një problem: megjithëse janë të mira në zbulimin e gabimeve me bit të vetëm, ato mund të ngatërrojnë të dhëna krejtësisht të rastësishme si të vlefshme me një probabilitet mjaft të lartë. Kishte tashmë një artikull mbi Habr që e përshkruante këtë. problem në jetën reale.

Prandaj, për ta bërë praktikisht të pamundur përputhjen e rastësishme të shumës së kontrollit, duhet të përdoren shumë kontrolli prej 32 bitësh ose më shumë. (për gjatësi më të mëdha se 64 bit, zakonisht përdoren funksionet kriptografike hash).

Pavarësisht faktit që shkrova më parë se duhet të kursejmë hapësirë ​​me çdo kusht, ne prapë do të përdorim një kontroll 32-bitësh (16 bit nuk janë të mjaftueshëm, probabiliteti i një përplasjeje është më i madh se 0.01%; dhe 24 bit, siç thonë, nuk janë as këtu as atje).

Këtu mund të lindë një kundërshtim: a e ruajtëm vërtet çdo bajt kur zgjodhëm kompresimin, vetëm që tani të na duhej të jepnim katër bajt njëherësh? A nuk do të kishte qenë më mirë të mos kompresonim ose të mos shtonim një shumë kontrolli? Sigurisht që jo, pa kompresim. nuk do të thotë, se nuk kemi nevojë për kontroll të integritetit.

Lidhur me zgjedhjen e polinomit, ne nuk do ta shpikim rrotën, por do të marrim CRC-32C që është aktualisht popullor.
Ky kod zbulon gabime 6 bit në paketa deri në 22 bajt (ndoshta rasti më i zakonshëm për ne), gabime 4 bit në paketa deri në 655 bajt (gjithashtu një rast i zakonshëm për ne), 2 ose çdo numër tek gabimesh bit në paketa me çdo gjatësi të arsyeshme.

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

Artikull në Wikipedia rreth KDF-së.

Parametrat e kodit CRC-32c mbi Uebfaqja e Kupmanit — ndoshta specialisti kryesor i CRC në planet.

В artikulli i tij ka një kod tjetër interesant, i cili ofron parametra pak më të mirë për gjatësitë e paketave që janë të rëndësishme për ne, por unë nuk e konsiderova ndryshimin të rëndësishëm dhe nuk e konsiderova veten mjaftueshëm kompetent për të zgjedhur kodin e personalizuar mbi atë standard dhe të hulumtuar mirë.

Gjithashtu, meqenëse të dhënat tona janë të kompresuara, lind pyetja: a duhet të llogarisim shumën e kontrollit të të dhënave të kompresuara apo të pakompresuara?

Argumentet në favor të llogaritjes së shumës së kontrollit të të dhënave të pakompresuara:

• Në fund të fundit, duhet të kontrollojmë integritetin e ruajtjes së të dhënave - kështu që e kontrollojmë drejtpërdrejt (në të njëjtën kohë, do të kontrollohen gabimet e mundshme në zbatimin e kompresimit/dekompresimit, dëmtimet e shkaktuara nga memoria e dobët, etj.);
• Algoritmi i deflatimit në zlib ka një implementim mjaft të pjekur dhe nuk duhet rrëzim me të dhëna hyrëse "të shtrembëra", për më tepër, shpesh është në gjendje të zbulojë në mënyrë të pavarur gabimet në rrjedhën hyrëse, duke zvogëluar probabilitetin e përgjithshëm të moszbulimit të një gabimi (Unë kryeva një test me përmbysjen e një biti të vetëm në një regjistrim të shkurtër, zlib zbuloi një gabim në rreth një të tretën e rasteve).

Argumentet kundër llogaritjes së shumës së kontrollit të të dhënave të pakompresuara:

• CRC është projektuar posaçërisht për gabimet e pakta të biteve që janë tipike për memorien flash (një gabim biti në një rrjedhë të kompresuar mund të shkaktojë një ndryshim masiv në rrjedhën e daljes, në të cilën, thjesht teorikisht, mund të "kapim" një përplasje);
• Nuk më pëlqen shumë ideja e furnizimit të të dhënave potencialisht të korruptuara me dekompresorin, kush e di, si do të reagojë ai.

Në këtë projekt, vendosa të devijoj nga praktika përgjithësisht e pranuar e ruajtjes së një kontrolli të të dhënave të pakompresuara.

Përmbledhje: Ne përdorim CRC-32C, llogarisim checksum nga të dhënat në formën në të cilën ato janë shkruar në flash (pas kompresimit).

Teprica

Përdorimi i kodimit të tepërt, sigurisht, nuk eliminon humbjen e të dhënave; megjithatë, ai mund të zvogëlojë ndjeshëm (shpesh me shumë urdhra madhësie) mundësinë e humbjes së pariparueshme të të dhënave.

Ne mund të përdorim lloje të ndryshme të redundancës për të korrigjuar gabimet.
Kodet Hamming mund të korrigjojnë gabimet e një biti të vetëm, kodet Reed-Solomon mund të jenë simbolike, kopje të shumëfishta të të dhënave së bashku me shumat e kontrollit, ose kodimi si RAID-6 mund të ndihmojë në rikuperimin e të dhënave edhe në rast të korruptimit masiv.
Fillimisht, isha i prirur të përdorja gjerësisht kodimin që korrigjon gabimet, por më pas kuptova se së pari duhet të kemi një ide se nga cilat gabime duam të mbrohemi, dhe pastaj të zgjedhim kodimin.

Më parë përmendëm se gabimet duhet të identifikohen sa më shpejt të jetë e mundur. Kur ka të ngjarë të hasim gabime?

1. Regjistrim i papërfunduar (për ndonjë arsye, energjia elektrike u ndërpre gjatë regjistrimit, Raspberry Pi ngriu, etj.)
   Fatkeqësisht, në rast të një gabimi të tillë, e vetmja mundësi është të injorohen të dhënat e pavlefshme dhe të konsiderohen të dhënat e humbura;
2. Gabime shkrimi (për ndonjë arsye, diçka tjetër nga ajo që u shkrua u shkrua në memorien flash)
   Ne mund t’i zbulojmë menjëherë gabime të tilla nëse bëjmë një lexim testimi menjëherë pas regjistrimit;
3. Korruptim i të dhënave në memorie gjatë ruajtjes;
4. Gabime në lexim
   Për të korrigjuar gabimin, nëse shuma e kontrollit nuk përputhet, mjafton të përsërisni leximin disa herë.

Kjo do të thotë që vetëm gabimet e tipit 3 (korruptimi spontan i të dhënave gjatë ruajtjes) nuk mund të korrigjohen pa kodim korrigjues të gabimeve. Duket se gabime të tilla janë ende jashtëzakonisht të pamundura.

Përmbledhje: U vendos që të braktiset kodimi i tepërt, por nëse operacioni tregon se ky vendim është i gabuar, atëherë do të kthehemi në shqyrtimin e çështjes (me statistikat e grumbulluara tashmë mbi dështimet, të cilat do të na lejojnë të zgjedhim llojin optimal të kodimit).

Tjetër

Sigurisht, formati i artikullit nuk lejon të justifikohet çdo pjesë e formatit. (dhe unë jam tashmë i lodhur), kështu që do të shqyrtoj shkurtimisht disa pika që nuk u përmendën më parë.

• U vendos që të gjitha faqet të ishin "të barabarta"
  Kjo do të thotë, nuk do të ketë faqe të veçanta me meta të dhëna, rrjedha të ndara etj., por në vend të kësaj një rrjedhë të vetme që rishkruan të gjitha faqet me radhë.
  Kjo siguron konsumim të njëtrajtshëm të faqeve, asnjë pikë të vetme defekti dhe thjesht një pamje të këndshme;
• Është thelbësore të sigurohet versionimi i formatit.
  Një format pa një numër versioni në kokë është i keq!
  Mjafton të shtoni një fushë me një Numër Magjik (nënshkrim) të caktuar në kokën e faqes, e cila do të tregojë versionin e formatit të përdorur. (Nuk mendoj se do të ketë as një duzinë prej tyre në praktikë);
• Përdorni një kokë me gjatësi të ndryshueshme për regjistrimet (të cilat ka shumë), duke u përpjekur ta bëni atë 1 bajt të gjatë në shumicën e rasteve;
• Për të koduar gjatësinë e kokës dhe gjatësinë e pjesës së cunguar të regjistrimit të kompresuar, përdorni kode binare me gjatësi të ndryshueshme.

Ishte shumë e dobishme gjenerator online Kodet Huffman. Vetëm brenda pak minutash, ne arritëm të gjenim kodet e kërkuara me gjatësi të ndryshueshme.

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

Renditja e bajteve

Fushat më të mëdha se një bajt ruhen në formatin big-endian (renditja e bajteve të rrjetit), domethënë, 0x1234 shkruhet si 0x12, 0x34.

Ndarja në faqe

E gjithë memoria flash është e ndarë në faqe me madhësi të barabartë.

Madhësia e parazgjedhur e faqes është 32 KB, por jo më shumë se 1/4 e madhësisë totale të çipit të memories (për një çip 4 MB kjo rezulton në 128 faqe).

Çdo faqe ruan të dhëna në mënyrë të pavarur nga të tjerat (domethënë, të dhënat në një faqe nuk i referohen të dhënave në një faqe tjetër).

Të gjitha faqet numërohen në rend natyror (në rend rritës të adresave), duke filluar me numrin 0 (faqja zero fillon në adresën 0, e para në 32 KB, e dyta në 64 KB, etj.)

Çipi i memories përdoret si një buffer unazor, domethënë, së pari regjistrimi shkon në faqen numër 0, pastaj në faqen numër 1, ..., kur mbushim faqen e fundit, fillon një cikël i ri dhe regjistrimi vazhdon nga faqja zero.

Brenda faqes

Në fillim të faqes, ruhet një kokë faqeje prej 4 bajtësh, pastaj një shumë kontrolli e kokës (CRC-32C), më pas të dhënat ruhen në formatin "koka, të dhëna, shumë kontrolli".

Titulli i faqes (i gjelbër i ndyrë në diagram) përbëhet nga:

• fushë dy-bajtëshe e Numrit Magjik (e njohur edhe si tregues i versionit të formatit)
  për versionin aktual të formatit konsiderohet si 0xed00 ⊕ номер страницы;
• numërues dy-bajtësh "Versioni i Faqes" (numri i ciklit të rishkrimit të memories).

Regjistrimet në një faqe ruhen në formë të kompresuar (duke përdorur algoritmin e deflatimit). Të gjitha regjistrimet në një faqe të vetme kompresohen në një rrjedhë të vetme (duke përdorur një fjalor të përbashkët) dhe kompresimi fillon nga e para në çdo faqe të re. Kjo do të thotë që dekompresimi i çdo regjistrimi kërkon të gjitha regjistrimet e mëparshme nga ajo faqe (dhe vetëm ajo faqe).

Çdo regjistrim do të kompresohet me flamurin Z_SYNC_FLUSH, duke rezultuar në përfundimin e rrjedhës së kompresuar me 4 bajt 0x00, 0x00, 0xff, 0xff, ndoshta të paraprirë nga një ose dy zero bajt të tjerë.
Ne e hedhim poshtë këtë sekuencë (4, 5 ose 6 bajt të gjatë) kur shkruajmë në memorien flash.

Titulli i regjistrimit është 1, 2 ose 3 bajt, duke ruajtur:

• një bit (T) që tregon llojin e regjistrimit: 0 - konteksti, 1 - log;
• fushë me gjatësi të ndryshueshme (S) nga 1 në 7 bit, që përcakton gjatësinë e kokës dhe "bishtin" që duhet t'i shtohet regjistrimit për çpaketim;
• gjatësia e regjistrimit (L).

Tabela e vlerave të S:

S
Gjatësia e kokës, bajt
U hodh poshtë gjatë shkrimit, bajt

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)

U përpoqa ta ilustroja, por nuk e di sa e qartë doli:

Këtu fusha T është shënuar me të verdhë, fusha S me të bardhë, L (gjatësia e të dhënave të kompresuara në bajt) me të gjelbër, të dhënat e kompresuara me blu dhe bajtet përfundimtare të të dhënave të kompresuara që nuk shkruhen në memorien flash me të kuqe.

Kështu, ne mund të shkruajmë tituj regjistrimesh me gjatësinë më të zakonshme (deri në 63+5 bajt në formë të kompresuar) në një bajt.

Pas çdo shkrimi, ruhet një shumë kontrolli CRC-32C, e cila përdor vlerën e përmbysur të shumës së kontrollit të mëparshëm si vlerë fillestare (init).

CRC ka vetinë e "kohëzgjatjes", formula e mëposhtme funksionon (plus ose minus përmbysja e bitit në proces): .
Kjo do të thotë, ne në fakt llogarisim CRC-në e të gjithë bajteve të kokës dhe të dhënave të mëparshme në këtë faqe.

Menjëherë pas checksum është koka e rekordit tjetër.

Titulli është projektuar në një mënyrë të tillë që bajti i tij i parë të jetë gjithmonë i ndryshëm nga 0x00 dhe 0xff (nëse në vend të bajtit të parë të titullit hasim 0xff, kjo do të thotë se kjo është një zonë e papërdorur; 0x00 sinjalizon një gabim).

Algoritme të përafërta

Leximi nga memoria flash

Çdo lexim shoqërohet me një kontroll të shumës së kontrollit.
Nëse shuma e kontrollit nuk përputhet, leximi përsëritet disa herë me shpresën e leximit përfundimtar të të dhënave të sakta.

(kjo ka kuptim, Linux Nuk ruan në memorje leximet nga NOR Flash, e verifikuar)

Shkrimi në memorien flash

Ne i shkruajmë të dhënat.
Le t’i lexojmë.

Nëse të dhënat e lexuara nuk përputhen me të dhënat e shkruara, ne e mbushim zonën me zero dhe sinjalizojmë një gabim.

Përgatitja e një mikroqarku të ri për operim

Për inicializim, një kokë me versionin 1 shkruhet në faqen e parë (më saktë, zero).
Pas kësaj, konteksti fillestar (që përmban UUID-in e makinës dhe cilësimet fillestare) shkruhet në këtë faqe.

Kaq është, memoria flash është gati për t’u përdorur.

Ngarkimi i makinës

Gjatë ngarkimit, lexohen 8 bajtet e para të secilës faqe (header + CRC); faqet me një Numër Magjik të panjohur ose një CRC të pavlefshëm injorohen.
Nga faqet "e sakta", zgjidhen faqet me versionin maksimal dhe nga këto, merret faqja me numrin më të lartë.
Lexohet regjistrimi i parë, kontrollohet saktësia e CRC-së dhe kontrollohet flamuri "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 "aktive".
dhe në faqen e gjetur lexojmë të gjitha të dhënat, ato me flamurin "kontekst" i aplikojmë.
Ne e ruajmë fjalorin zlib (do të nevojitet për ta shtuar në këtë faqe).

Kaq është, shkarkimi është i plotë, konteksti është rikthyer, mund të punoni.

Shtimi i një hyrjeje në regjistër

Ne e kompresojmë regjistrimin me fjalorin e saktë, duke specifikuar Z_SYNC_FLUSH. Kontrollojmë nëse regjistrimi i kompresuar përshtatet në faqen aktuale.
Nëse nuk përshtatet (ose ka pasur gabime CRC në faqe), filloni një faqe të re (shih më poshtë).
Ne shkruajmë të dhënat dhe e bëjmë CRC-në. Nëse ndodh ndonjë gabim, hapim një faqe të re.

Faqe e re

Ne zgjedhim një faqe falas me numrin më të ulët (e konsiderojmë një faqe me një kontroll të pavlefshëm në kokë ose një version më të ulët se ai aktual) si të lirë. Nëse nuk ka faqe të tilla, ne zgjedhim faqen me numrin më të ulët midis atyre me një version të barabartë me atë aktual.
Ne e fshijmë faqen e zgjedhur. Kontrollojmë përmbajtjen kundrejt 0xff. Nëse diçka nuk shkon, marrim faqen tjetër të disponueshme e kështu me radhë.
Ne e shkruajmë kokën në faqen e fshirë, hyrja e parë është gjendja aktuale e kontekstit dhe hyrja tjetër është hyrja e pashkruar e regjistrit (nëse ka një të tillë).

Zbatueshmëria e formatit

Sipas mendimit tim, ky është një format i mirë për ruajtjen e çdo rrjedhe informacioni pak a shumë të kompresueshme (tekst i thjeshtë, JSON, MessagePack, CBOR, ndoshta protobuf) në NOR Flash.

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

Nuk duhet të përdoret me media me BER të lartë si NAND ose MLC NOR. (A është ky lloj memorieje në dispozicion për shitje? Kam parë përmendje të tij vetëm në dokumente mbi kodet e korrigjimit.).

Për më tepër, nuk duhet të përdoret me pajisje që kanë FTL-në e tyre: USB flash drive, SD, MicroSD, etj. (Për këtë lloj memorieje, krijova një format me një madhësi faqeje prej 512 bajtësh, një nënshkrim në fillim të secilës faqe dhe numra unikë të regjistrimeve - ndonjëherë, isha në gjendje të rikuperoja të gjitha të dhënat nga një flash drive "me probleme" me një lexim të thjeshtë sekuencial).

Në varësi të aplikacionit, formati mund të përdoret pa modifikim në disqe flash nga 128Kbps (16Kbps) deri në 1Gbps (128Mbps). Nëse dëshirohet, mund të përdoret edhe në çipa me kapacitet më të madh, megjithëse madhësia e faqes ka të ngjarë të duhet të rregullohet. (Por këtu lind pyetja e fizibilitetit ekonomik; çmimi i NOR Flash me kapacitet të madh nuk është inkurajues).

Nëse dikush e gjen këtë format interesant dhe dëshiron ta përdorë në një projekt me burim të hapur, më njoftoni. Do të përpiqem të gjej kohën për ta përmirësuar kodin dhe për ta postuar në GitHub.

Përfundim

Siç mund ta shohim, formati doli të ishte i thjeshtë. dhe madje edhe i mërzitshëm.

Është e vështirë të pasqyroj evolucionin e perspektivës sime në një artikull, por më besoni: fillimisht, doja të krijoja diçka të sofistikuar, të pathyeshme, të aftë të mbijetonte edhe një shpërthim bërthamor në afërsi. Megjithatë, arsyeja (shpresoj) përfundimisht mbizotëroi dhe gradualisht përparësitë u zhvendosën drejt thjeshtësisë dhe kompaktësisë.

A mund të gabohem? Po, sigurisht. Mund të jetë shumë mirë, për shembull, që kemi blerë një grup mikroçipash me cilësi të ulët. Ose për ndonjë arsye tjetër, pajisjet nuk do të përmbushin pritjet e besueshmërisë.

A kam ndonjë plan për këtë? Mendoj se pasi ta lexoni këtë artikull, nuk do të keni dyshime se kam. Dhe më shumë se një.

Më seriozisht, formati u zhvillua si një opsion pune dhe si një "tullumbace prove".

Për momentin, gjithçka po funksionon mirë; zgjidhja do të vendoset brenda pak ditësh. (përafërsisht) Në njëqind pajisje, do të shohim se çfarë ndodh në përdorimin "luftarak" (për fat të mirë, shpresoj që formati të lejojë zbulimin e besueshëm të dështimeve, në mënyrë që të jemi në gjendje të mbledhim statistika gjithëpërfshirëse). Brenda disa muajsh, do të jemi në gjendje të nxjerrim përfundime. (dhe nëse je i pafat, edhe më herët).

Nëse, pasi ta kem përdorur, zbuloj ndonjë problem serioz dhe kam nevojë për përmirësime, patjetër që do të shkruaj për këtë.

Letërsi

Nuk doja të përpiloja një listë të gjatë e të lodhshme referencash; në fund të fundit, të gjithë kanë Google.

Këtu vendosa të lë një listë me gjetjet që i gjeta veçanërisht interesante, por gradualisht ato migruan direkt në tekstin e artikullit dhe vetëm një artikull mbeti në listë:

1. Shërbim infgen Nga autori i zlib. Mund të shfaqë qartë përmbajtjen e arkivave deflate/zlib/gzip. Nëse keni nevojë të kuptoni brendësinë e formatit deflate (ose gzip), e rekomandoj fuqimisht.

Burimi: www.habr.com