0

リモート ホストに送信したい要求のプールが非常に大きいとします。他のサーバーと同様に、リモート ホストの容量には制限があります。すべてのメッセージは最終的に配信される必要があり、適時性は望ましいですが重要ではありません。送信したリクエストの応答時間や失敗率を監視する以外に、リモート ホストのこの容量を知る方法はありません。

リモート ホストをフォール オーバーさせることなく、スループットを最大化するレートでリクエストを送信するアルゴリズムを開発する必要があります。

最良の出力変数は、リクエスト N がリクエスト N-1 の M ナノ秒後にディスパッチされるような、リクエスト間の期間のようです。

最適なレートを決定する問題にどのようにアプローチすればよいですか? 作成できる書類はありますか? それとも、誰かが不思議なアルゴリズムを思い付くことができますか? 誰もこれを以前にやったことがありますか?

注: トークン バケットは、私が探している答えでもありません。私はすでにトークン バケットに非常によく似たものを使用していますが、トークンをバケットに追加するレートを決定する方法を探しています。

4

1 に答える 1

2

Web クローラーを作成したとき、魔法のアルゴリズムを思いつきませんでした。確かに完璧ではありませんが、かなり良い仕事をしていると思われるいくつかのヒューリスティックを使用しました。

まず、サイトの robots.txt ファイルを調べました。クロール遅延エントリがあった場合は、それを決して超えないようにしました。

他のサーバーについては、最後の n リクエストに必要な時間の実行中の平均を維持し (5 の値に落ち着いたと思います)、その平均よりも頻繁にリクエストを送信しないようにします。リクエストを行ってからレスポンスの処理が完了するまでの時間を測定しました。

サーバーがタイムアウトした場合、そのリクエストの時間は実行中の平均になります。

サーバーから 50x を受け取った場合、そのサーバーに別のリクエストを行う前に、かなり長い時間 (5 分以上) 遅延します。50x の応答が繰り返されると、誰かが問題を確認できるようになるまで、要求を停止することになります。

また、40x の応答も追跡しました。見つからなかったりアクセスが拒否されたりすると、クローラーはドメインの処理を停止し、フラグを立てて、誰かがそれを見ることができるようにします。

分散クローラーがありました。個々のクローラーが同じドメインに対して同時リクエストを行うことはなく、複数のサーバーが同じドメインに対して同時リクエストを行うことは珍しい、いくつかのクロスサーバー通信がありました。

これにより、特定のサーバーのスループットが最大化されなかったと確信していますが、大規模なサイトを非常にビジー状態に保ちました. 私たちにとってさらに重要なことは、多くのサイトによってブロックされるのを防いでくれたことです。

また、API を使用する多くのサイトの特殊なケースの処理も行いました。リクエストの制限がいくらかを言う人もいれば、それらのサイトの設定を調整して、すぐにそれに乗るようにしました. しかし、数十個しかありませんでした。9,000 台のサーバーの要求頻度を手動で構成する (そして変更に対応する) ことは現実的ではありません。ただし、ダースまたは 2 を手動で構成できる場合があります。

于 2013-02-23T00:47:59.323 に答える