6

この質問は StackOverflow で頻繁に繰り返されますが、以前の関連する回答をすべて読み、質問に少しひねりを加えています。

同じサイズの 4 億 7500 万行を含む 23Gb ファイルがあり、各行は 40 文字のハッシュ コードとそれに続く識別子 (整数) で構成されています。

受信ハッシュ コードのストリーム (合計で数十億) があり、受信ハッシュ コードごとに、それを見つけて、対応する識別子を出力する必要があります。このジョブは大規模ですが、一度だけ実行する必要があります。

ファイルが大きすぎてメモリに読み込めないため、次の方法でmmapを使用しようとしています:

codes = (char *) mmap(0,statbuf.st_size,PROT_READ,MAP_SHARED,codefile,0);

次に、コード内のアドレスに基づいて、アドレス演算を使用してバイナリ検索を実行します。

これは見事に機能し始めたようで、CPU を 100% 使用して数秒で数百万の識別子を生成しますが、その後、一見ランダムな時間が経過すると速度が遅くなり、クロールします。ps を使用してプロセスを確認すると、CPU を 100% 使用している状態 "R" から、CPU を 1% 使用している状態 "D" (ディスクバウンド) に変化しています。

これは繰り返し可能ではありません。同じデータに対してプロセスを再度開始できますが、「クロールが遅い」状態になるまでに 5 秒または 10 秒かかる場合があります。昨夜、これが起こる前に、私はそれからほぼ1分かかりました。

すべてが読み取り専用で、ファイルへの書き込みは試みておらず、マシン上の (制御している) 他のすべてのプロセスを停止しました。最新の Red Hat Enterprise Linux 64 ビット マシンです。

プロセスがディスクバウンドになる理由と停止方法を知っている人はいますか?

アップデート：

回答してくれた皆さん、そしてあなたのアイデアに感謝します。どういうわけかmmapを間違って使用しているのではないかと思っていたので、以前はさまざまな改善をすべて試したことがありませんでした。しかし、答えの要点は、すべてをメモリに詰め込むことができなければ、必然的に問題が発生するということでした. そこで、ハッシュ コードのサイズを、重複を作成しない先頭のプレフィックスのサイズに縮小しました。最初の 15 文字で十分でした。次に、結果のファイルをメモリに取り込み、入力されたハッシュ コードをそれぞれ約 20 億のバッチで実行しました。

4

5 に答える 5

3

まず、ファイルを分割します。

ハッシュコードで 1 つのファイルを作成し、整数 ID で別のファイルを作成します。行は同じなので、結果が見つかった後はうまく整列します。また、n番目ごとのハッシュを別のファイルに入れ、インデックスを保存するアプローチを試すこともできます。

たとえば、1000 番目ごとのハッシュ キーをインデックスと共に新しいファイルに入れ、それをメモリにロードします。次に、代わりにそれをバイナリスキャンします。これにより、ファイル内でさらにスキャンする必要がある 1000 エントリの範囲がわかります。はい、それでうまくいきます！しかし、おそらくそれよりもはるかに少ないでしょう。おそらく20レコードごとに、そのファイルサイズを20 +-で割るでしょう。

つまり、スキャン後は、ディスク上のファイルの数キロバイトに触れるだけで済みます。

もう 1 つのオプションは、ファイルを分割して複数のマシンのメモリに配置することです。次に、各ファイルをバイナリスキャンします。これにより、ディスクアクセスなしで可能な限り最速の検索が可能になります...

于 2013-02-14T02:45:33.517 に答える
2

プロセスがディスクバウンドになる理由と停止方法を知っている人はいますか?

バイナリ検索では、ファイル内で多くのシークが必要です。ファイル全体がメモリに収まらない場合、ページ キャッシュは大量のシークを適切に処理できず、このような動作が発生します。

これに対処する最善の方法は、大量のシークを削減/防止し、ページ キャッシュを機能させることです。

あなたのための3つのアイデア：

入力ストリームをソートできる場合は、次のアルゴリズムのようなものを使用して、ファイルをチャンクで検索できます。

code_block <- mmap the first N entries of the file, where N entries fit in memory
max_code <- code_block[N - 1]
while(input codes remain) {
  input_code <- next input code
  while(input_code > max_code)  {
    code_block <- mmap the next N entries of the file
    max_code <- code_block[N - 1]
  }
  binary search for input code in code_block
}

入力ストリームを並べ替えることができない場合は、データのインメモリ インデックスを構築することで、ディスク シークを減らすことができます。大きなファイルを渡し、次のようにtableします。

record_hash, offset into file where this record starts

このテーブルにすべてのレコードを保存しないでください。K 番目のレコードごとに保存してください。大きな K を選択しますが、これがメモリに収まるほど小さいです。

大きなファイルで特定のターゲット ハッシュを検索するには、インメモリ テーブルでバイナリ検索を実行してtable、ターゲット ハッシュより小さい最大のハッシュを見つけます。これが であるとしtable[h]ます。table[h].offset次に、 で始まり で終わるセグメントを mmaptable[h+1].offsetし、最終的なバイナリ検索を実行します。これにより、ディスク シークの回数が大幅に減少します。

これで十分でない場合は、複数のレイヤーのインデックスを作成できます。

 record_hash, offset into index where the next index starts

もちろん、インデックスのレイヤー数を事前に知っておく必要があります。

最後に、余剰資金がある場合は、いつでも 23 GB 以上の RAM を購入して、これを再びメモリ バウンドの問題にすることができます (Dell の Web サイトを見たところ、32 GB の RAM を搭載した新しいローエンド ワークステーションを購入すると1,400オーストラリアドル弱）。もちろん、それだけの量のデータをディスクから読み込むにはしばらく時間がかかりますが、データがそこにあれば準備は完了です。

于 2013-02-14T04:32:38.187 に答える
2

パトリシア トライ アルゴリズムをハッキングすることを考えたことはありますか? ハッシュ値と整数値のファイルを参照するデータ ファイルのパトリシア ツリー表現を構築できれば、各項目をノード ポインター (2*64 ビット?) に減らすことができるように思えます。ビット テスト オフセット (このシナリオでは 1 バイト) とファイル オフセット (複数の fseek() に対応する必要があるかもしれない uint64_t)。

于 2013-02-14T04:15:06.100 に答える
1

を使用する代わりにmmap、単純な古いlseek+を使用することを検討してreadください。いくつかのヘルパー関数を定義して、ハッシュ値またはそれに対応する整数を読み取ることができます。

void read_hash(int line, char *hashbuf) {
    lseek64(fd, ((uint64_t)line) * line_len, SEEK_SET);
    read(fd, hashbuf, 40);
}

int read_int(int line) {
    lseek64(fd, ((uint64_t)line) * line_len + 40, SEEK_SET);
    int ret;
    read(fd, &ret, sizeof(int));
    return ret;
}

次に、通常どおりバイナリ検索を実行します。少し遅くなるかもしれませんが、仮想メモリを消費し始めることはありません。

于 2013-02-14T04:59:22.210 に答える
1

私たちは裏話を知りません。ですので、的確なアドバイスは難しいです。どのくらいのメモリを持っていますか? あなたのハードドライブはどれくらい洗練されていますか? これは学習プロジェクトですか？あなたの時間は誰が払っていますか？32GB の RAM は、1 時間あたり 50 ドルを稼ぐ 2 日間の作業に比べてそれほど高価ではないようです。これはどのくらいの速度で実行する必要がありますか? 箱の外にどれだけ進んでいきますか？ソリューションは、高度な OS の概念を使用する必要がありますか? C のプログラムと結婚していますか? Postgresにこれを処理させるのはどうですか?

これは、リスクの低い代替手段です。このオプションは、他の提案ほど知的に魅力的ではありませんが、大きな利益をもたらす可能性があります. ファイルを 8GB の 3 つのチャンクまたは 4GB の 6 つのチャンクに分割します (使用しているマシンによっては、メモリに快適に収まる必要があります)。各マシンで同じソフトウェアを実行しますが、メモリ内で実行し、それぞれに RPC スタブを配置します。3 つまたは 6 つのワーカーのそれぞれに RPC 呼び出し元を書き込み、特定のハッシュ コードに関連付けられた整数を決定します。

于 2013-02-14T06:28:39.507 に答える