30

検索システムのバックエンド アプリケーションを開発しています。検索システムはファイルを一時ディレクトリにコピーし、ランダムな名前を付けます。次に、一時ファイルの名前をアプリケーションに渡します。私のアプリケーションは、限られた時間内に各ファイルを処理する必要があります。それ以外の場合はシャットダウンされます。これはウォッチドッグのようなセキュリティ対策です。ファイルの処理には時間がかかる可能性が高いため、このシナリオを処理できるアプリケーションを設計する必要があります。次に検索システムが同じファイルのインデックスを作成しようとしたときにアプリケーションがシャットダウンされた場合、別の一時的な名前が付けられる可能性があります。

明白な解決策は、検索システムとバックエンドの間に中間層を提供することです。バックエンドへのリクエストをキューに入れ、結果が到着するのを待ちます。リクエストが中間層でタイムアウトした場合 - 問題ありません。バックエンドは引き続き動作し、中間層のみが再起動され、後で検索システムによってリクエストが繰り返されたときにバックエンドから結果を取得できます。

問題は、ファイルを識別する方法です。それらの名前はランダムに変わります。MD5 のようなハッシュ関数を使用して、ファイルの内容をハッシュするつもりです。私は誕生日のパラドックスをよく知っており、リンクされた記事からの推定を使用して確率を計算しました。100,000 個以下のファイルがあると仮定すると、2 つのファイルが同じ MD5 (128 ビット) を持つ確率は約 1,47x10 -29です。

このような衝突確率を気にする必要がありますか、それともハッシュ値が等しいとファイルの内容が等しいと仮定する必要がありますか?

4

5 に答える 5

43

悪意のある誰かがあなたのファイルをいじって衝突を引き起こしていない限り、等しいハッシュは等しいファイルを意味します。（これは、インターネットからコンテンツをダウンロードしている場合に当てはまる可能性があります）その場合は、SHA2ベースの機能を使用してください。

偶発的なMD5の衝突はありません。1,47x10-29は本当に本当に少ない数です。

大きなファイルの再ハッシュの問題を克服するために、私は3段階のIDスキームを使用します。

  1. ファイルサイズのみ
  2. ファイルサイズ+ファイル内のさまざまな位置にある64K*4のハッシュ
  3. フルハッシュ

したがって、新しいサイズのファイルが表示された場合は、重複がないことが確実にわかります。等々。

于 2009-05-14T10:15:43.490 に答える
3

すべきではないと思います。

ただし、2 つの等しいファイルが異なる (実際の名前で、md5 ベースではない) という概念がある場合は、そうする必要があります。同様に、検索システムでは、2 つのドキュメントの内容がまったく同じである場合がありますが、それらは異なる場所にあるため区別されます。

于 2009-05-14T09:14:12.297 に答える
2

衝突なしでシリアル化する必要がある分散システムに UUID を使用しながら、安全にスリープできるモンテカルロ アプローチを思いつきました。

from random import randint
from math import log
from collections import Counter

def colltest(exp):
    uniques = []
    while True:
        r = randint(0,2**exp)
        if r in uniques:
            return log(len(uniques) + 1, 2)
        uniques.append(r)

for k,v in Counter([colltest(20) for i in xrange(1000)]):
    print k, "hash orders of magnitude events before collission:",v

次のように出力します。

5 hash orders of magnitude events before collission: 1
6 hash orders of magnitude events before collission: 5
7 hash orders of magnitude events before collission: 21
8 hash orders of magnitude events before collission: 91
9 hash orders of magnitude events before collission: 274
10 hash orders of magnitude events before collission: 469
11 hash orders of magnitude events before collission: 138
12 hash orders of magnitude events before collission: 1

私は前に公式を聞いたことがあります: log(x/2) キーを格納する必要がある場合は、少なくともキースペース e**(x) を持つハッシュ関数を使用してください。

実験を繰り返すと、1000 個の log-20 空間の母集団に対して、log(x/4) もの衝突が発生することがあることが示されています。

122 ビットの uuid4 の場合、約 2**31 個のアイテムができるまで、いくつかのコンピューターがランダムな uuid を選択している間、安全にスリープします。私が考えているシステムのピーク トランザクションは、1 秒あたり約 10 ～ 20 イベントであり、平均を 7 と想定しています。極度のパラノイアを考えると、約 10 年の運用ウィンドウが得られます。

于 2015-01-30T14:17:34.560 に答える
1

これは、任意のハッシュ サイズとオブジェクト数の衝突の確率を推定できるインタラクティブな計算機です - http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/

于 2015-04-23T13:51:05.183 に答える