Prehistoria

Hay máquinas expendedoras de diseño propio. Dentro de la Raspberry Pi y algo de cableado en una placa separada. Se conectan un aceptador de monedas, un aceptador de billetes, un terminal bancario... Todo está controlado por un programa autoescrito. Todo el historial de trabajo se escribe en un registro en una unidad flash (MicroSD), que luego se transmite a través de Internet (mediante un módem USB) al servidor, donde se almacena en una base de datos. La información de ventas se carga en 1c, también hay una interfaz web sencilla para seguimiento, etc.

Es decir, el diario es vital: para la contabilidad (ingresos, ventas, etc.), seguimiento (todo tipo de averías y otras circunstancias de fuerza mayor); Esta, se podría decir, es toda la información que tenemos sobre esta máquina.

problema

Las unidades flash se muestran como dispositivos muy poco fiables. Fracasan con envidiable regularidad. Esto provoca un tiempo de inactividad de la máquina y (si por alguna razón el registro no se pudo transferir en línea) a la pérdida de datos.

Esta no es la primera experiencia en el uso de unidades flash, antes hubo otro proyecto con más de cien dispositivos donde el cargador se almacenaba en unidades flash USB, también hubo problemas con la confiabilidad, a veces el número de los que fallaron un mes eran decenas. Probamos diferentes unidades flash, incluidas las de marca con memoria SLC, y algunos modelos son más confiables que otros, pero reemplazar las unidades flash no resolvió radicalmente el problema.

¡Atención! ¡Lectura larga! Si no te interesa el “por qué”, sino sólo el “cómo”, puedes seguir directamente Al final artículos

Solución

Lo primero que me viene a la cabeza es: abandonar la MicroSD, instalar, por ejemplo, un SSD y arrancar desde él. Teóricamente posible, probablemente, pero relativamente caro y no tan confiable (se agrega un adaptador USB-SATA; las estadísticas de fallas para los SSD económicos tampoco son alentadoras).

USB HDD tampoco parece una solución especialmente atractiva.

Por lo tanto, llegamos a esta opción: dejar el arranque desde MicroSD, pero usarlas en modo de solo lectura y almacenar el registro de operación (y otra información exclusiva de una pieza de hardware en particular: número de serie, calibraciones de sensores, etc.) en otro lugar. .

El tema de FS de solo lectura para frambuesas ya se ha estudiado por dentro y por fuera, no me detendré en los detalles de implementación en este artículo. (pero si hay interés, tal vez escriba un mini-artículo sobre este tema). El único punto que me gustaría señalar es que tanto por experiencia personal como por las revisiones de quienes ya lo han implementado, se gana en confiabilidad. Sí, es imposible deshacerse por completo de las averías, pero es muy posible reducir significativamente su frecuencia. Y las tarjetas se están unificando, lo que facilita mucho la sustitución por parte del personal de servicio.

Hardware

No hubo dudas especiales sobre la elección del tipo de memoria: NOR Flash.
Argumentos:

• conexión sencilla (normalmente el bus SPI, en el que ya tiene experiencia, por lo que no se prevén problemas de hardware);
• precio ridículo;
• protocolo operativo estándar (la implementación ya está en el kernel de Linux, si lo desea, puede tomar uno de terceros, que también está presente, o incluso escribir el suyo propio, afortunadamente, todo es simple);
• Fiabilidad y recursos:
  de una hoja de datos típica: los datos se almacenan durante 20 años, 100000 ciclos de borrado por cada bloque;
  de fuentes de terceros: BER extremadamente baja, no requiere códigos de corrección de errores (algunos trabajos consideran ECC para NOR, pero generalmente todavía significan MLC NOR; esto también sucede).

Estimemos los requisitos de volumen y recursos.

Me gustaría que se garantizara que los datos se guardarán durante varios días. Esto es necesario para que ante cualquier problema de comunicación no se pierda el historial de ventas. Nos centraremos en 5 días, durante este período. (incluso teniendo en cuenta fines de semana y festivos) el problema se puede solucionar.

Actualmente recopilamos alrededor de 100 KB de registros por día (de 3 a 4 mil entradas), pero gradualmente esta cifra está creciendo: el detalle aumenta y se agregan nuevos eventos. Además, a veces hay ráfagas (algunos sensores comienzan a enviar spam con falsos positivos, por ejemplo). Calcularemos para 10 mil registros de 100 bytes cada uno: megabytes por día.

En total salen 5MB de datos limpios (bien comprimidos). más para ellos (cálculo aproximado) 1 MB de datos de servicio.

Es decir, necesitamos un chip de 8MB si no usamos compresión, o 4MB si la usamos. Números bastante realistas para este tipo de memoria.

En cuanto al recurso: si planeamos que toda la memoria se reescriba no más de una vez cada 5 días, entonces durante 10 años de servicio obtendremos menos de mil ciclos de reescritura.
Permítanme recordarles que el fabricante promete cien mil.

Un poco sobre NOR vs NAND

Hoy en día, por supuesto, la memoria NAND es mucho más popular, pero no la usaría para este proyecto: NAND, a diferencia de NOR, requiere necesariamente el uso de códigos de corrección de errores, una tabla de bloques defectuosos, etc., así como las patas de Los chips NAND suelen ser mucho más grandes.

Las desventajas de NOR incluyen:

• pequeño volumen (y, en consecuencia, alto precio por megabyte);
• baja velocidad de comunicación (en gran parte debido al hecho de que se utiliza una interfaz en serie, generalmente SPI o I2C);
• borrado lento (dependiendo del tamaño del bloque, tarda desde una fracción de segundo hasta varios segundos).

Parece que no hay nada crítico para nosotros, así que continuamos.

Si los detalles son interesantes, se ha seleccionado el microcircuito. at25df321a (sin embargo, esto no es importante, hay muchos análogos en el mercado que son compatibles en pinout y sistema de comando; incluso si queremos instalar un microcircuito de otro fabricante y/o de otro tamaño, todo funcionará sin cambiar el código).

Utilizo el controlador integrado en el kernel de Linux; en Raspberry, gracias al soporte de superposición del árbol de dispositivos, todo es muy simple: debe colocar la superposición compilada en /boot/overlays y modificar ligeramente /boot/config.txt.

Ejemplo de archivo dts

Para ser honesto, no estoy seguro de que esté escrito sin errores, pero 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?";
    };
};

Y otra línea en config.txt

dtoverlay=at25:spimaxfrequency=50000000

Omitiré la descripción de cómo conectar el chip a la Raspberry Pi. Por un lado, no soy un experto en electrónica, por otro lado, todo aquí es banal incluso para mí: el microcircuito tiene solo 8 patas, de las cuales necesitamos tierra, energía, SPI (CS, SI, SO, SCK ); los niveles son los mismos que los de Raspberry Pi, no se requiere cableado adicional, simplemente conecte los 6 pines indicados.

Formulación del problema

Como de costumbre, el planteamiento del problema pasa por varias iteraciones y me parece que es hora de la siguiente. Así que detengámonos, juntemos lo que ya está escrito y aclaremos los detalles que quedan en la sombra.

Entonces, hemos decidido que el registro se almacenará en SPI NOR Flash.

¿Qué es NOR Flash para quienes no lo saben?

Se trata de una memoria no volátil con la que podrás realizar tres operaciones:

1. Lectura
   La lectura más común: transmitimos la dirección y leemos tantos bytes como necesitemos;
2. Grabar
   Escribir en flash NOR parece normal, pero tiene una peculiaridad: solo puedes cambiar de 1 a 0, pero no al revés. Por ejemplo, si teníamos 0x55 en una celda de memoria, luego de escribirle 0x0f, 0x05 ya estará almacenado allí. (ver tabla justo debajo);
3. Borrar:
   Por supuesto, necesitamos poder hacer la operación opuesta: cambiar 0 a 1, para eso es exactamente la operación de borrado. A diferencia de los dos primeros, no funciona con bytes, sino con bloques (el bloque de borrado mínimo en el chip seleccionado es de 4kb). Borrar destruye todo el bloque y es la única forma de cambiar de 0 a 1. Por lo tanto, cuando se trabaja con memoria flash, a menudo es necesario alinear las estructuras de datos con el límite del bloque de borrado.
   Grabación en NOR Flash:

Datos binarios

Fue
01010101

Grabado
00001111

Se convirtió en
00000101

El registro en sí representa una secuencia de registros de longitud variable. La longitud típica de un registro es de unos 30 bytes (aunque a veces se producen registros de varios kilobytes de longitud). En este caso, trabajamos con ellos simplemente como un conjunto de bytes, pero, si te interesa, se utiliza CBOR dentro de los registros.

Además del registro, necesitamos almacenar cierta información de "configuración", tanto actualizada como no: una determinada ID del dispositivo, calibraciones del sensor, un indicador de "dispositivo temporalmente deshabilitado", etc.
Esta información es un conjunto de registros clave-valor, también almacenados en CBOR. No tenemos mucha de esta información (unos pocos kilobytes como máximo) y se actualiza con poca frecuencia.
En lo que sigue lo llamaremos contexto.

Si recordamos dónde comenzó este artículo, es muy importante garantizar un almacenamiento de datos confiable y, si es posible, un funcionamiento continuo incluso en caso de fallas de hardware o corrupción de datos.

¿Qué fuentes de problemas se pueden considerar?

• Apagado durante operaciones de escritura/borrado. Esto pertenece a la categoría de "no hay truco contra la palanca".
  Información de discusiones en stackexchange: cuando se apaga la alimentación mientras se trabaja con flash, tanto borrar (establecer en 1) como escribir (establecer en 0) conducen a un comportamiento indefinido: los datos se pueden escribir, escribir parcialmente (digamos, transferimos 10 bytes/80 bits , pero todavía no se pueden escribir sólo 45 bits), también es posible que algunos de los bits estén en un estado "intermedio" (la lectura puede producir tanto 0 como 1);
• Errores en la propia memoria flash.
  La BER, aunque es muy baja, no puede ser igual a cero;
• Errores de autobús
  Los datos transmitidos a través de SPI no están protegidos de ninguna manera, pueden ocurrir errores de un solo bit y errores de sincronización: pérdida o inserción de bits (lo que conduce a una distorsión masiva de los datos);
• Otros errores/fallos
  Errores en el código, fallos de Raspberry, interferencias extraterrestres...

He formulado los requisitos cuyo cumplimiento, en mi opinión, es necesario para garantizar la fiabilidad:

• los registros deben pasar a la memoria flash inmediatamente, las escrituras retrasadas no se consideran; - si ocurre un error, debe detectarse y procesarse lo antes posible; - el sistema debe, si es posible, recuperarse de los errores.
  (un ejemplo de la vida "cómo no debería ser", que creo que todos han encontrado: después de un reinicio de emergencia, el sistema de archivos está "roto" y el sistema operativo no arranca)

Ideas, enfoques, reflexiones.

Cuando comencé a pensar en este problema, muchas ideas pasaron por mi cabeza, por ejemplo:

• utilizar compresión de datos;
• utilice estructuras de datos inteligentes, por ejemplo, almacenando los encabezados de los registros por separado de los propios registros, de modo que si hay un error en algún registro, pueda leer el resto sin problemas;
• utilice campos de bits para controlar la finalización de la grabación cuando se apaga la alimentación;
• almacenar sumas de verificación para todo;
• utilice algún tipo de codificación resistente al ruido.

Algunas de estas ideas se utilizaron, mientras que otras se decidió abandonar. Vayamos en orden.

Compresión de datos

Los acontecimientos en sí que registramos en el diario son bastante similares y repetibles (“lanzó una moneda de 5 rublos”, “presionó el botón para dar cambio”, ...). Por tanto, la compresión debería ser bastante eficaz.

La sobrecarga de compresión es insignificante (nuestro procesador es bastante potente, incluso el primer Pi tenía un núcleo con una frecuencia de 700 MHz, los modelos actuales tienen varios núcleos con una frecuencia de más de un gigahercio), la tasa de cambio con el almacenamiento es baja (varios megabytes por segundo), el tamaño de los registros es pequeño. En general, si la compresión tiene un impacto en el rendimiento, sólo será positivo. (absolutamente acrítico, solo afirmando). Además, no tenemos Linux incorporado, sino normal, por lo que la implementación no debería requerir mucho esfuerzo (basta con vincular la biblioteca y usar varias funciones de ella).

Se tomó una parte del registro de un dispositivo en funcionamiento (1.7 MB, 70 mil entradas) y primero se verificó la compresibilidad usando gzip, lz4, lzop, bzip2, xz, zstd disponibles en la computadora.

• gzip, xz, zstd mostraron resultados similares (40Kb).
  Me sorprendió que el xz de moda se mostrara aquí al nivel de gzip o zstd;
• lzip con la configuración predeterminada dio resultados ligeramente peores;
• lz4 y lzop no mostraron muy buenos resultados (150Kb);
• bzip2 mostró un resultado sorprendentemente bueno (18Kb).

Entonces, los datos están muy bien comprimidos.
Entonces (si no encontramos fallas fatales) ¡habrá compresión! Simplemente porque en una misma unidad flash caben más datos.

Pensemos en las desventajas.

Primer problema: ya hemos acordado que cada registro debe flashear inmediatamente. Normalmente, el archivador recopila datos del flujo de entrada hasta que decide que es hora de escribir el fin de semana. Necesitamos recibir inmediatamente un bloque de datos comprimido y almacenarlo en una memoria no volátil.

Veo tres maneras:

1. Comprima cada registro utilizando la compresión de diccionario en lugar de los algoritmos comentados anteriormente.
   Es una opción completamente funcional, pero no me gusta. Para garantizar un nivel de compresión más o menos decente, el diccionario debe "adaptarse" a datos específicos; cualquier cambio provocará que el nivel de compresión caiga catastróficamente. Sí, el problema se puede resolver creando una nueva versión del diccionario, pero esto es un dolor de cabeza: necesitaremos almacenar todas las versiones del diccionario; en cada entrada tendremos que indicar con qué versión del diccionario fue comprimido...
2. Comprime cada registro mediante algoritmos “clásicos”, pero independientemente de los demás.
   Los algoritmos de compresión considerados no están diseñados para funcionar con registros de este tamaño (decenas de bytes), la relación de compresión será claramente inferior a 1 (es decir, aumentar el volumen de datos en lugar de comprimir);
3. Haga FLUSH después de cada grabación.
   Muchas bibliotecas de compresión son compatibles con FLUSH. Este es un comando (o un parámetro del procedimiento de compresión), al recibirlo el archivador forma un flujo comprimido para que pueda usarse para restaurar todos datos sin comprimir que ya se han recibido. Tal analogía sync en sistemas de archivos o commit en sql.
   Lo importante es que las operaciones de compresión posteriores podrán utilizar el diccionario acumulado y la relación de compresión no se verá tan afectada como en la versión anterior.

Creo que es obvio que elegí la tercera opción, veámosla con más detalle.

Fundar gran articulo sobre FLUSH en zlib.

Hice una prueba de rodilla basada en el artículo, tomé 70 mil entradas de registro de un dispositivo real, con un tamaño de página de 60 Kb. (volveremos al tamaño de página más adelante) recibió:

Datos iniciales
Compresión gzip -9 (sin FLUSH)
zlib con Z_PARTIAL_FLUSH
zlib con Z_SYNC_FLUSH

Volumen, KB
1692
40
352
604

A primera vista, el precio aportado por FLUSH es excesivamente alto, pero en realidad no tenemos muchas opciones: o no comprimir en absoluto o comprimir (y de manera muy efectiva) con FLUSH. No debemos olvidar que tenemos 70 mil registros, la redundancia introducida por Z_PARTIAL_FLUSH es de sólo 4-5 bytes por registro. Y la relación de compresión resultó ser de casi 5:1, lo que es más que un resultado excelente.

Puede resultar sorprendente, pero Z_SYNC_FLUSH es en realidad una forma más eficiente de realizar FLUSH.

Cuando se usa Z_SYNC_FLUSH, los últimos 4 bytes de cada entrada siempre serán 0x00, 0x00, 0xff, 0xff. Y si los conocemos, entonces no tenemos que almacenarlos, por lo que el tamaño final es de sólo 324Kb.

El artículo al que me vinculé tiene una explicación:

Se agrega un nuevo bloque de tipo 0 con contenido vacío.

Un bloque tipo 0 con contenido vacío consta de:

• el encabezado del bloque de tres bits;
• 0 a 7 bits iguales a cero, para lograr la alineación de bytes;
• la secuencia de cuatro bytes 00 00 FF FF.

Como puede ver fácilmente, en el último bloque antes de estos 4 bytes hay de 3 a 10 bits cero. Sin embargo, la práctica ha demostrado que en realidad hay al menos 10 bits cero.

Resulta que estos bloques de datos cortos suelen (¿siempre?) codificarse utilizando un bloque de tipo 1 (bloque fijo), que necesariamente termina con 7 bits cero, lo que da un total de 10 a 17 bits cero garantizados (y el resto ser cero con una probabilidad de alrededor del 50%).

Entonces, según los datos de prueba, en el 100% de los casos hay un byte cero antes de 0x00, 0x00, 0xff, 0xff, y en más de un tercio de los casos hay dos bytes cero (Quizás el hecho es que uso CBOR binario, y cuando uso texto JSON, los bloques de tipo 2 - bloque dinámico serían más comunes, respectivamente, se encontrarían bloques sin bytes cero adicionales antes de 0x00, 0x00, 0xff, 0xff).

En total, utilizando los datos de prueba disponibles, es posible incluir menos de 250 Kb de datos comprimidos.

Puedes ahorrar un poco más haciendo malabarismos con los bits: por ahora ignoramos la presencia de unos pocos bits cero al final del bloque, algunos bits al principio del bloque tampoco cambian...
Pero luego tomé la firme decisión de dejar de hacerlo, de lo contrario, a este ritmo, podría acabar desarrollando mi propio archivador.

En total, de mis datos de prueba recibí 3-4 bytes por escritura, la relación de compresión resultó ser más de 6:1. Seré honesto: no esperaba tal resultado; en mi opinión, cualquier resultado mejor que 2:1 ya es un resultado que justifica el uso de la compresión.

Todo está bien, pero zlib (deflate) sigue siendo un algoritmo de compresión arcaico, bien merecido y un poco anticuado. El mero hecho de que los últimos 32 KB del flujo de datos sin comprimir se utilicen como diccionario parece extraño hoy (es decir, si algún bloque de datos es muy similar al que estaba en el flujo de entrada hace 40 KB, entonces comenzará a archivarse nuevamente. y no se referirá a un suceso anterior). En los archivadores modernos de moda, el tamaño del diccionario a menudo se mide en megabytes en lugar de kilobytes.

Entonces continuamos nuestro miniestudio sobre los archivadores.

A continuación probamos bzip2 (recuerde, sin FLUSH mostró una relación de compresión fantástica de casi 100:1). Desafortunadamente, funcionó muy mal con FLUSH; el tamaño de los datos comprimidos resultó ser mayor que el de los datos sin comprimir.

Mis suposiciones sobre las razones del fracaso.

Libbz2 ofrece sólo una opción de descarga, que parece borrar el diccionario (análoga a Z_FULL_FLUSH en zlib); no se habla de ninguna compresión efectiva después de esto.

Y el último en ser probado fue zstd. Dependiendo de los parámetros, comprime al nivel de gzip, pero mucho más rápido, o mejor que gzip.

Desgraciadamente, con FLUSH no funcionó muy bien: el tamaño de los datos comprimidos era de unos 700 KB.

Я hizo una pregunta En la página de github del proyecto, recibí una respuesta de que se deben contar con hasta 10 bytes de datos de servicio por cada bloque de datos comprimidos, lo cual se aproxima a los resultados obtenidos; no hay forma de ponerse al día con deflate.

Decidí detenerme en este punto de mis experimentos con archivadores (permítanme recordarles que xz, lzip, lzo, lz4 no se mostraron ni siquiera en la etapa de prueba sin FLUSH, y no consideré algoritmos de compresión más exóticos).

Volvamos a los problemas de archivo.

El segundo problema (como dicen en orden, no en valor) es que los datos comprimidos son un solo flujo, en el que constantemente hay referencias a secciones anteriores. Así, si una sección de datos comprimidos se daña, perdemos no sólo el bloque de datos descomprimidos asociado, sino también todos los posteriores.

Existe un enfoque para resolver este problema:

1. Evite que ocurra el problema: agregue redundancia a los datos comprimidos, lo que le permitirá identificar y corregir errores; hablaremos de esto más tarde;
2. Minimizar las consecuencias si ocurre un problema.
   Ya hemos dicho anteriormente que puede comprimir cada bloque de datos de forma independiente y el problema desaparecerá por sí solo (el daño a los datos de un bloque provocará la pérdida de datos solo para este bloque). Sin embargo, este es un caso extremo en el que la compresión de datos será ineficaz. El extremo opuesto: utilizar los 4 MB de nuestro chip como un único archivo, lo que nos dará una compresión excelente, pero consecuencias catastróficas en caso de corrupción de datos.
   Sí, es necesario un compromiso en términos de fiabilidad. Pero debemos recordar que estamos desarrollando un formato de almacenamiento de datos para memoria no volátil con un BER extremadamente bajo y un período de almacenamiento de datos declarado de 20 años.

Durante los experimentos, descubrí que las pérdidas más o menos notables en el nivel de compresión comienzan en bloques de datos comprimidos de menos de 10 KB de tamaño.
Anteriormente se mencionó que la memoria utilizada es paginada; no veo ninguna razón por la cual no se deba utilizar la correspondencia “una página - un bloque de datos comprimidos”.

Es decir, el tamaño de página mínimo razonable es de 16 KB (con reserva para información de servicio). Sin embargo, un tamaño de página tan pequeño impone restricciones significativas sobre el tamaño máximo de registro.

Aunque todavía no espero registros de más de unos pocos kilobytes en forma comprimida, decidí usar páginas de 32 Kb (para un total de 128 páginas por chip).

Resumen:

• Almacenamos datos comprimidos usando zlib (deflate);
• Para cada entrada configuramos Z_SYNC_FLUSH;
• Para cada registro comprimido, recortamos los bytes finales. (por ejemplo, 0x00, 0x00, 0xff, 0xff); en el encabezado indicamos cuántos bytes cortamos;
• Almacenamos datos en páginas de 32Kb; hay un único flujo de datos comprimidos dentro de la página; En cada página comenzamos la compresión nuevamente.

Y, antes de terminar con la compresión, me gustaría llamar su atención sobre el hecho de que solo tenemos unos pocos bytes de datos comprimidos por registro, por lo que es sumamente importante no inflar la información del servicio, aquí cada byte cuenta.

Almacenamiento de encabezados de datos

Dado que tenemos registros de longitud variable, necesitamos determinar de alguna manera la ubicación/límites de los registros.

Conozco tres enfoques:

1. Todos los registros se almacenan en un flujo continuo, primero hay un encabezado de registro que contiene la longitud y luego el registro en sí.
   En esta realización, tanto los encabezados como los datos pueden tener una longitud variable.
   Básicamente, obtenemos una lista enlazada individualmente que se utiliza todo el tiempo;
2. Los encabezados y los propios registros se almacenan en flujos separados.
   Al utilizar cabezales de longitud constante, nos aseguramos de que el daño a un cabezal no afecte a los demás.
   Se utiliza un enfoque similar, por ejemplo, en muchos sistemas de archivos;
3. Los registros se almacenan en un flujo continuo, el límite del registro está determinado por un determinado marcador (un carácter/secuencia de caracteres que está prohibido dentro de los bloques de datos). Si hay un marcador dentro del registro, lo reemplazamos con alguna secuencia (escapamos de ella).
   Un enfoque similar se utiliza, por ejemplo, en el protocolo PPP.

Voy a ilustrar

Opción 1:

Aquí todo es muy sencillo: conociendo la longitud del registro, podemos calcular la dirección del siguiente encabezado. Así que avanzamos por los encabezados hasta encontrar un área llena de 0xff (área libre) o el final de la página.

Opción 2:

Debido a la longitud variable de los registros, no podemos decir de antemano cuántos registros (y por lo tanto encabezados) necesitaremos por página. Puedes distribuir los encabezados y los datos en diferentes páginas, pero yo prefiero un enfoque diferente: colocamos tanto los encabezados como los datos en una página, pero los encabezados (de tamaño constante) provienen del principio de la página y el los datos (de longitud variable) provienen del final. Tan pronto como se “encuentran” (no hay suficiente espacio libre para una nueva entrada), consideramos que esta página está completa.

Opción 3:

No es necesario almacenar la longitud u otra información sobre la ubicación de los datos en el encabezado; los marcadores que indican los límites de los registros son suficientes. Sin embargo, los datos deben procesarse al escribir/leer.
Usaría 0xff como marcador (que llena la página después de borrarlo), por lo que el área libre definitivamente no se tratará como datos.

Tabla de comparación:

1 opción
2 opción
3 opción

Tolerancia a errores
-
+
+

Compacidad
+
-
+

Complejidad de implementación
*
**
**

La opción 1 tiene un defecto fatal: si alguno de los cabezales se daña, toda la cadena posterior se destruye. Las opciones restantes le permiten recuperar algunos datos incluso en caso de daños masivos.
Pero aquí conviene recordar que decidimos almacenar los datos en forma comprimida, por lo que perdemos todos los datos de la página después de un registro "roto", por lo que aunque hay un signo negativo en la tabla, no lo hacemos. tenlo en cuenta.

Compacidad:

• en la primera opción, necesitamos almacenar solo la longitud en el encabezado, si usamos números enteros de longitud variable, en la mayoría de los casos podemos arreglárnoslas con un byte;
• en la segunda opción necesitamos almacenar la dirección inicial y la longitud; el registro debe tener un tamaño constante, calculo 4 bytes por registro (dos bytes para el desplazamiento y dos bytes para la longitud);
• la tercera opción solo necesita un carácter para indicar el inicio de la grabación, además la grabación en sí aumentará entre un 1 y un 2% debido al blindaje. En general, aproximadamente a la par con la primera opción.

Inicialmente, consideré la segunda opción como la principal (e incluso escribí la implementación). Lo abandoné sólo cuando finalmente decidí usar la compresión.

Quizás algún día siga usando una opción similar. Por ejemplo, si tengo que lidiar con el almacenamiento de datos para una nave que viaja entre la Tierra y Marte, habrá requisitos completamente diferentes en cuanto a confiabilidad, radiación cósmica, ...

En cuanto a la tercera opción: le di dos estrellas por la dificultad de implementación simplemente porque no me gusta jugar con el blindaje, cambiar la longitud en el proceso, etc. Sí, tal vez sea parcial, pero tendré que escribir el código; ¿por qué obligarte a hacer algo que no te gusta?

Resumen: Elegimos la opción de almacenamiento en forma de cadenas "encabezado con longitud - datos de longitud variable" debido a la eficiencia y facilidad de implementación.

Uso de campos de bits para monitorear el éxito de las operaciones de escritura

No recuerdo ahora de dónde saqué la idea, pero se parece a esto:
Para cada entrada, asignamos varios bits para almacenar banderas.
Como dijimos anteriormente, después de borrar todos los bits se llenan con 1 y podemos cambiar 1 a 0, pero no al revés. Entonces, para "la bandera no está configurada" usamos 1, para "la bandera está configurada" usamos 0.

Así es como se vería poner un registro de longitud variable en flash:

1. Establezca la bandera "la grabación de duración ha comenzado";
2. Registre la longitud;
3. Establezca el indicador "la grabación de datos ha comenzado";
4. Registramos datos;
5. Configure el indicador "grabación finalizada".

Además, tendremos un indicador de "error ocurrido", para un total de indicadores de 4 bits.

En este caso, tenemos dos estados estables "1111" - la grabación no ha comenzado y "1000" - la grabación se realizó correctamente; En caso de una interrupción inesperada del proceso de grabación, recibiremos estados intermedios, que luego podremos detectar y procesar.

El enfoque es interesante, pero solo protege contra cortes repentinos de energía y fallas similares, lo cual, por supuesto, es importante, pero está lejos de ser la única (o incluso la principal) razón de posibles fallas.

Resumen: Sigamos adelante en busca de una buena solución.

sumas de control

Las sumas de verificación también permiten asegurarnos (con una probabilidad razonable) de que estamos leyendo exactamente lo que debería haberse escrito. Y, a diferencia de los campos de bits comentados anteriormente, siempre funcionan.

Si consideramos la lista de posibles fuentes de problemas que discutimos anteriormente, entonces la suma de verificación puede reconocer un error independientemente de su origen. (excepto, quizás, los extraterrestres maliciosos, que también pueden falsificar la suma de verificación).

Entonces, si nuestro objetivo es verificar que los datos estén intactos, las sumas de verificación son una gran idea.

La elección del algoritmo para calcular la suma de comprobación no generó dudas: CRC. Por un lado, las propiedades matemáticas permiten detectar ciertos tipos de errores al 100%; por otro lado, en datos aleatorios, este algoritmo generalmente muestra una probabilidad de colisiones no mucho mayor que el límite teórico. . Puede que no sea el algoritmo más rápido, ni siempre el mínimo en cuanto a número de colisiones, pero tiene una cualidad muy importante: en las pruebas que encontré, no hubo patrones en los que fallara claramente. La estabilidad es la principal cualidad en este caso.

Ejemplo de estudio volumétrico: Parte 1, Parte 2 (enlaces a narod.ru, lo siento).

Sin embargo, la tarea de seleccionar una suma de verificación no está completa; CRC es toda una familia de sumas de verificación. Debes decidir la longitud y luego elegir un polinomio.

Elegir la longitud de la suma de comprobación no es una cuestión tan sencilla como parece a primera vista.

Permítanme ilustrar:
Tengamos la probabilidad de un error en cada byte. y una suma de verificación ideal, calculemos el número promedio de errores por millón de registros:

Datos, bytes
Suma de comprobación, byte
Errores no detectados
Detecciones de errores falsos
Total de falsos positivos

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

Parecería que todo es simple: dependiendo de la longitud de los datos a proteger, elija la longitud de la suma de verificación con un mínimo de positivos incorrectos, y el truco está en la bolsa.

Sin embargo, surge un problema con las sumas de comprobación cortas: aunque son buenas para detectar errores de un solo bit, con una probabilidad bastante alta pueden aceptar como correctos datos completamente aleatorios. Ya había un artículo sobre Habré que describía problema en la vida real.

Por lo tanto, para hacer casi imposible una coincidencia aleatoria de sumas de verificación, es necesario utilizar sumas de verificación de 32 bits o más de longitud. (para longitudes superiores a 64 bits, se suelen utilizar funciones hash criptográficas).

A pesar de que escribí anteriormente que necesitamos ahorrar espacio por todos los medios, seguiremos usando una suma de comprobación de 32 bits (16 bits no son suficientes, la probabilidad de colisión es superior al 0.01%; y 24 bits, ya que decir, no están ni aquí ni allá).

Aquí puede surgir una objeción: ¿guardamos cada byte al elegir la compresión para ahora dar 4 bytes a la vez? ¿No sería mejor no comprimir ni añadir una suma de comprobación? Por supuesto que no, sin compresión. no significa, que no necesitamos verificación de integridad.

Al elegir un polinomio, no reinventaremos la rueda, sino que tomaremos el ahora popular CRC-32C.
Este código detecta errores de 6 bits en paquetes de hasta 22 bytes (quizás el caso más común para nosotros), errores de 4 bits en paquetes de hasta 655 bytes (también un caso común para nosotros), errores de 2 o cualquier número impar de bits en paquetes. de cualquier duración razonable.

Si a alguien le interesan los detalles

Artículo de Wikipedia sobre la CDN.

Parámetros del código CRC-32c en Sitio web de Koopman — quizás el principal especialista en CCR del planeta.

В su articulo есть otro código interesante, que proporciona parámetros ligeramente mejores para las longitudes de paquetes que son relevantes para nosotros, pero no consideré la diferencia significativa y fui lo suficientemente competente como para elegir un código personalizado en lugar del estándar y bien investigado.

Además, dado que nuestros datos están comprimidos, surge la pregunta: ¿deberíamos calcular la suma de comprobación de los datos comprimidos o sin comprimir?

Argumentos a favor de calcular la suma de comprobación de datos sin comprimir:

• En última instancia, necesitamos verificar la seguridad del almacenamiento de datos, por lo que lo verificamos directamente (al mismo tiempo, se verificarán posibles errores en la implementación de la compresión/descompresión, daños causados ​​por memoria rota, etc.);
• El algoritmo deflate en zlib tiene una implementación bastante madura y no debería caer con datos de entrada "torcidos"; además, a menudo es capaz de detectar errores de forma independiente en el flujo de entrada, lo que reduce la probabilidad general de no detectar un error (se llevó a cabo una prueba invirtiendo un solo bit en un registro corto, zlib detectó un error en aproximadamente un tercio de los casos).

Argumentos en contra del cálculo de la suma de comprobación de datos sin comprimir:

• CRC está "adaptado" específicamente para los pocos errores de bits que son característicos de la memoria flash (un error de bits en un flujo comprimido puede causar un cambio masivo en el flujo de salida, en el que, puramente teóricamente, podemos "captar" una colisión);
• Realmente no me gusta la idea de pasar datos potencialmente rotos al descompresor, quien sabecómo reaccionará.

En este proyecto, decidí desviarme de la práctica generalmente aceptada de almacenar una suma de verificación de datos sin comprimir.

Resumen: Usamos CRC-32C, calculamos la suma de verificación a partir de los datos en la forma en que están escritos en la memoria flash (después de la compresión).

Redundancia

Por supuesto, el uso de codificación redundante no elimina la pérdida de datos; sin embargo, puede reducir significativamente (a menudo en muchos órdenes de magnitud) la probabilidad de una pérdida irrecuperable de datos.

Podemos utilizar diferentes tipos de redundancia para corregir errores.
Los códigos Hamming pueden corregir errores de un solo bit, los códigos de caracteres Reed-Solomon, múltiples copias de datos combinadas con sumas de verificación o codificaciones como RAID-6 pueden ayudar a recuperar datos incluso en caso de corrupción masiva.
Inicialmente, estaba comprometido con el uso generalizado de codificación resistente a errores, pero luego me di cuenta de que primero debemos tener una idea de qué errores queremos protegernos y luego elegir la codificación.

Dijimos anteriormente que los errores deben detectarse lo más rápido posible. ¿En qué puntos podemos encontrar errores?

1. Grabación sin terminar (por alguna razón en el momento de grabar se cortó la corriente, la Raspberry se congeló,...)
   Por desgracia, en caso de tal error, solo queda ignorar los registros no válidos y considerar los datos perdidos;
2. Errores de escritura (por alguna razón, lo que se escribió en la memoria flash no fue lo que se escribió)
   Podemos detectar inmediatamente dichos errores si hacemos una lectura de prueba inmediatamente después de la grabación;
3. Distorsión de datos en la memoria durante el almacenamiento;
4. Errores de lectura
   Para corregirlo, si el checksum no coincide, basta con repetir la lectura varias veces.

Es decir, sólo los errores del tercer tipo (corrección espontánea de datos durante el almacenamiento) no pueden corregirse sin una codificación resistente a errores. Parece que tales errores siguen siendo extremadamente improbables.

Resumen: Se decidió abandonar la codificación redundante, pero si la operación muestra el error de esta decisión, entonces se volverá a considerar el problema (con estadísticas ya acumuladas sobre fallas, que permitirán elegir el tipo óptimo de codificación).

otro

Por supuesto, el formato del artículo no nos permite justificar cada detalle del formato. (y ya se me acabaron las fuerzas), así que repasaré brevemente algunos puntos que no se han abordado antes.

• Se decidió hacer todas las páginas “iguales”
  Es decir, no habrá páginas especiales con metadatos, hilos separados, etc., sino un único hilo que reescribe todas las páginas por turno.
  Esto asegura un desgaste uniforme de las páginas, sin ningún punto de falla, y simplemente me gusta;
• Es imperativo proporcionar versiones del formato.
  ¡Un formato sin un número de versión en el encabezado es malo!
  Basta con agregar un campo con un determinado Número Mágico (firma) al encabezado de la página, que indicará la versión del formato utilizado. (No creo que en la práctica haya ni siquiera una docena);
• Utilice un encabezado de longitud variable para los registros (de los cuales hay muchos), intentando que tenga 1 byte de longitud en la mayoría de los casos;
• Para codificar la longitud del encabezado y la longitud de la parte recortada del registro comprimido, utilice códigos binarios de longitud variable.

ayudó mucho generador en línea Códigos Huffman. En tan solo unos minutos pudimos seleccionar los códigos de longitud variable necesarios.

Descripción del formato de almacenamiento de datos.

Orden de bytes

Los campos de más de un byte se almacenan en formato big-endian (orden de bytes de red), es decir, 0x1234 se escribe como 0x12, 0x34.

Paginación

Toda la memoria flash se divide en páginas de igual tamaño.

El tamaño de página predeterminado es 32 KB, pero no más de 1/4 del tamaño total del chip de memoria (para un chip de 4 MB, se obtienen 128 páginas).

Cada página almacena datos independientemente de las demás (es decir, los datos de una página no hacen referencia a los datos de otra página).

Todas las páginas están numeradas en orden natural (en orden ascendente de direcciones), comenzando con el número 0 (la página cero comienza en la dirección 0, la primera página comienza en 32 Kb, la segunda página comienza en 64 Kb, etc.)

El chip de memoria se utiliza como buffer cíclico (buffer circular), es decir, primero se escribe a la página número 0, luego a la número 1,..., cuando llenamos la última página, comienza un nuevo ciclo y la grabación continúa desde la página cero. .

Dentro de la pagina

Al comienzo de la página, se almacena un encabezado de página de 4 bytes, luego una suma de verificación del encabezado (CRC-32C) y luego los registros se almacenan en el formato "encabezado, datos, suma de verificación".

El título de la página (verde sucio en el diagrama) consta de:

• Campo de número mágico de dos bytes (también un signo de la versión del formato)
  para la versión actual del formato se calcula como 0xed00 ⊕ номер страницы;
• Contador de dos bytes “Versión de página” (número de ciclo de reescritura de memoria).

Las entradas de la página se almacenan en forma comprimida (se utiliza el algoritmo deflate). Todos los registros de una página se comprimen en un hilo (se utiliza un diccionario común) y en cada nueva página la compresión comienza de nuevo. Es decir, para descomprimir cualquier registro, se requieren todos los registros anteriores de esta página (y sólo éste).

Cada registro se comprimirá con el indicador Z_SYNC_FLUSH y al final del flujo comprimido habrá 4 bytes 0x00, 0x00, 0xff, 0xff, posiblemente precedidos por uno o dos bytes cero más.
Descartamos esta secuencia (4, 5 o 6 bytes de longitud) al escribir en la memoria flash.

El encabezado del registro tiene 1, 2 o 3 bytes y almacena:

• un bit (T) que indica el tipo de registro: 0 - contexto, 1 - registro;
• un campo de longitud variable (S) de 1 a 7 bits, que define la longitud del encabezado y la “cola” que se debe agregar al registro para su descompresión;
• longitud del registro (L).

Tabla de valores S:

S
Longitud del encabezado, bytes
Descartado al escribir, 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)

Intenté ilustrarlo, no sé con qué claridad quedó:

El amarillo aquí indica el campo T, el blanco el campo S, el verde L (la longitud de los datos comprimidos en bytes), el azul los datos comprimidos y el rojo los bytes finales de los datos comprimidos que no están escritos en la memoria flash.

Por lo tanto, podemos escribir encabezados de registros de la longitud más común (hasta 63+5 bytes en forma comprimida) en un byte.

Después de cada registro, se almacena una suma de verificación CRC-32C, en la que el valor invertido de la suma de verificación anterior se utiliza como valor inicial (init).

CRC tiene la propiedad de "duración", la siguiente fórmula funciona (más o menos inversión de bits en el proceso): .
Es decir, de hecho, calculamos el CRC de todos los bytes anteriores de encabezados y datos en esta página.

Directamente después de la suma de verificación está el encabezado del siguiente registro.

El encabezado está diseñado de tal manera que su primer byte siempre es diferente de 0x00 y 0xff (si en lugar del primer byte del encabezado encontramos 0xff, entonces esto significa que se trata de un área no utilizada; 0x00 indica un error).

Algoritmos de ejemplo

Lectura de la memoria flash

Cualquier lectura viene con una verificación de suma de verificación.
Si la suma de verificación no coincide, la lectura se repite varias veces con la esperanza de leer los datos correctos.

(Esto tiene sentido, Linux no almacena en caché las lecturas de NOR Flash, probado)

Escribir en la memoria flash

Registramos los datos.
Leámoslos.

Si los datos leídos no coinciden con los datos escritos, llenamos el área con ceros y señalamos un error.

Preparando un nuevo microcircuito para su funcionamiento.

Para la inicialización, se escribe un encabezado con la versión 1 en la primera (o más bien en cero) página.
Después de eso, el contexto inicial se escribe en esta página (contiene el UUID de la máquina y la configuración predeterminada).

Eso es todo, la memoria flash está lista para usar.

Cargando la máquina

Al cargar, se leen los primeros 8 bytes de cada página (encabezado + CRC), se ignoran las páginas con un Número Mágico desconocido o un CRC incorrecto.
De las páginas “correctas”, se seleccionan las páginas con la versión máxima y de ellas se toma la página con el número más alto.
Se lee el primer registro, se verifica la exactitud del CRC y la presencia de la bandera "contexto". Si todo está bien, esta página se considera actual. Si no, volvemos a la anterior hasta encontrar una página “en vivo”.
y en la página encontrada leemos todos los registros, aquellos que usamos con la bandera “contexto”.
Guarde el diccionario zlib (será necesario para agregarlo a esta página).

Todo, la descarga está completa, el contexto se restaura, puedes trabajar.

Agregar una entrada de diario

Comprimimos el registro con el diccionario correcto, especificando Z_SYNC_FLUSH y vemos si el registro comprimido cabe en la página actual.
Si no encaja (o hubo errores CRC en la página), comience una nueva página (ver más abajo).
Anotamos el acta y el CRC. Si ocurre un error, comience una nueva página.

Nueva pagina

Seleccionamos una página gratuita con el número mínimo (consideramos página gratuita una página con una suma de comprobación incorrecta en el encabezado o con una versión inferior a la actual). Si no existen dichas páginas, seleccione la página con el número mínimo de aquellas que tienen una versión igual a la actual.
Borramos la página seleccionada. Comprobamos el contenido con 0xff. Si algo anda mal, pase a la siguiente página gratuita, etc.
Escribimos un encabezado en la página borrada, la primera entrada es el estado actual del contexto, la siguiente es la entrada del registro no escrita (si existe).

Aplicabilidad del formato

En mi opinión, resultó ser un buen formato para almacenar flujos de información más o menos comprimibles (texto sin formato, JSON, MessagePack, CBOR, posiblemente protobuf) en NOR Flash.

Por supuesto, el formato está "adaptado" para SLC NOR Flash.

No debe usarse con medios con alto BER como NAND o MLC NOR. (¿Esa memoria está siquiera disponible para la venta? Solo la he visto mencionada en trabajos sobre códigos de corrección).

Además, no se debe utilizar con dispositivos que tengan su propia FTL: USB flash, SD, MicroSD, etc. (para dicha memoria creé un formato con un tamaño de página de 512 bytes, una firma al principio de cada página y números de registro únicos; a veces era posible recuperar todos los datos de una unidad flash "defectuosa" mediante una simple lectura secuencial).

Dependiendo de las tareas, el formato se puede utilizar sin cambios en unidades flash de 128 Kbit (16 Kb) a 1 Gbit (128 MB). Si lo deseas, puedes usarlo en chips más grandes, pero probablemente necesites ajustar el tamaño de la página. (Pero aquí ya surge la cuestión de la viabilidad económica; el precio de NOR Flash de gran volumen no es alentador).

Si alguien encuentra interesante el formato y quiere usarlo en un proyecto abierto, escriba, intentaré encontrar tiempo, pulir el código y publicarlo en github.

Conclusión

Como puedes ver, al final el formato resultó sencillo. y hasta aburrido.

Es difícil reflejar la evolución de mi punto de vista en un artículo, pero créanme: inicialmente quería crear algo sofisticado, indestructible, capaz de sobrevivir incluso a una explosión nuclear en las proximidades. Sin embargo, la razón (espero) todavía ganó y gradualmente las prioridades cambiaron hacia la simplicidad y la compacidad.

¿Será que me equivoqué? Si seguro. Bien puede resultar, por ejemplo, que hayamos comprado un lote de microcircuitos de baja calidad. O por alguna otra razón el equipo no cumplirá con las expectativas de confiabilidad.

¿Tengo un plan para esto? Creo que después de leer el artículo no te queda duda de que hay un plan. Y ni siquiera solo.

En una nota un poco más seria, el formato se desarrolló como una opción de trabajo y como un “globo de prueba”.

Por el momento todo lo que está sobre la mesa está funcionando bien, literalmente el otro día se implementará la solución. (aproximadamente) en cientos de dispositivos, veamos qué sucede en la operación de “combate” (afortunadamente, espero que el formato le permita detectar fallas de manera confiable; para que pueda recopilar estadísticas completas). En unos meses se podrán sacar conclusiones (y si no tienes suerte, incluso antes).

Si, según los resultados del uso, se descubren problemas graves y se requieren mejoras, definitivamente escribiré sobre ello.

Literatura

No quería hacer una lista larga y tediosa de obras usadas; al fin y al cabo, todo el mundo tiene Google.

Aquí decidí dejar una lista de hallazgos que me parecieron particularmente interesantes, pero gradualmente migraron directamente al texto del artículo y un elemento permaneció en la lista:

1. Utilidad Infgen del autor zlib. Puede mostrar claramente el contenido de los archivos deflate/zlib/gzip. Si tiene que lidiar con la estructura interna del formato deflate (o gzip), lo recomiendo encarecidamente.

Fuente: habr.com