förhistoria

Det finns varuautomater av egen design. Inuti Raspberry Pi och lite ledningar på ett separat kort. En myntmottagare, en sedelmottagare, en bankterminal ansluts... Allt styrs av ett egenskrivet program. Hela arbetshistoriken skrivs till en logg på ett flashminne (MicroSD), som sedan överförs via Internet (med ett USB-modem) till servern, där den lagras i en databas. Försäljningsinformation laddas in i 1c, det finns även ett enkelt webbgränssnitt för övervakning osv.

Det vill säga, tidskriften är avgörande - för redovisning (intäkter, försäljning, etc.), övervakning (alla typer av misslyckanden och andra force majeure-förhållanden); Detta kan man säga är all information vi har om den här maskinen.

problem

Flash-enheter visar sig vara mycket opålitliga enheter. De misslyckas med avundsvärd regelbundenhet. Detta leder till både maskinstopp och (om loggen av någon anledning inte kunde överföras online) till dataförlust.

Detta är inte den första erfarenheten av att använda flash-enheter, innan detta fanns ett annat projekt med mer än hundra enheter, där tidningen lagrades på USB-minnen, det fanns också problem med tillförlitligheten, ibland antalet som misslyckades i en månad var i dussintal. Vi provade olika flashenheter, inklusive märkesvaror med SLC-minne, och vissa modeller är mer pålitliga än andra, men att byta ut flashenheter löste inte problemet radikalt.

Varning! Långläst! Om du inte är intresserad av "varför", utan bara av "hur", kan du gå direkt i tråden artikeln.

beslutet

Det första som kommer att tänka på är: överge MicroSD, installera till exempel en SSD och starta från den. Teoretiskt möjligt, förmodligen, men relativt dyrt och inte så tillförlitligt (en USB-SATA-adapter läggs till; felstatistik för budget-SSD-enheter är inte heller uppmuntrande).

USB HDD ser inte heller ut som en särskilt attraktiv lösning.

Därför kom vi till det här alternativet: lämna uppstarten från MicroSD, men använd dem i skrivskyddat läge, och lagra operationsloggen (och annan information som är unik för en viss hårdvara - serienummer, sensorkalibreringar, etc.) någon annanstans .

Ämnet med skrivskyddad FS för hallon har redan studerats inifrån och ut, jag kommer inte att uppehålla mig vid implementeringsdetaljer i den här artikeln (men om det finns intresse kanske jag skriver en miniartikel om detta ämne). Den enda punkt jag skulle vilja notera är att både av personlig erfarenhet och från recensioner av de som redan har implementerat det, finns det en vinst i tillförlitlighet. Ja, det är omöjligt att helt bli av med sammanbrott, men att avsevärt minska deras frekvens är fullt möjligt. Och korten håller på att förenas, vilket gör utbytet mycket lättare för servicepersonalen.

Hårdvaran delen

Det rådde ingen speciell tvekan om valet av minnestyp - NOR Flash.
Argument:

• enkel anslutning (oftast SPI-bussen, som du redan har erfarenhet av att använda, så inga hårdvaruproblem förutses);
• löjligt pris;
• standardoperativt protokoll (implementeringen finns redan i Linux-kärnan, om du vill kan du ta en tredje part, som också finns, eller till och med skriva din egen, lyckligtvis är allt enkelt);
• tillförlitlighet och resurs:
  från ett typiskt datablad: data lagras i 20 år, 100000 XNUMX raderingscykler för varje block;
  från tredje parts källor: extremt låg BER, postulerar inget behov av felkorrigeringskoder (vissa verk anser ECC för NOR, men vanligtvis betyder de fortfarande MLC NOR; detta händer också).

Låt oss uppskatta kraven på volym och resurs.

Jag skulle vilja att uppgifterna garanteras sparas i flera dagar. Detta är nödvändigt så att försäljningshistoriken inte går förlorad vid eventuella problem med kommunikationen. Vi kommer att fokusera på 5 dagar, under denna period (även med hänsyn till helger och helgdagar) problemet kan lösas.

Vi samlar för närvarande cirka 100 kb loggar per dag (3-4 tusen poster), men gradvis växer denna siffra - detaljerna ökar, nya händelser läggs till. Plus, ibland finns det skurar (vissa sensorer börjar spamma med falska positiva, till exempel). Vi kommer att beräkna för 10 tusen poster 100 byte vardera - megabyte per dag.

Totalt kommer 5MB ren (väl komprimerad) data ut. Mer till dem (grov uppskattning) 1 MB servicedata.

Det vill säga, vi behöver ett 8MB-chip om vi inte använder komprimering, eller 4MB om vi använder det. Ganska realistiska siffror för denna typ av minne.

När det gäller resursen: om vi planerar att hela minnet inte ska skrivas om mer än en gång var 5:e dag, så får vi under 10 års tjänst mindre än tusen omskrivningscykler.
Låt mig påminna dig om att tillverkaren lovar hundra tusen.

Lite om NOR vs NAND

Idag är naturligtvis NAND-minne mycket mer populärt, men jag skulle inte använda det för det här projektet: NAND, till skillnad från NOR, kräver nödvändigtvis användning av felkorrigeringskoder, en tabell med dåliga block, etc., och även benen på NAND-chips brukar vara mycket mer.

Nackdelarna med NOR inkluderar:

• liten volym (och följaktligen högt pris per megabyte);
• låg kommunikationshastighet (till stor del på grund av att ett seriellt gränssnitt används, vanligtvis SPI eller I2C);
• långsam radering (beroende på blockstorleken tar det från en bråkdel av en sekund till flera sekunder).

Det verkar som att det inte är något kritiskt för oss, så vi fortsätter.

Om detaljerna är intressanta har mikrokretsen valts at25df321a (Detta är dock oviktigt, det finns många analoger på marknaden som är kompatibla i pinout och kommandosystem; även om vi vill installera en mikrokrets från en annan tillverkare och/eller en annan storlek, kommer allt att fungera utan att ändra koda).

Jag använder drivrutinen inbyggd i Linux-kärnan; på Raspberry, tack vare stöd för enhetsträdöverlagring, är allt väldigt enkelt - du måste lägga den kompilerade överlagringen i /boot/overlays och ändra /boot/config.txt något.

Exempel på dts-fil

För att vara ärlig är jag inte säker på att det är skrivet utan fel, men det fungerar.

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

Och ytterligare en rad i config.txt

dtoverlay=at25:spimaxfrequency=50000000

Jag kommer att utelämna beskrivningen av att ansluta chipet till Raspberry Pi. Å ena sidan är jag ingen expert på elektronik, å andra sidan är allt här banalt även för mig: mikrokretsen har bara 8 ben, varav vi behöver jord, kraft, SPI (CS, SI, SO, SCK ); nivåerna är desamma som för Raspberry Pi, ingen extra ledning krävs - anslut bara de angivna 6 stiften.

Problem uttalande

Som vanligt går problemformuleringen igenom flera iterationer, och det verkar för mig att det är dags för nästa. Så låt oss sluta, sätta ihop det som redan har skrivits och förtydliga detaljerna som ligger kvar i skymundan.

Så vi har beslutat att loggen ska lagras i SPI NOR Flash.

Vad är NOR Flash för de som inte vet?

Detta är ett icke-flyktigt minne med vilket du kan göra tre operationer:

1. Läsning:
   Den vanligaste läsningen: vi överför adressen och läser så många byte som vi behöver;
2. rekord:
   Att skriva till NOR flash ser ut som en vanlig, men den har en egenhet: du kan bara ändra 1 till 0, men inte vice versa. Till exempel, om vi hade 0x55 i en minnescell, efter att ha skrivit 0x0f till den, kommer 0x05 redan att lagras där (se tabellen nedan);
3. Radera:
   Naturligtvis måste vi kunna göra den motsatta operationen - ändra 0 till 1, det är precis vad raderingsoperationen är till för. Till skillnad från de två första fungerar den inte med byte, utan med block (minsta raderingsblock i det valda chipet är 4kb). Radera förstör hela blocket och är det enda sättet att ändra 0 till 1. När man arbetar med flashminne måste man därför ofta anpassa datastrukturer till raderingsblockets gräns.
   Inspelning i NOR Flash:

Binära data

det var
01010101

Spelade in
00001111

Har blivit
00000101

Själva loggen representerar en sekvens av poster med variabel längd. Den typiska längden på en post är cirka 30 byte (även om poster som är flera kilobyte långa ibland förekommer). I det här fallet arbetar vi med dem helt enkelt som en uppsättning byte, men om du är intresserad används CBOR i posterna

Utöver loggen måste vi lagra viss "inställningsinformation", både uppdaterad och inte: ett visst enhets-ID, sensorkalibreringar, en flagga för "enheten är tillfälligt inaktiverad", etc.
Den här informationen är en uppsättning nyckel-värdeposter som också lagras i CBOR. Vi har inte mycket av denna information (högst några få kilobyte), och den uppdateras sällan.
I det följande kommer vi att kalla det sammanhang.

Om vi ​​kommer ihåg var denna artikel började är det mycket viktigt att säkerställa tillförlitlig datalagring och om möjligt kontinuerlig drift även vid hårdvarufel/datakorruption.

Vilka källor till problem kan övervägas?

• Stäng av under skriv/radering. Det här är från kategorin "det finns inget trick mot kofot."
  Information från diskussioner på stackexchange: när strömmen är avstängd när du arbetar med flash leder både radering (ställt till 1) och skriv (ställt till 0) till odefinierat beteende: data kan skrivas, delvis skrivas (säg, vi överförde 10 byte/80 bitar) , men ännu inte bara 45 bitar kan skrivas), är det också möjligt att vissa av bitarna kommer att vara i ett "mellanläge" (läsning kan ge både 0 och 1);
• Fel i själva flashminnet.
  BER, även om den är mycket låg, kan inte vara lika med noll;
• Bussfel
  Data som överförs via SPI är inte skyddad på något sätt, enkelbitsfel och synkroniseringsfel kan mycket väl uppstå - förlust eller infogning av bitar (vilket leder till massiv datakorruption);
• Andra fel/fel
  Fel i koden, hallonfel, främmande störningar...

Jag har formulerat de krav, vars uppfyllande enligt min mening är nödvändig för att säkerställa tillförlitlighet:

• poster måste läggas in i flashminnet omedelbart, fördröjda skrivningar beaktas inte - om ett fel uppstår måste det upptäckas och bearbetas så tidigt som möjligt - systemet ska om möjligt återställa sig från fel.
  (ett exempel från livet "hur det inte borde vara", som jag tror att alla har stött på: efter en nödstart är filsystemet "trasigt" och operativsystemet startar inte)

Idéer, förhållningssätt, reflektioner

När jag började tänka på det här problemet, flöt många idéer genom mitt huvud, till exempel:

• använd datakomprimering;
• använd smarta datastrukturer, till exempel lagra postrubriker separat från själva posterna, så att om det finns ett fel i någon post kan du läsa resten utan problem;
• använd bitfält för att kontrollera slutförandet av inspelningen när strömmen stängs av;
• lagra kontrollsummor för allt;
• använd någon typ av brusbeständig kodning.

Några av dessa idéer användes, vissa beslutades att överges. Låt oss gå i ordning.

Datakomprimering

Själva händelserna som vi registrerar i journalen är ganska lika och repeterbara ("kastade ett 5 rubelmynt", "tryckte på knappen för att ge växel", ...). Därför bör kompression vara ganska effektiv.

Kompressionskostnaden är obetydlig (vår processor är ganska kraftfull, även den första Pi hade en kärna med en frekvens på 700 MHz, nuvarande modeller har flera kärnor med en frekvens på över en gigahertz), växelkursen med lagringen är låg (flera megabyte per sekund) är storleken på posterna liten. I allmänhet, om komprimering har en inverkan på prestanda, kommer det bara att vara positivt. (absolut okritisk, bara konstaterar). Dessutom har vi inte riktigt inbäddad, men vanlig Linux - så implementeringen borde inte kräva mycket ansträngning (det räcker att bara länka biblioteket och använda flera funktioner från det).

En bit av loggen togs från en fungerande enhet (1.7 MB, 70 tusen poster) och kontrollerades först för kompressibilitet med hjälp av gzip, lz4, lzop, bzip2, xz, zstd tillgängliga på datorn.

• gzip, xz, zstd visade liknande resultat (40Kb).
  Jag blev förvånad över att den fashionabla xz visade sig här på nivån gzip eller zstd;
• lzip med standardinställningar gav något sämre resultat;
• lz4 och lzop visade inte särskilt bra resultat (150Kb);
• bzip2 visade ett överraskande bra resultat (18Kb).

Så data komprimeras väldigt bra.
Så (om vi inte hittar fatala brister) kommer det att bli kompression! Helt enkelt för att mer data får plats på samma flashenhet.

Låt oss tänka på nackdelarna.

Första problemet: vi har redan kommit överens om att varje skiva omedelbart måste gå att blinka. Vanligtvis samlar arkiveraren in data från inmatningsströmmen tills den bestämmer sig för att det är dags att skriva på helgen. Vi måste omedelbart ta emot ett komprimerat datablock och lagra det i ett icke-flyktigt minne.

Jag ser tre sätt:

1. Komprimera varje post med hjälp av ordbokskomprimering istället för algoritmerna som diskuterats ovan.
   Det är ett helt fungerande alternativ, men jag gillar det inte. För att säkerställa en mer eller mindre anständig nivå av komprimering måste ordboken "skräddarsys" till specifika data; varje förändring kommer att leda till att komprimeringsnivån faller katastrofalt. Ja, problemet kan lösas genom att skapa en ny version av ordboken, men detta är en huvudvärk - vi kommer att behöva lagra alla versioner av ordboken; i varje post måste vi ange med vilken version av ordboken den komprimerades...
2. Komprimera varje post med "klassiska" algoritmer, men oberoende av de andra.
   Komprimeringsalgoritmerna som övervägs är inte utformade för att fungera med poster av denna storlek (tiotals byte), komprimeringsförhållandet kommer helt klart att vara mindre än 1 (det vill säga att öka datavolymen istället för att komprimera);
3. Gör FLUSH efter varje inspelning.
   Många komprimeringsbibliotek har stöd för FLUSH. Detta är ett kommando (eller en parameter till komprimeringsproceduren), vid mottagandet bildar arkiveraren en komprimerad ström så att den kan användas för att återställa alla okomprimerad data som redan har tagits emot. En sådan analog sync i filsystem eller commit i sql.
   Vad som är viktigt är att efterföljande komprimeringsoperationer kommer att kunna använda den ackumulerade ordboken och komprimeringsförhållandet kommer inte att drabbas lika mycket som i den tidigare versionen.

Jag tycker att det är uppenbart att jag valde det tredje alternativet, låt oss titta på det mer i detalj.

Hittades bra artikel om FLUSH i zlib.

Jag gjorde ett knätest baserat på artikeln, tog 70 tusen loggposter från en riktig enhet, med en sidstorlek på 60Kb (vi återkommer till sidstorlek senare) mottagen:

Rå data
Komprimering gzip -9 (ingen FLUSH)
zlib med Z_PARTIAL_FLUSH
zlib med Z_SYNC_FLUSH

Volym, KB
1692
40
352
604

Vid första anblicken är priset som FLUSH bidrar med överdrivet högt, men i verkligheten har vi lite val - antingen att inte komprimera alls, eller att komprimera (och mycket effektivt) med FLUSH. Vi får inte glömma att vi har 70 tusen poster, redundansen som introduceras av Z_PARTIAL_FLUSH är bara 4-5 byte per post. Och kompressionsförhållandet visade sig vara nästan 5:1, vilket är mer än ett utmärkt resultat.

Det kan komma som en överraskning, men Z_SYNC_FLUSH är faktiskt ett mer effektivt sätt att göra FLUSH

När du använder Z_SYNC_FLUSH kommer de sista 4 byten av varje post alltid att vara 0x00, 0x00, 0xff, 0xff. Och om vi känner till dem behöver vi inte lagra dem, så den slutliga storleken är bara 324Kb.

Artikeln jag länkade till har en förklaring:

Ett nytt typ 0-block med tomt innehåll läggs till.

Ett typ 0-block med tomt innehåll består av:

• trebitars blockhuvudet;
• 0 till 7 bitar lika med noll, för att uppnå byte-inriktning;
• fyrabytesekvensen 00 00 FF FF.

Som du lätt kan se finns det i det sista blocket före dessa 4 byte från 3 till 10 nollbitar. Men praxis har visat att det faktiskt finns minst 10 nollbitar.

Det visar sig att sådana korta datablock vanligtvis (alltid?) kodas med ett block av typ 1 (fast block), som nödvändigtvis slutar med 7 nollbitar, vilket ger totalt 10-17 garanterade nollbitar (och resten kommer att vara noll med en sannolikhet på cirka 50 %).

Så på testdata finns det i 100 % av fallen en nollbyte före 0x00, 0x00, 0xff, 0xff, och i mer än en tredjedel av fallen finns det två nollbyte (kanske faktum är att jag använder binär CBOR, och när jag använder text JSON skulle block av typ 2 - dynamiskt block vara vanligare, respektive block utan ytterligare noll byte före 0x00, 0x00, 0xff, 0xff skulle påträffas).

Totalt, med hjälp av tillgängliga testdata, är det möjligt att passa in i mindre än 250Kb komprimerad data.

Du kan spara lite mer genom att jonglera lite: för närvarande ignorerar vi närvaron av några nollbitar i slutet av blocket, några bitar i början av blocket förändras inte heller...
Men sedan tog jag ett viljestarkt beslut att sluta, annars kunde jag i den här takten sluta med att utveckla mitt eget arkiv.

Totalt, från mina testdata, fick jag 3-4 byte per skrivning, kompressionsförhållandet visade sig vara mer än 6:1. Jag ska vara ärlig: jag förväntade mig inte ett sådant resultat; enligt min mening är allt bättre än 2:1 redan ett resultat som motiverar användningen av komprimering.

Allt är bra, men zlib (deflate) är fortfarande en arkaisk, välförtjänt och lite gammaldags komprimeringsalgoritm. Bara det faktum att de sista 32Kb av den okomprimerade dataströmmen används som en ordbok ser konstigt ut idag (det vill säga om något datablock är väldigt likt det som fanns i inmatningsströmmen för 40Kb sedan, då kommer det att börja arkiveras igen, och kommer inte att hänvisa till en tidigare händelse). I fashionabla moderna arkiverare mäts ordboksstorleken ofta i megabyte snarare än kilobyte.

Så vi fortsätter vår ministudie av arkivarier.

Därefter testade vi bzip2 (kom ihåg, utan FLUSH visade den ett fantastiskt kompressionsförhållande på nästan 100:1). Tyvärr fungerade det mycket dåligt med FLUSH, storleken på den komprimerade datan visade sig vara större än den okomprimerade datan.

Mina antaganden om orsakerna till misslyckandet

Libbz2 erbjuder bara ett spolningsalternativ, vilket verkar rensa ordboken (analogt med Z_FULL_FLUSH i zlib), det är inte tal om någon effektiv komprimering efter detta.

Och den sista som testades var zstd. Beroende på parametrarna komprimeras den antingen på nivån för gzip, men mycket snabbare eller bättre än gzip.

Tyvärr, med FLUSH fungerade det inte särskilt bra: storleken på den komprimerade datan var cirka 700Kb.

Я ställde en fråga på projektets github-sida fick jag ett svar att du borde räkna med upp till 10 byte servicedata för varje block med komprimerad data, vilket är nära de erhållna resultaten; det finns inget sätt att komma ikapp med deflate.

Jag bestämde mig för att sluta vid denna tidpunkt i mina experiment med arkiverare (låt mig påminna dig om att xz, lzip, lzo, lz4 inte visade sig ens på teststadiet utan FLUSH, och jag övervägde inte mer exotiska komprimeringsalgoritmer).

Låt oss återgå till arkiveringsproblem.

Det andra (som de säger i ordning, inte i värde) problemet är att den komprimerade datan är en enda ström, där det ständigt finns referenser till tidigare avsnitt. Om en del av komprimerad data skadas förlorar vi alltså inte bara det associerade blocket med okomprimerad data, utan även alla efterföljande.

Det finns ett sätt att lösa detta problem:

1. Förhindra att problemet uppstår - lägg till redundans till de komprimerade data, vilket gör att du kan identifiera och korrigera fel; vi ska prata om detta senare;
2. Minimera konsekvenserna om ett problem uppstår
   Vi har redan sagt tidigare att du kan komprimera varje datablock självständigt, och problemet kommer att försvinna av sig självt (skada på data från ett block kommer att leda till förlust av data endast för detta block). Detta är dock ett extremfall där datakomprimering kommer att vara ineffektiv. Den motsatta ytterligheten: använd alla 4 MB av vårt chip som ett enda arkiv, vilket kommer att ge oss utmärkt komprimering, men katastrofala konsekvenser i händelse av datakorruption.
   Ja, det krävs en kompromiss när det gäller tillförlitlighet. Men vi måste komma ihåg att vi utvecklar ett datalagringsformat för icke-flyktigt minne med extremt låg BER och en deklarerad datalagringstid på 20 år.

Under experimenten upptäckte jag att mer eller mindre märkbara förluster i komprimeringsnivån börjar på block med komprimerad data mindre än 10 KB i storlek.
Det nämndes tidigare att minnet som används är sökt, jag ser ingen anledning till att korrespondensen "en sida - ett block med komprimerad data" inte skulle användas.

Det vill säga den minsta rimliga sidstorleken är 16Kb (med en reserv för serviceinformation). En så liten sidstorlek medför dock betydande begränsningar för den maximala poststorleken.

Även om jag ännu inte förväntar mig poster större än några kilobyte i komprimerad form, bestämde jag mig för att använda 32Kb-sidor (för totalt 128 sidor per chip).

Sammanfattning:

• Vi lagrar data komprimerad med zlib (deflate);
• För varje post ställer vi in ​​Z_SYNC_FLUSH;
• För varje komprimerad post trimmar vi de efterföljande byten (t.ex. 0x00, 0x00, 0xff, 0xff); i rubriken anger vi hur många byte vi skär av;
• Vi lagrar data på 32Kb-sidor; det finns en enda ström av komprimerad data inuti sidan; På varje sida börjar vi komprimera igen.

Och innan jag avslutar med komprimering vill jag uppmärksamma er på att vi bara har några byte komprimerad data per post, så det är extremt viktigt att inte blåsa upp serviceinformationen, varje byte räknas här.

Lagra datahuvuden

Eftersom vi har poster med variabel längd måste vi på något sätt bestämma posternas placering/gränser.

Jag känner till tre tillvägagångssätt:

1. Alla poster lagras i en kontinuerlig ström, först finns det en posthuvud som innehåller längden, och sedan själva posten.
   I denna utföringsform kan både rubriker och data vara av variabel längd.
   I huvudsak får vi en enkellänkad lista som används hela tiden;
2. Rubriker och själva posterna lagras i separata strömmar.
   Genom att använda rubriker med konstant längd säkerställer vi att skador på en rubrik inte påverkar de andra.
   Ett liknande tillvägagångssätt används till exempel i många filsystem;
3. Poster lagras i en kontinuerlig ström, postgränsen bestäms av en viss markör (ett tecken/sekvens av tecken som är förbjudet inom datablock). Om det finns en markör inuti posten, så ersätter vi den med någon sekvens (escape den).
   Ett liknande tillvägagångssätt används till exempel i PPP-protokollet.

Jag ska illustrera.

Alternativ 1:

Allt är väldigt enkelt här: genom att veta längden på posten kan vi beräkna adressen till nästa rubrik. Så vi går igenom rubrikerna tills vi möter ett område fyllt med 0xff (fritt område) eller slutet av sidan.

Alternativ 2:

På grund av den varierande postlängden kan vi inte i förväg säga hur många poster (och därmed rubriker) vi kommer att behöva per sida. Du kan sprida rubrikerna och själva data över olika sidor, men jag föredrar ett annat tillvägagångssätt: vi placerar både rubrikerna och data på en sida, men rubrikerna (med konstant storlek) kommer från början av sidan, och data (av variabel längd) kommer från slutet. Så fort de "träffas" (det finns inte tillräckligt med ledigt utrymme för en ny post) anser vi denna sida vara komplett.

Alternativ 3:

Det finns inget behov av att lagra längden eller annan information om platsen för data i rubriken, det räcker med markörer som anger gränserna för posterna. Uppgifterna måste dock bearbetas vid skrivning/läsning.
Jag skulle använda 0xff som en markör (som fyller sidan efter radering), så det fria området kommer definitivt inte att behandlas som data.

Jämförelsetabell:

Alternativ 1
Alternativ 2
Alternativ 3

Feltolerans
-
+
+

densitet
+
-
+

Implementeringskomplexitet
*
**
**

Alternativ 1 har ett ödesdigert fel: om någon av huvuden är skadad, förstörs hela efterföljande kedja. De återstående alternativen låter dig återställa vissa data även i händelse av massiv skada.
Men här är det lämpligt att komma ihåg att vi bestämde oss för att lagra data i en komprimerad form, och så förlorar vi all data på sidan efter en "bruten" post, så även om det finns ett minus i tabellen, gör vi det inte ta hänsyn till det.

Kompakthet:

• i det första alternativet behöver vi bara lagra längden i rubriken, om vi använder heltal med variabel längd kan vi i de flesta fall klara oss med en byte;
• i det andra alternativet måste vi lagra startadressen och längden; posten måste ha en konstant storlek, jag uppskattar 4 byte per post (två byte för offset och två byte för längden);
• det tredje alternativet behöver bara ett tecken för att indikera starten av inspelningen, plus att själva inspelningen ökar med 1-2 % på grund av avskärmning. I allmänhet ungefär paritet med det första alternativet.

Till en början ansåg jag det andra alternativet som det viktigaste (och skrev till och med implementeringen). Jag övergav det först när jag äntligen bestämde mig för att använda komprimering.

En dag kanske jag fortfarande kommer att använda ett liknande alternativ. Om jag till exempel ska ta itu med datalagring för ett fartyg som färdas mellan jorden och Mars kommer det att finnas helt andra krav på tillförlitlighet, kosmisk strålning, ...

När det gäller det tredje alternativet: jag gav det två stjärnor för svårigheten att implementera helt enkelt för att jag inte gillar att bråka med skärmning, ändra längden i processen, etc. Ja, jag kanske är partisk, men jag måste skriva koden - varför tvinga dig själv att göra något du inte gillar.

Sammanfattning: Vi väljer lagringsalternativet i form av kedjor "header med längd - data av variabel längd" på grund av effektivitet och enkel implementering.

Använda bitfält för att övervaka framgången för skrivoperationer

Jag minns inte var jag fick idén nu, men det ser ut ungefär så här:
För varje post tilldelar vi flera bitar för att lagra flaggor.
Som vi sa tidigare, efter radering är alla bitar fyllda med 1:or, och vi kan ändra 1 till 0, men inte vice versa. Så för "flaggan är inte satt" använder vi 1, för "flaggan är inställd" använder vi 0.

Så här kan det se ut att lägga en skiva med variabel längd i flash:

1. Ställ in flaggan "längdinspelning har startat";
2. Anteckna längden;
3. Ställ in flaggan "datainspelning har startat";
4. Vi registrerar data;
5. Ställ in flaggan "inspelning avslutad".

Dessutom kommer vi att ha en "fel inträffade" flagga, för totalt 4 bitars flaggor.

I det här fallet har vi två stabila tillstånd "1111" - inspelningen har inte startat och "1000" - inspelningen lyckades; vid ett oväntat avbrott i inspelningsprocessen kommer vi att få mellanliggande tillstånd som vi sedan kan upptäcka och bearbeta.

Tillvägagångssättet är intressant, men det skyddar bara mot plötsliga strömavbrott och liknande fel, vilket naturligtvis är viktigt, men detta är långt ifrån den enda (eller ens huvud) orsaken till eventuella fel.

Sammanfattning: Låt oss gå vidare och leta efter en bra lösning.

Kontrollsummor

Kontrollsummor gör det också möjligt att försäkra sig (med rimlig sannolikhet) att vi läser exakt vad som borde ha skrivits. Och till skillnad från bitfälten som diskuterats ovan fungerar de alltid.

Om vi ​​överväger listan över potentiella problemkällor som vi diskuterade ovan, kan kontrollsumman känna igen ett fel oavsett dess ursprung (förutom kanske illvilliga utomjordingar - de kan också förfalska kontrollsumman).

Så om vårt mål är att verifiera att data är intakt är kontrollsummor en utmärkt idé.

Valet av algoritm för att beräkna kontrollsumman väckte inga frågor - CRC. Å ena sidan gör matematiska egenskaper det möjligt att fånga vissa typer av fel till 100 %, å andra sidan visar denna algoritm på slumpmässiga data att sannolikheten för kollisioner inte är mycket större än den teoretiska gränsen . Det är kanske inte den snabbaste algoritmen, och det är inte heller alltid det minsta när det gäller antalet kollisioner, men den har en mycket viktig egenskap: i de tester jag stötte på fanns det inga mönster där den tydligt misslyckades. Stabilitet är huvudkvaliteten i detta fall.

Exempel på en volymetrisk studie: Del 1, Del 2 (länkar till narod.ru, förlåt).

Uppgiften att välja en kontrollsumma är dock inte komplett, CRC är en hel familj av kontrollsummor. Du måste bestämma längden och sedan välja ett polynom.

Att välja kontrollsummans längd är inte en så enkel fråga som det verkar vid första anblicken.

Låt mig illustrera:
Låt oss ha sannolikheten för ett fel i varje byte och en idealisk kontrollsumma, låt oss beräkna det genomsnittliga antalet fel per miljon poster:

Data, byte
Kontrollsumma, byte
Oupptäckta fel
Falska feldetekteringar
Totalt falska positiva

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

Det verkar som att allt är enkelt - beroende på längden på data som skyddas, välj längden på kontrollsumman med ett minimum av felaktiga positiva - och tricket är i bagaget.

Det uppstår dock ett problem med korta kontrollsummor: även om de är bra på att upptäcka enstaka bitfel kan de med ganska stor sannolikhet acceptera helt slumpmässiga data som korrekta. Det fanns redan en artikel om Habré som beskrev problem i verkliga livet.

Därför, för att göra en slumpmässig kontrollsumma matchning nästan omöjlig, måste du använda kontrollsummor som är 32 bitar eller längre. (för längder större än 64 bitar används vanligtvis kryptografiska hashfunktioner).

Trots det faktum att jag skrev tidigare att vi måste spara utrymme med alla medel, kommer vi fortfarande att använda en 32-bitars kontrollsumma (16 bitar är inte tillräckligt, sannolikheten för en kollision är mer än 0.01%; och 24 bitar, eftersom de säg, är varken här eller där).

En invändning kan uppstå här: sparade vi varje byte när vi valde komprimering för att nu ge 4 byte på en gång? Skulle det inte vara bättre att inte komprimera eller lägga till en kontrollsumma? Naturligtvis inte, ingen kompression betyder inte, att vi inte behöver integritetskontroll.

När vi väljer ett polynom kommer vi inte att uppfinna hjulet på nytt, utan ta den nu populära CRC-32C.
Denna kod upptäcker 6 bitars fel på paket upp till 22 byte (kanske det vanligaste fallet för oss), 4 bitars fel på paket upp till 655 byte (också ett vanligt fall för oss), 2 eller vilket udda antal bitfel som helst på paket av någon rimlig längd.

Om någon är intresserad av detaljerna

Wikipedia-artikel om CRC.

Kodparametrar crc-32c på Koopmans hemsida — kanske den ledande CRC-specialisten på planeten.

В hans artikel finns en annan intressant kod, vilket ger något bättre parametrar för de paketlängder som är relevanta för oss, men jag ansåg inte skillnaden signifikant, och jag var kompetent nog att välja anpassad kod istället för den vanliga och väl undersökta.

Eftersom vår data är komprimerad uppstår också frågan: ska vi beräkna kontrollsumman för komprimerad eller okomprimerad data?

Argument för att beräkna kontrollsumman för okomprimerade data:

• Vi måste i slutändan kontrollera säkerheten för datalagring - så vi kontrollerar den direkt (samtidigt kommer eventuella fel i implementeringen av komprimering/dekompression, skador orsakade av trasigt minne, etc. att kontrolleras);
• Deflate-algoritmen i zlib har en ganska mogen implementering och bör inte falla med "krokiga" indata; dessutom kan den ofta självständigt upptäcka fel i ingångsströmmen, vilket minskar den totala sannolikheten för att oupptäcka ett fel (genomförde ett test med invertering av en enda bit i en kort post, zlib upptäckte ett fel i ungefär en tredjedel av fallen).

Argument mot att beräkna kontrollsumman för okomprimerade data:

• CRC är "skräddarsydd" specifikt för de få bitfel som är karakteristiska för flashminne (ett bitfel i en komprimerad ström kan orsaka en massiv förändring i utströmmen, där vi rent teoretiskt kan "fånga" en kollision);
• Jag gillar inte riktigt tanken på att skicka potentiellt trasiga data till dekomprimeraren, Vem vethur han kommer att reagera.

I detta projekt bestämde jag mig för att avvika från den allmänt accepterade praxis att lagra en kontrollsumma av okomprimerad data.

Sammanfattning: Vi använder CRC-32C, vi beräknar kontrollsumman från data i den form som de skrivs för att blinka (efter komprimering).

Redundans

Användningen av redundant kodning eliminerar naturligtvis inte dataförlust, men det kan avsevärt (ofta i många storleksordningar) minska sannolikheten för oåterkallelig dataförlust.

Vi kan använda olika typer av redundans för att rätta till fel.
Hamming-koder kan korrigera enbitsfel, Reed-Solomon-teckenkoder, flera kopior av data i kombination med kontrollsummor eller kodningar som RAID-6 kan hjälpa till att återställa data även i händelse av massiv korruption.
Till en början var jag engagerad i den utbredda användningen av felbeständig kodning, men sedan insåg jag att vi först måste ha en uppfattning om vilka fel vi vill skydda oss från, och sedan välja kodning.

Vi sa tidigare att fel måste fångas upp så snabbt som möjligt. Vid vilka punkter kan vi stöta på fel?

1. Oavslutad inspelning (av någon anledning vid tidpunkten för inspelningen stängdes strömmen av, hallonet frös, ...)
   Tyvärr, i händelse av ett sådant fel återstår bara att ignorera ogiltiga poster och betrakta data som förlorade;
2. Skrivfel (av någon anledning var det som skrevs till flashminnet inte det som skrevs)
   Vi kan omedelbart upptäcka sådana fel om vi gör en testavläsning direkt efter inspelningen;
3. Förvrängning av data i minnet under lagring;
4. Läsfel
   För att korrigera det, om kontrollsumman inte stämmer överens, räcker det att upprepa avläsningen flera gånger.

Det vill säga, endast fel av den tredje typen (spontan korruption av data under lagring) kan inte korrigeras utan felbeständig kodning. Det verkar som att sådana fel fortfarande är extremt osannolika.

Sammanfattning: det beslutades att överge redundant kodning, men om operationen visar felet i detta beslut, återgå till övervägande av problemet (med redan ackumulerad statistik om fel, vilket gör det möjligt att välja den optimala typen av kodning).

Andra

Naturligtvis tillåter inte formatet på artikeln oss att motivera varje bit i formatet (och min kraft har redan tagit slut), så jag ska kort gå igenom några punkter som inte berörts tidigare.

• Det beslutades att göra alla sidor "lika"
  Det vill säga att det inte blir några speciella sidor med metadata, separata trådar etc, utan istället en enda tråd som skriver om alla sidor i tur och ordning.
  Detta säkerställer jämnt slitage på sidorna, ingen enskild punkt av misslyckande, och jag bara gillar det;
• Det är absolut nödvändigt att tillhandahålla versionshantering av formatet.
  Ett format utan ett versionsnummer i rubriken är dåligt!
  Det räcker att lägga till ett fält med ett visst magiskt nummer (signatur) till sidhuvudet, vilket kommer att indikera versionen av formatet som används (Jag tror inte att det i praktiken kommer att finnas ens ett dussin av dem);
• Använd en rubrik med variabel längd för poster (som det finns många av), och försök göra den 1 byte lång i de flesta fall;
• För att koda längden på rubriken och längden på den trimmade delen av den komprimerade posten, använd binära koder med variabel längd.

Hjälpte mycket online generator Huffman koder. På bara några minuter kunde vi välja önskade koder med variabel längd.

Beskrivning av datalagringsformat

Byte-ordning

Fält som är större än en byte lagras i big-endian-format (nätverksbyteordning), det vill säga 0x1234 skrivs som 0x12, 0x34.

Paginering

Allt flashminne är uppdelat i lika stora sidor.

Standardsidstorleken är 32Kb, men inte mer än 1/4 av minneskretsens totala storlek (för ett 4MB-chip erhålls 128 sidor).

Varje sida lagrar data oberoende av de andra (det vill säga data på en sida refererar inte till data på en annan sida).

Alla sidor är numrerade i naturlig ordning (i stigande adressordning), börjar med nummer 0 (sida noll börjar på adress 0, första sidan börjar på 32Kb, andra sidan börjar på 64Kb, etc.)

Minneschippet används som en cyklisk buffert (ringbuffert), det vill säga att först skrivning går till sidnummer 0, sedan nummer 1, ..., när vi fyller sista sidan börjar en ny cykel och inspelningen fortsätter från sida noll .

Inne på sidan

I början av sidan lagras en sidhuvud på 4 byte, sedan en kontrollsumma för rubriken (CRC-32C), sedan lagras poster i formatet "huvud, data, kontrollsumma".

Sidtiteln (smutsig grön i diagrammet) består av:

• två-byte Magic Number-fält (också ett tecken på formatversionen)
  för den aktuella versionen av formatet beräknas det som 0xed00 ⊕ номер страницы;
• två-byte räknare "Sidversion" (minnes omskrivningscykelnummer).

Poster på sidan lagras i komprimerad form (deflate-algoritmen används). Alla poster på en sida komprimeras i en tråd (en gemensam ordbok används), och på varje ny sida börjar komprimeringen på nytt. Det vill säga, för att dekomprimera en post krävs alla tidigare poster från denna sida (och endast denna).

Varje post kommer att komprimeras med Z_SYNC_FLUSH-flaggan, och i slutet av den komprimerade strömmen kommer det att finnas 4 byte 0x00, 0x00, 0xff, 0xff, eventuellt föregås av ytterligare en eller två nollbyte.
Vi förkastar denna sekvens (4, 5 eller 6 byte lång) när vi skriver till flashminnet.

Posthuvudet är 1, 2 eller 3 byte som lagrar:

• en bit (T) som indikerar typen av post: 0 - kontext, 1 - log;
• ett fält med variabel längd (S) från 1 till 7 bitar, som definierar längden på rubriken och "svansen" som måste läggas till posten för dekomprimering;
• rekordlängd (L).

S-värdestabell:

S
Rubrikens längd, byte
Kasserade vid skrivning, 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)

Jag försökte illustrera, jag vet inte hur tydligt det blev:

Gult här indikerar T-fältet, vitt S-fältet, grönt L (längden på den komprimerade datan i byte), blå den komprimerade datan, röd den slutliga byten av den komprimerade datan som inte skrivs till flashminnet.

Således kan vi skriva postrubriker av den vanligaste längden (upp till 63+5 byte i komprimerad form) i en byte.

Efter varje post lagras en CRC-32C-kontrollsumma, i vilken det inverterade värdet av den föregående kontrollsumman används som initialvärde (init).

CRC har egenskapen "varaktighet", följande formel fungerar (plus eller minus bitinversion i processen): .
Det vill säga, i själva verket beräknar vi CRC för alla tidigare bytes med rubriker och data på den här sidan.

Direkt efter kontrollsumman är rubriken för nästa post.

Headern är utformad på ett sådant sätt att dess första byte alltid skiljer sig från 0x00 och 0xff (om vi istället för den första byten i headern stöter på 0xff, betyder det att detta är ett oanvänt område; 0x00 signalerar ett fel).

Exempel på algoritmer

Läser från flashminnet

Alla avläsningar kommer med en kontrollsumma.
Om kontrollsumman inte stämmer överens upprepas avläsningen flera gånger i hopp om att läsa rätt data.

(det här är vettigt, Linux cachelagrar inte läsningar från NOR Flash, testat)

Skriv till flashminnet

Vi registrerar uppgifterna.
Låt oss läsa dem.

Om den lästa datan inte stämmer överens med den skrivna datan fyller vi området med nollor och signalerar ett fel.

Förbereder en ny mikrokrets för drift

För initiering skrivs en rubrik med version 1 till den första (eller snarare noll) sidan.
Därefter skrivs det initiala sammanhanget till den här sidan (innehåller maskinens UUID och standardinställningar).

Det är allt, flashminnet är klart att användas.

Laddar maskinen

Vid laddning läses de första 8 byten av varje sida (huvud + CRC), sidor med ett okänt magiskt nummer eller en felaktig CRC ignoreras.
Från de "rätta" sidorna väljs sidor med den maximala versionen, och sidan med det högsta antalet tas från dem.
Den första posten läses, korrektheten av CRC och närvaron av "kontext"-flaggan kontrolleras. Om allt är bra anses denna sida vara aktuell. Om inte, rullar vi tillbaka till den föregående tills vi hittar en "live"-sida.
och på den hittade sidan läser vi alla poster, de som vi använder med "kontext"-flaggan.
Spara zlib-ordboken (den kommer att behövas för att lägga till den här sidan).

Det är allt, nedladdningen är klar, sammanhanget är återställt, du kan arbeta.

Lägga till en journalanteckning

Vi komprimerar posten med rätt ordbok, specificerar Z_SYNC_FLUSH. Vi ser om den komprimerade posten passar på den aktuella sidan.
Om det inte passar (eller om det fanns CRC-fel på sidan), starta en ny sida (se nedan).
Vi skriver ner posten och CRC. Om ett fel uppstår, starta en ny sida.

Ny sida

Vi väljer en gratissida med minsta antalet (vi anser att en gratissida är en sida med en felaktig kontrollsumma i rubriken eller med en mindre version än den nuvarande). Om det inte finns några sådana sidor, välj sidan med minsta antal bland de som har en version som är lika med den nuvarande.
Vi raderar den valda sidan. Vi kontrollerar innehållet med 0xff. Om något är fel, ta nästa gratissida osv.
Vi skriver en rubrik på den raderade sidan, den första posten är det aktuella tillståndet för sammanhanget, nästa är den oskrivna loggposten (om det finns en).

Formattillämplighet

Enligt min mening visade det sig vara ett bra format för att lagra eventuella mer eller mindre komprimerbara informationsströmmar (vanlig text, JSON, MessagePack, CBOR, eventuellt protobuf) i NOR Flash.

Naturligtvis är formatet "skräddarsytt" för SLC NOR Flash.

Den ska inte användas med media med hög BER som NAND eller MLC NOR (finns ett sådant minne ens till salu? Jag har bara sett det nämnt i arbeten om korrigeringskoder).

Dessutom bör den inte användas med enheter som har sin egen FTL: USB-flash, SD, MicroSD, etc (för sådant minne skapade jag ett format med en sidstorlek på 512 byte, en signatur i början av varje sida och unika postnummer - ibland var det möjligt att återställa all data från en "felaktig" flashenhet genom enkel sekventiell läsning).

Beroende på uppgifterna kan formatet användas utan ändringar på flashenheter från 128Kbit (16Kb) till 1Gbit (128MB). Om så önskas kan du använda den på större marker, men du behöver förmodligen justera sidstorleken (Men här uppstår redan frågan om ekonomisk genomförbarhet; priset för stora volymer NOR Flash är inte uppmuntrande).

Om någon tycker att formatet är intressant och vill använda det i ett öppet projekt, skriv, jag ska försöka hitta tiden, polera koden och lägga upp den på github.

Slutsats

Som du kan se visade sig formatet till slut vara enkelt och till och med tråkigt.

Det är svårt att spegla utvecklingen av min synvinkel i en artikel, men tro mig: från början ville jag skapa något sofistikerat, oförstörbart, som kan överleva till och med en kärnvapenexplosion i närheten. Men förnuftet (hoppas jag) vann ändå och gradvis skiftade prioriteringarna mot enkelhet och kompakthet.

Kan det vara så att jag hade fel? Ja visst. Det kan mycket väl visa sig till exempel att vi köpt ett parti av lågkvalitativa mikrokretsar. Eller av någon annan anledning kommer utrustningen inte att uppfylla tillförlitlighetsförväntningarna.

Har jag en plan för detta? Jag tror att du efter att ha läst artikeln inte tvivlar på att det finns en plan. Och inte ens ensam.

På en lite mer seriös notering utvecklades formatet både som ett fungerande alternativ och som en "provballong".

För tillfället fungerar allt på bordet bra, bokstavligen häromdagen kommer lösningen att distribueras (ungefär) på hundratals enheter, låt oss se vad som händer i "strid" operation (lyckligtvis hoppas jag att formatet gör att du kan upptäcka fel på ett tillförlitligt sätt; så att du kan samla in fullständig statistik). Om några månader kommer det att vara möjligt att dra slutsatser (och om du har otur, ännu tidigare).

Om, baserat på resultatet av användningen, allvarliga problem upptäcks och förbättringar krävs, kommer jag definitivt att skriva om det.

Litteratur

Jag ville inte göra en lång tråkig lista över begagnade verk; trots allt har alla Google.

Här bestämde jag mig för att lämna en lista över fynd som verkade särskilt intressanta för mig, men gradvis migrerade de direkt in i artikelns text, och ett objekt fanns kvar på listan:

1. Verktyg infgen från författaren zlib. Kan tydligt visa innehållet i deflate/zlib/gzip-arkiv. Om du har att göra med den interna strukturen för deflate (eller gzip)-formatet rekommenderar jag det starkt.

Källa: will.com