← システム性能分析のしくみ コース
3. リトルの法則 — 同時実行数はどう決まるか
系に入ってくる要求の数と、1件あたりの滞在時間から、系の中に何件が同時にいるかが決まります。その関係を図で追っていきましょう。
① 系を1つの箱として見る
要求が到着する到着率 λ(件/秒)
箱の中に入る
系(この箱の中)中にいる平均件数 L(件)
境界は自分で決める平均 W 秒とどまってから
要求が退出する完了して箱から出る
- ・λ は単位時間あたりに箱へ入る件数です
- ・W は1件が箱に入ってから出るまでの平均時間で、待ち時間と処理時間の両方を含みます
- ・L は瞬間ごとに数えた「箱の中の件数」を時間平均した値です
箱の中身を一切のぞかずに、入る速さ・とどまる長さ・中にいる数の3つだけを見ます。この3つの関係がリトルの法則です。
② L = λW という関係
λ(件/秒)到着率
W(秒)平均滞在時間
かけ算すると
L = λ × W系内の平均件数(件)
式を変形すると
W = L ÷ λ滞在時間を求める形
λ = L ÷ Wスループットを求める形
- ・単位で確かめられます。(件/秒)×(秒)=(件) となり、L が件数になります
- ・時間の単位は λ と W の間で打ち消し合い、残るのは件数だけです
- ・J. D. C. Little が1961年に証明した関係です(Operations Research 9(3): 383-387)
3つの量のうち2つを測れば、残りの1つは測らなくても計算で出せます。実務ではこの「測らずに出せる」性質が効いてきます。
③ 数値を入れてみる
λ = 200 件/秒1秒間に200件が到着
W = 0.05 秒1件あたり50ミリ秒で完了
L = 200 × 0.05
L = 10 件平均して常時10件が処理中
では W が10倍に伸びたら
W = 0.5 秒1件あたり500ミリ秒
L = 100 件同じ λ でも同時数は10倍
- ・同じ到着率でも、1件が遅くなるほど系内に溜まる件数は比例して増えます
- ・逆に W を半分にできれば、同じ λ を半分の同時数で捌けます
毎秒200件を捌いていても、1件が0.05秒で終わるなら同時にいるのは平均10件だけです。同時数は到着率だけでは決まりません。
④ スレッド数・コネクション数の見積もりに使う
捌きたい λ例: 200 件/秒
実測した W例: 0.05 秒
L = λW で必要な同時数を出す
必要な L = 10平均10枠が常に埋まる
平均であって最大ではない
プールサイズは L より大きく取る到着の揺らぎを吸収する余裕が要る
- ・W は待ち時間を含むので、実測値を使う場合は「処理時間」ではなく「滞在時間」を測ります
- ・L はあくまで時間平均です。瞬間的にはこれより多い時点も少ない時点もあります
- ・DBコネクションプールのように系が入れ子になる場合、それぞれの箱ごとに L を出せます
スレッド数やコネクションプールサイズは、勘ではなく L = λW から出発して決められます。ただし L は平均なので、そのままの数を上限にはしません。
⑤ L に上限があるとき何が起きるか
L の上限 = 10スレッド数やプールサイズで固定
λ が 200 件/秒あたりまでは
L = 10 に収まるW = 0.05 秒のまま
平均的には待ちが出にくいλ が 400 件/秒に増えると
L は 10 から増やせない枠が全部埋まっている
入れない要求は外で待つ待ち行列ができる
待ち行列も系に含めて数え直すと
L が待ち分だけ増えるL = λW を満たすため
W が伸びる待ち時間が滞在時間に乗る
- ・処理中の枠数に上限があっても、待っている要求まで含めた L は増え続けます
- ・λ を減らせないなら、W が伸びることで式の辻褄が合います
- ・到着が偏る場合、平均の λ が上限に届く前から待ちが発生します
- ・待ち行列にも上限があると、そこを超えた要求は系に入れず拒否されます
同時実行枠が埋まりきると、あふれた要求は外で待ちます。λ が変わらないまま L が増えるので、その分だけ W が伸びるという形で現れます。
⑥ 分布を仮定していないこと
必要な前提系が定常であること
長期平均が一定値に落ち着くこれらは仮定していない
到着の分布一定でもバースト的でもよい
処理時間の分布ばらついていてよい
処理の順序FIFO でなくてよい
だから
どの箱にも当てはめられる系の中身を知らなくてよい
- ・必要なのは、L・λ・W の平均が有限で、系が定常であることです
- ・到着過程の分布・処理時間の分布・処理順序のいずれにも影響されません
- ・系の中に系がある場合、それぞれの箱にも全体にも同じ関係を当てはめられます
この法則は待ち行列の細かいモデルを立てなくても使えます。中身を知らないまま外から測った2つの量だけで、3つめが分かるのが強みです。