Contesto

Abbiamo distributori automatici di nostra produzione. All'interno ci sono Raspberry Pi e un po' di componentistica su una scheda separata. Sono collegati un ripetitore di monete, un accettatore di banconote e un terminale bancario… Tutto è gestito da un programma sviluppato internamente. L'intera storia operativa viene registrata in un diario su una chiavetta USB (MicroSD), che poi viene trasmessa via internet (tramite un modem USB) a un server, dove viene salvata in un database. Le informazioni sulle vendite vengono caricate in 1C, e c'è anche una semplice interfaccia web per il monitoraggio e simili.

Quindi il diario è vitale — per la contabilità (qui ci sono i ricavi, le vendite, ecc.), per il monitoraggio (tutte le possibili anomalie e altre circostanze impreviste); questa è, possiamo dire, l'unica informazione che abbiamo su questo distributore.

Problema

Le chiavette USB si rivelano dispositivi molto inaffidabili. Si rompono con sorprendente regolarità. Questo porta sia a fermi dei distributori, sia (se per qualche motivo il diario non può essere inviato online) a perdite di dati.

Questa non è la prima esperienza con le chiavette USB, in precedenza c'era un altro progetto con più di cento dispositivi, dove il diario era salvato su chiavette USB; anche lì ci sono stati problemi di affidabilità, talvolta il numero di chiavette rotte in un mese si contava a decine. Abbiamo provato diverse chiavette, incluse quelle di marca con memoria SLC; alcune modelli sono più affidabili di altre, ma la sostituzione delle chiavette non ha risolto radicalmente il problema.

Attenzione! Un longread! Se non ti interessa il "perché" e ti interessa solo il "come", puoi andare direttamente in fondo dell'articolo.

Soluzione

La prima cosa che mi viene in mente: rinunciare a MicroSD, installare, ad esempio, un SSD e avviarlo da lì. Teoricamente è possibile, probabilmente, ma relativamente costoso e non così affidabile (si aggiunge un adattatore USB-SATA; anche le statistiche sui SSD economici non sono incoraggianti).

Dischi USB HDD non sembrano una soluzione particolarmente attraente.

Quindi siamo giunti a questa opzione: mantenere l'avvio da MicroSD, ma usarli in modalità di sola lettura, e conservare il diario di funzionamento (e altre informazioni uniche per ciascun dispositivo — numero di serie, calibrazioni dei sensori, ecc.) da un'altra parte.

L'argomento dei filesystem in sola lettura per Raspberry Pi è stato già esplorato a fondo, non mi soffermerò sui dettagli di implementazione in questo articolo. (ma se ci sarà interesse, magari scriverò un mini-articolo su questo tema). L'unico punto che vorrei sottolineare: sia per esperienza personale, sia per le recensioni di chi già ha implementato, il guadagno in affidabilità è reale. Sì, è impossibile eliminare completamente i guasti, tuttavia è assolutamente possibile ridurne significativamente la frequenza. Inoltre, le schede diventano unificate, il che semplifica notevolmente la sostituzione per il personale di servizio.

Parte hardware

Non c'erano dubbi sulla scelta del tipo di memoria — NOR Flash.
Argomenti:

• connessione semplice (più spesso bus SPI, di cui già abbiamo esperienza, quindi non si prevedono problemi "hardware");
• prezzo ridicolo;
• protocollo standard di funzionamento (l'implementazione è già presente nel kernel di Linux, se vuoi puoi prendere una soluzione esterna, che ci sono, o addirittura scrivere la tua, dato che è tutto molto semplice);
• affidabilità e durata:
  da un tipico datasheet: i dati vengono conservati per 20 anni, 100000 cicli di cancellazione per ogni blocco;
  da fonti esterne: BER estremamente basso, si postula l'assenza della necessità di codici di correzione degli errori (in alcuni lavori si considera ECC per NOR, ma di solito si intende MLC NOR, può capitare anche questo).

Facciamo alcune stime sui requisiti di volume e risorsa.

Vogliamo garantire che i dati vengano salvati per alcuni giorni. Questo è necessario affinché, in caso di problemi di connessione, la storia delle vendite non venga persa. Ci orienteremo su 5 giorni, in questo lasso di tempo (anche considerando i fine settimana e le festività) può risolvere il problema.

Attualmente accumuliamo circa 100 kb di diario al giorno (3-4 mila registrazioni), tuttavia questa cifra sta crescendo — aumenta la dettagliabilità, vengono aggiunti nuovi eventi. Inoltre, a volte ci sono picchi (un certo sensore inizia a inviare falsi allarmi, ad esempio). Calcoliamo su 10 mila registrazioni di 100 byte — un megabyte al giorno.

In totale risultano 5 MB di dati 'puliti' (ben comprimibili). A questi aggiungiamo (una stima grossolana) 1 MB di dati di servizio.

Quindi abbiamo bisogno di un chip da 8 MB se non utilizziamo la compressione, o 4 MB se la utilizziamo. Sono cifre molto realistiche per questo tipo di memoria.

Per quanto riguarda la risorsa: se prevediamo che la memoria sarà completamente riscritta non più spesso di una volta ogni 5 giorni, dopo 10 anni di servizio otteniamo meno di mille cicli di riscrittura.
Ricordo che il produttore promette centomila.

Un po' su NOR vs NAND

Oggi, ovviamente, la memoria NAND è molto più popolare, ma per questo progetto non la utilizzerei: a differenza della NOR, la NAND richiede necessariamente l'uso di codici di correzione degli errori, tabelle dei blocchi difettosi, ecc., e i pin dei chip NAND sono tipicamente molto più numerosi.

Tra i difetti della NOR possiamo citare:

• basso volume (e, di conseguenza, alto costo per megabyte);
• velocità di trasferimento non elevata (in gran parte a causa dell'utilizzo di interfacce seriali, generalmente SPI o I2C);
• veloce cancellazione (a seconda delle dimensioni del blocco, richiede frazioni di secondo fino a diversi secondi).

Non sembra ci siano criticità per noi, quindi continuiamo.

Se sei interessato ai dettagli, è stato scelto il chip at25df321a (comunque non è rilevante, ci sono molte alternative sul mercato compatibili per pinout e sistema di comandi; anche se volessimo installare un chip di un altro produttore e/o di un'altra capacità, funzionerà senza modifiche al codice).

Utilizzo il driver incorporato nel kernel di Linux, su Raspberry, grazie al supporto per device tree overlay, è tutto molto semplice: basta inserire l'overlay compilato in /boot/overlays e modificare leggermente /boot/config.txt.

Esempio di file dts

A dire il vero, non sono sicuro che sia scritto senza errori, ma funziona.

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

E un'altra riga in config.txt

dtoverlay=at25:spimaxfrequency=50000000

Non descriverò il collegamento del chip al Raspberry Pi. Da un lato, non sono un esperto di elettronica, dall'altro — qui è tutto banale anche per me: il chip ha solo 8 pin, di cui abbiamo bisogno di terra, alimentazione, SPI (CS, SI, SO, SCK); i livelli corrispondono a quelli del Raspberry Pi, non è necessaria alcuna ulteriore circuitazione — basta collegare i 6 contatti indicati.

Definizione del compito

Come al solito, la definizione del compito avviene in diverse iterazioni; mi sembra che sia giunto il momento per un'altra. Quindi, fermiamoci, mettiamo insieme ciò che è già stato scritto e chiarifichiamo i dettagli rimasti nell'ombra.

Quindi, abbiamo deciso che il registro sarà memorizzato nella Flash SPI NOR.

Che cos'è la Flash NOR per chi non lo sa

È una memoria non volatile, sulla quale possiamo eseguire tre operazioni:

1. Lettura:
   La lettura più comune: forniamo l'indirizzo e leggiamo il numero di byte di cui abbiamo bisogno;
2. Scrittura:
   La scrittura nella flash NOR sembra normale, ma ha una particolarità: possiamo solo cambiare 1 in 0, ma non viceversa. Ad esempio, se nella cella di memoria c'era 0x55, dopo la scrittura di 0x0f ci sarà 0x05 (vedi tabella qui sotto);
3. Cancellazione:
   Naturalmente, dobbiamo anche essere in grado di eseguire l'operazione inversa — cambiare 0 in 1, ed è proprio per questo che esiste l'operazione di cancellazione. A differenza delle prime due, opera non su byte, ma su blocchi (il blocco minimo di cancellazione nel chip selezionato è di 4kb). La cancellazione annienta l'intero blocco e questo è l'unico modo per cambiare 0 in 1. Pertanto, quando si lavora con la memoria flash, spesso è necessario allineare le strutture dati al confine del blocco di cancellazione.
   Scrittura nella Flash NOR:

Dati binari

C'era
01010101

Scritti.
00001111

Diventato
00000101

Il registro stesso rappresenta una sequenza di registrazioni di lunghezza variabile. La lunghezza tipica di una registrazione è di circa 30 byte (anche se a volte ci sono registrazioni di diversi kilobyte). In questo caso, lavoriamo con esse semplicemente come a un insieme di byte, ma se interessa, all'interno delle registrazioni si utilizza CBOR.

Oltre al registro, abbiamo bisogno di memorizzare alcune informazioni 'di configurazione', sia aggiornabili che non: un certo ID della macchina, le calibrazioni dei sensori, un flag 'macchina temporaneamente spenta', ecc.
Queste informazioni consistono in una serie di registrazioni chiave-valore, anch'esse memorizzate in CBOR. Non abbiamo molte di queste informazioni (al massimo pochi kilobyte), e vengono aggiornate di rado.
In futuro le chiameremo contesto.

Se ricordiamo da dove è iniziato questo articolo, è molto importante garantire l'affidabilità della memorizzazione dei dati e, se possibile, un funzionamento ininterrotto anche in caso di guasti hardware/danni ai dati.

Quali fonti di problemi possiamo considerare?

• Interruzione dell'alimentazione durante le operazioni di scrittura/cancellazione. Questo rientra nella categoria 'non esiste rimedio contro il destino'.
  Informazioni da dibattito stackexchange: in caso di interruzione dell'alimentazione durante l'operazione di flash, sia la cancellazione (impostazione a 1) che la scrittura (impostazione a 0) portano a un comportamento indefinito: i dati possono essere scritti, scritti parzialmente (ad esempio, abbiamo inviato 10 byte/80 bit, ma sono stati scritti solo 45 bit), non è da escludere che parte dei bit possa trovarsi in uno stato 'intermedio' (la lettura può restituire sia 0 che 1);
• Errori della memoria flash stessa.
  Il BER, anche se molto basso, non può essere zero;
• Errori sulla linea
  I dati trasmessi via SPI non sono protetti in alcun modo; potrebbero verificarsi sia errori di bit singoli che errori di sincronizzazione — perdita o inserimento di bit (il che porta a gravi distorsioni dei dati);
• Altri errori/fallimenti.
  Errori di codice, «bug» Raspberry, intervento di alieni...

Ho formulato i requisiti che, a mio avviso, sono necessari per garantire l'affidabilità:

• le registrazioni devono essere scritte nella memoria flash immediatamente, la scrittura ritardata non è considerata; - se si è verificato un errore, deve essere rilevato e gestito il prima possibile; - il sistema deve ripristinare il suo funzionamento dopo un errore, se possibile.
  (un esempio della vita reale «come non dovrebbe essere», con cui penso tutti abbiamo avuto a che fare: dopo un riavvio forzato, il file system si è corrotto e il sistema operativo non si avvia)

Idee, approcci, riflessioni

Quando ho iniziato a pensare a questo compito, ho avuto molte idee, ad esempio:

• utilizzare la compressione dei dati;
• utilizzare strutture dati ingegnose, ad esempio memorizzare gli header delle registrazioni separatamente dalle stesse registrazioni, in modo che in caso di errore in una registrazione sia possibile leggere le altre senza problemi;
• utilizzare campi bit per controllare il completamento della registrazione in caso di interruzione di alimentazione;
• memorizzare checksum per tutto e per tutti;
• utilizzare qualche forma di codifica resistente alle interferenze.

Alcune di queste idee sono state utilizzate, mentre altre sono state scartate. Procediamo con ordine.

Compressione dei dati

Gli eventi che registriamo nel log sono piuttosto omogenei e ripetitivi («lanciata moneta da 5 rubli», «premuto il pulsante per ricevere il resto», ...). Pertanto, la compressione dovrebbe rivelarsi abbastanza efficace.

I costi di compressione sono insignificanti (il nostro processore è abbastanza potente, anche sul primo Pi c'era un core con frequenza di 700 MHz, e sui modelli attuali diversi core con frequenza superiore a un gigahertz), la velocità di scambio con il deposito non è alta (alcuni megabyte al secondo), le dimensioni delle registrazioni non sono elevate. In generale, se la compressione avrà un impatto sulle prestazioni, sarà solo positivo (assolutamente non critico, sto solo constatando). Inoltre, noi non utilizziamo un vero embedded, ma un normale Linux — quindi l'implementazione non dovrebbe richiedere molti sforzi (basta collegare una libreria e utilizzare alcune funzioni di essa).

È stato preso un campione di log da un dispositivo funzionante (1,7 MB, 70.000 registrazioni) e inizialmente verificato per la compressibilità utilizzando gzip, lz4, lzop, bzip2, xz, zstd disponibili sul computer.

• gzip, xz, zstd hanno mostrato risultati simili (40KB).
  È sorprendente che il trendy xz abbia mostrato risultati pari a gzip o zstd;
• lzip con impostazioni predefinite ha dato risultati leggermente peggiori;
• lz4 e lzop hanno mostrato risultati non molto buoni (150KB);
• bzip2 ha mostrato risultati sorprendentemente buoni (18KB).

Quindi, i dati si comprimono molto bene.
Pertanto, (se non troviamo difetti fatali) sarà necessario comprimere! Semplicemente perché sulla stessa memoria flash sarà possibile memorizzare più dati.

Pensiamo ai difetti.

Il primo problema: abbiamo già concordato che ogni registrazione deve essere scritta immediatamente nella flash. Di solito, il compressore raccoglie i dati dal flusso di input fino a quando non decide che è ora di scrivere nell'output. A noi serve invece ottenere subito un blocco di dati compressi e memorizzarlo nella memoria non volatile.

Vedo tre strade:

1. Comprimere ogni registrazione usando la compressione a dizionario al posto degli algoritmi considerati sopra.
   Un'opzione operativa, ma non mi piace. Per garantire un livello di compressione ragionevole, il dizionario deve essere 'ottimizzato' per i dati specifici; qualsiasi modifica porterà a una caduta catastrofica del livello di compressione. Sì, il problema può essere risolto creando una nuova versione del dizionario, ma è un onere — dovremo memorizzare tutte le versioni del dizionario; in ogni registrazione dovremo specificare con quale versione del dizionario è stata compressa…
2. Comprimere ogni registrazione con algoritmi 'classici', ma indipendentemente dalle altre.
   Gli algoritmi di compressione considerati non sono progettati per lavorare con registrazioni di queste dimensioni (decine di byte), il fattore di compressione sarà chiaramente inferiore a 1 (ossia incremento del volume dei dati anziché compressione);
3. Fare FLUSH dopo ogni registrazione.
   Molte librerie di compressione supportano il FLUSH. Questo è un comando (o parametro per la procedura di compressione), ricevuto il quale, il compressore genera un flusso compresso in modo tale da poter ripristinare tutti i dati non compressi che sono già stati ricevuti. Questa è un'analogia sync nei file system o commit in sql.
   È importante che le operazioni di compressione successive possano utilizzare il dizionario accumulato e il grado di compressione non sarà colpito così duramente come nella precedente opzione.

Penso sia ovvio che ho scelto la terza opzione, approfondiamo questo punto.

Trovato ottimo articolo su FLUSH in zlib.

Ho realizzato un test ispirato a un articolo, raccogliendo 70.000 registri da un dispositivo reale, con una dimensione della pagina di 60 KB. (parleremo ancora della dimensione della pagina) ho ottenuto:

Dati di origine
Compressione gzip -9 (senza FLUSH)
zlib con Z_PARTIAL_FLUSH
zlib con Z_SYNC_FLUSH

Dimensione, KB
1692
40
352
604

A prima vista, il costo del FLUSH sembra eccessivo, ma in realtà abbiamo poche opzioni: o non comprimere affatto, o comprimere (e in modo molto efficace) con FLUSH. Non dimentichiamo che abbiamo 70.000 registri e l'overhead introdotto da Z_PARTIAL_FLUSH è solo di 4-5 byte per registrazione. Il rapporto di compressione è risultato essere quasi 5:1, un ottimo risultato.

Potrebbe sembrare inaspettato, ma in realtà Z_SYNC_FLUSH è un metodo più efficiente per effettuare il FLUSH.

Nel caso in cui si utilizzi Z_SYNC_FLUSH, gli ultimi 4 byte di ogni registrazione saranno sempre 0x00, 0x00, 0xff, 0xff. E se li conosciamo, possiamo non memorizzarli, quindi la dimensione finale è di soli 324 KB.

Nell'articolo a cui mi riferisco, c'è una spiegazione:

Un nuovo blocco di tipo 0 con contenuti vuoti viene aggiunto.

Un blocco di tipo 0 con contenuti vuoti consiste in:

• l'intestazione del blocco di tre bit;
• da 0 a 7 bit pari a zero, per raggiungere l'allineamento dei byte;
• la sequenza di quattro byte 00 00 FF FF.

Come si può notare facilmente, nel blocco finale prima di questi 4 byte ci sono da 3 a 10 bit zero. Tuttavia, la pratica ha dimostrato che i bit zero sono in realtà almeno 10.

Si scopre che blocchi di dati così brevi sono solitamente (sempre?) codificati usando un blocco di tipo 1 (blocco fisso), che deve necessariamente terminare con 7 bit zero, arrivando così a garantire da 10 a 17 bit zero (e gli altri saranno zero con una probabilità di circa il 50%).

Pertanto, nei dati di test, in 100% dei casi, prima di 0x00, 0x00, 0xff, 0xff c'è un byte zero, e in più di un terzo dei casi ci sono due byte zero. (forse è dovuto al fatto che utilizzo CBOR binario, e nel caso di JSON testuale si incontrerebbero più frequentemente blocchi di tipo 2 - blocco dinamico, quindi ci sarebbero blocchi senza ulteriori byte zero prima di 0x00, 0x00, 0xff, 0xff)..

In definitiva, con i dati di test disponibili, si può scendere a meno di 250 KB di dati compressi.

Si possono risparmiare ancora un po' di byte, facendo un po' di giocoleria con i bit: ora stiamo ignorando la presenza di diversi bit zero alla fine del blocco, alcuni bit all'inizio del blocco non cambiano nemmeno...
Ma qui ho preso la decisione di fermarmi, altrimenti a questo ritmo potrei finire per sviluppare un mio archiviatore.

In sintesi, dai miei dati di test ho ottenuto 3-4 byte per registrazione, e il rapporto di compressione è stato superiore a 6:1. A dir la verità: non mi aspettavo un risultato del genere, a mio parere tutto ciò che è meglio di 2:1 è già un risultato che giustifica l'uso della compressione.

Tutto bene, ma zlib (deflate) è comunque un algoritmo di compressione piuttosto arcaico e un po' retro. Solo il fatto che venga utilizzato un dizionario delle ultime 32 KB del flusso non compresso sembra strano oggi (cioè se un blocco di dati è molto simile a ciò che era nel flusso di ingresso 40 KB fa, inizierà a essere archiviato di nuovo, invece di fare riferimento a un'entrata passata). Negli archivi moderni, la dimensione del dizionario è più spesso misurata in megabyte piuttosto che in kilobyte.

Quindi continuiamo la nostra mini-ricerca sugli archivi.

Il successivo test è stato condotto su bzip2 (ricordo, senza FLUSH ha mostrato un grado fantastico di compressione, quasi 100:1). Purtroppo, con FLUSH ha mostrato prestazioni molto scarse, e la dimensione dei dati compressi è risultata maggiore di quella dei dati non compressi.

Le mie supposizioni sulle ragioni del fallimento.

Libbz2 offre solo un'opzione di flush, che sembra pulire il dizionario (analogo a Z_FULL_FLUSH in zlib), e non possiamo parlare di una compressione efficiente dopo questo.

E infine, è stato testato zstd. A seconda dei parametri, comprime al livello di gzip, ma molto più velocemente, oppure meglio di gzip.

Purtroppo, con FLUSH anche lui ha mostrato prestazioni 'non molto buone': la dimensione dei dati compressi è risultata di circa 700 KB.

Io ho posto una domanda sulla pagina del progetto su github, ho ricevuto la risposta che si può prevedere di avere fino a 10 byte di dati di overhead per ogni blocco di dati compressi, che è vicino ai risultati ottenuti, e non si potrà mai raggiungere deflate.

A questo punto ho deciso di fermarmi con gli esperimenti sugli archivi (ricordo che xz, lzip, lzo, lz4 non hanno mostrato buone prestazioni nemmeno nella fase di test senza FLUSH, e non ho voluto considerare algoritmi di compressione più esotici).

Torniamo ai problemi di archiviazione.

Il secondo (come si dice, in ordine ma non per importanza) problema è che i dati compressi rappresentano un singolo flusso, nel quale ci sono costantemente riferimenti a segmenti precedenti. Pertanto, se un segmento dei dati compressi è danneggiato, perdiamo non solo il blocco non compresso associato, ma anche tutti i successivi.

Ci sono approcci per risolvere questo problema:

1. Avvisare della comparsa di un problema significa aggiungere ridondanza nei dati compressi, che permette di identificare e correggere errori; di questo parleremo più avanti;
2. Minimizzare le conseguenze in caso di problema
   Abbiamo già detto in precedenza che ciascun blocco di dati può essere compresso in modo indipendente, e in questo caso il problema scomparirà da solo (la corruzione dei dati di un blocco comporterà la perdita solo dei dati di quel blocco). Tuttavia, questo è un caso estremo in cui la compressione dei dati sarà inefficace. L'opposto estremo è utilizzare tutti i 4MB del nostro chip come un'unica archiviazione, il che ci fornirà un'ottima compressione, ma conseguenze catastrofiche in caso di corruzione dei dati.
   Sì, è necessario un compromesso in termini di affidabilità. Ma bisogna ricordare che stiamo sviluppando un formato di archiviazione dei dati per una memoria non volatile con un BER estremamente basso e con una durata dichiarata di 20 anni.

Durante gli esperimenti ho scoperto che le perdite di livello di compressione cominciano a diventare più o meno evidenti su blocchi di dati compressi di dimensione inferiore a 10KB.
È stato precedentemente menzionato che la memoria utilizzata ha un'organizzazione a pagine; non vedo motivi per cui non dovremmo utilizzare la corrispondenza "una pagina - un blocco di dati compressi".

Quindi, la dimensione minima ragionevole della pagina è di 16KB (con un margine per le informazioni di servizio). Tuttavia, una dimensione così piccola della pagina impone limitazioni significative sulla dimensione massima del record.

Sebbene al momento non prevedo record superiori a un kilobyte in forma compressa, ho deciso di utilizzare pagine di dimensione 32KB (in totale 128 pagine per chip).

Riepilogo:

• I dati sono archiviati compressi utilizzando zlib (deflate);
• Per ogni record impostiamo Z_SYNC_FLUSH;
• Per ogni record compresso, tagliamo i byte finali (ad esempio, 0x00, 0x00, 0xff, 0xff); nell'intestazione indichiamo quanti byte abbiamo tagliato;
• I dati sono memorizzati in pagine da 32KB; all'interno della pagina c'è un flusso continuo di dati compressi; su ogni pagina inizia una nuova compressione.

E, prima di concludere con la compressione, vorrei sottolineare che i dati compressi risultano in soli pochi byte per record, quindi è estremamente importante non gonfiare le informazioni di servizio; ogni byte conta.

Archiviazione delle intestazioni dei dati

Poiché abbiamo record di lunghezza variabile, dobbiamo trovare un modo per determinare il posizionamento / i confini dei record.

Conosco tre approcci:

1. Tutti i record sono memorizzati in un flusso continuo, prima c'è l'intestazione del record, che contiene la lunghezza, e poi il record stesso.
   In questa opzione sia le intestazioni che i dati possono avere lunghezza variabile.
   Essenzialmente, otteniamo una lista collegata, che viene utilizzata ampiamente;
2. Le intestazioni e i record stessi sono immagazzinati in flussi separati.
   Utilizzando intestazioni di lunghezza fissa, otteniamo che la corruzione di un'intestazione non influisce sulle altre.
   Questo approccio è utilizzato, ad esempio, in molti file system;
3. I record sono archiviati in un flusso continuo, il confine del record è determinato da un certo marcatore (simbolo / sequenza di simboli che sono vietati all'interno dei blocchi di dati). Se all'interno del record appare un marcatore, lo sostituiamo con una certa sequenza (lo mascheriamo).
   Questo approccio è utilizzato, per esempio, nel protocollo PPP.

Illustro.

Opzione 1:

Qui tutto è molto semplice: conoscendo la lunghezza del record possiamo calcolare l'indirizzo della successiva intestazione. In questo modo ci spostiamo tra le intestazioni finché non troviamo un'area riempita di 0xff (area libera) o la fine della pagina.

Opzione 2:

A causa della lunghezza variabile dei record, non possiamo dire in anticipo quanti record (e quindi intestazioni) avremo bisogno per ogni pagina. Possiamo separare le intestazioni e i dati su pagine diverse, ma preferisco un altro approccio: inseriamo sia le intestazioni che i dati sulla stessa pagina, ma le intestazioni (di dimensione fissa) vanno dall'inizio della pagina, mentre i dati (di lunghezza variabile) vanno dalla fine. Non appena 'si incontrano' (non c'è spazio libero per un nuovo record) consideriamo che questa pagina è piena.

Opzione 3:

Non è necessario memorizzare nell'intestazione la lunghezza o altre informazioni sulla disposizione dei dati; sono sufficienti i marcatori che indicano i confini dei record. Tuttavia, i dati devono essere elaborati durante la scrittura / lettura.
Come marcatore utilizzerei 0xff (con cui la pagina è riempita dopo la cancellazione), quindi l'area libera non sarà mai interpretata come dati.

Tabella comparativa:

Opzione 1
Opzione 2
Opzione 3

Resilienza agli errori
—
+
+

Compattezza
+
—
+

Complesso di implementazione
*
**
**

L'opzione 1 presenta un difetto fatale: se uno dei titoli viene danneggiato, si distrugge l'intera catena successiva. Le altre opzioni permettono di recuperare parte dei dati anche in caso di danni massicci.
Ma qui è opportuno ricordare che abbiamo deciso di memorizzare i dati in forma compressa; quindi perdiamo comunque tutti i dati sulla pagina dopo la registrazione "rotta", quindi anche se nella tabella c'è un meno, non lo consideriamo.

Compattezza:

• nella prima opzione dobbiamo memorizzare nell'intestazione solo la lunghezza; se usiamo variabili intere di lunghezza variabile, nella maggior parte dei casi possiamo limitarci a un byte;
• nella seconda opzione dobbiamo memorizzare l'indirizzo iniziale e la lunghezza; la registrazione deve avere dimensioni fisse, stimo sia di 4 byte per registrazione (due byte per l'offset e due byte per la lunghezza);
• per la terza opzione basta un solo carattere per indicare l'inizio della registrazione, più la registrazione stessa che, a causa dell'escaping, aumenterà dell'1-2%. In generale, c'è una parità approssimativa con la prima opzione.

Inizialmente consideravo la seconda opzione come principale (e avevo anche scritto un'implementazione). Ho abbandonato solo quando ho deciso definitivamente di utilizzare la compressione.

È possibile che un giorno utilizzi comunque un'opzione simile. Ad esempio, se dovessi gestire la memorizzazione dei dati per una nave che viaggia tra la Terra e Marte — con requisiti completamente diversi per l'affidabilità, l'irradiazione spaziale, …

Per quanto riguarda la terza opzione: le ho assegnato due stelle per la complessità di implementazione, semplicemente perché non mi piace occuparmi di escaping, modifiche della lunghezza in corso d'opera, ecc. Sì, forse è un pregiudizio, ma il codice dovrò scriverlo io — perché costringermi a fare qualcosa che non mi piace.

Riepilogo: scegliamo l'opzione di memorizzazione in catene "intestazione con lunghezza — dati di lunghezza variabile" per l'efficienza e la semplicità di implementazione.

Utilizzo di bit per controllare il successo delle operazioni di scrittura

Non ricordo già dove ho preso l'idea, ma è strutturata all'incirca così:
Per ogni registrazione, riserviamo alcuni bit per memorizzare i flag.
Come abbiamo detto prima, dopo l'operazione erase tutti i bit sono impostati a 1, e possiamo modificare 1 a 0, ma non viceversa. Quindi per "flag non impostato" utilizziamo 1 e per "flag impostato" — 0.

Ecco come può apparire la memorizzazione di dati di lunghezza variabile nella flash:

1. Impostiamo il flag "scrittura lunghezza iniziata";
2. Scriviamo la lunghezza;
3. Impostiamo il flag "scrittura dati iniziata";
4. Scriviamo i dati;
5. Impostiamo il flag "scrittura completata".

Inoltre, avremo un flag "si è verificato un errore", quindi 4 flag.

In questo caso abbiamo due stati stabili "1111" — scrittura non iniziata e "1000" — scrittura avvenuta con successo; in caso di interruzioni impreviste del processo di scrittura, otterremo stati intermedi che potremo poi rilevare e gestire.

L'approccio è interessante, ma protegge solo da interruzioni improvvise di corrente e eventi simili, il che è importante, ma non è certo l'unica (e nemmeno la principale) causa di possibili guasti.

Riepilogo: Andiamo avanti nella ricerca di una buona soluzione.

Checksum

Le checksum offrono anche la possibilità di assicurarci (con buona probabilità) che stiamo leggendo esattamente ciò che doveva essere scritto. E, a differenza dei bit di controllo sopra esaminati, funzionano sempre.

Se consideriamo l'elenco delle potenziali fonti di problemi di cui abbiamo parlato, le checksum possono identificare errori indipendentemente dalla loro origine (a meno, forse, che non siano alieni malvagi — potrebbero falsificare anche le checksum).

Quindi, se il nostro obiettivo è verificare che i dati siano integri, le checksum sono un'ottima idea.

La scelta dell'algoritmo per calcolare la checksum non ha sollevato dubbi — CRC. Da un lato, le proprietà matematiche consentono di rilevare al 100% errori di alcuni tipi, dall'altro — su dati casuali di solito questo algoritmo mostra una probabilità di collisione non molto maggiore rispetto al limite teorico. . Anche se non è l'algoritmo più veloce, né sempre il minimo in termini di collisioni, ha una qualità molto importante: nei test che ho visto non ho trovato pattern in cui fallisse in modo evidente. La stabilità è la qualità principale in questo caso.

Esempio di studio approfondito: parte 1, parte 2 (link a narod.ru, scusate).

Tuttavia, la questione della scelta della checksum non è conclusa; il CRC è un'intera famiglia di checksum. Dobbiamo decidere la lunghezza e poi scegliere il polinomio.

La scelta della lunghezza della checksum non è una questione così semplice come può sembrare a prima vista.

Illustro:
Supponiamo di avere una probabilità di errore in ogni byte e un checksum ideale, calcoliamo il numero medio di errori su un milione di record:

Dati, byte
Checksum, byte
Errori non rilevati
Falsi positivi degli errori
Totale degli errori

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

Sembra tutto semplice: scegli la lunghezza del checksum in base alla lunghezza dei dati protetti, con il minimo di falsi positivi — e sei a posto.

Tuttavia, con checksum brevi si presenta un problema: sebbene individuino bene gli errori singoli, possono avere una probabilità piuttosto alta di interpretare dati casuali come corretti. Su Habr c'era già un articolo che descriveva il problema nella vita reale.

Pertanto, per rendere praticamente impossibile una coincidenza casuale del checksum, è necessario utilizzare checksum di almeno 32 bit (per lunghezze superiori a 64 bit solitamente si utilizzano funzioni hash crittografiche).

Anche se ho scritto in precedenza che bisogna risparmiare spazio con ogni mezzo, useremo comunque un checksum a 32 bit (16 bit sono pochi, la probabilità di collisione è superiore allo 0,01%; mentre 24 bit, come si suol dire, non sono né qui né lì).

Qui potrebbe sorgere un'obiezione: abbiamo risparmiato ogni byte scegliendo la compressione, quindi adesso dobbiamo dare 4 byte in un colpo solo? Non sarebbe meglio non comprimere e non aggiungere il checksum? Certo, no, l'assenza di compressione non significache non abbiamo bisogno di verificare l'integrità.

Per quanto riguarda la scelta del polinomio, non inventiamo la ruota, ma prenderemo il popolare CRC-32C.
Questo codice rileva 6 errori di bit in pacchetti fino a 22 byte (probabilmente il caso più comune per noi), 4 errori di bit in pacchetti fino a 655 byte (anche questo è un caso frequente per noi), 2 o qualsiasi numero dispari di errori di bit in pacchetti di qualsiasi lunghezza ragionevole.

Se qualcuno è interessato ai dettagli

Articolo di Wikipedia sul CRC.

I parametri del codice crc-32c con sito di Kupman — probabilmente il principale esperto di CRC al mondo.

In il suo articolo ci siano un altro codice interessante, che fornisce parametri leggermente migliori per le lunghezze dei pacchetti a noi rilevanti, ma non ho ritenuto la differenza significativa, e mi sento abbastanza competente da scegliere un codice personalizzato invece di uno standard ben studiato.

Inoltre, dato che i nostri dati sono compressi, sorge la questione: calcolare il checksum sui dati compressi o non compressi?

Argomentazioni a favore del calcolo del checksum sui dati non compressi:

• alla fine dobbiamo verificare l'integrità dei dati memorizzati — quindi lo verifichiamo direttamente (nel frattempo, verranno controllati eventuali errori nell'implementazione della compressione/decompressione, danni causati da memoria difettosa, ecc.);
• l'algoritmo deflate in zlib ha una realizzazione abbastanza matura e non dovrebbe fallire con dati «strani», inoltre, spesso è in grado di rilevare autonomamente errori nel flusso di ingresso, riducendo la probabilità complessiva di errori non rilevati (ho condotto un test invertendo un singolo bit in un breve record, zlib ha rilevato l'errore circa un terzo delle volte).

Argomentazioni contro il calcolo del checksum sui dati non compressi:

• Il CRC è progettato per errori di bit relativamente rari, caratteristici della memoria flash (un errore di bit nel flusso compresso può comportare un cambiamento massiccio nel flusso di uscita, su cui, teoricamente, possiamo «catturare» una collisione);
• non mi piace molto l'idea di passare al decompressore dati che potrebbero essere corrotti, chi lo sacome reagirà.

In questo progetto ho deciso di allontanarmi dalla pratica comune di memorizzare il checksum sui dati non compressi.

Riepilogo: utilizziamo CRC-32C, il checksum viene calcolato sui dati nella forma in cui vengono registrati nella flash (dopo la compressione).

Ridondanza

L'uso della codifica ridondante non elimina ovviamente la perdita di dati, tuttavia, può sostanzialmente (spesso di molti ordini di grandezza) ridurre la probabilità di perdita di dati irreversibile.

Possiamo utilizzare diversi tipi di ridondanza per correggere gli errori.
I codici di Hamming possono correggere errori singoli di bit, i codici di Reed-Solomon sono simbolici, copie multiple di dati insieme a checksum o codificazioni come RAID-6 possono aiutare a ripristinare i dati anche in caso di danni massicci.
Inizialmente ero orientato a un ampio utilizzo della codifica a prova di errore, ma poi ho capito che prima bisogna avere un'idea di quali errori vogliamo difenderci, e poi scegliere la codifica.

Abbiamo detto in precedenza che gli errori devono essere rilevati il più rapidamente possibile. Quando possiamo incontrare errori?

1. Registrazione incompleta (per qualche motivo l'alimentazione si è spenta durante la registrazione, Raspberry si è bloccato, …)
   Purtroppo, in caso di tale errore, non rimane altro da fare che ignorare le registrazioni non valide e considerare i dati persi;
2. Errori di registrazione (per qualche motivo nella memoria flash è stato registrato qualcosa di diverso da quanto previsto)
   Possiamo rilevare immediatamente tali errori se eseguiamo una lettura di controllo subito dopo la registrazione;
3. Distorsione dei dati in memoria durante l’archiviazione;
4. Errori di lettura
   Per correggere basta ripetere la lettura più volte in caso di non corrispondenza del checksum.

Cioè, solo gli errori di terzo tipo (corruzione spontanea dei dati durante l'archiviazione) non possono essere corretti senza codifica resistente agli errori. Si pensa che tali errori siano comunque estremamente improbabili.

Riepilogo: Si è deciso di rinunciare alla codifica ridondante, ma se l'operazione dimostrerà l'erroneità di questa decisione, si tornerà a considerare la questione (con già statistiche accumulate sui guasti, che permetteranno di scegliere il tipo di codifica ottimale).

Altro

Ovviamente, il formato dell'articolo non consente di giustificare ogni bit nel formato (e io ho già esaurito le forze), quindi passerò brevemente attraverso alcuni punti non trattati in precedenza.

• Si è deciso di rendere tutte le pagine «paritarie»
  Cioè non ci saranno pagine speciali con metadati, flussi separati, ecc.; invece ci sarà un unico flusso che riscrive tutte le pagine a turno.
  Questo assicura un'usura uniforme delle pagine, l'assenza di un unico punto di guasto, e semplicemente piace;
• È necessario prevedere la versione del formato.
  Un formato senza numero di versione nell'intestazione è malvagio!
  È sufficiente aggiungere nel titolo della pagina un campo con un certo Magic Number (firma), che indicherà la versione del formato utilizzato (non penso che nella pratica ce ne siano anche dieci);
• Utilizzare per le registrazioni (delle quali ce ne sono molte) un'intestazione di lunghezza variabile, cercando di renderla lunga 1 byte nella maggior parte dei casi;
• Per codificare la lunghezza dell'intestazione e la lunghezza della parte troncata della registrazione compressa, utilizzare codici binari di lunghezza variabile.

È stato molto utile un generatore online di codici di Huffman. In pochi minuti sono riuscito a trovare i codici di lunghezza variabile necessari.

Descrizione del formato di archiviazione dei dati

Ordinamento dei byte

I campi di dimensione superiore a un byte sono memorizzati in formato big-endian (ordine dei byte di rete), cioè 0x1234 è registrato come 0x12, 0x34.

Divisione in pagine

L'intera memoria flash è suddivisa in pagine di dimensioni uguali.

La dimensione della pagina per impostazione predefinita è di 32 Kb, ma non superiore a 1/4 della dimensione complessiva del chip di memoria (per un chip da 4 Mb si ottengono 128 pagine).

Ogni pagina memorizza i dati in modo indipendente dalle altre (cioè i dati di una pagina non fanno riferimento ai dati di un'altra pagina).

Tutte le pagine sono numerate in ordine naturale (in ordine crescente di indirizzi), a partire dal numero 0 (la pagina zero inizia dall'indirizzo 0, la prima dalla 32 Kb, la seconda dalla 64 Kb e così via)

Il chip di memoria è utilizzato come buffer circolare (ring buffer), cioè inizialmente la registrazione avviene nella pagina numero 0, poi nella pagina numero 1, … quando riempiamo l'ultima pagina, inizia un nuovo ciclo e la registrazione continua dalla pagina zero.

All'interno della pagina

All'inizio della pagina è memorizzato un'intestazione di 4 byte, poi il checksum dell'intestazione (CRC-32C), quindi sono memorizzate le registrazioni nel formato «intestazione, dati, checksum».

L'intestazione della pagina (nella figura di colore verde sporco) è composta da:

• un campo di due byte Magic Number (che è anche il segnale della versione del formato)
  per la versione attuale del formato è calcolata come 0xed00 ⊕ numero della pagina;
• un contatore di due byte «Versione della pagina» (numero del ciclo di riscrittura della memoria).

Le registrazioni nella pagina sono memorizzate in forma compressa (viene utilizzato l'algoritmo deflate). Tutte le registrazioni su una pagina vengono compresse in un unico flusso (viene utilizzato un dizionario comune), su ogni nuova pagina la compressione inizia da capo. Cioè, per la decompressione di qualsiasi registrazione sono necessarie tutte le registrazioni precedenti in questa pagina (e solo in questa).

Ogni registrazione è compressa con il flag Z_SYNC_FLUSH, e in fondo al flusso compresso risultano 4 byte 0x00, 0x00, 0xff, 0xff, preceduti, forse, da uno o due byte nulli.
Questa sequenza (di lunghezza 4, 5 o 6 byte) viene scartata durante la scrittura nella memoria flash.

L'intestazione della registrazione consiste in 1, 2 o 3 byte, che memorizzano:

• un bit (T), che indica il tipo di registrazione: 0 — contesto, 1 — registro;
• un campo di lunghezza variabile (S) da 1 a 7 bit, che determina la lunghezza dell'intestazione e del «codice», che deve essere aggiunto alla registrazione per la decompressione;
• la lunghezza della registrazione (L).

Tabella dei valori S:

S
Lunghezza dell'intestazione, byte
Scartato durante la registrazione, 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)

Ho cercato di illustrare, non so quanto sia chiaro:

In giallo è indicato il campo T, in bianco il campo S, in verde L (lunghezza dei dati compressi in byte), in azzurro i dati compressi, in rosso i byte finali dei dati compressi che non vengono scritti nella memoria flash.

In questo modo, potremo registrare gli header di lunghezza più comune (fino a 63+5 byte in forma compressa) in un solo byte.

Dopo ogni registrazione viene memorizzata una somma di controllo CRC-32C, che utilizza come valore iniziale (init) il valore invertito della somma di controllo precedente.

Il CRC ha la proprietà della 'continuità', si applica (più o meno invertendo i bit nel processo) la seguente formula: .
In altre parole, calcoliamo il CRC di tutti i byte precedenti degli header e dei dati in questa pagina.

Subito dopo la somma di controllo si trova l'header della registrazione successiva.

L'header è costruito in modo tale che il suo primo byte sia sempre diverso da 0x00 e 0xff (se incontriamo 0xff al posto del primo byte dell'header, significa che è un'area non utilizzata; 0x00 segnala un errore).

Algoritmi approssimativi

Lettura dalla memoria flash

Qualsiasi lettura avviene con verifica della somma di controllo.
Se la somma di controllo non corrisponde, la lettura viene ripetuta più volte nella speranza di leggere i dati corretti.

(ha senso, Linux non memorizza nella cache le letture dalla NOR Flash, confermato)

Scrittura nella memoria flash

Registriamo i dati.
Li leggiamo.

Se i dati letti non corrispondono a quelli scritti, riempiamo l'area di zeri e segnaliamo un errore.

Preparazione del nuovo chip per il lavoro

Per l'inizializzazione, nella prima (o meglio, zero) pagina si scrive un header con versione 1.
Dopo di che, in questa pagina viene scritto il contesto iniziale (contiene UUID della macchina e impostazioni predefinite).

Ecco, la memoria flash è pronta per l'uso.

Avvio della macchina

Durante l'avvio si leggono i primi 8 byte di ogni pagina (header + CRC), le pagine con un Magic Number sconosciuto o un CRC errato vengono ignorate.
Dalle pagine 'corrette' vengono selezionate le pagine con la versione massima, da cui viene presa la pagina con il numero più alto.
Viene letta la prima registrazione, viene verificata la correttezza del CRC e la presenza del flag 'contesto'. Se tutto è a posto, questa pagina è considerata attuale. Se no, torniamo alla pagina precedente, finché non troviamo una pagina 'viva'.
Dalla pagina trovata leggiamo tutte le registrazioni, quelle con il flag 'contesto' le applichiamo.
Salviamo il dizionario zlib (ne avremo bisogno per ulteriori registrazioni in questa pagina).

Tutto, il caricamento è completato, il contesto è ripristinato, possiamo lavorare.

Aggiunta di una registrazione al registro

Comprimi la registrazione con il dizionario corretto, specificando Z_SYNC_FLUSH. Controlliamo se la registrazione compressa entra nella pagina attuale.
Se non ci sta (o se ci sono errori CRC nella pagina), iniziamo una nuova pagina (vedi sotto).
Registriamo la registrazione e il CRC. Se si verifica un errore, iniziamo una nuova pagina.

Nuova pagina

Selezioniamo una pagina libera con il numero più basso (consideriamo libera una pagina con somma di controllo errata nell'header o con versione inferiore a quella attuale). Se non ci sono pagine di questo tipo, scegliamo la pagina con il numero più basso tra quelle con versione uguale a quella attuale.
Eseguiamo l'erase della pagina scelta. Verifichiamo il contenuto con 0xff. Se qualcosa non va, prendiamo la successiva pagina libera, e così via.
Nella pagina cancellata scriviamo l'header, come prima registrazione lo stato attuale del contesto, la successiva — la registrazione non scritta del registro (se c'è).

Applicabilità del formato

A mio avviso, è emerso un buon formato per memorizzare qualsiasi flusso di informazioni semi-comprimibili (testo semplice, JSON, MessagePack, CBOR, possibilmente protobuf) nella NOR Flash.

Certo, il formato è 'ottimizzato' per SLC NOR Flash.

Non dovrebbe essere usato con supporti ad alto BER, come NAND o MLC NOR (esiste davvero una memoria di questo tipo in commercio? Ho visto solo riferimenti nei lavori sui codici di correzione).

Ancora di più, non dovrebbe essere usato con dispositivi che hanno il proprio FTL: USB flash, SD, MicroSD, ecc. (per tale memoria avevo creato un formato con dimensione della pagina di 512 byte, una firma all'inizio di ogni pagina e numeri unici per le registrazioni — a volte da una flash 'guasta' sono riuscito a recuperare tutti i dati attraverso letture sequenziali semplici).

A seconda delle esigenze, il formato può essere utilizzato senza modifiche su chiavette USB da 128 Kbit (16 Kb) fino a 1 Gbit (128 Mb). Se desiderato, può essere utilizzato anche su chip di maggiore capacità, solo che probabilmente è necessario regolare la dimensione della pagina (Ma qui si pone già il problema della convenienza economica, il prezzo della NOR Flash di grande capacità non è incoraggiante).

Se a qualcuno il formato è sembrato interessante e vuole utilizzarlo in un progetto aperto, scrivete pure, cercherò di trovare il tempo per sistemare il codice e caricarlo su github.

Conclusione

Come vediamo, alla fine il formato si è rivelato semplice e persino noioso.

Nell'articolo è difficile riflettere l'evoluzione del mio punto di vista, ma credetemi: inizialmente volevo creare qualcosa di complesso, indistruttibile, capace di sopravvivere anche a un'esplosione nucleare nei dintorni. Tuttavia, la ragione (spero) ha prevalso e gradualmente le priorità si sono spostate verso la semplicità e la compattezza.

È possibile che mi sia sbagliato? Sì, certo. Potrebbe benissimo capitare, ad esempio, che abbiamo acquistato un lotto di chip scadenti. Oppure per qualche altro motivo l'attrezzatura non soddisferà le aspettative in termini di affidabilità.

Ho un piano per questo caso? Credo che leggendo l'articolo non dubitiate che ci sia un piano. E non uno solo.

Se vogliamo essere un po' più seri, il formato è stato sviluppato sia come opzione di lavoro che come "prova".

Ad oggi tutto funziona normalmente, letteralmente nei prossimi giorni la soluzione sarà implementata (circa) su cento dispositivi, vedremo come si comporterà in "condizioni operative" (spero che il formato permetta di rilevare in modo affidabile i guasti; così potremo raccogliere statistiche complete). Tra qualche mese sarà possibile fare delle conclusioni (e se non va bene, anche prima).

Se al termine dell'uso si rivelano problemi seri e sono necessarie modifiche, ne darò sicuramente notizia.

Letteratura

Non volevo creare un lungo elenco noioso di lavori utilizzati, alla fine Google ce l'ha tutti.

Qui ho deciso di lasciare un elenco delle scoperte che mi sono sembrate particolarmente interessanti, ma gradualmente sono state integrate direttamente nel testo dell'articolo, e nell'elenco è rimasto un solo punto:

1. Utility infgen di autore zlib. È in grado di visualizzare in modo chiaro il contenuto di archivi deflate/zlib/gzip. Se vi capita di dover capire il funzionamento interno del formato deflate (o gzip), lo consiglio vivamente.

Fonte: habr.com