Wie generiere und validiere ich Dateiprüfsummen effizient?

2683
Aaron Rubinstein

Ich möchte in der Lage sein, Prüfsummen für umfangreiche Sammlungen von Dateien zu erfassen und zu überprüfen, die normalerweise in einer komplexen Verzeichnishierarchie verschachtelt sind.

Benötigt jede einzelne Datei eine Prüfsumme? Gibt es Möglichkeiten, die vorhandene Verzeichnisstruktur zu nutzen, um beispielsweise nur einen Knoten im Dateibaum zu überprüfen und nicht notwendigerweise jede Datei darin?

12
In den Antworten ist zu beachten, dass es wichtig ist, die Bedrohungstypen und die Prüfsumme entsprechend zu unterscheiden. [Eine frühere Antwort zum Stack-Überlauf in Bibliotheks- und Informationswissenschaften] (http://libraries.stackexchange.com/a/615/438), die ich beigesteuert habe, könnte von Interesse sein, obwohl es meistens um HDFS geht. Andy Jackson vor 11 Jahren 0

6 Antworten auf die Frage

13
db48x

Die effizienteste Methode zur Verwendung von Prüfsummen besteht darin, den Computer dazu zu bringen, alles zu erledigen. Verwenden Sie ein Dateisystem wie ZFS, das Prüfsummen verwendet (tatsächlich verwendet sie Hashes, die stärker als eine Prüfsumme sind), wenn alle Daten geschrieben werden, und überprüft sie bei jedem Lesen der Daten. Der Nachteil ist natürlich, dass ZFS nicht weiß, wann eine Datei gelöscht oder überschrieben wird. Dies ist ein Fehler und der normale Betrieb. Da ZFS jedoch Semantik für das Kopieren beim Schreiben verwendet, können Sie die Snapshotting-Funktion verwenden, um das Risiko zu minimieren .

ZFS kann auch Daten, für die eine Hash-Prüfung nicht erfolgreich ist, mithilfe der von Ihnen eingerichteten Redundanz automatisch wiederherstellen. Dabei kann es sich um eine Parität im Raid5-Stil, um Laufwerkspiegelungen oder um doppelte Kopien handeln (fügen Sie die Kopien = N-Eigenschaft in ein ZFS-Dateisystem ein und es werden N Kopien gespeichert von allen Daten, die Sie schreiben). Es speichert auch die Hashes in einem Merkle-Baum, wobei der Hashwert einer Datei von den Hashwerten der Blöcke abhängt, der Hash eines Verzeichniseintrags von den Hashwerten der darin enthaltenen Dateien und Verzeichnisse abhängt und vom Hash eines Dateisystems abhängt auf dem Hash des Wurzelverzeichnisses usw.

Unabhängig davon, mit welcher Lösung Sie am Ende arbeiten, Sie werden immer feststellen, dass der Prozess durch die Geschwindigkeit Ihrer Festplatten und nicht durch die Geschwindigkeit Ihrer CPU begrenzt ist.

Vergessen Sie auch nicht, die BER Ihrer Festplatten zu berücksichtigen. Es sind doch nur Teller mit Spinnrost. Ein Laufwerk auf Consumer-Ebene hat eine Fehlerrate von 1 falsch gelesenen Bit für alle 10 ^ 14-Bit-Lesevorgänge, was sich auf 1 Bit von jeweils 11 Terabyte auswirkt, die Sie lesen. Wenn Sie über einen Datensatz von 11 Terabyte verfügen und den Hashwert jeder Datei darin berechnen, haben Sie eine dieser Prüfsummen falsch berechnet und einen Block einer der Dateien im Datensatz dauerhaft beschädigt. ZFS kennt jedoch den Hashwert jedes Blocks, den er auf jede Festplatte in Ihrem Pool geschrieben hat, und weiß daher, welcher Block verloren ging. Es kann dann die Redundanz (Parität, Spiegelungen oder zusätzliche Kopien) in Ihrem Pool verwenden, um die Daten in diesem Block mit den korrekten Werten neu zu schreiben.

Ben bringt jedoch einen guten Punkt in den Kommentaren auf. ZFS macht keinen der Hashwerte, die es berechnet, für den Benutzer verfügbar, daher sollten Daten, die in ein ZFS-System ein- oder ausgehen, von Hashes begleitet werden. Ich mag die Art und Weise, wie das Internet-Archiv dies mit einer XML-Datei tut, die jedes Element im Archiv enthält. Siehe https://ia801605.us.archive.org/13/items/fakebook_the-firehouse-jazz-band-fake-book/fakebook_the-firehouse-jazz-band-fake-book_files.xml .

Du warst schneller als ich. Ich wollte auch ein Hash-basiertes System vorschlagen. Hash jede Datei, Hash der Datei-Hashes (+ Unterverzeichnishashes) für einen Verzeichnis-Hash usw. Der Kompromiss ist CPU / IO vs. Fehlerwahrscheinlichkeit. Checksum / CRC ist billig, aber die Fehlerwahrscheinlichkeit steigt mit der Skala. Dies gilt auch für häufige Hashes, die jedoch mit einer wesentlich geringeren Fehlerwahrscheinlichkeit beginnen. The Diamond Z vor 11 Jahren 1
Selbst wenn Sie ein Dateisystem wie ZFS betreiben (Btrfs verfügt auch über ähnliche Funktionen, ist aber noch in der Entwicklung und wird derzeit noch nicht als betriebsbereit betrachtet). Sie müssen jedoch eine periodische "Scrub" -Operation durchführen, um sicherzustellen, dass die Daten vorhanden sind gelesen und gegen die Prüfsummen oder Hashes geprüft. Sie müssen lediglich Prüfsummen berechnen und dann nichts mit ihnen tun, bis der Zugriff auf die Daten erforderlich ist. Dies ist möglicherweise schlechter als wertlos. a CVn vor 11 Jahren 3
Das Durchlaufen eines Userspace md5sum über etwa 150 GB an Daten auf meinem Heim-PC dauerte etwa 40 Minuten Wandzeit (rein I / O-gebunden). Bei einer 100-fachen Skalierung erhalten wir eine Überprüfung von 15 TB über einen Farbton von weniger als drei Tagen, * auf Consumer-Hardware. * Ich würde dies sicherlich auch für ein großes Archiv als machbar betrachten, mit einem richtig ausgewählten Intervall. a CVn vor 11 Jahren 1
@ BenFino-Radin ZFS hat den Vorteil, dass eine Datei, die im Speicher beschädigt ist, nicht aus dem Dateisystem gelesen werden kann. Außerdem werden Fehler protokolliert. Wenn Sie also die Datei regelmäßig prüfen und die Systemprotokolle regelmäßig überprüfen, können Sie sicher sein, dass sich die Datei außerhalb der vorgesehenen Verwendungsart des Dateisystems nicht geändert hat. ** Natürlich ** schützt das nicht vor böswilliger oder fehlerhafter Software, die den Dateiinhalt durch die vorgesehenen Einrichtungen des Systems beschädigt. * Für das * benötigen Sie eine Art Prüfsumme oder Hashing. Ich würde argumentieren, dass die beiden zusammengehören. a CVn vor 11 Jahren 1
Ja das ist ein guter Punkt. In meinem letzten Scrub wurden 2 Kilobyte Daten repariert, die schlecht gegangen waren. Das sind vier Blöcke, verteilt auf fünf Laufwerke! Je länger Sie zwischen den Lesevorgängen für ein bestimmtes Datenelement wechseln, desto höher ist die Wahrscheinlichkeit, dass Sie in einer einzigen Datei genügend Fehler sammeln, die nicht wiederhergestellt werden können. vor 11 Jahren 1
Richtig, das ist ein toller Punkt bei MichaelKjörling. Ich habe nicht wirklich viel darüber gesagt, wie ich Effizienz definiere. Dies kann sicherlich untragbar werden, wenn Sie Dateien häufig validieren möchten, z. B. mehrmals pro Woche, wenn Sie sich über die 10-TB-Skala bewegen. vor 11 Jahren 0
Ich bin mit @ BenFino-Radin hier bezüglich ZFS. Es ist sicherlich praktisch, und ich kann sehen, dass es in Verbindung mit tragbareren Aufbewahrungslösungen nützlich ist, aber allein davon würde man zu einem Dateisystem führen, und das macht mich definitiv unbequem. vor 11 Jahren 0
ZFS berechnet Prüfsummen für Blöcke, keine Dateien oder Bitströme, oder? Während ZFS das Berechnungsproblem löst, scheint es, dass es weniger für den Benutzer überprüfbar ist und keine Fixitätsdaten erzeugt, die unabhängig vom Dateisystem tragbar sind. Dies ist ein Muss für Archive. vor 11 Jahren 3
6
Danubian Sailor

Ich würde für jede Datei eine Prüfsumme generieren. Prüfsummen sind sehr klein, und wenn Sie eine Prüfsumme für das gesamte Verzeichnis generieren, müssen Sie auch jede Datei verarbeiten (zumindest, wenn Sie nicht über Verzeichnisprüfsummen sprechen, die nur aus Verzeichniseinträgen bestehen. Ich würde sie auch machen, um sicherzustellen, dass keine Daten vorliegen ist gelöscht).

Angenommen, Sie haben eine Prüfsumme für das gesamte Archiv. Sie wissen, dass die Daten beschädigt sind, aber Sie wissen nicht, ob es sich nur um eine Datei handelt, und was noch wichtiger ist. Mit separaten Prüfsummen erhalten Sie mehr Flexibilität. Sie können eine einzelne Datei erkennen, die beschädigt ist, und sie aus der Datei aus einer anderen Sicherung ersetzen (die wiederum andere Dateien beschädigt haben kann).

Auf diese Weise überleben Ihre Daten eher.

Das macht durchaus Sinn. Ich frage mich nur, welche Strategien es gibt, um die rechenintensive Aufgabe zu lösen, Hunderttausende Prüfsummen zu erzeugen und zu prüfen. vor 11 Jahren 0
4
Christian Pietsch

Maybe this is a good time to bring up BagIt. This is a very simple yet powerful file packaging format intended for archiving, long term preservation, and transfer of digital objects. Users include the Library of Congress and the California Digital Library.

A BagIt tool (they exist in several programming languages) puts your files into a certain directory structure and does the checksumming/hashing for you. That is all.

PS: Of course, BagIt tools can also verify bags against the included checksums/hashes, and you can add some metadata to bags. But that's as complex as bags get.

1
a CVn

Diese Antwort ist eine Kombination aus der von @ lechlukasz und @ db48x, die auch einige Punkte in Kommentaren sowie einige meiner eigenen Gedanken enthält.

Der einfache Weg nach vorne besteht aus einem kombinierten Dateisystem- und separaten Metadaten-Ansatz.

Durch die Verwendung eines Dateisystems, das Daten-Hashing und -Validierung im laufenden Betrieb durchführt, wie ZFS oder Btrfs (beachten Sie, dass Btrfs zwar große Fortschritte gemacht hat, derzeit jedoch noch nicht als produktionsbereit erachtet wird), können Sie vernünftig sein Wenn Sie sicher sind, dass die Daten von der Festplatte gelesen werden können, ohne dass das Betriebssystem fehlerhaft ist, wurden die gelesenen Daten in der vom Dateisystem vorgesehenen Weise auf die Festplatte geschrieben. Durch das Ausführen von periodischen "Scrub" -Vorgängen werden alle Daten gelesen und anhand der Vorstellung des Dateisystems überprüft, wie sie aussehen sollen.

Dies schützt jedoch nur vor Beschädigungen auf der Festplatte (unlesbare Blöcke, direkte Hardwareschreibfehler, ungültige Schreibvorgänge, die Teile der Daten direkt auf dem Blockgerät beschädigen usw.). Sie schützt nicht vor Softwarefehlern, fehlerhafter Benutzerbedienung oder böswilliger Software, die über die vorgesehenen Betriebssystemeinrichtungen für die Arbeit mit Dateien arbeitet, sofern diese Einrichtungen keine Fehler enthalten.

Zum Schutz vor letzteren benötigen Sie eine weitere Schutzschicht. Das Prüfen oder Sammeln von Daten aus der Sicht einer Benutzeranwendung trägt zum Schutz vor vielen der oben genannten Risiken bei, muss jedoch separat durchgeführt werden (entweder als integrierte Prozessaktion in der Software oder als vollständig separater Prozess).

Mit der heutigen Hardware und dem praktischen Speicher für große Datenmengen (Spinning Platter-Festplatten im Gegensatz zu Solid-State-Festplatten / SSDs) sind selbst komplexe Hash-Algorithmen wie SHA1 weitgehend I / O-gebunden - das heißt die Geschwindigkeit bei dem die Daten gehasht werden, hängt von der Lesegeschwindigkeit des Speichersystems ab und nicht von der Fähigkeit des Computers, den Hash zu berechnen. Ich habe ein Experiment mit dem Ausführen eines MD5-Hashing-Prozesses für den Benutzerraum über ungefähr 150 GB an Daten durchgeführt, der sich auf einen Mid-Tier-Consumer-PC im Jahr 2012 bezieht. Er wurde beendet, nachdem die Festplatte im Wesentlichen ohne Unterbrechung für ungefähr 40 Minuten trainiert wurde. Wenn Sie diese Zahlen um das 100-Fache steigern, erhalten Sie in etwa drei Tagen die MD5-Hashwerte einer 15-TB-Sammlung auf derselben Hardware. Durch Hinzufügen von Lesetransferrate (die leicht erreicht werden kann, zBei RAID 0 handelt es sich beispielsweise um Striping ohne Redundanz, das üblicherweise zur Erzielung einer höheren Lese- / Schreibleistung verwendet wird, möglicherweise in Kombination mit RAID 1, das RAID 10 bildet. Die Zeit bis zum Abschluss kann für die gleiche Datenmenge gesenkt werden.

Durch die Kombination der beiden Optionen erhalten Sie das Beste aus beiden Welten: Das Dateisystem gibt Ihnen die Sicherheit, dass Sie beim Lesen der Datei das tatsächlich Geschriebene erhalten haben, und ein separater Fixitätsprüfungsprozess kann über die gesamte Sammlung ausgeführt werden, um sicherzustellen, dass die Daten sichergestellt sind gespeichert noch entspricht, was in das Archiv aufgenommen wurde. Jede Inkonsistenz zwischen den beiden Dateien (das Dateisystem gibt an, dass die Datei in Ordnung ist, die Überprüfung der Richtigkeit gibt an, dass dies nicht der Fall ist) weist auf eine Datei hin, die außerhalb des vorgesehenen Betriebsmodus des Archivs, jedoch innerhalb der Betriebssystemfunktionen des Betriebssystems geändert wurde, und fordert eine Wiederherstellung von einem sekundären Server an kopieren (sichern). Die Fixitätsprüfung kann daher in einem längeren Zeitintervall ausgeführt werden, was für sehr große Archive unabdingbar ist. Trotzdem können Online-Zugriffe nach wie vor garantiert nicht von der Hardware beschädigt werden, wenn das Lesen erfolgreich ist. Allgemein gesagt, Die Archivierungssoftware kann sich darauf verlassen, dass das Dateisystem Inkonsistenzen als Lesefehler meldet und im Hintergrund eine separate Überprüfung der Fixität durchführt, während der Benutzer mit der Datei arbeitet und eine entsprechende Meldung anzeigt, wenn die Datei nicht mit der Aufnahme übereinstimmt in das Archiv. Bei Verwendung eines Block-Hash-Dateisystems hat ein solches Schema einen minimalen Einfluss auf die wahrgenommene Leistung und bietet gleichzeitig die Gewähr, dass der Inhalt korrekt ist.

1
mjuarez

Ich bin die Antworten durchgegangen, und obwohl ich die Idee mag, ZFS zur Behandlung der Datenschichtfehler zu verwenden, gibt es immer noch das Problem, dass die Dateien aus Versehen oder in böswilliger Absicht geändert werden. ZFS schützt Sie in diesem Fall nicht, und wie andere Personen auch, wird es Ihnen keinen für den Benutzer sichtbaren "Hash" geben, den Sie für eine externe Validierung an einem anderen Ort speichern können.

Es gibt eine Linux-Anwendung namens TripWire, die ausgiebig zur Überwachung von Systemdateien verwendet wurde, um zu überprüfen, ob sie nach einem Angriff nicht geändert wurden. Dieses Projekt wird anscheinend jetzt aufgegeben, aber es gibt ein neues AIDE (Advanced Intrusion Detection Environment), das auf ServerFault empfohlen wird:

https://serverfault.com/questions/62539/tripwire-and-alternatives

Bei der Installation wird es alle x Minuten ausgeführt, kann vom Benutzer konfiguriert werden, und es werden alle von Ihnen angegebenen Ordner auf Änderungen in den Dateien geprüft. Es muss einmal ausgeführt werden, um alle Dateihashes zu berechnen. Anschließend werden alle Hashes mit der aktuellen Datei verglichen und sichergestellt, dass sie immer noch gleich sind. Sie können angeben, welcher Hashtyp oder welche Kombination von Hashwerten verwendet werden soll (ich würde nichts Schwächeres als SHA-256 empfehlen), welche Dateiattribute verwendet werden sollen (Inhalt, Größe, geänderter Zeitstempel usw.), die Häufigkeit, mit der geprüft wird. wie / wo die Hash-Datenbank gespeichert werden soll usw.

Einige mögen diesen Overkill in Betracht ziehen, aber abhängig von den Anforderungen des OP kann es ihm mehr Sicherheit geben, dass die Daten, die er speichert, nach einem bestimmten Zeitpunkt gleich bleiben.

0
John Lovejoy

Das National Archives of Australia hat den [Checksum Checker] ( http://checksumchecker.sourceforge.net/ ) entwickelt, der unter GPLv3 frei verfügbar ist.

Er liest eine Prüfsumme und einen Algorithmus aus einer Datenbank, berechnet dann die Prüfsumme für die Datei neu, vergleicht die beiden Werte und meldet im Fehlerfall. Es unterstützt die Algorithmen MD5, SHA1, SHA2, SHA256 und SHA512.

Andere Software in ihrem digitalen Repository [DPR] ( http://dpr.sourceforge.net/ ) generiert die anfängliche Prüfsumme (sowie alle anderen Verarbeitungsaktivitäten).

Verwandte Probleme