4

私は毎日約100万のURLを追加/更新する必要があるプロジェクトに取り組んでいます。ある日はほとんど更新され、ある日はほとんど追加され、ある日は混合されます。

したがって、すべてのクエリで、URLテーブルでURLの一意性を検索する必要があります。

現時点ではインデックスがurl列に設定されており、正常に機能するため、URLの検索方法は非常に高速ですが、インデックスが同じ列に保持され、新しいレコードが数百万単位で追加される場合、RAMは今後数週間で十分ではなくなります。

だから私は解決策を探しているので、合計で1億5000万以上のURLがある場合、その検索は高速になるはずです。md5でインデックスを作成することを考えていますが、衝突の可能性が心配です。友人から、crc32ハッシュも計算し、md5と連結して衝突の可能性をゼロにし、binary（20）に格納するように言われました。これにより、現在url列データとして設定されている255ではなく20バイトのみがインデックスとして使用されます。タイプ。

現在、合計で約5,000万のURLがあり、8GBのRAMで正常に動作しています。

昨日、同じプロジェクトに関連するURLテキストの圧縮（短縮ではない）とmysqlへの保存について質問しました。

[編集] 検索を高速化するために、crc32ハッシュを10進形式でのみ配置する別の解決策を考えました。また、アプリケーションレベルの移植では、返されるレコードの数を確認します。複数のレコードが返される場合は、正確なURLも一致する必要があります。そうすれば、20バイト（md5 + crc32）ではなく各行に4バイトを格納することで、RAMとディスクスペースの負荷を低く抑えながら、衝突を回避することもできます。あなたが言うこと？

4

1 に答える 1

6

すべての質問を読んだ後（一意の制約によりハッシュが役に立たなくなりますか？、512ビットハッシュと4 128ビットハッシュおよびURLテキスト圧縮（短縮ではない）およびmysqlに格納）、問題は多かれ少なかれ次のとおりであることがわかりました。

「8GBのRAMを使用して+1億5000万のURLをmySQLに保存する必要がありますが、毎日更新するため、すべてのURLの書き込みと取得で優れたパフォーマンスを発揮します。そのため、多くのURLを取得して確認します。データベースに対して。実際には5000万のURLがあり、次の3か月で毎日約100万増加します。」

それですか？

重要な点は次のとおりです。保存するURLの形式はどのようになっていますか。URLを読み返す必要がありますか、それとも単にURLに関する情報を更新する必要がありますが、部分的なURLなどに基づいて検索することはありませんか？

URL = " http://www.somesite.com.tv/images/picture01.jpg "であり、ファイル名を含むすべてを保存するとします。異なる場合は、詳細を提供するか、私の回答の仮定を修正してください。

  1. URL内の文字のグループを置き換えることでスペースを節約できる場合。ここでわかるように、すべてのASCII文字がURLで有効であるとは限りません：RFC1738 、したがって、それらを使用してURLを表す（および圧縮する）ことができます。たとえば、文字0x81を使用して「http：//」を表すと6文字節約でき、0x82を使用して「.jpg」を表すとさらに3バイト節約できます。

  2. いくつかの単語は非常に一般的かもしれません（「画像」、「画像」、「ビデオ」、「ユーザー」など）。0x90から0x9fまでの文字+その他の文字（つまり、0x90 0x01、0x90 0x02、0x90 0xfa）を使用してそのような単語をエンコードする場合、16 * 256=4,096の「辞書エントリ」を使用して最もよく使用される単語をエンコードできます。2バイトを使用して4〜8文字を表します。

編集：上記のRFCで読むことができるように、URLには印刷可能なASCII文字しか含めることができません。これは、RFCでいくつかの観察が行われている状態で、0x20から0x7Fの文字のみを使用する必要があることを意味します。したがって、0x80以降の文字（16進表記、ASCIIテーブルでは10進数の128文字）は使用しないでください。したがって、1つの文字（たとえば0x90）を1つのフラグとして選択して、「次のバイトは辞書内の指示であり、私が使用するインデックスである」ことを示すことができる場合。1文字（0x90）* 256文字（0x00から0xFFまで）=辞書の256エントリ。ただし、文字0x90〜0x9f（または10進数で144〜159）を使用して、それらが辞書のフラグであることを示すこともできます。これにより、16*256の可能性が得られます...

これらの2つの方法は、データベースのスペースを大幅に節約し、衝突などを心配することなく元に戻すことができます。アプリケーションで辞書を作成し、それを使用してURLをエンコード/デコードするだけで、非常に高速になります。データベースがはるかに軽量になります。

すでに+50MのURLがあるので、それらに基づいて統計を生成し、より良い辞書を生成することができます。

ハッシュの使用：この場合のハッシュは、サイズとセキュリティの間のトレードオフです。衝突した場合、どれほど悪いことになるでしょうか？そしてこの場合、あなたはあなたを助けるために誕生日のパラドックスを使うことができます。

記事を読んで問題を理解してください。すべての入力（URLに含まれる可能性のある文字）が同等である場合、衝突の可能性を見積もることができます。そして、反対の計算をすることができます：許容可能な衝突確率とファイルの数を考えると、範囲はどのくらい広くすべきですか？そして、あなたの範囲はハッシュ関数によって生成されたビット数に正確に関連しているので...

編集： 128ビットを提供するハッシュ関数がある場合、2^128の可能な結果が得られます。したがって、誕生日のパラドックスの「範囲」は2 ^ 128です。これは、1年が365日ではなく2 ^ 128日であるようなものです。したがって、衝突の確率を計算します（「2つのファイルが同じ日に生まれ、365日ではなく2^128日である年）。512ビットを提供するハッシュを使用することを選択した場合、範囲は0から2 ^512...になります。

また、RFCを念頭に置いてください。インターネット/ URLの世界では、すべてのバイト（256文字）が有効であるとは限りません。したがって、衝突の可能性は低くなります。あなたにとって良い ：）。

于 2011-09-15T17:15:58.867 に答える