待ち行列ネットワークとボトルネック

要求はキャッシュ、アプリ、データベースを順に訪れ、戻ったり複数の子要求へ分岐したりします。待ち行列ネットワークは、外部要求数を各資源が処理する仕事量へ変換します。

待ちを求める前に流量を解く

ノード $j$ への外部到着率を ${\gamma }_j$、ノード $i$ の完了後に $j$ へ進む確率を $p_{ij}$ とすると、定常流量保存は：

$${\lambda }_j={\gamma }_j+\sum _i{\lambda }_i{p}_{ij}.$$

これは経路の記帳で、各ノードのM/M/1分布を保証しません。開放Jacksonネットワークには、独立な外部Poisson到着、指数処理、適切に独立な無記憶経路、無限待機容量、各ノードの安定負荷などが必要です。内部過程も無条件に独立標本とは扱えません。

鍵はJacksonの定常積形式です。本章の単一窓口ノードでは：

$$P(N_1=n_1,\dots ,N_k=n_k)=\prod _{j=1}^k(1-{\rho }_j){\rho }_j^{n_j},{\rho }_j={\lambda }_j/{\mu }_j<1.$$

同じ定常時刻の各ノード占有数の独立性であり、経路上の待ち時間の独立性ではありません。戻りがあると内部到着はPoissonでなくてもよく、この周辺分布から平均占有とネットワーク平均時間を求められます。条件と区別は MITのJackson網講義を参照してください。

実験ではノード1、2を通り、確率 $p$ で1へ戻り、残りは退出します。各業務の各ノード平均訪問数は $V=1/(1-p)$、内部流量はともに ${\lambda }_{0}V$。処理率は100/sと250/sで、安定には ${\lambda }_{0}V<100$ が必要です。

$$E[T_{\mathrm{network}}]=V\left(\frac{1}{100-{\lambda }_{0}V}+\frac{1}{250-{\lambda }_{0}V}\right).$$

各ノード平均系内数を足し、ネットワークのLittleの法則を使って導けるため、一要求の経路上の遅延が独立である必要はありません。既定値 ${\lambda }_0=40$/s、$p=0.2$ では $V=1.25$、内部各50/s、平均31.25 msです。

外部流量を固定して戻り確率を上げると、内部負荷が増えます。ボトルネック以上では定常条件が「いいえ」となり、平均時間は — です。有限の図から存在しない定常解を出しません。

サービス需要とボトルネック界

業務一件あたり資源 $j$ の平均サービス需要は $D_j=V_{j}E[S_j]$。単一容量資源の利用率は $U_j=X{D}_j$ なので、必要なスループット上界は：

$$X\le \frac{1}{{\max }_j{D}_j}.$$

$D_j$ は占有処理だけで待機を含みません。応答時間を入れると混雑を固有仕事量と誤認します。交換可能な資源が $c_j$ 個なら $c_j/D_j$ にできますが、割当可能性と共有ボトルネックなしが前提です。上界は任意の遅延目標で到達できる性能の保証ではありません。

固定 $N$ ユーザー、平均思考時間 $Z$ の閉鎖系では $N=X(E[T]+Z)$。完了してから次を送るユーザーは応答が遅いと流入を減らします。外部予定で到着し続ける開放系とは違います。

ファンアウトと裾

$m$ 子要求の全完了を待つと時間に $\max (T_1,\dots ,T_m)$ が含まれます。子時間が独立同分布でCDFが $F$ の場合だけ、最大値のCDFは $F(t{)}^m$。一子が閾値内に終わる確率0.99でも、独立な100子が全部終わる確率は $0.99^{100}\approx 0.366$ です。

共通DB、ネットワーク、障害は依存を作るため、無条件に掛け算できません。直列段の平均は足せますが、各段p99の和は一般に全体p99ではありません。結合測定、適切な確率界、依存モデルが必要です。

確認問題

1. 業務一件がDBを平均3回、各5 ms占有します。単一資源の上界はいくつですか。

2. 10ユーザー、$Z=0$ で平均応答が0.1 sから1 sになると閉鎖負荷試験はどう変わりますか。

続けて読む

CMUの性能講義は操作定律、開放・閉鎖系、ネットワークを扱います。分割と経路の実例は Kafkaアーキテクチャへ進めます。