4

以前の投稿で、Java でのカスタム ハッシュ マップ/テーブルのコーディングについて質問しました。今、私はそれを解決することができず、本当に欲しいものを適切に言及するのを忘れているかもしれないので、明確かつ正確にするためにそれらすべてを要約しています.

私がやろうとしていること：

URL でユーザー アクセス タイプを検索する必要があるサーバーのコードを作成しようとしています。

現在、私は 11 億 1000 万の URL (約) を持っています。

それで、私たちがしたことは、

1) データベースを 1 億 1000 万の URL ごとに 10 分割。2) キーが URL の一部 (LONG として表される) であり、値が URL の他の部分 (INT として表される) である並列配列を使用して HashMap を構築する -キーは複数の値を持つことができます。

3) 次に、システムの開始時に、1 日あたり他の URL (1 日に保存された数百万の URL) を HashMap で検索します。

あなたが試したこと：

1) 多くの NoSQL データベースを試しましたが、目的にはあまり適していませんでした。

2)その目的のために、(2 つの並列配列を使用して)カスタム ハッシュマップを作成しました。

それで、問題は何ですか：

システムが起動したら、各データベースのハッシュテーブルをロードし、何百万もの URL を検索する必要があります。

さて、問題は、

1) HashTable のパフォーマンスは非常に優れていますが、コードは HashTable の読み込みに時間がかかります (ファイル チャネルとメモリ マップ バッファーを使用して読み込みますが、HashTable の読み込みには 20 秒かかります - 2 億 2000 万のエントリ - 読み込み係数が 0.5 であるため、最も速く見つけました）

したがって、時間を費やしています: (HashTable Load + HashTable Search) * DB の数 = (5 + 20) * 10 = 250 秒。これは私たちにとって非常に高価であり、ほとんどの場合 (250 秒のうち 200 秒) はハッシュテーブルの読み込みに費やされます。

別の方法を考えていますか：

1 つの方法は次のとおりです。

メモリ マップト バッファを使用することで、読み込みと格納を気にせず、キャッシュをオペレーティング システムに任せることができます。ただし、何百万ものキーを検索する必要があるため、上記よりもパフォーマンスが低下します。

HashTable のパフォーマンスは優れていますが、読み込み時間が長いことがわかったので、次のような別の方法でカットすることを考えました。

1) サイズ Integer_MAX (独自のカスタム リンク リスト) のリンク リストの配列を作成します。

2) 値 (int) を、番号がキー番号であるリンク リストに挿入します (キー サイズを INT に減らします)。

3) したがって、リンクされたリストのみをディスクに格納する必要があります。

さて、問題は、このような大量のリンク リストを作成するには多くの時間がかかることです。データが十分に分散されていなければ、このような大量のリンク リストを作成しても意味がありません。

だから、あなたの要件は何ですか：

単に私の要件：

1) 複数の値を挿入して検索するキー。優れた検索パフォーマンスを探しています。2）メモリに（特に）ロードする高速な方法。

(キーは 64 ビットの INT で、値は 32 ビットの INT です。1 つのキーは最大で 2 ～ 3 個の値を持つことができます。キーを 32 ビットにすることもできますが、より多くの衝突が発生しますが、改善できれば許容範囲です) .

誰でも私を助けることができますか、これを解決する方法、またはこの問題を解決する方法についてのコメントはありますか?

ありがとう。

注意:

1) スタック オーバーフローの以前の提案によると、ディスク キャッシュ用の事前読み取りデータは、システムの起動時にアプリケーションが動作を開始し、システムの起動の翌日に開始されるため、不可能です。

2) 要件が単純であるため (ハッシュテーブルのキー値を挿入し、ロードして検索 (値を取得) することを意味します)、NoSQL データベースが適切にスケーリングされていることはわかりませんでした。

3) 私たちのアプリケーションは小さなプロジェクトの一部であり、小さなキャンパスに適用されるため、そのために SSD ディスクを購入する人はいないと思います。それが私の限界です。

4) Guava/Trove も使用しますが、16 GB にもそのような大量のデータを保存することはできません (32 GB の ubuntu サーバーを使用しています)。

4

3 に答える 3

0

1億1,100万のデータ項目にすばやくアクセスする必要がある場合は、ハッシュが最適です。しかし、車輪の再発明はしないでください。次のようなものを使用してください。

于 2012-08-01T19:23:24.290 に答える
0

(私があなたの問題を正しく理解していれば) 複雑な方法で問題にアプローチしようとしているように思えます。
つまり、プリロードしようとしているデータは、そもそも巨大です (2 億 2000 万 * 64 ~ 14GB としましょう)。そして、あなたはこれのためにメモリマップなどをしようとしています。
これは、異なるマシンに負荷を分散することで解決される典型的な問題だと思います。つまり、リンクされたリストのインデックスを見つけようとする代わりに、マップの特定の部分がロードされている適切なマシンのインデックスを見つけ出し、そこからそのマシンから値を取得しようとする必要があります (各マシンはこの部分をロードしました)。データベース マップを作成し、マップの適切な部分、つまり毎回マシンからデータを取得します)。
多分私はここから離れているかもしれませんが、32ビットマシンを使用していると思われます.
したがって、1 台のマシン アーキテクチャを使用し続ける必要があり、ハードウェアを改善することが経済的に不可能な場合 (ご指摘のとおり、64 ビット マシンと RAM または SSD の増設)、劇的な改善はできないと思います。

于 2012-08-01T20:24:05.430 に答える