10

最大約 2 億の 40 ビット値を格納できる大きなハッシュ セットを格納する必要があります。2 億の 64 ビット値として保存することは許容されます (2 億 * 16 ビットの損失にもかかわらず)。

要件は次のとおりです。

  • 小さなメモリフットプリント(ディスクスペースは問題ではなく、メモリは問題です)

  • 高速contains(long l)およびadd(long l)メソッド (SQL よりもはるかに高速)

  • 埋め込み

  • 無料で厄介なライセンスなし (Berkeley DB なし)。LGPL 大丈夫です。

  • 偽陽性も偽陰性もないので、ディスクベースのブルームフィルターなどは私が求めているものではありません

SQL は私が求めているものではありません。

私は本当にこのような速いものを求めていると思っているからです(ソリューションがSQLソリューションよりもはるかに高速であることに注意してください):

高速なディスクベースのハッシュテーブル?

Google にはそのような Java API がありますか?

「キー」のみを使用する高速なディスクベースのキー/値ペアの実装は機能しますか?

または、他の何か?

私はむしろ再発明したくありません。

4

3 に答える 3

2

128 GB のディスクに余裕がある場合は、40 ビット値ごとに 1 ビットを格納できます。次に、ランダムアクセスファイルを使用して、ビットが設定されていることを確認したり、変更したりできます。値を挿入したり、インデックスを維持したりする必要はありません。

于 2010-02-27T09:21:10.240 に答える
2

sg-cdb (djb の cdb の奇妙なギズモ ポート) を試してから、RandomAccessFile を BufferedRandomAccessFile (jai-imageio コードに適切なものがあります) に交換します。

私は書き込みパフォーマンスを吹き飛ばしています。屋根を通り抜けます(すべてがバッファリングされ、一挙にコミットされるため)。ただし、バッファリングされた RAF の読み取りパフォーマンスは変わりません。

H2 一括インポートと時間をかけて比較することができました。

データベースは単純です: キー => 値。ルックアップはキーでのみサポートされています。キーは私の場合(base32でエンコードされたランダムなint + base32でエンコードされた一意のint)であるため、ローカリティは実際にはあまり役に立たないはずです。値は、120 のランダム バイトの配列です。

ロード (SQL 挿入)

h2、131MB キャッシュ (フラッシュを含み、起動は含まない):

2011 年 5 月 4 日午後 11 時 45 分 10 秒 test.TestH2Simple メイン : 挿入が実行され、次の時間に追加されました:101625 ミリ秒

データベースサイズ:約140MB

バッチサイズ: 2000 : 挿入が実行され、追加: 116875 ミリ秒

バッチサイズ: 10000 : insertsperformed の追加: 70234 ミリ秒

cdb の sg-cdb (奇妙なギズモ) ポートと比較します。

RandomAccessFile あり: フラッシュなしの挿入:21688 ミリ秒、フラッシュ:30359 ミリ秒、合計:52047 ミリ秒 ディスク上のファイルのサイズ: 66.1 MB (69,315,632 バイト)

BufferedRandomAccessFile の場合: 約 6.5 秒

もちろん、H2 は挿入中に継続的にデータをフラッシュしているのに対し、sg-cdb はそうではないため、実際には公正な比較ではありません。比較を行う際には、この点に留意する必要があります。おそらく公平なのは、sg-cdb 挿入と H2 一括挿入を比較することです。

読み取り (SQL 選択)

sg-cdb

: 検索:490000 完了:1304544550439 かかった:17547 ミリ秒、カウンター:0

H2

: 19579 ミリ秒で実行された選択

メモリ マップ ファイルについて: 探しているファイルではないようです。MMap ファイルの優れたパフォーマンスは、約 100MB 以上をメモリにマップした場合です (私の経験)。

于 2011-05-04T23:07:09.227 に答える
0

ハッシュ テーブルではなく、B ツリーを使用する必要があると思います。ハッシュ テーブルにはセカンダリ ストレージの適切な局所性がないため、ディスク I/O に多くの時間を費やすことになります。

ほとんどのデータベースは、リレーショナルであろうとなかろうと、インデックスを B ツリーとして実装しているため、他のデータが添付されていないインデックスを格納するのと同じことを話しているのです。

このデータ ストアを同時に更新する複数のプロセスがありますか?

于 2010-03-02T13:50:32.727 に答える