学習遅延：キューイング理論

時間の経過に伴う待ち時間のテーマは、Yandexのさまざまなシステムで興味深いものになります。 これは、これらのシステムにサービス保証が表示されるときに発生します。 明らかに、ユーザーに何らかの機会を約束するだけでなく、妥当な応答時間で受信を保証することも重要であるという事実です。 もちろん、応答時間の「合理性」はシステムごとに大きく異なりますが、すべてのシステムで遅延が現れる基本原則は共通しており、詳細から切り離して考えることができます。



私の名前はSergey Trifonovです。YandexのReal-Time Map Reduceのチームで働いています。 2番目および1秒未満の応答時間を備えたリアルタイムデータフロー処理用のプラットフォームを開発しています。 このプラットフォームは内部ユーザーが利用でき、常に受信するデータストリームでアプリケーションコードを実行できます。 過去100年および10年のレイテンシ分析のトピックについて、人類の基本概念の概要を簡単に説明します。次に、キューイング理論を使用してレイテンシについて正確に学習できることを理解しようとします。



待ち時間の現象は、電話通信ネットワークである待ち行列システムの出現に関連して、私の知る限り体系的に調査され始めました。 キューイング理論は、1909年のA.K.アーランの研究から始まり、ポアソン分布がランダムな電話トラフィックに適用可能であることを示しました。 アーランは、電話ネットワークを設計するために何十年も使用されてきた理論を開発しました。 この理論により、サービス拒否の確率を判断できます。 回線交換チャネルを備えた電話ネットワークでは、すべてのチャネルがビジーであり、コールを発信できない場合に障害が発生しました。 このイベントの確率を制御する必要がありました。 たとえば、すべての通話の95％が処理されることを保証したかったのです。 Erlangの式を使用すると、通話の時間と数がわかっている場合に、この保証を満たすために必要なサーバーの数を決定できます。 実際、このタスクは品質保証に過ぎず、今日でも人々は同様の問題を解決しています。 しかし、システムははるかに複雑になっています。 キューイング理論の主な問題は、ほとんどの施設で教えられておらず、通常のM / M / 1キュー以外の質問を理解している人はほとんどいないことです（ 以下の表記を参照 ）が、人生はこのシステムよりもはるかに複雑であることはよく知られています。 したがって、M / M / 1をバイパスして、最も興味深いものにすぐに行くことを提案します。

平均値

システム内の確率分布に関する完全な知識を得ようとせず、より単純な質問に焦点を合わせれば、興味深く有用な結果を得ることができます。 最も有名なものは、もちろん、 リトルの定理です。 任意の入力ストリーム、任意の複雑さの内部デバイス、および内部の任意のスケジューラーを備えたシステムに適用できます。 唯一の要件は、システムが安定していることです。平均応答時間とキューの長さが存在する必要があり、それらは単純な式で接続されます

$$

$$L = \ラムダW$$

どこで $$$L$ -システムの対象となる部分のリクエストの平均時間数[pcs]、 $$$W$ -要求がシステムのこの部分を通過する平均時間[s]、 $$$\ラムダ$ -システムでのリクエストの受信速度[pcs / s]。 定理の長所は、キュー、エグゼキューター、キュー+エグゼキューター、またはネットワーク全体に適用できることです。 多くの場合、この定理はおおよそ次のように使用されます。「1Gbit / sのストリームが私たちに向かって流れており、平均応答時間を測定しました。これは10ミリ秒です。したがって、平均1.25 MBが飛行しています。」 したがって、この計算は正しくありません。 より正確には、すべてのリクエストのサイズがバイト単位で同じ場合にのみ当てはまります。 リトルの定理は、クエリをバイト単位ではなく小片単位でカウントします。

リトルの定理の使用方法

数学では、多くの場合、真の洞察を得るために証拠を研究する必要があります。 これはまさにその通りです。 リトルの定理は非常に優れているので、ここで証明のスケッチを示します。 着信トラフィックは機能によって記述されます $$$A（t）$ -その時点でログインしているリクエストの数 $$$t$ 。 同様に $$$D（t）$ -その時点でログアウトされたリクエストの数 $$$t$ 。 要求のエントリ（終了）の瞬間は、最後のバイトの受信（送信）の瞬間と見なされます。 システムの境界はこれらの時点でのみ決定されるため、定理は広く適用できます。 これらの関数のグラフを同じ軸に描くと、簡単にわかります $$$A（t）-D（t）$ 時刻tにおけるシステム内のリクエストの数です。 $$$W_n$ n番目の要求の応答時間です。



定理は1961年にのみ正式に証明されましたが、その関係自体はそのずっと前から知られていました。



実際、システム内で要求を並べ替えることができる場合、すべてが少し複雑になります。そのため、簡単にするために、これは起こらないと仮定します。 この場合も定理は真実ですが。 次に、グラフ間の面積を計算しましょう。 これを行うには2つの方法があります。 まず、列によると-積分が通常考えるように。 この場合、被積分関数はキューのサイズであることがわかります。 第二に、行ごとに-すべてのリクエストのレイテンシを単純に加算します。 両方の計算が同じ面積を与えることは明らかであるため、それらは等しくなります。 この等式の両方の部分を、面積を計算した時間Δtで割ると、左側に平均キュー長があります。 $$$L$ （平均の定義による）。 右側には少し注意が必要です。 分子と分母に別の数のクエリNを追加する必要があり、成功します。

$$

$$\ frac {\ sum W_i} {\ Delta t} = \ frac {\ sum W_i} {N} \ frac {N} {\ Delta t} = W \ lambda$$

十分に大きいΔtまたは1つの雇用期間を考慮すると、端の質問は削除され、定理は証明済みと見なされます。



証明では、確率の分布を使用しなかったと言うことが重要です。 実際、リトルの定理は決定論的な法則です！ このような法律は、操作法のキューイング理論で呼ばれています。 これらは、システムの任意の部分およびさまざまなランダム変数の任意の分布に適用できます。 これらの法則は、ネットワークの平均値を分析するために使用できるコンストラクターを形成します。 欠点は、それらがすべて平均にのみ適用され、分布に関する知識を提供しないことです。



リトルの定理をバイトに適用できない理由の質問に戻ると、 $$$A（t）$ そして $$$D（t）$ 現在、それらは小片ではなくバイト単位で測定されます。 次に、同様の引数を実行すると、代わりに $$$W$ 奇妙なことは、合計バイト数で割った領域です。 それはまだ数秒ですが、それはより大きなリクエストがより多くの重みを取得する少しの加重平均レイテンシです。 この値は、バイトの平均レイテンシーと呼ぶことができます-ピースをバイトで置き換えたため、一般に論理的ですが、リクエストのレイテンシーではありません。



リトルの定理によると、特定の要求のストリームでは、システム内の応答時間と要求の数は比例します。 すべての要求が同じように見える場合、電力を増加させなければ平均応答時間を短縮できません。 クエリのサイズが事前にわかっている場合は、内部の順序を変更して、間の領域を減らすことができます $$$A（t）$ そして $$$D（t）$ したがって、平均システム応答時間。 この考え方を続けると、最短処理時間アルゴリズムと最短残り処理時間アルゴリズムは、それぞれ混雑する可能性なしに、1台のサーバーの最小平均応答時間を与えることを証明できます。 しかし、副作用があります-大きなリクエストは無期限に処理されないかもしれません。 この現象は「飢v」と呼ばれ、公平性計画の概念と密接に関連しています。これは、以前のスケジューリングの投稿である神話と現実から学ぶことができます。



リトルの法則の理解に関連するもう1つの一般的なトラップがあります。 ユーザーリクエストに対応するシングルスレッドサーバーがあります。 何らかの方法でL-このサーバーへのキュー内のリクエストの平均数、S-サーバーが1つのリクエストを処理した平均時間を測定したとします。 次に、新しい着信リクエストを検討します。 平均して、彼は彼の前にLクエリを見る。 それぞれにサービスを提供するには、平均してS秒かかります。 平均待ち時間は $$$W = L S$ 。 しかし、定理により、 $$$W = L / \ラムダ$ 。 式を同等にすると、ナンセンスがわかります。 $$$S = 1 / \ラムダ$ 。 この推論の何が問題になっていますか？

1. あなたの目を引く最初のもの：定理による応答時間はSに依存しません。実際、もちろん、依存します。 サーバーの速度が速いほど、キューの長さが短くなり、応答時間が短くなるということは、平均キューの長さがすでにこれを考慮しているということです。
2. キューが永久に蓄積されるのではなく、定期的にリセットされるシステムを検討します。 これは、サーバーの使用率が100％未満であり、すべての着信要求をスキップし、これらの要求が到着したのと同じ平均速度で、つまり単一の要求を処理するのに平均してS秒ではなく、 $$$1 / \ラムダ$ 単にリクエストを処理しない場合があるためです。 事実、損失のない安定したオープンシステムでは、スループットはサーバーの速度に依存せず、入力ストリームによってのみ決定されます。
3. 着信リクエストがシステム内でリクエストの時間平均数を認識するという仮定は、常に正しいとは限りません。 反例：着信リクエストは定期的に送信され、次のリクエストが到着する前に各リクエストを処理します。 リアルタイムシステムの典型的な状況。 着信要求は常にシステム内でゼロの要求を見ますが、平均してシステムには明らかにゼロ以上の要求があります。 要求が完全にランダムな時間に来る場合、実際には「要求の平均数を見る」 。
   
   
   
   
   
   
   
   
   
   
4. 一定の確率で、サーバーに「拡張」する必要がある要求が既に1つある可能性があることを考慮しませんでした。 一般的な場合、「アフターサービス」の平均時間はサービスの最初の時間とは異なり、時には逆説的に 、はるかに長くなることがあります。 最後にこの問題に戻り、マイクロバーストについて説明しますので、ご期待ください。

したがって、リトルの定理は、大小のシステム、キュー、サーバー、および単一の処理スレッドに適用できます。 しかし、これらすべての場合、リクエストは通常​​何らかの方法で分類されます。 異なるユーザーのリクエスト、異なる優先度のリクエスト、異なる場所からのリクエスト、または異なるタイプのリクエスト。 この場合、クラスによって集約された情報は面白くありません。 はい、混合リクエストの平均数とそれらすべての平均応答時間は再び比例します。 しかし、特定のクラスのリクエストの平均応答時間を知りたい場合はどうでしょうか？ 驚くべきことに、リトルの定理は特定のクラスのクエリに適用できます。 この場合、次のように取る必要があります $$$\ラムダ$ すべてではなく、このクラスが要求する割合。 として $$$L$ そして $$$W$ -システムの調査対象部分におけるこのクラスのリクエストの数と滞留時間の平均値。

オープンシステムとクローズドシステム

閉じたシステムの場合、結論に至る「間違った」推論の行が存在することは注目に値します $$$S = 1 / \ラムダ$ 本当であることが判明。 クローズドシステムとは、リクエストが外部から送信されず、外部に送信されず、内部に循環するシステムです。 または、フィードバックシステム：リクエストがシステムを離れるとすぐに、新しいリクエストが実行されます。 これらのシステムも重要です。なぜなら、開いているシステムはすべて、閉じたシステムに没頭していると見なすことができるからです。 たとえば、サイトは、要求が絶えず注がれ、処理され、取り下げられるオープンシステムと考えることができます。逆に、サイトの視聴者全員がいるクローズドシステムと考えることもできます。 その後、彼らは通常、ユーザーの数は固定されていると言い、彼らはリクエストへの応答を待つか「考える」。彼らは自分のページを手に入れ、リンクをクリックするまで。 思考時間が常にゼロである場合、システムはバッチシステムとも呼ばれます。



閉じたシステムのリトルの法則は、外部からの到着の速度が $$$\ラムダ$ （それらは閉じたシステムではありません）システム帯域幅に置き換えます。 上記のシングルスレッドサーバーをバッチシステムでラップすると、次のようになります。 $$$S = 1 / \ラムダ$ そして100％リサイクル。 多くの場合、このようなシステムの外観は予期しない結果をもたらします。 90年代には、指数関数的分布以外の分布の研究に弾みをつけた単一のシステムとして、ユーザーと一緒にインターネットを考慮するだけでした。 分布についてさらに説明しますが、ここでは、ほぼすべての場所が指数関数的であると考えられていたことに注意してください。 ただし、実際に重要なすべての分布が同じように長いテールを持つわけではなく、分布のテールの知識を試すことができることが判明しました。 しかし、今のところ、平均値に戻りましょう。

相対論的効果

オープンシステム、つまり複雑なネットワークまたは単純なシングルスレッドサーバーがあるとします-それは重要ではありません。 要求の到着を2倍にし、すべてのシステムコンポーネントの処理能力を2倍にするなど、処理を半分に高速化するとどうなりますか？ 使用率、スループット、システム内の平均リクエスト数、および平均応答時間はどのように変化しますか？ シングルスレッドサーバーの場合、数式を取得して「額に」適用して結果を得ることができますが、任意のネットワークで何をするのでしょうか。 直感的な解決策は次のとおりです。 時間が2倍になったと仮定すると、「高速化された参照システム」では、サーバーの速度と要求の流れは変わらないように見えました。 したがって、加速時間のすべてのパラメーターは以前と同じ値になります。 言い換えれば、システムのすべての「可動部」の加速度は、時計の加速度に相当します。 次に、通常の時間で値をシステムに変換します。 無次元の数量（使用率と平均リクエスト数）は変わりません。 次元に1次の時間因子が含まれる値は、比例して変化します。 [requests / s]のスループットは2倍になり、応答と待機時間[s]は半分になります。



この結果は、次の2つの方法で解釈できます。

1. k回加速されたシステムは、タスクフローをk回以上消化し、平均応答時間をk回短縮できます。
2. パワーは変化しなかったが、単純にタスクのサイズがk倍減少したと言えます。 同じ負荷をシステムに送信していますが、小さな断片で切断されていることがわかります。 そして...ああ奇跡！ 平均応答時間が短縮されました！

繰り返しますが、これは単純なサーバーだけでなく、幅広いクラスのシステムに当てはまることに注意してください。 実用的な観点からは、2つの問題のみがあります。

1. システムのすべての部分を簡単に加速できるわけではありません。 一部に影響を与えることはできません。 たとえば、光の速度。
2. すべてのタスクが1ビット未満の部分で情報を送信する方法を学習していないため、すべてのタスクをますます小さなものに分割できるわけではありません。

限界への移行を検討してください。 同じオープンシステムで、解釈番号2を想定します。各着信要求を半分に分割します。 応答時間も半分に分割されます。 分割を何度も繰り返します。 そして、システム内の何も変更する必要さえありません。 着信要求を十分に多数のパーツに分割するだけで、応答時間を任意に短くすることができます。 限界では、クエリの代わりに「クエリフルイド」を取得し、それをサーバーでフィルタリングすると言うことができます。 これは、いわゆる流体モデルであり、単純化された分析に非常に便利なツールです。 しかし、なぜ応答時間がゼロなのでしょうか？ 何が悪かったのですか？ レイテンシを考慮しなかったのはどこですか？ 私たちは光の速度だけを考慮しなかったことがわかります。倍にすることはできません。 ネットワークチャネルでの伝播時間は変更できず、我慢できます。 実際、ネットワークを介した伝送には、伝送時間と伝播時間の2つの要素が含まれます。 1つ目は、電力（チャネル幅）を増やすか、パケットのサイズを小さくすることで加速でき、2つ目は影響を与えるのが非常に困難です。 私たちの「液体モデル」では、液体を蓄積するためのリザーバーはありませんでした。つまり、伝播時間がゼロではない一定のネットワークチャネルです。 ところで、それらを「液体モデル」に追加すると、遅延は伝播時間の合計によって決定され、ノード内のキューは空のままになります。 キューは、パケットサイズと入力ストリームの変動性（読み取りバースト）のみに依存します。



レイテンシーに関して言えば、ストリーム計算では対応できず、デバイスを破棄してもすべてが解決されるわけではありません。 リクエストのサイズを考慮し、配信時間を忘れないようにする必要があります。配信時間はキューイング理論ではしばしば無視されますが、計算に追加することはまったく難しくありません。

分布

キューイングの理由は何ですか？ 明らかに、システムには十分な容量がなく、過剰な要求が蓄積されていますか？ 本当じゃない！ キューは、十分なリソースがあるシステムでも発生します。 十分な容量がない場合、理論家が言うように、システムは安定していません。 キューイングには2つの主な理由があります。要求の不規則性と要求サイズの変動性です。 これらの理由の両方が排除された例、つまり、同じサイズのリクエストが厳密に定期的に来るリアルタイムシステムについては、すでに検討しました。 キューは形成されません。 平均キュー時間はゼロです。 この動作を実現することは、不可能ではないにしても非常に困難であるため、キューが形成されることは明らかです。 キューイング理論は、両方の原因が本質的にランダムであり、いくつかのランダム変数によって説明されるという仮定に基づいています。



使用されるさまざまなシステムを説明するには ケンドール表記 A / S / k / K、ここでAはリクエスト間の時間の分布、Sはリクエストサイズの分布、kはサーバーの数、Kはシステム内の同時リクエスト数の制限です（制限がない場合は省略）。 たとえば、既知のM / M / 1は次のように復号化されます。最初のM（MarkovianまたはMemoryless）は、タスクのポアソンストリームがシステムに供給されることを意味します。 読み取り：メッセージは一定の平均速度でランダムに到着します $$$\ラムダ$ 1秒あたりの要求-放射性崩壊のように-または、より正式には、2つの隣接するイベント間の時間には指数分布があります。 2番目のMは、これらのメッセージのサービスにも指数分布があり、平均で1秒あたりのμ要求が処理されることを意味します。 最後に、最後のユニットは、サービスが単一のサーバーによって実行されることを示します。 表記の4番目の部分が欠落しているため、キューは制限されません。 この表記法で使用される文字はかなり奇妙に選択されています。Gは任意の分布（いいえ、ガウスではない、と思うかもしれません）、Dは決定論的です。 リアルタイムシステム-D / D / 1。 アーランが1909年に決定した最初のキューイングシステムは、M / D / 1でした。 しかし、分析的にまだ解決されていないシステムは、k> 1の場合M / G / kであり、M / G / 1の解は1930年に発見されました。

なぜ指数分布を使用するのですか？

主な理由は、後で説明するように、数学者がすでに多くのことを知っているマルコフ連鎖を使用できるようになるため、ほとんどすべてのキューの問題を解決可能にするためです。 指数分布には、メモリがないため、理論に適した多くの特性があります。 ここでは、このプロパティの定義は行いません;開発者にとっては、 失敗率による説明の方が役立ちます。 デバイスがあり、実際にはそのようなデバイスの寿命の分布を知っていると仮定します：寿命の初めに故障することが多く、その後比較的まれに故障し、保証期間の終了後に再び故障し始めることがよくあります。 正式には、この情報は正確に故障率関数に含まれており、分布に非常に単純に関連しています。 実際、これは、デバイスがある程度まで生き残っているという事実を考慮した「整合した」確率密度です。 実用的な観点から、これはまさに私たちが興味を持っているものです。つまり、デバイスがすでに稼働している時間の関数としてのデバイスの故障率です。 たとえば、故障率が一定である場合、つまり、デバイスの故障の頻度が動作時間に依存せず、故障が一定の頻度でランダムに発生する場合、デバイスの寿命の分布は指数関数的です。 この場合、デバイスの動作時間を予測するために、デバイスが使用されていた時間、デバイスの種類、その他を知る必要はありません。 これが「メモリ不足」です。

短い尾と長い尾

故障率はどの分布でも計算できます。 キューイング理論において、クエリの実行時間を分散します。 失敗率は、すでに実行されている量に基づいて、要求が実行される時間を示します。 失敗率が増加している場合、リクエストが完了する時間が長いほど、すぐに終了する可能性が高くなります。 失敗率が低下している場合、リクエストの実行時間が長いほど、実行時間が長くなる可能性が高くなります。 これら2つのオプションのどちらが、コンピューティングシステム、データベース、およびソフトウェアとハ​​ードウェアに関連する他のものに最も典型的であると思いますか？ そもそも、なぜこれがさらに重要なのですか？ 日常生活の例。 , , - . ? , — . ( failure rate) . « » .



, , failure rate, , , unix- . , .



RTMR , . LWTrace - . . , . , $$$\mathbf{P}\{S>x\}$ . , failure rate , , : .











$$$\mathbf{P}\{S>x\} = x^{-a}$ , — . , « », 80/20: , . . , . , RTMR -, , . パラメータ $$$a=1.16$ , 80/20: 20% 80% .

, . . , , , - . , — . « » , « » — . : , ? , ( , ), . , 0 . , , $$$\mu N_1$ $$$\lambda N_0$ 。 , , — . . , . M/M/1 $$$\mathbf{P}\{Q=i\} = (1 - \rho) \rho^i$ どこで $$$\rho = \lambda / \mu$ — . 物語の終わり。 , , , .



, , , , , . — . , , — failure rate.



, , . — . , . , , $$$\mathbf{P}\{response\_time > t\} = e^{-(\mu-\lambda)t}$ $$$1/(\mu-\lambda)$ 。

, , . , . , -, , . . , , , — . , , . , , . , , .

, , . . , . , . M/M/k/k M/M/k, . , . , , , , . M/M/k/k , , , , . , .



M/M/k , , , — . , M/M/1. , , , . . M/M/k/k M/M/k, B . , , , square root staffing rule. , M/M/k - λ . , . : , ? , ? , . , : ( ) , . — , . , M/M/1 , « » $$$\mu - \lambda$ . , , : $$$2\mu - 2\lambda$ 。 , , M/M/k . , « », . « » , : .



, , . , — M/M/k-. , , , — M/M/k, M/M/k , , . , , FIFO-. , , . , 10 , , . : .

, M/M/k, , . : . , , , . , M/M/k, . , , .



— . — . , , , , product-form solution . , — . . :

1. . , , . , , « »: , № 1, № 2 , № 2, № 1 № 3 . , 100%- .
2. . , , . , , . . — . , , , , .
3. .

ジャクソンネットワークの例。



フィードバックが存在する場合、ポアソンストリームは取得されないことに注意してください。これは、フローが相互に依存していることが判明したためです。 フィードバックノードからの出口では、非ポアソンストリームも取得されるため、すべてのフローが非ポアソンになります。 ただし、驚くべきことに、上記の制限が満たされている場合、これらの非ポアソンフローはすべて、ポアソンフロー（ああ、この確率理論）とまったく同じように動作することがわかります。 そして、再び製品形式のソリューションを取得します。 このようなネットワークはJacksonネットワークと呼ばれ、フィードバックを提供できるため、任意のサーバーに複数回アクセスできます。 より多くの自由が許可されている他のネットワークもありますが、結果として、ネットワークに関するキューイング理論の重要な分析的成果はすべて、入力および製品形式のソリューションでポアソンフローを含み、これはこの理論によって批判され、90年代に導かれました他の理論の開発、実際に配布が必要なものとそれらをどのように扱うかの研究。



ジャクソンネットワークのこの理論全体の重要なアプリケーションは、IPネットワークおよびATMネットワークでのパケットモデリングです。 モデルは非常に適切です。サービス時間はパケットがチャネルに送信された時間に対応するため、パケットサイズはあまり変化せず、パケット自体に依存せず、チャネル幅のみに依存します。 ランダムな送信時間はワイルドに聞こえますが、実際にはそれほど大きな変動性はありません。 さらに、確定的なサービス時間を備えたネットワークでは、遅延を同様のジャクソンネットワークより長くすることはできないため、このようなネットワークを安全に使用して上から応答時間を推定できることがわかります。

非指数分布

説明したすべての結果は指数分布に関連していましたが、実際の分布は異なることも言及しました。 この理論全体はまったく役に立たないという感じがあります。 これは完全に真実ではありません。 さらに、他の分布をこの数学的装置に統合する方法があります。さらに、実際には任意の分布を統合する方法がありますが、コストがかかります。 いくつかの興味深いケースを除いて、明示的な形式でソリューションを取得する機会が失われ、製品形式のソリューションが失われ、コンストラクターで失われます。各問題は、マルコフ連鎖を使用してゼロから完全に解決する必要があります。 理論上、これは大きな問題ですが、実際には単に数値的手法の適用を意味し、はるかに複雑で現実に近い問題を解決することを可能にします。

位相法

アイデアはシンプルです。 マルコフ連鎖では、1つの状態内にメモリを保持することはできません。したがって、すべての遷移は、2つの遷移間の時間の指数分布でランダムでなければなりません。 しかし、状態が複数のサブ状態に分割されている場合はどうでしょうか？ 構造全体をマルコフ連鎖のままにしたい場合、サブステート間の遷移はまだ指数分布である必要があります。本当にそうしたいのは、そのような連鎖を解く方法を知っているからです。 サブステートは、直列に配置されている場合、多くの場合フェーズと呼ばれ、パーティションプロセスはフェーズメソッドと呼ばれます。



最も単純な例。 リクエストはいくつかのフェーズで処理されます。たとえば、最初にデータベースから必要なデータを読み取り、次に計算を実行してから、結果をデータベースに書き込みます。 これらの3つのステージがすべて同じ時間の指数分布を持っているとします。 3つのフェーズすべての通過時間を合わせてどの分布がありますか？ これはErlangの配布です。











しかし、多数の短い同一フェーズを作成するとどうなりますか？ 限界では、決定論的分布を取得します。 つまり、チェーンを構築することで、分布のばらつきを減らすことができます。



ばらつきを増やすことは可能ですか？ 簡単です。 フェーズチェーンの代わりに、代替カテゴリを使用して、それらの1つをランダムに選択します。 例。 ほとんどすべてのリクエストは迅速に実行されますが、巨大なリクエストが届く可能性はわずかですが、時間がかかります。 このような分布では、故障率が低下します。 長く待つほど、リクエストが2番目のカテゴリに分類される可能性が高くなります。











相の方法の開発を続けると、理論家は、任意の非負の分布に正確にアプローチできる分布のクラスがあることを発見しました！ Coxian分布は位相法によって構築されます。すべての段階を完了する必要はありません。各段階の完了の可能性がある程度あります。











この種の分布は、非ポアソン入力ストリームの生成と非指数サービス時間の作成の両方に使用できます。 たとえば、サービス時間のアーラン分布を持つM / E2 / 1システムのマルコフ連鎖を次に示します。 状態は数値のペア（n、s）によって決定されます。nはキューの長さ、sはサーバーが配置されているステージの番号（1番目または2番目）です。 nとsのすべての組み合わせが可能です。 着信メッセージはnのみを変更し、フェーズが完了すると、2番目のフェーズの完了後に交互にキューの長さを減らします。

マイクロバーストがあります！

容量の半分でロードされたシステムの速度は低下しますか？ 最初の被験者として、M / G / 1を準備します。 指定：入口でのポアソン流とサービス時間の任意の分布。 システム全体での単一のリクエストのパスを考慮してください。 ランダムに着信する着信リクエストは、キューの前にあるリクエストの平均時間数を確認します $$$\ mathbf {E} [N_Q]$ 。 それぞれの平均処理時間 $$$\ mathbf {E} [S]$ 。 処分に等しい確率で $$$\ rho$ 、サーバーには別のリクエストがあり、最初に時間内に「サービス」する必要があります $$$\ mathbf {E} [S_e]$ 。 まとめると、キューでの合計待機時間は $$$\ mathbf {E} [T_Q] = \ mathbf {E} [N_Q] \ mathbf {E} [S] + \ rho \ mathbf {E} [S_e]$ 。 リトルの定理により $$$\ mathbf {E} [N_Q] = \ lambda \ mathbf {E} [T_Q]$ ; 組み合わせると、次のようになります。

$$

$$\ mathbf {E} [T_Q] = \ frac {\ rho} {1- \ rho} \ mathbf {E} [S_e]$$

つまり、キューでの待機時間は2つの要因によって決まります。 1つ目はサーバー使用率の影響で、2つ目はアフターサービス時間の平均です。 2番目の要因を考慮してください。 ある時点で到着するリクエスト $$$t$ 、アフターケアに時間がかかることがわかります $$$S_e（t）$ 。











平均時間 $$$\ mathbf {E} [S_e]$ 関数の平均値によって決定されます $$$S_e（t）$ 、つまり、三角形の面積を合計時間で割ったものです。 1つの「中間」三角形に制限できることは明らかです。 $$$\ mathbf {E} [S_e] = \ mathbf {E} [S ^ 2] / 2 \ mathbf {E} [S]$ 。 これはかなり予想外です。 アフターサービス時間は、サービス時間の平均値だけでなく、その変動性によっても決まることがわかりました。 説明は簡単です。 長い間隔に陥る確率 $$$S$ さらに、実際には、この間隔の期間Sに比例します。 これは有名な待機時間のパラドックス、または検査のパラドックスを説明しています。 しかし、M / G / 1に戻ります。 取得したすべてを組み合わせて、可変性を使用して書き換える場合 $$$C ^ 2_S = \ mathbf {E} [S] / \ mathbf {E} [S] ^ 2$ よく知られているPollaczek-Khinchine式を取得します。

$$

$$\ mathbf {E} [T_Q] = \ frac {\ rho} {1- \ rho} \ frac {\ mathbf {E} [S]} {2}（C ^ 2_S + 1）$$

証拠があなたを退屈させたならば、それが実際にその適用の結果を喜ばせることを願っています。 RTMRでサービス時間データを既に調べました。 ロングテールは、非常に大きなばらつきで発生します。この場合 $$$C ^ 2_S = 381$ 。 ご覧のとおり、これは $$$C ^ 2_S = 1$ 指数分布の場合。 平均して、すべてが超高速です： $$$\ mathbf {E} [S] = 263.792μs$ 。 ここで、RTMRがM / G / 1システムによってモデル化され、システムに大きな負荷がかからないようにします。 $$$\ rho = 0.5$ 。 式に代入すると、次のようになります $$$\ mathbf {E} [T_Q] = 1 *（381 + 1）/ 2 * 263.792μs= 50 ms$ 。 マイクロバーストにより、このような高速で十分に活用されていないシステムであっても、平均して不快なシステムに変わる可能性があります。 50ミリ秒の間、ハードドライブに6回アクセスできます。運が良ければ、別の大陸のデータセンターにもアクセスできます。 ちなみに、G / G / 1の場合、着信トラフィックの変動性を考慮した近似があります。代わりに、まったく同じに見えます $$$C ^ 2_S + 1$ それは両方の品種の合計です $$$C ^ 2_S + C ^ 2_A$ 。 複数のサーバーの場合、状況は改善されますが、複数のサーバーの影響は最初の要因のみに影響します。 変動の影響は残ります： $$$\ mathbf {E} [T_Q] ^ {G / G / k}≈\ mathbf {E} [T_Q] ^ {M / M / k}（C ^ 2_S + C ^ 2_A）/ 2$ 。



マイクロバーストはどのように見えますか？ スレッドプールに関して、これらは、リサイクルスケジュールに表示されないほど高速に処理され、自身の背後にキューを作成してプールの応答時間に影響を与えるほど遅く処理されるタスクです。 理論的な観点から、これらはディストリビューションの末尾からの巨大なクエリです。 10個のスレッドのプールがあり、15秒ごとに収集される稼働時間とダウンタイムのメトリックに基づいて構築されたリサイクルスケジュールを見てみましょう。 まず、1つのスレッドがまったくハングしていることや、10のスレッドすべてが1秒間大きなタスクを同時に実行した後、14秒間何もしなかったことに気付かない場合があります。 15秒の解像度では、使用率が最大100％に跳ね返って0％に戻り、応答時間が低下します。 たとえば、これはマイクロバーストのように見える場合があります。これは、顕微鏡で見ると、6つのスレッドのプールで15秒ごとに発生します。











顕微鏡として、プロセッサシステムまでのイベント（要求の受信と完了）の時間を記録するトレースシステムが使用されます。



具体的には、このような状況に対処するために、RTMRはSelfPingメカニズムを使用します。これは、キュー内の待機時間を測定するためだけに、厳密に定期的（10ミリ秒ごと）に小さなタスクをスレッドプールに送信します。 最悪の場合、この測定に10ミリ秒の期間が追加され、ウィンドウで最大15秒が取られます。 したがって、ウィンドウの最大遅延について上記から推定値を取得します。 はい、応答時間が10ミリ秒未満の場合、実際の状況は表示されませんが、この場合、すべてが正常であると仮定できます-単一のマイクロバーストはありません。 しかし、この追加のセルフpingアクティビティは、厳密に制限された量のCPUを消費します。 このメカニズムは、普遍的で非侵襲的であるという点で便利です。スレッドプールのコードまたはその中で実行されるタスクのコードを変更する必要はありません。 私が強調するのは、測定されるのはまさに最悪のケースであり、パーセンタイルと比較して非常に便利で直感的なことです。 メカニズムは、別の同様の状況も検出します。多数の完全に通常の要求の同時到着です。 15秒のリサイクルスケジュールで問題を確認できるほど多くない場合は、これもマイクロバーストと見なすことができます。



さて、SelfPingが何か不適切なことが起こっていることを示したらどうなるでしょうか？ 有罪を見つける方法は？ これを行うには、LWTraceで既に述べたトレースを使用します。 問題のあるマシンに移動し、監視を通じて、目的のスレッドプール内のすべてのタスクを監視し、遅いタスクのみをメモリに保存するトレースを実行します。 その後、トップ100のスロートラックを確認できます。 短い調査の後、トレースをオフにします。 加害者を検索する他のすべての方法は適切ではありません。スレッドプールのすべてのタスクのログを書き込むことは不可能です。 また、すべてのタスクのトラックを収集する必要があるため、遅いタスクのみを作成することも最適なソリューションではありません。これも費用がかかります。 難しいタスクはあまりにもまれなのでプロファイルに表示されないため、perfを使用したプロファイリングは役に立ちません。

サービス時間分布の独立性

まだ使用していない「自由度」がもう1つあります。 着信ストリームとリクエストのサイズ、異なるサーバー数についても説明しましたが、スケジューラについてはまだ話していません。 すべての例にはFIFO処理が含まれています。 既に述べたように、スケジューリングはシステムの応答時間に実際に影響し、適切なスケジューラーはレイテンシーを大幅に改善できます（SPTおよびSRPTアルゴリズム）。 しかし、計画はキューイング理論の非常に高度なトピックです。 おそらく、この理論はプランナーの研究にはあまり適していませんが、プランナーを使用して確率システムに関する答えを与え、平均値を計算できる唯一の理論です。 「最悪の場合」の計画について多くのことを理解することを可能にする他の理論がありますが、それらについては別の機会に話します。



ここで、一般的なルールの興味深い例外を見てみましょう。まだネットワークの製品形式のソリューションを取得できており、便利なコンストラクターを作成できます。 1つのノードM / Cox / 1 / PSから始めましょう。 ポアソン入力ストリーム、サービス時間のほぼ任意の分布（Coxian分布）および公平なスケジューラー（プロセッサ共有）、すべての要求を同時に処理しますが、現在の数に反比例する速度です。 そのようなシステムはどこにありますか？ たとえば、これはオペレーティングシステムで公平なプロセススケジューラが機能する方法です。 一見複雑なシステムのように見えるかもしれませんが、対応するマルコフ連鎖を構築して（フェーズメソッドのセクションを参照）、キュー長の分布がM / M / 1 / FIFOシステムを正確に繰り返すことがわかります。平均値は同じですが、指数関数的に分布しています。



これは素晴らしい結果です！ マイクロバーストのセクションで見たものとは対照的に、ここではサービス時間の変動はパーセンタイルのいずれにおいても応答時間に影響しません！ このプロパティはまれであり、非感度プロパティと呼ばれます。 通常、待機がないシステムで発生し、すでに実行されているもののアフターサービスを待つ必要がない場合、要求は何らかの方法ですぐに実行され始めます。 このプロパティを持つシステムの別の例は、M / M /∞です。 サーバーの数は無限であるため、期待もしていません。 このようなシステムでは、ノードからの出力ストリームの分布が良好であるため、そのようなサーバーを備えたネットワーク（BCMPネットワーク）の製品形式のソリューションを取得できます 。



完全を期すために、最も単純な例を検討してください。 異なる平均速度で動作する2つのサーバー（たとえば、プロセッサの周波数が異なる）、着信タスクの任意のサイズの分布、サービングサーバーがランダムに選択され、ほとんどのタスクは高速サーバーに送られます。 平均応答時間を見つける必要があります。 解決策。 $$$\ mathbf {E} [T] = 1/3 \ mathbf {E} [T_1] + 2/3 \ mathbf {E} [T_2]$ 。 よく知られている式を適用します $$$\ mathbf {E} [T_i] = 1 /（\ mu_i-\ lambda_i）$ 平均応答時間M / M / 1 / FCFSおよびget $$$\ mathbf {E} [T] = 1/3 * 1 /（3-3 * 1/3）+ 2/3 * 1 /（4-3 * 2/3）= 0.5秒$ 。



さて、それで終わりです。計画について説明したので、締めくくります。 次の記事では、リアルタイムシステムでレイテンシの問題にどのようにアプローチし、そこでどのような概念が使用されているかを説明します。

読み、見るもの

1. キューイングの理論の研究には常にかなりの数学が伴い、多くの場合、考慮されるシステムはコンピューターサイエンスとは関係がないため、優れた教科書を見つけるのは困難です。 パフォーマンスモデリングとコンピューターシステムの設計：アクションのキューイング理論 （2013）をお勧めします。 ここにはまだ十分な数学がありますが、すべてが興味深いシステムに適用されます。 この記事のほとんどは、この本の無料のリテールです。
2. ロバート・B・クーパーによるビデオ講義の形式で私が知っている理論の古典を、意味を失うことなく可能な限り簡単に提示する。 これらの講義では、彼はほとんどすべての本とそれを理解するために必要なすべてを非常にわかりやすく伝えています。