1

私は単純な負荷分散サービスを実装しているので、Big-O は将来のパフォーマンスとスケーラビリティの重要な要素になると思います。しかし、両方のアルゴリズム ( WRRとRR )の big-O に関する参照は見つかりませんでした。

両方計算してみました。
(計算が間違っている可能性があることを警告しますが、正しい答えが得られたらすぐに投稿を編集します)

n-> サービス提供ノード数 (および重み)
z-> 待機/未完了タスク数
WRR の場合: O(n n z)
RR の場合: O(z^2)

For WRR: O(1)
For RR: O(1)

したがって、本当の問題は、私の計算が正しいかどうかですが、最も重要なのは、(実行中の各ノードに対して) 1 秒あたり数千の送信されたタスクを継続的に負荷分散した場合に、どのアルゴリズムが最も速く実行されるかということです。

いくつかの参考資料:

  • 非常に優れた RR の実装
  • WRRに関するスタックオーバーフローの質問

乾杯！

4

1 に答える 1

0

では、正確に何を測定する必要があるのでしょうか。大きな O はアルゴリズムのパフォーマンスに関するものであるため、各スケジューリング決定の時間の複雑さ、つまり 1 つのタスクを 1 つのノードに一致させるために必要な操作の数を測定するのが合理的であるように思われます。

ラウンドロビン

準備完了ノードのリストと待機タスクのリストの両方をキューとして実装でき、キューに対する操作は一定の償却時間で実装できます。したがって、キューに新しいメモリを割り当てる必要がある場合を除いて、O(1) で操作します。

加重ラウンドロビン

重みが固定されていて可換である場合、ここでも同じ複雑さを実現できます。各ノードをその重みに比例して循環キューに数回配置するだけです。キュー内でそれらを均等に配置するアルゴリズムを定式化できます。ほとんどの実用的なアプリケーションでは、適度な量子化により、適度に小さな整数として表現できる (つまり、スケーリングされた) 重みが得られます。

その他の考慮事項

ノードがビジーかアイドルかについて、何かフィードバックはありますか? もしそうなら、公平性の要件を述べていないので、RRは十分に機能するはずです。アイドル状態のフィードバックがない場合は、WRR が理にかなっている可能性があります。しかし、その場合、zノードがタスクを受け入れる準備ができているかどうかわからない場合、どのようにタスクを待機させるのでしょうか? バランサーが十分に速く処理できないために待機している場合でも、スケジューリング アルゴリズムの前と同じようにタスクのキューを想像できるため、考慮すべき問題ではありません。そのキューの長さは何にも影響しません。スケジューラで発生します。ここでも、優先順位、QoS 保証、または同様のメタ情報なしで、すべてのタスクが同じであると仮定します。

于 2013-02-07T22:07:20.663 に答える