prehistorie

Er zijn automaten van ons eigen ontwerp. Binnenin de Raspberry Pi en wat bedrading op een apart bord. Een muntacceptor, een bankbiljetacceptor, een bankterminal zijn aangesloten... Alles wordt aangestuurd door een zelfgeschreven programma. De volledige werkgeschiedenis wordt naar een logboek op een flashstation (MicroSD) geschreven, dat vervolgens via internet (met behulp van een USB-modem) naar de server wordt verzonden en daar in een database wordt opgeslagen. Verkoopinformatie wordt in 1c geladen, ook is er een eenvoudige webinterface voor monitoring etc.

Dat wil zeggen, het dagboek is van vitaal belang - voor de boekhouding (inkomsten, verkopen, enz.), Monitoring (allerlei mislukkingen en andere overmachtsomstandigheden); Je zou kunnen zeggen dat dit alle informatie is die we over deze machine hebben.

probleem

Flashdrives blijken zeer onbetrouwbare apparaten te zijn. Ze falen met benijdenswaardige regelmaat. Dit leidt tot stilstand van de machine en (als het logboek om de een of andere reden niet online kan worden overgedragen) tot gegevensverlies.

Dit is niet de eerste ervaring met het gebruik van flashdrives, daarvoor was er nog een project met meer dan honderd apparaten, waarbij het tijdschrift werd opgeslagen op USB-flashdrives, er waren ook problemen met de betrouwbaarheid, soms was het aantal dat faalde een maand was in de tientallen. We hebben verschillende flashdrives geprobeerd, waaronder merkversies met SLC-geheugen, en sommige modellen zijn betrouwbaarder dan andere, maar het vervangen van flashdrives heeft het probleem niet radicaal opgelost.

Waarschuwing! Lang lezen! Als je niet geïnteresseerd bent in ‘waarom’, maar alleen in ‘hoe’, kun je meteen doorgaan Uiteindelijk artikelen.

beslissing

Het eerste dat in je opkomt is: verlaat MicroSD, installeer bijvoorbeeld een SSD en start ervan op. Theoretisch mogelijk waarschijnlijk, maar relatief duur en niet zo betrouwbaar (er is een USB-SATA-adapter toegevoegd; storingsstatistieken voor budget-SSD's zijn ook niet bemoedigend).

USB HDD lijkt ook geen bijzonder aantrekkelijke oplossing.

Daarom kwamen we tot deze optie: laat het opstarten vanaf MicroSD staan, maar gebruik ze in de alleen-lezen-modus, en sla het bedieningslogboek (en andere informatie die uniek is voor een bepaald stuk hardware - serienummer, sensorkalibraties, enz.) ergens anders op. .

Het onderwerp alleen-lezen FS voor frambozen is al van binnen en van buiten bestudeerd, ik zal in dit artikel niet ingaan op implementatiedetails (maar als er interesse is, schrijf ik misschien een mini-artikel over dit onderwerp). Het enige punt dat ik zou willen opmerken is dat zowel uit persoonlijke ervaring als uit beoordelingen van degenen die het al hebben geïmplementeerd, er sprake is van winst in betrouwbaarheid. Ja, het is onmogelijk om volledig van storingen af ​​te komen, maar het is heel goed mogelijk om de frequentie ervan aanzienlijk te verminderen. En de kaarten worden steeds uniformer, wat vervanging voor het servicepersoneel veel eenvoudiger maakt.

De hardware onderdeel

Er was geen bijzondere twijfel over de keuze van het geheugentype - NOR Flash.
Argumenten:

• eenvoudige aansluiting (meestal de SPI-bus, waar u al ervaring mee heeft, dus er zijn geen hardwareproblemen voorzien);
• belachelijke prijs;
• standaard besturingssysteem (de implementatie zit al in de Linux-kernel, als je wilt, kun je een derde partij nemen, die ook aanwezig is, of zelfs je eigen schrijven, gelukkig is alles eenvoudig);
• betrouwbaarheid en middelen:
  uit een typisch gegevensblad: gegevens worden 20 jaar bewaard, 100000 wiscycli voor elk blok;
  uit bronnen van derden: extreem lage BER, veronderstelt dat er geen foutcorrectiecodes nodig zijn (sommige werken beschouwen ECC als NOR, maar meestal bedoelen ze nog steeds MLC NOR; dit gebeurt ook).

Laten we de vereisten voor volume en middelen schatten.

Ik wil graag dat de gegevens gegarandeerd meerdere dagen bewaard blijven. Dit is nodig zodat bij eventuele communicatieproblemen de verkoophistorie niet verloren gaat. Tijdens deze periode concentreren wij ons op 5 dagen (zelfs rekening houdend met weekends en feestdagen) het probleem kan worden opgelost.

We verzamelen momenteel ongeveer 100 kb aan logboeken per dag (3-4 duizend inzendingen), maar geleidelijk groeit dit cijfer - de details nemen toe, er worden nieuwe evenementen toegevoegd. Bovendien zijn er soms uitbarstingen (sommige sensoren beginnen bijvoorbeeld te spammen met valse positieven). We berekenen voor 10 records elk 100 bytes - megabytes per dag.

In totaal komt er 5MB aan schone (goed gecomprimeerde) data vrij. Meer voor hen (ruwe schatting) 1 MB aan servicegegevens.

Dat wil zeggen dat we een chip van 8 MB nodig hebben als we geen compressie gebruiken, of 4 MB als we deze gebruiken. Vrij realistische cijfers voor dit type geheugen.

Wat de hulpbron betreft: als we van plan zijn dat het hele geheugen niet vaker dan eens in de vijf dagen wordt herschreven, dan krijgen we over een periode van tien jaar minder dan duizend herschrijfcycli.
Laat me u eraan herinneren dat de fabrikant honderdduizend belooft.

Een beetje over NOR versus NAND

Tegenwoordig is NAND-geheugen natuurlijk veel populairder, maar ik zou het niet voor dit project gebruiken: NAND vereist, in tegenstelling tot NOR, noodzakelijkerwijs het gebruik van foutcorrectiecodes, een tabel met slechte blokken, enz., en ook de benen van NAND-chips zijn meestal veel meer.

De nadelen van NOR zijn onder meer:

• klein volume (en dienovereenkomstig hoge prijs per megabyte);
• lage communicatiesnelheid (grotendeels vanwege het gebruik van een seriële interface, meestal SPI of I2C);
• langzaam wissen (afhankelijk van de blokgrootte duurt dit een fractie van een seconde tot enkele seconden).

Het lijkt erop dat er niets kritisch voor ons is, dus we gaan verder.

Als de details interessant zijn, is de microschakeling geselecteerd bij25df321a (dit is echter onbelangrijk, er zijn veel analogen op de markt die compatibel zijn wat betreft pinout en commandosysteem; zelfs als we een microschakeling van een andere fabrikant en/of een ander formaat willen installeren, zal alles werken zonder de code).

Ik gebruik de driver die in de Linux-kernel is ingebouwd; op Raspberry is alles, dankzij de ondersteuning voor device tree overlay, heel eenvoudig: je moet de gecompileerde overlay in /boot/overlays plaatsen en /boot/config.txt enigszins aanpassen.

Voorbeeld dts-bestand

Eerlijk gezegd weet ik niet zeker of het zonder fouten is geschreven, maar het werkt.

/*
 * 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 een regel in config.txt

dtoverlay=at25:spimaxfrequency=50000000

De beschrijving van het aansluiten van de chip op de Raspberry Pi laat ik achterwege. Aan de ene kant ben ik geen expert in elektronica, aan de andere kant is alles hier zelfs voor mij banaal: de microschakeling heeft slechts 8 poten, waarvan we aarde, stroom, SPI (CS, SI, SO, SCK) nodig hebben ); de niveaus zijn hetzelfde als die van de Raspberry Pi, er is geen extra bedrading nodig - sluit gewoon de aangegeven 6 pinnen aan.

Formulering van het probleem

Zoals gewoonlijk doorloopt de probleemstelling verschillende iteraties, en het lijkt mij dat het tijd is voor de volgende. Laten we dus stoppen, samenvoegen wat al is geschreven en de details verduidelijken die in de schaduw blijven.

Daarom hebben we besloten dat het logbestand wordt opgeslagen in SPI NOR Flash.

Wat is NOR Flash voor degenen die het niet weten?

Dit is niet-vluchtig geheugen waarmee je drie bewerkingen kunt uitvoeren:

1. Lezing:
   De meest voorkomende lezing: we verzenden het adres en lezen zoveel bytes als we nodig hebben;
2. record:
   Schrijven naar NOR-flash ziet eruit als normaal, maar heeft één bijzonderheid: je kunt alleen 1 in 0 veranderen, maar niet andersom. Als we bijvoorbeeld 0x55 in een geheugencel hadden, dan zal na het schrijven van 0x0f ernaar, 0x05 daar al worden opgeslagen (zie tabel hieronder);
3. wissen:
   Natuurlijk moeten we de tegenovergestelde bewerking kunnen uitvoeren: verander 0 in 1, dit is precies waar de wisbewerking voor is. In tegenstelling tot de eerste twee werkt het niet met bytes, maar met blokken (het minimale wisblok in de geselecteerde chip is 4 kb). Erase vernietigt het hele blok en is de enige manier om 0 in 1 te veranderen. Wanneer u met flash-geheugen werkt, moet u daarom vaak datastructuren uitlijnen op de grens van het wisblok.
   Opnemen in NOR Flash:

Binaire data

Het was
01010101

Opgenomen
00001111

Is geworden
00000101

Het logboek zelf vertegenwoordigt een reeks records met variabele lengte. De typische lengte van een record is ongeveer 30 bytes (hoewel soms records voorkomen die meerdere kilobytes lang zijn). In dit geval werken we er gewoon mee als een set bytes, maar als je geïnteresseerd bent, wordt CBOR gebruikt in de records

Naast het logboek moeten we ook wat “instellingsinformatie” opslaan, zowel bijgewerkt als niet: een bepaald apparaat-ID, sensorkalibraties, een vlag “apparaat is tijdelijk uitgeschakeld”, enz.
Deze informatie bestaat uit een reeks sleutelwaarderecords, ook opgeslagen in CBOR. We hebben niet veel van deze informatie (hooguit een paar kilobytes) en deze wordt niet vaak bijgewerkt.
In wat volgt zullen we dit context noemen.

Als we ons herinneren waar dit artikel begon, is het erg belangrijk om te zorgen voor een betrouwbare gegevensopslag en, indien mogelijk, een continue werking, zelfs in het geval van hardwarestoringen/gegevensbeschadiging.

Welke oorzaken van problemen kunnen worden overwogen?

• Uitschakelen tijdens schrijf-/wisbewerkingen. Dit komt uit de categorie ‘er bestaat geen truc tegen een koevoet’.
  Informatie van discussies op stackexchange: wanneer de stroom wordt uitgeschakeld tijdens het werken met flash, leiden zowel wissen (ingesteld op 1) als schrijven (ingesteld op 0) tot ongedefinieerd gedrag: gegevens kunnen worden geschreven, gedeeltelijk geschreven (we hebben bijvoorbeeld 10 bytes/80 bits overgedragen , maar er kunnen nog niet slechts 45 bits worden geschreven), is het ook mogelijk dat sommige bits zich in een “tussenliggende” toestand bevinden (lezen kan zowel 0 als 1 opleveren);
• Fouten in het flashgeheugen zelf.
  BER, hoewel zeer laag, kan niet gelijk zijn aan nul;
• Busfouten
  Gegevens die via SPI worden verzonden, worden op geen enkele manier beschermd; zowel enkele bitfouten als synchronisatiefouten kunnen optreden - verlies of invoeging van bits (wat leidt tot enorme gegevensvervorming);
• Andere fouten/storingen
  Fouten in de code, Raspberry-storingen, buitenaardse interferentie...

Ik heb de eisen geformuleerd waarvan de vervulling naar mijn mening noodzakelijk is om de betrouwbaarheid te garanderen:

• records moeten onmiddellijk in het flash-geheugen worden geplaatst; vertraagde schrijfbewerkingen worden niet in aanmerking genomen; - als er een fout optreedt, moet deze zo vroeg mogelijk worden gedetecteerd en verwerkt; - het systeem moet, indien mogelijk, herstellen van fouten.
  (een voorbeeld uit het leven “hoe het niet zou moeten zijn”, waarvan ik denk dat iedereen het wel eens is tegengekomen: na een noodherstart is het bestandssysteem “kapot” en start het besturingssysteem niet op)

Ideeën, benaderingen, reflecties

Toen ik over dit probleem begon na te denken, flitsten er veel ideeën door mijn hoofd, bijvoorbeeld:

• gebruik datacompressie;
• gebruik slimme datastructuren, bijvoorbeeld door recordkoppen apart van de records zelf op te slaan, zodat u, als er een fout in een record staat, de rest zonder problemen kunt lezen;
• gebruik bitvelden om de voltooiing van de opname te regelen wanneer de stroom wordt uitgeschakeld;
• bewaar controlesommen voor alles;
• gebruik een soort ruisbestendige codering.

Sommige van deze ideeën werden gebruikt, terwijl van andere werd besloten om ze te laten varen. Laten we in volgorde gaan.

Data compressie

De gebeurtenissen zelf die we in het dagboek vastleggen, lijken behoorlijk op elkaar en zijn herhaalbaar ("gooide een munt van 5 roebel", "drukte op de knop om wisselgeld te geven", ...). Daarom zou compressie behoorlijk effectief moeten zijn.

De compressieoverhead is onbeduidend (onze processor is behoorlijk krachtig, zelfs de eerste Pi had één kern met een frequentie van 700 MHz, de huidige modellen hebben meerdere kernen met een frequentie van meer dan een gigahertz), de wisselkoers met de opslag is laag (meerdere megabytes per seconde), is de omvang van de records klein. Als compressie invloed heeft op de prestaties, zal dit over het algemeen alleen maar positief zijn. (absoluut onkritisch, ik zeg het alleen maar). Bovendien hebben we geen echte embedded, maar gewone Linux - dus de implementatie zou niet veel moeite moeten kosten (het is voldoende om gewoon de bibliotheek te koppelen en er verschillende functies uit te gebruiken).

Een stukje van het logbestand werd van een werkend apparaat (1.7 MB, 70 vermeldingen) gehaald en eerst gecontroleerd op compressibiliteit met behulp van gzip, lz4, lzop, bzip2, xz, zstd beschikbaar op de computer.

• gzip, xz, zstd lieten vergelijkbare resultaten zien (40Kb).
  Ik was verrast dat de modieuze xz zich hier op het niveau van gzip of zstd liet zien;
• lzip met standaardinstellingen gaf iets slechtere resultaten;
• lz4 en lzop lieten geen erg goede resultaten zien (150Kb);
• bzip2 liet een verrassend goed resultaat zien (18Kb).

De gegevens worden dus zeer goed gecomprimeerd.
Dus (als we geen fatale gebreken vinden) zal er sprake zijn van compressie! Simpelweg omdat er meer gegevens op dezelfde flashdrive passen.

Laten we eens nadenken over de nadelen.

Eerste probleem: we hebben al afgesproken dat elke plaat onmiddellijk naar de flash moet. Doorgaans verzamelt het archiveringshulpmiddel gegevens uit de invoerstroom totdat het besluit dat het tijd is om in het weekend te schrijven. We moeten onmiddellijk een gecomprimeerd gegevensblok ontvangen en dit opslaan in een niet-vluchtig geheugen.

Ik zie drie manieren:

1. Comprimeer elk record met behulp van woordenboekcompressie in plaats van de hierboven besproken algoritmen.
   Het is een volledig werkende optie, maar ik vind het niet leuk. Om een ​​min of meer behoorlijk compressieniveau te garanderen, moet het woordenboek worden ‘op maat gemaakt’ voor specifieke gegevens; elke verandering zal ertoe leiden dat het compressieniveau catastrofaal daalt. Ja, het probleem kan worden opgelost door een nieuwe versie van het woordenboek te maken, maar dit is lastig: we zullen alle versies van het woordenboek moeten opslaan; bij elk item moeten we aangeven met welke versie van het woordenboek het is gecomprimeerd...
2. Comprimeer elk record met behulp van ‘klassieke’ algoritmen, maar onafhankelijk van de andere.
   De compressie-algoritmen die worden overwogen zijn niet ontworpen om te werken met records van deze omvang (tientallen bytes), de compressieverhouding zal duidelijk minder dan 1 zijn (dat wil zeggen, het datavolume vergroten in plaats van comprimeren);
3. Voer FLUSH uit na elke opname.
   Veel compressiebibliotheken ondersteunen FLUSH. Dit is een opdracht (of een parameter voor de compressieprocedure), waarna de archiver bij ontvangst een gecomprimeerde stroom vormt, zodat deze kan worden gebruikt voor het herstellen alle ongecomprimeerde gegevens die al zijn ontvangen. Zo'n analoog sync in bestandssystemen of commit in sql.
   Wat belangrijk is, is dat daaropvolgende compressiebewerkingen het verzamelde woordenboek kunnen gebruiken en dat de compressieverhouding niet zoveel zal lijden als in de vorige versie.

Ik denk dat het duidelijk is dat ik voor de derde optie heb gekozen, laten we er wat meer in detail naar kijken.

Gevonden geweldig artikel over FLUSH in zlib.

Ik heb een knietest gedaan op basis van het artikel, 70 loggegevens overgenomen van een echt apparaat, met een paginagrootte van 60 KB (we komen later terug op het paginaformaat) ontvangen:

Initiële gegevens
Compressie gzip -9 (geen FLUSH)
zlib met Z_PARTIAL_FLUSH
zlib met Z_SYNC_FLUSH

Deel, KB
1692
40
352
604

Op het eerste gezicht is de prijs die FLUSH bijdraagt ​​buitensporig hoog, maar in werkelijkheid hebben we weinig keus: ofwel helemaal niet comprimeren, ofwel (en zeer effectief) comprimeren met FLUSH. We moeten niet vergeten dat we 70 records hebben; de redundantie geïntroduceerd door Z_PARTIAL_FLUSH bedraagt ​​slechts 4-5 bytes per record. En de compressieverhouding bleek bijna 5:1 te zijn, wat een meer dan uitstekend resultaat is.

Het komt misschien als een verrassing, maar Z_SYNC_FLUSH is eigenlijk een efficiëntere manier om FLUSH uit te voeren

Bij gebruik van Z_SYNC_FLUSH zijn de laatste 4 bytes van elke invoer altijd 0x00, 0x00, 0xff, 0xff. En als we ze kennen, hoeven we ze niet op te slaan, dus de uiteindelijke grootte is slechts 324 KB.

Het artikel waarnaar ik linkte, bevat een uitleg:

Er is een nieuw type 0-blok met lege inhoud toegevoegd.

Een type 0 blok met lege inhoud bestaat uit:

• de drie-bits blokkop;
• 0 tot 7 bits gelijk aan nul, om byte-uitlijning te bereiken;
• de reeks van vier bytes 00 00 FF FF.

Zoals u gemakkelijk kunt zien, zijn er in het laatste blok vóór deze 4 bytes 3 tot 10 nulbits. De praktijk leert echter dat er feitelijk minimaal 10 nulbits zijn.

Het blijkt dat zulke korte datablokken meestal (altijd?) worden gecodeerd met behulp van een blok van type 1 (vast blok), dat noodzakelijkerwijs eindigt met 7 nulbits, wat een totaal oplevert van 10-17 gegarandeerde nulbits (en de rest zal nul zijn met een waarschijnlijkheid van ongeveer 50%).

Dus op testgegevens staat er in 100% van de gevallen één nulbyte vóór 0x00, 0x00, 0xff, 0xff, en in meer dan een derde van de gevallen zijn er twee nulbytes (misschien is het een feit dat ik binaire CBOR gebruik, en bij gebruik van tekst JSON zouden blokken van type 2 - dynamisch blok vaker voorkomen, respectievelijk blokken zonder extra nulbytes vóór 0x00, 0x00, 0xff, 0xff zouden worden aangetroffen).

In totaal is het met behulp van de beschikbare testgegevens mogelijk om minder dan 250 KB aan gecomprimeerde gegevens in te passen.

Door te jongleren met bits kun je wat meer besparen: voorlopig negeren we de aanwezigheid van een paar nulbits aan het einde van het blok, ook een paar bits aan het begin van het blok veranderen niet...
Maar toen nam ik de wilskrachtige beslissing om te stoppen, anders zou ik in dit tempo uiteindelijk mijn eigen archiveringshulpmiddel kunnen ontwikkelen.

In totaal ontving ik uit mijn testgegevens 3-4 bytes per schrijfbeurt, de compressieverhouding bleek meer dan 6:1 te zijn. Ik zal eerlijk zijn: zo'n resultaat had ik niet verwacht; naar mijn mening is alles beter dan 2:1 al een resultaat dat het gebruik van compressie rechtvaardigt.

Alles is in orde, maar zlib (deflate) is nog steeds een archaïsch, welverdiend en enigszins ouderwets compressie-algoritme. Alleen al het feit dat de laatste 32 KB van de niet-gecomprimeerde datastroom als woordenboek wordt gebruikt, ziet er tegenwoordig vreemd uit (dat wil zeggen: als een datablok erg lijkt op wat zich 40 KB geleden in de invoerstroom bevond, dan zal het opnieuw worden gearchiveerd. en verwijst niet naar een eerdere gebeurtenis). In moderne, moderne archiveringssystemen wordt de woordenboekgrootte vaak gemeten in megabytes in plaats van in kilobytes.

Dus gaan we door met onze ministudie naar archiveringssystemen.

Vervolgens hebben we bzip2 getest (onthoud dat het zonder FLUSH een fantastische compressieverhouding van bijna 100:1 liet zien). Helaas presteerde het erg slecht met FLUSH; de grootte van de gecomprimeerde gegevens bleek groter te zijn dan de niet-gecomprimeerde gegevens.

Mijn aannames over de redenen voor de mislukking

Libbz2 biedt slechts één flush-optie, die het woordenboek lijkt te wissen (analoog aan Z_FULL_FLUSH in zlib); hierna is er geen sprake van enige effectieve compressie.

En de laatste die werd getest was zstd. Afhankelijk van de parameters wordt het gecomprimeerd op het niveau van gzip, maar veel sneller of beter dan gzip.

Helaas presteerde het met FLUSH niet erg goed: de grootte van de gecomprimeerde gegevens was ongeveer 700 Kb.

Я een vraag gesteld op de github-pagina van het project kreeg ik het antwoord dat je moet rekenen op maximaal 10 bytes aan servicegegevens voor elk blok gecomprimeerde gegevens, wat dicht in de buurt komt van de verkregen resultaten; er is geen manier om deflatie in te halen.

Ik besloot op dit punt te stoppen met mijn experimenten met archiveringsprogramma's (laat me je eraan herinneren dat xz, lzip, lzo, lz4 zich zelfs in de testfase zonder FLUSH niet lieten zien, en ik heb geen rekening gehouden met meer exotische compressie-algoritmen).

Laten we terugkeren naar de archiveringsproblemen.

Het tweede (zoals ze zeggen in volgorde, niet in waarde) is dat de gecomprimeerde gegevens één enkele stroom zijn, waarin voortdurend wordt verwezen naar eerdere secties. Als een deel van de gecomprimeerde gegevens beschadigd raakt, verliezen we dus niet alleen het bijbehorende blok met niet-gecomprimeerde gegevens, maar ook alle daaropvolgende blokken.

Er is een aanpak om dit probleem op te lossen:

1. Voorkom dat het probleem zich voordoet - voeg redundantie toe aan de gecomprimeerde gegevens, waardoor u fouten kunt identificeren en corrigeren; we zullen hier later over praten;
2. Minimaliseer de gevolgen als er zich een probleem voordoet
   We hebben al eerder gezegd dat je elk datablok onafhankelijk kunt comprimeren, en het probleem zal vanzelf verdwijnen (schade aan de gegevens van één blok zal alleen voor dit blok tot gegevensverlies leiden). Dit is echter een extreem geval waarin datacompressie niet effectief zal zijn. Het tegenovergestelde uiterste: gebruik alle 4 MB van onze chip als één enkel archief, wat ons een uitstekende compressie zal opleveren, maar catastrofale gevolgen in geval van gegevenscorruptie.
   Ja, er is een compromis nodig op het gebied van betrouwbaarheid. Maar we moeten niet vergeten dat we een gegevensopslagformaat voor niet-vluchtig geheugen aan het ontwikkelen zijn met een extreem lage BER en een aangegeven gegevensopslagperiode van 20 jaar.

Tijdens de experimenten ontdekte ik dat min of meer merkbare verliezen in het compressieniveau beginnen bij blokken gecomprimeerde gegevens die kleiner zijn dan 10 KB.
Er werd eerder vermeld dat het gebruikte geheugen gepagineerd is; ik zie geen reden waarom de correspondentie “één pagina - één blok gecomprimeerde gegevens” niet zou moeten worden gebruikt.

Dat wil zeggen dat de minimale redelijke paginagrootte 16 Kb is (met een reserve voor service-informatie). Een dergelijk klein paginaformaat legt echter aanzienlijke beperkingen op aan de maximale recordgrootte.

Hoewel ik nog geen records verwacht die groter zijn dan een paar kilobytes in gecomprimeerde vorm, heb ik besloten om 32Kb-pagina's te gebruiken (voor een totaal van 128 pagina's per chip).

Samenvatting:

• We slaan gegevens gecomprimeerd op met zlib (deflate);
• Voor elke invoer stellen we Z_SYNC_FLUSH in;
• Voor elk gecomprimeerd record knippen we de volgbytes bij (bijvoorbeeld 0x00, 0x00, 0xff, 0xff); in de header geven we aan hoeveel bytes we afsnijden;
• We slaan gegevens op in pagina's van 32 KB; er is één enkele stroom gecomprimeerde gegevens op de pagina; Op elke pagina starten we opnieuw met comprimeren.

En voordat ik afsluit met de compressie, wil ik uw aandacht vestigen op het feit dat we slechts een paar bytes aan gecomprimeerde gegevens per record hebben, dus het is uiterst belangrijk om de service-informatie niet op te blazen; elke byte telt hier.

Gegevenskoppen opslaan

Omdat we records van variabele lengte hebben, moeten we op de een of andere manier de plaatsing/grenzen van records bepalen.

Ik ken drie benaderingen:

1. Alle records worden in een continue stroom opgeslagen, eerst is er een recordkop met de lengte en vervolgens het record zelf.
   In deze uitvoeringsvorm kunnen zowel headers als data een variabele lengte hebben.
   In wezen krijgen we een enkelvoudig gekoppelde lijst die voortdurend wordt gebruikt;
2. Headers en de records zelf worden in afzonderlijke streams opgeslagen.
   Door headers van constante lengte te gebruiken, zorgen we ervoor dat schade aan één header de andere niet beïnvloedt.
   Een soortgelijke aanpak wordt bijvoorbeeld in veel bestandssystemen gebruikt;
3. Records worden opgeslagen in een continue stroom, waarbij de recordgrens wordt bepaald door een bepaalde markering (een teken/reeks van tekens die verboden is binnen datablokken). Als er een markering in de record staat, vervangen we deze door een bepaalde reeks (escape it).
   Een soortgelijke aanpak wordt bijvoorbeeld gebruikt in het PPP-protocol.

Ik zal illustreren.

Optie 1:

Alles is hier heel eenvoudig: als we de lengte van het record kennen, kunnen we het adres van de volgende header berekenen. We doorlopen dus de kopjes totdat we een gebied tegenkomen dat gevuld is met 0xff (vrij gebied) of het einde van de pagina.

Optie 2:

Vanwege de variabele recordlengte kunnen we op voorhand niet zeggen hoeveel records (en dus headers) we per pagina nodig hebben. Je kunt de headers en de data zelf over verschillende pagina’s spreiden, maar ik geef de voorkeur aan een andere aanpak: we plaatsen zowel de headers als de data op één pagina, maar de headers (van constante grootte) komen vanaf het begin van de pagina, en de gegevens (van variabele lengte) komen van het einde. Zodra ze elkaar “ontmoeten” (er is niet genoeg vrije ruimte voor een nieuwe inzending), beschouwen we deze pagina als voltooid.

Optie 3:

Het is niet nodig om de lengte of andere informatie over de locatie van de gegevens in de header op te slaan; markeringen die de grenzen van de records aangeven zijn voldoende. Bij het schrijven/lezen moeten de gegevens echter wel worden verwerkt.
Ik zou 0xff gebruiken als markering (die de pagina vult na wissen), dus het vrije gebied zal zeker niet als gegevens worden behandeld.

Vergelijkingstabel:

optie 1
optie 2
optie 3

Fouttolerantie
-
+
+

dichtheid
+
-
+

Complexiteit van de implementatie
*
**
**

Optie 1 heeft een fatale fout: als een van de headers beschadigd is, wordt de hele daaropvolgende keten vernietigd. Met de overige opties kunt u sommige gegevens herstellen, zelfs in geval van enorme schade.
Maar hier is het passend om te onthouden dat we besloten hebben de gegevens in gecomprimeerde vorm op te slaan, en dus verliezen we alle gegevens op de pagina na een “gebroken” record, dus ook al staat er een minteken in de tabel, we doen dat niet hou er rekening mee.

Compactheid:

• bij de eerste optie hoeven we alleen de lengte in de header op te slaan; als we gehele getallen met variabele lengte gebruiken, kunnen we in de meeste gevallen met één byte rondkomen;
• bij de tweede optie moeten we het startadres en de lengte opslaan; het record moet een constante grootte hebben, ik schat 4 bytes per record (twee bytes voor de offset en twee bytes voor de lengte);
• de derde optie heeft slechts één teken nodig om het begin van de opname aan te geven, plus de opname zelf zal door afscherming met 1-2% toenemen. Over het algemeen ongeveer gelijk aan de eerste optie.

Aanvankelijk beschouwde ik de tweede optie als de belangrijkste (en schreef zelfs de implementatie). Ik heb het pas opgegeven toen ik uiteindelijk besloot compressie te gebruiken.

Misschien zal ik ooit nog een soortgelijke optie gebruiken. Als ik bijvoorbeeld te maken heb met dataopslag voor een schip dat tussen de aarde en Mars reist, zullen er totaal andere eisen gesteld worden aan betrouwbaarheid, kosmische straling, …

Wat betreft de derde optie: ik gaf het twee sterren vanwege de moeilijkheid van de implementatie, simpelweg omdat ik er niet van houd om te rommelen met afscherming, de lengte ervan te veranderen, enz. Ja, misschien ben ik bevooroordeeld, maar ik zal de code moeten schrijven - waarom zou je jezelf dwingen iets te doen dat je niet leuk vindt?

Samenvatting: We kiezen voor de opslagoptie in de vorm van ketens “header met lengte - gegevens van variabele lengte” vanwege efficiëntie en implementatiegemak.

Bitvelden gebruiken om het succes van schrijfbewerkingen te controleren

Ik weet niet meer waar ik het idee vandaan haalde, maar het ziet er ongeveer zo uit:
Voor elke invoer wijzen we verschillende bits toe om vlaggen op te slaan.
Zoals we eerder zeiden, worden na het wissen alle bits gevuld met 1-en, en kunnen we 1 in 0 veranderen, maar niet andersom. Dus voor “de vlag is niet ingesteld” gebruiken we 1, voor “de vlag is ingesteld” gebruiken we 0.

Zo zou het plaatsen van een record met variabele lengte in Flash eruit kunnen zien:

1. Zet de vlag “lengte opname is gestart”;
2. Noteer de lengte;
3. Zet de vlag “gegevensregistratie is gestart”;
4. Wij registreren gegevens;
5. Stel de vlag “opname beëindigd” in.

Bovendien zullen we een vlag "error opgetreden" hebben, voor een totaal van 4 bit-vlaggen.

In dit geval hebben we twee stabiele toestanden: “1111” – de opname is niet gestart en “1000” – de opname is gelukt; bij een onverwachte onderbreking van het opnameproces krijgen we tussentoestanden, die we vervolgens kunnen detecteren en verwerken.

De aanpak is interessant, maar beschermt alleen tegen plotselinge stroomstoringen en soortgelijke storingen, wat natuurlijk belangrijk is, maar dit is verre van de enige (of zelfs de belangrijkste) reden voor mogelijke storingen.

Samenvatting: Laten we verder gaan op zoek naar een goede oplossing.

Controlesommen

Controlesommen maken het ook mogelijk om er zeker van te zijn (met een redelijke waarschijnlijkheid) dat we precies lezen wat er had moeten worden geschreven. En, in tegenstelling tot de hierboven besproken bitvelden, werken ze altijd.

Als we de lijst met potentiële bronnen van problemen bekijken die we hierboven hebben besproken, kan de controlesom een ​​fout herkennen, ongeacht de oorsprong ervan (behalve misschien voor kwaadwillende buitenaardse wezens - zij kunnen ook de controlesom vervalsen).

Dus als het ons doel is om te verifiëren dat de gegevens intact zijn, zijn checksums een goed idee.

De keuze van het algoritme voor het berekenen van de controlesom riep geen vragen op - CRC. Aan de ene kant maken wiskundige eigenschappen het mogelijk om bepaalde soorten fouten 100% op te vangen; aan de andere kant toont dit algoritme op willekeurige gegevens meestal de kans op botsingen niet veel groter dan de theoretische limiet . Het is misschien niet het snelste algoritme, en ook niet altijd het minimum in termen van het aantal botsingen, maar het heeft een heel belangrijke kwaliteit: in de tests die ik tegenkwam waren er geen patronen waarin het duidelijk faalde. Stabiliteit is in dit geval de belangrijkste kwaliteit.

Voorbeeld van een volumetrisch onderzoek: Deel 1, Deel 2 (links naar narod.ru, sorry).

De taak van het selecteren van een controlesom is echter niet voltooid; CRC is een hele familie van controlesommen. U moet beslissen over de lengte en vervolgens een polynoom kiezen.

Het kiezen van de controlesomlengte is niet zo eenvoudig als het op het eerste gezicht lijkt.

Laat me illustreren:
Laten we de waarschijnlijkheid van een fout in elke byte berekenen en een ideale controlesom: laten we het gemiddelde aantal fouten per miljoen records berekenen:

Gegevens, byte
Controlesom, byte
Onopgemerkte fouten
Valse foutdetecties
Totaal valse positieven

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

Het lijkt erop dat alles eenvoudig is: kies, afhankelijk van de lengte van de gegevens die worden beschermd, de lengte van de controlesom met een minimum aan onjuiste positieven - en de truc zit in de tas.

Er doet zich echter een probleem voor bij korte controlesommen: hoewel ze goed zijn in het detecteren van fouten van enkele bits, kunnen ze met een vrij grote waarschijnlijkheid volledig willekeurige gegevens als correct accepteren. Er was al een artikel over Habré dat dit beschrijft probleem in het echte leven.

Om een ​​willekeurige checksum-match vrijwel onmogelijk te maken, moet u daarom checksums gebruiken die 32 bits of langer zijn. (voor lengtes groter dan 64 bit worden meestal cryptografische hashfuncties gebruikt).

Ondanks het feit dat ik eerder schreef dat we absoluut ruimte moeten besparen, zullen we nog steeds een 32-bits checksum gebruiken (16 bits zijn niet genoeg, de kans op een botsing is meer dan 0.01%; en 24 bits, omdat ze zeg: zijn noch hier noch daar).

Hier kan een bezwaar rijzen: hebben we bij het kiezen van compressie elke byte bewaard om nu 4 bytes tegelijk te geven? Zou het niet beter zijn om geen controlesom te comprimeren of toe te voegen? Natuurlijk niet, geen compressie betekent niet, dat we geen integriteitscontrole nodig hebben.

Bij het kiezen van een polynoom zullen we het wiel niet opnieuw uitvinden, maar de nu populaire CRC-32C nemen.
Deze code detecteert 6 bitfouten op pakketten tot 22 bytes (misschien het meest voorkomende geval voor ons), 4 bitfouten op pakketten tot 655 bytes (ook een veel voorkomend geval voor ons), 2 of een oneven aantal bitfouten op pakketten van elke redelijke lengte.

Als iemand geïnteresseerd is in de details

Wikipedia-artikel over CRC.

Codeparameters crc-32c op Koopman-website – misschien wel de leidende CRC-specialist ter wereld.

В zijn artikel er is nog een interessante code, wat iets betere parameters biedt voor de pakketlengtes die voor ons relevant zijn, maar ik vond het verschil niet significant, en ik was bekwaam genoeg om aangepaste code te kiezen in plaats van de standaard en goed onderzochte code.

Omdat onze gegevens gecomprimeerd zijn, rijst de vraag: moeten we de controlesom van gecomprimeerde of ongecomprimeerde gegevens berekenen?

Argumenten vóór het berekenen van de controlesom van niet-gecomprimeerde gegevens:

• Uiteindelijk moeten we de veiligheid van de gegevensopslag controleren - dus we controleren deze rechtstreeks (tegelijkertijd worden mogelijke fouten bij de implementatie van compressie/decompressie, schade veroorzaakt door kapot geheugen, enz. gecontroleerd);
• Het deflate-algoritme in zlib heeft een redelijk volwassen implementatie en zou niet moeten vallen met “scheve” invoergegevens; bovendien is het vaak in staat om onafhankelijk fouten in de invoerstroom te detecteren, waardoor de algehele kans kleiner wordt dat een fout niet wordt gedetecteerd (een test uitgevoerd waarbij een enkele bit in een korte record werd geïnverteerd, zlib heeft een fout gedetecteerd in ongeveer een derde van de gevallen).

Argumenten tegen het berekenen van de controlesom van niet-gecomprimeerde gegevens:

• CRC is specifiek ‘op maat gemaakt’ voor de paar bitfouten die kenmerkend zijn voor flashgeheugen (een bitfout in een gecomprimeerde stroom kan een enorme verandering in de uitvoerstroom veroorzaken, waarop we, puur theoretisch, een botsing kunnen ‘vangen’);
• Ik hou niet echt van het idee om mogelijk kapotte gegevens door te geven aan de decompressor, Wie weethoe hij zal reageren.

In dit project heb ik besloten af ​​te wijken van de algemeen aanvaarde praktijk van het opslaan van een controlesom van ongecomprimeerde gegevens.

Samenvatting: We gebruiken CRC-32C, we berekenen de controlesom uit de gegevens in de vorm waarin ze naar flash zijn geschreven (na compressie).

Ontslag

Het gebruik van redundante codering elimineert gegevensverlies uiteraard niet, maar kan de kans op onherstelbaar gegevensverlies wel aanzienlijk (vaak vele ordes van grootte) verkleinen.

We kunnen verschillende soorten redundantie gebruiken om fouten te corrigeren.
Hamming-codes kunnen fouten van één bit corrigeren, Reed-Solomon-tekencodes, meerdere kopieën van gegevens gecombineerd met controlesommen, of coderingen zoals RAID-6 kunnen helpen gegevens te herstellen, zelfs in het geval van enorme corruptie.
Aanvankelijk was ik voorstander van het wijdverbreide gebruik van foutbestendige codering, maar toen besefte ik dat we eerst een idee moeten hebben van tegen welke fouten we ons willen beschermen, en dan voor codering moeten kiezen.

We hebben eerder gezegd dat fouten zo snel mogelijk moeten worden ontdekt. Op welke punten kunnen we fouten tegenkomen?

1. Onvoltooide opname (om de een of andere reden werd op het moment van opnemen de stroom uitgeschakeld, de Raspberry bevroor, ...)
   Helaas, in het geval van een dergelijke fout hoeft u alleen maar ongeldige records te negeren en de gegevens als verloren te beschouwen;
2. Schrijffouten (om de een of andere reden was wat naar het flashgeheugen werd geschreven niet wat er werd geschreven)
   We kunnen dergelijke fouten onmiddellijk detecteren als we onmiddellijk na de opname een testuitlezing doen;
3. Vervorming van gegevens in het geheugen tijdens opslag;
4. Leesfouten
   Om dit te corrigeren, als de controlesom niet overeenkomt, volstaat het om de meting meerdere keren te herhalen.

Dat wil zeggen dat alleen fouten van het derde type (spontane beschadiging van gegevens tijdens opslag) niet kunnen worden gecorrigeerd zonder foutbestendige codering. Het lijkt erop dat dergelijke fouten nog steeds uiterst onwaarschijnlijk zijn.

Samenvatting: er werd besloten om overtollige codering achterwege te laten, maar als de werking de fout van deze beslissing aantoont, keer dan terug naar de overweging van het probleem (met reeds verzamelde statistieken over fouten, waardoor het optimale type codering kan worden gekozen).

Ander

Natuurlijk staat het formaat van het artikel ons niet toe om elk stukje in het formaat te rechtvaardigen (en mijn kracht is al op), dus ik zal kort enkele punten bespreken die nog niet eerder zijn besproken.

• Er is besloten om alle pagina’s “gelijk” te maken
  Dat wil zeggen dat er geen speciale pagina's zullen zijn met metadata, afzonderlijke threads, enz., maar in plaats daarvan één enkele thread die alle pagina's beurtelings herschrijft.
  Dit zorgt voor een gelijkmatige slijtage van de pagina's, geen enkel storingspunt, en dat vind ik gewoon leuk;
• Het is absoluut noodzakelijk om versiebeheer van het formaat aan te bieden.
  Een formaat zonder versienummer in de header is slecht!
  Het volstaat om een ​​veld met een bepaald Magic Number (handtekening) aan de paginakop toe te voegen, dat de versie van het gebruikte formaat aangeeft (Ik denk niet dat het er in de praktijk zelfs maar een dozijn zullen zijn);
• Gebruik een header met variabele lengte voor records (waarvan er veel zijn), en probeer deze in de meeste gevallen 1 byte lang te maken;
• Gebruik binaire codes met variabele lengte om de lengte van de koptekst en de lengte van het ingekorte deel van het gecomprimeerde record te coderen.

Heeft veel geholpen onlinegenerator Huffman-codes. In slechts een paar minuten konden we de vereiste codes met variabele lengte selecteren.

Beschrijving van het gegevensopslagformaat

Byte volgorde

Velden groter dan één byte worden opgeslagen in big-endian-indeling (volgorde van netwerkbytes), dat wil zeggen dat 0x1234 wordt geschreven als 0x12, 0x34.

Paginering

Al het flashgeheugen is verdeeld in pagina's van gelijke grootte.

De standaardpaginagrootte is 32Kb, maar niet meer dan 1/4 van de totale grootte van de geheugenchip (voor een chip van 4MB worden 128 pagina's verkregen).

Op elke pagina worden gegevens onafhankelijk van de andere pagina's opgeslagen (dat wil zeggen dat gegevens op de ene pagina niet verwijzen naar gegevens op een andere pagina).

Alle pagina's zijn genummerd in natuurlijke volgorde (in oplopende volgorde van adressen), beginnend met nummer 0 (pagina nul begint op adres 0, de eerste pagina begint op 32Kb, de tweede pagina begint op 64Kb, etc.)

De geheugenchip wordt gebruikt als een cyclische buffer (ringbuffer), dat wil zeggen dat het eerste schrijven naar paginanummer 0 gaat, vervolgens naar nummer 1, .... Wanneer we de laatste pagina vullen, begint een nieuwe cyclus en gaat de opname verder vanaf pagina nul .

Binnen de pagina

Aan het begin van de pagina wordt een paginakop van 4 bytes opgeslagen, vervolgens een header-checksum (CRC-32C), en vervolgens worden records opgeslagen in het “header, data, checksum”-formaat.

De paginatitel (viesgroen in het diagram) bestaat uit:

• Magisch nummerveld van twee bytes (ook een teken van de formaatversie)
  voor de huidige versie van het formaat wordt het berekend als 0xed00 ⊕ номер страницы;
• twee-byte teller “Paginaversie” (nummer van de geheugenherschrijfcyclus).

Gegevens op de pagina worden in gecomprimeerde vorm opgeslagen (er wordt gebruik gemaakt van het deflate-algoritme). Alle records op één pagina worden gecomprimeerd in één thread (er wordt gebruik gemaakt van een gemeenschappelijk woordenboek) en op elke nieuwe pagina begint de compressie opnieuw. Dat wil zeggen, om een ​​record te decomprimeren, zijn alle voorgaande records van deze pagina (en alleen deze) vereist.

Elke record wordt gecomprimeerd met de vlag Z_SYNC_FLUSH en aan het einde van de gecomprimeerde stroom zijn er 4 bytes 0x00, 0x00, 0xff, 0xff, mogelijk voorafgegaan door nog een of twee nulbytes.
We negeren deze reeks (4, 5 of 6 bytes lang) bij het schrijven naar flash-geheugen.

De recordkop bevat 1, 2 of 3 bytes waarin het volgende wordt opgeslagen:

• één bit (T) die het type record aangeeft: 0 - context, 1 - log;
• een veld met variabele lengte (S) van 1 tot 7 bits, dat de lengte definieert van de header en de “tail” die aan het record moeten worden toegevoegd voor decompressie;
• recordlengte (L).

S-waardetabel:

S
Lengte header, bytes
Verwijderd bij schrijven, 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)

Ik probeerde het te illustreren, ik weet niet hoe duidelijk het bleek:

Geel geeft hier het T-veld aan, wit het S-veld, groen L (de lengte van de gecomprimeerde gegevens in bytes), blauw de gecomprimeerde gegevens, rood de laatste bytes van de gecomprimeerde gegevens die niet naar het flashgeheugen zijn geschreven.

We kunnen dus recordheaders van de meest voorkomende lengte (tot 63+5 bytes in gecomprimeerde vorm) in één byte schrijven.

Na elke record wordt een CRC-32C-checksum opgeslagen, waarbij de omgekeerde waarde van de vorige checksum als initiële waarde (init) wordt gebruikt.

CRC heeft de eigenschap ‘duur’, de volgende formule werkt (plus of min bit-inversie in het proces): .
Dat wil zeggen dat we in feite de CRC berekenen van alle voorgaande bytes aan headers en gegevens op deze pagina.

Direct na de controlesom volgt de header van het volgende record.

De header is zo ontworpen dat de eerste byte ervan altijd verschilt van 0x00 en 0xff (als we in plaats van de eerste byte van de header 0xff tegenkomen, betekent dit dat dit een ongebruikt gebied is; 0x00 signaleert een fout).

Voorbeeldalgoritmen

Lezen uit Flash-geheugen

Elke meting wordt geleverd met een checksum-controle.
Als de controlesom niet overeenkomt, wordt het lezen meerdere keren herhaald in de hoop de juiste gegevens te lezen.

(dit is logisch, Linux slaat geen lezingen van NOR Flash op in de cache, getest)

Schrijf naar flash-geheugen

Wij registreren de gegevens.
Laten we ze lezen.

Als de gelezen gegevens niet overeenkomen met de geschreven gegevens, vullen we het gebied met nullen en signaleren we een fout.

Een nieuwe microschakeling voorbereiden voor gebruik

Voor initialisatie wordt een header met versie 1 naar de eerste (of liever nul) pagina geschreven.
Daarna wordt de initiële context naar deze pagina geschreven (bevat de UUID van de machine en standaardinstellingen).

Dat is alles, het flashgeheugen is klaar voor gebruik.

Het laden van de machine

Bij het laden worden de eerste 8 bytes van elke pagina (header + CRC) gelezen, pagina's met een onbekend Magic Number of een onjuiste CRC worden genegeerd.
Van de "juiste" pagina's worden pagina's met de maximale versie geselecteerd en de pagina met het hoogste nummer wordt daaruit gehaald.
Het eerste record wordt gelezen, de juistheid van de CRC en de aanwezigheid van de “context”-vlag worden gecontroleerd. Als alles in orde is, wordt deze pagina als actueel beschouwd. Als dat niet het geval is, gaan we terug naar de vorige totdat we een ‘live’ pagina vinden.
en op de gevonden pagina lezen we alle records, die we gebruiken met de vlag "context".
Sla het zlib-woordenboek op (deze is nodig om deze aan deze pagina toe te voegen).

Dat is alles, de download is voltooid, de context is hersteld, u kunt werken.

Een journaalboeking toevoegen

We comprimeren het record met het juiste woordenboek, met vermelding van Z_SYNC_FLUSH, en kijken of het gecomprimeerde record op de huidige pagina past.
Als het niet past (of als er CRC-fouten op de pagina staan), start dan een nieuwe pagina (zie hieronder).
We noteren het record en de CRC. Als er een fout optreedt, start dan een nieuwe pagina.

Nieuwe pagina

We selecteren een vrije pagina met het minimumaantal (we beschouwen een gratis pagina als een pagina met een onjuiste checksum in de header of met een versie die lager is dan de huidige). Als dergelijke pagina's niet bestaan, selecteert u de pagina met het minimumaantal van de pagina's met een versie die gelijk is aan de huidige.
We wissen de geselecteerde pagina. We controleren de inhoud met 0xff. Als er iets mis is, neem dan de volgende vrije pagina, enz.
We schrijven een koptekst op de gewiste pagina, de eerste invoer is de huidige status van de context, de volgende is de ongeschreven loginvoer (als die er is).

Formaat toepasbaarheid

Naar mijn mening bleek het een goed formaat te zijn voor het opslaan van min of meer samendrukbare informatiestromen (platte tekst, JSON, MessagePack, CBOR, mogelijk protobuf) in NOR Flash.

Uiteraard is het formaat “op maat” gemaakt voor SLC NOR Flash.

Het mag niet worden gebruikt met hoge BER-media zoals NAND of MLC NOR (is dergelijk geheugen überhaupt te koop? Ik heb het alleen vermeld zien staan ​​in werken over correctiecodes).

Bovendien mag het niet worden gebruikt met apparaten die over een eigen FTL beschikken: USB-flash, SD, MicroSD, enz (voor dergelijk geheugen heb ik een formaat gemaakt met een paginagrootte van 512 bytes, een handtekening aan het begin van elke pagina en unieke recordnummers - soms was het mogelijk om alle gegevens van een "glitched" flashstation te herstellen door eenvoudig opeenvolgend te lezen).

Afhankelijk van de taken kan het formaat zonder wijzigingen worden gebruikt op flashdrives van 128Kbit (16Kb) tot 1Gbit (128MB). Indien gewenst kunt u het op grotere chips gebruiken, maar moet u waarschijnlijk het paginaformaat aanpassen (Maar hier rijst de vraag van de economische haalbaarheid al; de prijs voor grootschalige NOR Flash is niet bemoedigend).

Als iemand het formaat interessant vindt en het in een open project wil gebruiken, schrijf dan, ik zal proberen de tijd te vinden, de code op te poetsen en op github te plaatsen.

Conclusie

Zoals je kunt zien, bleek het formaat uiteindelijk eenvoudig en zelfs saai.

Het is moeilijk om de evolutie van mijn standpunt in een artikel weer te geven, maar geloof me: aanvankelijk wilde ik iets geavanceerds, onverwoestbaars creëren, dat zelfs een nucleaire explosie in de directe omgeving kon overleven. De rede (hoop ik) won echter nog steeds en geleidelijk verschoven de prioriteiten naar eenvoud en compactheid.

Zou het kunnen dat ik ongelijk had? Ja tuurlijk. Het kan bijvoorbeeld heel goed blijken dat we een partij microschakelingen van lage kwaliteit hebben gekocht. Of om een ​​andere reden voldoet de apparatuur niet aan de betrouwbaarheidsverwachtingen.

Heb ik hier een plan voor? Ik denk dat je na het lezen van het artikel geen twijfel meer hebt dat er een plan is. En niet eens alleen.

Iets serieuzer: het formaat werd zowel als werkoptie als als ‘proefballon’ ontwikkeld.

Op dit moment werkt alles wat op tafel ligt prima, letterlijk binnenkort wordt de oplossing ingezet (ongeveer) Laten we op honderden apparaten eens kijken wat er gebeurt tijdens de “gevechts”-operatie (gelukkig hoop ik dat je met het formaat op betrouwbare wijze fouten kunt detecteren, zodat je volledige statistieken kunt verzamelen). Over een paar maanden zullen we conclusies kunnen trekken (en als je pech hebt, zelfs eerder).

Als er op basis van de gebruiksresultaten ernstige problemen worden ontdekt en er verbeteringen nodig zijn, dan zal ik daar zeker over schrijven.

Literatuur

Ik wilde geen lange, vervelende lijst met gebruikte werken maken; iedereen heeft immers Google.

Hier besloot ik een lijst met bevindingen achter te laten die mij bijzonder interessant leken, maar geleidelijk migreerden ze rechtstreeks naar de tekst van het artikel, en één item bleef op de lijst staan:

1. Nut infgen van de auteur zlib. Kan de inhoud van deflate/zlib/gzip-archieven duidelijk weergeven. Als je te maken hebt met de interne structuur van het deflate (of gzip) formaat, raad ik het ten zeerste aan.

Bron: www.habr.com