Mi implementación de buffer de anillo en flash NOR

Antecedentes


Hay máquinas expendedoras de nuestro propio diseño. Dentro de la Raspberry Pi y un poco de flejes en una placa separada. Un aceptador de monedas, un aceptador de billetes, una terminal bancaria están conectados ... Un programa autoescrito maneja todo. Toda la historia del trabajo se escribe en la revista en una unidad flash USB (MicroSD), que luego se transmite a través de Internet (utilizando un módem USB) al servidor, donde se agrega a la base de datos. La información de ventas se carga en 1s, también hay una interfaz web simple para monitoreo, etc.


Es decir, la revista es vital: para la contabilidad (hay ingresos, ventas, etc.), monitoreo (todo tipo de fallas y otras circunstancias de fuerza mayor); Esto, se puede decir, toda la información que tenemos sobre esta máquina.


El problema


Las unidades flash se muestran como dispositivos muy poco confiables. Fallan con envidiable regularidad. Esto conduce al tiempo de inactividad de la máquina y (si por alguna razón el diario no se pudo transmitir en línea) a la pérdida de datos.


Esta no es la primera experiencia de usar unidades flash, antes de que hubiera otro proyecto con más de cien dispositivos donde la revista se almacenaba en unidades flash USB, también hubo problemas de confiabilidad, a veces la cantidad de fallas por mes era decenas. Probamos diferentes unidades flash, incluidas las de marca en la memoria SLC, y algunos modelos son más confiables que otros, pero reemplazar las unidades flash no resolvió el problema radicalmente.


Atencion Longrid! Si no está interesado en “por qué”, sino solo en “cómo”, puede ir inmediatamente al final del artículo.


Solución


Lo primero que viene a la mente: abandonar MicroSD, poner, por ejemplo, SSD, y arrancar desde allí. Es teóricamente posible, probablemente, pero relativamente costoso y no tan confiable (se agrega un adaptador USB-SATA; en los SSD de presupuesto, las estadísticas de fallas tampoco son satisfactorias).


USB HDD tampoco parece una solución particularmente atractiva.


Por lo tanto, llegamos a esta opción: deje la descarga desde MicroSD, pero úsela en modo de solo lectura y almacene el registro de operaciones (y otra información exclusiva de una pieza específica de hardware: número de serie, calibraciones de sensores, etc.) en otro lugar.


El tema de FS de solo lectura para frambuesas ya se ha estudiado a lo largo y ancho, no me detendré en los detalles de la implementación en este artículo (pero si hay interés, tal vez escribiré un mini artículo sobre este tema) . El único punto que quiero señalar: tanto por experiencia personal como por revisiones que ya han implementado una ganancia en confiabilidad, es. Sí, es imposible deshacerse por completo de las averías, pero es bastante posible reducir significativamente su frecuencia. Sí, y las tarjetas se unifican, lo que simplifica enormemente el reemplazo del personal de mantenimiento.


Hardware


No había dudas sobre la elección del tipo de memoria: NOR Flash.
Argumentos:


  • conexión simple (más a menudo el bus SPI, la experiencia de uso que ya está allí, por lo que no se esperan problemas "de hierro");
  • precio ridículo;
  • protocolo operativo estándar (la implementación ya está en el kernel de Linux, si lo desea, puede tomar un tercero, que también está presente, o incluso escribir el suyo, el beneficio es simple);
  • fiabilidad y recursos:
    de una hoja de datos típica: los datos se almacenan durante 20 años, 100,000 ciclos de borrado para cada bloque;
    de fuentes de terceros: BER extremadamente bajo, se postula que no hay necesidad de códigos de corrección de errores (en algunos documentos se considera ECC para NOR, pero generalmente MLC NOR se entiende allí, sucede) .

Permítanos estimar los requisitos de volumen y recursos.


Quiero tener la garantía de guardar datos durante varios días. Esto es necesario para que en caso de problemas con la conexión no se pierda el historial de ventas. Nos centraremos en 5 días, durante este período (incluso teniendo en cuenta los fines de semana y días festivos), podemos resolver el problema.


Ahora estamos escribiendo alrededor de 100kb de revistas por día (3-4 mil registros), pero gradualmente esta cifra está creciendo: los detalles están aumentando, se están agregando nuevos eventos. Además, a veces hay ráfagas (algunos sensores comienzan a enviar spam con falsos positivos, por ejemplo). Calcularemos 10 mil registros de 100 bytes - megabytes por día.


Sale un total de 5 MB de datos limpios (bien comprimibles). También (estimación aproximada) 1 MB de datos de servicio.


Es decir, necesitamos un microchip de 8 MB si no usa compresión, o 4 MB si lo usa. Números bastante reales para este tipo de memoria.


En cuanto al recurso: si planeamos reescribir toda la memoria no más de una vez cada 5 días, en 10 años de servicio obtendremos menos de mil ciclos de reescritura.
Recuerdo que el fabricante promete cien mil.


Un poco sobre NOR vs NAND

Hoy, por supuesto, la memoria NAND es mucho más popular, pero para este proyecto no la usaría: NAND, a diferencia de NOR, necesariamente requiere el uso de códigos de corrección de errores, una tabla de bloques defectuosos, etc., y las patas de los chips NAND Por lo general, mucho más.


Las desventajas de NOR incluyen:


  • pequeño volumen (y, en consecuencia, alto precio por megabyte);
  • bajo tipo de cambio (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, toma de fracciones de un segundo a varios segundos).

Parece que no es nada crítico para nosotros, así que continúe.


Si los detalles son interesantes, se eligió el chip at25df321a (sin embargo, esto es insignificante, hay muchos análogos en el mercado que son compatibles con el pinout y el sistema de comando; incluso si queremos colocar el chip de otro fabricante y / u otro volumen, 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 /boot/config.txt un poco.


Archivo dts de ejemplo

Honestamente, no estoy seguro de lo 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 conectar el chip a la Raspberry Pi. Por un lado, no soy un experto en electrónica, por otro lado, todo es trivial incluso para mí: el microcircuito tiene solo 8 patas, de las cuales necesitamos tierra, potencia, SPI (CS, SI, SO, SCK); los niveles coinciden con los de Raspberry Pi, no se requiere enlace adicional, solo conecte los 6 contactos especificados.


Declaración del problema.


Como de costumbre, la formulación del problema pasa por varias iteraciones, me parece que ha llegado el momento de la próxima. Entonces detengámonos, juntemos lo que ya se ha escrito y aclaremos los detalles que quedan en las sombras.


Por lo tanto, decidimos que el registro se almacenará en SPI NOR Flash.


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

Esta es una memoria no volátil con la que puede realizar tres operaciones:


  1. Lectura:
    La lectura más común: pasamos la dirección y leemos todos los bytes que necesitamos;
  2. Registro:
    Escribir en flash NOR parece normal, pero tiene una peculiaridad: solo puede cambiar de 1 a 0, pero no al revés. Por ejemplo, si teníamos 0x55 en la celda de memoria, luego de escribirle 0x0f, 0x05 ya estará almacenado allí (consulte la tabla a continuación) ;
  3. Borrar:
    Por supuesto, también debemos ser capaces de hacer la operación inversa: cambiar de 0 a 1, razón por la cual existe la operación de borrado. A diferencia de los dos primeros, funciona no en bytes, sino en bloques (el bloque de borrado mínimo en el microcircuito seleccionado es 4kb). Borrar destruye todo el bloque y esta es la única forma de cambiar de 0 a 1. Por lo tanto, cuando se trabaja con memoria flash, a menudo tiene que alinear las estructuras de datos con el borde del bloque de borrado.
    Grabar en NOR Flash:

Datos binarios
Era01010101
Grabado00001111
Se ha convertido00000101

El diario en sí representa una secuencia de registros de longitud variable. Una longitud de grabación típica es de aproximadamente 30 bytes (aunque a veces ocurren grabaciones de varios kilobytes de longitud). En este caso, trabajamos con ellos como un conjunto de bytes, pero, si le interesa, CBOR se usa dentro de los registros.


Además del diario, necesitamos almacenar cierta información de "ajuste", ya sea actualizada o no: una determinada identificación del dispositivo, calibración del sensor, el indicador "dispositivo está temporalmente desactivado", etc.
Esta información es un conjunto de registros de valores clave, también almacenados en CBOR. No tenemos mucha de esta información (unos pocos kilobytes como máximo), se actualiza con poca frecuencia.
En el futuro, lo llamaremos contexto.


Si recuerda dónde comenzó este artículo, es muy importante garantizar la fiabilidad del almacenamiento de datos y, si es posible, la operación continua incluso en caso de fallas de hardware / corrupción de datos.


¿Qué fuentes de problemas pueden considerarse?


  • Apague durante las operaciones de escritura / borrado. Esto es de la categoría de "contra la chatarra sin recepción".
    Información de la discusión sobre stackexchange: cuando apaga la alimentación mientras trabaja con flash, eso borra (configuración a 1), esa escritura (configuración a 0) conduce a un comportamiento indefinido: los datos se pueden escribir, escribir parcialmente (por ejemplo, transferimos 10 bytes / 80 bits , y solo se lograron grabar 45 bits), también es posible que algunos de los bits estén en el estado "intermedio" (la lectura puede producir 0 o 1);
  • Errores de la memoria flash en sí.
    BER, aunque muy bajo, no puede ser igual a cero;
  • Errores de bus
    Los datos transmitidos a través de SPI no están protegidos de ninguna manera, bien pueden ocurrir como errores de un solo bit o errores de sincronización: pérdida o inserción de bits (lo que conduce a una distorsión masiva de datos);
  • Otros errores / fallas
    Errores en el código, fracasos de frambuesa, intervención alienígena ...

Formulé requisitos, cuyo cumplimiento, en mi opinión, es necesario para garantizar la confiabilidad:


  • Los registros deben escribirse en la memoria flash de inmediato, no se considera la grabación pendiente; si se produce un error, debe detectarse y procesarse lo antes posible; el sistema debe, si es posible, recuperarse de los errores.
    (un ejemplo de la vida "como no debería ser", que, creo, todos se encontraron: después de un reinicio de emergencia, el sistema de archivos "se rompió" y el sistema operativo no se inicia)

Ideas, enfoques, pensamientos


Cuando comencé a pensar en esta tarea, un montón de ideas pasaron por mi cabeza, por ejemplo:


  • Usar compresión de datos
  • Utilice estructuras de datos complicadas, por ejemplo, almacene encabezados de registro por separado de los registros mismos, de modo que si se produce un error en un registro, puede leer el resto sin ningún problema;
  • use campos de bits para controlar la integridad de la grabación cuando se apaga la alimentación;
  • almacenar sumas de comprobación para todo y para todo;
  • use algún tipo de codificación de corrección de errores.

Se utilizaron algunas de estas ideas, se decidió rechazar algunas. Vamos en orden.


Compresión de datos


Los eventos que registramos en el diario en sí son bastante iguales y repetibles ("arrojó una moneda de 5 rublos", "hizo clic en el botón de cambio de entrega", ...). Por lo tanto, la compresión debería ser bastante efectiva.


La sobrecarga para la compresión es insignificante (el procesador que tenemos es bastante potente, incluso en el primer Pi había un núcleo con una frecuencia de 700 MHz, en los modelos actuales había varios núcleos con una frecuencia de más de un gigahercio), la velocidad de intercambio con el almacenamiento es baja (varios megabytes por segundo), el tamaño del registro es pequeño. En general, si la compresión afectará el rendimiento, entonces solo es positivo (absolutamente no crítico, solo afirmativo) . Además, no tenemos un Linux real incrustado, sino ordinario, por lo que la implementación no debería requerir mucho esfuerzo (solo vincula la biblioteca y usa varias funciones de ella).


Se tomó una parte del registro del dispositivo de trabajo (1.7 MB, 70 mil registros) y, para empezar, se verificó la compresibilidad utilizando gzip, lz4, lzop, bzip2, xz, zstd disponibles en la computadora.


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

Entonces los datos se comprimen muy bien.
Entonces (si no encontramos fallas fatales) ¡debería haber compresión! Solo porque caben más datos en la misma unidad flash.


Pensemos en los defectos.


El primer problema: ya hemos acordado que cada registro debe comenzar de inmediato. Por lo general, el archivador recopila datos de la secuencia de entrada hasta que decide que es hora de escribir en la salida. Necesitamos obtener inmediatamente un bloque de datos comprimido y guardarlo en una memoria no volátil.


Veo tres formas:


  1. Comprima cada entrada usando la compresión del diccionario en lugar de los algoritmos discutidos anteriormente.
    Es una opción de trabajo, pero no me gusta. Para garantizar un nivel de compresión más o menos decente, el diccionario debe ser "afilado" para datos específicos, cualquier cambio conducirá al hecho de que el nivel de compresión cae catastróficamente. Sí, el problema se resuelve creando una nueva versión del diccionario, pero esto es un dolor de cabeza: necesitaremos almacenar todas las versiones del diccionario; en cada entrada necesitaremos indicar con qué versión del diccionario fue comprimido ...
  2. Comprima cada entrada con algoritmos "clásicos", pero independientemente de los demás.
    Los algoritmos de compresión considerados no están diseñados para trabajar con registros de este tamaño (decenas de bytes), el coeficiente de compresión será claramente menor que 1 (es decir, un aumento en la cantidad de datos en lugar de compresión);
  3. ENJUAGUE después de cada grabación.
    Muchas bibliotecas de compresión tienen soporte para FLUSH. Este es un comando (o parámetro para el procedimiento de compresión), al recibir el cual el archivador genera una secuencia comprimida para que, sobre la base, todos los datos no comprimidos que ya se hayan recibido puedan restaurarse. Tal análogo de sync en sistemas de archivos o commit en sql.
    Lo que es importante, las operaciones de compresión posteriores podrán usar el diccionario acumulado y la relación de compresión no sufrirá tanto como en la versión anterior.

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


Hubo un gran artículo sobre FLUSH en zlib.


Hice una prueba motivada basada en el artículo, tomé 70 mil entradas de diario de un dispositivo real, con un tamaño de página de 60Kb (volveremos al tamaño de la página) :


Datos de origenCompresión Gzip -9 (sin FLUSH)zlib con Z_PARTIAL_FLUSHzlib con Z_SYNC_FLUSH
Volumen, Kb169240352604

A primera vista, el precio introducido por FLUSH es excesivamente alto, pero en realidad tenemos una mala elección, ya sea no comprimir en absoluto o comprimir (y de manera muy eficiente) con FLUSH. No olvide que tenemos 70 mil registros, la redundancia introducida por Z_PARTIAL_FLUSH es de solo 4-5 bytes por registro. Y la relación de compresión resultó ser casi 5: 1, lo cual es más que un excelente resultado.


Puede parecer inesperado, pero en realidad Z_SYNC_FLUSH es una forma más eficiente de hacer FLUSH

En el caso de usar Z_SYNC_FLUSH, los últimos 4 bytes de cada registro siempre serán 0x00, 0x00, 0xff, 0xff. Y si los conocemos, entonces no podemos almacenarlos, por lo que el tamaño total es de solo 324Kb.


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


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

Un bloque de tipo 0 con contenido vacío consta de:
  • el encabezado de 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, en el último bloque antes de estos 4 bytes viene de 3 a 10 bits cero. Sin embargo, la práctica ha demostrado que cero bits son en realidad al menos 10.


Resulta que tales bloques de datos cortos generalmente se codifican (¿siempre?) Usando un bloque de tipo 1 (bloque fijo), que necesariamente termina con 7 bits cero, por lo que obtenemos 10-17 bits cero garantizados (y el resto será cero con una probabilidad de aproximadamente 50%).


Entonces, en los datos de prueba, en el 100% de los casos, antes de 0x00, 0x00, 0xff, 0xff hay un byte cero, y más que en el tercer caso hay dos bytes cero (tal vez el hecho es que uso CBOR binario, y cuando uso texto CBOR Es más probable que JSON cumpla con bloques de tipo 2: bloque dinámico, respectivamente, los bloques se producirían sin bytes cero adicionales antes de 0x00, 0x00, 0xff, 0xff) .


El total de los datos de prueba disponibles puede caber en menos de 250 Kb de datos comprimidos.


Puede ahorrar un poco más haciendo malabares con los bits: ahora ignoramos la presencia de varios bits cero al final del bloque, varios bits al comienzo del bloque tampoco cambian ...
Pero luego tomé una decisión decidida de detenerme, de lo contrario a tal ritmo puede alcanzar el desarrollo de su archivador.


En total, obtuve 3-4 bytes por registro de mis datos de prueba, la relación de compresión fue más de 6: 1. Honestamente, no conté con ese resultado, en mi opinión, todo lo que es mejor que 2: 1 ya es un resultado que justifica el uso de la compresión.


Todo está bien, pero zlib (desinflar) todavía está arcaico Algoritmo de compresión bien merecido y ligeramente anticuado. El mero hecho de que los últimos 32Kb del flujo de datos sin comprimir se usen como diccionario parece extraño hoy (es decir, si algún bloque de datos es muy similar a lo que estaba en el flujo de entrada 40Kb atrás, comenzará a archivarse nuevamente, pero no consulte la entrada anterior). En de moda El diccionario de tamaño de los archivadores modernos a menudo se mide en megabytes en lugar de kilobytes.


Entonces continuamos nuestro mini estudio de archivadores.


Luego se probó bzip2 (recuerdo, sin FLUSH mostró una relación de compresión fantástica, casi 100: 1). Por desgracia, con FLUSH se mostró muy mal, el tamaño de los datos comprimidos fue mayor que el no comprimido.


Mis suposiciones sobre las razones del fracaso

Libbz2 ofrece solo una opción de descarga, que parece borrar el diccionario (similar a Z_FULL_FLUSH en zlib), no hay razón para hablar de algún tipo de compresión efectiva.


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


Por desgracia, con FLUSH demostró ser "no muy": el tamaño de los datos comprimidos fue de aproximadamente 700Kb.


Hice una pregunta en la página del proyecto en github, recibí una respuesta de que vale la pena contar con hasta 10 bytes de datos de servicio para cada bloque de datos comprimidos, que está cerca de los resultados, la captura de desinflado no funciona.


Decidí detener esto en experimentos con archivadores (les recuerdo que xz, lzip, lzo, lz4 no se mostraron incluso en la etapa de prueba sin FLUSH, pero no consideré algoritmos de compresión más exóticos).


Volvemos a los problemas de archivo.


El segundo problema (como se dice en orden, pero no en valor): los datos comprimidos son un flujo único en el que se envían constantemente a secciones anteriores. Por lo tanto, cuando una sección de datos comprimidos está dañada, perdemos no solo el bloque de datos sin comprimir asociado con ellos, sino también todos los subsiguientes.


Hay un enfoque para resolver este problema:


  1. Evite la aparición de un problema: agregue redundancia a los datos comprimidos, lo que permitirá identificar y corregir errores; hablaremos de esto más tarde;
  2. Minimice las consecuencias en caso de un problema.
    Ya dijimos anteriormente que es posible comprimir cada bloque de datos de forma independiente, y el problema desaparecerá por sí solo (la corrupción de datos de un bloque conducirá a la pérdida de datos de solo este bloque). Sin embargo, este es un caso extremo en el que la compresión de datos será ineficiente. El extremo opuesto: use los 4 MB de nuestro microcircuito como un archivo único, lo que nos dará una excelente compresión, pero consecuencias catastróficas en caso de corrupción de datos.
    Sí, se necesita un compromiso en términos de confiabilidad. 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.

En el curso de los experimentos, descubrí que las pérdidas más o menos notables en el nivel de compresión comienzan en bloques de datos comprimidos con un tamaño de menos de 10Kb.
Se mencionó anteriormente que la memoria utilizada tiene una organización de página, no veo ninguna razón por la que no deba usar la correspondencia de "una página: un bloque de datos comprimidos".


Es decir, el tamaño mínimo de página razonable es de 16Kb (con un margen para la información de servicio). Sin embargo, un tamaño de página tan pequeño impone restricciones significativas en el tamaño máximo de grabación.


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


Resumen:


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

Y, antes de terminar con la compresión, me gustaría llamar la atención sobre el hecho de que solo obtenemos unos pocos bytes de datos de escritura, por lo que es extremadamente importante no inflar la información del servicio, cada byte se cuenta.


Almacenar encabezados de datos


Como 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 una secuencia continua, primero viene el encabezado del 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.
    De hecho, obtenemos una lista de enlaces únicos que se usa todo el tiempo;
  2. Los encabezados y registros se almacenan en secuencias separadas.
    Al usar encabezados de longitud constante, nos aseguramos de que el daño a un encabezado no afecte al resto.
    Se utiliza un enfoque similar, por ejemplo, en muchos sistemas de archivos;
  3. Los registros se almacenan en una secuencia continua, el límite del registro está determinado por algún marcador (símbolo / secuencia de caracteres, que está / está prohibido dentro de los bloques de datos). Si se encuentra un marcador dentro del registro, lo reemplazamos con una secuencia determinada (escapar de él).
    Se utiliza un enfoque similar, por ejemplo, en el protocolo PPP.

Voy a ilustrar


Opcion 1:
Opcion 1
Aquí todo es muy simple: conociendo la longitud del registro, podemos calcular la dirección del próximo encabezado. Entonces nos movemos a través de los encabezados hasta encontrar una región llena de 0xff (región libre) o el final de la página.


Opcion 2:
Opción 2
Debido a la longitud variable del registro, no podemos decir de antemano cuántos registros (y, por lo tanto, los encabezados) por página necesitamos. Puede distribuir los encabezados y los datos en páginas diferentes, pero prefiero un enfoque diferente: colocamos los encabezados y los datos en la misma página, sin embargo, los encabezados (de tamaño constante) provienen del principio de la página y los datos (de longitud variable) desde el final. Tan pronto como se "encuentren" (no hay suficiente espacio libre para un nuevo registro), consideramos que esta página está llena.


Opcion 3:
Opción 3
No es necesario almacenar en el encabezado la longitud u otra información sobre la ubicación de los datos, hay suficientes marcadores que indican los límites de los registros. Sin embargo, los datos deben procesarse mientras se escribe / lee.
Como marcador, usaría 0xff (que la página se llena después de borrar), por lo que el área libre definitivamente no se tratará como datos.


Tabla de comparación:


Opcion 1Opción 2Opción 3
Tolerancia a errores-++
Compacidad+-+
Complejidad de implementación* *** **** **

La opción 1 tiene un defecto fatal: si alguno de los encabezados está dañado, se destruye toda nuestra cadena posterior. Otras opciones le permiten recuperar parte de los datos incluso con daños masivos.
Pero aquí es apropiado recordar que decidimos almacenar los datos en forma comprimida, por lo que perdemos todos los datos en la página después del registro "roto", por lo que, aunque hay un signo negativo en la tabla, no lo tenemos en cuenta.


Compacidad:


  • en la primera versión, necesitamos almacenar solo la longitud en el encabezado, si se usan enteros de longitud variable, en la mayoría de los casos podemos hacerlo con un byte;
  • en la segunda opción, necesitamos almacenar la dirección de inicio y la longitud; el registro debe tener un tamaño constante, calculo 4 bytes por registro (dos bytes por desplazamiento y dos bytes por longitud);
  • , - 1-2%. .

( ). , .


, - - . , , — , , ...


: , , .. , , , — , .


: " — " - .



, , :
.
, erase 1, 1 0, . " " 1, " " — 0.


flash:


  1. “ ”;
  2. ;
  3. “ ”;
  4. ;
  5. “ ”.

, “ ”, 4 .


“1111” — “1000” — ; , .


, , , , , ( ) .


: .



( ) , . , , .


, , ( , , — ) .


, , , — .


— CRC. , 100% , — 2n. , , : , . — .


: 1 , 2 ( narod.ru, ) .


, CRC — . , .


, .


:
103, :


,,
10 010000 01000
114 49991003
12≈019971997
14 4≈039903990
100 099550 09955
101399901029
102≈019791979
104 4≈039543954
10000 06323050 0632305
1000124703682838
1000210735745
10004 4≈014691469

, — — .


, : , , . , .


, , 32 ( 64 -) .


, , , - 32- (16 , 0.01%; 24 , , ).


: , 4 ? ? , , .


, CRC-32C.
6 22 (, c), 4 655 ( ), 2 .


CRC.


crc-32c — , CRC .


, , , , .


, , : ?


"" :


  • — ( /, , ..);
  • deflate zlib "" , , , ( , zlib ).

"" :


  • CRC "" , - ( , , , "" );
  • , , .

.


: CRC-32C, , flash ( ).



, , , , ( ) .


, .
, - , RAID-6 .
, , , .


, . ?


  1. ( - , Raspberry, ...)
    , ;
  2. ( - flash- , )
    , ;
  3. ;

  4. .

( ) . , - .


: , , , ( , ).



, ( ) , , .


  • ""
    - , .., , .
    , , ;
  • .
    — !
    Magic Number (), ( , ) ;
  • ( ) , 1 ;
  • .

- . .



Byte order


, , big-endian (network byte order), 0x1234 0x12, 0x34.



- .


32, , 1/4 ( 4 128 ).


( ).


( ), 0 ( 0, — 32, — 64 ..)


(ring buffer), 0, 1, ..., , .




4- , (CRC-32C), ", , ".


( -) :


  • Magic Number ( — )
    0xed00 ⊕ ;
  • " " ( ).

( deflate). ( ), . ( ).


Z_SYNC_FLUSH, 4 0x00, 0x00, 0xff, 0xff, , , .
( 4, 5 6 ) -.


1, 2 3 , :


  • (T), : 0 — , 1 — ;
  • (S) 1 7 , "", ;
  • (L).

S:


S,,
015 ( 00 00 00 ff ff )
1016 ( 00 00 00 00 ff ff )
11024 ( 00 00 ff ff )
111025 ( 00 00 00 ff ff )
1111026 ( 00 00 00 00 ff ff )
111110034 ( 00 00 ff ff )
111110135 ( 00 00 00 ff ff )
111111036 ( 00 00 00 00 ff ff )

, , :

T, — S, L ( ), — , — , -.


, ( 63+5 ) .


CRC-32C, (init) .


CRC "", (- ) : CRC(init,A||B)=CRC(CRC(init,A),B).
CRC .


.


, 0x00 0xff ( 0xff, ; 0x00 ).



-


.
— - .


( , Linux NOR Flash, )


-


.
.


— .



( ) 1.
( UUID ).


, - .



8 ( + CRC), Magic Number CRC .
"" , , .
, CRC, "". — . — , "" .
, , "" .
zlib ( ).


, , , .



, Z_SYNC_FLUSH., .
( CRC) — (. ).
CRC. — .



( ). — , .
erase. 0xff. - — , ..
, , — ( ).



, - ( , JSON, MessagePack, CBOR, , protobuf) NOR Flash.


, "" SLC NOR Flash.


BER, NAND MLC NOR ( ? ) .


, , FTL: USB flash, SD, MicroSD, etc ( 512 , — "" ) .


128 (16) 1 (128). , , , ( , NOR Flash ) .


- , — , , github.


Conclusión


, .


, : - , , . , () - .


, ? Si por supuesto. , , . - .


? , , . .


, , " ".


, () , , "" (, , ; ). ( — ) .


, .



, .


, , , :


  1. infgen zlib. deflate/zlib/gzip. deflate ( gzip) — .

Source: https://habr.com/ru/post/479044/


All Articles