historiaurrea

Gure diseinu propioko vending makinak daude. Raspberry Pi-ren barruan eta kableatu batzuk plaka bereizi batean. Txanpon-hartzaile bat, billete-hartzaile bat, banku-terminal bat konektatuta daude... Guztia norberak idatzitako programa batek kontrolatzen du. Lan-historia osoa pendrive bateko erregistro batean idazten da (MicroSD), eta gero Internet bidez (USB modem bat erabiliz) zerbitzarira igortzen da, non datu-base batean gordetzeko. Salmenten informazioa 1c-n kargatzen da, monitorizaziorako web interfaze sinple bat ere badago, etab.

Hau da, aldizkaria ezinbestekoa da - kontabilitatea (sarrerak, salmentak, etab.), jarraipena (mota guztietako hutsegiteak eta ezinbesteko kasuak); Hau da, esan liteke, makina honi buruz daukagun informazio guztia.

arazoa

Flash unitateak oso fidagarriak diren gailuak direla erakusten dute. Erregulartasun inbidiagarriz huts egiten dute. Horrek makinaren geldialdia eta (arrazoiren batengatik erregistroa sarean transferitu ezin bada) datuak galtzea dakar.

Hau ez da flash drive-ak erabiltzeko lehen esperientzia, honen aurretik beste proiektu bat zegoen ehun gailu baino gehiagorekin, non aldizkaria USB flash driveetan gordetzen zen, fidagarritasunarekin ere arazoak zeuden, batzuetan huts egin zutenen kopurua. hilabete bat dozenaka izan zen. Flash unitate desberdinak probatu genituen, SLC memoria duten markakoak barne, eta modelo batzuk beste batzuk baino fidagarriagoak dira, baina flash unitateak ordezkatzeak ez zuen arazoa erabat konpondu.

Arreta! Luze irakurri! "Zergatik" interesatzen ez bazaizu, "nola" baizik ez baduzu, zuzen joan zaitezke Azkenean artikuluak.

Erabaki

Burura datorkigun lehenengo gauza hau da: MicroSD abandonatu, instalatu, adibidez, SSD bat eta bertatik abiarazi. Teorikoki posible, ziurrenik, baina nahiko garestia, eta ez hain fidagarria (USB-SATA egokitzaile bat gehitzen da; aurrekontu SSDen hutsegiteen estatistikak ere ez dira pozgarriak).

USB HDD-ak ere ez du irtenbide bereziki erakargarria denik.

Hori dela eta, aukera honetara iritsi ginen: utzi MicroSD-tik abiarazteari, baina erabili irakurtzeko moduan, eta gorde eragiketa-erregistroa (eta hardware-pieza jakin baterako bestelako informazioa - serie-zenbakia, sentsoreen kalibrazioak, etab.) beste nonbait. .

Mugurdientzako irakurtzeko soilik FS gaia barrutik eta kanpotik aztertu da dagoeneko, ez naiz artikulu honetan inplementazioaren xehetasunetan luzatuko (baina interesa badago, agian gai honi buruzko artikulu txiki bat idatziko dut). Kontuan izan nahi dudan puntu bakarra zera da, bai esperientzia pertsonaletik eta baita dagoeneko ezarri dutenen berrikuspenetatik ere, fidagarritasunean irabazten dela. Bai, ezinezkoa da matxurak guztiz kentzea, baina haien maiztasuna nabarmen murriztea posible da. Eta txartelak bateratzen ari dira, eta horrek askoz errazten du ordezkatzea zerbitzuetako langileentzat.

hardware zatia

Ez zegoen inolako zalantzarik memoria motaren aukerak - NOR Flash.
Argudioak:

• konexio sinplea (gehienetan SPI busa, dagoeneko erabiltzen duzun esperientzia, beraz ez da hardware arazorik aurreikusten);
• prezio barregarria;
• operazio-protokolo estandarra (inplementazioa Linux nukleoan dago jada, nahi baduzu, hirugarrenen bat har dezakezu, hori ere presente dagoena, edo baita zurea idatzi, zorionez dena erraza da);
• fidagarritasuna eta baliabidea:
  datu-orri tipiko batetik: datuak 20 urtez gordetzen dira, 100000 ezabatze-ziklo bloke bakoitzeko;
  Hirugarrenen iturrietatik: BER oso baxua, akatsak zuzentzeko kodeen beharrik ez duela postulatzen (lan batzuek ECC NORrentzat hartzen dute kontuan, baina normalean oraindik MLC NOR esan nahi dute; hau ere gertatzen da).

Estima ditzagun bolumenaren eta baliabidearen baldintzak.

Datuak hainbat egunetan gordetzea bermatuta egotea nahiko nuke. Hau beharrezkoa da komunikazioarekin arazorik izanez gero, salmenta-historia gal ez dadin. 5 egunetan zentratuko gara, tarte horretan (nahiz eta asteburuak eta jaiegunak kontuan hartuta) arazoa konpondu daiteke.

Gaur egun 100 kb-ko erregistro inguru biltzen ditugu egunean (3-4 mila sarrera), baina pixkanaka zifra hau hazten ari da - xehetasunak handitzen ari dira, gertaera berriak gehitzen ari dira. Gainera, batzuetan leherketak egoten dira (sentsore batzuk positibo faltsuekin spammatzen hasten dira, adibidez). 10 mila erregistro bakoitzeko 100 byte kalkulatuko ditugu - megabyte eguneko.

Guztira, 5 MB datu garbi (ondo konprimituta) ateratzen dira. Haiei gehiago (kalkulu gutxi gorabehera) 1 MB zerbitzuko datuak.

Hau da, 8MB-ko txipa behar dugu konpresioa erabiltzen ez badugu, edo 4MB-koa erabiltzen badugu. Zenbaki nahiko errealistak memoria mota honetarako.

Baliabideari dagokionez: memoria osoa 5 egunetik behin baino gehiagotan berridatziko dela aurreikusten badugu, 10 urteko zerbitzuan mila berridazketa-ziklo baino gutxiago izango ditugu.
Gogorarazten dizut fabrikatzaileak ehun mila agintzen dituela.

NOR vs NAND buruz pixka bat

Gaur egun, jakina, NAND memoria askoz ezagunagoa da, baina ez nuke proiektu honetarako erabiliko: NANDek, NOR ez bezala, nahitaez eskatzen du erroreak zuzentzeko kodeak, bloke txarren taula, etab., eta baita hankak ere. NAND txipak normalean askoz gehiago.

NORren desabantailak honako hauek dira:

• bolumen txikia (eta, horren arabera, megabyte bakoitzeko prezio altua);
• komunikazio-abiadura baxua (neurri handi batean serieko interfaze bat erabiltzen delako, normalean SPI edo I2C);
• motela ezabatzea (blokearen tamainaren arabera, segundo baten zatitik segundo batzuetara igarotzen da).

Badirudi ez dagoela ezer kritiko guretzat, beraz, jarraitzen dugu.

Xehetasunak interesgarriak badira, mikrozirkuitua hautatu da at25df321a (hala ere, horrek ez du garrantzirik, analogo asko daude merkatuan pinout eta komando sisteman bateragarriak direnak; nahiz eta fabrikatzaile edo/eta beste tamaina bateko mikrozirkuitu bat instalatu nahi badugu, dena funtzionatuko du aldatu gabe. kodea).

Linux nukleoan integratutako kontrolatzailea erabiltzen dut; Raspberry-n, gailuen zuhaitzaren gainjartze-laguntzari esker, dena oso erraza da - konpilatutako gainjartzea /boot/overlays-en jarri eta /boot/config.txt apur bat aldatu behar duzu.

Adibidea dts fitxategia

Egia esateko, ez nago ziur akatsik gabe idatzi denik, baina funtzionatzen du.

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

Eta beste lerro bat config.txt-en

dtoverlay=at25:spimaxfrequency=50000000

Txipa Raspberry Pi-ra konektatzearen deskribapena baztertuko dut. Batetik, ez naiz elektronikan aditua, bestetik, hemen dena hutsala da niretzat ere: mikrozirkuituak 8 hanka baino ez ditu, eta horietatik lurra, potentzia, SPI (CS, SI, SO, SCK) behar ditugu. ); mailak Raspberry Pi-ren berdinak dira, ez da kableatu gehigarririk behar - konektatu besterik ez dago adierazitako 6 pinak.

Arazoaren formulazioa

Ohi bezala, arazoaren adierazpenak hainbat iterazioz pasatzen ditu, eta hurrengorako garaia dela iruditzen zait. Geldi gaitezen, beraz, idatzitakoa bildu eta itzalean geratzen diren xehetasunak argitu.

Beraz, erregistroa SPI NOR Flash-en gordeko dela erabaki dugu.

Zer da NOR Flash ezagutzen ez dutenentzat?

Memoria ez-hegazkorra da eta honekin hiru eragiketa egin ditzakezu:

1. Irakurketa:
   Irakurketa ohikoena: helbidea transmititzen dugu eta behar adina byte irakurtzen ditugu;
2. erregistroa:
   NOR flash-era idazteak ohikoa dirudi, baina badu berezitasun bat: 1etik 0ra bakarrik alda dezakezu, baina ez alderantziz. Adibidez, memoria gelaxka batean 0x55 bagenuen, orduan 0x0f idatzi ondoren, 0x05 dagoeneko gordeko da bertan (ikus beheko taula);
3. Ezabatu:
   Noski, kontrako eragiketa egiteko gai izan behar dugu - aldatu 0-tik 1era, horixe da zehazki ezabatzeko eragiketa. Lehenengo biek ez bezala, ez da byteekin funtzionatzen, blokeekin baizik (hautatutako txiparen gutxieneko ezabatze-blokea 4kb-koa da). Ezabatzeak bloke osoa suntsitzen du eta 0tik 1era aldatzeko modu bakarra da. Hori dela eta, flash memoriarekin lan egiten duzunean, askotan datu-egiturak ezabatzeko blokeen mugarekin lerrokatu behar dituzu.
   NOR Flash-en grabatzea:

Datu bitarrak

zen
01010101

Grabatua
00001111

Bihurtu da
00000101

Erregistroak berak luzera aldakorreko erregistroen sekuentzia bat adierazten du. Erregistro baten ohiko luzera 30 byte ingurukoa da (nahiz eta zenbait kilobyte-ko luzera duten erregistroak gertatzen diren batzuetan). Kasu honetan, byte multzo gisa lan egiten dugu haiekin, baina, interesatzen bazaizu, CBOR erabiltzen da erregistroen barruan.

Erregistroaz gain, "konfigurazio" informazio batzuk gorde behar ditugu, eguneratuak eta ez: gailuaren ID jakin bat, sentsoreen kalibrazioak, "gailu aldi baterako desgaituta dago" bandera, etab.
Informazio hau gako-balio-erregistroen multzoa da, CBOR-en ere gordeta. Ez dugu informazio hori askorik (gehienez kilobyte batzuk), eta gutxitan eguneratzen da.
Jarraian testuingurua deituko diogu.

Artikulu hau non hasi zen gogoratzen badugu, oso garrantzitsua da datuen biltegiratze fidagarria eta, ahal bada, etengabeko funtzionamendua ziurtatzea, nahiz eta hardware-akatsak/datuak hondatuta egon.

Zein arazo-iturri har daitezke?

• Itzali idazketa/ezabaketa eragiketetan. Hau "ez dago trikimailurik palanka" kategoriakoa da.
  Informazioa eztabaidak stackexchange-n: flash-arekin lan egiten duzun bitartean itzalita dagoenean, bai ezabatzeak (1-an ezarrita) bai idazteak (0-n ezarrita) jokaera zehaztugabea dakar: datuak idatzi daitezke, partzialki idatzi (esan, 10 byte/80 bit transferitu ditugu). , baina oraindik 45 bit bakarrik idatz daitezke), baliteke bit batzuk “tarteko” egoeran egotea ere (irakurtzeak 0 eta 1 sor ditzake);
• Akatsak flash memorian bertan.
  BER, oso baxua izan arren, ezin da zeroren berdina izan;
• Autobusen akatsak
  SPI bidez transmititzen diren datuak ez daude inola ere babestuta; bit bakarreko erroreak zein sinkronizazio akatsak gerta daitezke - bitak galtzea edo sartzea (datuen distortsio masiboa eragiten duena);
• Beste akats / akats batzuk
  Kodean akatsak, Raspberry akatsak, estralurtar interferentziak...

Baldintzak formulatu ditut, eta horien betetzea, nire ustez, beharrezkoa da fidagarritasuna bermatzeko:

• erregistroak berehala sartu behar dira flash memoriara, atzeratutako idazketak ez dira kontuan hartzen; - akatsen bat gertatzen bada, ahalik eta azkarren detektatu eta prozesatu behar da; - sistemak, ahal bada, akatsetatik berreskuratu behar du.
  (bizitzako adibide bat “nola izan behar ez”, denek topatu dutela uste dut: larrialdiko berrabiarazi ondoren, fitxategi sistema “hautsi” dago eta sistema eragilea ez da abiarazten)

Ideiak, planteamenduak, hausnarketak

Arazo honi buruz pentsatzen hasi nintzenean, ideia asko burutik pasa zitzaizkidan, adibidez:

• erabili datuen konpresioa;
• erabili datu-egitura burutsuak, adibidez, erregistroen goiburuak erregistroetatik bereizita gordetzea, edozein erregistrotan akatsen bat izanez gero, gainerakoak arazorik gabe irakurtzeko;
• erabili bit-eremuak korrontea itzalita dagoenean grabaketa amaitzea kontrolatzeko;
• dena gordetzeko checksumak;
• erabili zaratari erresistenteak diren kodeketa mota batzuk.

Ideia horietako batzuk erabili ziren, beste batzuk bertan behera uztea erabaki zuten. Goazen ordenan.

Datuen konpresioa

Aldizkarian erregistratzen ditugun gertaerak nahiko antzekoak eta errepikagarriak dira (“5 errublo txanpon bat bota zuen”, “aldaketa emateko botoia sakatu zuen”, ...). Beraz, konpresioak nahiko eraginkorra izan behar du.

Konpresioaren gainkostua hutsala da (gure prozesadorea nahiko indartsua da, lehen Pi-k ere nukleo bat zuen 700 MHz-ko maiztasuna zuena, egungo modeloek gigahertz baino gehiagoko maiztasuna duten hainbat nukleo dituzte), biltegiratze-tasa baxua da (hainbat megabyte segundoko), erregistroen tamaina txikia da. Oro har, konpresioak errendimenduan eragina badu, positiboa baino ez da izango. (erabat akritikoa, esatea besterik ez). Gainera, ez dugu benetako txertatua, Linux arrunta baizik; beraz, inplementazioak ez luke esfortzu handirik beharko (nahikoa da liburutegia lotzea eta bertatik hainbat funtzio erabiltzea).

Erregistroaren zati bat funtzionatzen duen gailu batetik hartu zen (1.7 MB, 70 mila sarrera) eta lehenik konprimagarritasuna egiaztatu zen ordenagailuan eskuragarri dauden gzip, lz4, lzop, bzip2, xz, zstd erabiliz.

• gzip, xz, zstd-ek antzeko emaitzak erakutsi zituen (40Kb).
  Harrituta geratu nintzen modan dagoen xz-a hemen gzip edo zstd mailan agertu izana;
• ezarpen lehenetsiekin lzip-ek emaitza apur bat okerragoak eman zituen;
• lz4 eta lzop-ek ez zuten emaitza oso onak eman (150Kb);
• bzip2-k emaitza harrigarri ona erakutsi zuen (18Kb).

Beraz, datuak oso ondo konprimituta daude.
Beraz (akats hilgarriak aurkitzen ez baditugu) konpresioa egongo da! Besterik gabe, datu gehiago sartu daitezkeelako flash drive berean.

Pentsa ditzagun desabantailak.

Lehenengo arazoa: dagoeneko adostu dugu disko bakoitzak berehala flashera joan behar duela. Normalean, artxibatzaileak sarrerako korrontearen datuak biltzen ditu asteburuan idazteko ordua dela erabaki arte. Datu-bloke konprimitu bat berehala jaso eta memoria ez lurrunkor batean gorde behar dugu.

Hiru modu ikusten ditut:

1. Konprimitu erregistro bakoitza hiztegi-konpresioa erabiliz goian aipaturiko algoritmoen ordez.
   Erabat funtzionatzen duen aukera da, baina ez zait gustatzen. Konpresio-maila gutxi-asko duina ziurtatzeko, hiztegia datu zehatzetara "neurri" egon behar da; edozein aldaketak konpresio-maila katastrofikoki jaitsiko du. Bai, arazoa hiztegiaren bertsio berri bat sortuz konpon daiteke, baina hau buruhaustea da - hiztegiaren bertsio guztiak gorde beharko ditugu; sarrera bakoitzean hiztegiaren zein bertsiorekin konprimitu den adierazi beharko dugu...
2. Konprimitu erregistro bakoitza algoritmo “klasikoak” erabiliz, baina besteekiko independentean.
   Kontuan hartutako konpresio-algoritmoak ez daude diseinatuta tamaina honetako erregistroekin lan egiteko (hamarka byte), konpresio-erlazioa 1 baino txikiagoa izango da (hau da, datu-bolumena handitzea konprimitu beharrean);
3. Egin FLUSH grabaketa bakoitzaren ondoren.
   Konpresio liburutegi askok FLUSH-erako euskarria dute. Hau komando bat da (edo konpresio-prozeduraren parametroa), artxibatzaileak korronte konprimitu bat osatzen duen jasotzean, leheneratu ahal izateko. guztiak dagoeneko jaso diren konprimitu gabeko datuak. Halako analogoa sync fitxategi-sistemetan edo commit sql-en.
   Garrantzitsuena da ondorengo konpresio-eragiketak metatutako hiztegia erabiltzeko gai izango direla eta konpresio-erlazioak ez duela aurreko bertsioan bezainbeste sufrituko.

Hirugarren aukera aukeratu dudala agerikoa dela uste dut, ikus dezagun zehatzago.

Aurkituta artikulu bikaina FLUSH-i buruz zlib-n.

Artikuluan oinarritutako belauneko proba bat egin nuen, 70 mila erregistro-sarrera hartu nituen benetako gailu batetik, 60Kb-ko orrialdearen tamainarekin (geroago itzuliko gara orriaren tamainara) jaso:

Datu gordinak
Konpresioa gzip -9 (EZ FLUSH)
zlib Z_PARTIAL_FLUSH-rekin
zlib Z_SYNC_FLUSH-rekin

Bolumena, KB
1692
40
352
604

Lehen begiratuan, FLUSH-ek ekartzen duen prezioa gehiegizkoa da, baina, egia esan, aukera gutxi dugu - edo batere ez konprimitzeko, edo konprimitzeko (eta oso eraginkortasunez) FLUSH-ekin. Ez dugu ahaztu behar 70 mila erregistro ditugula, Z_PARTIAL_FLUSH-ek sartutako erredundantzia erregistro bakoitzeko 4-5 byte baino ez da. Eta konpresio-erlazioa ia 5:1 izan zen, hau da, emaitza bikaina baino gehiago.

Ezustekoa izan daiteke, baina Z_SYNC_FLUSH benetan FLUSH egiteko modu eraginkorragoa da

Z_SYNC_FLUSH erabiltzean, sarrera bakoitzaren azken 4 byteak 0x00, 0x00, 0xff, 0xff izango dira beti. Eta ezagutzen baditugu, ez ditugu gorde beharrik, beraz, azken tamaina 324Kb baino ez da.

Estekatu dudan artikuluak azalpen bat du:

Eduki hutsak dituen 0 motako bloke berri bat eransten da.

Eduki hutsak dituen 0 motako blokeak honako hauek ditu:

• hiru biteko blokeen goiburua;
• 0 eta 7 bit zeroren berdinak, byteen lerrokatzea lortzeko;
• lau byteko sekuentzia 00 00 FF FF.

Erraz ikusten duzunez, 4 byte hauen aurreko azken blokean 3 eta 10 zero bit daude. Hala ere, praktikak erakutsi du benetan gutxienez 10 zero bit daudela.

Horrelako datu-bloke laburrak normalean (beti?) 1 motako bloke bat erabiliz (bloke finkoa) kodetzen dira, nahitaez 7 zero bitekin amaitzen dena, guztira 10-17 bermatutako zero bit (eta gainerakoak izango dira). zero izan %50 inguruko probabilitatearekin).

Beraz, probako datuetan, kasuen % 100ean zero byte bat dago 0x00, 0x00, 0xff, 0xff aurretik, eta kasuen heren batean baino gehiagotan bi zero byte daude. (agian kontua da CBOR bitarra erabiltzen dudala, eta JSON testua erabiltzean, 2 motako blokeak - bloke dinamikoa ohikoagoak izango lirateke, hurrenez hurren, 0x00, 0x00, 0xff, 0xff baino lehen zero byte gehigarririk gabeko blokeak topatuko lirateke).

Guztira, eskuragarri dauden proba-datuak erabiliz, 250Kb baino gutxiagoko datu konprimituetan sar daiteke.

Apur bat gehiago aurreztu dezakezu malabareak eginez: oraingoz blokearen amaieran zero bit batzuen presentzia baztertzen dugu, blokearen hasieran bit batzuk ere ez dira aldatzen...
Baina gero gelditzeko erabaki sendoa hartu nuen, bestela erritmo honetan nire artxibo propioa garatzen amaituko nuke.

Guztira, nire probako datuetatik 3-4 byte jaso nituen idazketa bakoitzeko, konpresio-erlazioa 6:1 baino gehiagokoa izan zen. Zintzoa izango naiz: ez nuen halako emaitzarik espero; nire ustez, 2:1 baino hobea dena konpresioaren erabilera justifikatzen duen emaitza da dagoeneko.

Dena ondo dago, baina zlib (deflate) konpresio-algoritmo arkaikoa, merezitakoa eta apur bat zaharkitua da oraindik. Konprimitu gabeko datu-korrontearen azken 32Kb hiztegi gisa erabiltzeak gaur egun arraroa dirudi (hau da, datu-blokeren bat duela 40Kb sarrerako korrontean zegoenaren oso antzekoa bada, berriro artxibatzen hasiko da, eta ez du aurreko agerraldi bati erreferentzia egingo). Modako artxibo modernoetan, hiztegiaren tamaina sarritan megabytetan neurtzen da, kilobytetan baino.

Beraz, artxiboen azterketa txikiarekin jarraitzen dugu.

Ondoren, bzip2 probatu genuen (gogoratu, FLUSH gabe ia 100:1eko konpresio-erlazio zoragarria erakusten zuela). Zoritxarrez, FLUSH-ekin oso gaizki aritu zen; konprimitutako datuen tamaina konprimitu gabeko datuena baino handiagoa izan zen.

Porrotaren arrazoiei buruzko nire hipotesiak

Libbz2-k hutsegite aukera bakarra eskaintzen du, badirudi hiztegia garbitzen duela (zlib-en Z_FULL_FLUSH-en antzekoa); ez da konpresio eraginkorrik hitz egiten honen ondoren.

Eta probatu zuten azkena zstd izan zen. Parametroen arabera, gzip mailan konprimitzen du, baina askoz azkarrago, edo gzip baino hobeto.

Ai, FLUSH-ekin ez zuen oso ondo aritu: konprimitutako datuen tamaina 700Kb ingurukoa zen.

Я galdera bat egin zuen proiektuaren github orrian, erantzun bat jaso nuen datu konprimituen bloke bakoitzeko 10 byte zerbitzuko datuekin zenbatu behar zenituzkeela, lortutako emaitzetatik gertu dagoena; ez dago deflazioari aurre egiteko modurik.

Artxiboekin egindako esperimentuetan une honetan gelditzea erabaki nuen (gogora dezazuen xz, lzip, lzo, lz4 ez zirela froga-fasean ere erakutsi FLUSH gabe, eta ez nituen konpresio-algoritmo exotikoagoak kontuan hartu).

Itzuli gaitezen artxibatzeko arazoetara.

Bigarren (ordenan esaten den bezala, ez balioan) arazoa da konprimitutako datuak korronte bakarra direla, eta bertan etengabe aurreko atalen erreferentziak daude. Horrela, konprimitutako datuen atal bat hondatzen bada, konprimitu gabeko datuen bloke elkartua ez ezik, ondorengo guztiak ere galduko ditugu.

Arazo hau konpontzeko planteamendu bat dago:

1. Saihestu arazoa gertatzea - ​​gehitu erredundantzia konprimitutako datuei, eta horrek akatsak identifikatu eta zuzentzeko aukera emango dizu; honetaz gero hitz egingo dugu;
2. Arazoren bat gertatzen bada ondorioak gutxitzea
   Lehenago esan dugu datu-bloke bakoitza modu independentean konprimitu dezakezula eta arazoa berez desagertuko dela (bloke bateko datuen kalteak bloke honetarako soilik datuak galtzea ekarriko du). Hala ere, datuen konpresioa eraginkorra izango den muturreko kasua da. Kontrako muturra: erabili gure txiparen 4MB guztiak artxibo bakar gisa, eta horrek konpresio bikaina emango digu, baina ondorio katastrofikoak datuak hondatuz gero.
   Bai, fidagarritasunari dagokionez konpromisoa behar da. Baina gogoratu behar dugu memoria ez-hegazkorrerako datuak biltegiratzeko formatu bat garatzen ari garela, BER oso baxuarekin eta 20 urteko deklaratutako datuak gordetzeko epearekin.

Esperimentuetan zehar, deskubritu nuen konpresio mailan galera gehiago edo gutxiago nabarmenak hasten direla 10 KB baino gutxiagoko datu konprimituen blokeetan.
Lehen aipatu zen erabiltzen den memoria orria dela; Ez dut ikusten arrazoirik "orrialde bat - datu konprimituen bloke bat" korrespondentzia ez erabiltzeko.

Hau da, arrazoizko gutxieneko orrialdearen tamaina 16Kb-koa da (zerbitzuaren informaziorako erreserba batekin). Hala ere, hain orrialde txikiak muga handiak ezartzen ditu erregistroaren gehienezko tamainan.

Oraindik konprimitutako kilobyte batzuk baino gehiagoko erregistroak espero ez baditut ere, 32Kb-ko orriak erabiltzea erabaki nuen (guztira 128 orrialde txip bakoitzeko).

Laburpena:

• Datuak konprimituta gordetzen ditugu zlib (deflate) erabiliz;
• Sarrera bakoitzeko Z_SYNC_FLUSH ezarri dugu;
• Konprimitutako erregistro bakoitzeko, amaierako byteak mozten ditugu (adibidez, 0x00, 0x00, 0xff, 0xff); goiburuan zenbat byte moztu ditugun adierazten dugu;
• Datuak 32Kb-ko orrialdeetan gordetzen ditugu; orriaren barruan datu konprimituen korronte bakarra dago; Orrialde bakoitzean berriro hasiko gara konpresioa.

Eta, konpresioarekin amaitu aurretik, zure arreta deitu nahi dizut erregistro bakoitzeko datu konprimitu batzuk baino ez ditugula, beraz, oso garrantzitsua da zerbitzuaren informazioa ez puztea, byte bakoitzak hemen balio du.

Datuen goiburuak gordetzea

Luzera aldakorreko erregistroak ditugunez, nolabait erregistroen kokapena/mugak zehaztu behar ditugu.

Hiru ikuspegi ezagutzen ditut:

1. Erregistro guztiak etengabeko korronte batean gordetzen dira, lehenik eta behin, luzera duen erregistro-goiburua dago, eta gero erregistroa bera.
   Gorabide honetan, goiburuak zein datuak luzera aldakorrekoak izan daitezke.
   Funtsean, denbora guztian erabiltzen den zerrenda bana lotua lortzen dugu;
2. Goiburuak eta erregistroak korronte bereizietan gordetzen dira.
   Luzera konstanteko goiburuak erabiliz, goiburu batean kalteak besteei eraginik ez diela ziurtatzen dugu.
   Antzeko ikuspegia erabiltzen da, adibidez, fitxategi-sistema askotan;
3. Erregistroak etengabeko korronte batean gordetzen dira, erregistroaren muga markatzaile jakin batek zehazten du (datu blokeetan debekatuta dagoen karaktere/sekuentzia). Erregistroaren barruan markatzaile bat badago, sekuentzia batekin ordezkatuko dugu (ihes egin).
   Antzeko ikuspegia erabiltzen da, adibidez, PPP protokoloan.

ilustratuko dut.

Aukera 1:

Hemen dena oso erraza da: erregistroaren luzera ezagututa, hurrengo goiburuko helbidea kalkula dezakegu. Beraz, goiburuetan zehar mugitzen gara 0xff (eremu librea) edo orriaren amaierarekin betetako eremu batekin topo egin arte.

Aukera 2:

Erregistroaren luzera aldakorra dela eta, ezin dugu aldez aurretik esan zenbat erregistro (eta, beraz, goiburu) beharko ditugun orrialde bakoitzeko. Goiburuak eta datuak beraiek orri ezberdinetan zabal ditzakezu, baina nik beste ikuspegi bat nahiago dut: goiburuak eta datuak orrialde batean jartzen ditugu, baina goiburuak (tamaina konstantekoak) orrialdearen hasieratik datoz, eta datuak (luzera aldakorrekoak) amaieratik datoz. “Elkartu” bezain laster (ez dago leku libre nahikorik sarrera berri baterako), orri hau osatutzat jotzen dugu.

Aukera 3:

Ez dago goiburuan datuen kokapenari buruzko luzera edo bestelako informaziorik gorde beharrik; nahikoa dira erregistroen mugak adierazten dituzten markatzaileak. Hala ere, datuak idaztean/irakurtzean landu behar dira.
0xff markatzaile gisa erabiliko nuke (orria ezabatu ondoren betetzen duena), beraz, eremu librea ez da datu gisa tratatuko.

Konparazio taula:

Aukera 1
Aukera 2
Aukera 3

Akatsen tolerantzia
-
+
+

dentsitate
+
-
+

Ezarpenaren konplexutasuna
*
**
**

1. aukerak akats larri bat du: goiburuetakoren bat hondatzen bada, ondorengo kate osoa suntsitu egingo da. Gainerako aukerek datu batzuk berreskuratzeko aukera ematen dute, nahiz eta kalte handiak izan.
Baina hemen komeni da gogoratzea datuak inprimaki konprimituan gordetzea erabaki genuela, eta, beraz, orrialdeko datu guztiak galtzen ditugula erregistro "hautsi" baten ondoren, beraz, taulan minus bat egon arren, ez dugu kontuan hartu.

Trinkotasuna:

• lehen aukeran, luzera bakarrik gorde behar dugu goiburuan;luzera aldakorreko zenbaki osoak erabiltzen baditugu, kasu gehienetan byte batekin atera gaitezke;
• bigarren aukeran hasierako helbidea eta luzera gorde behar ditugu; Erregistroak tamaina konstantea izan behar du, 4 byte kalkulatzen ditut erregistro bakoitzeko (bi byte desplazamendurako, eta bi byte luzerako);
• hirugarren aukerak karaktere bakarra behar du grabazioaren hasiera adierazteko, gainera grabazioa bera % 1-2 handituko da blindajearen ondorioz. Oro har, gutxi gorabehera lehen aukerarekin parekotasuna.

Hasieran, bigarren aukera nagusitzat hartu nuen (eta inplementazioa ere idatzi nuen). Konpresioa erabiltzea erabaki nuenean bakarrik abandonatu nuen.

Agian noizbait antzeko aukera bat erabiliko dut. Adibidez, Lurraren eta Marteren artean bidaiatzen duen ontzi baten datuen biltegiratzeari aurre egin behar badiot, fidagarritasunari, erradiazio kosmikoari, ... betekizun guztiz desberdinak izango dira.

Hirugarren aukerari dagokionez: bi izar eman nizkion inplementatzeko zailtasunagatik, ez dudalako gustatzen blindarekin nahastea, prozesuan luzera aldatzea, etab. Bai, agian alboratzailea naiz, baina kodea idatzi beharko dut - zergatik behartu zeure burua gustuko ez duzun zerbait egitera.

Laburpena: Biltegiratze aukera "luzera duen goiburua - luzera aldakorreko datuak" kateen moduan aukeratzen dugu eraginkortasuna eta inplementatzeko erraztasuna dela eta.

Bit eremuak erabiltzea idazketa-eragiketen arrakasta kontrolatzeko

Orain ez dut gogoan nondik atera nuen ideia, baina itxura hau dauka:
Sarrera bakoitzeko, hainbat bit esleitzen ditugu banderak gordetzeko.
Lehen esan dugun bezala, ezabatu ondoren bit guztiak 1ez betetzen dira, eta 1etik 0ra alda dezakegu, baina ez alderantziz. Beraz, "bandera ez dago ezarrita"-rako 1 erabiltzen dugu, "bandera ezarrita dago"-rako 0 erabiltzen dugu.

Hona hemen luzera aldakorreko erregistro bat flashean jartzea nolakoa izan daitekeen:

1. Ezarri "luzera grabatzen hasi da" bandera;
2. Grabatu luzera;
3. Ezarri "datuen grabaketa hasi da" bandera;
4. Datuak erregistratzen ditugu;
5. Ezarri "grabaketa amaituta" bandera.

Horrez gain, "errore gertatu den" bandera izango dugu, guztira 4 biteko banderak.

Kasu honetan, bi egoera egonkor ditugu "1111" - grabaketa ez da hasi eta "1000" - grabaketa arrakastatsua izan da; grabaketa-prozesuaren ustekabeko eten bat gertatuz gero, tarteko egoerak jasoko ditugu, gero detektatu eta prozesatu ahal izateko.

Planteamendua interesgarria da, baina bat-bateko etenaldietatik eta antzeko akatsetatik soilik babesten du, eta hori, noski, garrantzitsua da, baina hau hutsegiteen arrazoi bakarra (edo baita nagusiena) urrun dago.

Laburpena: Goazen aurrera irtenbide on baten bila.

Checksumak

Checksumek ere posible egiten dute ziurtatzeko (arrazoizko probabilitatearekin) idatzi behar zena zehazki irakurtzen ari garela. Eta, goian aipaturiko bit eremuek ez bezala, beti funtzionatzen dute.

Goian eztabaidatu dugun arazo-iturri potentzialen zerrenda kontuan hartzen badugu, checksum-ak akats bat antzeman dezake bere jatorria edozein dela ere. (agian, atzerritar gaiztoentzat izan ezik - checksuma ere faltsu dezakete).

Beraz, gure helburua datuak osorik daudela egiaztatzea bada, checksumak ideia bikaina dira.

Checksuma kalkulatzeko algoritmoa aukeratzeak ez du inolako galderarik sortu - CRC. Alde batetik, propietate matematikoek errore mota batzuk % 100ean harrapatzea ahalbidetzen dute; bestetik, ausazko datuetan algoritmo honek talkak izateko probabilitatea muga teorikoa baino askoz handiagoa ez dela erakusten du. . Agian ez da algoritmorik azkarrena, ezta talka kopuruari dagokionez ere minimoa, baina oso kalitate garrantzitsua du: aurkitu ditudan probetan ez zegoen argi huts egin duen eredurik. Egonkortasuna da kalitate nagusia kasu honetan.

Azterketa bolumetriko baten adibidea: 1 zatia, 2 zatia (narod.ru-rako estekak, barkatu).

Hala ere, checksum bat hautatzeko zeregina ez da amaitu; CRC checksum familia oso bat da. Luzera erabaki behar duzu, eta gero polinomio bat aukeratu.

Checksumaren luzera aukeratzea ez da lehen begiratuan dirudien bezain galdera erraza.

Utzidazu ilustratzen:
Eman dezagun byte bakoitzean errore bat izateko probabilitatea eta checksum ideal bat, kalkula dezagun akatsen batez besteko kopurua milioi erregistro bakoitzeko:

Datuak, byte
Checksum, byte
Antzeman gabeko akatsak
Errore faltsuak hautematea
Guztizko positibo faltsuak

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

Badirudi dena erraza dela - babestutako datuen luzeraren arabera, hautatu checksumaren luzera positibo oker gutxienekin - eta trikimailua poltsan dago.

Dena den, arazo bat sortzen da batuketa laburrekin: bit bakarreko akatsak hautematen onak diren arren, nahiko probabilitate handiarekin guztiz ausazko datuak zuzen gisa onar ditzakete. Habréri buruzko artikulu bat zegoen jada deskribatzen arazoa bizitza errealean.

Hori dela eta, ausazko kontrol batuketa bat ia ezinezkoa izan dadin, 32 bit edo gehiagoko luzera duten kontrol-sumoak erabili behar dituzu. (64 bit baino gehiagoko luzeretarako, hash funtzio kriptografikoak erabiltzen dira normalean).

Lehenago lekua aurreztu behar dugula idatzi dudan arren, 32 biteko checksum bat erabiliko dugu oraindik (16 bit ez dira nahikoa, talka egiteko probabilitatea % 0.01 baino gehiagokoa da; eta 24 bit, hala nola. esan, ez daude ez hemen ez han) .

Eragozpen bat sor daiteke hemen: konpresioa aukeratzerakoan byte guztiak gorde al ditugu orain 4 byte aldi berean emateko? Ez al litzateke hobe batuketa bat ez konprimitzea edo gehitzea? Noski ez, konpresiorik ez ez du esan nahi, ez dugula osotasun egiaztapenik behar.

Polinomio bat aukeratzerakoan, ez dugu gurpila berrasmatuko, orain ezaguna den CRC-32C hartuko dugu baizik.
Kode honek 6 biteko erroreak detektatzen ditu 22 byte arteko paketeetan (agian guretzat ohikoena dena), 4 biteko akatsak 655 byte arteko paketeetan (guretzat ohikoa den kasua ere), paketeetako 2 biteko errore edo edozein bit-kopuru. zentzuzko edozein luzera.

Norbaitek xehetasunak interesatzen baditu

Wikipediako artikulua CRCri buruz.

Kode parametroak crc-32c on Koopman webgunea - agian planetako CRC espezialista nagusia.

В bere artikulua dago beste kode interesgarri bat, guretzat garrantzitsuak diren pakete-luzeretarako parametro apur bat hobeak eskaintzen dituena, baina ez nuen aldea esanguratsutzat jo, eta nahikoa gaitasun izan nuen kode pertsonalizatua aukeratzeko estandar eta ondo ikertutakoaren ordez.

Gainera, gure datuak konprimituta daudenez, galdera sortzen da: konprimitutako edo konprimitu gabeko datuen checksum-a kalkulatu behar al dugu?

Konprimitu gabeko datuen checksum-a kalkulatzearen aldeko argudioak:

• Azken finean, datuak biltegiratzeko segurtasuna egiaztatu behar dugu - beraz, zuzenean egiaztatzen dugu (aldi berean, konpresio/deskonpresioaren ezarpenean egon daitezkeen akatsak, memoria hautsiak eragindako kalteak, etab. egiaztatuko dira);
• Zlib-en deflate algoritmoak nahiko inplementazio heldua du eta ez luke behar sarrerako datu "makurrekin" erori; gainera, sarritan, sarrerako korrontean akatsak modu independentean detektatzeko gai da, errore bat ez hautemateko probabilitate orokorra murriztuz (erregistro labur batean bit bakar bat inbertituz proba bat egin zuen, zlib-ek errore bat detektatu zuen kasuen heren batean).

Konprimitu gabeko datuen kontrol batura kalkulatzearen aurkako argudioak:

• CRC flash memoriaren ezaugarriak diren bit-errore gutxi batzuetarako bereziki "egokituta" dago (konprimitutako korronte batean akats batek irteerako korrontean aldaketa izugarria eragin dezake, eta horren gainean, teorikoki, talka bat "harrapa dezakegu");
• Ez zait asko gustatzen apurtuta egon daitezkeen datuak deskonpresorera pasatzearen ideia, Nork dakinola erreakzionatuko duen.

Proiektu honetan, konprimitu gabeko datuen checksum bat gordetzeko orokorrean onartutako praktikatik aldeztea erabaki nuen.

Laburpena: CRC-32C erabiltzen dugu, kontrol batura kalkulatzen dugu flashean idazten diren datuetatik (konprimitu ondoren).

Erredundantzia

Kodetze erredundantea erabiltzeak ez du, noski, datu-galera kentzen; hala ere, datu-galera berreskuraezina izateko probabilitatea nabarmen murrizten du (askotan magnitude askoren arabera).

Erredundantzia mota desberdinak erabil ditzakegu akatsak zuzentzeko.
Hamming-kodeek bit bakarreko akatsak zuzen ditzakete, Reed-Solomon karaktere-kodeek, datuen kopia batuketekin konbinatuta edo RAID-6 bezalako kodetzeek datuak berreskuratzen lagun dezakete ustelkeria larria gertatuz gero.
Hasieran, akatsen aurkako kodeketaren erabilera zabalaren aldeko apustua egin nuen, baina gero konturatu nintzen lehenik eta behin geure burua babestu nahi ditugun akatsen ideia izan behar genuela eta gero kodeketa aukeratu.

Lehen esan genuen akatsak ahalik eta azkarren harrapatu behar direla. Zein puntutan aurki ditzakegu akatsak?

1. Amaitu gabeko grabaketa (arrazoiren batengatik grabatzeko unean itzali egin zen, Raspberry izoztu zen, ...)
   Ai, horrelako akatsen bat gertatuz gero, baliogabeko erregistroei jaramonik egin eta datuak galdutzat jotzea besterik ez da geratzen;
2. Idazteko erroreak (arrazoiren batengatik, flash memorian idatzitakoa ez zen idatzitakoa izan)
   Horrelako akatsak berehala antzeman ditzakegu grabatu eta berehala irakurritako proba bat egiten badugu;
3. Memorian dauden datuen distortsioa gordetzean;
4. Irakurketa akatsak
   Zuzentzeko, nahikoa da irakurketa hainbat aldiz errepikatzea kontrol-sumuma ez-egokitzen bada.

Hau da, hirugarren motako akatsak (datuen bat-bateko ustelkeria biltegiratze garaian) bakarrik ezin dira zuzendu erroreen aurkako kodeketarik gabe. Badirudi horrelako akatsak oraindik oso nekezak direla.

Laburpena: kodeketa erredundantea bertan behera uztea erabaki zen, baina eragiketak erabaki honen akatsa erakusten badu, itzul zaitez arazoa aztertzera (hutsei buruzko estatistikak pilatuta daudenak, kodetze mota optimoa aukeratzeko aukera emango duena).

Beste

Noski, artikuluaren formatuak ez digu formatuan bit guztiak justifikatzen uzten (eta indarrak jada agortu zaizkit), beraz, lehen landu ez diren puntu batzuk labur-labur azalduko ditut.

• Orrialde guztiak "berdinak" egitea erabaki zen
  Hau da, ez da orri berezirik izango metadatuak, hari bereiziak, etab., baizik eta orrialde guztiak txandaka berridazten dituen hari bakarra.
  Honek orrialdeetan higadura berdina bermatzen du, hutsegite puntu bakarra ez, eta gustatzen zait;
• Ezinbestekoa da formatuaren bertsioa ematea.
  Goiburuan bertsio-zenbakirik gabeko formatua gaiztoa da!
  Nahikoa da zenbaki magiko (sinadura) jakin bat duen eremu bat gehitzea orriaren goiburuan, erabilitako formatuaren bertsioa adieraziko duena. (Ez dut uste praktikan dozena bat ere izango direnik);
• Erabili luzera aldakorreko goiburua erregistroetarako (asko daude), kasu gehienetan byte bateko luzera izan nahian;
• Goiburuaren luzera eta konprimitutako erregistroaren zati moztuaren luzera kodetzeko, erabili luzera aldakorreko kode bitarrak.

Asko lagundu lineako sorgailua Huffman kodeak. Minutu gutxitan eskatutako luzera aldakorreko kodeak hautatu ahal izan genituen.

Datuak biltegiratzeko formatuaren deskribapena

Byte ordena

Byte bat baino handiagoak diren eremuak big-endian formatuan gordetzen dira (sareko byten ordena), hau da, 0x1234 0x12, 0x34 gisa idazten da.

Paginazioa

Flash memoria guztia tamaina bereko orrialdeetan banatuta dago.

Orrialde-tamaina lehenetsia 32Kb da, baina memoria-txiparen guztizko tamainaren 1/4 baino gehiago ez (4MB-ko txip baterako, 128 orrialde lortzen dira).

Orrialde bakoitzak besteetatik independenteki gordetzen ditu datuak (hau da, orrialde bateko datuek ez dituzte beste orrialde bateko datuak erreferentzia egiten).

Orrialde guztiak ordena naturalean daude zenbakituta (helbideen goranzko ordenan), 0 zenbakitik hasita (zero orria 0 helbidean hasten da, lehenengo orrialdea 32Kb-tik, bigarren orrialdea 64Kb-tik, etab.)

Memoria-txipa buffer zikliko (ring buffer) gisa erabiltzen da, hau da, lehenengo idazketa 0 zenbakira doa, gero 1 zenbakira, ..., azken orria betetzen dugunean, ziklo berri bat hasten da eta grabaketa zero orrialdetik jarraitzen du. .

Orrialde barruan

Orrialdearen hasieran, 4 byteko orrialdeko goiburua gordetzen da, ondoren goiburuko checksum bat (CRC-32C), gero erregistroak "goiburua, datuak, checksum" formatuan gordetzen dira.

Orriaren izenburua (diagraman berde zikina) honako hauek ditu:

• bi byteko Magic Number eremua (formatuaren bertsioaren seinale ere bada)
  formatuaren uneko bertsiorako honela kalkulatzen da 0xed00 ⊕ номер страницы;
• bi byte-ko kontagailua "Orrialdearen bertsioa" (memoria berridazketa zikloaren zenbakia).

Orriaren sarrerak forma konprimituan gordetzen dira (deflate algoritmoa erabiltzen da). Orrialde bateko erregistro guztiak hari batean konprimitzen dira (hiztegi arrunt bat erabiltzen da), eta orrialde berri bakoitzean konpresioa berriro hasten da. Hau da, edozein erregistro deskonprimitzeko, orrialde honetako aurreko erregistro guztiak (eta hau bakarrik) beharrezkoak dira.

Erregistro bakoitza Z_SYNC_FLUSH banderarekin konprimituko da, eta konprimitutako korrontearen amaieran 4x0, 00x0, 00xff, 0xff 0 byte egongo dira, ziurrenik zero byte bat edo bi gehiagoren aurretik.
Sekuentzia hau (4, 5 edo 6 byteko luzera) baztertzen dugu flash memorian idaztean.

Erregistroaren goiburuak 1, 2 edo 3 byte ditu gordetzeko:

• bit bat (T) erregistro mota adieraziz: 0 - testuingurua, 1 - log;
• 1 eta 7 bit arteko luzera aldakorreko eremu bat (S), deskonpresiorako erregistroari gehitu beharreko goiburuaren luzera eta "buztana" definituz;
• erregistroaren luzera (L).

S balioen taula:

S
Goiburuaren luzera, byte
Idazketan baztertua, byte

0
1
5 (00 00 00 ff ff)

10
1
6 (00 00 00 00 ff ff)

110
2
4 (00 00 ff ff)

1110
2
5 (00 00 00 ff ff)

11110
2
6 (00 00 00 00 ff ff)

1111100
3
4 (00 00 ff ff)

1111101
3
5 (00 00 00 ff ff)

1111110
3
6 (00 00 00 00 ff ff)

Saiatu nintzen ilustratzen, ez dakit zein argi geratu zen:

Hemen horiak T eremua adierazten du, zuriak S eremua, berdeak L (konprimitutako datuen luzera bytetan), urdinez konprimitutako datuak, gorria konprimitutako datuen azken byteak flash memorian idazten ez diren.

Horrela, luzera arrunteneko erregistro-goiburuak (63+5 byte arte konprimituta) byte batean idatz ditzakegu.

Erregistro bakoitzaren ondoren, CRC-32C checksum bat gordetzen da, eta bertan aurreko checksumaren alderantzizko balioa erabiltzen da hasierako balio gisa (init).

CRCk "iraupenaren" propietatea du, hurrengo formulak funtzionatzen du (prozesuan bit-inbertsioa gehi edo ken): .
Hau da, hain zuzen ere, orrialde honetako goiburuen eta datuen aurreko byte guztien CRC kalkulatzen dugu.

Zuzenean kontrol batura jarraituz hurrengo erregistroaren goiburua dago.

Goiburua honela diseinatuta dago, non bere lehen bytea beti 0x00 eta 0xff-tik desberdina den (goiburuaren lehen bytearen ordez 0xff aurkitzen badugu, horrek esan nahi du erabili gabeko eremua dela; 0x00-k errore bat adierazten du).

Algoritmo adibideak

Flash memoriatik irakurtzea

Edozein irakurketa kontrol-sumaren egiaztapenarekin dator.
Checksum-a bat ez badator, irakurketa hainbat aldiz errepikatzen da datu zuzenak irakurtzeko asmoz.

(Horrek zentzua du, Linuxek ez ditu NOR Flash-eko irakurketak cachean gordetzen, probatua)

Idatzi flash memorian

Datuak grabatzen ditugu.
Irakur ditzagun.

Irakurritako datuak ez badatoz bat idatzitako datuekin, eremua zeroz beteko dugu eta errore bat adierazten dugu.

Funtzionatzeko mikrozirkuitu berri bat prestatzea

Hasieratzeko, 1. bertsioa duen goiburu bat idazten da lehenengo orrialdean (edo, hobeto esanda, zeroan).
Horren ondoren, hasierako testuingurua orri honetan idazten da (makinaren UUID eta ezarpen lehenetsiak ditu).

Hori da, flash memoria erabiltzeko prest dago.

Makina kargatzea

Kargatzean, orrialde bakoitzeko lehen 8 byteak (goiburua + CRC) irakurtzen dira, Zenbaki magiko ezezaguna edo CRC okerra duten orriak ez ikusi egiten dira.
Orrialde "zuzenetatik" gehieneko bertsioa duten orrialdeak hautatzen dira, eta kopuru handiena duen orria ateratzen da.
Lehenengo erregistroa irakurtzen da, CRCren zuzentasuna eta "testuingurua" banderaren presentzia egiaztatzen da. Dena ondo badago, orri hau egungotzat hartzen da. Hala ez bada, aurrekora itzuliko gara "zuzeneko" orri bat aurkitu arte.
eta aurkitutako orrian erregistro guztiak irakurtzen ditugu, “testuingurua” banderarekin erabiltzen ditugunak.
Gorde zlib hiztegia (beharrezkoa izango da orrialde honetan gehitzeko).

Hori da, deskarga amaitu da, testuingurua leheneratu da, lan egin dezakezu.

Aldizkariko sarrera bat gehitzea

Erregistroa hiztegi egokiarekin konprimitzen dugu, Z_SYNC_FLUSH zehaztuz. Konprimitutako erregistroa uneko orrialdera egokitzen den ikusten dugu.
Ez bada egokitzen (edo orrialdean CRC akatsak egon badaude), hasi orri berri bat (ikus behean).
Erregistroa eta CRC idazten ditugu. Errore bat gertatzen bada, hasi orri berri bat.

Orrialde berria

Gutxieneko zenbakia duen orrialde libre bat hautatzen dugu (goiburuan kontrol-sumuma okerra duen orrialdetzat edo oraingoa baino bertsio txikiagoa duen orrialdetzat jotzen dugu). Horrelako orrialderik ez badago, hautatu uneko bertsioa dutenen artean gutxieneko zenbakia duen orria.
Hautatutako orria ezabatzen dugu. Edukiak 0xff-rekin egiaztatzen ditugu. Zerbait gaizki badago, hartu doan hurrengo orria, etab.
Ezabatutako orrialdean goiburu bat idazten dugu, lehenengo sarrera testuinguruaren uneko egoera da, hurrengoa idatzi gabeko erregistroko sarrera da (baldin badago).

Formatuaren aplikagarritasuna

Nire ustez, formatu ona izan zen konprimagarria den informazio korronte gehiago edo gutxiago (testu arrunta, JSON, MessagePack, CBOR, agian protobuf) NOR Flash-en gordetzeko.

Jakina, formatua SLC NOR Flasherako "neurrira" dago.

Ez da erabili behar NAND edo MLC NOR bezalako BER handiko euskarriekin (Halako memoria salgai al dago? Kode zuzentzaileen lanetan bakarrik ikusi dut aipatuta).

Gainera, ez da erabili behar FTL propioa duten gailuekin: USB flash, SD, MicroSD, etab (Memoria horretarako 512 byteko orri-tamaina duen formatu bat sortu dut, orrialde bakoitzaren hasieran sinadura bat eta erregistro-zenbaki bakarrak - batzuetan, irakurketa sekuentzial soil baten bidez "garatuta" dagoen flash drive batetik datu guztiak berreskuratzea posible zen).

Zereginen arabera, formatua aldaketarik gabe erabil daiteke 128Kbit (16Kb) 1Gbit (128MB) pendriveetan. Nahi izanez gero, txip handiagoetan erabil dezakezu, baina ziurrenik orriaren tamaina egokitu beharko duzu (Baina hemen bideragarritasun ekonomikoaren auzia sortzen da dagoeneko; bolumen handiko NOR Flashen prezioa ez da pozgarria).

Norbaiti formatua interesgarria iruditzen bazaio eta proiektu ireki batean erabili nahi badu, idatzi, denbora bilatzen saiatuko naiz, kodea leuntzen eta github-en argitaratu.

Ondorioa

Ikus dezakezunez, azkenean formatua sinplea izan da eta baita aspergarria ere.

Zaila da nire ikuspuntuaren bilakaera artikulu batean islatzea, baina sinets iezadazu: hasieran zerbait sofistikatua, suntsiezina, hurbileko leherketa nuklear bati ere bizirauteko gai dena sortu nahi nuen. Hala ere, arrazoiak (espero dut) oraindik irabazi zuen eta pixkanaka lehentasunak sinpletasunera eta trinkotasunera aldatu ziren.

Izan al daiteke oker nengoela? Bai ziur. Baliteke, adibidez, kalitate baxuko mikrozirkuitu sorta bat erosi genuela. Edo beste arrazoiren batengatik ekipoak ez ditu fidagarritasun itxaropenak beteko.

Ba al dut horretarako planik? Uste dut artikulua irakurri ondoren plan bat dagoela dudarik ez duzula. Eta ez bakarrik.

Ohar apur bat serioago batean, formatua lan-aukera gisa eta "probako puxika" gisa garatu zen.

Momentuz mahai gainean dagoen guztia ondo dabil, literalki herenegun irtenbidea zabalduko da (gutxi gorabehera) ehunka gailutan, ikus dezagun zer gertatzen den "borroka" eragiketan (zorionez, espero dut formatuak hutsegiteak fidagarri detektatzeko aukera ematea; beraz, estatistika osoak bil ditzakezu). Hilabete gutxi barru ondorioak ateratzeko aukera izango da (eta zorterik ez baduzu, lehenago ere).

Erabileraren emaitzetan oinarrituta arazo larriak aurkitzen badira eta hobekuntzak beharrezkoak badira, zalantzarik gabe idatziko dut horri buruz.

Literatura

Ez nuen erabilitako lanen zerrenda neketsurik egin nahi; azken finean, denek dute Google.

Hemen bereziki interesgarriak iruditu zaizkidan aurkikuntzen zerrenda uztea erabaki nuen, baina pixkanaka artikuluko testura zuzenean migratzen joan ziren, eta elementu bat zerrendan geratu zen:

1. Erabilgarritasuna infgen egilearen zlib. Argi eta garbi bistaratu ditzake deflate/zlib/gzip artxiboen edukia. Deflate (edo gzip) formatuaren barne egiturari aurre egin behar bazaio, gomendatzen dizut.

Iturria: www.habr.com