Como eu gero e valido com eficiência somas de verificação de arquivo?

Gostaria de capturar e validar somas de verificação para coleções de arquivos em larga escala, geralmente aninhadas em uma hierarquia de diretórios complexa.

Cada arquivo precisa de uma soma de verificação? Existem maneiras de aproveitar a estrutura de diretórios existente para, por exemplo, validar apenas um nó na árvore de arquivos e não necessariamente todos os arquivos contidos nela?

A maneira mais eficiente de usar somas de verificação é fazer o computador fazer tudo. Use um sistema de arquivos como o ZFS, que somas de verificação (na verdade, usa hashes, que são mais fortes que uma soma de verificação) todos os dados quando gravados e os verifica toda vez que os dados são lidos. Obviamente, a desvantagem é que o ZFS não sabe quando excluir ou substituir um arquivo é um erro e quando é uma operação normal, mas como o ZFS usa a semântica de copiar na gravação para tudo, você pode usar o recurso de captura instantânea para reduzir o risco .

O ZFS também pode restaurar automaticamente os dados que falham na verificação de hash usando qualquer redundância configurada, seja paridade no estilo raid5, espelhos de unidade ou cópias duplicadas (adicione a propriedade copy = N a qualquer sistema de arquivos ZFS e ele armazenará N cópias de qualquer dado que você escreve). Ele também armazena os hashes em uma árvore Merkle, onde o valor de hash de um arquivo depende dos hashes dos blocos, o hash de uma entrada de diretório depende dos valores de hash dos arquivos e diretórios que ele contém, o hash de um sistema de arquivos depende no hash do diretório raiz etc.

Independentemente de qual solução você encontrar, sempre encontrará que o processo é limitado pela velocidade dos seus discos, não pela velocidade da sua CPU.

Além disso, não se esqueça de levar em consideração o BER de seus discos. Afinal, são meros pratos de ferrugem que gira. Uma unidade no nível do consumidor tem uma taxa de erro de 1 bit de leitura incorreta para cada 10 ^ 14 bits lidos, o que resulta em 1 bit a cada 11 terabytes que você lê. Se você tiver um conjunto de dados de 11 terabytes e computar o hash de cada arquivo nele, terá calculado uma dessas somas de verificação incorretamente e danificado permanentemente um bloco de um dos arquivos no conjunto de dados. O ZFS, no entanto, conhece o hash de cada bloco que gravou em todos os discos do seu pool e, portanto, sabe qual bloco foi perdido. Em seguida, ele pode usar a redundância (paridade, espelhos ou cópias extras) em seu pool para reescrever os dados nesse bloco com os valores corretos.

Ben menciona um bom argumento nos comentários. O ZFS não expõe nenhum dos valores de hash que calcula para o usuário; portanto, os dados que entram ou saem de um sistema ZFS devem ser acompanhados por hashes. Gosto da maneira como o Internet Archive faz isso com um arquivo xml que acompanha todos os itens do arquivo. Veja https://ia801605.us.archive.org/13/items/fakebook_the-firehouse-jazz-band-fake-book/fakebook_the-firehouse-jazz-band-fake-book_files.xml como exemplo.

Eu geraria soma de verificação para cada arquivo. As somas de verificação são muito pequenas e a geração de soma de verificação para todo o diretório exigiria que você processasse todos os arquivos também (pelo menos se você não estiver falando sobre soma de verificação de diretório, feita apenas a partir de entradas de diretório - eu as faria também, para garantir que não haja dados) esta deletado).

Suponha que você tenha uma soma de verificação para todo o arquivo morto. Você sabe que os dados estão corrompidos, mas não sabe se esse é apenas um arquivo e, mais importante, qual deles. Ter somas de verificação separadas oferece mais flexibilidade. Você pode detectar um único arquivo que está corrompido e substituí-lo por outro backup (que pode, por sua vez, ter outro arquivo corrompido).

Dessa forma, é mais provável que seus dados sobrevivam.

Talvez seja um bom momento para abrir o BagIt . Esse é um formato de empacotamento de arquivo muito simples, porém poderoso, destinado ao arquivamento, preservação a longo prazo e transferência de objetos digitais. Os usuários incluem a Biblioteca do Congresso e a Biblioteca Digital da Califórnia.

Uma ferramenta BagIt (que existe em várias linguagens de programação) coloca seus arquivos em uma determinada estrutura de diretórios e faz a soma de verificação / hash para você. Isso é tudo.

PS: Obviamente, as ferramentas BagIt também podem verificar malas em relação às somas de verificação / hashes incluídas, e você pode adicionar alguns metadados às malas. Mas isso é tão complexo quanto as malas.

Esta resposta é uma combinação daquela de @ lechlukasz e @ db48x , incorporando também alguns pontos feitos nos comentários, bem como alguns dos meus próprios pensamentos.

O caminho simples a seguir é uma abordagem combinada de sistema de arquivos e metadados separados.

Ao usar um sistema de arquivos que faz hash e validação de dados dinamicamente, como ZFS ou Btrfs (observe que, embora tenham sido feitos grandes avanços, o Btrfs não é considerado pronto para uso de produção no momento), você pode estar razoavelmente Certifique-se de que, se os dados puderem ser lidos no disco sem o erro do sistema operacional, os dados lidos foram gravados no disco da maneira pretendida pelo sistema de arquivos. Ao executar operações periódicas de "limpeza", todos os dados são lidos e verificados com base na idéia do sistema de arquivos de como deveria ser.

No entanto, isso protege apenas contra corrupção no disco (blocos ilegíveis, erros definitivos de gravação de hardware, gravações inválidas que danificam partes dos dados diretamente no dispositivo de bloco etc.). Ele não protege contra um erro de software, operação incorreta do usuário ou software mal-intencionado que funciona através dos recursos pretendidos do sistema operacional para trabalhar com arquivos, supondo que esses recursos estejam livres desses erros.

Para se proteger contra o último, você precisa de outra camada de proteção. A soma de verificação ou o hash de dados na perspectiva de um aplicativo de usuário ajudará a proteger contra muitos dos riscos mencionados acima, mas precisa ser executada separadamente (como uma ação de processo interna no software ou como um processo completamente separado).

Com o hardware de hoje e o que é prático para armazenar grandes quantidades de dados (discos rígidos de prato giratório em oposição a discos de estado sólido / SSDs), até mesmo algoritmos de hash complexos como o SHA1 serão amplamente ligados à E / S - ou seja, a velocidade na qual os dados são hash, será uma função da velocidade de leitura do sistema de armazenamento, e não da capacidade do processador do computador de calcular o hash. Fiz um experimento com a execução de um processo de hash MD5 no espaço do usuário com aproximadamente 150 GB de dados sobre o que em 2012 era um PC de nível intermediário, e ele foi concluído após o exercício do disco basicamente sem interrupção por cerca de 40 minutos. Ao aumentar esses números 100 vezes, você obterá os hashes MD5 de uma coleção de 15 TB em cerca de três dias no mesmo hardware. Adicionando taxa de transferência de leitura (que pode ser facilmente realizada, por exemplo,O RAID 0, por exemplo, é distribuído sem redundância, comumente usado para obter um desempenho mais alto de leitura / gravação, possivelmente em combinação com o RAID 1 que forma o RAID 10 ), o tempo para conclusão pode ser reduzido para a mesma quantidade de dados.

Ao combinar os dois, você obtém o melhor dos dois mundos: o sistema de arquivos garante que o que você recebeu ao ler o arquivo foi o que foi realmente escrito, e que um processo separado de verificação de correção pode ser executado em toda a coleção, garantindo que os dados armazenado ainda corresponde ao que foi ingerido no arquivo morto. Qualquer inconsistência entre os dois (o sistema de arquivos diz que o arquivo está OK, a verificação de correção diz que não) indicará um arquivo que foi modificado fora do modo de operação pretendido do arquivo, mas de dentro das instalações do sistema operacional, solicitando uma restauração de um secundário cópia (backup). Portanto, a verificação da fixidez pode ser executada em um intervalo de tempo mais longo, o que se torna essencial para arquivos muito grandes, mas ainda é garantido que todos os acessos online não sejam corrompidos no hardware se as leituras forem bem-sucedidas. Em princípio, o software de arquivamento pode contar com o sistema de arquivos para relatar inconsistências como erros de leitura e executar uma verificação de correção separada em segundo plano, pois o usuário está trabalhando com o arquivo e exibindo uma mensagem apropriada, indicando que o arquivo não corresponde ao que foi ingerido no arquivo. Usando um sistema de arquivos com hash em bloco, esse esquema teria um impacto mínimo no desempenho percebido, enquanto ainda assegurava que o conteúdo estivesse correto.

Examinei as respostas e, embora goste da idéia de confiar no ZFS para lidar com os erros da camada de dados, ainda há o problema de os arquivos serem alterados, por engano ou maliciosamente. O ZFS não o protegerá nesse caso e, como alguém mencionado, não fornecerá um "hash" visível para o usuário para armazenar em outro lugar para validação externa.

Há um aplicativo Linux chamado TripWire que foi amplamente utilizado para monitorar os executáveis ​​do sistema, para validar que eles não foram alterados após um ataque. Aparentemente, esse projeto agora está abandonado, mas há um novo chamado AIDE (Advanced Intrusion Detection Environment), recomendado no ServerFault:

/server/62539/tripwire-and-alternatives

Quando você instala, ele é executado a cada x minutos, configurável pelo usuário, e verifica todas as pastas especificadas para alterações nos arquivos. Ele precisa ser executado uma vez para calcular todos os hashes do arquivo e, depois disso, verifica todos os hashes em relação ao arquivo atual e garante que eles ainda sejam os mesmos. Você pode especificar qual tipo de hash ou combinação de hashes usar (eu não recomendaria nada mais fraco que o SHA-256), quais atributos de arquivo usar (conteúdo, tamanho, carimbo de data / hora modificado etc.), a frequência com que ele verifica, como / onde armazenar o banco de dados de hash, etc.

Alguns podem considerar esse exagero, mas, dependendo dos requisitos do OP, pode dar-lhe mais tranquilidade que os dados que ele está armazenando permanecerão os mesmos após um certo período de tempo.

O National Archives of Australia desenvolveu o [Checksum Checker] ( http://checksumchecker.sourceforge.net/ ), que está disponível gratuitamente sob a GPLv3.

Ele lê uma soma de verificação e algoritmo de um banco de dados e recalcula a soma de verificação para o arquivo, compara os dois valores e relatórios se houver um erro. Ele suporta os algoritmos MD5, SHA1, SHA2, SHA256 e SHA512.

Outro software em seu repositório digital [DPR] ( http://dpr.sourceforge.net/ ) gera a soma de verificação inicial (além de executar todas as outras atividades de processamento)