待ち行列理論とテイルレイテンシ

なぜp99だけが跳ね上がるのか

平均レイテンシは健全なのに、p99（99パーセンタイル）だけが負荷時に突然悪化する——運用していれば誰もが遭遇する現象です。これは実装のバグではなく、待ち行列（キュー）を持つあらゆる系に普遍的に現れる数理的な帰結 です。サーバー、スレッドプール、データベースのコネクションプール、ディスクI/Oキュー——リクエストが資源を待って並ぶ場所には、必ず同じ法則が働きます。

待ち行列理論は、この「待ち」を確率過程として扱い、利用率（混み具合）と応答時間の関係 を定量化します。本記事では Little's Law と M/M/1 モデルを起点に、なぜ高負荷でテイル（裾）が暴れるのかを原理から解きほぐします。

Little's Law：系を貫く保存則

最も基本的かつ強力な関係が Little's Law です。記号で書くと L = λ × W。

• L：系の中に滞留している平均の件数（処理中＋待機中のリクエスト数）
• λ（ラムダ）：単位時間あたりの平均到着率（スループット、例：req/s）
• W：1件が系に滞在する平均時間（待ち時間＋処理時間＝応答時間）

この式の凄みは、到着分布や処理時間分布に一切の仮定を置かない ことです。系が安定（長期的に入る量と出る量が釣り合う）でありさえすれば成立します。だからこそ実測値の検算に使えます。たとえば毎秒2000リクエストを捌くサービスで平均応答時間が50ms（0.05s）なら、系内に滞留する平均件数は L = 2000 × 0.05 = 100 件。つまり常時100件が処理中か順番待ちです。

M/M/1モデル：利用率と応答時間の非線形性

「待ち時間」を具体的に求めるには、もう少しモデルを特定します。最も基本的なのが M/M/1 です。記法は 到着過程 / サービス時間分布 / サーバー数 を表すケンドール記法で、M/M/1 は次を意味します。

• 1つ目の M：到着が ポアソン過程（到着間隔が指数分布、ランダムでバースト性を持つ）
• 2つ目の M：サービス時間が 指数分布（処理時間のばらつきが大きい）
• 1：サーバー（処理窓口）は 1つ

ここで核心となるのが 利用率 ρ（ロー）= λ / μ です。μ（ミュー）は単位時間あたりに処理できる件数（サービス率）。ρ は「窓口がどれだけ忙しいか」を 0〜1 で表します。M/M/1 では平均応答時間 W が次式で与えられます。

W = 1 / (μ − λ) = (1/μ) / (1 − ρ)

ここで 1/μ は混雑がないときの素の処理時間です。注目すべきは分母の (1 − ρ)。ρ が 1 に近づくと分母がゼロに向かい、W は無限大に発散 します。これが非線形性の正体です。

利用率 ρ	待ち時間の倍率 1/(1−ρ)	解釈
0.5	2倍	半分の余裕。応答は素の処理時間の2倍
0.8	5倍	ここまでは緩やかな悪化
0.9	10倍	急カーブに突入
0.95	20倍	わずかな負荷増が致命傷に
0.99	100倍	実質崩壊

ρ が 0.5 から 0.8 へ上がっても倍率は 2→5 と緩やかですが、0.9 から 0.95 への移動は 10→20 と一気に跳ねます。利用率を80%以下に保つ という運用上の経験則は、この曲線の「膝（ニー）」の手前に留まれという意味だったのです。容量設計でヘッドルームを確保する根拠でもあります（/devops/capacity-planning/）。

なぜテイル（裾）が暴れるのか

p99 が平均から乖離して暴れる理由は、待ち行列の確率的な性質にあります。

第一に、バースト性 です。ポアソン到着では、たまたま短時間にリクエストが集中する瞬間が必ず生じます。窓口が空いていればすぐ処理されますが、利用率が高いと「既に並んでいる列の後ろ」に着くため、待ち時間が積み上がります。この「運悪く混んだ瞬間に来た少数のリクエスト」がテイルを形成します。

第二に、分散の効き方 です。指数分布のサービス時間は分散が大きく、平均の何倍もかかる処理がときどき発生します。1件の長い処理が窓口を占有すると、その背後の全リクエストが待たされます。

ヘッドオブラインブロッキング

この「背後が待たされる」現象を ヘッドオブラインブロッキング（HOL blocking） と呼びます。FIFO（先入れ先出し）キューでは、先頭の1件が詰まると、たとえ後続が一瞬で終わる軽い処理でも、先頭が捌けるまで一切前に進めません。

• 単一コネクション上で重いクエリと軽いクエリが直列に並ぶと、軽い方まで巻き添えになる
• TCPやHTTP/1.1のコネクション多重では、1つの遅い応答が同じ接続上の後続を止める
• ロック待ちや単一スレッドのイベントループでも同型の詰まりが起きる

HOL blocking の怖さは、全体の平均にはほとんど影響しないのに、巻き込まれた少数のリクエストのテイルだけを悪化させる 点にあります。だからこそ p99 にだけ症状が出ます。対策の方向は、優先度付きキューイング、コネクション多重化（HTTP/2のストリーム）、重い処理の隔離（別プール化）などです。

テイル増幅：多段アーキテクチャの罠

マイクロサービス（/devops/microservices/）では、1つのユーザーリクエストが内部で多数のサービス呼び出しに分岐・直列化します。ここで テイル増幅（tail amplification） が起きます。

仮に各バックエンドが個別には p99 = 10ms（99%は10ms以内）だとします。あるユーザーリクエストが100個のバックエンドを呼び、全部が揃って初めて応答できる（ファンアウト＋全件待ち合わせ）とすると、「少なくとも1つが遅い裾に当たる」確率は急増します。各呼び出しが独立なら、全100件が10ms以内に収まる確率は約 0.99^100 ≒ 0.366。つまり約63%のユーザーリクエストが、どこか1つの遅延に引きずられる ことになります。個々のサービスの p99 が良好でも、合成したエンドツーエンドのテイルは劇的に悪化するのです。

テイル増幅への実務的な打ち手の一つが ヘッジ要求（hedged request） です。一定時間内に応答が返らなければ、同じ要求を別レプリカにも投げ、先に返った方を採用します。遅い裾に当たった少数のケースを救い、p99 を引き下げます。あわせて、どこで時間を使っているかを可視化する/devops/distributed-tracing/が、テイルの原因特定に不可欠です。

運用への落とし込み

理論が示す結論は明快です。利用率を抑えることが最も効くテイル対策 です。

• 目標利用率を低めに（例：60〜70%）設計する：1/(1−ρ) の曲線の膝より手前に留まる。コストとのトレードオフだが、p99 を守る最安の保険。
• 平均ではなくパーセンタイルでSLOを定める：ユーザー体験はテイルが決める。p99・p999 を SLI に据える（/devops/sre-slo/）。
• キューの可視化：滞留件数 L や待ち行列長を直接メトリクス化し、Little's Law で検算する。
• 隔離と優先度：重い処理を軽い処理から分け、HOL blocking を物理的に断つ。

待ち行列理論は抽象的に見えて、スレッドプールのサイズ、オートスケールの発火閾値、SLO の置き方まで、運用判断の根拠を与えてくれます。「なぜ高負荷でp99が暴れるのか」を 1/(1−ρ) の一語で説明できる こと——それが、感覚ではなく数理で性能を設計する第一歩です。

まとめ

• Little's Law（L=λW） は分布に依存しない保存則。実測値の検算と容量逆算の土台になる。
• M/M/1 の応答時間は 1/(1−ρ) で発散 する。利用率が0.8を超えると曲線の膝に入り、わずかな負荷増が致命傷になる。
• テイルは平均と別物。バースト性・指数的な裾・HOLブロッキングが、少数のリクエストの p99 を選択的に悪化させる。
• 多段ファンアウトはテイルを増幅 する。各サービスが健全でも合成 p99 は崩れる。ヘッジ要求・隔離・トレーシングで対処する。
• 最も効く防御は 利用率を抑えること。p99 でSLOを定め、ヘッドルームを設計に織り込む。