esihistoria

Siellä on omia suunnittelemiamme myyntiautomaatteja. Raspberry Pi:n sisällä ja jotkut johdotukset erillisellä levyllä. Kolikon vastaanottaja, seteleiden vastaanottaja, pankkipääte on kytketty... Kaikkea ohjaa itse kirjoitettu ohjelma. Koko työhistoria kirjoitetaan muistitikulle (MicroSD) olevaan lokiin, joka sitten siirretään Internetin kautta (USB-modeemin avulla) palvelimelle, jossa se tallennetaan tietokantaan. Myyntitiedot ladataan 1c:hen, siellä on myös yksinkertainen web-käyttöliittymä seurantaan jne.

Toisin sanoen päiväkirja on elintärkeä - kirjanpitoon (tulot, myynti jne.), seurantaan (kaikenlaiset viat ja muut ylivoimaiset esteet); Voidaan sanoa, että tämä on kaikki tieto, joka meillä on tästä koneesta.

ongelma

Flash-asemat osoittavat olevansa erittäin epäluotettavia laitteita. Ne epäonnistuvat kadehdittavalla säännöllisyydellä. Tämä johtaa sekä koneen seisokkiin että (jos lokia ei jostain syystä voitu siirtää verkkoon) tietojen katoamiseen.

Tämä ei ole ensimmäinen kokemus flash-asemien käytöstä, ennen tätä oli toinen yli sadan laitteen projekti, jossa lehti tallennettiin USB-muistitikuille, myös luotettavuudessa oli ongelmia, välillä epäonnistuneiden määrä. kuukausi oli kymmeniä. Kokeilimme erilaisia ​​flash-asemia, myös merkkituotteita SLC-muistilla, ja jotkut mallit ovat luotettavampia kuin toiset, mutta flash-asemien vaihtaminen ei ratkaise ongelmaa radikaalisti.

Varoitus! Pitkään luettu! Jos et ole kiinnostunut "miksi", vaan vain "miten", voit mennä suoraan Lopussa artikkeli.

päätös

Ensimmäinen asia, joka tulee mieleen, on: hylkää MicroSD, asenna esimerkiksi SSD ja käynnistä se. Teoreettisesti mahdollista, luultavasti, mutta suhteellisen kallis, eikä niin luotettava (USB-SATA-sovitin on lisätty; budjetti-SSD-levyjen vikatilastot eivät myöskään ole rohkaisevia).

USB HDD ei myöskään näytä erityisen houkuttelevalta ratkaisulta.

Siksi päädyimme tähän vaihtoehtoon: jätä käynnistys MicroSD-kortilta, mutta käytä niitä vain luku -tilassa ja tallenna toimintaloki (ja muut tietylle laitteistolle ainutlaatuiset tiedot - sarjanumero, anturin kalibroinnit jne.) jonnekin muualle .

Aihetta vadelmien vain luku -tilassa olevasta FS:stä on jo tutkittu sisältä ja ulkoa, en viivyttele toteutuksen yksityiskohdista tässä artikkelissa (mutta jos kiinnostusta löytyy, ehkä kirjoitan tästä aiheesta miniartikkelin). Ainoa asia, jonka haluaisin huomauttaa, on se, että sekä henkilökohtaisen kokemuksen että sen jo toteuttaneiden arvioiden perusteella luotettavuus paranee. Kyllä, on mahdotonta päästä kokonaan eroon häiriöistä, mutta niiden tiheyden vähentäminen merkittävästi on täysin mahdollista. Ja kortit yhtenäistyvät, mikä helpottaa huomattavasti huoltohenkilöstön vaihtoa.

Laitteiston osa

Muistityypin valinnasta - NOR Flash - ei ollut erityistä epäilystä.
argumentit:

• yksinkertainen yhteys (useimmiten SPI-väylä, jonka käytöstä sinulla on jo kokemusta, joten laitteistoongelmia ei ole odotettavissa);
• naurettava hinta;
• standardi käyttöprotokolla (toteutus on jo Linux-ytimessä, jos haluat, voit ottaa kolmannen osapuolen, joka on myös läsnä, tai jopa kirjoittaa omasi, onneksi kaikki on yksinkertaista);
• luotettavuus ja resurssit:
  tyypillisestä tietolomakkeesta: tietoja säilytetään 20 vuotta, 100000 XNUMX tyhjennysjaksoa jokaista lohkoa kohden;
  kolmannen osapuolen lähteistä: erittäin alhainen BER, olettaa, ettei virheenkorjauskoodeja tarvita (jotkut teokset harkitsevat ECC:tä NOR:lle, mutta yleensä ne tarkoittavat silti MLC NOR:ia; näin myös tapahtuu).

Arvioidaan volyymi- ja resurssivaatimukset.

Haluaisin, että tiedot säilytetään useiden päivien ajan. Tämä on välttämätöntä, jotta kommunikaatio-ongelmien sattuessa myyntihistoria ei katoa. Keskitymme 5 päivään tänä aikana (myös viikonloput ja juhlapyhät huomioon ottaen) ongelma voidaan ratkaista.

Keräämme tällä hetkellä noin 100 kb lokeja päivässä (3-4 tuhatta merkintää), mutta vähitellen tämä luku kasvaa - yksityiskohdat lisääntyvät, uusia tapahtumia lisätään. Lisäksi joskus esiintyy purskeita (esimerkiksi jotkut anturit alkavat lähettää roskapostia väärillä positiivisilla tuloksilla). Laskemme 10 tuhannelle tietueelle 100 tavua - megatavua päivässä.

Yhteensä 5 Mt puhdasta (hyvin pakattua) tietoa tulee ulos. Heille enemmän (karkea arvio) 1 Mt palvelutietoja.

Eli tarvitsemme 8 Mt:n sirun, jos emme käytä pakkausta, tai 4 Mt, jos käytämme sitä. Melko realistisia lukuja tämän tyyppiselle muistille.

Mitä tulee resurssiin: jos suunnittelemme, että koko muisti kirjoitetaan uudelleen enintään kerran 5 päivässä, niin yli 10 vuoden palvelun saamme alle tuhat uudelleenkirjoitusjaksoa.
Haluan muistuttaa, että valmistaja lupaa satatuhatta.

Hieman NOR vs NAND

Nykyään tietysti NAND-muisti on paljon suositumpi, mutta en käyttäisi sitä tähän projektiin: NAND, toisin kuin NOR, vaatii välttämättä virheenkorjauskoodien käyttöä, huonojen lohkojen taulukkoa jne. sekä myös jalkoja NAND-siruja yleensä paljon enemmän.

NOR:n haittoja ovat:

• pieni määrä (ja vastaavasti korkea hinta megatavua kohden);
• alhainen tiedonsiirtonopeus (johtuen pitkälti siitä, että käytetään sarjaliitäntää, yleensä SPI tai I2C);
• hidas tyhjennys (lohkon koosta riippuen se kestää sekunnin murto-osasta useisiin sekunteihin).

Näyttää siltä, ​​ettei meille ole mitään kriittistä, joten jatkamme.

Jos yksityiskohdat kiinnostavat, mikropiiri on valittu at25df321a (Tällä ei kuitenkaan ole merkitystä, markkinoilla on paljon analogeja, jotka ovat yhteensopivia pinout- ja komentojärjestelmässä; vaikka haluaisimme asentaa mikropiirin eri valmistajalta ja/tai eri kokoiselta, kaikki toimii muuttamatta koodi).

Käytän Linux-ytimeen sisäänrakennettua ohjainta; Raspberryssä laitepuun peittokuvan tuen ansiosta kaikki on hyvin yksinkertaista - sinun täytyy laittaa käännetty peittokuva kansioon /boot/overlays ja muokata hieman /boot/config.txt-tiedostoa.

Esimerkki dts-tiedostosta

Rehellisesti sanottuna en ole varma, onko se kirjoitettu ilman virheitä, mutta se toimii.

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

Ja toinen rivi config.txt:ssä

dtoverlay=at25:spimaxfrequency=50000000

Jätän pois kuvauksen sirun liittämisestä Raspberry Pi:hen. Toisaalta en ole elektroniikan asiantuntija, toisaalta kaikki täällä on minullekin banaalia: mikropiirissä on vain 8 jalkaa, joista tarvitsemme maadoituksen, tehon, SPI:n (CS, SI, SO, SCK); tasot ovat samat kuin Raspberry Pi:ssä, lisäjohdotuksia ei tarvita - liitä vain ilmoitetut 6 nastaa.

Ongelma

Kuten tavallista, ongelmanlausunto käy läpi useita iteraatioita, ja minusta näyttää siltä, ​​että on seuraavan aika. Pysähdytään siis, kootaan yhteen jo kirjoitettu ja selvennetään varjossa jääviä yksityiskohtia.

Joten olemme päättäneet, että loki tallennetaan SPI NOR Flashiin.

Mikä NOR Flash on niille, jotka eivät tiedä?

Tämä on haihtumaton muisti, jolla voit tehdä kolme toimintoa:

1. Lukeminen:
   Yleisin lukema: lähetämme osoitteen ja luemme niin monta tavua kuin tarvitsemme;
2. Запись:
   NOR-flashille kirjoittaminen näyttää tavalliselta, mutta sillä on yksi erikoisuus: voit muuttaa vain 1 arvoksi 0, mutta ei päinvastoin. Esimerkiksi, jos meillä oli muistisolussa 0x55, 0x0 tallennetaan jo siihen, kun siihen on kirjoitettu 0x05f (katso taulukko alla);
3. Erase:
   Tietenkin meidän on kyettävä tekemään päinvastainen toimenpide - vaihda 0 arvoksi 1, tämä on juuri sitä varten, mitä varten poistotoiminto on tarkoitettu. Toisin kuin kaksi ensimmäistä, se ei toimi tavuilla, vaan lohkoilla (valitun sirun vähimmäispoistolohko on 4 kt). Erase tuhoaa koko lohkon ja on ainoa tapa muuttaa 0:ksi 1. Siksi flash-muistin kanssa työskennellessä joudut usein kohdistamaan tietorakenteet poistolohkon rajaan.
   Nauhoitus NOR Flashilla:

Binaaridata

se oli
01010101

Äänitetty
00001111

On tullut
00000101

Itse loki edustaa vaihtelevan pituisten tietueiden sarjaa. Tietueen tyypillinen pituus on noin 30 tavua (vaikka joskus esiintyy useita kilotavuja pitkiä tietueita). Tässä tapauksessa työskentelemme niiden kanssa yksinkertaisesti tavujoukona, mutta jos olet kiinnostunut, tietueiden sisällä käytetään CBOR:ia

Lokin lisäksi meidän on tallennettava joitain "asetustietoja", sekä päivitettyjä että päivittämättömiä: tietty laitetunnus, anturin kalibroinnit, "laite on tilapäisesti poistettu käytöstä" -merkki jne.
Nämä tiedot ovat joukko avainarvotietueita, jotka on myös tallennettu CBOR:iin. Meillä ei ole paljon näitä tietoja (enintään muutama kilotavu), ja niitä päivitetään harvoin.
Seuraavassa kutsumme sitä kontekstiksi.

Jos muistamme, mistä tämä artikkeli alkoi, on erittäin tärkeää varmistaa luotettava tiedon tallennus ja mahdollisuuksien mukaan jatkuva toiminta myös laitteistovikojen/tietojen vioittumisen yhteydessä.

Mitä ongelmien lähteitä voidaan ajatella?

• Katkaise virta kirjoitus-/poistotoimintojen aikana. Tämä on kategoriasta "sorkkarauta vastaan ​​ei ole temppuja".
  Tiedot osoitteesta keskusteluja pinonvaihdossa: kun virta katkaistaan ​​flash-työskentelyn aikana, sekä poisto (asetettu arvoon 1) että kirjoittaminen (asetettu 0:ksi) johtavat määrittelemättömään toimintaan: dataa voidaan kirjoittaa, osittain kirjoittaa (esimerkiksi siirsimme 10 tavua/80 bittiä , mutta vain 45 bittiä ei vielä voida kirjoittaa), on myös mahdollista, että osa biteistä on "välitilassa" (luku voi tuottaa sekä 0:n että 1:n);
• Virheet itse flash-muistissa.
  BER, vaikka se on hyvin alhainen, ei voi olla yhtä suuri kuin nolla;
• Bussivirheet
  SPI:n kautta lähetettyä dataa ei suojata millään tavalla; sekä yksittäisiä bittejä että synkronointivirheitä voi tapahtua - bittien menetys tai lisäys (joka johtaa massiiviseen tietojen vääristymiseen);
• Muita vikoja/virheitä
  Virheitä koodissa, Raspberry-häiriöitä, ulkomaalaisten häiriöitä...

Olen muotoillut vaatimukset, joiden täyttäminen on mielestäni välttämätöntä luotettavuuden varmistamiseksi:

• tietueiden on mentävä flash-muistiin välittömästi, viivästyneitä kirjoituksia ei huomioida - jos virhe ilmenee, se tulee havaita ja käsitellä mahdollisimman aikaisessa vaiheessa - järjestelmän tulee mahdollisuuksien mukaan toipua virheistä.
  (esimerkki elämästä "miten sen ei pitäisi olla", johon mielestäni kaikki ovat törmänneet: hätäuudelleenkäynnistyksen jälkeen tiedostojärjestelmä "rikki" ja käyttöjärjestelmä ei käynnisty)

Ideoita, lähestymistapoja, pohdintoja

Kun aloin miettimään tätä ongelmaa, päässäni välähti monia ideoita, mm.

• käyttää tietojen pakkausta;
• käytä älykkäitä tietorakenteita, esimerkiksi tallentamalla tietueiden otsikot erilleen itse tietueista, jotta jos jossakin tietueessa on virhe, voit lukea loput ilman ongelmia;
• käytä bittikenttiä tallennuksen valmistumisen ohjaamiseen, kun virta on katkaistu;
• tallentaa tarkistussummat kaikesta;
• käytä jonkinlaista melunkestävää koodausta.

Joitakin näistä ideoista käytettiin hyväksi, kun taas toisista päätettiin luopua. Mennään järjestyksessä.

Tietojen pakkaus

Itse päiväkirjaan tallentamamme tapahtumat ovat melko samankaltaisia ​​ja toistettavia ("heitti 5 ruplan kolikon", "painattiin vaihtorahanappia", ...). Siksi pakkaamisen pitäisi olla varsin tehokasta.

Kompressioteho on merkityksetön (prosessorimme on melko tehokas, jopa ensimmäisessä Pi:ssä oli yksi ydin 700 MHz:n taajuudella, nykyisissä malleissa on useita ydintä, joiden taajuus on yli gigahertsin), vaihtokurssi tallennustilan kanssa on alhainen (useita megatavua sekunnissa), tietueiden koko on pieni. Yleensä, jos pakkaus vaikuttaa suorituskykyyn, se on vain positiivista. (Täysin kritiikitön, totean vain). Lisäksi meillä ei ole todellista sulautettua, vaan tavallista Linuxia - joten toteutuksen ei pitäisi vaatia paljon vaivaa (riittää vain linkittää kirjasto ja käyttää useita toimintoja siitä).

Pala lokista otettiin toimivalta laitteelta (1.7 MB, 70 tuhatta merkintää) ja tarkistettiin ensin pakattavuus käyttämällä tietokoneessa olevia gzip, lz4, lzop, bzip2, xz, zstd.

• gzip, xz, zstd näyttivät samanlaisia ​​tuloksia (40 kt).
  Olin yllättynyt, että muodikas xz esiintyi täällä gzip- tai zstd-tasolla;
• lzip oletusasetuksilla antoi hieman huonompia tuloksia;
• lz4 ja lzop eivät osoittaneet kovin hyviä tuloksia (150Kb);
• bzip2 näytti yllättävän hyvää tulosta (18Kb).

Joten tiedot pakataan erittäin hyvin.
Joten (jos emme löydä kohtalokkaita puutteita) tapahtuu pakkaus! Yksinkertaisesti siksi, että samalle flash-asemalle mahtuu enemmän tietoa.

Mietitään haittoja.

Ensimmäinen ongelma: olemme jo sopineet, että jokaisen ennätyksen täytyy välittömästi alkaa vilkkua. Tyypillisesti arkistaattori kerää dataa syöttövirrasta, kunnes se päättää, että on aika kirjoittaa viikonloppuna. Meidän on välittömästi vastaanotettava pakattu tietolohko ja tallennettava se haihtumattomaan muistiin.

Näen kolme tapaa:

1. Pakkaa jokainen tietue käyttämällä sanakirjapakkausta edellä käsiteltyjen algoritmien sijaan.
   Se on täysin toimiva vaihtoehto, mutta en pidä siitä. Enemmän tai vähemmän kunnollisen pakkaustason varmistamiseksi sanakirja on "räätälöitävä" tiettyjen tietojen mukaan, mikä tahansa muutos johtaa pakkaustason katastrofaaliseen laskuun. Kyllä, ongelma voidaan ratkaista luomalla uusi versio sanakirjasta, mutta tämä on päänsärky - meidän on tallennettava kaikki sanakirjan versiot; jokaisessa merkinnässä meidän on ilmoitettava, millä sanakirjan versiolla se on pakattu...
2. Pakkaa jokainen tietue käyttämällä "klassisia" algoritmeja, mutta muista riippumatta.
   Tarkasteltavana olevia pakkausalgoritmeja ei ole suunniteltu toimimaan tämän kokoisten tietueiden kanssa (kymmeniä tavuja), pakkaussuhde on selvästi alle 1 (eli datamäärän lisääminen pakkaamisen sijaan);
3. Suorita FLUSH jokaisen tallennuksen jälkeen.
   Monissa pakkauskirjastoissa on FLUSH-tuki. Tämä on komento (tai pakkausprosessin parametri), jonka vastaanotettuaan arkistaattori muodostaa pakatun virran, jotta sitä voidaan käyttää palauttamiseen kaikki pakkaamattomia tietoja, jotka on jo vastaanotettu. Sellainen analogi sync tiedostojärjestelmissä tai commit sql:ssä.
   Tärkeää on, että myöhemmät pakkaustoiminnot voivat käyttää kertynyttä sanakirjaa eikä pakkaussuhde kärsi niin paljon kuin edellisessä versiossa.

Mielestäni on selvää, että valitsin kolmannen vaihtoehdon, katsotaanpa sitä tarkemmin.

Löytyi hieno artikkeli Tietoja FLUSHista zlibissä.

Tein polvitestin artikkelin perusteella, otin 70 tuhatta lokimerkintää oikealta laitteelta, sivun koko 60Kb (sivun kokoon palaamme myöhemmin) otettu vastaan:

Raakatiedot
Pakkaus gzip -9 (ei FLUSH)
zlib ja Z_PARTIAL_FLUSH
zlib Z_SYNC_FLUSH:lla

Volyymi, KB
1692
40
352
604

Ensi silmäyksellä FLUSHin tarjoama hinta on liian korkea, mutta todellisuudessa meillä ei ole juurikaan valinnanvaraa - joko olla pakkaamatta ollenkaan tai kompressoida (ja erittäin tehokkaasti) FLUSHilla. Emme saa unohtaa, että meillä on 70 tuhatta tietuetta, Z_PARTIAL_FLUSH:n tuoma redundanssi on vain 4-5 tavua per tietue. Ja pakkaussuhde osoittautui melkein 5:1, mikä on enemmän kuin erinomainen tulos.

Se voi tulla yllätyksenä, mutta Z_SYNC_FLUSH on itse asiassa tehokkaampi tapa tehdä FLUSH

Käytettäessä Z_SYNC_FLUSH:ta kunkin merkinnän viimeiset 4 tavua ovat aina 0x00, 0x00, 0xff, 0xff. Ja jos tunnemme ne, meidän ei tarvitse tallentaa niitä, joten lopullinen koko on vain 324 kt.

Artikkelissa, johon linkitin, on selitys:

Lisätään uusi tyypin 0 lohko, jonka sisältö on tyhjä.

Tyypin 0 lohko, jossa on tyhjä sisältö, koostuu:

• kolmibittinen lohkootsikko;
• 0 - 7 bittiä, joka vastaa nollaa tavujen tasauksen saavuttamiseksi;
• nelitavuinen sekvenssi 00 00 FF FF.

Kuten voit helposti nähdä, viimeisessä lohkossa ennen näitä 4 tavua on 3 - 10 nollabittiä. Käytäntö on kuitenkin osoittanut, että nollabittejä on itse asiassa vähintään 10.

Osoittautuu, että tällaiset lyhyet tietolohkot koodataan yleensä (aina?) käyttämällä tyypin 1 lohkoa (kiinteä lohko), joka välttämättä päättyy 7 nollabittiin, jolloin saadaan yhteensä 10-17 taattua nollabittiä (ja loput olla nolla noin 50 %:n todennäköisyydellä.

Joten testitiedoissa 100 %:ssa tapauksista on yksi nolla tavu ennen 0x00, 0x00, 0xff, 0xff ja yli kolmanneksessa tapauksista kaksi nollatavua (ehkä tosiasia on, että käytän binaarista CBOR:ia, ja teksti-JSON:ia käytettäessä tyypin 2 lohkot - dynaaminen lohko olisivat yleisempiä, vastaavasti kohdata lohkot ilman ylimääräisiä nollatavuja ennen 0x00, 0x00, 0xff, 0xff).

Kaiken kaikkiaan saatavilla olevaa testidataa käyttämällä on mahdollista mahtua alle 250 kb:n pakattuun dataan.

Voit säästää hieman enemmän tekemällä bittien jongleerausta: toistaiseksi jätämme huomiotta muutaman nollan läsnäolon lohkon lopussa, muutama bitti lohkon alussa ei myöskään muutu...
Mutta sitten tein vahvan tahdon päätöksen lopettaa, muuten tällä vauhdilla voisin päätyä kehittämään oman arkistaattorini.

Kaiken kaikkiaan testitiedoistani sain 3-4 tavua kirjoitusta kohti, pakkaussuhde osoittautui yli 6:1. Olen rehellinen: en odottanut tällaista tulosta, mielestäni mikä tahansa parempi kuin 2:1 on jo tulos, joka oikeuttaa kompression käytön.

Kaikki on hyvin, mutta zlib (deflate) on edelleen arkaainen, ansaittu ja hieman vanhanaikainen pakkausalgoritmi. Pelkästään se tosiasia, että pakkaamattoman tietovirran viimeiset 32 ​​kb käytetään sanakirjana, näyttää tänään oudolta (eli jos jokin tietolohko on hyvin samankaltainen kuin syöttövirrassa 40 kt sitten, sitä aletaan arkistoida uudelleen, eikä viittaa aikaisempaan tapahtumaan). Muodikkaissa nykyaikaisissa arkistoissa sanakirjan koko mitataan usein megatavuina kilotavujen sijaan.

Jatkamme siis arkistoijien minitutkimusta.

Seuraavaksi testasimme bzip2:ta (muista, että ilman FLUSHia se osoitti fantastisen pakkaussuhteen melkein 100:1). Valitettavasti se toimi erittäin huonosti FLUSH:n kanssa; pakatun tiedon koko osoittautui suuremmiksi kuin pakkaamaton data.

Omat oletukseni epäonnistumisen syistä

Libbz2 tarjoaa vain yhden huuhteluvaihtoehdon, joka näyttää tyhjentävän sanakirjan (analogisesti Z_FULL_FLUSH:ssa zlibissä); tehokkaasta pakkaamisesta ei ole tämän jälkeen puhetta.

Ja viimeinen testattava oli zstd. Parametreista riippuen se pakkaa joko gzip-tasolla, mutta paljon nopeammin tai paremmin kuin gzip.

Valitettavasti FLUSHilla se ei toiminut kovin hyvin: pakatun tiedon koko oli noin 700 kb.

Я kysyi kysymyksen projektin github-sivulla sain vastauksen, että jokaista pakattua datalohkoa kohden pitäisi laskea jopa 10 tavua palveludataa, mikä on lähellä saatuja tuloksia; deflatointia ei voi saada kiinni.

Päätin lopettaa tähän kohtaan arkistointikokeiluni (muistutan, että xz, lzip, lzo, lz4 eivät näyttäneet itseään edes testausvaiheessa ilman FLUSHia, enkä ajatellut eksoottisempia pakkausalgoritmeja).

Palataan arkistointiongelmiin.

Toinen (kuten sanotaan järjestyksessä, ei arvoltaan) ongelma on, että pakattu data on yksittäinen virta, jossa on jatkuvasti viittauksia aikaisempiin osioihin. Näin ollen, jos osa pakatusta tiedosta vaurioituu, menetämme paitsi siihen liittyvän pakkaamattoman datalohkon, myös kaikki myöhemmät.

On olemassa lähestymistapa tämän ongelman ratkaisemiseksi:

1. Estä ongelman esiintyminen - lisää pakattuun tietoon redundanssia, jonka avulla voit tunnistaa ja korjata virheet; puhumme tästä myöhemmin;
2. Minimoi seuraukset, jos ongelma ilmenee
   Olemme jo aiemmin sanoneet, että voit pakata jokaisen tietolohkon itsenäisesti, ja ongelma poistuu itsestään (yhden lohkon tietojen vaurioituminen johtaa vain tämän lohkon tietojen katoamiseen). Tämä on kuitenkin äärimmäinen tapaus, jossa tietojen pakkaus on tehoton. Päinvastainen ääripää: käytä kaikki 4 Mt sirumme yhtenä arkistona, mikä antaa meille erinomaisen pakkauksen, mutta tuhoisat seuraukset tietojen vioittumisen tapauksessa.
   Kyllä, luotettavuuden suhteen tarvitaan kompromissi. Mutta meidän on muistettava, että kehitämme tietojen tallennusmuotoa haihtumattomalle muistille, jolla on erittäin alhainen BER ja ilmoitettu tietojen tallennusaika 20 vuotta.

Kokeiden aikana huomasin, että enemmän tai vähemmän havaittavissa olevat pakkaustason häviöt alkavat alle 10 kt:n kokoisista pakatun datan lohkoista.
Aiemmin mainittiin, että käytetty muisti on sivuttu, enkä näe mitään syytä, miksi "yksi sivu - yksi lohko pakattua dataa" -vastaavuutta ei tulisi käyttää.

Toisin sanoen pienin kohtuullinen sivukoko on 16 kt (palvelutietojen varauksella). Tällainen pieni sivukoko asettaa kuitenkin merkittäviä rajoituksia tietueen enimmäiskoolle.

Vaikka en vielä odota muutaman kilotavun suuruisia tietueita pakatussa muodossa, päätin käyttää 32 kt:n sivuja (yhteensä 128 sivua per siru).

Yhteenveto:

• Tallennamme tiedot pakattuna käyttämällä zlib (deflate);
• Jokaiselle merkinnälle asetamme Z_SYNC_FLUSH;
• Leikkaamme jokaisen pakatun tietueen lopussa olevat tavut (esim. 0x00, 0x00, 0xff, 0xff); otsikossa ilmoitamme kuinka monta tavua katkaisimme;
• Tallennamme tiedot 32 kb:n sivuille; sivulla on yksi pakatun tiedon virta; Jokaisella sivulla aloitamme pakkaamisen uudelleen.

Ja ennen kuin lopetan pakkaamisen, haluaisin kiinnittää huomionne siihen, että meillä on vain muutama tavu pakattua dataa tietueita kohti, joten on erittäin tärkeää, että palvelutietoja ei liioiteta, sillä jokainen tavu on tärkeä.

Tietojen otsikoiden tallentaminen

Koska meillä on vaihtelevan pituisia tietueita, meidän on jotenkin määritettävä tietueiden sijainti/rajat.

Tiedän kolme lähestymistapaa:

1. Kaikki tietueet tallennetaan jatkuvana virtana, ensin on tietueen otsikko, joka sisältää pituuden, ja sitten itse tietue.
   Tässä suoritusmuodossa sekä otsikot että tiedot voivat olla vaihtelevan pituisia.
   Pohjimmiltaan saamme yksitellen linkitetyn luettelon, jota käytetään jatkuvasti;
2. Otsikot ja itse tietueet tallennetaan erillisiin virtoihin.
   Käyttämällä vakiopituisia otsikoita varmistamme, että yhden otsikon vaurioituminen ei vaikuta muihin.
   Samanlaista lähestymistapaa käytetään esimerkiksi monissa tiedostojärjestelmissä;
3. Tietueet tallennetaan jatkuvana virtana, tietueen rajan määrittää tietty merkki (merkki/merkkijono, joka on kielletty tietolohkoissa). Jos tietueen sisällä on merkki, korvaamme sen jollain sekvenssillä (escap it).
   Samanlaista lähestymistapaa käytetään esimerkiksi PPP-protokollassa.

Havainnollistan.

Vaihtoehto 1:

Kaikki on täällä hyvin yksinkertaista: tietueen pituuden avulla voimme laskea seuraavan otsikon osoitteen. Joten siirrymme otsikoiden läpi, kunnes kohtaamme alueen, joka on täynnä 0xff (vapaa alue) tai sivun loppuun.

Vaihtoehto 2:

Muuttuvan tietueen pituuden vuoksi emme voi sanoa etukäteen, kuinka monta tietuetta (ja siten otsikoita) tarvitsemme sivua kohden. Voit jakaa otsikot ja itse tiedot eri sivuille, mutta pidän parempana erilaista lähestymistapaa: asetamme sekä otsikot että tiedot yhdelle sivulle, mutta (vakiokokoiset) otsikot tulevat sivun alusta, ja tiedot (muuttuvan pituiset) tulevat lopusta. Heti kun he "tapaavat" (uudelleen merkinnälle ei ole tarpeeksi vapaata tilaa), katsomme tämän sivun valmiiksi.

Vaihtoehto 3:

Otsikkoon ei tarvitse tallentaa pituutta tai muuta tietoa tietojen sijainnista, vaan tietueiden rajat osoittavat merkit riittävät. Tietoja on kuitenkin käsiteltävä kirjoitettaessa/luettaessa.
Käyttäisin 0xff-merkkiä (joka täyttää sivun poistamisen jälkeen), joten vapaata aluetta ei varmasti käsitellä datana.

Vertailu Taulukko:

Vaihtoehto 1
Vaihtoehto 2
Vaihtoehto 3

Virheiden sietokyky
-
+
+

tiheys
+
-
+

Toteutuksen monimutkaisuus
*
**
**

Vaihtoehdossa 1 on kohtalokas virhe: jos jokin otsikoista vaurioituu, koko seuraava ketju tuhoutuu. Jäljellä olevat vaihtoehdot mahdollistavat joidenkin tietojen palauttamisen jopa massiivisten vaurioiden sattuessa.
Mutta tässä on hyvä muistaa, että päätimme tallentaa tiedot pakatussa muodossa, joten menetämme kaikki sivun tiedot "rikkoutuneen" tietueen jälkeen, joten vaikka taulukossa on miinus, emme tee sitä. ota se huomioon.

Kompakti:

• ensimmäisessä vaihtoehdossa meidän täytyy tallentaa vain pituus otsikkoon; jos käytämme muuttuvan pituisia kokonaislukuja, niin useimmissa tapauksissa pärjäämme yhdellä tavulla;
• toisessa vaihtoehdossa meidän on tallennettava aloitusosoite ja pituus; tietueen on oltava vakiokokoinen, arvioin 4 tavua per tietue (kaksi tavua offsetille ja kaksi tavua pituudelle);
• Kolmas vaihtoehto tarvitsee vain yhden merkin osoittamaan tallennuksen alkamista, ja itse tallennus kasvaa 1-2% suojauksen vuoksi. Yleensä suunnilleen pariteetti ensimmäisen vaihtoehdon kanssa.

Aluksi pidin toista vaihtoehtoa tärkeimpänä (ja jopa kirjoitin toteutuksen). Lopetin sen vasta, kun lopulta päätin käyttää pakkausta.

Ehkä vielä joskus käytän samanlaista vaihtoehtoa. Esimerkiksi, jos joudun käsittelemään Maan ja Marsin välillä matkustavan laivan datan tallennusta, niin luotettavuudelle, kosmiselle säteilylle, ...

Mitä tulee kolmanteen vaihtoehtoon: Annoin sille kaksi tähteä toteutuksen vaikeudesta yksinkertaisesti siksi, että en pidä sotkemisesta suojauksen kanssa, pituuden muuttamisesta prosessin aikana jne. Kyllä, ehkä olen puolueellinen, mutta minun on kirjoitettava koodi - miksi pakottaa itsesi tekemään jotain, josta et pidä.

Yhteenveto: Valitsemme tallennusvaihtoehdon ketjujen muodossa "pituinen otsikko - muuttuvapituiset tiedot" tehokkuuden ja toteutuksen helppouden vuoksi.

Bittikenttien käyttäminen kirjoitustoimintojen onnistumisen seuraamiseen

En nyt muista mistä idean sain, mutta se näyttää suunnilleen tältä:
Jokaiselle merkinnälle varaamme useita bittejä lippujen tallentamiseen.
Kuten aiemmin sanoimme, tyhjennyksen jälkeen kaikki bitit täytetään ykkösillä, ja voimme muuttaa 1:n nollaan, mutta ei päinvastoin. Joten "lippua ei ole asetettu" varten käytämme 1, "lippu on asetettu" käytämme 0.

Vaihtuvanpituisen tietueen asettaminen flashiin saattaa näyttää tältä:

1. Aseta lippu "pituuden tallennus on alkanut";
2. Kirjaa pituus;
3. Aseta "tietojen tallennus on alkanut" -lippu;
4. Tallennamme tietoja;
5. Aseta "nauhoitus päättynyt" -lippu.

Lisäksi meillä on "virhe tapahtui" -lippu, yhteensä 4 bitin lippua.

Tässä tapauksessa meillä on kaksi vakaata tilaa "1111" - tallennus ei ole alkanut ja "1000" - tallennus onnistui; Tallennusprosessin odottamattoman keskeytyksen sattuessa saamme välitiloja, jotka voimme sitten havaita ja käsitellä.

Lähestymistapa on mielenkiintoinen, mutta se suojaa vain äkillisiltä sähkökatkoilta ja vastaavilta häiriöiltä, ​​mikä on tietysti tärkeää, mutta tämä ei ole kaukana ainoa (tai jopa tärkein) syy mahdollisille epäonnistumisille.

Yhteenveto: Jatketaan hyvää ratkaisua etsimässä.

Tarkistussummat

Tarkistussummat mahdollistavat myös (kohtuullisella todennäköisyydellä) varmistuksen, että luemme juuri sen, mitä olisi pitänyt kirjoittaa. Ja toisin kuin yllä mainitut bittikentät, ne toimivat aina.

Jos otamme huomioon luettelon mahdollisista ongelmalähteistä, joista keskustelimme yllä, tarkistussumma pystyy tunnistamaan virheen sen alkuperästä riippumatta (paitsi ehkä pahantahtoiset muukalaiset - he voivat myös väärentää tarkistussumman).

Joten jos tavoitteenamme on varmistaa, että tiedot ovat ehjät, tarkistussummat ovat hyvä idea.

Algoritmin valinta tarkistussumman laskemiseksi ei herättänyt kysymyksiä - CRC. Toisaalta matemaattiset ominaisuudet mahdollistavat tietyntyyppisten virheiden havaitsemisen 100 %:sti, toisaalta satunnaisessa datassa tämä algoritmi yleensä näyttää törmäystodennäköisyyden, joka ei ole paljon suurempi kuin teoreettinen raja . Se ei ehkä ole nopein algoritmi, eikä se ole aina minimi törmäysten lukumäärän suhteen, mutta sillä on erittäin tärkeä ominaisuus: kohtaamissani testeissä ei ollut kaavoja, joissa se olisi selvästi epäonnistunut. Vakaus on tärkein ominaisuus tässä tapauksessa.

Esimerkki tilavuustutkimuksesta: osa 1, osa 2 (linkit osoitteeseen narod.ru, anteeksi).

Tarkistussumman valintatehtävä ei kuitenkaan ole valmis, CRC on koko joukko tarkistussummia. Sinun on päätettävä pituus ja valittava sitten polynomi.

Tarkistussumman pituuden valitseminen ei ole niin yksinkertainen kysymys kuin miltä ensi silmäyksellä näyttää.

Havainnollistan:
Otetaan virheen todennäköisyys jokaisessa tavussa ja ihanteellinen tarkistussumma, lasketaan keskimääräinen virheiden määrä miljoonaa tietuetta kohden:

Data, tavu
Tarkistussumma, tavu
Havaitsemattomia virheitä
Väärät virheiden havainnot
Vääriä positiivisia tuloksia yhteensä

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

Vaikuttaa siltä, ​​​​että kaikki on yksinkertaista - suojattavien tietojen pituudesta riippuen valitse tarkistussumman pituus vähintään virheellisillä positiivisilla - ja temppu on pussissa.

Lyhyillä tarkistussummilla on kuitenkin ongelma: vaikka ne ovat hyviä havaitsemaan yksibittisiä virheitä, ne voivat melko suurella todennäköisyydellä hyväksyä täysin satunnaisen tiedon oikeaksi. Habrésta oli jo artikkeli, jossa kuvattiin ongelma oikeassa elämässä.

Siksi, jotta satunnainen tarkistussumma vastaa lähes mahdotonta, sinun on käytettävä 32 bitin pituisia tai pidempiä tarkistussummia. (yli 64 bitin pituuksissa käytetään yleensä kryptografisia hajautusfunktioita).

Huolimatta siitä, että kirjoitin aiemmin, että tilaa täytyy säästää kaikin keinoin, käytämme silti 32-bittistä tarkistussummaa (16 bittiä ei riitä, törmäyksen todennäköisyys on yli 0.01 %; ja 24 bittiä, koska ne sano, eivät ole täällä eikä siellä).

Tästä voi syntyä vastalause: tallensimmeko jokaisen tavun pakkauksen valinnassa, jotta saisimme nyt 4 tavua kerralla? Eikö olisi parempi olla pakkaamatta tai lisäämättä tarkistussummaa? Ei tietenkään, ei pakkausta ei tarkoita, että emme tarvitse eheyden tarkistusta.

Polynomia valittaessa emme keksi pyörää uudelleen, vaan otamme nyt suositun CRC-32C:n.
Tämä koodi havaitsee 6 bitin virheet 22 tavun paketeissa (ehkä yleisin tapaus meille), 4 bitin virheitä 655 tavun paketeissa (myös yleinen tapaus meille), 2 tai minkä tahansa parittoman määrän bittivirheitä paketeissa minkä tahansa kohtuullisen pituuden.

Jos jotakuta kiinnostaa yksityiskohdat

Wikipedian artikkeli CRC:stä.

Koodiparametrit crc-32c päälle Koopmanin verkkosivuilla — ehkä planeetan johtava CRC-asiantuntija.

В hänen artikkelinsa on toinen mielenkiintoinen koodi, joka tarjoaa hieman paremmat parametrit meille oleville pakettien pituuksille, mutta en pitänyt eroa merkittävänä, ja olin tarpeeksi pätevä valitsemaan mukautetun koodin standardin ja hyvin tutkitun koodin sijaan.

Lisäksi, koska tietomme on pakattu, herää kysymys: pitäisikö meidän laskea pakattujen vai pakkaamattomien tietojen tarkistussumma?

Argumentit pakkaamattomien tietojen tarkistussumman laskemisen puolesta:

• Meidän on viime kädessä tarkistettava tietojen tallennuksen turvallisuus - joten tarkistamme sen suoraan (samalla tarkistetaan mahdolliset virheet pakkauksen/dekompression toteutuksessa, rikkinäisen muistin aiheuttamat vauriot jne.);
• Zlibin deflate-algoritmilla on melko kypsä toteutus ja ei pitäisi putoaa "väärillä" syöttötiedoilla; lisäksi se pystyy usein havaitsemaan virheet tulovirrassa, mikä vähentää virheen havaitsematta jättämisen yleistä todennäköisyyttä (suoritettu testi invertoimalla yhden bitin lyhyessä tietueessa, zlib havaitsi virheen noin kolmanneksessa tapauksista).

Argumentit pakkaamattomien tietojen tarkistussumman laskemista vastaan:

• CRC on "räätälöity" erityisesti niitä harvoja bittivirheitä varten, jotka ovat ominaisia ​​flash-muistille (bittivirhe pakatussa virrassa voi aiheuttaa massiivisen muutoksen lähtövirrassa, jossa puhtaasti teoreettisesti voimme "saapua" törmäyksen);
• En todellakaan pidä ajatuksesta siirtää mahdollisesti rikkinäisiä tietoja dekompressoriin, Kuka tietäämiten hän reagoi.

Tässä projektissa päätin poiketa yleisesti hyväksytystä käytännöstä tallentaa pakkaamattoman datan tarkistussumma.

Yhteenveto: Käytämme CRC-32C:tä, laskemme tarkistussumman tiedoista siinä muodossa, jossa ne on kirjoitettu flashiksi (pakkauksen jälkeen).

Redundanssi

Redundantin koodauksen käyttö ei tietenkään eliminoi tietojen häviämistä, mutta se voi merkittävästi (usein useiden suuruusluokkien) vähentää peruuttamattoman tiedon menetyksen todennäköisyyttä.

Voimme käyttää erilaisia ​​redundanssityyppejä virheiden korjaamiseen.
Hamming-koodit voivat korjata yksibittiset virheet, Reed-Solomon-merkkikoodit, useat datakopiot yhdistettyinä tarkistussummiin tai RAID-6:n kaltaiset koodaukset voivat auttaa tietojen palauttamisessa jopa massiivisessa korruptiossa.
Aluksi olin sitoutunut virheenkestävän koodauksen laajaan käyttöön, mutta sitten tajusin, että meidän on ensin saatava käsitys siitä, miltä virheiltä haluamme suojautua, ja sitten valita koodaus.

Sanoimme aiemmin, että virheet on löydettävä mahdollisimman nopeasti. Missä kohdissa voimme kohdata virheitä?

1. Keskeneräinen tallennus (jostain syystä äänityshetkellä virta katkaistiin, Raspberry jumiutui, ...)
   Valitettavasti tällaisen virheen sattuessa ei tarvitse muuta kuin jättää huomioimatta virheelliset tietueet ja harkita tietojen katoamista;
2. Kirjoitusvirheet (jostain syystä flash-muistiin kirjoitettu ei ollut sitä, mitä kirjoitettiin)
   Voimme havaita tällaiset virheet välittömästi, jos teemme testilukeman välittömästi tallennuksen jälkeen;
3. Muistissa olevien tietojen vääristyminen tallennuksen aikana;
4. Lukuvirheet
   Sen korjaamiseksi, jos tarkistussumma ei täsmää, riittää toistaa lukema useita kertoja.

Toisin sanoen vain kolmannen tyyppisiä virheitä (tietojen spontaani vioittuminen tallennuksen aikana) ei voida korjata ilman virheenkestävää koodausta. Vaikuttaa siltä, ​​että tällaiset virheet ovat edelleen erittäin epätodennäköisiä.

Yhteenveto: redundantista koodauksesta päätettiin luopua, mutta jos toiminta osoittaa tämän päätöksen virheen, palaa asian pohtimiseen (jo kertyneillä virhetilastoilla, jotka mahdollistavat optimaalisen koodaustyypin valitsemisen).

Muut

Artikkelin muoto ei tietenkään salli meidän perustella jokaista muotoa (ja voimani ovat jo loppuneet), joten käyn lyhyesti läpi joitakin kohtia, joita ei ole käsitelty aiemmin.

• Päätettiin tehdä kaikista sivuista "tasa-arvoisia"
  Eli ei tule erikoissivuja, joissa on metatietoja, erillisiä säikeitä jne., vaan yksi säie, joka kirjoittaa kaikki sivut vuorotellen uudelleen.
  Tämä varmistaa tasaisen kulumisen sivuille, ei yhtä vikakohtaa, ja pidän siitä;
• On välttämätöntä tarjota muodon versiointi.
  Muoto ilman versionumeroa otsikossa on paha!
  Riittää, kun lisäät sivun otsikkoon kentän tietyllä maagisella numerolla (allekirjoitus), joka ilmaisee käytetyn muodon version (En usko, että käytännössä niitä tulee olemaan tusinaakaan);
• Käytä tietueille (joita on paljon) vaihtuvapituista otsikkoa, yritä tehdä siitä useimmissa tapauksissa 1 tavu pitkä;
• Jos haluat koodata pakatun tietueen otsikon pituuden ja leikatun osan pituuden, käytä muuttuvapituisia binäärikoodeja.

Auttoi paljon online-generaattori Huffman koodit. Vain muutamassa minuutissa pystyimme valitsemaan tarvittavat muuttuvapituiset koodit.

Tietojen tallennusmuodon kuvaus

Tavujärjestys

Tavua suuremmat kentät tallennetaan big-endian-muodossa (verkkotavujärjestys), eli 0x1234 kirjoitetaan muodossa 0x12, 0x34.

Sivunumerointi

Kaikki flash-muisti on jaettu samankokoisiin sivuihin.

Sivun oletuskoko on 32 kt, mutta enintään 1/4 muistisirun kokonaiskoosta (4 Mt:n sirulla saadaan 128 sivua).

Jokainen sivu tallentaa tiedot muista riippumatta (eli yhden sivun tiedot eivät viittaa toisen sivun tietoihin).

Kaikki sivut on numeroitu luonnollisessa järjestyksessä (osoitteiden nousevassa järjestyksessä), alkaen numerosta 0 (sivu nolla alkaa osoitteesta 0, ensimmäinen sivu alkaa 32 kt, toinen sivu alkaa 64 kt jne.)

Muistisirua käytetään syklisenä puskurina (rengaspuskurina), eli ensin kirjoitetaan sivulle 0, sitten numero 1, ..., kun viimeinen sivu täytetään, alkaa uusi sykli ja tallennus jatkuu sivulta nolla. .

Sivun sisällä

Sivun alkuun tallennetaan 4-tavuinen sivuotsikko, sitten otsikon tarkistussumma (CRC-32C), sitten tietueet tallennetaan "header, data, checksum" -muodossa.

Sivun otsikko (kaaviossa likaisenvihreä) koostuu:

• kaksitavuinen Magic Number -kenttä (myös muotoversion merkki)
  muodon nykyiselle versiolle se lasketaan seuraavasti 0xed00 ⊕ номер страницы;
• kaksitavuinen laskuri "Sivun versio" (muistin uudelleenkirjoitusjakson numero).

Sivun merkinnät tallennetaan pakatussa muodossa (käytetään deflate-algoritmia). Kaikki yhdellä sivulla olevat tietueet pakataan yhteen säikeeseen (käytetään yleistä sanakirjaa), ja jokaisella uudella sivulla pakkaus alkaa alusta. Toisin sanoen minkä tahansa tietueen purkamiseen vaaditaan kaikki tämän sivun aiemmat tietueet (ja vain tämä yksi).

Jokainen tietue pakataan Z_SYNC_FLUSH-lipulla, ja pakatun virran lopussa on 4 tavua 0x00, 0x00, 0xff, 0xff, joita edeltää mahdollisesti yksi tai kaksi nollatavua lisää.
Hylkäämme tämän sekvenssin (4, 5 tai 6 tavua pitkä) kirjoitettaessa flash-muistiin.

Tietueen otsikko on 1, 2 tai 3 tavua, joka tallentaa:

• yksi bitti (T), joka ilmaisee tietueen tyypin: 0 - konteksti, 1 - log;
• muuttuvapituinen kenttä (S) 1 - 7 bittiä, joka määrittää otsikon pituuden ja "häntä", joka on lisättävä tietueeseen pakkauksen purkamista varten;
• ennätyspituus (L).

S-arvotaulukko:

S
Otsikon pituus, tavua
Hylätty kirjoitusvaiheessa, tavu

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)

Yritin havainnollistaa, en tiedä kuinka selkeästi se osoittautui:

Keltainen tarkoittaa tässä T-kenttää, valkoinen S-kenttää, vihreä L (pakatun tiedon pituus tavuina), sininen pakattua dataa, punainen pakatun datan viimeisiä tavuja, joita ei kirjoiteta flash-muistiin.

Näin ollen voimme kirjoittaa yleisimmän pituisia tietueotsikoita (jopa 63+5 tavua pakatussa muodossa) yhteen tavuun.

Jokaisen tietueen jälkeen tallennetaan CRC-32C-tarkistussumma, jossa alkuarvona (init) käytetään edellisen tarkistussumman käänteistä arvoa.

CRC:llä on ominaisuus "kesto", seuraava kaava toimii (plus tai miinus bitin käännös prosessissa): .
Toisin sanoen laskemme tämän sivun kaikkien aiempien otsikoiden ja tietojen CRC:n.

Suoraan tarkistussumman jälkeen on seuraavan tietueen otsikko.

Otsikko on suunniteltu siten, että sen ensimmäinen tavu on aina erilainen kuin 0x00 ja 0xff (jos otsikon ensimmäisen tavun sijasta kohtaamme 0xff, tämä tarkoittaa, että tämä on käyttämätön alue; 0x00 ilmoittaa virheestä).

Esimerkkialgoritmit

Lukeminen Flash-muistista

Kaikkien lukemien mukana tulee tarkistussumman tarkistus.
Jos tarkistussumma ei täsmää, lukeminen toistetaan useita kertoja toivoen, että oikeat tiedot luetaan.

(Tämä on järkevää, Linux ei tallenna NOR Flashin lukuja välimuistiin, testattu)

Kirjoita flash-muistiin

Tallennamme tiedot.
Luemme ne.

Jos luetut tiedot eivät vastaa kirjoitettua dataa, täytämme alueen nolilla ja ilmoitamme virheestä.

Uuden mikropiirin valmistelu käyttöön

Alustamista varten otsikko, jonka versio on 1, kirjoitetaan ensimmäiselle (tai pikemminkin nollalle) sivulle.
Tämän jälkeen alkukonteksti kirjoitetaan tälle sivulle (sisältää koneen UUID:n ja oletusasetukset).

Siinä kaikki, flash-muisti on käyttövalmis.

Koneen lataus

Ladattaessa jokaisen sivun (otsikko + CRC) ensimmäiset 8 tavua luetaan, sivut, joilla on tuntematon maaginen numero tai virheellinen CRC ohitetaan.
"Oikeilta" sivuilta valitaan sivut, joilla on suurin versio, ja niistä otetaan sivu, jolla on suurin numero.
Ensimmäinen tietue luetaan, CRC:n oikeellisuus ja "konteksti"-lipun olemassaolo tarkistetaan. Jos kaikki on kunnossa, tätä sivua pidetään ajan tasalla. Jos ei, palaamme edelliseen, kunnes löydämme "live-sivun".
ja löydetyltä sivulta luemme kaikki tietueet, ne, joita käytämme "konteksti"-lipulla.
Tallenna zlib-sanakirja (sitä tarvitaan tälle sivulle lisäämiseen).

Siinä kaikki, lataus on valmis, konteksti on palautettu, voit työskennellä.

Päiväkirjamerkinnän lisääminen

Pakkaamme tietueen oikealla sanakirjalla määrittämällä Z_SYNC_FLUSH. Katsomme mahtuuko pakattu tietue nykyiselle sivulle.
Jos se ei sovi (tai sivulla oli CRC-virheitä), aloita uusi sivu (katso alla).
Kirjoitamme muistiin ja CRC:n. Jos tapahtuu virhe, aloita uusi sivu.

Uusi sivu

Valitsemme ilmaisen sivun, jolla on vähimmäismäärä (ilmaiseksi sivuksi katsomme sivun, jonka otsikossa on virheellinen tarkistussumma tai jonka versio on nykyistä pienempi). Jos tällaisia ​​sivuja ei ole, valitse sivu, jolla on pienin määrä sivuja, joiden versio on sama kuin nykyinen.
Poistamme valitun sivun. Tarkistamme sisällön 0xff:lla. Jos jokin on vialla, siirry seuraavalle ilmaiselle sivulle jne.
Kirjoitamme poistetulle sivulle otsikon, ensimmäinen merkintä on kontekstin nykyinen tila, seuraava on kirjoittamaton lokimerkintä (jos sellainen on).

Muotoilun soveltuvuus

Mielestäni se osoittautui hyväksi muodoksi enemmän tai vähemmän pakattavien tietovirtojen (plain text, JSON, MessagePack, CBOR, mahdollisesti protobuf) tallentamiseen NOR Flashiin.

Tietenkin muoto on "räätälöity" SLC NOR Flashille.

Sitä ei tule käyttää korkean BER-väliaineen, kuten NAND tai MLC NOR, kanssa (onko tällaista muistia edes myynnissä? Olen nähnyt sen mainittavan vain korjauskoodeja koskevissa teoksissa).

Sitä ei myöskään saa käyttää laitteissa, joissa on oma FTL: USB-flash, SD, MicroSD jne (tällaiselle muistille loin muodon, jonka sivukoko on 512 tavua, allekirjoitus jokaisen sivun alussa ja yksilölliset tietuenumerot - joskus oli mahdollista palauttaa kaikki tiedot "häiriöiseltä" flash-asemalta yksinkertaisella peräkkäisellä lukemalla).

Tehtävistä riippuen muotoa voidaan käyttää ilman muutoksia flash-asemilla 128Kbit (16Kb) - 1Gbit (128MB). Voit halutessasi käyttää sitä suuremmilla siruilla, mutta sinun on todennäköisesti säädettävä sivun kokoa (Mutta tässä herää jo kysymys taloudellisesta toteutettavuudesta; suuren volyymin NOR Flashin hinta ei ole rohkaiseva).

Jos joku pitää formaattia kiinnostavana ja haluaa käyttää sitä avoimessa projektissa, kirjoita, yritän löytää ajan, hioa koodia ja laittaa sen githubiin.

Johtopäätös

Kuten näette, muoto osoittautui lopulta yksinkertaiseksi ja jopa tylsää.

On vaikea heijastaa näkemykseni kehitystä artikkelissa, mutta uskokaa minua: alunperin halusin luoda jotain hienostunutta, tuhoutumatonta, joka pystyy selviytymään jopa ydinräjähdyksestä lähietäisyydellä. Järki (toivottavasti) kuitenkin voitti ja painopisteet siirtyivät vähitellen kohti yksinkertaisuutta ja kompaktisuutta.

Voisiko olla, että olin väärässä? Toki. Voi hyvinkin käydä niin, että ostimme erän huonolaatuisia mikropiirejä. Tai jostain muusta syystä laite ei täytä luotettavuusodotuksia.

Onko minulla suunnitelmaa tälle? Luulen, että artikkelin lukemisen jälkeen sinulla ei ole epäilystäkään suunnitelman olemassaolosta. Eikä edes yksin.

Hieman vakavammin sanottuna formaattia kehitettiin sekä toimivaksi vaihtoehdoksi että "koeilmapalloksi".

Tällä hetkellä kaikki pöydällä oleva toimii hyvin, kirjaimellisesti toissapäivänä ratkaisu otetaan käyttöön (suunnilleen) sadoilla laitteilla, katsotaan mitä tapahtuu "taistelussa" (onneksi toivon, että muoto mahdollistaa virheiden havaitsemisen luotettavasti, jotta voit kerätä täydelliset tilastot). Muutaman kuukauden päästä on mahdollista tehdä johtopäätöksiä (ja jos olet epäonninen, jopa aikaisemmin).

Jos käytön tulosten perusteella havaitaan vakavia ongelmia ja parannuksia tarvitaan, kirjoitan siitä ehdottomasti.

Kirjallisuus

En halunnut tehdä pitkää tylsää listaa käytetyistä teoksista, sillä jokaisella on Google.

Päätin jättää tänne listan löydöistä, jotka vaikuttivat minusta erityisen mielenkiintoisilta, mutta vähitellen ne siirtyivät suoraan artikkelin tekstiin, ja listalle jäi yksi kohde:

1. Apuohjelma infgen kirjoittajalta zlib. Voi näyttää selkeästi deflate/zlib/gzip-arkistojen sisällön. Jos joudut käsittelemään deflate (tai gzip) -muodon sisäistä rakennetta, suosittelen sitä.

Lähde: will.com