6

ネットワーク経由で大きなファイルを転送する必要があり、それらのチェックサムを 1 時間ごとに作成する必要があります。そのため、チェックサムを生成する速度は私にとって重要です。

どういうわけか、Windows XP Pro 64 ビット マシンで zlib.crc32 と zlib.adler32 を 4GB を超えるファイルで動作させることができません。ここで 32 ビットの制限に達したのではないでしょうか? hashlib.md5 を使用して結果を得ることができましたが、問題は速度です。4.8GB ファイルの md5 を生成するには、約 5 分かかります。タスク マネージャーは、プロセスが 1 つのコアのみを使用していることを示しています。

私の質問は次のとおりです。

  1. 大きなファイルでcrcを機能させる方法はありますか? md5よりcrcの方が好き
  2. そうでない場合、md5.hexdigest()/md5.digest を高速化する方法はありますか? またはこの場合、hashlib hexdigest/digest はありますか? 多分それをマルチスレッドプロセスに分割しますか？それ、どうやったら出来るの？

PS: 私は「資産管理」システムのようなものに取り組んでいます。svn のようなものですが、資産は大きな圧縮された画像ファイルで構成されています。ファイルには、わずかな増分変更があります。変更の検出とエラーの検出には、ハッシュ/チェックサムが必要です。

4

6 に答える 6

5

これは、ライブラリ/言語の選択の問題ではなく、アルゴリズムの選択の問題です。

主に考慮すべき2つのポイントがあるようです。

  • ディスクI/Oは全体的なパフォーマンスにどの程度影響しますか？
  • エラー検出機能の期待される信頼性はどれくらいですか？

明らかに、2番目の質問に対する答えは「いくつかのフォールスネガティブが許可されている」のようなものです。これは、4Gbメッセージに対する32ビットハッシュの信頼性は、適度にノイズの多いチャネルであっても、実質的に絶対的なものではないためです。

マルチスレッドによってI/Oを改善できると仮定すると、メッセージ全体の順次スキャンを必要としないハッシュを選択できます。代わりに、ファイルを並行して処理し、個々のセクションをハッシュし、ハッシュ値を組み合わせるか追加して、より長く、より信頼性の高いエラー検出デバイスを形成することができます。

次のステップは、このファイルの処理を順序付けられたセクションとして形式化し、そのように送信することです（受信者側で再接着するため）。このアプローチは、ファイルの生成方法に関する追加情報（たとえば、ログファイルのように追加によって排他的に変更される場合があります）とともに、必要なハッシュ計算の量を制限することさえ可能にする場合があります。このアプローチの追加された複雑さは、非常に高速なCRC計算が必要な場合に重み付けする必要があります。

補足：Alder32は、特定のしきい値を下回るメッセージサイズに制限されていません。これは、zlibAPIの制限である可能性があります。（ところで、zlib.adler32について私が見つけた参照はバッファーを使用していましたが、このアプローチは、ストリーミングプロセスを優先して、巨大なメッセージのコンテキストでは回避する必要があります。ファイルから少し読み取り、計算し、繰り返します。 。）

于 2009-10-07T17:24:08.143 に答える
3

まず、CRC アルゴリズムには、任意の長さのデータの処理を妨げるものは何もありません (ただし、特定の実装では制限が課される可能性があります)。

ただし、ファイル同期アプリケーションでは、ファイルが大きくなったときにファイル全体をハッシュしたくない場合があるため、おそらく問題にはなりません。ファイル全体をハッシュし、両端のハッシュが異なる場合は、ファイル全体をコピーする必要があります。固定サイズのチャンクをハッシュする場合、ハッシュが変更されたチャンクのみをコピーする必要があります。ファイルへの変更のほとんどがローカライズされている場合 (データベースなど)、必要なコピーが大幅に少なくなる可能性があります (また、チャンクごとの計算を複数のコアに分散する方が簡単です)。

ハッシュ アルゴリズム自体に関して言えば、基本的なトレードオフは速度と衝突の欠如です (2 つの異なるデータ チャンクが同じハッシュを生成します)。CRC-32 は高速ですが、一意の値が 2^32 しかないため、衝突が発生する可能性があります。MD5 ははるかに低速ですが、2^128 の一意の値を持つため、衝突はほとんど見られません (ただし、理論的には可能です)。より大きなハッシュ (SHA1、SHA256、...) にはさらに固有の値がありますが、それでも低速です: それらが必要かどうかは疑問です: 意図的に心配しているデジタル署名アプリケーションとは異なり、偶発的な衝突が心配です (悪意を持って) 設計された衝突。

rsync ユーティリティが行うことと非常によく似たことをしようとしているようです。rsyncだけ使えますか？

于 2009-10-07T18:02:08.270 に答える
2

XP でファイルのサイズ制限に達している可能性があります。64 ビットはより多くのアドレス空間を提供します (アプリケーションごとに 2GB (またはそれくらい) のアドレス空間を削除します) が、おそらくファイル サイズの問題に対しては何もしません。

于 2009-10-08T23:02:25.297 に答える
1

md5自体を並行して実行することはできません。ただし、ファイルをセクションごとに（並列に）md5して、ハッシュのリストのmd5を取得することができます。

ただし、これは、ハッシュがIO制限されていないことを前提としています。これは、IOが制限されていると思われます。Anton Gogolevが示唆しているように、ファイルを効率的に（2の累乗の大きなチャンクで）読み取っていることを確認してください。それが終わったら、ファイルが断片化されていないことを確認してください。

また、新しいプロジェクトには、md5ではなくsha256などのハッシュを選択する必要があります。

zlibチェックサムは4Gbファイルのmd5よりもはるかに高速ですか？

于 2009-10-07T16:39:25.690 に答える
1

MD5 の性質上、大きなファイルの MD5 ハッシュを計算するために複数のコアを使用することはできません。メッセージがチャンクに分割され、厳密な順序でハッシュ関数に供給されることが期待されます。ただし、1 つのスレッドを使用してファイルを内部キューに読み込み、別のスレッドでハッシュを計算することができます。ただし、これによりパフォーマンスが大幅に向上するとは思いません。

大きなファイルの処理に非常に時間がかかるという事実は、「バッファリングされていない」読み取りが原因である可能性があります。たとえば、一度に 16 Kb を読み取ってから、コンテンツをチャンクでハッシュ関数にフィードします。

于 2009-10-07T16:36:30.360 に答える
0

crc-generatorモジュールを試しましたか？

于 2009-10-07T16:43:18.837 に答える