27

ハッシュのセット（MD5の最初の64ビットなので、非常にランダムに分散されます）があり、新しいハッシュがセットに含まれているかどうかを確認し、それをセットに追加できるようにしたいと考えています。

セットはそれほど大きくはなく、最大のものは数百万の要素になりますが、数百のセットがあるため、すべてをメモリに保持することはできません。

私がこれまでに持っていたいくつかのアイデア：

  • すべてをsqliteテーブルに保持しようとしましたが、すべてをメモリに収めることができなくなると、非常に遅くなります。
  • ブルームフィルターは、エラー率が非常に高いように聞こえます。私は小さなエラー率を気にしません（64ビットハッシュはすでに4G要素セットで1つの衝突を与えます）が、1％のようなエラー率は非常に高すぎます。
  • ファイルにギャップのあるハッシュのソート済みリストを保持し、十分なギャップがない場合はサイズを変更します。ハッシュは均一に分散されているため、このような非常に単純なスキームでも機能するはずです。

私は本当に明白な何かを逃していますか？優れたディスクベースのハッシュテーブルを実装するためのヒントはありますか？

4

6 に答える 6

19

最終的に使用したソリューションは次のとおりです。

  • 1セットにつき1ファイル
  • ファイルには 2^k 個のバケットが含まれており、それぞれが 256 バイトまたは 8 バイトの 32 エントリです。
  • 空のエントリは単にゼロにされます (000... は有効なハッシュですが、ハッシュの性質上、すべてが既に他のすべてと衝突する可能性がある場合、2^-64 の衝突の可能性は気にしません)。
  • すべてのハッシュは、最初の k ビットから推測されたバケットに存在します
  • バケットがオーバーフローした場合、ファイル サイズが 2 倍になり、すべてのバケットが分割されます
  • read()/write() ではなく、mmap() を介してすべてにアクセスします。

低レベルの Perl コードであるにもかかわらず、sqlite よりも信じられないほど高速であり、Perl は実際には高性能データベース向けではありません。MD5 よりも均一に分散されていないものでは機能しません。実装をシンプルに保つためにすべてが非常に均一であると想定しています。

最初に seek()/sysread()/syswrite() で試してみましたが、非常に遅く、mmap() バージョンは実際にははるかに高速です。

于 2009-02-03T22:23:10.290 に答える
12

あなたの問題/ニーズを正確に理解するのに苦労しましたが、それでもGitと、SHA1参照をディスクに保存する方法について考えさせられました:

与えられたハッシュの 16 進文字列表現、たとえば " abfab0da6f4ebc23cb15e04ff500ed54" を取ります。ハッシュの最初の 2 文字 (abこの場合は " ") を切り取り、ディレクトリにします。次に、残り (" fab0da6f4ebc23cb15e04ff500ed54") を使用して、ファイルを作成し、その中に何かを入れます。

このようにして、自動インデックス作成を使用して、ディスク上でかなりまともなパフォーマンスを得ることができます (当然、FS によって異なります)。./ab/fab0daさらに、最初の 2 文字 (" [..]")の後にディレクトリ区切り文字を挿入するだけで、既知の任意のハッシュに直接アクセスできます。

ボールを完全に逃した場合は申し訳ありませんが、運が良ければ、これでアイデアが得られるかもしれません。

于 2009-02-03T22:32:51.597 に答える
6

BerkeleyDBの仕事のように聞こえます。

于 2009-01-30T11:07:15.867 に答える
3

他のディスクベースのハッシュアルゴリズム/データ構造には、線形ハッシュと拡張可能ハッシュが含まれます。

于 2011-12-22T03:11:16.893 に答える
0

ハッシュにはランダムアクセスを使用する必要があるため、どのデータベースでも適切なパフォーマンスが得られるとは思えません。最善の策は、ディスク キャッシュを増やして (RAM を増やして)、ランダム アクセス速度が非常に速いハードディスク (おそらくソリッド ステート ディスク) を入手することです。

于 2009-01-30T13:01:40.800 に答える