Antecedentes

Existem máquinas de venda automática com design próprio. Dentro do Raspberry Pi e um pouco de cintas em uma placa separada. Um aceitador de moedas, um aceitador de contas e um terminal bancário estão conectados ... Um programa auto-escrito gerencia tudo. Todo o histórico do trabalho é gravado na revista em uma unidade flash USB (MicroSD), que é transmitida pela Internet (usando um modem USB) para o servidor, onde é adicionada ao banco de dados. As informações de vendas são carregadas em 1s, também há uma interface web simples para monitoramento etc.

Ou seja, a revista é vital - para contabilidade (receita, vendas, etc.), monitoramento (todos os tipos de falhas e outras circunstâncias de força maior); você pode dizer todas as informações que temos sobre esta máquina.

O problema

As unidades flash se mostram dispositivos muito pouco confiáveis. Eles falham com regularidade invejável. Isso leva ao tempo de inatividade da máquina e (se por algum motivo o diário não puder ser transmitido on-line) à perda de dados.

Esta não é a primeira experiência do uso de pen drives, antes disso havia outro projeto com mais de cem dispositivos em que a revista era armazenada em pen drives USB, havia também problemas de confiabilidade, às vezes o número de falhas por mês era de dezenas. Tentamos diferentes drives flash, incluindo os de marca na memória SLC, e alguns modelos são mais confiáveis ​​que outros, mas a substituição de drives flash não resolveu o problema radicalmente.

Atenção! Longrid! Se você não está interessado em "por que", mas apenas em "como", pode ir imediatamente para o final do artigo.

Solução

A primeira coisa que vem à mente: abandone o MicroSD, coloque, por exemplo, SSD e inicialize a partir dele. É teoricamente possível, provavelmente, mas relativamente caro e não tão confiável (um adaptador USB-SATA é adicionado; nos SSDs de orçamento, as estatísticas de falha também não são felizes).

O HDD USB também não parece uma solução particularmente atraente.

Portanto, chegamos a esta opção: deixe o download do MicroSD, mas use-o no modo somente leitura e armazene o log de operações (e outras informações exclusivas de uma peça de hardware específica - número de série, calibrações do sensor etc.) em outro local.

O tópico FS somente leitura para framboesas já foi estudado ao longo do tempo. Não vou me debruçar sobre os detalhes da implementação neste artigo (mas se houver interesse, talvez eu escreva um mini-artigo sobre esse tópico) . O único ponto que quero ressaltar: pela experiência pessoal e pelas avaliações que já implementaram um ganho em confiabilidade, é. Sim, é impossível se livrar completamente das falhas, mas é bem possível reduzir significativamente sua frequência. Sim, e os cartões se tornam unificados, o que simplifica bastante a substituição da equipe de manutenção.

Hardware

Não havia dúvida sobre a escolha do tipo de memória - NOR Flash.
Argumentos:

• conexão simples (na maioria das vezes o barramento SPI, a experiência de usar que já existe, para que não haja problemas "de ferro" esperados);
• preço ridículo;
• protocolo operacional padrão (a implementação já está no kernel do Linux, se desejar, você pode contratar um terceiro, que também está presente, ou até mesmo escrever o seu, o benefício é simples);
• confiabilidade e recursos:
  de uma folha de dados típica: os dados são armazenados por 20 anos, 100.000 ciclos de apagamento para cada bloco;
  de fontes de terceiros: BER extremamente baixo, postula-se que não há necessidade de códigos de correção de erros (em alguns documentos, o ECC para NOR é considerado, mas geralmente MLC NOR é usado para isso, acontece) .

Vamos estimar os requisitos de volume e recurso.

Quero ter a garantia de salvar dados por vários dias. Isso é necessário para que, em caso de problemas com a conexão, o histórico de vendas não seja perdido. Vamos nos concentrar em 5 dias, durante esse período (mesmo levando em consideração fins de semana e feriados), podemos resolver o problema.

Agora estamos digitando cerca de 100kb de revista por dia (3-4 mil registros), mas gradualmente esse número está crescendo - os detalhes estão aumentando, novos eventos estão sendo adicionados. Além disso, às vezes há explosões (alguns sensores começam a enviar spam com falsos positivos, por exemplo). Vamos calcular 10 mil registros de 100 bytes - megabytes por dia.

Um total de 5 MB de dados limpos (bem compactáveis) sai. Eles também (estimativa aproximada) 1 MB de dados de serviço.

Ou seja, precisamos de um microchip de 8 MB se você não usar compactação ou 4 MB se você o usar. Números reais para esse tipo de memória.

Quanto ao recurso: se planejarmos que toda a memória seja reescrita não mais que uma vez a cada 5 dias, em 10 anos de serviço obteremos menos de mil ciclos de reescrita.
Lembro-me, o fabricante promete cem mil.

Se os detalhes forem interessantes, o chip at25df321a foi escolhido (no entanto, isso é insignificante, existem muitos análogos no mercado que são compatíveis com a pinagem e o sistema de comando; mesmo que desejemos colocar o chip de outro fabricante e / ou outro volume, tudo funcionará sem alterar o código) .

Eu uso o driver embutido no kernel do Linux, no Raspberry, graças ao suporte à sobreposição de árvore de dispositivos, tudo é muito simples - você precisa colocar a sobreposição compilada em / boot / overlays e modificar um pouco o /boot/config.txt.

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

 dtoverlay=at25:spimaxfrequency=50000000 

Omitirei a descrição de conectar o chip ao Raspberry Pi. Por um lado, não sou especialista em eletrônica, por outro lado, tudo é trivial até para mim: o microcircuito possui apenas 8 pernas, das quais precisamos de terra, energia, SPI (CS, SI, SO, SCK); os níveis coincidem com os do Raspberry Pi, nenhuma ligação adicional é necessária - basta conectar os 6 contatos especificados.

Declaração do problema

Como sempre, a formulação do problema passa por várias iterações, parece-me que chegou a hora da próxima. Então vamos parar, montar o que já foi escrito e esclarecer os detalhes restantes nas sombras.

Portanto, decidimos que o log será armazenado no SPI NOR Flash.

O próprio diário representa uma sequência de registros de tamanho variável. Um comprimento de gravação típico é de cerca de 30 bytes (embora algumas vezes ocorram gravações de vários kilobytes). Nesse caso, trabalhamos com eles como um conjunto de bytes, mas, se você estiver interessado, o CBOR é usado dentro dos registros.

Além do diário, precisamos armazenar algumas informações de "ajuste", atualizadas ou não: um determinado ID do dispositivo, calibração do sensor, o sinalizador "o dispositivo está temporariamente desativado", etc.
Essas informações são um conjunto de registros de valores-chave, também armazenados no CBOR. Não temos muitas informações (no máximo alguns kilobytes), elas são atualizadas com pouca frequência.
No futuro, chamaremos de contexto.

Se você se lembrar de onde este artigo começou, é muito importante garantir a confiabilidade do armazenamento de dados e, se possível, operação contínua, mesmo no caso de falhas de hardware / corrupção de dados.

Quais fontes de problemas podem ser consideradas?

• Desligue durante as operações de gravação / exclusão. Isto é da categoria de "contra sucata sem recepção".
  Informações da discussão sobre stackexchange: quando a energia é desligada durante o trabalho com flash, a exclusão (configuração 1), a gravação (configuração 0) levam a um comportamento indefinido: os dados podem ser gravados, parcialmente gravados (por exemplo, transferimos 10 bytes / 80 bits) e apenas 45 bits conseguiram ser gravados), também é possível que alguns bits estejam no estado "intermediário" (a leitura pode produzir 0 ou 1);
• Erros da própria memória flash.
  BER, embora muito baixo, não pode ser igual a zero;
• Erros de barramento
  Os dados transmitidos via SPI não são protegidos de forma alguma, podem ocorrer como erros de bit único ou erros de sincronização - perda ou inserção de bits (o que leva a uma distorção maciça de dados);
• Outros erros / falhas
  Erros no código, "falhas" de framboesa, intervenção alienígena ...

Formulei requisitos, cujo cumprimento, na minha opinião, é necessário para garantir a confiabilidade:

• Os registros devem ser gravados na memória flash imediatamente, a gravação pendente não é considerada; - se ocorrer um erro, ele deve ser detectado e processado o mais rápido possível; - o sistema deve, se possível, recuperar-se de erros.
  (um exemplo da vida "como não deveria ser", que acho que todos conheceram: após uma reinicialização de emergência, o sistema de arquivos "quebrou" e o sistema operacional não inicializa)

Ideias, Abordagens, Pensamentos

Quando comecei a pensar nessa tarefa, várias idéias passaram pela minha cabeça, por exemplo:

• Usar compactação de dados
• Use estruturas de dados complicadas, por exemplo, armazene cabeçalhos de registros separadamente dos próprios registros, para que, se ocorrer um erro em um registro, você possa ler o restante sem problemas
• use campos de bits para controlar a integridade da gravação quando a energia for desligada;
• armazenar somas de verificação para tudo e tudo;
• use algum tipo de codificação de correção de erros.

Algumas dessas idéias foram usadas, outras foram decididas recusar. Vamos em ordem.

Compressão de dados

Os eventos que gravamos no diário são iguais e repetíveis ("jogou uma moeda de 5 rublos", "clicou no botão de entrega de trocas", ...). Portanto, a compactação deve ser bastante eficaz.

A sobrecarga para compactação é insignificante (o processador que temos é bastante poderoso, mesmo no primeiro Pi havia um núcleo com frequência de 700 MHz, nos modelos atuais havia vários núcleos com frequência superior a um gigahertz), a velocidade de troca com o armazenamento é baixa (vários megabytes por segundo), o tamanho do registro é pequeno. Em geral, se a compactação afetará o desempenho, apenas positivo (absolutamente não crítico, apenas afirmando) . Além disso, não temos um Linux realmente incorporado, mas comum - portanto a implementação não deve exigir muito esforço (basta vincular a biblioteca e usar várias funções).

Uma parte do log foi retirada do dispositivo de trabalho (1,7 MB, 70 mil registros) e, para começar, foi verificada a compressibilidade usando os gzip, lz4, lzop, bzip2, xz, zstd disponíveis no computador.

• gzip, xz, zstd apresentaram resultados semelhantes (40Kb).
  Fiquei surpreso que o xz da moda se mostrasse aqui no nível gzip ou zstd;
• O lzip com configurações padrão deu um resultado um pouco pior;
• lz4 e lzop não apresentaram resultados muito bons (150Kb);
• O bzip2 mostrou resultados surpreendentemente bons (18Kb).

Portanto, os dados são compactados muito bem.
Então (se não encontrarmos falhas fatais), deve haver compressão! Só porque mais dados caberão na mesma unidade flash.

Vamos pensar nas falhas.

O primeiro problema: já concordamos que cada registro deve aparecer imediatamente. Normalmente, o arquivador coleta dados do fluxo de entrada até decidir que é hora de gravar na saída. Precisamos obter imediatamente um bloco de dados compactados e salvá-lo na memória não volátil.

Eu vejo três maneiras:

1. Compacte cada entrada usando a compactação de dicionário em vez dos algoritmos discutidos acima.
   É uma opção de trabalho, mas eu não gosto. Para garantir um nível de compactação mais ou menos decente, o dicionário deve ser "aprimorado" para dados específicos, qualquer alteração levará ao fato de que o nível de compactação cai catastroficamente. Sim, o problema é resolvido com a criação de uma nova versão do dicionário, mas isso é uma dor de cabeça - precisaremos armazenar todas as versões do dicionário; em cada entrada, precisaremos indicar com qual versão do dicionário ele foi compactado ...
2. Comprima cada entrada com algoritmos "clássicos", mas independentemente dos outros.
   Os algoritmos de compactação em questão não foram projetados para trabalhar com registros desse tamanho (dezenas de bytes); o coeficiente de compactação será claramente menor que 1 (ou seja, um aumento na quantidade de dados em vez da compactação);
3. FLUSH após cada gravação.
   Muitas bibliotecas de compactação têm suporte para FLUSH. Este é um comando (ou parâmetro do procedimento de compactação), após o recebimento do arquivador, que gera um fluxo compactado para que, com base em todos os dados não compactados já recebidos, possam ser restaurados. Um análogo de sync em sistemas de arquivos ou commit em sql.
   O que é importante, as operações de compactação subsequentes poderão usar o dicionário acumulado e a taxa de compactação não sofrerá tanto quanto na versão anterior.

Eu acho que é óbvio que escolhi a terceira opção, vamos falar mais detalhadamente.

Houve um ótimo artigo sobre o FLUSH no zlib.

Fiz um teste motivado com base no artigo, peguei 70 mil entradas de diário de um dispositivo real, com um tamanho de página de 60Kb (retornaremos ao tamanho da página) :

À primeira vista, o preço introduzido pelo FLUSH é excessivamente alto, mas, na realidade, temos uma má escolha - não comprimir nada, nem comprimir (e com muita eficiência) o FLUSH. Não esqueça que temos 70 mil registros, a redundância introduzida por Z_PARTIAL_FLUSH é de apenas 4-5 bytes por registro. E a taxa de compressão acabou por ser quase 5: 1, o que é mais do que um excelente resultado.

No total, obtive de 3 a 4 bytes por registro dos meus dados de teste, a taxa de compactação era superior a 6: 1. Honestamente, eu não contei com esse resultado, na minha opinião tudo o que é melhor que 2: 1 já é um resultado que justifica o uso da compactação.

Está tudo bem, mas o zlib (deflate) ainda está arcaico algoritmo de compressão bem merecido e levemente antiquado. O mero fato de que os últimos 32 KB do fluxo de dados não compactados sejam usados ​​como um dicionário parece hoje estranho (ou seja, se algum bloco de dados for muito semelhante ao que estava no fluxo de entrada de 40 KB novamente, ele começará a ser arquivado novamente, mas não será consulte a entrada anterior). Em elegante o dicionário de tamanho dos arquivadores modernos é geralmente medido em megabytes em vez de kilobytes.

Então, continuamos nosso mini-estudo de arquivadores.

Em seguida, o bzip2 foi testado (lembre-se, sem FLUSH, ele mostrou uma taxa de compressão fantástica, quase 100: 1). Infelizmente, com o FLUSH mostrou-se muito pouco, o tamanho dos dados compactados foi maior que o dos não compactados.

E o zstd foi o último a ser testado. Dependendo dos parâmetros, ele é compactado no nível gzip, mas muito mais rápido, ou gzip é melhor.

Infelizmente, com o FLUSH, ele provou ser "não muito": o tamanho dos dados compactados ficou em torno de 700Kb.

Fiz uma pergunta na página do projeto no github, recebi uma resposta que vale a pena contar com até 10 bytes de dados de serviço para cada bloco de dados compactados, que é próximo aos resultados, capturar deflate não funciona.

Decidi parar com isso em experimentos com arquivadores (lembro que xz, lzip, lzo, lz4 não apareceram no estágio de teste sem o FLUSH, mas não considerei algoritmos de compressão mais exóticos).

Voltamos aos problemas de arquivamento.

O segundo problema (como eles dizem em ordem, mas não em valor) - os dados compactados são um único fluxo no qual há constantemente o envio para as seções anteriores. Assim, quando uma seção de dados compactados é danificada, perdemos não apenas o bloco de dados não compactados associado a ela, mas também todos os subsequentes.

Existe uma abordagem para resolver esse problema:

1. Evitar a ocorrência de um problema - adicione redundância aos dados compactados, o que permitirá identificar e corrigir erros; falaremos sobre isso mais tarde;
2. Minimize as consequências em caso de problema
   Já dissemos anteriormente que é possível compactar cada bloco de dados de forma independente, e o problema desaparecerá por si só (a corrupção de dados de um bloco levará à perda de dados apenas desse bloco). No entanto, este é um caso extremo em que a compactação de dados será ineficiente. O extremo oposto: use todos os 4 MB do nosso microcircuito como um único arquivo, o que nos dará uma excelente compressão, mas consequências catastróficas em caso de corrupção de dados.
   Sim, é necessário um compromisso em termos de confiabilidade. Mas devemos lembrar que estamos desenvolvendo um formato de armazenamento de dados para memória não volátil com um BER extremamente baixo e um período de armazenamento de dados declarado de 20 anos.

No decorrer das experiências, descobri que as perdas mais ou menos perceptíveis no nível de compactação começam em blocos de dados compactados com um tamanho inferior a 10 KB.
Foi mencionado anteriormente que a memória usada possui uma organização da página; não vejo razão para que você não deva usar a correspondência “uma página - um bloco de dados compactados”.

Ou seja, o tamanho mínimo de página razoável é 16 KB (com uma margem para informações de serviço). No entanto, um tamanho de página tão pequeno impõe restrições significativas ao tamanho máximo de gravação.

Embora eu ainda não espere registros de mais unidades de kilobytes na forma compactada, decidi usar 32 KB de páginas (um total de 128 páginas por chip).

Resumo:

• Armazenamos dados compactados usando zlib (deflate);
• Para cada registro, defina Z_SYNC_FLUSH;
• Para cada registro compactado, recortamos os bytes finais (por exemplo, 0x00, 0x00, 0xff, 0xff) ; no cabeçalho, indique quantos bytes cortamos;
• Armazenamos dados em páginas de 32Kb; dentro da página, há um único fluxo de dados compactados; em cada página, começamos a compactação novamente.

E, antes de terminar a compactação, gostaria de chamar a atenção para o fato de termos apenas alguns bytes de dados de gravação, por isso é extremamente importante não aumentar as informações de serviço, pois cada byte é contado.

Armazenando cabeçalhos de dados

Como temos registros de comprimento variável, precisamos determinar de alguma forma a localização / limites dos registros.

Conheço três abordagens:

1. Todos os registros são armazenados em um fluxo contínuo, primeiro vem o cabeçalho do registro que contém o comprimento e depois o próprio registro.
   Nesta modalidade, os cabeçalhos e os dados podem ter um comprimento variável.
   De fato, obtemos uma lista vinculada única que é usada o tempo todo;
2. Os próprios cabeçalhos e registros são armazenados em fluxos separados.
   Usando cabeçalhos de comprimento constante, garantimos que os danos a um cabeçalho não afetem o restante.
   Uma abordagem semelhante é usada, por exemplo, em muitos sistemas de arquivos;
3. Os registros são armazenados em um fluxo contínuo, o limite do registro é determinado por algum marcador (símbolo / sequência de caracteres, que é / que é proibido dentro de blocos de dados). Se um marcador for encontrado dentro do registro, então o substituiremos por uma determinada sequência (escape).
   Uma abordagem semelhante é usada, por exemplo, no protocolo PPP.

Vou ilustrar.

Opção 1:

Tudo é muito simples aqui: sabendo o tamanho do registro, podemos calcular o endereço do próximo cabeçalho. Então, movemos os cabeçalhos até encontrarmos uma região preenchida com 0xff (região livre) ou no final da página.

Opção 2:

Devido ao tamanho variável do registro, não podemos dizer antecipadamente quantos registros (e, portanto, os cabeçalhos) por página que precisamos. Você pode espalhar os cabeçalhos e os dados em páginas diferentes, mas eu prefiro uma abordagem diferente: colocamos os cabeçalhos e os dados na mesma página, no entanto, os cabeçalhos (de tamanho constante) vêm do início da página e os dados (de tamanho variável) do final. Assim que eles "se encontram" (não há espaço livre suficiente para um novo registro) - consideramos que esta página está cheia.

Opção 3:

Não há necessidade de armazenar no cabeçalho o comprimento ou outras informações sobre a localização dos dados, existem marcadores suficientes que indicam os limites dos registros. No entanto, os dados devem ser processados ​​durante a gravação / leitura.
Como marcador, eu usaria 0xff (que a página é preenchida após a exclusão), para que a área livre definitivamente não seja tratada como dados.

Tabela de comparação:

A opção 1 tem uma falha fatal: se algum cabeçalho estiver danificado, toda a cadeia subsequente será destruída. Outras opções permitem recuperar parte dos dados, mesmo com grandes danos.
Mas aqui é apropriado lembrar que decidimos armazenar os dados em um formato compactado e, portanto, perdemos todos os dados na página após o registro "quebrado", portanto, mesmo que haja um sinal de menos na tabela, não levamos em conta.

Compacidade:

• na primeira versão, precisamos armazenar apenas o comprimento no cabeçalho, se números inteiros de comprimento variável forem usados, na maioria dos casos, podemos fazer com um byte;
• na segunda opção, precisamos armazenar o endereço inicial e o comprimento; o registro deve ter um tamanho constante, eu estimo 4 bytes por registro (dois bytes por deslocamento e dois bytes por comprimento);
• , - 1-2%. .

( ). , .

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

: , , .. , , , — , .

: " — " - .

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

flash:

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

, “ ”, 4 .

“1111” — “1000” — ; , .

, , , , , ( ) .

: .

( ) , . , , .

, , ( , , — ) .

, , , — .

— CRC. , 100% , — $$$2^{-n}$. , , : , . — .

: 1 , 2 ( narod.ru, ) .

, CRC — . , .

, .

:
$$$10^{-3}$, :

, — — .

, : , , . , .

, , 32 ( 64 -) .

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

: , 4 ? ? , , .

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

, , : ?

"" :

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

"" :

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

.

: CRC-32C, , flash ( ).

, , , , ( ) .

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

, . ?

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

( ) . , - .

: , , , ( , ).

Outros

, ( ) , , .

• ""
  - , .., , .
  , , ;
• .
  — !
  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:

, , :

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.

Conclusão

, .

, : - , , . , () - .

, ? Sim claro. , , . - .

? , , . .

, , " ".

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

, .

Literatura

, .

, , , :

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