有限待ち行列と受付制御

有限待ち行列は無制限の蓄積を、受付と拒否の取引へ変えます。系内数が増えなくても、要求の大半を拒否していれば業務目標を満たすとは限りません。

M/M/1/KのKは処理中も含む

Poisson到着、独立指数処理、単一FCFS窓口を維持し、系内を最大 $K$ 要求に制限します。満杯では即座に拒否し、再試行や放棄はありません。提供負荷比 $r=\lambda /\mu$ とすると：

$${\pi }_n=\frac{r^n}{{\sum }_{j=0}^K{r}^j},n=0,\dots ,K.$$

$r=1$ では全状態が $1/(K+1)$ で、特異点はありません。正の到着率と処理率を持つ有限連鎖は正再帰的で、提供流量が能力を超えても定常分布を持ちます。この $r$ は実利用率ではなく1を超え得ます。

Poisson到着では拒否確率は ${\pi }_K$ です。有効受付率、稼働割合、受付者の平均系内時間は：

$${\lambda }_{\mathrm{eff}}=\lambda (1-{\pi }_K)=\mu (1-{\pi }_0),U=1-{\pi }_0,E[T\mid \text{accepted}]=\frac{L}{{\lambda }_{\mathrm{eff}}}.$$

$L=\sum n{\pi }_n$ です。内部の系内数に外部 $\lambda$ を使うと、入っていない拒否要求を分母へ混ぜてしまいます。

既定値 $\lambda =120$/s、$\mu =100$/s、$K=5$ では、拒否約25.1%、受付約89.9/s、平均系内時間約33.6 msです。Kを増やすと拒否を減らし稼働を高める一方、受付者の待ちが増える場合があります。モデルにはタイムアウトや処理失敗がなく、受付者は全件完了します。本番の成功率は別に測ります。

受付制御、背圧、タイムアウト

受付制御は保護対象の資源を消費する前に仕事を拒否・延期します。背圧は下流の制約を上流へ伝え、待ちをクライアントや別の列へ移す場合があります。タイムアウトは呼出側が待つ時間を制限します。三つは代替関係ではありません。

呼出側のタイムアウトだけではサーバーの元の処理が止まらず、再試行で複数コピーが並行動作する場合があります。締切を伝播し、待機・派工時に残り予算を確認し、実際に可能な取消や重複排除を用意します。M/M/1/Kにはこれらがないので、平均から締切成功率を直接出せません。

待機予算20 ms、平均1000/sからK=20ならp99を満たすとは断定できません。前方の仕事量、残余処理、並列数、変動が重要です。確実な仕事量上限があれば保守的な待ち上限を作れますが、なければ分布や測定が必要です。

有効な成功仕事量を評価する

提供、受付、完了、有効成功（goodput）を分けます。速い拒否が増えると全体遅延分位点が良く見えることすらあります。拒否率と成功要求の遅延を並べ、タイムアウト、取消、未完了をSLOにどう数えるか宣言します。

確認問題

1. $\lambda =\mu$、$K=1$ の拒否率と受付者平均時間はいくつですか。

2. タイムアウトを1 sから100 msにするとサーバー仕事量は必ず減りますか。

続けて読む

有限容量は MIT講義、受付と拒否コストは Google SRE、重複と業務単位はメッセージの意味論を参照してください。