Abgesehen von Performance- und Sicherheitsüberlegungen und unter Annahme einer Hash-Funktion mit perfektem Avalanche-Effekt, die ich für Prüfsummen von Datenblöcken verwenden sollte: CRC32 oder Hash, abgeschnitten auf N Bytes? I.e. was wird eine kleinere Wahrscheinlichkeit haben, einen Fehler zu verpassen? Speziell:
Datenblöcke sollen wiederholt über das Netzwerk übertragen und auf der Festplatte gespeichert werden. Blöcke können 1 KB bis 1 GB groß sein.
Soweit ich es verstehe, kann CRC32 bis zu 32 Bit Flips mit 100% Zuverlässigkeit erkennen, aber danach nähert sich seine Zuverlässigkeit 1-2^(-32) und ist für einige Muster viel schlechter. Eine perfekte 4-Byte-Hash-Zuverlässigkeit ist immer 1-2^(-32) , gehen Sie also.
8-Byte-Hash sollte eine viel bessere Gesamtzuverlässigkeit haben ( 2^(-64) Chance, einen Fehler zu verpassen), sollte es also gegenüber CRC32 bevorzugt werden? Was ist mit CRC64?
Ich denke, die Antwort hängt von der Art der Fehler ab, die bei einer solchen Operation erwartet werden. Werden wir wahrscheinlich spärliche 1-Bit-Flips oder massive Blockkorruption sehen? Auch wenn die meisten Speicher- und Netzwerkhardware eine Art von CRC implementiert, sollten nicht schon versehentliche Bit-Flips behoben werden?
Nur Sie können sagen, ob 1-2 -32 für Ihre Anwendung gut genug ist oder nicht. Die Fehlererkennungsleistung zwischen einer CRC- n und n -Bits von einer guten Hash-Funktion wird sehr ähnlich sein, also wählen Sie, was schneller ist. Das ist wahrscheinlich die CRC- n .
Aktualisierung:
Das obige "Das ist wahrscheinlich die CRC- n " ist nur etwas wahrscheinlich. Es ist nicht so wahrscheinlich, wenn sehr leistungsfähige Hash-Funktionen verwendet werden. Insbesondere CityHash scheint fast so schnell zu sein wie ein CRC-32, der mit der Intel crc32 Hardware-Anweisung berechnet wurde ! Ich habe drei CityHash-Routinen und die Intel crc32 Anweisung in einer 434 MB Datei getestet. Die crc32 -Anweisungsversion (die einen CRC-32C berechnet) benötigte 24 ms CPU-Zeit. CityHash64 dauerte 55 ms, CityHash128 60 ms und CityHashCrc128 50 ms. CityHashCrc128 verwendet denselben Hardware-Befehl, berechnet jedoch keinen CRC.
Um die CRC-32C-Berechnung so schnell zu bekommen, musste ich mit drei crc32 -Anweisungen in drei separaten Puffern arbeiten, um die drei arithmetisch-logischen Einheiten parallel in einem einzigen Kern zu verwenden Schreiben der inneren Schleife in Assembler. CityHash ist verdammt schnell. Wenn Sie die Anweisung crc32 nicht haben, wäre es schwierig, einen 32-Bit-CRC so schnell wie einen CityHash64 oder CityHash128 zu berechnen.
Beachten Sie jedoch, dass die CityHash-Funktionen für diesen Zweck geändert werden müssen oder eine willkürliche Auswahl getroffen werden muss, um eine konsistente Bedeutung für den CityHash-Wert bei großen Datenströmen zu definieren. Der Grund ist, dass diese Funktionen nicht eingerichtet sind, um gepufferte Daten zu akzeptieren, d. H. Die Funktionen jeweils zu einem Zeitpunkt zu verarbeiten und zu erwarten, dass das gleiche Ergebnis erhalten wird, als ob der gesamte Datensatz der Funktion auf einmal zugeführt würde. Die CityHash-Funktionen müssten geändert werden, um einen Zwischenstatus zu aktualisieren.
Die Alternative und was ich für den schnellen und schmutzigen Test gemacht habe, ist die Verwendung der Seed-Versionen der Funktionen, in denen ich den CityHash aus dem vorherigen Puffer als Seed für den nächsten Puffer verwenden würde. Das Problem dabei ist, dass das Ergebnis dann von der Puffergröße abhängig ist. Wenn Sie CityHash-Puffer unterschiedlicher Größe mit diesem Ansatz füttern, erhalten Sie unterschiedliche Hash-Werte.
Ein weiteres Update vier Jahre später :
Noch schneller ist die xxhash-Familie . Ich würde jetzt das über einen CRC für einen nicht kryptografischen Hash empfehlen.
Beseitigung von "Performance" Problemen; Vielleicht möchten Sie eine der SHA-2-Funktionen (zB SHA-256) in Betracht ziehen.
Tags und Links hash checksum crc32 error-detection