M/M/1：利用率とテールレイテンシ

4 分で読了 #待ち行列理論 #基礎理論

このページの目次

M/M/1はランダムな到着と処理を厳密に解けるモデルです。利用率が1に近づくと待ち時間が非線形に増える理由と、平均だけでは利用者の経験を表せない理由を示します。

状態平衡から平均へ

外生Poisson到着率 $λ$ 、独立同分布の指数処理率 $μ$ 、両者の独立、単一FCFS窓口、無限待機容量、放棄・再試行なしを仮定します。状態 $n$ は系内要求数。到着により率 $λ$ で増え、空でないとき処理完了により率 $μ$ で減ります。

定常状態の隣接平衡は $π_{n} λ = π_{n + 1} μ$ 。 $ρ = λ / μ$ とおいて幾何級数を正規化すると：

$π_{n} = (1 - ρ) ρ^{n}, ρ < 1; L = n \geq 0 \sum n π_{n} = \frac{ρ}{1 - ρ} .$

したがって：

$E [T] = \frac{1}{μ - λ}, E [W_{q}] = \frac{ρ}{μ - λ}, L_{q} = \frac{ρ ^{2}}{1 - ρ} .$

$ρ \geq 1$ では無限状態連鎖を正規化できず、定常分布はありません。式へ代入して「負の待ち時間」を出すのは誤りです。等号もこの確率系の安全な平衡点ではありません。

到着者は確率 $π_{n}$ で前に $n$ 要求を見ます。無記憶性により自身の系内時間は $n + 1$ 個の独立指数処理時間の和です。これを幾何分布の重みで混ぜると：

$P (T > t) = e^{- (μ - λ) t}, t \geq 0.$

待ち時間は異なり、確率 $1 - ρ$ で直ちに処理が始まります。

$P (W_{q} > t) = ρ e^{- (μ - λ) t}, P (W_{q} = 0) = 1 - ρ .$

系内時間の $p$ 分位点は $t_{p} = - ln (1 - p) / (μ - λ)$ 。このモデルのp99は平均の約4.605倍ですが、実サービス全般に共通する比率ではありません。

図を準備しています

M/M/1：利用率とテールレイテンシ · 実験

定常FCFS M/M/1、待機容量無限、μ=100/s。Wqの裾はt=0でρ、残りは待たずに処理されます。下図の縦線は現在の利用率で、値はモデル内の厳密値です。

$μ = 100$ /s、 $ρ = 0.8$ なら平均系内時間50 ms、平均待ち40 ms、p99約230 ms。 $ρ = 0.9$ では100、90、461 msになります。平均処理時間は常に10 msです。

このモデルで系内時間p99を200 ms以下にするには：

$μ - λ \geq \frac{ln 100}{0.2} \approx 23.026 s^{- 1} .$

$μ = 100$ /sなら $λ \leq 76.974$ /sです。条件付きの流量範囲であり、長い処理、バッチ、多段処理、下流の低速化があればモデルと負荷試験を見直します。

利用率曲線だけでは拡張の効果も分かりません。ワーカーを増やしても本当のボトルネックの $μ$ が変わらず、競合で低下する場合すらあります。占有時間と負荷依存の動作から能力を識別します。

考え方

半分は待たずに開始できますが、処理は必要です。 $W_{q}$ は0に確率質量を持ち、 $T$ は持ちません。待つ確率と総遅延の分布を混同しないようにします。

考え方

定常FCFS M/M/1が適用できる場合に限ります。実際は混合分布、多段処理、相関があり得ます。分布を記録してモデル誤差を確認する必要があります。

MIT Urban Operations Research §4.6.1は状態と系内時間の分布を導きます。次章では平均処理時間を保ちながら指数分布の仮定を緩めます。