4

一連のファイルを読み取り、それをキーと値のペアに分割し、これらをディスク上のそのキーの (キー、値のリスト) として保存する必要があります。これは、map-reduce パラダイムとよく似ています。ただし、すべてが1台のコンピューターにあります。たとえば、さまざまなファイルにさまざまなリストを書き、キーでファイルに名前を付けることができます。それは物事を行う非常に貧弱な方法のようです。まず、キーが 10 億個あれば、最終的には 10 億個のファイルになります。したがって、明らかにそれはうまくいきません。何らかのメモリ マッピングが必要になります。また、マップ ジョブを実行する別のスレッドを用意する必要があるため、同じバッファに書き込む場合は、それらの間である種の同期が必要になります。キーと値のバッファマッピングがあり、バッファを同期している場合、スレッドはお互いのつま先を踏んではならないので、その部分はうまくいくはずです。問題は、値をディスクにマッピングする方法です。同じファイル内の異なるキーに対応するバッファを書き込むにはどうすればよいですか? 誰かが私を正しい方向に向けることができれば、それは大歓迎です。この分野に関する私の知識は非常に哀れです。再度、感謝します。

4

4 に答える 4

6

実用的な観点からは、Lirik が提案したように、BerkeleyDB でこれを行うのは簡単です。

実践よりも理論に興味がある場合は、これを「外部ソート」操作としてアプローチすることをお勧めします。つまり、できるだけ多くの入力をメモリに読み込み、キーで並べ替えます。ソートされたチャンクを単一のファイルとして書き出します。ソートされたファイルは、1 つのファイルに簡単にマージできます。

他のアプリケーションの中でも、これは Lucene がテキスト検索用の「逆インデックス」を構築するために使用するアプローチです。「キー」は文書内の単語であり、「値」はその単語が出現する文書のリストです。Lucene はドキュメントを読み取り、単語ごとに単語からドキュメントへのエントリをメモリに作成します。メモリがいっぱいになると、インデックス セグメントがディスクに書き込まれます。ディスク上に多数のインデックス セグメントがある場合、それらは 1 つのセグメントにマージされます。実際、Lucene のインデックス ライターをタスクに適合させることもできます。

作業は複数のスレッドに分割できます。ただし、ディスクの競合には注意が必要です。多くのファイルを同時に読み書きするためにスキップすると、従来のドライブの速度が大幅に低下します。いくつかの活動を同時にスケジュールする機会があるかもしれません。特にマシンに 2 つのディスク ドライブがある場合は、以前に並べ替えられたチャンクをディスクに書き込んでいる間に、おそらく 1 つのファイルから新しいデータを読み込むことができます。もちろん、ソートされたセグメントの一部を一時的に保存するために SSD を使用すると、非常に役立ちます。

于 2011-08-03T20:08:06.940 に答える
4

Oracle の Berkeley DBがぴったりだと思います。

BerkeleyDB

Berkeley DB は、上記のように、利用可能なアクセス方法の 1 つでインデックス付けされたキーと値のペアでデータの不透明なバイト配列としてデータを格納するように設計されています。

Berkeley は非常に堅牢で成熟しており、高速ですが、より軽量なアプローチを使用する場合はSQLiteを使用してください。

もう 1 つのオプションは、Google の LevelDB を使用することです。これは C++ で書かれていますが、その周りに Java ラッパーがあります。LevelDB は気が遠くなるほど高速で、非常に軽量です。

あなたのプロジェクトについてこれ以上の詳細はありませんが、私は次のようにしか言えません:

  • これらすべてのソリューションでは、キーと値のペアが同じファイルに保存されます (必要に応じて、複数のインスタンスを個別のファイルに保存できますが、その理由はわかりません)。
  • BerkeleyDB と LevelDB には、非常に優れたキャッシュ機能とマッピング機能があります。
  • BDB と LDB も圧縮が可能です (SQLite も圧縮できるかどうかは不明です)。
  • キーの配布によっては (つまり、Google のCityHashのような優れたハッシュ関数を使用している場合)、非常に優れたデータの局所性を実現できるため、テーブル スキャンを減らすことができます。
  • これらのソリューションはディスクベースであり、一般にマルチスレッドのディスク I/O 操作は必要ないため、おそらく独自のスレッド セーフ バッファを記述し、複数のスレッドが BDB/LDB に書き込むことを避ける必要があります。

批評: - 「キーと値のバッファー マッピング」の意味がよくわかりません... 各キーにバッファーをマッピングしていますか? なぜそれが必要なのですか？

于 2011-08-03T19:23:30.173 に答える
0

Hadoopの使用を見たことがありますか?

于 2011-08-04T20:05:51.507 に答える