0

次のシナリオに最適な（最速の）アルゴリズムについて誰かがアイデアを持っているかどうかを尋ねたいと思います。

  • X プロセスは、非常に大きなファイルのリストを生成します。各プロセスは一度に 1 つのファイルを生成します
  • ファイルの準備ができたことが Y プロセスに通知されています。各 Y プロセスには、通知を収集するための独自のキューがあります
  • ある時点で、1 つの X プロセスが、ラウンド ルービン アルゴリズムを持つロード バランサーを介して 1 つの Y プロセスに通知します。
  • 各ファイルにはサイズがあり、当然ながら、ファイルが大きいほど X と Y の両方が忙しくなります

制限事項

  • ファイルが Y プロセスに入ると、それを削除して別の Y プロセスに移動するのは現実的ではありません。

現時点では、他の制限は考えられません。

このアプローチの欠点

  • ときどき X が遅れます (ファイルがプッシュされなくなります)。キューイングシステムの影響はあまり受けず、変更しても遅い/良い時間があります.
  • ときどき Y が遅れます (大量のファイルがキューに集まります)。繰り返しますが、以前と同じことです。
  • 1 Y プロセスは非常に大きなファイルでビジーです。また、キューにはいくつかの小さなファイルがあり、他の Y プロセスが引き継ぐ可能性があります。
  • 通知自体は HTTP 経由で行われるため、信頼できない場合があります。通知は失敗し、デバッグは何も明らかにしませんでした。

画像をより明確に見るのに役立つ詳細がいくつかあります。

  • Y プロセスは DB スレッド/ジョブです
  • X プロセスは Web アプリです
  • ファイルが X プロセスに到達すると、これらもクエリを実行して DB 側からリソースを消費します。制作部分に影響あり

今、私は次のアプローチを検討しました：

  • X は以前と同様にファイルを生成しますが、Y には通知しません。ファイル リストを作成するためのバッファ (テーブル) を保持します。
  • Y は常にバッファ内のファイルを検索し、それらを取得して独自のキューに格納します。

さて、この変更は実用的でしょうか? 私が言ったように、各 Y プロセスには独自のキューがあり、それを保持するのは効率的ではないようです。もしそうなら、私はまだ次のビットについて未定です：

取得するファイルを決定する方法

私はナップザックの問題を読みましたが、最初からファイルのリスト全体を持っている場合、それは適用できると思いますが、私は持っていません。実際、私は各ファイルのリストとサイズを持っていますが、各ファイルをいつ取得できるようになるかはわかりません。

私は生産者と消費者の問題を経験しましたが、それは固定バッファーとそれを最適化することを中心にしていますが、このシナリオではバッファーは無制限であり、それが大きいか小さいかはあまり気にしません。

次善の策は、各 Y プロセスが最小のファイルをロックして取得する貪欲なアプローチです。最初はそれが最速のアプローチのように見えます。私は現在それを検証するためのシミュレーションを構築していますが、セカンドオピニオンは素晴らしいでしょう.

更新 誰もが全体像を把握できるようにするために、ここに簡単に作成した図をリンクします。

  • ジョブはプロセスから独立しています。それらは高速で実行され、可能なファイル数を処理します。
  • ジョブがファイルで終了すると、HTTP リクエストが LB に送信されます
  • 各プロセスは、LB からの要求 (ファイル) をキューに入れます
  • LB はラウンド ロビン ルールで動作します

ダイアグラム

4

1 に答える 1

0

現在のLBの考え方は良くない

あなたが説明したロードバランサーは、あなたが言っている未来を予測するために不必要に必要とされるため、悪い考えです。さらに、ジョブの長さがさまざまな場合、ラウンドロビンはひどいスケジューリング戦略です。

消費者がアイドル状態のときに LB に通知するだけです。プロデューサから新しいジョブが到着すると、最初のアイドル状態のコンシューマが選択され、そこにジョブが送信されます。アイドル状態のコンシューマがない場合、プロデューサのジョブは LB のキューに入れられ、空いているコンシューマが現れるのを待ちます。

このようにして、消費者は常に最適に忙しくなります。

「(たとえば) 100 個のアプリを処理するために 1 つのキューを用意するのは非効率的です」とあなたは言います。これは大きな直感の飛躍であり、おそらく間違っています。ファイル名のみを処理するワーク キューは高速です。平均的な「非常に大きなファイル」処理操作よりも 100 倍高速である必要があるだけです (100 人のコンシューマーがいると推測するため)。ファイル処理は通常、10 秒または 1 秒です。たとえば、Apache mod または Redis に基づいて 2 つのランダムな選択を行うキュー ハンドラーは、1 秒あたり 10,000 のリクエストを簡単に処理できます。これは、ボトルネックから 10 倍離れています。

FIFO ベースでアイドル状態のコンシューマーから選択する場合、すべてのジョブの長さが等しい場合、動作はラウンドロビンになります。

LB が絶対に作業をキューに入れられない場合

次に、Ty(t) を、現在のエポック t で消費者 y のキュー内の作業を完了するために必要な将来の合計時間とします。LB の目標は、Ty(t) の値をすべての y と t で等しくすることです。これが理想です。

理想にできるだけ近づけるために、これらの Ty(t) 値を計算するための内部モデルが必要です。エポック t にプロデューサーから新しいジョブが到着すると、最小の Ty(t) 値を持つコンシューマー y を見つけ、この y にジョブを割り当て、それに応じてモデルを調整します。これは、この状況に最適な「残り時間の少ない」スケジューリング戦略のバリエーションです。

モデルは必然的に近似値でなければなりません。近似の質によって、その有用性が決まります。

標準的なアプローチ (OS スケジューリングなどから) は、各コンシューマー y に対して [t, T]_y のペアを維持することです。T は、過去のエポック t で計算された Ty(t) の推定値です。したがって、後のエポック t+d では、Ty(t+d) を max(Tt,0) として推定できます。最大値は、d>t の場合、推定ジョブ時間が期限切れになっているため、コンシューマーは完了する必要があります。

LB は、取得できるあらゆる情報を使用してモデルを更新します。例としては、ジョブに必要な時間の見積もり (おそらくファイル サイズやその他の特性に基づく説明から)、消費者が実際にジョブを終了したという通知 (LB は、完了したジョブの推定期間だけ T を減らし、t を更新します)、割り当てです。新しいジョブの (LB は、新しいジョブの推定継続時間だけ T を増やして t を更新します)、および長いジョブ中の消費者からの推定残り時間の中間進捗更新。

LB で利用可能な情報が詳細な場合は、[t, T]_y ペアの合計時間 T を、y でキューに入れられた作業のより完全なモデルに置き換える必要があります。たとえば、推定ジョブ期間のリストです。ここで、リストの先頭は現在実行中のものです。

LB モデルが正確であるほど、仕事が利用可能になったときにコンシューマーが飢える可能性が低くなります。これは回避しようとしていることです。

于 2013-03-23T20:22:59.973 に答える