3

URLでユーザーアクセスタイプを検索する必要があるサーバー用にコーディングしようとしています。

現在、最初は、1日に1億の異なるURLにアクセスしていることがわかります。現在、それは1日あたり約6億の異なるURLになりました。

1億人の場合、私たちが行ったことは次のとおりです。

1)キーがURLの一部(LONGとして表される)であり、値がURLの他の部分(INTとして表される)である並列配列を使用してHashMapを構築します-キーは複数の値を持つことができます。

2)次に、HashMapを検索して、URLがアクセスされた回数を見つけます。

ここで、HashTableが大きくなるにつれて、次のようになりました。

1)2つまたは3つの個別のHashTableを作成し、それを(一般的なファイルシステムに)ロードして保存し、URLがアクセスされた回数を確認します。

さて、問題は、

1)HashTableのパフォーマンスは非常に優れていますが、HashTableのロード/保存中にコードに時間がかかります(ファイルチャネルを使用しており、HashTableのロード/保存に16〜19秒かかります-2億エントリ-負荷率が0.5であるため)

私たちが尋ねようとしているのは:

1)この問題を解決する方法についてコメントはありますか?

2)ロード/保存時間を短縮する方法(以前に尋ねましたが、ファイルチャネルが最善の方法のようです)?

3)大きなHashTable(メモリ以上)を保存し、それを繰り返しキャッシュすることは良い解決策になりますか?もしそうなら、それを行う方法(少なくともいくつかのポインタ)。使ってみました

RandomAccessFile raf = new RandomAccessFile("array.dat", "rw");
IntBuffer map = raf.getChannel().map(FileChannel.MapMode.READ_WRITE, 0, 1 << 30).order(ByteOrder.nativeOrder()).asIntBuffer();

ただし、以前よりもパフォーマンスが低下します。

ありがとう。

注意:

1)Stack Overflowの以前の提案に従って、TokyoCabinetのようないくつかのNoSQL DBを使用しますが、私たちの経験から、カスタムHashTableは、1億のキーと値のペアよりも優れたパフォーマンスを提供します。

2)システムが起動するとアプリケーションが動作を開始し、翌日にシステムが起動するため、ディスクキャッシュのデータを先読みすることはできません。

私たちが言及するのを忘れたのは:

1)私たちのアプリケーションはプロジェクトの一部であり、小さなキャンパスに適用されるため、アクセスされるURLは8億以下であると想定しています。したがって、600/700のデータ値は固定されていると考えることができます。

2)私たちの主な関心事はパフォーマンスです。

3)アプリケーションをローカルで実行する必要があります。

編集:私たちのハッシュマップのコードはここにあります。

4

12 に答える 12

6

テーブルにメモリマップドバッファとしてアクセスするのが最適な場合があります。そうすれば、ロードや保存を気にせずにファイルへのランダムアクセスを実装し、キャッシュをオペレーティングシステムに任せることができます。現在の実装では、読み取りと書き込みにメモリマップドアクセスがすでに使用されていますが、それでもその間のJavaヒープにデータが読み込まれます。このデータの重複とコピーは避けてください。バッキングファイル自体をデータ構造として扱い、必要な場合にのみ、実際に必要な部分にのみアクセスします。

そのファイル内で、ハッシュの衝突が問題ではないと本当に確信している場合は、ハッシュマップが機能します。それ以外の場合は、ハードディスクページとほぼ同じサイズのノードを持つB+ツリーを探します。このように、各ディスクアクセスは、単一のキーよりもはるかに多くの使用可能なデータを生成するため、ツリーが浅くなり、個々のディスク操作が少なくなります。

他の人がこのようなものを実装していると思いますが、独自のハッシュマップの実装を好む場合は、独自のメモリマップドB+ツリーも作成することをお勧めします。

于 2012-07-11T14:44:31.687 に答える
3

全体のアプローチは私にはばかげているように聞こえます。あなたが本当に達成したいのは、個別のURLごとの単純なアクセスカウンターです。その性質上、このデータは頻繁に書き込まれますが、読み取られることはめったにありません。

この目的のために、データベーステーブルを作成し、アクセスごとに新しいエントリを追加します(ログとしても機能します)。URLにアクセスした頻度を把握する必要がある場合は、テーブルのSELECT COUNTを使用して簡単に行うことができます(URLエントリとともに保存する追加データの量に応じて、昨日のアクセス頻度などの制約付きカウントを実行することもできます)。 、先週など)。

これにより、すべての作業が、結果が本当に必要になるところまで延期されます。

ところで、Webサーバーのログファイルからもアクセスカウントを取得できる場合があるため、自分でデータを書き込む必要がない場合があります。最初にこれを調べてください。

于 2012-07-10T10:44:27.210 に答える
1

JCSのようなキャッシングフレームワークを使用できます。10億のキーと値のペアは問題にはなりません。

http://commons.apache.org/jcs/

于 2012-07-03T14:03:19.520 に答える
0

OracleCoherenceCacheを使用することをお勧めします。HashTableMapが持つすべてのメソッドを備えていることのすべての利点を得ることができます。

パフォーマンス面では、要件に応じてデータを保存できます。ご覧ください。

于 2012-07-12T08:55:25.583 に答える
0

アプリケーションを外部のコンピューティング能力を使用せずにローカルで実行する必要がある場合、ダイレクトメモリアクセスよりもパフォーマンスが高いソリューションはありません。HashMapよりも優れたパフォーマンスを提供できる唯一のデータ構造は配列です。すべての要素でのアクセスはO(1)です。ただし、これには、アイテムの数を事前に知っており、要素ごとに一意のアドレス指定インデックスがあり、隣接する重要なメモリを予約できる必要があります。

説明したように限られたケースに適した配列の後、HashTablesがありますが、データのサイズが大きくなると、衝突と動的サイズ変更のコストが増加し、パフォーマンスが低下します。

java.util.HashMap javadocを参照するだけでなく、Wikipediahttp ://en.wikipedia.org/wiki/Hash_tableを参照して次のことを理解することもできます。

  • それを計算するのにどれくらいの費用がかかりますか?
  • 価値はどのようにうまく分配されていますか?
  • 使用している負荷率はどれくらいですか。つまり、競合を解決するためにどのくらいのコストがかかりますか?
  • すべてのデータが完全に含まれるようになる前に、HashMapのサイズを変更する必要がある頻度はどれくらいですか?

HashMapをビルドするときにパフォーマンスが低下する場合(これは実際にはConcurrentHashMapであると私は信じています(並列にビルドする場合はスレッドセーフである必要があります)、なぜそれが発生するのかを調査することをお勧めします。

簡単ですが、簡単に始めるには、HashMapをTreeMapに置き換えます。このツリーマップのパフォーマンスは、そのサイズの決定論的関数であり、2つのパフォーマンスを比較します。


反対側で私があなたの質問を誤解し、複数のマシンで計算をスケーリングする機会がある場合、誰かがすでに指摘しているように、市場には興味深いソリューションがたくさんあり、それにカサンドラを追加します。

これらのソリューションは、負荷を複数のノードに分散することでパフォーマンスを向上させますが、各ノード内では、高速で効率的なアドレス指定のためによく知られたアルゴリズムを使用します。

于 2012-07-10T13:06:09.310 に答える
0

間違いなくredisを試してみてください、それは他のものを打ち負かすと思います

于 2012-07-03T14:05:41.580 に答える
0

基本的にCで記述されたキー/バリューストアであるBerkeleyDBを使用して、究極のパフォーマンスを実現できます。これはOracle製品(オープンソースですが)なので、真剣に受け止めます。

于 2012-07-03T14:06:55.563 に答える
0

質問とフォローアップの議論については明確ではありませんが、あなたの質問の性質は何ですか?
a)各営業日に約7億のURLをすべて処理するか、
b)それらの約7億のURLの一部をヒットするかの間で、非常に異なる状況が発生します。

つまり、URLの数に対するクエリの数の比率はどれくらいですか?

あなたの説明から、あなたはあなたの配列の異なる部分を表す異なるファイルをロード/アンロードしているように聞こえます...これはランダムなクエリを示唆し、それは(b)を示唆します。

また、「オールインメモリ」は実行不可能である(つまり、複数のファイルにまたがるアレイを分割した)ことをすでに認識しているので、最適なディスクアクセスアルゴリズムが次のビジネスの順序のようです。 、 いいえ?

クエリごとに、ファイル内でオフセットして数ページをメモリに読み込む単純なシーク(n * arrayElementSize)を試しましたか(キーごとの値の最大数を知っていますか?)。配列にはすでにベースインデックスが(計算されて)あるので、これは簡単にプロトタイプを作成できるはずです。

于 2012-07-11T04:35:26.850 に答える
0

HugeCollectionsを試すことができます、私はそれがこの目的のために書かれたと思います


数百万または数十億のエントリを持つコレクションをサポートするHugeCollectionsライブラリ。

具体的にはHugeMap

于 2012-07-13T12:17:26.150 に答える
0

メモリデータベースでオープンソースのsqliteを使用します。

于 2012-07-16T07:11:03.130 に答える
0

私があなたを正しく理解していれば、あなたのデータ構造はそれほど大きくありません

[(32 + 64) * 600 million] bits i.e. a 53.644 MB structure in memory

マップデータ構造もある程度のスペースを消費します。troveが最もメモリ効率の高いデータ構造の1つであるという難しい方法を見つけました。TLongIntHashMapを使用して、長いキーと整数値を格納します。LongおよびIntegerメモリオブジェクトをバイパスするように生のプリミティブを格納しました

于 2012-07-16T08:36:34.367 に答える
0

ほとんどの場合、メモリに収まらない読み取り専用のデータセットがあり、高速なキールックアップが必要なようです。いくつかの可能なトレードオフを除いて、ここには特効薬の解決策はありません。

600Mのレコードに至る所でアクセスする場合、何をしても、ディスクのランダムアクセス速度によって制限されます(シーケンシャルアクセス速度ではありません)。ファイルに直接アクセスするために使用FileChannel.mapします(いいえ、メモリ内のファイルの内容を読み取らず、操作するだけMappedByteBufferです。OSがキャッシュを処理します)。SSDに投資することは、お金を使う良い方法のように見えます(または、メモリをもう少し購入するだけですか?)。

これはキャンパス環境ですよね?ラボでコンピューターを使用して、memcached / redis/etcを作成できるかもしれません。集まる?多分あなたはそれを時間外に使うことができますか?

識別可能なデータに同時にアクセスする場合(つまり、ドメインa、bなどを分析する場合)、データをバケットに分割することをお勧めします。キャッシュを支援するために、関連データを物理的に近くに保つように。または、URLを事前に並べ替えて、バイナリ検索方式でアクセスしますか?

衝突の可能性がある程度許容できる場合は、完全なURLを保存せず、ハッシュキーとして64ビットのURLハッシュのみを保存できますか?いくつかの体操であなたはおそらく鍵をまったく保管しないで逃げることができますか?

それが今のところ私の考えです。

于 2012-07-16T19:38:05.637 に答える