parahistorinë

Ka makina shitëse të dizajnit tonë. Brenda Raspberry Pi dhe disa instalime elektrike në një tabelë të veçantë. Lidhen një pranues monedhash, një pranues faturash, një terminal banke... Gjithçka kontrollohet nga një program i shkruar vetë. E gjithë historia e punës shkruhet në një regjistër në një flash drive (MicroSD), i cili më pas transmetohet nëpërmjet internetit (duke përdorur një modem USB) në server, ku ruhet në një bazë të dhënash. Informacioni i shitjeve ngarkohet në 1c, ekziston gjithashtu një ndërfaqe e thjeshtë në internet për monitorim, etj.

Kjo do të thotë, ditari është jetik - për kontabilitetin (të ardhurat, shitjet, etj.), monitorimin (të gjitha llojet e dështimeve dhe rrethanat e tjera të forcës madhore); Ky, mund të thuhet, është i gjithë informacioni që kemi për këtë makinë.

problem

Disqet flash tregohen si pajisje shumë jo të besueshme. Dështojnë me rregullsi të lakmueshme. Kjo çon në ndërprerjen e makinës dhe (nëse për ndonjë arsye regjistri nuk mund të transferohej në internet) në humbje të të dhënave.

Kjo nuk është përvoja e parë e përdorimit të disqeve flash, para kësaj ka pasur një projekt tjetër me më shumë se njëqind pajisje, ku revista ruhej në disqet USB, kishte edhe probleme me besueshmërinë, nganjëherë numri i atyre që dështuan në një muaj ishte në dhjetra. Ne provuam disqe të ndryshme flash, duke përfshirë ato të markës me memorie SLC, dhe disa modele janë më të besueshme se të tjerët, por zëvendësimi i disqeve flash nuk e zgjidhi rrënjësisht problemin.

Kujdes! Për një kohë të gjatë! Nëse nuk ju intereson "pse", por vetëm "si", mund të shkoni drejt në fije artikull.

vendim

Gjëja e parë që ju vjen në mendje është: braktisni MicroSD, instaloni, për shembull, një SSD dhe nisni prej saj. Teorikisht e mundur, ndoshta, por relativisht e shtrenjtë dhe jo aq e besueshme (shtohet një përshtatës USB-SATA; statistikat e dështimit për SSD-të buxhetore gjithashtu nuk janë inkurajuese).

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

Prandaj, arritëm te ky opsion: lini nisjen nga MicroSD, por përdorni ato në modalitetin vetëm për lexim dhe ruani regjistrin e funksionimit (dhe informacione të tjera unike për një pjesë të veçantë të harduerit - numrin serial, kalibrimin e sensorit, etj.) diku tjetër .

Tema e FS vetëm për lexim për mjedrat tashmë është studiuar brenda dhe jashtë, nuk do të ndalem në detajet e zbatimit në këtë artikull (por nëse ka interes, ndoshta do të shkruaj një mini-artikull për këtë temë). E vetmja pikë që do të doja të theksoja është se si nga përvoja personale ashtu edhe nga rishikimet e atyre që e kanë zbatuar tashmë, ka një përfitim në besueshmëri. Po, është e pamundur të heqësh qafe plotësisht prishjet, por ulja e ndjeshme e frekuencës së tyre është mjaft e mundur. Dhe kartat po unifikohen, gjë që e bën zëvendësimin shumë më të lehtë për personelin e shërbimit.

Pjesa hardware

Nuk kishte asnjë dyshim të veçantë për zgjedhjen e llojit të kujtesës - NOR Flash.
Argumentet:

lidhje e thjeshtë (më shpesh autobusi SPI, të cilin tashmë keni përvojë në përdorimin, kështu që nuk parashikohen probleme harduerike);
çmim qesharak;
protokolli standard i funksionimit (zbatimi është tashmë në kernelin Linux, nëse dëshironi, mund të merrni një të palës së tretë, e cila është gjithashtu e pranishme, ose edhe të shkruani tuajin, për fat të mirë gjithçka është e thjeshtë);
besueshmëria dhe burimet:
nga një fletë të dhënash tipike: të dhënat ruhen për 20 vjet, 100000 cikle fshirjeje për çdo bllok;
nga burimet e palëve të treta: BER jashtëzakonisht i ulët, postulon se nuk ka nevojë për kode korrigjimi të gabimeve (disa vepra e konsiderojnë ECC për NOR, por zakonisht ato ende nënkuptojnë MLC NOR; kjo ndodh gjithashtu).

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

Do të doja që të dhënat të ruhen për disa ditë të garantuara. Kjo është e nevojshme në mënyrë që në rast të ndonjë problemi komunikimi, historia e shitjeve të mos humbasë. Ne do të fokusohemi në 5 ditë, gjatë kësaj periudhe (madje duke marrë parasysh fundjavat dhe festat) problemi mund të zgjidhet.

Aktualisht mbledhim rreth 100 kb regjistra në ditë (3-4 mijë hyrje), por gradualisht kjo shifër po rritet - detajet po rriten, po shtohen ngjarje të reja. Plus, ndonjëherë ka breshëri (për shembull, disa sensorë fillojnë të postojnë mesazhe të padëshiruara me pozitivë të rremë). Ne do të llogarisim për 10 mijë regjistrime 100 bajt secili - megabajt në ditë.

Në total, dalin 5 MB të dhëna të pastra (të ngjeshura mirë). Më shumë për ta (vlerësim i përafërt) 1 MB të dhëna shërbimi.

Kjo do të thotë, ne kemi nevojë për një çip 8MB nëse nuk përdorim kompresim, ose 4MB nëse e përdorim atë. Numra mjaft realistë për këtë lloj memorie.

Sa i përket burimit: nëse planifikojmë që e gjithë memoria të rishkruhet jo më shumë se një herë në 5 ditë, atëherë mbi 10 vjet shërbim do të marrim më pak se një mijë cikle rishkrimi.
Më lejoni t'ju kujtoj se prodhuesi premton njëqind mijë.

Pak rreth NOR vs NAND

Sot, sigurisht, memoria NAND është shumë më e popullarizuar, por unë nuk do ta përdorja atë për këtë projekt: NAND, ndryshe nga NOR, kërkon domosdoshmërisht përdorimin e kodeve të korrigjimit të gabimeve, një tabelë të blloqeve të këqija, etj., si dhe këmbët e Çipat NAND zakonisht shumë më tepër.

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 e komunikimit (kryesisht për shkak të faktit se përdoret një ndërfaqe serike, zakonisht SPI ose I2C);
fshirje e ngadaltë (në varësi të madhësisë së bllokut, zgjat nga një pjesë e sekondës deri në disa sekonda).

Duket se nuk ka asgjë kritike për ne, ndaj vazhdojmë.

Nëse detajet janë interesante, mikroqarku është zgjedhur në 25df321a (megjithatë, kjo është e parëndësishme, ka shumë analoge në treg që janë të pajtueshme në sistemin pinout dhe komandimi; edhe nëse duam të instalojmë një mikroqark nga një prodhues dhe/ose një madhësi të ndryshme, gjithçka do të funksionojë pa ndryshuar kodi).

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

Shembull i skedarit dts

Për të qenë i sinqertë, 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 tjetër në config.txt

dtoverlay=at25:spimaxfrequency=50000000

Do të heq përshkrimin e lidhjes së çipit me Raspberry Pi. Nga njëra anë, unë nuk jam ekspert në elektronikë, nga ana tjetër, gjithçka këtu është banale edhe për mua: mikroqarku ka vetëm 8 këmbë, nga të cilat ne kemi nevojë për tokë, fuqi, SPI (CS, SI, SO, SCK ); nivelet janë të njëjta me ato të Raspberry Pi, nuk kërkohet instalime elektrike shtesë - thjesht lidhni 6 kunjat e treguara.

Formulimi i problemit

Si zakonisht, deklarata e problemit kalon nëpër disa përsëritje dhe më duket se është koha për tjetrën. Pra, le të ndalemi, të bashkojmë atë që tashmë është shkruar dhe të sqarojmë detajet që mbeten në hije.

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

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

Kjo është memorie jo e paqëndrueshme me të cilën mund të kryeni tre operacione:

Leximi:
Leximi më i zakonshëm: ne transmetojmë adresën dhe lexojmë aq bajt sa na duhen;
regjistruar:
Shkrimi në NOR flash duket si i rregullt, por ka një veçori: mund të ndryshoni vetëm 1 në 0, por jo anasjelltas. Për shembull, nëse kishim 0x55 në një qelizë memorie, atëherë pasi të shkruanim 0x0f në të, 0x05 tashmë do të ruhet atje (shih tabelën më poshtë);
Fshi:
Natyrisht, ne duhet të jemi në gjendje të bëjmë operacionin e kundërt - të ndryshojmë 0 në 1, pikërisht për këtë është operacioni i fshirjes. Ndryshe nga dy të parat, ai nuk funksionon me bajt, por me blloqe (blloku minimal i fshirjes në çipin e zgjedhur është 4 kb). Erase shkatërron të gjithë bllokun dhe është mënyra e vetme për të ndryshuar 0 në 1. Prandaj, kur punoni me memorie flash, shpesh duhet të rreshtoni strukturat e të dhënave me kufirin e bllokut të fshirjes.
Regjistrimi në NOR Flash:

Të dhënat binare

ajo ishte
01010101

I regjistruar
00001111

Becomeshtë bërë
00000101

Vetë regjistri përfaqëson një sekuencë regjistrimesh me gjatësi të ndryshueshme. Gjatësia tipike e një rekordi është rreth 30 bajt (edhe pse ndonjëherë ndodhin regjistrime që janë disa kilobajtë në gjatësi). Në këtë rast, ne punojmë me ta thjesht si një grup bajtësh, por, nëse jeni të interesuar, CBOR përdoret brenda rekordeve

Përveç regjistrit, duhet të ruajmë disa informacione "konfigurimi", të përditësuara dhe jo: një ID të caktuar të pajisjes, kalibrimet e sensorit, një flamur "pajisja është çaktivizuar përkohësisht", etj.
Ky informacion është një grup regjistrimesh me vlerë kyçe, të ruajtura gjithashtu në CBOR. Ne nuk kemi shumë nga ky informacion (më së shumti disa kilobajt) dhe përditësohet rrallë.
Në vijim do ta quajmë kontekst.

Nëse kujtojmë se ku 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 vazhdueshëm edhe në rast të dështimeve të harduerit/korruptimit të të dhënave.

Cilat burime problemesh mund të merren parasysh?

Fikeni gjatë operacioneve të shkrimit/fshirjes. Kjo është nga kategoria e "nuk ka mashtrim kundër levës".
Informacion nga diskutime në stackexchange: kur rryma fiket gjatë punës me blic, si fshirja (caktuar në 1) ashtu edhe shkrimi (caktuar në 0) çojnë në sjellje të pacaktuar: të dhënat mund të shkruhen, të shkruhen pjesërisht (të themi, kemi transferuar 10 byte/80 bit , por nuk mund të shkruhen ende vetëm 45 bit), është gjithashtu e mundur që disa nga bit-at të jenë në një gjendje "të ndërmjetme" (leximi mund të prodhojë si 0 ashtu edhe 1);
Gabime në vetë memorien flash.
BER, edhe pse shumë i ulët, nuk mund të jetë i barabartë me zero;
Gabimet e autobusit
Të dhënat e transmetuara nëpërmjet SPI nuk mbrohen në asnjë mënyrë; mund të ndodhin si gabime në një bit ashtu edhe gabime sinkronizimi - humbja ose futja e biteve (që çon në shtrembërim masiv të të dhënave);
Gabime / defekte të tjera
Gabime në kod, defekte në Raspberry, ndërhyrje nga jashtëtokësorët...

Unë kam formuluar kërkesat, përmbushja e të cilave, për mendimin tim, është e nevojshme për të siguruar besueshmërinë:

të dhënat duhet të futen menjëherë në memorie flash, shkrimet e vonuara nuk merren parasysh; - nëse ndodh një gabim, ai duhet të zbulohet dhe përpunohet sa më shpejt që të jetë e mundur; - sistemi duhet, nëse është e mundur, të rikuperohet nga gabimet.
(një shembull nga jeta "si nuk duhet të jetë", të cilin mendoj se të gjithë e kanë hasur: pas një rindezjeje emergjente, sistemi i skedarëve është "i prishur" dhe sistemi operativ nuk niset)

Ide, qasje, reflektime

Kur fillova të mendoj për këtë problem, shumë ide më rrodhën në kokë, për shembull:

përdorni kompresimin e të dhënave;
përdorni struktura të zgjuara të të dhënave, për shembull, ruani titujt e rekordeve veçmas nga vetë regjistrimet, në mënyrë që nëse ka një gabim në ndonjë regjistrim, të mund të lexoni pjesën tjetër pa asnjë problem;
përdorni fushat bit për të kontrolluar përfundimin e regjistrimit kur rryma është e fikur;
ruani shumat e kontrollit për gjithçka;
përdorni një lloj kodimi rezistent ndaj zhurmës.

Disa nga këto ide u përdorën, ndërsa të tjerat u vendosën të braktiseshin. Le të shkojmë me radhë.

Kompresimi i të dhënave

Vetë ngjarjet që ne regjistrojmë në ditar janë mjaft të ngjashme dhe të përsëritshme ("hodhi një monedhë 5 rubla", "shtypi butonin për të dhënë kusur", ...). Prandaj, kompresimi duhet të jetë mjaft efektiv.

Shkalla e sipërme e kompresimit është e parëndësishme (procesori ynë është mjaft i fuqishëm, madje Pi i parë kishte një bërthamë me një frekuencë prej 700 MHz, modelet aktuale kanë disa bërthama me një frekuencë mbi një gigahertz), kursi i këmbimit me ruajtjen është i ulët (disa megabajt për sekondë), madhësia e regjistrimeve është e vogël. Në përgjithësi, nëse kompresimi ka një ndikim në performancën, ai do të jetë vetëm pozitiv. (absolutisht jokritike, thjesht duke deklaruar). Plus, ne nuk kemi Linux të vërtetë të ngulitur, por të rregullt - kështu që zbatimi nuk duhet të kërkojë shumë përpjekje (mjafton thjesht të lidhni bibliotekën dhe të përdorni disa funksione prej saj).

Një pjesë e regjistrit u mor nga një pajisje pune (1.7 MB, 70 mijë hyrje) dhe fillimisht 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 (40 Kb).
U habita që xz në modë u shfaq këtu në nivelin e gzip ose zstd;
lzip me cilësimet e paracaktuar dha rezultate pak më të këqija;
lz4 dhe lzop treguan rezultate jo shumë të mira (150 Kb);
bzip2 tregoi një rezultat çuditërisht të mirë (18 Kb).

Pra, të dhënat janë të ngjeshura shumë mirë.
Pra (nëse nuk gjejmë të meta fatale) do të ketë ngjeshje! Thjesht sepse më shumë të dhëna mund të futen në të njëjtën flash drive.

Le të mendojmë për disavantazhet.

Problemi i parë: ne kemi rënë dakord tashmë që çdo regjistrim duhet të shkojë menjëherë në ndezje. Në mënyrë tipike, arkivuesi mbledh të dhëna nga transmetimi i hyrjes derisa të vendosë se është koha për të shkruar në fundjavë. Duhet të marrim menjëherë një bllok të ngjeshur të dhënash dhe ta ruajmë atë në memorie jo të paqëndrueshme.

Unë shoh tre mënyra:

Kompresoni çdo rekord duke përdorur kompresimin e fjalorit në vend të algoritmeve të diskutuara më sipër.
Është një opsion plotësisht funksional, por nuk më pëlqen. Për të siguruar një nivel pak a shumë të mirë të kompresimit, fjalori duhet të "përshtatet" me të dhëna specifike; çdo ndryshim do të çojë në rënien katastrofike të nivelit të kompresimit. Po, problemi mund të zgjidhet duke krijuar një version të ri të fjalorit, por kjo është një dhimbje koke - do të na duhet të ruajmë të gjitha versionet e fjalorit; në çdo hyrje do të duhet të tregojmë se me cilin version të fjalorit është ngjeshur...
Kompresoni çdo rekord duke përdorur algoritme "klasike", por në mënyrë të pavarur nga të tjerët.
Algoritmet e kompresimit në shqyrtim nuk janë krijuar për të punuar me regjistrime të kësaj madhësie (dhjetëra bajt), raporti i kompresimit do të jetë qartë më i vogël se 1 (d.m.th., rritja e vëllimit të të dhënave në vend të kompresimit);
Bëni FLUSH pas çdo regjistrimi.
Shumë biblioteka të kompresimit kanë mbështetje për FLUSH. Ky është një komandë (ose një parametër i procedurës së kompresimit), pas marrjes së të cilit arkivuesi formon një rrjedhë të ngjeshur në mënyrë që të mund të përdoret për të rivendosur të gjithë të dhëna të pakompresuara që tashmë janë marrë. Një analog i tillë sync në sistemet e skedarëve ose commit në sql.
Ajo që është e rëndësishme është që operacionet e mëvonshme të kompresimit do të jenë në gjendje të përdorin fjalorin e grumbulluar 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ë test gjuri bazuar në artikull, mora 70 mijë hyrje në log nga një pajisje e vërtetë, me një madhësi faqeje 60 Kb (do të kthehemi në madhësinë e faqes më vonë) mori:

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ë pamje të parë, çmimi i kontribuar nga FLUSH është tepër i lartë, por në realitet ne kemi pak zgjedhje - ose të mos ngjeshim fare, ose të ngjeshim (dhe në mënyrë shumë efektive) me FLUSH. Nuk duhet të harrojmë se kemi 70 mijë regjistrime, teprica e futur nga Z_PARTIAL_FLUSH është vetëm 4-5 bajt për rekord. Dhe raporti i kompresimit doli të jetë pothuajse 5:1, që është më shumë se një rezultat i shkëlqyer.

Mund të jetë befasi, por Z_SYNC_FLUSH është në fakt një mënyrë më efikase për të bërë FLUSH

Kur përdorni Z_SYNC_FLUSH, 4 bajtët e fundit të çdo hyrjeje do të jenë gjithmonë 0x00, 0x00, 0xff, 0xff. Dhe nëse i njohim, atëherë nuk kemi pse t'i ruajmë, kështu që madhësia përfundimtare është vetëm 324 Kb.

Artikulli me të cilin u lidha ka një shpjegim:

Është shtuar një bllok i ri i tipit 0 me përmbajtje boshe.

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

kokën e bllokut me tre bit;

0 deri në 7 bit të barabartë me zero, për të arritur shtrirjen e bajtit;

sekuenca prej katër bajtësh 00 00 FF FF.

Siç mund ta shihni lehtësisht, në bllokun e fundit para këtyre 4 bajteve ka nga 3 deri në 10 bit zero. Sidoqoftë, praktika ka treguar se në të vërtetë ka të paktën 10 bit zero.

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

Pra, në të dhënat e testit, në 100% të rasteve ka një bajt zero para 0x00, 0x00, 0xff, 0xff, dhe në më shumë se një e treta e rasteve ka dy bajt zero. (ndoshta fakti është se unë përdor CBOR binar, dhe kur përdor tekstin JSON, blloqet e tipit 2 - bllok dinamik do të ishin më të zakonshëm, përkatësisht, blloqet pa zero bajt shtesë para se të haseshin 0x00, 0x00, 0xff, 0xff).

Në total, duke përdorur të dhënat e disponueshme të testit, është e mundur të futeni në më pak se 250 Kb të dhëna të ngjeshura.

Mund të kurseni pak më shumë duke bërë mashtrime të vogla: tani për tani ne injorojmë praninë e disa biteve zero në fund të bllokut, disa bit në fillim të bllokut gjithashtu nuk ndryshojnë...
Por më pas 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, nga të dhënat e mia të provës që mora 3-4 bajt për shkrim, raporti i kompresimit doli të ishte më shumë se 6:1. Unë do të jem i sinqertë: nuk e prisja një rezultat të tillë; për mendimin tim, çdo gjë më e mirë se 2: 1 është tashmë një rezultat që justifikon përdorimin e kompresimit.

Gjithçka është në rregull, por zlib (shfryrja) është ende një algoritëm kompresimi arkaik, i merituar dhe paksa i modës së vjetër. Thjesht fakti që 32 Kb e fundit e rrjedhës së të dhënave të pakompresuara përdoret si fjalor sot duket i çuditshëm (d.m.th., nëse një bllok i të dhënave është shumë i ngjashëm me atë që ishte në rrjedhën hyrëse 40 Kb më parë, atëherë ai do të fillojë të arkivohet përsëri, dhe nuk do t'i referohet një ndodhie të mëparshme). Në arkivuesit modernë në modë, madhësia e fjalorit matet shpesh në megabajt dhe jo në kilobajt.

Pra, ne vazhdojmë mini-studimin tonë të arkivuesve.

Më pas testuam bzip2 (mos harroni, pa FLUSH ai tregoi një raport fantastik kompresimi prej pothuajse 100:1). Fatkeqësisht, performoi shumë dobët me FLUSH; madhësia e të dhënave të ngjeshur doli të ishte më e madhe se të dhënat e pakompresuara.

Supozimet e mia për arsyet e dështimit

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

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

Mjerisht, me FLUSH 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 një përgjigje që duhet të llogarisni deri në 10 bajtë të të dhënave të shërbimit për çdo bllok të dhënash të ngjeshur, që është afër rezultateve të marra; nuk ka asnjë mënyrë për të kapur hapin e deflate.

Vendosa të ndalem në këtë pikë në eksperimentet e mia me arkivuesit (më lejoni t'ju kujtoj se xz, lzip, lzo, lz4 nuk u shfaqën as në fazën e testimit pa FLUSH, dhe nuk mora parasysh algoritme më ekzotike të kompresimit).

Le të kthehemi te problemet e arkivimit.

Problemi i dytë (siç thonë ata me radhë, jo në vlerë) është se të dhënat e ngjeshur janë një rrjedhë e vetme, në të cilën vazhdimisht ka referenca për seksionet e mëparshme. Kështu, nëse një pjesë e të dhënave të kompresuara dëmtohet, ne humbasim jo vetëm bllokun shoqërues të të dhënave të pakompresuara, por edhe të gjitha ato pasuese.

Ekziston një qasje për të zgjidhur këtë problem:

Parandaloni shfaqjen e problemit - shtoni tepricë në të dhënat e kompresuara, të cilat do t'ju lejojnë të identifikoni dhe korrigjoni gabimet; do të flasim për këtë më vonë;
Minimizoni pasojat nëse shfaqet një problem
Ne kemi thënë tashmë më herët se ju mund të kompresoni çdo bllok të dhënash në mënyrë të pavarur dhe problemi do të zhduket vetë (dëmtimi i të dhënave të një blloku do të çojë në humbjen e të dhënave vetëm për këtë bllok). Megjithatë, ky është një rast ekstrem në të cilin kompresimi i të dhënave do të jetë i paefektshëm. Ekstremi i kundërt: përdorni të gjitha 4MB të çipit tonë si një arkiv i vetëm, i cili do të na japë kompresim të shkëlqyer, por pasoja katastrofike në rast të prishjes së 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 memorie jo të paqëndrueshme me BER jashtëzakonisht të ulët dhe një periudhë të deklaruar të ruajtjes së të dhënave prej 20 vjetësh.

Gjatë eksperimenteve, zbulova se humbjet pak a shumë të dukshme në nivelin e kompresimit fillojnë në blloqe të dhënash të kompresuara me madhësi më të vogël se 10 KB.
U përmend më parë se memoria e përdorur është e faqezuar; nuk shoh asnjë arsye pse të mos përdoret korrespondenca "një faqe - një bllok i të dhënave të kompresuara".

Kjo do të thotë, madhësia minimale e arsyeshme e faqes është 16 Kb (me një rezervë për informacionin e shërbimit). Sidoqoftë, një madhësi kaq e vogël e faqes imponon kufizime të rëndësishme në madhësinë maksimale të regjistrimit.

Megjithëse nuk pres ende regjistrime më të mëdha se disa kilobajt në formë të ngjeshur, vendosa të përdor faqe 32 Kb (për një total prej 128 faqesh për çip).

Përmbledhje:

Ne ruajmë të dhëna të ngjeshur duke përdorur zlib (deflate);
Për çdo hyrje kemi vendosur Z_SYNC_FLUSH;
Për çdo rekord të ngjeshur, ne shkurtojmë bajtët pasues (p.sh. 0x00, 0x00, 0xff, 0xff); në kokë tregojmë sa bajt kemi prerë;
Ne ruajmë të dhëna në faqe 32 Kb; ka një rrjedhë të vetme të të dhënave të ngjeshur brenda faqes; Në çdo faqe fillojmë përsëri ngjeshjen.

Dhe, përpara se të mbaroj me kompresimin, do të doja të tërhiqja vëmendjen tuaj për faktin se ne kemi vetëm disa bajt të dhëna të ngjeshur për regjistrim, kështu që është jashtëzakonisht e rëndësishme të mos fryni informacionin e shërbimit, çdo bajt këtu vlen.

Ruajtja e titujve të të dhënave

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

Unë di tre qasje:

Të gjitha regjistrimet ruhen në një rrjedhë të vazhdueshme, së pari ka një kokë regjistrimi që përmban gjatësinë, dhe më pas vetë rekordin.
Në këtë mishërim, të dy titujt dhe të dhënat mund të jenë me gjatësi të ndryshueshme.
Në thelb, ne marrim një listë të lidhur vetëm që përdoret gjatë gjithë kohës;
Titujt dhe vetë të dhënat ruhen në rrjedha të veçanta.
Duke përdorur titujt me gjatësi konstante, ne sigurohemi që dëmtimi i njërit kokë të mos ndikojë tek të tjerët.
Një qasje e ngjashme përdoret, për shembull, në shumë sisteme skedarësh;
Regjistrimet ruhen në një rrjedhë të vazhdueshme, kufiri i regjistrimit përcaktohet nga një shënues i caktuar (një karakter/sekuencë karakteresh që është e ndaluar brenda blloqeve të të dhënave). Nëse ka një shënues brenda rekordit, atëherë ne e zëvendësojmë atë me një sekuencë (shpëtojmë).
Një qasje e ngjashme përdoret, për shembull, në protokollin PPP.

Unë do të ilustroj.

Opsioni 1:

Gjithçka është shumë e thjeshtë këtu: duke ditur gjatësinë e rekordit, ne mund të llogarisim adresën e kokës tjetër. Kështu kalojmë nëpër titujt derisa ndeshemi me një zonë të mbushur me 0xff (zona e lirë) ose në fund të faqes.

Opsioni 2:

Për shkak të gjatësisë së ndryshueshme të regjistrimit, ne nuk mund të themi paraprakisht se sa regjistrime (dhe për rrjedhojë titujt) do të na duhen për faqe. Ju mund t'i shpërndani vetë titujt dhe të dhënat në faqe të ndryshme, por unë preferoj një qasje të ndryshme: ne vendosim si titujt ashtu edhe të dhënat në një faqe, por titujt (me madhësi konstante) vijnë nga fillimi i faqes, dhe të dhënat (me gjatësi të ndryshueshme) vijnë nga fundi. Sapo të "takohen" (nuk ka hapësirë të mjaftueshme të lirë për një hyrje të re), ne e konsiderojmë këtë faqe të përfunduar.

Opsioni 3:

Nuk ka nevojë të ruani gjatësinë ose informacione të tjera në lidhje me vendndodhjen e të dhënave në kokë; shënuesit që tregojnë kufijtë e të dhënave janë të mjaftueshëm. Megjithatë, të dhënat duhet të përpunohen gjatë shkrimit/leximit.
Unë do të përdorja 0xff si një shënues (i cili mbush faqen pas fshirjes), kështu që zona e lirë nuk do të trajtohet patjetër si të dhëna.

Tabela krahasuese:

Opsioni 1
Opsioni 2
Opsioni 3

Toleranca ndaj gabimeve
-
+
+

densitet
+
-
+

Kompleksiteti i zbatimit
*
**
**

Opsioni 1 ka një të metë fatale: nëse ndonjë nga kokat është dëmtuar, i gjithë zinxhiri i mëvonshëm shkatërrohet. Opsionet e mbetura ju lejojnë të rikuperoni disa të dhëna edhe në rast dëmtimi masiv.
Por këtu është e përshtatshme të kujtojmë se ne vendosëm t'i ruajmë të dhënat në një formë të ngjeshur, dhe kështu humbasim të gjitha të dhënat në faqe pas një rekordi "të thyer", kështu që edhe pse ka një minus në tabelë, ne nuk e bëjmë ta marrë parasysh.

Kompaktësia:

në opsionin e parë, duhet të ruajmë vetëm 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 dhe gjatësinë fillestare; rekordi duhet të jetë një madhësi konstante, unë vlerësoj 4 bajt për regjistrim (dy bajtë për kompensimin dhe dy bajtë për gjatësinë);
opsioni i tretë ka nevojë vetëm për një karakter për të treguar fillimin e regjistrimit, plus vetë regjistrimi do të rritet me 1-2% për shkak të mbrojtjes. Në përgjithësi, përafërsisht barazi me opsionin e parë.

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

Ndoshta një ditë do të përdor akoma një opsion të ngjashëm. Për shembull, nëse më duhet të merrem me ruajtjen e të dhënave për një anije që udhëton midis Tokës dhe Marsit, do të ketë kërkesa krejtësisht të ndryshme për besueshmërinë, rrezatimin kozmik, ...

Sa për opsionin e tretë: i dhashë dy yje për vështirësinë e zbatimit thjesht sepse nuk më pëlqen të ngatërroj me mbrojtjen, të ndryshoj gjatësinë në proces, etj. Po, ndoshta jam i njëanshëm, por do të më duhet të shkruaj kodin - pse ta detyroni veten të bëni diçka që nuk ju pëlqen.

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

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

Nuk e mbaj mend tani se ku 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ë herët, pas fshirjes të gjitha bitet mbushen me 1, dhe ne mund të 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ë rekordi me gjatësi të ndryshueshme në blic:

Vendosni flamurin "regjistrimi i gjatësisë ka filluar";
Regjistroni gjatësinë;
Vendosni flamurin "Regjistrimi i të dhënave ka filluar";
Ne regjistrojmë të dhëna;
Vendosni flamurin "regjistrimi përfundoi".

Përveç kësaj, do të kemi një flamur "ka ndodhur gabim", për një total prej 4 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, ne 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 (ose edhe kryesore) për dështimet e mundshme.

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

Tavolina kontrolli

Shumat e kontrollit gjithashtu bëjnë të mundur që të sigurohemi (me probabilitet të arsyeshëm) që po lexojmë saktësisht atë që duhet të ishte shkruar. Dhe, ndryshe nga fushat e bitave të diskutuara më sipër, ato gjithmonë funksionojnë.

Nëse marrim parasysh listën e burimeve të mundshme të problemeve që diskutuam më lart, atëherë shuma e kontrollit është në gjendje të njohë një gabim pavarësisht nga origjina e tij (përveç, ndoshta, për të huajt me qëllim të keq - ata gjithashtu mund të 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 për llogaritjen e shumës së kontrollit nuk ngriti asnjë pyetje - CRC. Nga njëra anë, vetitë matematikore bëjnë të mundur kapjen 100% të llojeve të caktuara të gabimeve; nga ana tjetër, në të dhëna të rastësishme ky algoritëm zakonisht tregon probabilitetin e përplasjeve jo shumë më të madhe se kufiri teorik. . Mund të mos jetë algoritmi më i shpejtë, as nuk është gjithmonë minimumi për sa i përket numrit të përplasjeve, por ka një cilësi shumë të rëndësishme: në testet që kam hasur, nuk ka pasur modele në të cilat dështoi qartë. Stabiliteti është cilësia kryesore në këtë rast.

Shembull i një studimi vëllimor: Pjesa 1, Pjesa 2 (lidhje me narod.ru, më fal).

Sidoqoftë, detyra për të zgjedhur një shumë kontrolli nuk është e plotë; CRC është një familje e tërë kontrollesh. Duhet të vendosni për gjatësinë dhe më pas të zgjidhni një polinom.

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

Më lejoni të ilustroj:
Le të kemi probabilitetin e një gabimi në çdo bajt dhe një kontroll ideal, le të llogarisim numrin mesatar të gabimeve për milion regjistrime:

Të dhënat, bajt
Shuma kontrolluese, bajt
Gabime të pazbuluara
Zbulimet e gabuara të rreme
Pozitive totale false

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 se gjithçka është e thjeshtë - në varësi të gjatësisë së të dhënave që mbrohen, zgjidhni gjatësinë e shumës së kontrollit me një minimum pozitiv të pasaktë - dhe mashtrimi është në çantë.

Megjithatë, lind një problem me shumat e shkurtra të kontrollit: megjithëse janë të mirë në zbulimin e gabimeve të një biti, ata me një probabilitet mjaft të lartë mund të pranojnë të dhëna krejtësisht të rastësishme si të sakta. Kishte tashmë një artikull në Habré që përshkruante problem në jetën reale.

Prandaj, për ta bërë pothuajse të pamundur një përputhje të rastësishme të kontrollit, duhet të përdorni shuma kontrolli që janë 32 bit ose më të gjatë. (për gjatësi më të mëdha se 64 bit, zakonisht përdoren funksionet hash kriptografike).

Përkundër faktit që kam shkruar më herët se duhet të kursejmë hapësirë me çdo kusht, ne do të përdorim përsëri një shumë kontrolli 32-bit (16 bit nuk janë të mjaftueshëm, probabiliteti i një përplasjeje është më shumë se 0.01%; dhe 24 bit, pasi ato thuaj, nuk janë as këtu as atje).

Këtu mund të lindë një kundërshtim: a e kemi ruajtur çdo bajt kur zgjedhim kompresimin në mënyrë që tani të japim 4 bajt menjëherë? A nuk do të ishte më mirë të mos ngjeshni ose shtoni një shumë kontrolli? Sigurisht që jo, pa kompresim nuk do te thote, se nuk kemi nevojë për kontroll të integritetit.

Kur zgjedhim një polinom, ne nuk do të rishpikim timonin, por do të marrim CRC-32C tani të njohura.
Ky kod zbulon gabime 6 bit në pako deri në 22 bajt (ndoshta rasti më i zakonshëm për ne), gabime 4 bit në pako deri në 655 bajt (gjithashtu një rast i zakonshëm për ne), 2 ose çdo numër tek gabimet e biteve në paketa me çdo gjatësi të arsyeshme.

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

Artikull Wikipedia rreth CRC.

Parametrat e kodit CRC-32c mbi Faqja e internetit Koopman — ndoshta specialisti kryesor i CRC në planet.

В artikullin e tij ka një kod tjetër interesant, i cili ofron parametra pak më të mirë për gjatësinë e paketave që janë të rëndësishme për ne, por unë nuk e konsiderova ndryshimin domethënës dhe isha mjaftueshëm kompetent për të zgjedhur kodin personal në vend të atij standardi dhe të hulumtuar mirë.

Gjithashtu, duke qenë se të dhënat tona janë të ngjeshura, lind pyetja: a duhet të llogarisim kontrollin e 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, ne duhet të kontrollojmë sigurinë e ruajtjes së të dhënave - kështu që ne i 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 prishur, etj.);
Algoritmi i deflate në zlib ka një zbatim mjaft të pjekur dhe nuk duhet bie me të dhëna hyrëse "të shtrembër"; 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 për të mos zbuluar një gabim (kryhet 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ë "përshtatur" posaçërisht për disa gabime bit që janë karakteristikë për memorien flash (një gabim bit në një rrymë të ngjeshur mund të shkaktojë një ndryshim masiv në rrjedhën e daljes, mbi të cilën, thjesht teorikisht, mund të "kapim" një përplasje);
Nuk më pëlqen shumë ideja e kalimit të të dhënave potencialisht të prishura në dekompresor, Kush e disi do të reagojë.

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

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

Teprica

Përdorimi i kodimit të tepërt, natyrisht, nuk eliminon humbjen e të dhënave, megjithatë, ai mund të zvogëlojë ndjeshëm (shpesh me shumë shkallë) gjasat 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 Hamming mund të korrigjojnë gabimet e një biti, kodet e karaktereve Reed-Solomon, kopjet e shumta të të dhënave të kombinuara me shumat e kontrollit ose kodimet si RAID-6 mund të ndihmojnë në rikuperimin e të dhënave edhe në rast të korrupsionit masiv.
Fillimisht, isha i përkushtuar ndaj përdorimit të gjerë të kodimit rezistent ndaj gabimeve, por më pas kuptova se fillimisht duhet të kemi një ide se nga cilat gabime duam të mbrohemi dhe më pas të zgjedhim kodimin.

Ne thamë më herët se gabimet duhet të kapen sa më shpejt që të jetë e mundur. Në cilat pika mund të hasim gabime?

Regjistrimi i papërfunduar (për disa arsye në kohën e regjistrimit, rryma ishte fikur, Raspberry ngriu, ...)
Mjerisht, në rast të një gabimi të tillë, gjithçka që mbetet është të injorohen të dhënat e pavlefshme dhe të konsiderohen të dhënat e humbura;
Shkrimi i gabimeve (për disa arsye, ajo që u shkrua në memorie flash nuk ishte ajo që ishte shkruar)
Ne mund të zbulojmë menjëherë gabime të tilla nëse bëjmë një test të lexuar menjëherë pas regjistrimit;
Deformimi i të dhënave në memorie gjatë ruajtjes;
Gabimet e leximit
Për ta korrigjuar atë, nëse shuma e kontrollit nuk përputhet, mjafton të përsërisni leximin disa herë.

Kjo do të thotë, vetëm gabimet e llojit të tretë (prishja spontane e të dhënave gjatë ruajtjes) nuk mund të korrigjohen pa kodim rezistent ndaj 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 gabimin e këtij vendimi, atëherë kthehuni në shqyrtimin e çështjes (me statistika të grumbulluara tashmë për dështimet, gjë që do të lejojë zgjedhjen e llojit optimal të kodimit).

Tjetër

Sigurisht, formati i artikullit nuk na lejon të justifikojmë çdo grimë në format (dhe forca ime tashmë ka mbaruar), kështu që unë do të kaloj shkurtimisht disa pika që nuk janë prekur më parë.

U vendos që të gjitha faqet të bëhen "të barabarta"
Kjo do të thotë, nuk do të ketë faqe të veçanta me metadata, tema të veçanta, etj., por në vend të kësaj, një fije e vetme që rishkruan të gjitha faqet me radhë.
Kjo siguron konsumim të barabartë në faqe, asnjë pikë të vetme dështimi, dhe thjesht më pëlqen;
Është e domosdoshme 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 të caktuar magjik (nënshkrim) në kokën e faqes, e cila do të tregojë versionin e formatit të përdorur (Unë nuk mendoj se në praktikë do të ketë as një duzinë prej tyre);
Përdorni një kokë me gjatësi të ndryshueshme për regjistrime (nga të cilat ka shumë), duke u përpjekur ta bëni atë 1 bajt në shumicën e rasteve;
Për të koduar gjatësinë e kokës dhe gjatësinë e pjesës së prerë të rekordit të ngjeshur, përdorni kode binare me gjatësi të ndryshueshme.

Ndihmoi shumë gjenerator në internet Kodet Huffman. Në vetëm pak minuta ne ishim në gjendje të zgjidhnim kodet e kërkuara me gjatësi të ndryshueshme.

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

Renditja e bajtit

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.

Faqezim

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, fitohen 128 faqe).

Çdo faqe ruan të dhëna në mënyrë të pavarur nga të tjerat (d.m.th., të dhënat në një faqe nuk referojnë të dhënat në një faqe tjetër).

Të gjitha faqet numërohen sipas rendit natyror (në rendin rritës të adresave), duke filluar me numrin 0 (faqja zero fillon në adresën 0, faqja e parë fillon me 32 Kb, faqja e dytë fillon me 64 Kb, etj.)

Çipi i memories përdoret si një bufer ciklik (ring buffer), domethënë fillimisht shkrimi shkon në faqen numër 0, pastaj numri 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, më pas një numër kontrolli i titullit (CRC-32C), më pas të dhënat ruhen në formatin "header, data, checksum".

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

Fusha e Numrit Magjik me dy bajtë (gjithashtu një shenjë e versionit të formatit)
për versionin aktual të formatit llogaritet si 0xed00 ⊕ номер страницы;
numëruesi me dy bajtë "Versioni i faqes" (numri i ciklit të rishkrimit të memories).

Regjistrimet në faqe ruhen në formë të ngjeshur (përdoret algoritmi i deflate). Të gjitha regjistrimet në një faqe janë të ngjeshura në një fill (përdoret një fjalor i zakonshëm) dhe në çdo faqe të re kompresimi fillon përsëri. Kjo do të thotë, për të dekompozuar çdo rekord, kërkohen të gjitha regjistrimet e mëparshme nga kjo faqe (dhe vetëm kjo).

Çdo rekord do të kompresohet me flamurin Z_SYNC_FLUSH, dhe në fund të rrjedhës së ngjeshur do të ketë 4 bajt 0x00, 0x00, 0xff, 0xff, mundësisht 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ë memorie flash.

Titulli i regjistrimit është 1, 2 ose 3 bajt që ruan:

një bit (T) që tregon llojin e regjistrimit: 0 - kontekst, 1 - log;
një fushë me gjatësi të ndryshueshme (S) nga 1 deri në 7 bit, që përcakton gjatësinë e kokës dhe "bishtin" që duhet të shtohet në rekordin për dekompresim;
gjatësia e rekordit (L).

Tabela e vlerave S:

S
Gjatësia e kokës, bajt
Hedhur në shkrim, 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 të ilustroj, nuk e di sa qartë doli:

E verdha këtu tregon fushën T, e bardha fushën S, e gjelbër L (gjatësia e të dhënave të ngjeshur në bajt), bluja të dhënat e ngjeshura, e kuqja bajtët përfundimtarë të të dhënave të kompresuara që nuk janë shkruar në memorien flash.

Kështu, ne mund të shkruajmë titujt e rekordeve me gjatësinë më të zakonshme (deri në 63+5 bajt në formë të ngjeshur) në një bajt.

Pas çdo regjistrimi, ruhet një kontroll CRC-32C, në të cilën vlera e përmbysur e shumës së kontrollit të mëparshëm përdoret si vlerë fillestare (init).

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

Duke ndjekur drejtpërdrejt shumën e kontrollit është titulli i rekordit tjetër.

Koka është projektuar në atë mënyrë që bajt i parë i tij është gjithmonë i ndryshëm nga 0x00 dhe 0xff (nëse në vend të bajtit të parë të kokës hasim 0xff, atëherë kjo do të thotë se kjo është një zonë e papërdorur; 0x00 sinjalizon një gabim).

Shembuj të algoritmeve

Leximi nga Flash Memoria

Çdo lexim vjen me një kontroll kontrolli.
Nëse shuma e kontrollit nuk përputhet, leximi përsëritet disa herë me shpresën për të lexuar të dhënat e sakta.

(kjo ka kuptim, Linux nuk ruan leximet në cache nga NOR Flash, i testuar)

Shkruani në memorie flash

Ne regjistrojmë të dhënat.
Le t'i lexojmë ato.

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 funksionim

Për inicializimin, një kokë me versionin 1 shkruhet në faqen e parë (ose më mirë zero).
Pas kësaj, konteksti fillestar shkruhet në këtë faqe (përmban UUID-në e makinës dhe cilësimet e paracaktuara).

Kjo është e gjitha, memoria flash është gati për përdorim.

Ngarkimi i makinës

Gjatë ngarkimit, lexohen 8 bajtët e parë të secilës faqe (header + CRC), faqet me një numër magjik të panjohur ose një CRC të pasaktë shpërfillen.
Nga faqet “korrekte” zgjidhen faqet me versionin maksimal dhe prej tyre merret faqja me numrin më të madh.
Lexohet rekordi i parë, kontrollohet korrektësia e CRC dhe prania e flamurit "kontekst". Nëse gjithçka është në rregull, kjo faqe konsiderohet aktuale. Nëse jo, ne kthehemi te ajo e mëparshme derisa të gjejmë një faqe "live".
dhe në faqen e gjetur lexojmë të gjitha regjistrimet, ato që përdorim me flamurin “kontekst”.
Ruani fjalorin zlib (do të nevojitet për ta shtuar në këtë faqe).

Kjo është e gjitha, shkarkimi ka përfunduar, konteksti është rikthyer, ju mund të punoni.

Shtimi i një hyrjeje në ditar

Ne e kompresojmë rekordin me fjalorin e duhur, duke specifikuar Z_SYNC_FLUSH. Ne shohim nëse rekordi i ngjeshur përshtatet në faqen aktuale.
Nëse nuk përshtatet (ose ka pasur gabime CRC në faqe), hapni një faqe të re (shih më poshtë).
Ne shkruajmë rekordin dhe CRC. Nëse ndodh një gabim, hapni një faqe të re.

Faqe e re

Ne zgjedhim një faqe falas me numrin minimal (ne e konsiderojmë një faqe falas si një faqe me një kontroll të pasaktë në kokë ose me një version më të vogël se ai aktual). Nëse nuk ka faqe të tilla, zgjidhni faqen me numrin minimal nga ato që kanë një version të barabartë me atë aktual.
Ne fshijmë faqen e zgjedhur. Ne kontrollojmë përmbajtjen me 0xff. Nëse diçka nuk është në rregull, merrni faqen tjetër falas, etj.
Ne shkruajmë një kokë në faqen e fshirë, hyrja e parë është gjendja aktuale e kontekstit, tjetra është hyrja e regjistrit të pashkruar (nëse ka një të tillë).

Zbatueshmëria e formatit

Sipas mendimit tim, doli të ishte një format i mirë për ruajtjen e çdo rryme informacioni pak a shumë të kompresueshëm (tekst i thjeshtë, JSON, MessagePack, CBOR, ndoshta protobuf) në NOR Flash.

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

Nuk duhet të përdoret me media të larta BER si NAND ose MLC NOR (a disponohet edhe për shitje një memorie e tillë? E kam parë të përmendet vetëm në punimet për kodet e korrigjimit).

Për më tepër, nuk duhet të përdoret me pajisje që kanë FTL-në e tyre: USB flash, SD, MicroSD, etj. (për një memorie të tillë krijova një format me një madhësi faqeje 512 bajt, një nënshkrim në fillim të secilës faqe dhe numra unik rekord - ndonjëherë ishte e mundur të rikuperoheshin të gjitha të dhënat nga një flash drive "me gabime" me lexim të thjeshtë vijues).

Në varësi të detyrave, formati mund të përdoret pa ndryshime në disqet flash nga 128Kbit (16Kb) në 1Gbit (128MB). Nëse dëshironi, mund ta përdorni në çipa më të mëdhenj, por ndoshta duhet të rregulloni madhësinë e faqes (Por këtu lind tashmë çështja e fizibilitetit ekonomik; çmimi për NOR Flash me vëllim të madh nuk është inkurajues).

Nëse dikujt i duket interesant formati dhe dëshiron ta përdorë atë në një projekt të hapur, shkruaj, unë do të përpiqem të gjej kohën, të lëmoj kodin dhe ta postoj në github.

Përfundim

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

Është e vështirë të pasqyrosh evolucionin e këndvështrimit tim në një artikull, por më besoni: fillimisht doja të krijoja diçka të sofistikuar, të pathyeshme, të aftë për t'i mbijetuar edhe një shpërthimi bërthamor në afërsi. Megjithatë, arsyeja (shpresoj) ende fitoi dhe gradualisht prioritetet u zhvendosën drejt thjeshtësisë dhe kompaktësisë.

A mund të jetë se kam gabuar? Po sigurisht. Mund të rezultojë, për shembull, se kemi blerë një grumbull mikroqarqesh me cilësi të ulët. Ose për ndonjë arsye tjetër pajisja nuk do të përmbushë pritjet e besueshmërisë.

A kam një plan për këtë? Unë mendoj se pasi të keni lexuar artikullin nuk keni dyshim se ka një plan. Dhe as vetëm.

Në një shënim pak më serioz, formati u zhvillua edhe si një opsion pune dhe si një "tullumbace prove".

Për momentin gjithçka në tryezë po funksionon mirë, fjalë për fjalë një ditë tjetër zgjidhja do të vendoset (afërsisht) në qindra pajisje, le të shohim se çfarë ndodh në operacionin "luftarak" (për fat të mirë, shpresoj që formati t'ju lejojë të zbuloni me besueshmëri dështimet; në mënyrë që të mblidhni statistika të plota). Pas disa muajsh do të jetë e mundur të nxirren përfundime (dhe nëse je i pafat, edhe më herët).

Nëse, bazuar në rezultatet e përdorimit, zbulohen probleme serioze dhe kërkohen përmirësime, atëherë unë patjetër do të shkruaj për të.

Letërsi

Nuk doja të bëja një listë të gjatë të lodhshme të veprave të përdorura; në fund të fundit, të gjithë kanë Google.

Këtu vendosa të lë një listë të gjetjeve që më dukeshin veçanërisht interesante, por gradualisht ato migruan drejtpërdrejt në tekstin e artikullit dhe një artikull mbeti në listë:

Shërbim infgen nga autori zlib. Mund të shfaqë qartë përmbajtjen e arkivave deflate/zlib/gzip. Nëse duhet të merreni me strukturën e brendshme të formatit deflate (ose gzip), ju rekomandoj shumë.

Burimi: www.habr.com

Implementimi im i një buffer unazor në NOR flash