voorgeskiedenis

Daar is vendingmasjiene van ons eie ontwerp. Binne die Raspberry Pi en 'n paar bedrading op 'n aparte bord. 'n Muntaannemer, 'n wisselaannemer, 'n bankterminaal is gekoppel... Alles word deur 'n selfgeskrewe program beheer. Die hele werkgeskiedenis word na 'n log op 'n flash drive (MicroSD) geskryf, wat dan via die internet (met 'n USB-modem) na die bediener gestuur word, waar dit in 'n databasis gestoor word. Verkoopsinligting word in 1c gelaai, daar is ook 'n eenvoudige webkoppelvlak vir monitering, ens.

Dit wil sê, die joernaal is noodsaaklik - vir rekeningkunde (inkomste, verkope, ens.), monitering (alle soorte mislukkings en ander force majeure-omstandighede); Dit, kan 'n mens sê, is al die inligting wat ons oor hierdie masjien het.

probleem

Flash drives wys hulself as baie onbetroubare toestelle. Hulle misluk met benydenswaardige reëlmaat. Dit lei tot beide stilstand van die masjien en (as die logboek om een ​​of ander rede nie aanlyn oorgedra kon word nie) tot dataverlies.

Dit is nie die eerste ervaring van die gebruik van flash drives nie, voor dit was daar 'n ander projek met meer as honderd toestelle, waar die tydskrif op USB flash drives gestoor is, daar was ook probleme met betroubaarheid, soms die aantal wat misluk het in 'n maand was in die dosyne. Ons het verskillende flash drives probeer, insluitend handelsmerke met SLC geheue, en sommige modelle is meer betroubaar as ander, maar die vervanging van flash drives het nie die probleem radikaal opgelos nie.

Внимание! Langlees! As jy nie in “hoekom” belangstel nie, maar net in “hoe”, kan jy reguit gaan Op die ou end artikel.

besluit

Die eerste ding wat by jou opkom, is: laat vaar MicroSD, installeer byvoorbeeld 'n SSD en begin daaruit. Teoreties moontlik, waarskynlik, maar relatief duur, en nie so betroubaar nie ('n USB-SATA-adapter word bygevoeg; mislukkingstatistieke vir begroting-SSD's is ook nie bemoedigend nie).

USB HDD lyk ook nie na 'n besonder aantreklike oplossing nie.

Daarom het ons by hierdie opsie gekom: laat selflaai vanaf MicroSD, maar gebruik dit in leesalleen-modus, en stoor die operasielogboek (en ander inligting uniek aan 'n spesifieke stuk hardeware - reeksnommer, sensorkalibrasies, ens.) iewers anders .

Die onderwerp van leesalleen FS vir frambose is reeds binne en buite bestudeer, ek sal nie in hierdie artikel stilstaan ​​by implementeringsbesonderhede nie (maar as daar belangstelling is, skryf ek miskien 'n mini-artikel oor hierdie onderwerp). Die enigste punt wat ek wil opmerk, is dat beide uit persoonlike ervaring en uit resensies van diegene wat dit reeds geïmplementeer het, daar 'n wins in betroubaarheid is. Ja, dit is onmoontlik om heeltemal ontslae te raak van ineenstortings, maar dit is heel moontlik om hul frekwensie aansienlik te verminder. En die kaarte word verenig, wat vervanging baie makliker maak vir dienspersoneel.

Die hardeware deel

Daar was geen spesifieke twyfel oor die keuse van geheue tipe - NOR Flash.
Argumente:

• eenvoudige verbinding (meestal die SPI-bus, wat jy reeds ondervinding het om te gebruik, so geen hardeware probleme word voorsien nie);
• belaglike prys;
• standaard bedryfsprotokol (die implementering is reeds in die Linux-kern, as jy wil, kan jy 'n derdeparty een neem, wat ook teenwoordig is, of selfs jou eie skryf, gelukkig is alles eenvoudig);
• betroubaarheid en hulpbron:
  vanaf 'n tipiese datablad: data word vir 20 jaar gestoor, 100000 XNUMX uitvee-siklusse vir elke blok;
  van derdeparty-bronne: uiters lae BER, postuleer geen behoefte aan foutkorreksiekodes nie (sommige werke beskou ECC vir NOR, maar gewoonlik beteken hulle steeds MLC NOR; dit gebeur ook).

Kom ons skat die vereistes vir volume en hulpbron.

Ek wil graag hê dat die data gewaarborg word om vir 'n paar dae gestoor te word. Dit is nodig sodat in die geval van enige kommunikasieprobleme, die verkoopsgeskiedenis nie verlore gaan nie. Ons fokus op 5 dae gedurende hierdie tydperk (selfs met inagneming van naweke en vakansiedae) die probleem opgelos kan word.

Ons versamel tans ongeveer 100 kb logs per dag (3-4 duisend inskrywings), maar geleidelik groei hierdie syfer - die detail neem toe, nuwe gebeurtenisse word bygevoeg. Boonop is daar soms uitbarstings (sommige sensor begin byvoorbeeld strooipos met vals positiewes). Ons sal vir 10 duisend rekords 100 grepe elk - megagrepe per dag bereken.

In totaal kom 5MB skoon (goed saamgeperste) data uit. Meer aan hulle (rowwe skatting) 1 MB diensdata.

Dit wil sê, ons het 'n 8MB-skyfie nodig as ons nie kompressie gebruik nie, of 4MB as ons dit gebruik. Nogal realistiese getalle vir hierdie tipe geheue.

Wat die hulpbron betref: as ons beplan dat die hele geheue nie meer as een keer elke 5 dae herskryf sal word nie, dan kry ons oor 10 jaar diens minder as 'n duisend herskryfsiklusse.
Laat ek jou daaraan herinner dat die vervaardiger honderdduisend belowe.

'n Bietjie oor NOR vs NAND

Vandag is NAND-geheue natuurlik baie meer gewild, maar ek sal dit nie vir hierdie projek gebruik nie: NAND, anders as NOR, vereis noodwendig die gebruik van foutkorreksiekodes, 'n tabel van slegte blokke, ens., en ook die bene van NAND-skyfies gewoonlik baie meer.

Die nadele van NOR sluit in:

• klein volume (en gevolglik hoë prys per megagreep);
• lae kommunikasiespoed (grootliks as gevolg van die feit dat 'n seriële koppelvlak gebruik word, gewoonlik SPI of I2C);
• stadig uitvee (afhangende van die blokgrootte, neem dit van 'n breukdeel van 'n sekonde tot 'n paar sekondes).

Dit blyk dat daar niks krities vir ons is nie, so ons gaan voort.

As die besonderhede interessant is, is die mikrokring gekies op25df321a (dit is egter onbelangrik, daar is baie analoë op die mark wat versoenbaar is in pinout en opdragstelsel; selfs al wil ons 'n mikrokring van 'n ander vervaardiger en/of 'n ander grootte installeer, sal alles werk sonder om die kode).

Ek gebruik die drywer wat in die Linux-kern ingebou is; op Raspberry, danksy toestelboom-oorlegondersteuning, is alles baie eenvoudig - jy moet die saamgestelde oorleg in /boot/overlays plaas en /boot/config.txt effens verander.

Voorbeeld dts lêer

Om eerlik te wees, ek is nie seker dat dit sonder foute geskryf is nie, maar dit werk.

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

En nog 'n reël in config.txt

dtoverlay=at25:spimaxfrequency=50000000

Ek sal die beskrywing van die koppeling van die skyfie aan die Raspberry Pi weglaat. Aan die een kant is ek nie 'n kenner van elektronika nie, aan die ander kant is alles hier banaal, selfs vir my: die mikrokring het net 8 bene, waarvan ons grond, krag, SPI (CS, SI, SO, SCK nodig het) ); die vlakke is dieselfde as dié van die Raspberry Pi, geen bykomende bedrading is nodig nie - koppel net die aangeduide 6 penne.

Probleemstelling

Soos gewoonlik gaan die probleemstelling deur verskeie iterasies, en dit lyk vir my of dit tyd is vir die volgende een. So kom ons stop, stel saam wat reeds geskryf is, en verduidelik die besonderhede wat in die skaduwees bly.

Ons het dus besluit dat die log in SPI NOR Flash gestoor sal word.

Wat is NOR Flash vir diegene wat nie weet nie?

Dit is nie-vlugtige geheue waarmee jy drie bewerkings kan doen:

1. Lees:
   Die mees algemene lesing: ons stuur die adres en lees soveel grepe as wat ons nodig het;
2. Запись:
   Om na NOR-flits te skryf, lyk soos 'n gewone een, maar dit het een eienaardigheid: jy kan net 1 na 0 verander, maar nie andersom nie. Byvoorbeeld, as ons 0x55 in 'n geheuesel gehad het, sal 0x0 reeds daar gestoor word nadat 0x05f daarin geskryf is. (sien tabel net hieronder);
3. Vee uit:
   Natuurlik moet ons die teenoorgestelde bewerking kan doen - verander 0 na 1, dit is presies waarvoor die uitvee-bewerking is. Anders as die eerste twee, werk dit nie met grepe nie, maar met blokke (die minimum uitveeblok in die geselekteerde skyfie is 4kb). Vee vernietig die hele blok en is die enigste manier om 0 na 1 te verander. Daarom, wanneer jy met flitsgeheue werk, moet jy dikwels datastrukture in lyn bring met die uitvee-blokgrens.
   Opname in NOR Flash:

Binêre data

dit was
01010101

Opgeneem
00001111

Het geword
00000101

Die log self verteenwoordig 'n reeks rekords van veranderlike lengte. Die tipiese lengte van 'n rekord is ongeveer 30 grepe (hoewel rekords wat 'n paar kilogrepe lank is soms voorkom). In hierdie geval werk ons ​​bloot met hulle as 'n stel grepe, maar as jy belangstel, word CBOR binne die rekords gebruik

Benewens die log, moet ons 'n paar "instelling"-inligting stoor, beide opgedateer en nie: 'n sekere toestel-ID, sensorkalibrasies, 'n "toestel is tydelik gedeaktiveer"-vlag, ens.
Hierdie inligting is 'n stel sleutelwaarde-rekords, wat ook in CBOR gestoor word. Ons het nie baie van hierdie inligting nie (hoogstens 'n paar kilogrepe), en dit word selde opgedateer.
In wat volg sal ons dit konteks noem.

As ons onthou waar hierdie artikel begin het, is dit baie belangrik om betroubare databerging en, indien moontlik, deurlopende werking te verseker, selfs in die geval van hardewarefoute/datakorrupsie.

Watter bronne van probleme kan oorweeg word?

• Skakel af tydens skryf/vee-bewerkings. Dit is uit die kategorie van "daar is geen truuk teen koevoet nie."
  Inligting van besprekings op stackexchange: wanneer die krag afgeskakel word terwyl daar met flits gewerk word, lei beide uitvee (stel op 1) en skryf (stel op 0) tot ongedefinieerde gedrag: data kan geskryf word, gedeeltelik geskryf (sê, ons het 10 grepe/80 bisse oorgedra , maar daar kan nog nie net 45 bisse geskryf word nie), is dit ook moontlik dat sommige van die bisse in 'n "intermediêre" toestand sal wees (lees kan beide 0 en 1 produseer);
• Foute in die flitsgeheue self.
  BER, hoewel baie laag, kan nie gelyk wees aan nul nie;
• Bus foute
  Data wat via SPI versend word, word op geen manier beskerm nie; beide enkelbisfoute en sinchronisasiefoute kan voorkom - verlies of invoeging van bisse (wat lei tot massiewe datavervorming);
• Ander foute/foute
  Foute in die kode, framboos foute, uitheemse inmenging ...

Ek het die vereistes geformuleer, waarvan die nakoming na my mening nodig is om betroubaarheid te verseker:

• rekords moet onmiddellik in flitsgeheue gaan, vertraagde skryfwerk word nie oorweeg nie; - indien 'n fout voorkom, moet dit so vroeg as moontlik opgespoor en verwerk word; - die stelsel moet, indien moontlik, van foute herstel.
  ('n voorbeeld uit die lewe "hoe dit nie moet wees nie", wat ek dink almal teëgekom het: na 'n noodherlaai is die lêerstelsel "gebreek" en die bedryfstelsel begin nie)

Idees, benaderings, refleksies

Toe ek aan hierdie probleem begin dink het, het baie idees deur my kop geflits, byvoorbeeld:

• gebruik datakompressie;
• gebruik slim datastrukture, bv. stoor rekordopskrifte apart van die rekords self, sodat as daar 'n fout in enige rekord is, jy die res sonder enige probleme kan lees;
• gebruik bisvelde om die voltooiing van opname te beheer wanneer die krag afgeskakel is;
• stoor kontrolesomme vir alles;
• gebruik 'n soort geraasbestande kodering.

Sommige van hierdie idees is gebruik, terwyl ander besluit is om laat vaar te word. Kom ons gaan in volgorde.

Data kompressie

Die gebeure self wat ons in die joernaal opteken, is redelik soortgelyk en herhaalbaar ("het 'n muntstuk van 5 roebel gegooi", "die knoppie gedruk om kleingeld te gee", ...). Daarom moet kompressie redelik effektief wees.

Die kompressiebokoste is onbeduidend (ons verwerker is redelik kragtig, selfs die eerste Pi het een kern gehad met 'n frekwensie van 700 MHz, huidige modelle het verskeie kerns met 'n frekwensie van meer as 'n gigahertz), die wisselkoers met die berging is laag (verskeie megagrepe per sekonde), is die grootte van die rekords klein. Oor die algemeen, as kompressie 'n impak op prestasie het, sal dit net positief wees. (absoluut onkrities, sê net). Boonop het ons nie regte ingebedde nie, maar gewone Linux - so die implementering behoort nie veel moeite te verg nie (dit is genoeg om net die biblioteek te koppel en verskeie funksies daaruit te gebruik).

'n Stuk van die log is van 'n werkende toestel (1.7 MB, 70 duisend inskrywings) geneem en eers nagegaan vir saamdrukbaarheid met behulp van gzip, lz4, lzop, bzip2, xz, zstd wat op die rekenaar beskikbaar is.

• gzip, xz, zstd het soortgelyke resultate getoon (40Kb).
  Ek was verbaas dat die modieuse xz homself hier gewys het op die vlak van gzip of zstd;
• lzip met verstek instellings het effens slegter resultate gegee;
• lz4 en lzop het nie baie goeie resultate getoon nie (150Kb);
• bzip2 het 'n verbasend goeie resultaat getoon (18Kb).

Dus, die data is baie goed saamgepers.
So (as ons nie fatale foute vind nie) sal daar kompressie wees! Bloot omdat meer data op dieselfde flash drive kan pas.

Kom ons dink aan die nadele.

Eerste probleem: ons het reeds ooreengekom dat elke rekord dadelik moet gaan flits. Tipies, die argiefhouer versamel data van die invoerstroom totdat dit besluit dat dit tyd is om oor die naweek te skryf. Ons moet onmiddellik 'n saamgeperste blok data ontvang en dit in nie-vlugtige geheue stoor.

Ek sien drie maniere:

1. Druk elke rekord saam met behulp van woordeboekkompressie in plaas van die algoritmes wat hierbo bespreek is.
   Dit is 'n heeltemal werkende opsie, maar ek hou nie daarvan nie. Om 'n min of meer ordentlike vlak van kompressie te verseker, moet die woordeboek "gepasmaak" word vir spesifieke data; enige verandering sal daartoe lei dat die kompressievlak katastrofies daal. Ja, die probleem kan opgelos word deur 'n nuwe weergawe van die woordeboek te skep, maar dit is 'n kopseer - ons sal alle weergawes van die woordeboek moet stoor; in elke inskrywing sal ons moet aandui met watter weergawe van die woordeboek dit saamgepers is...
2. Druk elke rekord saam met "klassieke" algoritmes, maar onafhanklik van die ander.
   Die kompressie-algoritmes wat oorweeg word, is nie ontwerp om met rekords van hierdie grootte (tiene grepe) te werk nie, die kompressieverhouding sal duidelik minder as 1 wees (dit wil sê, die verhoging van die datavolume in plaas van om saam te pers);
3. Doen FLUSH na elke opname.
   Baie kompressiebiblioteke het ondersteuning vir FLUSH. Dit is 'n opdrag (of 'n parameter vir die kompressieprosedure), by ontvangs wat die argiveerder 'n saamgeperste stroom vorm sodat dit gebruik kan word om te herstel alle ongecomprimeerde data wat reeds ontvang is. So 'n analoog sync in lêerstelsels of commit in sql.
   Wat belangrik is, is dat daaropvolgende kompressie-bewerkings die opgehoopte woordeboek sal kan gebruik en die kompressieverhouding sal nie soveel skade ly as in die vorige weergawe nie.

Ek dink dit is duidelik dat ek die derde opsie gekies het, kom ons kyk in meer detail daarna.

Gevind wonderlike artikel oor FLUSH in zlib.

Ek het 'n knietoets op grond van die artikel gedoen, 70 duisend loginskrywings van 'n regte toestel geneem, met 'n bladsygrootte van 60Kb (ons sal later terugkom na bladsygrootte) ontvang:

Aanvanklike gegewens
Kompressie gzip -9 (geen FLUSH)
zlib met Z_PARTIAL_FLUSH
zlib met Z_SYNC_FLUSH

Volume, KB
1692
40
352
604

Met die eerste oogopslag is die prys wat deur FLUSH bygedra word buitensporig hoog, maar in werklikheid het ons min keuse - óf om glad nie saam te druk nie, óf om (en baie effektief) met FLUSH saam te druk. Ons moet nie vergeet dat ons 70 duisend rekords het nie, die oortolligheid wat deur Z_PARTIAL_FLUSH ingestel is, is slegs 4-5 grepe per rekord. En die kompressieverhouding blyk amper 5:1 te wees, wat meer as 'n uitstekende resultaat is.

Dit mag dalk as 'n verrassing kom, maar Z_SYNC_FLUSH is eintlik 'n meer doeltreffende manier om FLUSH te doen

Wanneer Z_SYNC_FLUSH gebruik word, sal die laaste 4 grepe van elke inskrywing altyd 0x00, 0x00, 0xff, 0xff wees. En as ons hulle ken, dan hoef ons hulle nie te stoor nie, so die finale grootte is slegs 324Kb.

Die artikel waarna ek geskakel het, het 'n verduideliking:

'n Nuwe tipe 0-blok met leë inhoud word aangeheg.

'n Tipe 0-blok met leë inhoud bestaan ​​uit:

• die drie-bis blok kop;
• 0 tot 7 bisse gelyk aan nul, om byte-belyning te bereik;
• die vier-grepe volgorde 00 00 FF FF.

Soos jy maklik kan sien, is daar in die laaste blok voor hierdie 4 grepe van 3 tot 10 nul bisse. Die praktyk het egter getoon dat daar eintlik ten minste 10 nul bisse is.

Dit blyk dat sulke kort blokkies data gewoonlik (altyd?) geënkodeer word deur gebruik te maak van 'n blok van tipe 1 (vaste blok), wat noodwendig eindig met 7 nul bisse, wat 'n totaal van 10-17 gewaarborgde nul bisse gee (en die res sal nul wees met 'n waarskynlikheid van ongeveer 50%.

Dus, op toetsdata, is daar in 100% van die gevalle een nulgrepe voor 0x00, 0x00, 0xff, 0xff, en in meer as 'n derde van die gevalle is daar twee nulgrepe (miskien is die feit dat ek binêre CBOR gebruik, en wanneer teks JSON gebruik word, sal blokke van tipe 2 - dinamiese blok meer algemeen wees, onderskeidelik, blokke sonder bykomende nulgrepe voor 0x00, 0x00, 0xff, 0xff sal teëgekom word).

In totaal, deur die beskikbare toetsdata te gebruik, is dit moontlik om by minder as 250Kb se saamgeperste data in te pas.

Jy kan 'n bietjie meer spaar deur bietjie jongleren te doen: vir nou ignoreer ons die teenwoordigheid van 'n paar nul stukkies aan die einde van die blok, 'n paar stukkies aan die begin van die blok verander ook nie ...
Maar toe neem ek 'n sterk wilsbesluit om op te hou, anders kan ek teen hierdie tempo uiteindelik my eie argiefhouer ontwikkel.

In totaal, uit my toetsdata wat ek 3-4 grepe per skryf ontvang het, het die kompressieverhouding meer as 6:1 geblyk te wees. Ek sal eerlik wees: ek het nie so 'n resultaat verwag nie; na my mening is enigiets beter as 2:1 reeds 'n resultaat wat die gebruik van kompressie regverdig.

Alles is goed, maar zlib (deflateer) is steeds 'n argaïese, welverdiende en effens outydse kompressie-algoritme. Die blote feit dat die laaste 32Kb van die ongecomprimeerde datastroom as 'n woordeboek gebruik word, lyk vandag vreemd (dit wil sê, as een of ander datablok baie soortgelyk is aan wat 40Kb gelede in die invoerstroom was, dan sal dit weer begin geargiveer word, en sal nie na 'n vorige gebeurtenis verwys nie). In modieuse moderne argiveerders word die woordeboekgrootte dikwels in megagrepe eerder as kilogrepe gemeet.

Ons gaan dus voort met ons mini-studie van argiveerders.

Vervolgens het ons bzip2 getoets (onthou, sonder FLUSH het dit 'n fantastiese kompressieverhouding van amper 100:1 getoon). Ongelukkig het dit baie swak gevaar met FLUSH; die grootte van die saamgeperste data het geblyk groter te wees as die ongecomprimeerde data.

My aannames oor die redes vir die mislukking

Libbz2 bied slegs een spoelopsie, wat blykbaar die woordeboek uitvee (analoog aan Z_FULL_FLUSH in zlib); daar is geen sprake van enige effektiewe kompressie hierna nie.

En die laaste een wat getoets is, was zstd. Afhangende van die parameters, komprimeer dit óf op die vlak van gzip, maar baie vinniger, óf beter as gzip.

Helaas, met FLUSH het dit nie baie goed gevaar nie: die grootte van die saamgeperste data was ongeveer 700Kb.

Я 'n vraag gevra op die projek se github-bladsy het ek 'n antwoord gekry dat jy op tot 10 grepe diensdata moet reken vir elke blok saamgeperste data, wat naby aan die resultate is wat verkry is; daar is geen manier om in te haal met deflater nie.

Ek het besluit om op hierdie punt te stop met my eksperimente met argiefhouers (laat ek jou herinner dat xz, lzip, lzo, lz4 hulself nie eers in die toetsstadium sonder FLUSH gewys het nie, en ek het nie meer eksotiese kompressie-algoritmes oorweeg nie).

Kom ons keer terug na argiefprobleme.

Die tweede (soos hulle sê in volgorde, nie in waarde nie) probleem is dat die saamgeperste data 'n enkele stroom is, waarin daar voortdurend verwysings na vorige afdelings is. Dus, as 'n gedeelte van saamgeperste data beskadig word, verloor ons nie net die gepaardgaande blok ongekomprimeerde data nie, maar ook alle daaropvolgendes.

Daar is 'n benadering om hierdie probleem op te los:

1. Voorkom dat die probleem voorkom - voeg oortolligheid by die saamgeperste data, wat jou sal toelaat om foute te identifiseer en reg te stel; ons sal later hieroor praat;
2. Minimaliseer gevolge as 'n probleem voorkom
   Ons het reeds vroeër gesê dat u elke datablok onafhanklik kan saamdruk, en die probleem sal vanself verdwyn (skade aan die data van een blok sal slegs vir hierdie blok tot die verlies van data lei). Dit is egter 'n uiterste geval waarin datakompressie ondoeltreffend sal wees. Die teenoorgestelde uiterste: gebruik al 4MB van ons skyfie as 'n enkele argief, wat ons uitstekende kompressie sal gee, maar katastrofiese gevolge in geval van datakorrupsie.
   Ja, 'n kompromie is nodig wat betroubaarheid betref. Maar ons moet onthou dat ons 'n databergingsformaat vir nie-vlugtige geheue ontwikkel met uiters lae BER en 'n verklaarde databergingstydperk van 20 jaar.

Tydens die eksperimente het ek ontdek dat min of meer merkbare verliese in die kompressievlak begin op blokke saamgeperste data van minder as 10 KB in grootte.
Daar is voorheen genoem dat die geheue wat gebruik word, geblaai word; ek sien geen rede waarom die "een bladsy - een blok saamgeperste data"-korrespondensie nie gebruik moet word nie.

Dit wil sê, die minimum redelike bladsygrootte is 16Kb (met 'n reserwe vir diensinligting). So 'n klein bladsygrootte stel egter aansienlike beperkings op die maksimum rekordgrootte.

Alhoewel ek nog nie rekords groter as 'n paar kilogrepe in saamgeperste vorm verwag nie, het ek besluit om 32Kb bladsye te gebruik (vir 'n totaal van 128 bladsye per skyfie).

Opsomming:

• Ons stoor data saamgepers met behulp van zlib (deflate);
• Vir elke inskrywing stel ons Z_SYNC_FLUSH;
• Vir elke saamgeperste rekord sny ons die agterste grepe af (bv. 0x00, 0x00, 0xff, 0xff); in die kopskrif dui ons aan hoeveel grepe ons afgesny het;
• Ons stoor data in 32Kb bladsye; daar is 'n enkele stroom saamgeperste data binne die bladsy; Op elke bladsy begin ons weer kompressie.

En, voordat ek klaarmaak met kompressie, wil ek u aandag daarop vestig dat ons slegs 'n paar grepe saamgeperste data per rekord het, so dit is uiters belangrik om nie die diensinligting op te blaas nie, elke greep tel hier.

Berging van dataopskrifte

Aangesien ons rekords van veranderlike lengte het, moet ons op een of ander manier die plasing/grense van rekords bepaal.

Ek ken drie benaderings:

1. Alle rekords word in 'n deurlopende stroom gestoor, eers is daar 'n rekordopskrif wat die lengte bevat, en dan die rekord self.
   In hierdie verpersoonliking kan beide opskrifte en data van veranderlike lengte wees.
   In wese kry ons 'n enkelgeskakelde lys wat heeltyd gebruik word;
2. Opskrifte en die rekords self word in aparte strome gestoor.
   Deur opskrifte van konstante lengte te gebruik, verseker ons dat skade aan een kopskrif nie die ander affekteer nie.
   'n Soortgelyke benadering word byvoorbeeld in baie lêerstelsels gebruik;
3. Rekords word in 'n aaneenlopende stroom gestoor, die rekordgrens word bepaal deur 'n sekere merker ('n karakter/reeks karakters wat binne datablokke verbode is). As daar 'n merker in die rekord is, vervang ons dit met 'n volgorde (ontsnap dit).
   'n Soortgelyke benadering word byvoorbeeld in die PPP-protokol gebruik.

Ek sal illustreer.

Opsie 1:

Alles is baie eenvoudig hier: as ons die lengte van die rekord ken, kan ons die adres van die volgende kopskrif bereken. Ons beweeg dus deur die opskrifte totdat ons 'n area teëkom gevul met 0xff (vrye area) of die einde van die bladsy.

Opsie 2:

Weens die veranderlike rekordlengte kan ons nie vooraf sê hoeveel rekords (en dus opskrifte) ons per bladsy benodig nie. Jy kan die opskrifte en die data self oor verskillende bladsye versprei, maar ek verkies 'n ander benadering: ons plaas beide die opskrifte en die data op een bladsy, maar die opskrifte (van konstante grootte) kom van die begin van die bladsy af, en die data (van veranderlike lengte) kom van die einde af. Sodra hulle “ontmoet” (daar is nie genoeg vrye spasie vir 'n nuwe inskrywing nie), beskou ons hierdie bladsy as voltooi.

Opsie 3:

Dit is nie nodig om die lengte of ander inligting oor die ligging van die data in die kopskrif te stoor nie; merkers wat die grense van die rekords aandui, is genoeg. Die data moet egter verwerk word tydens skryf/lees.
Ek sal 0xff as 'n merker gebruik (wat die bladsy vul na uitvee), so die vrye area sal beslis nie as data hanteer word nie.

Vergelyking tabel:

Opsie 1
Opsie 2
Opsie 3

Foutverdraagsaamheid
-
+
+

digtheid
+
-
+

Implementering kompleksiteit
*
**
**

Opsie 1 het 'n noodlottige fout: as enige van die kopstukke beskadig is, word die hele daaropvolgende ketting vernietig. Die oorblywende opsies laat jou toe om sommige data te herstel, selfs in die geval van groot skade.
Maar hier is dit gepas om te onthou dat ons besluit het om die data in 'n saamgeperste vorm te stoor, en dus verloor ons al die data op die bladsy na 'n "gebroke" rekord, so alhoewel daar 'n minus in die tabel is, doen ons dit nie neem dit in ag.

Kompaktheid:

• in die eerste opsie moet ons slegs die lengte in die kopskrif stoor; as ons heelgetalle van veranderlike lengte gebruik, dan kan ons in die meeste gevalle met een greep klaarkom;
• in die tweede opsie moet ons die beginadres en lengte stoor; die rekord moet 'n konstante grootte wees, ek skat 4 grepe per rekord (twee grepe vir die offset, en twee grepe vir die lengte);
• die derde opsie benodig net een karakter om die begin van die opname aan te dui, plus die opname self sal met 1-2% toeneem as gevolg van afskerming. In die algemeen, ongeveer gelykheid met die eerste opsie.

Aanvanklik het ek die tweede opsie as die belangrikste een beskou (en het selfs die implementering geskryf). Ek het dit eers laat vaar toe ek uiteindelik besluit het om kompressie te gebruik.

Miskien sal ek eendag nog 'n soortgelyke opsie gebruik. Byvoorbeeld, as ek te doen het met databerging vir 'n skip wat tussen die Aarde en Mars reis, sal daar heeltemal ander vereistes vir betroubaarheid, kosmiese straling, ...

Wat die derde opsie betref: ek het dit twee sterre gegee vir die moeilikheid van implementering bloot omdat ek nie daarvan hou om met afskerming rond te mors, die lengte in die proses te verander nie, ens. Ja, miskien is ek bevooroordeeld, maar ek sal die kode moet skryf - hoekom moet jy jouself dwing om iets te doen waarvan jy nie hou nie.

Opsomming: Ons kies die bergingsopsie in die vorm van kettings "kop met lengte - data van veranderlike lengte" as gevolg van doeltreffendheid en gemak van implementering.

Gebruik bitvelde om die sukses van skryfbewerkings te monitor

Ek onthou nou nie waar ek die idee gekry het nie, maar dit lyk so iets:
Vir elke inskrywing ken ons verskeie stukkies toe om vlae te stoor.
Soos ons vroeër gesê het, na uitvee is alle bisse gevul met 1s, en ons kan 1 na 0 verander, maar nie andersom nie. So vir "die vlag is nie gestel nie" gebruik ons ​​1, vir "die vlag is gestel" gebruik ons ​​0.

Dit is hoe dit kan lyk om 'n rekord met veranderlike lengte in flits te plaas:

1. Stel die vlag "lengte opname het begin";
2. Teken die lengte aan;
3. Stel die "data-opname het begin" vlag;
4. Ons teken die data aan;
5. Stel die "opname geëindig" vlag.

Daarbenewens sal ons 'n "fout het voorgekom" vlag hê, vir 'n totaal van 4 bis vlae.

In hierdie geval het ons twee stabiele toestande "1111" - opname het nie begin nie en "1000" - opname was suksesvol; in die geval van 'n onverwagte onderbreking van die opnameproses, sal ons tussentoestande ontvang, wat ons dan kan opspoor en verwerk.

Die benadering is interessant, maar dit beskerm net teen skielike kragonderbrekings en soortgelyke onderbrekings, wat natuurlik belangrik is, maar dit is ver van die enigste (of selfs die hoof) rede vir moontlike onderbrekings.

Opsomming: Kom ons gaan aan op soek na 'n goeie oplossing.

Kontrolesomme

Kontrolesomme maak dit ook moontlik om seker te maak (met redelike waarskynlikheid) dat ons presies lees wat geskryf moes gewees het. En, anders as die bietjie velde wat hierbo bespreek is, werk hulle altyd.

As ons die lys van potensiële bronne van probleme wat ons hierbo bespreek het oorweeg, dan kan die kontrolesom 'n fout herken ongeag die oorsprong daarvan (behalwe, miskien, vir kwaadwillige vreemdelinge - hulle kan ook die kontrolesom vervals).

So as ons doel is om te verifieer dat die data ongeskonde is, is kontrolesomme 'n goeie idee.

Die keuse van algoritme vir die berekening van die kontrolesom het geen vrae laat ontstaan ​​nie - CRC. Aan die een kant maak wiskundige eienskappe dit moontlik om sekere tipe foute 100% op te vang; aan die ander kant, op ewekansige data toon hierdie algoritme gewoonlik die waarskynlikheid van botsings wat nie veel groter is as die teoretiese limiet nie . Dit is dalk nie die vinnigste algoritme nie, en dit is ook nie altyd die minimum wat die aantal botsings betref nie, maar dit het 'n baie belangrike eienskap: in die toetse wat ek teëgekom het, was daar geen patrone waarin dit duidelik misluk het nie. Stabiliteit is die belangrikste kwaliteit in hierdie geval.

Voorbeeld van 'n volumetriese studie: deel 1, deel 2 (skakels na narod.ru, jammer).

Die taak om 'n kontrolesom te kies is egter nie voltooi nie; CRC is 'n hele familie van kontrolesomme. Jy moet oor die lengte besluit en dan 'n polinoom kies.

Die keuse van die kontrolesom-lengte is nie so 'n eenvoudige vraag soos dit met die eerste oogopslag lyk nie.

Laat ek illustreer:
Kom ons het die waarskynlikheid van 'n fout in elke greep en 'n ideale kontrolesom, kom ons bereken die gemiddelde aantal foute per miljoen rekords:

Data, byte
Kontrolesom, byte
Onopgemerkte foute
Vals foutopsporings
Totale vals positiewe

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

Dit wil voorkom asof alles eenvoudig is - afhangende van die lengte van die data wat beskerm word, kies die lengte van die kontrolesom met 'n minimum van verkeerde positiewe - en die truuk is in die sak.

'n Probleem ontstaan ​​egter met kort kontrolesomme: alhoewel hulle goed is om enkelbisfoute op te spoor, kan hulle met 'n redelike hoë waarskynlikheid heeltemal ewekansige data as korrek aanvaar. Daar was reeds 'n artikel oor Habré wat beskryf het probleem in die werklike lewe.

Daarom, om 'n ewekansige kontrolesom-passing byna onmoontlik te maak, moet jy kontrolesomme gebruik wat 32 bisse of langer is. (vir lengtes groter as 64 bisse, word kriptografiese hash-funksies tipies gebruik).

Ten spyte van die feit dat ek vroeër geskryf het dat ons met alle middele ruimte moet bespaar, sal ons steeds 'n 32-bis kontrolesom gebruik (16 bisse is nie genoeg nie, die waarskynlikheid van 'n botsing is meer as 0.01%; en 24 bisse, aangesien hulle sê, is nie hier of daar nie).

'n Beswaar kan hier ontstaan: het ons elke greep gestoor toe ons kompressie gekies het om nou 4 grepe gelyktydig te gee? Sou dit nie beter wees om nie 'n kontrolesom saam te druk of by te voeg nie? Natuurlik nie, geen kompressie nie beteken nie, dat ons nie integriteitskontrole nodig het nie.

Wanneer ons 'n polinoom kies, sal ons nie die wiel herontdek nie, maar die nou gewilde CRC-32C neem.
Hierdie kode bespeur 6 bis foute op pakkies tot 22 grepe (dalk die mees algemene geval vir ons), 4 bis foute op pakkies tot 655 grepe (ook 'n algemene geval vir ons), 2 of enige onewe aantal bis foute op pakkies van enige redelike lengte.

Indien iemand belangstel in die besonderhede

Wikipedia artikel oor CRC.

Kode parameters crc-32c op Koopman webwerf - miskien die voorste CRC-spesialis op die planeet.

В sy artikel daar is nog 'n interessante kode, wat effens beter parameters bied vir die pakkielengtes wat vir ons relevant is, maar ek het nie die verskil as betekenisvol beskou nie, en ek was bekwaam genoeg om pasgemaakte kode te kies in plaas van die standaard en goed nagevorsde een.

Ook, aangesien ons data saamgepers is, ontstaan ​​die vraag: moet ons die kontrolesom van saamgeperste of ongecomprimeerde data bereken?

Argumente ten gunste van die berekening van die kontrolesom van ongecomprimeerde data:

• Ons moet uiteindelik die veiligheid van databerging nagaan - dus gaan ons dit direk na (terselfdertyd sal moontlike foute in die implementering van kompressie/dekompressie, skade veroorsaak deur stukkende geheue, ens. nagegaan word);
• Die deflater-algoritme in zlib het 'n redelik volwasse implementering en moet nie val met "skewe" invoerdata; bowendien is dit dikwels in staat om foute in die invoerstroom onafhanklik op te spoor, wat die algehele waarskynlikheid verminder om 'n fout te onopspoor (het 'n toets uitgevoer met die omkeer van 'n enkele bis in 'n kort rekord, zlib het 'n fout opgespoor in ongeveer 'n derde van die gevalle).

Argumente teen die berekening van die kontrolesom van ongecomprimeerde data:

• CRC is spesifiek "gepasmaak" vir die paar bisfoute wat kenmerkend is van flitsgeheue ('n bisfout in 'n saamgeperste stroom kan 'n massiewe verandering in die uitsetstroom veroorsaak, waarop ons, suiwer teoreties, 'n botsing kan "vang");
• Ek hou nie regtig van die idee om potensieel gebroke data na die dekompressor deur te gee nie, Wie weethoe hy sal reageer.

In hierdie projek het ek besluit om af te wyk van die algemeen aanvaarde praktyk om 'n kontrolesom van ongecomprimeerde data te stoor.

Opsomming: Ons gebruik CRC-32C, ons bereken die kontrolesom uit die data in die vorm waarin hulle geskryf is om te flits (na kompressie).

Oortolligheid

Die gebruik van oortollige kodering skakel natuurlik nie dataverlies uit nie, maar dit kan egter aansienlik (dikwels met baie ordes van grootte) die waarskynlikheid van onherstelbare dataverlies verminder.

Ons kan verskillende tipes oortolligheid gebruik om foute reg te stel.
Hamming-kodes kan enkelbisfoute regstel, Reed-Solomon-karakterkodes, veelvuldige kopieë van data gekombineer met kontrolesomme, of enkoderings soos RAID-6 kan help om data te herstel, selfs in die geval van grootskaalse korrupsie.
Aanvanklik was ek verbind tot die wydverspreide gebruik van foutbestande kodering, maar toe het ek besef dat ons eers 'n idee moet hê van watter foute ons onsself wil beskerm, en dan kodering moet kies.

Ons het vroeër gesê dat foute so gou as moontlik opgespoor moet word. Op watter punte kan ons foute teëkom?

1. Onvoltooide opname (om een ​​of ander rede ten tyde van opname was die krag afgeskakel, die Framboos het gevries, ...)
   Helaas, in die geval van so 'n fout, is al wat oorbly om ongeldige rekords te ignoreer en die data as verlore te beskou;
2. Skryffoute (om een ​​of ander rede was dit wat in die flitsgeheue geskryf is nie wat geskryf is nie)
   Ons kan sulke foute onmiddellik opspoor as ons 'n toetslees onmiddellik na opname doen;
3. Vervorming van data in geheue tydens berging;
4. Leesfoute
   Om dit reg te stel, as die kontrolesom nie ooreenstem nie, is dit genoeg om die lesing verskeie kere te herhaal.

Dit wil sê, slegs foute van die derde tipe (spontane korrupsie van data tydens berging) kan nie reggestel word sonder foutbestande kodering nie. Dit blyk dat sulke foute steeds uiters onwaarskynlik is.

Opsomming: daar is besluit om oortollige kodering te laat vaar, maar as die operasie die fout van hierdie besluit toon, keer dan terug na die oorweging van die kwessie (met reeds opgehoopte statistieke oor mislukkings, wat dit moontlik maak om die optimale tipe kodering te kies).

Ander

Die formaat van die artikel laat ons natuurlik nie toe om elke stukkie in die formaat te regverdig nie (en my krag het reeds opgeraak), so ek gaan kortliks oor enkele punte wat nie vroeër aangeraak is nie.

• Daar is besluit om alle bladsye "gelyk" te maak
  Dit wil sê, daar sal geen spesiale bladsye met metadata, aparte drade, ens. wees nie, maar eerder 'n enkele draad wat alle bladsye om die beurt herskryf.
  Dit verseker egalige slytasie op die bladsye, geen enkele punt van mislukking nie, en ek hou net daarvan;
• Dit is noodsaaklik om weergawe van die formaat te verskaf.
  'n Formaat sonder 'n weergawenommer in die kopskrif is boos!
  Dit is genoeg om 'n veld met 'n sekere Magic Number (handtekening) by die bladsyopskrif te voeg, wat die weergawe van die formaat wat gebruik word, sal aandui (Ek dink nie dat daar in die praktyk selfs 'n dosyn van hulle sal wees nie);
• Gebruik 'n veranderlike lengte-opskrif vir rekords (waarvan daar baie is), en probeer dit in die meeste gevalle 1 greep lank maak;
• Gebruik veranderlike-lengte binêre kodes om die lengte van die kopskrif en die lengte van die afgewerkte deel van die saamgeperste rekord te enkodeer.

Baie gehelp aanlyn kragopwekker Huffman kodes. Binne net 'n paar minute kon ons die vereiste veranderlike lengtekodes kies.

Beskrywing van data stoor formaat

Byte volgorde

Velde groter as een greep word in groot-endian-formaat (netwerkgreepvolgorde) gestoor, dit wil sê, 0x1234 word geskryf as 0x12, 0x34.

Paginering

Alle flitsgeheue word in bladsye van gelyke grootte verdeel.

Die verstekbladsygrootte is 32Kb, maar nie meer as 1/4 van die totale grootte van die geheueskyfie nie (vir 'n 4MB-skyfie word 128 bladsye verkry).

Elke bladsy stoor data onafhanklik van die ander (dit wil sê, data op een bladsy verwys nie na data op 'n ander bladsy nie).

Alle bladsye is genommer in natuurlike volgorde (in stygende volgorde van adresse), begin met nommer 0 (bladsy nul begin by adres 0, die eerste bladsy begin by 32Kb, die tweede bladsy begin by 64Kb, ens.)

Die geheueskyfie word as 'n sikliese buffer (ringbuffer) gebruik, dit wil sê, skryf gaan eers na bladsy nommer 0, dan nommer 1, ..., wanneer ons die laaste bladsy vul, begin 'n nuwe siklus en opname gaan voort vanaf bladsy nul .

Binne die bladsy

Aan die begin van die bladsy word 'n 4-grepe bladsyopskrif gestoor, dan 'n kopkontrolesom (CRC-32C), dan word rekords in die "kop, data, kontrolesom"-formaat gestoor.

Die bladsytitel (vuilgroen in die diagram) bestaan ​​uit:

• twee-grepe Magic Number veld (ook 'n teken van die formaat weergawe)
  vir die huidige weergawe van die formaat word dit bereken as 0xed00 ⊕ номер страницы;
• twee-grepe teller "Blad weergawe" (geheue herskryf siklus nommer).

Inskrywings op die bladsy word in saamgeperste vorm gestoor (die deflate-algoritme word gebruik). Alle rekords op een bladsy word in een draad saamgepers ('n algemene woordeboek word gebruik), en op elke nuwe bladsy begin kompressie nuut. Dit wil sê, om enige rekord te dekomprimeer, word alle vorige rekords vanaf hierdie bladsy (en slegs hierdie een) vereis.

Elke rekord sal saamgepers word met die Z_SYNC_FLUSH vlag, en aan die einde van die saamgeperste stroom sal daar 4 grepe 0x00, 0x00, 0xff, 0xff wees, moontlik voorafgegaan deur nog een of twee nulgrepe.
Ons gooi hierdie volgorde (4, 5 of 6 grepe lank) weg wanneer ons na flitsgeheue skryf.

Die rekordopskrif is 1, 2 of 3 grepe wat stoor:

• een bis (T) wat die tipe rekord aandui: 0 - konteks, 1 - log;
• 'n Veranderlike lengteveld (S) van 1 tot 7 bisse, wat die lengte van die kopskrif en die "stert" definieer wat by die rekord gevoeg moet word vir dekompressie;
• rekordlengte (L).

S waarde tabel:

S
Koplengte, grepe
Weggegooi op skryf, 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)

Ek het probeer illustreer, ek weet nie hoe duidelik dit uitgedraai het nie:

Geel dui hier die T-veld aan, wit die S-veld, groen L (die lengte van die saamgeperste data in grepe), blou die saamgeperste data, rooi die finale grepe van die saamgeperste data wat nie na flitsgeheue geskryf is nie.

Ons kan dus rekordopskrifte van die mees algemene lengte (tot 63+5 grepe in saamgeperste vorm) in een greep skryf.

Na elke rekord word 'n CRC-32C kontrolesom gestoor, waarin die omgekeerde waarde van die vorige kontrolesom as die aanvanklike waarde (init) gebruik word.

CRC het die eienskap van "duur", die volgende formule werk (plus of minus bietjie inversie in die proses): .
Dit wil sê, ons bereken die CRC van alle vorige grepe van opskrifte en data op hierdie bladsy.

Direk na die kontrolesom is die opskrif van die volgende rekord.

Die kopskrif is so ontwerp dat sy eerste greep altyd verskil van 0x00 en 0xff (as ons in plaas van die eerste greep van die kop 0xff teëkom, beteken dit dat dit 'n ongebruikte area is; 0x00 dui op 'n fout).

Voorbeeld Algoritmes

Lees vanaf Flash Memory

Enige lesing kom met 'n kontrolesom-tjek.
As die kontrolesom nie ooreenstem nie, word die lesing verskeie kere herhaal in die hoop om die korrekte data te lees.

(dit maak sin, Linux kas nie lees van NOR Flash nie, getoets)

Skryf na flitsgeheue

Ons teken die data aan.
Kom ons lees hulle.

As die gelees data nie ooreenstem met die geskrewe data nie, vul ons die area met nulle en dui 'n fout aan.

Berei 'n nuwe mikrokring voor vir werking

Vir inisialisering word 'n kopskrif met weergawe 1 na die eerste (of eerder nul) bladsy geskryf.
Daarna word die aanvanklike konteks na hierdie bladsy geskryf (bevat die UUID van die masjien en verstekinstellings).

Dit is dit, die flitsgeheue is gereed vir gebruik.

Laai die masjien

Wanneer laai, word die eerste 8 grepe van elke bladsy (kop + CRC) gelees, bladsye met 'n onbekende Magic Number of 'n verkeerde CRC word geïgnoreer.
Van die “korrekte” bladsye word bladsye met die maksimum weergawe gekies, en die bladsy met die hoogste nommer word daarvan geneem.
Die eerste rekord word gelees, die korrektheid van die CRC en die teenwoordigheid van die "konteks" vlag word nagegaan. As alles reg is, word hierdie bladsy as huidige beskou. Indien nie, rol ons terug na die vorige een totdat ons 'n "live" bladsy kry.
en op die gevind bladsy lees ons al die rekords, dié wat ons gebruik met die “konteks” vlag.
Stoor die zlib-woordeboek (dit sal nodig wees om by hierdie bladsy te voeg).

Dit is dit, die aflaai is voltooi, die konteks is herstel, jy kan werk.

Voeg 'n joernaalinskrywing by

Ons druk die rekord saam met die korrekte woordeboek, spesifiseer Z_SYNC_FLUSH. Ons sien of die saamgeperste rekord op die huidige bladsy pas.
As dit nie pas nie (of daar was CRC-foute op die bladsy), begin 'n nuwe bladsy (sien hieronder).
Ons skryf die rekord en CRC neer. As 'n fout voorkom, begin 'n nuwe bladsy.

Nuwe bladsy

Ons kies 'n gratis bladsy met die minimum aantal (ons beskou 'n gratis bladsy as 'n bladsy met 'n verkeerde kontrolesom in die kopskrif of met 'n weergawe minder as die huidige een). As daar nie sulke bladsye is nie, kies die bladsy met die minimum aantal uit dié wat 'n weergawe gelyk aan die huidige een het.
Ons vee die geselekteerde bladsy uit. Ons kontroleer die inhoud met 0xff. As iets fout is, neem die volgende gratis bladsy, ens.
Ons skryf 'n kopskrif op die uitgevee bladsy, die eerste inskrywing is die huidige toestand van die konteks, die volgende is die ongeskrewe loginskrywing (as daar een is).

Formaat toepaslikheid

Na my mening het dit geblyk 'n goeie formaat te wees om enige min of meer saamdrukbare inligtingstrome (plain text, JSON, MessagePack, CBOR, moontlik protobuf) in NOR Flash te stoor.

Natuurlik is die formaat "gepasmaak" vir SLC NOR Flash.

Dit moet nie met hoë BER-media soos NAND of MLC NOR gebruik word nie (is sulke geheue selfs te koop beskikbaar? Ek het dit nog net gesien in werke oor regstellingskodes).

Boonop moet dit nie gebruik word met toestelle wat hul eie FTL het nie: USB-flits, SD, MicroSD, ens (vir so 'n geheue het ek 'n formaat geskep met 'n bladsygrootte van 512 grepe, 'n handtekening aan die begin van elke bladsy en unieke rekordnommers - soms was dit moontlik om al die data van 'n "flash drive" te herstel deur eenvoudige opeenvolgende lees).

Afhangende van die take, kan die formaat gebruik word sonder veranderinge op flash drives van 128Kbit (16Kb) tot 1Gbit (128MB). As jy wil, kan jy dit op groter skyfies gebruik, maar jy moet waarskynlik die bladsygrootte aanpas (Maar hier ontstaan ​​die vraag na ekonomiese haalbaarheid reeds; die prys vir groot volume NOR Flash is nie bemoedigend nie).

As iemand die formaat interessant vind en dit in 'n oop projek wil gebruik, skryf, ek sal probeer om die tyd te vind, die kode te poets en dit op github te plaas.

Gevolgtrekking

Soos u kan sien, het die formaat uiteindelik eenvoudig geblyk te wees en selfs vervelig.

Dit is moeilik om die evolusie van my standpunt in 'n artikel te weerspieël, maar glo my: aanvanklik wou ek iets gesofistikeerd, onvernietigbaar skep, wat selfs 'n kernontploffing in die nabyheid kon oorleef. Die rede (hoop ek) het egter steeds gewen en geleidelik het prioriteite verskuif na eenvoud en kompaktheid.

Kan dit wees dat ek verkeerd was? Ja seker. Dit kan dalk blyk, byvoorbeeld, dat ons 'n bondel lae-gehalte mikrobane gekoop het. Of om een ​​of ander rede sal die toerusting nie aan betroubaarheidsverwagtinge voldoen nie.

Het ek 'n plan hiervoor? Ek dink dat jy na die lees van die artikel geen twyfel het dat daar 'n plan is nie. En nie eers alleen nie.

Op 'n effens meer ernstige noot, die formaat is beide ontwikkel as 'n werkende opsie en as 'n "proefballon".

Op die oomblik werk alles op die tafel goed, letterlik die ander dag sal die oplossing ontplooi word (ongeveer) op honderde toestelle, kom ons kyk wat gebeur in "geveg"-operasie (gelukkig hoop ek dat die formaat jou toelaat om foute betroubaar op te spoor; sodat jy volledige statistieke kan insamel). Oor 'n paar maande sal dit moontlik wees om gevolgtrekkings te maak (en as jy ongelukkig is, selfs vroeër).

As, op grond van die resultate van gebruik, ernstige probleme ontdek word en verbeterings nodig is, sal ek beslis daaroor skryf.

Letterkunde

Ek wou nie 'n lang vervelige lys van gebruikte werke maak nie; almal het immers Google.

Hier het ek besluit om 'n lys van bevindings te laat wat vir my besonder interessant gelyk het, maar geleidelik het hulle direk na die teks van die artikel migreer, en een item het op die lys gebly:

1. Nuts infgen van die skrywer zlib. Kan die inhoud van deflate/zlib/gzip-argiewe duidelik vertoon. As jy die interne struktuur van die deflate (of gzip) formaat moet hanteer, beveel ek dit sterk aan.

Bron: will.com