12

バックグラウンド

EchoNestにはレート制限されたAPIがあります。特定のアプリケーション（APIキーを使用するリクエストで識別される）は、1分間に最大120回のREST呼び出しを行うことができます。サービス応答には、直前に行われたコールの総数の見積もりが含まれます。APIを繰り返し乱用すると（制限を超えて）、APIキーが取り消される可能性があります。

単一のマシン（クライアントにサービスを提供するWebサーバー）から使用する場合、アクセスの制御は簡単です。サーバーは要求の履歴を完全に認識しており、サーバー自体を正しく調整できます。

しかし、私は分散した独立したクライアントが並行して要求を行うプログラムに取り組んでいます。

このような場合、最適なソリューションが何であるかははるかに明確ではありません。そして、一般に、問題は決定不可能であるように見えます。120を超えるクライアントが、すべて以前の履歴がなく、同時に最初の要求を行うと、レートを超えます。

しかし、これは個人的なプロジェクトであり、クライアントの使用は散発的（バースト的）であると予想され、私のプロジェクトはこれまで大成功を収めたことがないため、大きな問題になることはないと予想されます。より可能性の高い問題は、少数のクライアントができるだけ早く多くのリクエストを行いたい場合があることです（たとえば、クライアントは、例外的に、初めて起動するときに数千のリクエストを行う必要がある場合があります-可能です2つのクライアントはほぼ同時に起動するため、利用可能な帯域幅を共有するには協力する必要があります）。

上記のすべてを考えると、クライアントが適切にレート制限するための適切なアルゴリズムは何ですか？APIはすべてのクライアントについて、直前のリクエストの総数を返すため、 限定的な連携が可能であることに注意してください。

現在のソリューション

私の現在の解決策（質問が書かれたとき-より良いアプローチが答えとして与えられています）は非常に単純です。各クライアントには、最後の呼び出しが行われた時間と、その呼び出しでAPIによって報告された、最後の1分間に行われた呼び出しの数の記録があります。

呼び出し数が60（制限の半分）未満の場合、クライアントはスロットルしません。これにより、少数のリクエストの高速バーストが可能になります。

それ以外の場合（つまり、以前のリクエストがさらにある場合）、クライアントは（つまり）で作業する必要がある制限レートを計算しperiod = 60 / (120 - number of previous requests)、前の呼び出しと現在の時間とのギャップがその期間（秒単位、60秒単位）を超えるまで待機します。 1分;1分あたり最大120リクエスト）。これにより、レートが効果的に抑制され、単独で動作している場合でも制限を超えないようになります。

しかし、上記には問題があります。注意深く検討すると、多数のリクエストに対して、単一のクライアントが振動し、最大スループットに達しないことがわかります（これは、「最初のバースト」が突然「ウィンドウの外に落ちる」ためであり、一部はアルゴリズムはその履歴を十分に活用していません）。そして、複数のクライアントがある程度協力するでしょうが、それが最適であるとは思えません。

より良いソリューション

クライアントの完全なローカル履歴を使用し、たとえば隠れマルコフモデルを使用して他のクライアントをモデル化するより良いソリューションを想像できます。したがって、各クライアントはAPIレポートを使用して、他の（不明な）クライアントをモデル化し、それに応じてレートを調整します。

また、単一のクライアントのアルゴリズムが、小さなバーストの無制限の動作から、振動を導入することなく多くの要求の最適で制限された動作に段階的に移行することも想像できます。

そのようなアプローチは存在しますか？誰かが実装やリファレンスを提供できますか？誰もがより良いヒューリスティックを考えることができますか？

これはどこかで既知の問題だと思います。どの分野で？待ち行列理論？

また、最適な解決策はなく、実際にうまく機能する伝承/伝統/受け入れられたヒューリスティックがあるかもしれないと推測します（前述のコメントを参照）。私は何を知りたいです...現在、私は既知のネットワークプロトコルで同様の問題を特定するのに苦労しています（もしそうなら、Perlmanはいくつかの美しい解決策を持っていると思います）。

また、コラボレーションを支援するために中央サーバーを必要とするソリューションにも興味があります（プログラムが普及した場合の将来の参照用に）。

免責事項

この質問は、EchoNestを批判することを意図したものではありません。彼らのサービスと使用条件は素晴らしいです。しかし、これをどのように使用するのが最善かを考えれば考えるほど、より複雑で興味深いものになります...

また、各クライアントには、呼び出しの繰り返しを回避するために使用されるローカルキャッシュがあります。

更新

おそらく関連する紙。

4

3 に答える 3

3

上記は機能しましたが、非常にノイズが多く、コードが混乱していました。私は今、より単純なアプローチを使用しています：

  • 電話を掛ける
  • 応答から、制限とカウントに注意してください

  • 計算する

    barrier = now() + 60 / max(1, (limit - count))**greedy
  • 次の呼び出しで、まで待ちますbarrier

考え方は非常に単純です。その分に残っているリクエストの数に比例して、ある程度の時間を待つ必要があります。たとえば、カウントが39で、制限が40の場合、1分間待機します。ただし、カウントがゼロの場合は、すぐにリクエストを行うことができます。パラメータはgreedyトレードオフです。1より大きい場合、「最初の」呼び出しはより迅速に行われますが、制限に達して60秒待機する可能性が高くなります。

これのパフォーマンスは上記のアプローチと同様であり、はるかに堅牢です。上記のアプローチは線形レートを見積もろうとして混乱するため、クライアントが「バースト」している場合に特に適しています。これにより、需要が少ないときにクライアントがいくつかの迅速なリクエストを「盗む」ことができます。

ここにコーディングします。

于 2013-02-09T16:08:08.157 に答える
1

いくつかの実験の後、最も重要なことは、現在の接続レートの上限について可能な限り適切な見積もりを取得することであるように思われます。

各クライアントは、タイムスタンプのキューを使用して、独自の（ローカル）接続レートを追跡できます。接続ごとにタイムスタンプがキューに追加され、1分より古いタイムスタンプは破棄されます。次に、「長期」（1分以上）の平均レートが、最初と最後のタイムスタンプとエントリ数（マイナス1）から求められます。「短期」（瞬間）レートは、最後の2つのリクエストの時間から見つけることができます。上限は、これら2つの値の最大値です。

各クライアントは、（他のクライアントからの）外部接続レートを見積もることもできます。「長期」レートは、サーバーによって報告された直前の「使用済み」接続の数から、（上記のキューからの）ローカル接続の数で修正して求めることができます。「短期」レートは、前回のリクエスト以降の「使用済み」数（ローカル接続の場合はマイナス1）から、時間差でスケーリングして見積もることができます。ここでも、上限（これら2つの値の最大値）が使用されます。

各クライアントは、これら2つのレート（ローカルと外部）を計算し、それらを加算して、サーバーへの接続の合計レートの上限を見積もります。この値は、現在最大値の80％から90％（1分あたり）0.8に設定されている目標レート帯域と比較されます。0.9 * 120

推定レートと目標レートの差から、各クライアントは独自の接続レートを変更します。1.1これは、前のデルタ（最後の接続と前の接続の間の時間）を取得し、それを（レートがターゲットを超える場合）または0.9（レートがターゲットよりも低い場合）でスケーリングすることによって行われます。次に、クライアントは、スケーリングされたデルタが通過するまで（新しい接続が要求された場合はスリープすることにより）、新しい接続の確立を拒否します。

最後に、上記の何も、すべてのクライアントに帯域幅を均等に共有することを強制しません。そこで、ローカルレートの見積もりにさらに10％を追加します。これは、レートが高いクライアントのレートを優先的に過大評価する効果があり、レートを下げる可能性が高くなります。このように、「貪欲な」クライアントは、消費を削減するというわずかに強い圧力を持っています。これは、長期的には、リソースの分散のバランスを保つのに十分であるように見えます。

重要な洞察は次のとおりです。

  • 「長期」と「短期」の見積もりを最大にすることにより、追加のクライアントが起動したときにシステムが保守的（およびより安定的）になります。

  • クライアントの総数は（0または1でない限り）わかりませんが、すべてのクライアントが同じコードを実行するため、相互に「信頼」できます。

  • 上記の場合、使用するレートについて「正確な」計算を行うことはできませんが、グローバルレートに応じて「一定の」補正（この場合は+/- 10％の係数）を行うことができます。

  • クライアント接続頻度の調整は、最後の2つの接続間のデルタに対して行われます（1分間の平均に基づいて調整するのは遅すぎて、振動が発生します）。

  • 貪欲なクライアントにわずかにペナルティを課すことで、バランスの取れた消費を実現できます。

（限定された）実験では、これはかなりうまく機能します（複数のクライアントが同時に開始するという最悪の場合でも）。主な欠点は次のとおりです。（1）最初の「バースト」が許可されない（サーバーにクライアントが少なく、クライアントに要求が少ない場合、スループットが向上します）。（2）システムはまだ約1分以上振動します（以下を参照）。（3）多数のクライアントを処理する場合（最悪の場合、たとえば、すべてを一度に開始する場合）、より大きなゲイン（たとえば、10％ではなく20％の修正）が必要になり、システムの安定性が低下する傾向があります。

プロット

（テスト）サーバーによって報告された「使用済み」量。時間に対してプロットされます（Unixエポック）。これは4つのクライアント（色付き）用であり、すべてが可能な限り多くのデータを消費しようとしています。

振動は通常のソースから発生します-補正は信号を遅らせます。それらは、（1）レートの上限を使用する（瞬時値から長期レートを予測する）こと、および（2）ターゲット帯域を使用することによって減衰されます。これが、制御理論を理解している人からの回答をいただければ幸いです...

ローカルレートと外部レートを別々に見積もることが重要であるかどうかは私にはわかりませんが（一方の短期レートが高く、もう一方の長期レートが高い場合に役立つ可能性があります）、それを削除しても状況が改善されるとは思えません。

結論として、この種のアプローチでは、これはすべて私が期待したとおりです。これは一種の動作ですが、単純なフィードバックベースのアプローチであるため、限られた範囲のパラメーター内でのみ安定します。どのような代替案が可能かわかりません。

于 2012-08-28T09:32:41.387 に答える
0

Echonest APIを使用しているので、すべてのAPI呼び出しで返されるレート制限ヘッダーを利用してみませんか？

通常、1分あたり120件のリクエストがあります。APIの消費を自己調整するのに役立つ3つのヘッダーがあります。

X-Ratelimit-Used
X-Ratelimit-Remaining
X-Ratelimit-Limit

**（「Ratelimit」の小文字の「ell」に注意してください。ドキュメントでは、大文字にする必要があると思われますが、実際には小文字です。）

これらのカウントは、APIキーを使用して他のプロセスによって行われた呼び出しを考慮しています。

かなりきちんとしていますね さて、こすりがあるのではないかと思います...

その1分あたり120リクエストは、実際には上限です。あなたはそれを当てにすることはできません。ドキュメントには、システムの負荷に応じて値が変動する可能性があると記載されています。私が行ったいくつかの呼び出しでは40程度の低さであり、場合によってはゼロを下回ることもあります（これが、echonest APIのバグであったことを本当に願っています！）

使用できるアプローチの1つは、使用率（使用量を制限で割った値）が特定のしきい値に達したら、速度を落とすことです。ただし、次の呼び出しで、「使用済み」が「制限」よりも大きくなるように、ダウンロードの制限が大幅に調整されている可能性があることに注意してください。

これは、ある時点までうまく機能します。Echonestは予測可能なマナーで制限を調整しないため、実際には400を回避することは困難です。

これが私が役立つと思ったいくつかのリンクです：

http://blog.echonest.com/post/15242456852/managing-your-api-rate-limit http://developer.echonest.com/docs/v4/#rate-limits

于 2013-03-01T20:16:12.973 に答える