10

パフォーマンスとセキュリティの考慮事項はさておき、完全な雪崩効果を持つハッシュ関数を想定すると、データのブロックのチェックサムにはどちらを使用する必要がありますか: CRC32 または N バイトに切り捨てられたハッシュ? つまり、どちらがエラーを見逃す確率が小さいでしょうか? 具体的には：

  1. CRC32 対 4 バイト ハッシュ
  2. CRC32 対 8 バイト ハッシュ
  3. CRC64 対 8 バイト ハッシュ

データ ブロックは、ネットワークを介して転送され、ディスクに繰り返し格納されます。ブロックのサイズは 1KB から 1GB です。

私が理解している限り、CRC32 は 100% の信頼性で最大 32 ビットの反転を検出できますが、その後は信頼性が近づき1-2^(-32)、一部のパターンではさらに悪化します。完全な 4 バイト ハッシュの信頼性は常に1-2^(-32)です。

8 バイトのハッシュは、全体的な信頼性 (エラーを見逃す可能性) がはるかに優れている2^(-64)はずですが、CRC32 よりも優先する必要がありますか? CRC64はどうですか？

答えは、そのような操作で予想されるエラーの種類によって異なると思います。まばらな 1 ビット フリップや大規模なブロック破損が発生する可能性はありますか? また、ほとんどのストレージおよびネットワーク ハードウェアが何らかの CRC を実装していることを考えると、偶発的なビット フリップは既に処理されているはずではないでしょうか?

4

2 に答える 2

13

1-2 -32がアプリケーションにとって十分かどうかを判断できるのは、あなただけです。優れたハッシュ関数からの CRC -nとnビットの間のエラー検出パフォーマンスは同じに非常に近いため、どちらか高速な方を選択します。それはおそらくCRC -nです。

アップデート：

上記の「それは CRC -nである可能性が高い」は、わずかに可能性が高いだけです。非常に高性能なハッシュ関数が使用されている場合、そうはなりません。特に、CityHashcrc32は、Intelハードウェア命令を使用して計算された CRC-32 とほぼ同じ速さのようです! crc32434 MB のファイルで3 つの CityHash ルーチンと Intel 命令をテストしました。crc32命令バージョン (CRC-32C を計算する) は、24 ミリ秒の CPU 時間を要しました。CityHash64 は 55 ミリ秒、CityHash128 は 60 ミリ秒、CityHashCrc128 は 50 ミリ秒かかりました。CityHashCrc128 は同じハードウェア命令を使用しますが、CRC を計算しません。

CRC-32C の計算を高速crc32化するために、単一のコアで 3 つの算術論理演算ユニットを並列に使用するために、3 つの別個のバッファーで 3 つの命令に工夫を凝らし、アセンブラーで内側のループを記述する必要がありました。 . CityHash は非常に高速です。この命令がなければcrc32、CityHash64 または CityHash128 と同程度の速さで 32 ビット CRC を計算するのは難しいでしょう。

ただし、この目的のために CityHash 関数を変更するか、大量のデータ ストリームで CityHash 値の一貫した意味を定義するために任意の選択を行う必要があることに注意してください。その理由は、これらの関数がバッファリングされたデータを受け入れるように設定されていないためです。つまり、一度に関数にチャンクを供給し、データのセット全体が関数に一度に供給された場合と同じ結果が得られることを期待しています。中間状態を更新するには、CityHash 関数を変更する必要があります。

別の方法として、簡単で汚いテストのために私が行ったことは、前のバッファーの CityHash を次のバッファーのシードとして使用する関数のシード バージョンを使用することです。その問題は、結果がバッファサイズに依存することです。このアプローチで CityHash に異なるサイズのバッファーをフィードすると、異なるハッシュ値が得られます。

4年後の別の更新：

さらに高速なのは xxhash ファミリーです。非暗号化ハッシュの場合は、CRC を使用することをお勧めします。

于 2013-01-26T17:06:01.983 に答える
0

「パフォーマンス」の問題はさておき。SHA-2関数の1つ（SHA-256など）の使用を検討することをお勧めします。

于 2013-01-28T05:35:32.950 に答える