prehistòria

Hi ha màquines expenedores de disseny propi. Dins del Raspberry Pi i alguns cablejats en una placa independent. Es connecta un acceptor de monedes, un acceptor de bitllets, un terminal bancari... Tot està controlat per un programa d'autor. Tot l'historial de treball s'escriu en un registre d'una unitat flaix (MicroSD), que després es transmet a través d'Internet (mitjançant un mòdem USB) al servidor, on s'emmagatzema en una base de dades. La informació de vendes es carrega a 1c, també hi ha una interfície web senzilla per al seguiment, etc.

És a dir, la revista és vital: per a la comptabilitat (ingressos, vendes, etc.), el seguiment (tot tipus de fallades i altres circumstàncies de força major); Aquesta, es podria dir, és tota la informació que tenim sobre aquesta màquina.

problema

Les unitats flash es mostren com a dispositius molt poc fiables. Fallen amb una regularitat envejable. Això provoca tant temps d'inactivitat de la màquina com (si per algun motiu el registre no es pot transferir en línia) a pèrdua de dades.

Aquesta no és la primera experiència d'utilitzar unitats flash, abans hi havia un altre projecte amb més d'un centenar de dispositius, on la revista s'emmagatzemava en unitats flash USB, també hi havia problemes de fiabilitat, de vegades el nombre de les que fallaven en un mes va ser a desenes. Vam provar diferents unitats flaix, incloses les de marca amb memòria SLC, i alguns models són més fiables que altres, però la substitució de les unitats flaix no va resoldre radicalment el problema.

Atenció! Llegir llargament! Si no us interessa el "per què", sinó només el "com", podeu anar recte en fil articles

decisió

El primer que em ve al cap és: abandonar MicroSD, instal·lar, per exemple, un SSD i arrencar-lo. Teòricament és possible, probablement, però relativament car i no tan fiable (s'afegeix un adaptador USB-SATA; les estadístiques de fallades dels SSD de pressupost tampoc són encoratjadores).

El disc dur USB tampoc sembla una solució especialment atractiva.

Per tant, vam arribar a aquesta opció: deixar l'arrencada des de MicroSD, però utilitzar-los en mode de només lectura i emmagatzemar el registre d'operacions (i altra informació exclusiva d'una peça concreta de maquinari: número de sèrie, calibracions del sensor, etc.) en un altre lloc. .

El tema de l'FS de només lectura per als gerds ja s'ha estudiat per dins i per fora, no em detendré en els detalls de la implementació en aquest article (però si hi ha interès, potser escriuré un mini-article sobre aquest tema). L'únic punt que m'agradaria destacar és que tant per l'experiència personal com per les revisions dels que ja l'han implementat, hi ha un guany en fiabilitat. Sí, és impossible desfer-se completament de les avaries, però és molt possible reduir-ne significativament la freqüència. I les targetes s'estan unificant, cosa que fa que la substitució sigui molt més fàcil per al personal de servei.

Maquinari

No hi havia cap dubte sobre l'elecció del tipus de memòria: NOR Flash.
Arguments:

• connexió senzilla (la majoria de vegades el bus SPI, que ja tens experiència utilitzant, de manera que no es preveuen problemes de maquinari);
• preu ridícul;
• protocol operatiu estàndard (la implementació ja està al nucli de Linux, si voleu, podeu agafar-ne un de tercer, que també hi estigui present, o fins i tot escriure el vostre, afortunadament tot és senzill);
• fiabilitat i recursos:
  d'un full de dades típic: les dades s'emmagatzemen durant 20 anys, 100000 cicles d'esborrat per a cada bloc;
  de fonts de tercers: BER extremadament baix, no postula la necessitat de codis de correcció d'errors (algunes obres consideren ECC per NOR, però normalment encara volen dir MLC NOR; això també passa).

Estimem els requisits de volum i recursos.

M'agradaria que es garanteixin que les dades es guardin durant diversos dies. Això és necessari perquè en cas de problemes de comunicació no es perdi l'historial de vendes. Ens centrarem en 5 dies, durant aquest període (fins i tot tenint en compte els caps de setmana i festius) el problema es pot resoldre.

Actualment recollim uns 100 kb de registres per dia (3-4 mil entrades), però a poc a poc aquesta xifra va creixent: el detall augmenta, s'hi afegeixen nous esdeveniments. A més, de vegades hi ha ràfegues (algun sensor comença a enviar correu brossa amb falsos positius, per exemple). Calcularem per a 10 mil registres 100 bytes cadascun: megabytes per dia.

En total, surten 5 MB de dades netes (ben comprimides). Més a ells (estimació aproximada) 1 MB de dades de servei.

És a dir, necessitem un xip de 8MB si no fem servir compressió, o 4MB si el fem servir. Nombres força realistes per a aquest tipus de memòria.

Pel que fa al recurs: si planifiquem que tota la memòria es reescrigui no més d'una vegada cada 5 dies, després de 10 anys de servei obtenim menys de mil cicles de reescriptura.
Deixeu-me recordar que el fabricant promet cent mil.

Una mica sobre NOR vs NAND

Avui, per descomptat, la memòria NAND és molt més popular, però no l'utilitzaria per a aquest projecte: NAND, a diferència de NOR, requereix necessàriament l'ús de codis de correcció d'errors, una taula de blocs defectuosos, etc., i també les potes de Els xips NAND solen ser molt més.

Els desavantatges de NOR inclouen:

• volum petit (i, en conseqüència, preu elevat per megabyte);
• baixa velocitat de comunicació (en gran part pel fet que s'utilitza una interfície sèrie, normalment SPI o I2C);
• esborrat lent (segons la mida del bloc, triga des d'una fracció de segon a uns quants segons).

Sembla que no hi ha res crític per a nosaltres, així que continuem.

Si els detalls són interessants, s'ha seleccionat el microcircuit at25df321a (no obstant això, això no té importància, hi ha molts anàlegs al mercat que són compatibles en pinout i sistema de comandament; encara que vulguem instal·lar un microcircuit d'un altre fabricant i/o una mida diferent, tot funcionarà sense canviar el codi).

Utilitzo el controlador integrat al nucli de Linux; a Raspberry, gràcies al suport de superposició de l'arbre del dispositiu, tot és molt senzill: cal posar la superposició compilada a /boot/overlays i modificar lleugerament /boot/config.txt.

Exemple de fitxer dts

Per ser sincer, no estic segur que estigui escrit sense errors, però funciona.

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

I una altra línia a config.txt

dtoverlay=at25:spimaxfrequency=50000000

Ometré la descripció de la connexió del xip al Raspberry Pi. D'una banda, no sóc un expert en electrònica, d'altra banda, aquí tot és banal fins i tot per a mi: el microcircuit només té 8 potes, de les quals necessitem terra, potència, SPI (CS, SI, SO, SCK). ); els nivells són els mateixos que els del Raspberry Pi, no es requereix cap cablejat addicional: només cal connectar els 6 pins indicats.

Declaració de problemes

Com és habitual, l'enunciat del problema passa per diverses iteracions i em sembla que és hora de la següent. Per tant, aturem-nos, ajuntem el que ja està escrit i aclarim els detalls que queden a l'ombra.

Per tant, hem decidit que el registre s'emmagatzemarà a SPI NOR Flash.

Què és NOR Flash per a aquells que no ho saben?

Aquesta és una memòria no volàtil amb la qual podeu fer tres operacions:

1. Lectura:
   La lectura més habitual: transmetem l'adreça i llegim tants bytes com necessitem;
2. Rècord:
   Escriure a NOR flash sembla una cosa normal, però té una particularitat: només pots canviar d'1 a 0, però no a l'inrevés. Per exemple, si teníem 0x55 en una cel·la de memòria, després d'escriure-hi 0x0f, 0x05 ja s'emmagatzemarà allà (vegeu la taula a continuació);
3. Esborra:
   Per descomptat, hem de ser capaços de fer l'operació contrària: canvieu de 0 a 1, per això és exactament l'operació d'esborrar. A diferència dels dos primers, no funciona amb bytes, sinó amb blocs (el bloc d'esborrat mínim al xip seleccionat és de 4 kb). Esborrar destrueix tot el bloc i és l'única manera de canviar de 0 a 1. Per tant, quan es treballa amb memòria flaix, sovint heu d'alinear les estructures de dades amb el límit del bloc d'esborrar.
   Gravació en NOR Flash:

Dades binàries

Va ser
01010101

Gravat
00001111

S'ha convertit
00000101

El propi registre representa una seqüència de registres de longitud variable. La longitud típica d'un registre és d'uns 30 bytes (tot i que de vegades es produeixen registres que tenen diversos kilobytes de longitud). En aquest cas, treballem amb ells simplement com un conjunt de bytes, però, si us interessa, s'utilitza CBOR dins dels registres.

A més del registre, hem d'emmagatzemar alguna informació de "configuració", tant actualitzada com no: un determinat identificador del dispositiu, calibracions del sensor, un indicador "dispositiu està temporalment desactivat", etc.
Aquesta informació és un conjunt de registres de valor-clau, també emmagatzemats a CBOR. No tenim molta d'aquesta informació (uns quants kilobytes com a màxim) i s'actualitza amb poca freqüència.
En el que segueix l'anomenarem context.

Si recordem on va començar aquest article, és molt important garantir un emmagatzematge de dades fiable i, si és possible, un funcionament continu fins i tot en cas de fallades de maquinari/corrupció de dades.

Quines fonts de problemes es poden considerar?

• Apagueu durant les operacions d'escriptura/esborrat. Això és de la categoria de "no hi ha cap truc contra la palanca".
  Informació de discussions a stackexchange: quan s'apaga l'alimentació mentre es treballa amb flash, tant l'esborrat (establert a 1) com l'escriptura (establert a 0) donen lloc a un comportament no definit: les dades es poden escriure, escriure parcialment (per exemple, hem transferit 10 bytes/80 bits). , però encara no només es poden escriure 45 bits), també és possible que alguns dels bits estiguin en un estat “intermedi” (la lectura pot produir tant 0 com 1);
• Errors a la pròpia memòria flash.
  El BER, encara que molt baix, no pot ser igual a zero;
• Errors de bus
  Les dades transmeses mitjançant SPI no estan protegides de cap manera; es poden produir tant errors d'un bit com errors de sincronització: pèrdua o inserció de bits (que condueix a una distorsió massiva de les dades);
• Altres errors/errors
  Errors en el codi, errors de Raspberry, interferències alienígenes...

He formulat els requisits, el compliment dels quals, al meu entendre, és necessari per garantir la fiabilitat:

• els registres han d'anar a la memòria flash immediatament, no es tenen en compte les escriptures retardades; - si es produeix un error, s'ha de detectar i processar el més aviat possible; - el sistema s'ha de recuperar, si és possible, dels errors.
  (un exemple de la vida "com no hauria de ser", que crec que tothom s'ha trobat: després d'un reinici d'emergència, el sistema de fitxers està "trencat" i el sistema operatiu no arrenca)

Idees, plantejaments, reflexions

Quan vaig començar a pensar en aquest problema, em van passar pel cap moltes idees, per exemple:

• utilitzar la compressió de dades;
• Utilitzeu estructures de dades intel·ligents, per exemple, emmagatzemant les capçaleres dels registres per separat dels mateixos registres, de manera que si hi ha un error en qualsevol registre, podeu llegir la resta sense cap problema;
• utilitzar camps de bits per controlar la finalització de l'enregistrament quan s'apaga l'alimentació;
• emmagatzemar sumes de control per a tot;
• utilitzar algun tipus de codificació resistent al soroll.

Algunes d'aquestes idees es van utilitzar, mentre que d'altres es van decidir abandonar. Anem en ordre.

Compressió de dades

Els propis esdeveniments que registrem al diari són força similars i repetibles ("va llançar una moneda de 5 rubles", "va pressionar el botó per donar canvi", ...). Per tant, la compressió hauria de ser força eficaç.

La sobrecàrrega de compressió és insignificant (el nostre processador és bastant potent, fins i tot el primer Pi tenia un nucli amb una freqüència de 700 MHz, els models actuals tenen diversos nuclis amb una freqüència superior a un gigahertz), el tipus de canvi amb l'emmagatzematge és baix (diversos megabytes per segon), la mida dels registres és petita. En general, si la compressió té un impacte en el rendiment, només serà positiu. (absolutament acrític, només afirmar). A més, no tenim Linux incrustat real, sinó regular, de manera que la implementació no hauria de requerir gaire esforç (n'hi ha prou amb enllaçar la biblioteca i utilitzar-ne diverses funcions).

Es va extreure una part del registre d'un dispositiu en funcionament (1.7 MB, 70 mil entrades) i primer es va comprovar la compressibilitat mitjançant gzip, lz4, lzop, bzip2, xz, zstd disponibles a l'ordinador.

• gzip, xz, zstd van mostrar resultats similars (40Kb).
  Em va sorprendre que el xz de moda es mostrés aquí a nivell de gzip o zstd;
• lzip amb la configuració predeterminada va donar resultats lleugerament pitjors;
• lz4 i lzop no van mostrar molt bons resultats (150Kb);
• bzip2 va mostrar un resultat sorprenentment bo (18Kb).

Per tant, les dades es comprimeixen molt bé.
Així que (si no trobem defectes fatals) hi haurà compressió! Simplement perquè hi poden cabre més dades a la mateixa unitat flaix.

Pensem en els inconvenients.

Primer problema: ja hem acordat que tots els registres han de passar immediatament a flash. Normalment, l'arxivador recull dades del flux d'entrada fins que decideix que és hora d'escriure el cap de setmana. Hem de rebre immediatament un bloc de dades comprimit i emmagatzemar-lo a la memòria no volàtil.

Hi veig tres maneres:

1. Comprimiu cada registre mitjançant la compressió del diccionari en lloc dels algorismes comentats anteriorment.
   És una opció totalment funcional, però no m'agrada. Per garantir un nivell de compressió més o menys decent, el diccionari s'ha d'"adaptar" a dades específiques; qualsevol canvi farà que el nivell de compressió caigui catastròficament. Sí, el problema es pot resoldre mitjançant la creació d'una nova versió del diccionari, però això és un mal de cap: haurem d'emmagatzemar totes les versions del diccionari; a cada entrada haurem d'indicar amb quina versió del diccionari s'ha comprimit...
2. Comprimiu cada registre utilitzant algorismes "clàssics", però independentment dels altres.
   Els algorismes de compressió considerats no estan dissenyats per treballar amb registres d'aquesta mida (desenes de bytes), la relació de compressió serà clarament inferior a 1 (és a dir, augmentant el volum de dades en lloc de comprimir-les);
3. Feu FLUSH després de cada gravació.
   Moltes biblioteques de compressió tenen suport per a FLUSH. Aquesta és una ordre (o un paràmetre del procediment de compressió), en rebre la qual l'arxivador forma un flux comprimit perquè es pugui utilitzar per restaurar tots dades sense comprimir que ja s'han rebut. Un anàleg així sync en sistemes de fitxers o commit en sql.
   El que és important és que les operacions de compressió posteriors podran utilitzar el diccionari acumulat i la relació de compressió no patirà tant com en la versió anterior.

Crec que és evident que vaig triar la tercera opció, mirem-la amb més detall.

Trobat gran article sobre FLUSH a zlib.

Vaig fer una prova de genoll basada en l'article, vaig prendre 70 mil entrades de registre des d'un dispositiu real, amb una mida de pàgina de 60Kb (tornarem a la mida de la pàgina més tard) rebut:

Dades primeres
Compressió gzip -9 (no FLUSH)
zlib amb Z_PARTIAL_FLUSH
zlib amb Z_SYNC_FLUSH

Volum, KB
1692
40
352
604

A primera vista, el preu aportat per FLUSH és excessivament elevat, però en realitat tenim poca opció: no comprimir gens o comprimir (i molt eficaçment) amb FLUSH. No hem d'oblidar que tenim 70 mil registres, la redundància introduïda per Z_PARTIAL_FLUSH és de només 4-5 bytes per registre. I la relació de compressió va resultar ser gairebé 5:1, que és més que un excel·lent resultat.

Pot ser una sorpresa, però Z_SYNC_FLUSH és en realitat una manera més eficient de fer FLUSH

Quan utilitzeu Z_SYNC_FLUSH, els darrers 4 bytes de cada entrada sempre seran 0x00, 0x00, 0xff, 0xff. I si els coneixem, no els hem d'emmagatzemar, de manera que la mida final és només de 324Kb.

L'article al qual he enllaçat té una explicació:

S'afegeix un bloc de tipus 0 nou amb contingut buit.

Un bloc de tipus 0 amb contingut buit consta de:

• la capçalera del bloc de tres bits;
• 0 a 7 bits iguals a zero, per aconseguir l'alineació de bytes;
• la seqüència de quatre bytes 00 00 FF FF.

Com podeu veure fàcilment, a l'últim bloc abans d'aquests 4 bytes hi ha de 3 a 10 bits zero. Tanmateix, la pràctica ha demostrat que en realitat hi ha almenys 10 bits zero.

Resulta que aquests blocs curts de dades solen ser (sempre?) codificats mitjançant un bloc de tipus 1 (bloc fix), que necessàriament acaba amb 7 bits zero, donant un total de 10-17 bits zero garantits (i la resta sigui zero amb una probabilitat d'aproximadament el 50%).

Així, a les dades de prova, en el 100% dels casos hi ha un byte zero abans de 0x00, 0x00, 0xff, 0xff i en més d'un terç dels casos hi ha dos bytes zero. (potser el fet és que faig servir CBOR binari, i quan utilitzo el text JSON, els blocs de tipus 2: bloc dinàmic serien més comuns, respectivament, blocs sense zero bytes addicionals abans que es trobaran 0x00, 0x00, 0xff, 0xff).

En total, utilitzant les dades de prova disponibles, és possible encaixar en menys de 250 Kb de dades comprimides.

Podeu estalviar una mica més fent malabars: de moment ignorem la presència d'uns pocs bits zero al final del bloc, uns quants bits al començament del bloc tampoc canvien...
Però aleshores vaig prendre la decisió decidida d'aturar-me, sinó a aquest ritme podria acabar desenvolupant el meu propi arxiu.

En total, de les meves dades de prova, vaig rebre 3-4 bytes per escriptura, la relació de compressió va resultar ser més de 6:1. Seré sincer: no esperava un resultat així; al meu entendre, qualsevol cosa millor que 2:1 ja és un resultat que justifica l'ús de la compressió.

Tot està bé, però zlib (desinflat) segueix sent un algorisme de compressió arcaic, merescut i una mica passat de moda. El simple fet que els últims 32 Kb del flux de dades sense comprimir s'utilitzin com a diccionari sembla estrany avui (és a dir, si algun bloc de dades és molt semblant al que hi havia al flux d'entrada fa 40 Kb, es començarà a arxivar de nou, i no es referirà a una ocurrència anterior). En els arxivadors moderns de moda, la mida del diccionari sovint es mesura en megabytes en lloc de quilobytes.

Així que continuem el nostre mini-estudi d'arxivistes.

A continuació, vam provar bzip2 (recordeu que sense FLUSH mostrava una relació de compressió fantàstica de gairebé 100:1). Malauradament, amb FLUSH va funcionar molt malament; la mida de les dades comprimides va resultar ser més gran que les dades no comprimides.

Les meves suposicions sobre els motius del fracàs

Libbz2 ofereix només una opció de neteja, que sembla esborrar el diccionari (anàloga a Z_FULL_FLUSH a zlib); després d'això no es parla de cap compressió efectiva.

I l'últim que es va provar va ser zstd. Segons els paràmetres, es comprimeix a nivell de gzip, però molt més ràpid, o millor que gzip.

Per desgràcia, amb FLUSH no va funcionar molt bé: la mida de les dades comprimides era d'uns 700Kb.

Я va fer una pregunta a la pàgina github del projecte, vaig rebre una resposta que hauríeu de comptar amb fins a 10 bytes de dades de servei per a cada bloc de dades comprimides, que s'aproxima als resultats obtinguts; no hi ha manera de posar-vos al dia amb el desinflat.

Vaig decidir aturar-me en aquest punt dels meus experiments amb arxivadors (permeteu-vos recordar que xz, lzip, lzo, lz4 no es van mostrar ni tan sols en l'etapa de prova sense FLUSH, i no vaig considerar algorismes de compressió més exòtics).

Tornem als problemes d'arxivament.

El segon problema (com diuen en ordre, no en valor) és que les dades comprimides són un sol flux, en el qual hi ha constantment referències a seccions anteriors. Així, si una secció de dades comprimides està danyada, perdem no només el bloc associat de dades no comprimides, sinó també tots els següents.

Hi ha un enfocament per resoldre aquest problema:

1. Eviteu que es produeixi el problema: afegiu redundància a les dades comprimides, que us permetran identificar i corregir errors; d'això en parlarem més endavant;
2. Minimitzar les conseqüències si es produeix un problema
   Ja hem dit anteriorment que podeu comprimir cada bloc de dades de manera independent i el problema desapareixerà per si mateix (el dany a les dades d'un bloc provocarà la pèrdua de dades només per a aquest bloc). Tanmateix, aquest és un cas extrem en què la compressió de dades serà ineficaç. L'extrem contrari: utilitzar tots els 4MB del nostre xip com a arxiu únic, la qual cosa ens donarà una compressió excel·lent, però conseqüències catastròfiques en cas de corrupció de dades.
   Sí, cal un compromís en termes de fiabilitat. Però hem de recordar que estem desenvolupant un format d'emmagatzematge de dades per a memòria no volàtil amb un BER extremadament baix i un període d'emmagatzematge de dades declarat de 20 anys.

Durant els experiments, vaig descobrir que les pèrdues més o menys notables en el nivell de compressió comencen en blocs de dades comprimides de menys de 10 KB de mida.
Abans es va esmentar que la memòria utilitzada està paginada; no veig cap raó per la qual no s'hagi d'utilitzar la correspondència "una pàgina - un bloc de dades comprimides".

És a dir, la mida mínima raonable de la pàgina és de 16 Kb (amb una reserva per a la informació del servei). Tanmateix, una mida de pàgina tan petita imposa restriccions importants a la mida màxima del registre.

Tot i que encara no espero registres més grans d'uns quants kilobytes en forma comprimida, vaig decidir utilitzar pàgines de 32 Kb (per a un total de 128 pàgines per xip).

Resum:

• Emmagatzemem dades comprimides mitjançant zlib (deflate);
• Per a cada entrada establim Z_SYNC_FLUSH;
• Per a cada registre comprimit, retallem els bytes finals (p. ex. 0x00, 0x00, 0xff, 0xff); a la capçalera indiquem quants bytes hem tallat;
• Emmagatzemem les dades en pàgines de 32Kb; hi ha un sol flux de dades comprimides dins de la pàgina; A cada pàgina tornem a començar la compressió.

I, abans d'acabar amb la compressió, m'agradaria cridar la vostra atenció sobre el fet que només tenim uns quants bytes de dades comprimides per registre, per la qual cosa és molt important no inflar la informació del servei, aquí cada byte compta.

Emmagatzematge de capçaleres de dades

Com que tenim registres de longitud variable, hem de determinar d'alguna manera la ubicació/límits dels registres.

Conec tres enfocaments:

1. Tots els registres s'emmagatzemen en un flux continu, primer hi ha una capçalera del registre que conté la longitud i després el propi registre.
   En aquesta realització, tant les capçaleres com les dades poden ser de longitud variable.
   Essencialment, obtenim una llista enllaçada individualment que s'utilitza tot el temps;
2. Les capçaleres i els propis registres s'emmagatzemen en fluxos separats.
   En utilitzar capçaleres de longitud constant, ens assegurem que els danys a una capçalera no afecten les altres.
   Un enfocament similar s'utilitza, per exemple, en molts sistemes de fitxers;
3. Els registres s'emmagatzemen en un flux continu, el límit del registre està determinat per un determinat marcador (un caràcter/seqüència de caràcters que està prohibit dins dels blocs de dades). Si hi ha un marcador dins del registre, llavors el substituïm per alguna seqüència (escapa'l).
   Un enfocament similar s'utilitza, per exemple, en el protocol PPP.

Il·lustraré.

Opció 1:

Aquí tot és molt senzill: sabent la durada del registre, podem calcular l'adreça de la següent capçalera. Així que ens movem pels encapçalaments fins que trobem una àrea plena de 0xff (àrea lliure) o el final de la pàgina.

Opció 2:

A causa de la longitud variable del registre, no podem dir per endavant quants registres (i, per tant, capçaleres) necessitarem per pàgina. Podeu repartir les capçaleres i les dades en diferents pàgines, però prefereixo un enfocament diferent: col·loquem tant les capçaleres com les dades en una pàgina, però les capçaleres (de mida constant) provenen del principi de la pàgina i les dades (de longitud variable) provenen del final. Tan bon punt es "reuneixin" (no hi ha prou espai lliure per a una nova entrada), considerem aquesta pàgina completa.

Opció 3:

No cal emmagatzemar la longitud ni cap altra informació sobre la ubicació de les dades a la capçalera; n'hi ha prou amb marcadors que indiquen els límits dels registres. No obstant això, les dades s'han de processar en escriure/llegir.
Jo utilitzaria 0xff com a marcador (que omple la pàgina després d'esborrar), de manera que l'àrea lliure definitivament no es tractarà com a dades.

Taula de comparació:

Opció 1
Opció 2
Opció 3

Tolerància a errors
-
+
+

Compactabilitat
+
-
+

Complexitat de la implementació
*
**
**

L'opció 1 té un defecte fatal: si alguna de les capçaleres està danyada, es destrueix tota la cadena posterior. Les opcions restants us permeten recuperar algunes dades fins i tot en cas de danys massius.
Però aquí convé recordar que vam decidir emmagatzemar les dades en forma comprimida i, per tant, perdem totes les dades de la pàgina després d'un registre "trencat", de manera que encara que hi hagi un negatiu a la taula, no tenir-ho en compte.

Compactetat:

• en la primera opció, només hem d'emmagatzemar la longitud a la capçalera; si fem servir nombres enters de longitud variable, en la majoria dels casos ens podem arreglar amb un byte;
• a la segona opció hem d'emmagatzemar l'adreça inicial i la longitud; el registre ha de tenir una mida constant, estimo 4 bytes per registre (dos bytes per al desplaçament i dos bytes per a la longitud);
• la tercera opció només necessita un caràcter per indicar l'inici de l'enregistrament, a més de la pròpia gravació augmentarà un 1-2% a causa del blindatge. En general, aproximadament paritat amb la primera opció.

Inicialment, vaig considerar la segona opció com a principal (i fins i tot vaig escriure la implementació). El vaig abandonar només quan finalment vaig decidir utilitzar la compressió.

Potser algun dia encara utilitzaré una opció semblant. Per exemple, si he de fer front a l'emmagatzematge de dades per a un vaixell que viatja entre la Terra i Mart, hi haurà requisits completament diferents de fiabilitat, radiació còsmica, ...

Pel que fa a la tercera opció: li vaig donar dues estrelles per la dificultat d'implementació simplement perquè no m'agrada fer-me malbé amb el blindatge, canviar la longitud en el procés, etc. Sí, potser sóc esbiaixat, però hauré d'escriure el codi: per què obligar-te a fer alguna cosa que no t'agrada?

Resum: Triem l'opció d'emmagatzematge en forma de cadenes "capçalera amb longitud - dades de longitud variable" per eficiència i facilitat d'implementació.

Ús de camps de bits per supervisar l'èxit de les operacions d'escriptura

Ara no recordo d'on vaig treure la idea, però sembla una cosa així:
Per a cada entrada, assignem diversos bits per emmagatzemar banderes.
Com hem dit anteriorment, després d'esborrar tots els bits s'omplen amb 1, i podem canviar d'1 a 0, però no a l'inrevés. Així que per a "la bandera no està establerta" fem servir 1, per a "la bandera està establerta" fem servir 0.

A continuació s'explica com podria semblar posar un registre de longitud variable al flash:

1. Establiu la marca "La gravació de la durada ha començat";
2. Enregistrar la durada;
3. Establiu la marca "La gravació de dades ha començat";
4. Enregistrem les dades;
5. Establiu la marca "enregistrament finalitzat".

A més, tindrem un senyalador "s'ha produït un error", per a un total de senyaladors de 4 bits.

En aquest cas, tenim dos estats estables "1111" - la gravació no ha començat i "1000" - la gravació va tenir èxit; en cas d'interrupció inesperada del procés d'enregistrament, rebrem estats intermedis, que després podrem detectar i processar.

L'enfocament és interessant, però només protegeix contra talls sobtats d'electricitat i fallades similars, cosa que, per descomptat, és important, però això està lluny de ser l'únic (o fins i tot el principal) motiu de possibles errors.

Resum: Seguim a la recerca d'una bona solució.

Sumes de control

Les sumes de control també permeten assegurar-nos (amb una probabilitat raonable) que estem llegint exactament el que s'hauria d'haver escrit. I, a diferència dels camps de bits comentats anteriorment, sempre funcionen.

Si considerem la llista de possibles fonts de problemes que hem comentat anteriorment, aleshores la suma de comprovació és capaç de reconèixer un error independentment del seu origen (excepte, potser, per als alienígenes maliciosos: també poden forjar la suma de control).

Per tant, si el nostre objectiu és verificar que les dades estan intactes, les sumes de control són una gran idea.

L'elecció de l'algoritme per calcular la suma de control no va plantejar cap pregunta: CRC. D'una banda, les propietats matemàtiques permeten captar certs tipus d'errors al 100%; d'altra banda, en dades aleatòries aquest algorisme sol mostrar la probabilitat de col·lisions no molt superior al límit teòric. . Potser no és l'algoritme més ràpid, ni sempre és el mínim pel que fa al nombre de col·lisions, però té una qualitat molt important: a les proves que em vaig trobar, no hi havia patrons en què va fallar clarament. L'estabilitat és la qualitat principal en aquest cas.

Exemple d'estudi volumètric: part de 1, part de 2 (enllaços a narod.ru, ho sento).

Tanmateix, la tasca de seleccionar una suma de comprovació no està completa; CRC és tota una família de suma de comprovació. Heu de decidir la longitud i després triar un polinomi.

Escollir la longitud de la suma de control no és una pregunta tan senzilla com sembla a primera vista.

Permeteu-me il·lustrar:
Tinguem la probabilitat d'error a cada byte i una suma de control ideal, calculem el nombre mitjà d'errors per milió de registres:

Dades, byte
Suma de comprovació, byte
Errors no detectats
Detecció d'errors falsos
Total de falsos positius

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

Sembla que tot és senzill -segons la longitud de les dades que es protegeix, trieu la durada de la suma de control amb un mínim de positius incorrectes- i el truc està a la bossa.

Tanmateix, sorgeix un problema amb les sumes de control curtes: tot i que són bons per detectar errors d'un sol bit, poden acceptar dades completament aleatòries com a correctes amb una probabilitat bastant alta. Ja hi havia un article sobre Habré descrivint problema a la vida real.

Per tant, per fer que una coincidència de suma de comprovació aleatòria sigui gairebé impossible, cal que utilitzeu sumas de comprovació de 32 bits o més de longitud. (per a longituds superiors a 64 bits, normalment s'utilitzen funcions hash criptogràfiques).

Malgrat que he escrit abans que hem d'estalviar espai per tots els mitjans, seguirem utilitzant una suma de verificació de 32 bits (16 bits no són suficients, la probabilitat d'una col·lisió és superior al 0.01%; i 24 bits, ja que dir, no hi són ni aquí ni allà).

Aquí pot sorgir una objecció: hem desat cada byte en triar la compressió per donar ara 4 bytes alhora? No seria millor no comprimir ni afegir una suma de verificació? Per descomptat que no, sense compressió No vol dir, que no necessitem una comprovació d'integritat.

Quan escollim un polinomi, no reinventarem la roda, sinó que agafarem l'ara popular CRC-32C.
Aquest codi detecta errors de 6 bits en paquets de fins a 22 bytes (potser el cas més comú per a nosaltres), errors de 4 bits en paquets de fins a 655 bytes (també un cas comú per a nosaltres), errors de 2 o qualsevol nombre imparell de bits en paquets. de qualsevol longitud raonable.

Si algú està interessat en els detalls

article de la Viquipèdia sobre CRC.

Paràmetres de codi crc-32c en Lloc web de Koopman — potser el principal especialista en CRC del planeta.

В el seu article hi un altre codi interessant, que proporciona paràmetres una mica millors per a les longituds de paquets que són rellevants per a nosaltres, però no vaig considerar la diferència significativa i vaig ser prou competent per triar el codi personalitzat en lloc de l'estàndard i ben investigat.

A més, com que les nostres dades estan comprimides, sorgeix la pregunta: hem de calcular la suma de control de les dades comprimides o no comprimides?

Arguments a favor del càlcul de la suma de control de dades no comprimides:

• En definitiva, hem de comprovar la seguretat de l'emmagatzematge de dades, així que ho comprovem directament (al mateix temps, es comprovaran possibles errors en la implementació de la compressió/descompressió, danys causats per la memòria trencada, etc.);
• L'algoritme de desinflat a zlib té una implementació bastant madura i no hauria de cau amb dades d'entrada "torçades"; a més, sovint és capaç de detectar errors de manera independent en el flux d'entrada, reduint la probabilitat global de no detectar un error (s'ha dut a terme una prova amb la inversió d'un sol bit en un registre curt, zlib va ​​detectar un error en aproximadament un terç dels casos).

Arguments contra el càlcul de la suma de control de dades no comprimides:

• CRC està "adaptat" específicament als pocs errors de bits que són característics de la memòria flaix (un error de bits en un flux comprimit pot provocar un canvi massiu en el flux de sortida, en el qual, purament teòricament, podem "atrapar" una col·lisió);
• No m'agrada molt la idea de passar dades potencialment trencades al descompressor, Qui sapcom reaccionarà.

En aquest projecte, vaig decidir desviar-me de la pràctica generalment acceptada d'emmagatzemar una suma de control de dades no comprimides.

Resum: Utilitzem CRC-32C, calculem la suma de control a partir de les dades en la forma en què s'escriuen a flash (després de la compressió).

Redundància

L'ús de la codificació redundant, per descomptat, no elimina la pèrdua de dades, però pot reduir significativament (sovint en molts ordres de magnitud) la probabilitat de pèrdua de dades irrecuperable.

Podem utilitzar diferents tipus de redundància per corregir errors.
Els codis Hamming poden corregir errors d'un sol bit, els codis de caràcters Reed-Solomon, les còpies múltiples de dades combinades amb sumes de control o les codificacions com RAID-6 poden ajudar a recuperar les dades fins i tot en cas de corrupció massiva.
Inicialment, estava compromès amb l'ús generalitzat de la codificació resistent als errors, però després em vaig adonar que primer hem de tenir una idea de quins errors volem protegir-nos i després triar la codificació.

Hem dit abans que els errors s'han de detectar el més aviat possible. En quins punts podem trobar errors?

1. Enregistrament sense acabar (per algun motiu en el moment de la gravació es va apagar l'alimentació, el Raspberry es va congelar, ...)
   Per desgràcia, en cas d'aquest error, només queda ignorar els registres no vàlids i considerar les dades perdudes;
2. Errors d'escriptura (per algun motiu, el que es va escriure a la memòria flaix no era el que es va escriure)
   Podem detectar immediatament aquests errors si fem una lectura de prova immediatament després de la gravació;
3. Distorsió de les dades a la memòria durant l'emmagatzematge;
4. Errors de lectura
   Per corregir-ho, si la suma de control no coincideix, n'hi ha prou amb repetir la lectura diverses vegades.

És a dir, només els errors del tercer tipus (corrupció espontània de les dades durant l'emmagatzematge) no es poden corregir sense una codificació resistent a errors. Sembla que aquests errors encara són molt poc probables.

Resum: es va decidir abandonar la codificació redundant, però si l'operació mostra l'error d'aquesta decisió, torneu a considerar el problema (amb estadístiques ja acumulades sobre errors, que permetran triar el tipus de codificació òptim).

Un altre

Per descomptat, el format de l'article no ens permet justificar cada bit del format (i les forces ja s'han acabat), així que repassaré breument alguns punts no tractats abans.

• Es va decidir fer totes les pàgines "iguals"
  És a dir, no hi haurà pàgines especials amb metadades, fils separats, etc., sinó un únic fil que reescriu totes les pàgines al seu torn.
  Això garanteix un desgast uniforme de les pàgines, no hi ha cap punt de fallada, i m'agrada;
• És imprescindible proporcionar versions del format.
  Un format sense un número de versió a la capçalera és dolent!
  N'hi ha prou d'afegir un camp amb un número màgic (signatura) determinat a la capçalera de la pàgina, que indicarà la versió del format utilitzat. (No crec que a la pràctica n'hi hagi ni una dotzena);
• Utilitzeu una capçalera de longitud variable per als registres (dels quals n'hi ha molts), intentant que tingui una longitud d'1 byte en la majoria dels casos;
• Per codificar la longitud de la capçalera i la longitud de la part retallada del registre comprimit, utilitzeu codis binaris de longitud variable.

Va ajudar molt generador en línia Codis Huffman. En pocs minuts vam poder seleccionar els codis de longitud variable necessaris.

Descripció del format d'emmagatzematge de dades

Ordre de bytes

Els camps més grans d'un byte s'emmagatzemen en format big-endian (ordre de bytes de xarxa), és a dir, 0x1234 s'escriu com a 0x12, 0x34.

Paginació

Tota la memòria flash es divideix en pàgines de la mateixa mida.

La mida de pàgina predeterminada és de 32 Kb, però no més d'1/4 de la mida total del xip de memòria (per a un xip de 4 MB, s'obtenen 128 pàgines).

Cada pàgina emmagatzema dades independentment de les altres (és a dir, les dades d'una pàgina no fan referència a dades d'una altra pàgina).

Totes les pàgines estan numerades per ordre natural (en ordre ascendent d'adreces), començant pel número 0 (la pàgina zero comença a l'adreça 0, la primera pàgina comença a 32 Kb, la segona pàgina comença a 64 Kb, etc.)

El xip de memòria s'utilitza com a buffer cíclic (ring buffer), és a dir, primer l'escriptura va a la pàgina número 0, després a la número 1, ..., quan omplim l'última pàgina, comença un nou cicle i l'enregistrament continua des de la pàgina zero. .

Dins de la pàgina

Al principi de la pàgina, s'emmagatzema una capçalera de pàgina de 4 bytes, després una suma de comprovació de la capçalera (CRC-32C) i després s'emmagatzemen els registres en el format "capçalera, dades, suma de comprovació".

El títol de la pàgina (verd brut al diagrama) consta de:

• camp Magic Number de dos bytes (també un signe de la versió de format)
  per a la versió actual del format es calcula com 0xed00 ⊕ номер страницы;
• comptador de dos bytes "Versió de la pàgina" (número de cicle de reescriptura de memòria).

Les entrades de la pàgina s'emmagatzemen en forma comprimida (s'utilitza l'algoritme de desinflat). Tots els registres d'una pàgina es comprimeixen en un fil (s'utilitza un diccionari comú) i a cada pàgina nova la compressió comença de nou. És a dir, per descomprimir qualsevol registre, calen tots els registres anteriors d'aquesta pàgina (i només aquesta).

Cada registre es comprimirà amb el senyalador Z_SYNC_FLUSH, i al final del flux comprimit hi haurà 4 bytes 0x00, 0x00, 0xff, 0xff, possiblement precedits d'un o dos bytes zero més.
Descartem aquesta seqüència (de 4, 5 o 6 bytes) quan escrivim a la memòria flash.

La capçalera del registre té 1, 2 o 3 bytes que emmagatzemen:

• un bit (T) que indica el tipus de registre: 0 - context, 1 - registre;
• un camp de longitud variable (S) d'1 a 7 bits, que defineix la longitud de la capçalera i la "cua" que cal afegir al registre per a la descompressió;
• longitud del registre (L).

Taula de valors S:

S
Longitud de la capçalera, bytes
Descartat en escriptura, 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)

Vaig intentar il·lustrar-ho, no sé amb quina claritat va resultar:

El groc indica aquí el camp T, el blanc el camp S, el verd L (la longitud de les dades comprimides en bytes), el blau les dades comprimides, el vermell els bytes finals de les dades comprimides que no s'escriuen a la memòria flash.

Així, podem escriure capçaleres de registre de la longitud més habitual (fins a 63+5 bytes en forma comprimida) en un byte.

Després de cada registre, s'emmagatzema una suma de comprovació CRC-32C, en la qual s'utilitza el valor invertit de la suma de comprovació anterior com a valor inicial (init).

CRC té la propietat de "durada", la fórmula següent funciona (més o menys inversió de bits en el procés): .
És a dir, de fet, calculem el CRC de tots els bytes anteriors de capçaleres i dades d'aquesta pàgina.

Directament després de la suma de comprovació hi ha la capçalera del següent registre.

La capçalera està dissenyada de manera que el seu primer byte sempre sigui diferent de 0x00 i 0xff (si en comptes del primer byte de la capçalera trobem 0xff, això vol dir que es tracta d'una àrea no utilitzada; 0x00 indica un error).

Algoritmes d'exemple

Lectura des de la memòria flash

Qualsevol lectura ve amb una comprovació de suma de verificació.
Si la suma de comprovació no coincideix, la lectura es repeteix diverses vegades amb l'esperança de llegir les dades correctes.

(això té sentit, Linux no guarda en memòria cau les lectures de NOR Flash, provat)

Escriu a la memòria flash

Enregistrem les dades.
Llegim-los.

Si les dades llegides no coincideixen amb les dades escrites, omplim l'àrea amb zeros i senyalem un error.

Preparant un nou microcircuit per al funcionament

Per a la inicialització, s'escriu una capçalera amb la versió 1 a la primera pàgina (o més aviat zero).
Després d'això, el context inicial s'escriu en aquesta pàgina (conté l'UUID de la màquina i la configuració predeterminada).

Això és tot, la memòria flaix està llesta per al seu ús.

Carregant la màquina

Quan es carrega, es llegeixen els primers 8 bytes de cada pàgina (capçalera + CRC), les pàgines amb un número màgic desconegut o un CRC incorrecte s'ignoren.
De les pàgines "correctes", se seleccionen pàgines amb la versió màxima i se'n treu la pàgina amb el nombre més alt.
Es llegeix el primer registre, es comprova la correcció del CRC i la presència de la bandera "context". Si tot està bé, aquesta pàgina es considera actual. Si no, tornem a l'anterior fins que trobem una pàgina "en directe".
i a la pàgina trobada llegim tots els registres, els que utilitzem amb la bandera “context”.
Deseu el diccionari zlib (serà necessari per afegir-lo a aquesta pàgina).

Això és tot, la descàrrega s'ha completat, el context s'ha restaurat, ja pots treballar.

Afegir una entrada de diari

Comprimim el registre amb el diccionari correcte, especificant Z_SYNC_FLUSH. Veiem si el registre comprimit encaixa a la pàgina actual.
Si no encaixa (o hi ha errors CRC a la pàgina), inicieu una pàgina nova (vegeu més avall).
Anotem el registre i el CRC. Si es produeix un error, inicieu una pàgina nova.

Pàgina nova

Seleccionem una pàgina gratuïta amb el nombre mínim (considerem que una pàgina lliure és una pàgina amb una suma de control incorrecta a la capçalera o amb una versió inferior a l'actual). Si no hi ha aquestes pàgines, seleccioneu la pàgina amb el nombre mínim d'aquelles que tenen una versió igual a l'actual.
Esborram la pàgina seleccionada. Comprovem el contingut amb 0xff. Si alguna cosa no funciona, agafeu la següent pàgina gratuïta, etc.
Escrivim una capçalera a la pàgina esborrada, la primera entrada és l'estat actual del context, la següent és l'entrada de registre no escrita (si n'hi ha).

Aplicabilitat del format

Al meu entendre, va resultar ser un bon format per emmagatzemar fluxos d'informació més o menys compressibles (text pla, JSON, MessagePack, CBOR, possiblement protobuf) a NOR Flash.

Per descomptat, el format està "adaptat" per a SLC NOR Flash.

No s'ha d'utilitzar amb mitjans de BER alt com NAND o MLC NOR (fins i tot aquesta memòria està disponible per a la venda? Només l'he vist esmentada en treballs sobre codis de correcció).

A més, no s'ha d'utilitzar amb dispositius que tinguin el seu propi FTL: flash USB, SD, MicroSD, etc (per a aquesta memòria vaig crear un format amb una mida de pàgina de 512 bytes, una signatura al començament de cada pàgina i números de registre únics; de vegades era possible recuperar totes les dades d'una unitat flaix "fallada" mitjançant una simple lectura seqüencial).

Depenent de les tasques, el format es pot utilitzar sense canvis en unitats flash de 128Kbit (16Kb) a 1Gbit (128MB). Si voleu, podeu utilitzar-lo en fitxes més grans, però probablement haureu d'ajustar la mida de la pàgina (Però aquí ja es planteja la qüestió de la viabilitat econòmica; el preu del NOR Flash de gran volum no és encoratjador).

Si algú troba el format interessant i vol utilitzar-lo en un projecte obert, escriu, intentaré trobar l'hora, polir el codi i publicar-lo a github.

Conclusió

Com podeu veure, al final el format va resultar senzill i fins i tot avorrit.

És difícil reflectir l'evolució del meu punt de vista en un article, però creieu-me: inicialment volia crear quelcom sofisticat, indestructible, capaç de sobreviure fins i tot a una explosió nuclear a prop. Tanmateix, la raó (espero) encara va guanyar i, a poc a poc, les prioritats van anar canviant cap a la simplicitat i la compacitat.

Pot ser que m'he equivocat? Si, es clar. Pot ser, per exemple, que vam comprar un lot de microcircuits de baixa qualitat. O per alguna altra raó, l'equip no complirà les expectatives de fiabilitat.

Tinc un pla per a això? Crec que després de llegir l'article no teniu cap dubte que hi ha un pla. I ni tan sols.

En una nota una mica més seriosa, el format es va desenvolupar tant com a opció de treball com com a "globus de prova".

De moment tot sobre la taula funciona bé, literalment l'altre dia es desplegarà la solució (aproximadament) en centenars de dispositius, vegem què passa en l'operació de "combat" (afortunadament, espero que el format us permeti detectar errors de manera fiable; així podreu recopilar estadístiques completes). En uns mesos es podran treure conclusions (i si no tens sort, fins i tot abans).

Si, segons els resultats de l'ús, es descobreixen problemes greus i es requereixen millores, definitivament escriuré sobre això.

Literatura

No volia fer una llista llarga i tediosa d'obres usades; després de tot, tothom té Google.

Aquí vaig decidir deixar una llista de troballes que em van semblar especialment interessants, però a poc a poc van anar migrant directament al text de l'article i un element va quedar a la llista:

1. Utilitat infgen de l'autor zlib. Pot mostrar clarament el contingut dels arxius deflate/zlib/gzip. Si heu de fer front a l'estructura interna del format deflate (o gzip), ho recomano molt.

Font: www.habr.com