- ブラウザURL入力
- DNS名前→IP
- ルータ経路選択
- ロードバランサ振り分け
- Nginx受け口
- アプリ処理今ここ
- DB保存
第13期の4本目です。前回までは数字の読み方でした。今回は「混み具合」という状態を扱います。
まず結論
1件あたりの仕事を増やさなくても、到着を増やすだけで応答時間は伸びます。増えたぶんは全部が「待ち」です。
だから使用率を上げ切る運用は、無駄を削っているのではなく待ち時間を代価として支払っています。「余力が遊んでいる」という指摘は、何を買っているかを見ていません。
1件あたり必ず5msかかるサーバがあります。処理内容は変えず、到着の間隔だけを詰めていきました。平均応答時間はどうなるでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
この回の「待ち行列」は、取り出し規則の話ではない
先に語の衝突を切ります。この研修では「待ち行列」を何度も使いました。ブラウザ編『イベントループ — タスクは集合、マイクロタスクは待ち行列』の題名や、listen(2) の backlog です。あれらはすべて「どの順に取り出すか」という規則の話でした。
**この回は別の意味です。扱うのは混み具合、「どれだけ溜まるか」**であって、どの順に取るかではありません。取り出し規則を固定し、到着の勢いだけを変えたとき何が起きるか。
主張はひとつ。余力は無駄ではなく、待ち時間を買わずに済ませるための代金です。
仕事を1ミリ秒も増やさずに、応答を10倍にする
本教材で測りました。Python の単一ワーカで、1件の処理時間をきっかり5.0msに固定し、変えたのは到着の勢いだけです(ポアソン到着・負荷は自分自身にのみ)。
理論上の最大処理能力は 1/5.0ms = 200件/秒。到着率をそこへ近づけると、平均応答時間は7ms台から76〜95msへ伸びました。
見てほしいのは、何が変わっていないかです。 サービス時間は全条件で5.0ms。1件あたりの仕事は1ミリ秒も増えていないのに、応答は10倍以上に。増分の大半は待ちです(クライアント側の費用の混入は後述)。
伸び方も比例ではありません。最大処理能力の3割から5割では平均がほとんど動かないのに、8割から9割では数倍になります。同じ増分が、同じ代価ではない。
サービス時間を5ms固定のまま到着率だけ上げたとき、伸びた時間の正体は何ですか。
国際標準が書いていること、書いていないこと
この現象を語る道具として L = λW がよく持ち出されます。「リトルの法則」と呼ばれている関係です。
本教材はこの名の由来となった1961年の論文を取得できませんでした(出版社が403)。読んでいないものに帰属させられないので**「〜によれば」とは書きません。**
代わりに、系を資源のプールに取った場合の同型の関係なら、国際標準の逐語で置けます。ITU-T Recommendation E.600 (03/93) §1.10 NOTE 2 です。
Traffic intensity is equivalent to the product of arrival rate and mean holding time.
到着率と平均保留時間の積と等価である、と注記しています(定義ではなく NOTE)。ただし電話トラフィックの標準であり、Web への適用は教材側の類推です。
さらに重要なのが、式は無条件では使えない点です。ITU-T E.500 (11/98) §5.2 が定常とみなす必要条件を3つ挙げ、§5.3 Assumption 4 が非定常な期間の除外まで求めています。
a) the job arrival process can be considered stationary; b) the job departure process can be considered stationary; c) both the arrival and departure processes have the same mean rate during the read-out period.
Exceptional read-out periods that violate Assumption 1 (e.g. the observed arrival process is highly non-stationary) should be detected and excluded from being considered.
標準自身が「前提の崩れる期間がある」ことを織り込んでいます。 しかも §5.2 は、平均保留時間が読み出し期間より十分短い場合に限って平均トラフィック密度を A = λ·n·h(式(1))で与えています。待ち時間の式は E.500 にありません。 言えるのは「式には前提があると標準が明文化している」までです。
- ・増えるのは待ちの段だけ。上の段は動かない
- ・数値は本教材の測定条件(VM上のPython単一ワーカ)
測るたびに順序が入れ替わった
同じスクリプトを2回走らせました。そこで起きたことが、数値より重要です。
1回目は到着率を上げるほど平均応答が単調に伸びました。ところが2回目は、最大処理能力の9割の平均が9.5割より大きくなり、大小関係が逆転したのです。
1つの読み方は、上限近くでは分散が大きく、短い測定では値が安定しない、です。ただし低負荷でも応答は7ms台と公称5msより長く、実効のサービス時間が5msを超えていたなら、公称9〜9.5割は実効で上限を超えた過負荷で、E.500 の前提の外です。どちらかは切り分けていません。
この不安定さは運用上の帰結を持ちます。上限近くで動かすとは、平均を予測しにくい領域で動かすことです。
なお測定では、到着率が高いほどクライアント側も1件1スレッドで数百本を抱えます。その費用が測定値に混じっている可能性を排除できていません(3本目のとおり、観測には費用があります)。
待ち行列の式を「どんなサーバにもそのまま当てはまる」と説明されたとき、どう評価しますか。
サーバの使用率と待ち時間
到着率を最大処理能力に近づけるほど、1件の処理時間は変わらないのに応答時間が伸びます。伸びるのは待ちだけです。
項目 到着率が低い 上限に近いサービス時間 5.0 ms 固定 5.0 ms 固定(不変)待ち ごくわずか 応答の大半測り直すと 近い値 大きく違う値
ハッシュ表の負荷率(アルゴリズム編で既習)
負荷率はバケットあたりの要素数の平均で、枠を増やさずに詰めるほど上がります。ハッシュ値の計算は重くならないのに、バケットの中を辿る手間だけが増えます。
項目 負荷率が低い 上限に近いハッシュ値計算 同じ 同じ(不変)バケット内探索 ほぼゼロ 増える使う枠(余白) 多い 少ない
サーバの使用率と、ハッシュ表の負荷率。層も単位も違いますが、共通する構造は何でしょうか。
「詰めたときに増える量」が、どちらも本来の仕事ではないことに注目してください。
この章のまとめ
- ここでの「待ち行列」は混み具合の話で、取り出し規則ではない。
- サービス時間を5ms固定のまま到着率だけ上げると、平均応答が7ms台から76〜95msへ(VM上のPython単一ワーカ)。増分の大半は待ち(クライアント側の費用の混入は未排除)。伸び方は比例しない。
- 上限近くでは値が再現しない。 測り直したら大小関係が逆転した。だから単一の数値表を作らない。
- L = λW と同型の関係(系を資源のプールに取った場合)は ITU-T E.600 (03/93) §1.10 NOTE 2 の逐語で置ける。原論文は未取得なので帰属させない。
- 式は無条件では使えない。E.500 (11/98) §5.2 が定常性の必要条件、§5.3 Assumption 4 が非定常な期間の除外を挙げる。式(1)もこの条件の下。待ち時間の式は E.500 に無い。
- 余力は無駄ではなく、待ち時間を買わずに済ませるための代金。 削るなら、どこまでの待ちを許すかを先に決める。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
「使用率が低いのは無駄です。詰めましょう」という提案を評価するとき、最初に確認すべきことは何ですか。
用語集(4語)
- 待ち(queueing delay)
- 順番が来るまでの時間。処理の時間とは別に積み上がる。本レッスンの「待ち行列」はこの混み具合の話で、取り出し規則ではない。
- サービス時間
- 1件を処理する時間。本レッスンの測定では5msに固定した。応答時間はこれと待ちの和になる。
- traffic intensity(トラフィック密度)
- ITU-T E.600 (03/93) §1.10 の語。ある瞬間に busy な資源の数。同 NOTE 2 は到着率と平均保留時間の積と等価だと注記する。単位はアーラン(erlang)。
- 定常性(stationarity)
- 統計的な性質が観測期間を通じて変わらないこと。ITU-T E.500 (11/98) §5.2 は、到着過程・退去過程が定常で両者の平均レートが同じことを必要条件に挙げる。