# リトルの法則 ## 定義 リトルの法則(Little's law)とは、待ち行列系(またはその任意の部分系)において、平均系内客数が平均到着率と平均滞在時間(応答時間)の積に等しいという関係である(平均系内客数 = 到着率 × 平均応答時間)。1961年に Little が最初に証明したとされ、系を到着と退出だけを観測する黒箱とみなす見方に基づく。成立条件はきわめて弱く、到着過程・サービス時間分布の形をいっさい仮定しない。必要なのは、観測期間を通じて系に入る客数と系を出る客数がほぼ等しいこと(系内で新たな客が生まれず、系内で永久に失われる客もいないこと)だけである。証明は、到着曲線と退出曲線の差(その時刻の系内客数)を時間積分した面積と、個々の客の系内滞在時間の総和が同じ量になるという恒等性に基づく。この法則はシステム全体だけでなく、その任意の部分系(待機部分だけ、サービス部分だけ等)にも境界を変えて適用でき、境界の引き方によって「平均待ち客数 = 到着率 × 平均待ち時間」「平均サービス中客数 = 到着率 × 平均サービス時間」のような別々の等式が得られる。有限バッファ系のように客が系に入る前に失われる場合は、実際に系へ入った客の到着率である実効到着率を用いる必要がある。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 30 Introduction to Queueing Theory]] §30.2, §30.3) 第33章はリトルの法則を、オペレーショナル法則(operational laws、確率分布への仮定を一切置かず測定量の定義関係だけから成り立つ法則群)の一員として位置づけ直す。装置 $i$ の系内客数 $Q_i$ とスループット $X_i$・応答時間 $R_i$ の間に $Q_i=X_iR_i$ という関係が成り立つとし、これを起点に一般応答時間の法則($R=\sum_i V_iR_i$、$V_i$ は訪問比率)・対話型応答時間の法則($R=N/X-Z$、$Z$ は思考時間)という2つの法則を連鎖的に導く。すなわち第33章では、リトルの法則は単独の等式としてだけでなく、システム全体の応答時間・ユーザ数・思考時間・スループットという4者の関係へと積み上げていくための最初の連結環として使われる。この連鎖は、中央サブシステム全体にリトルの法則を適用し($Q=XR$)、個々の装置の $Q_i=X_iR_i$ を代入して強制フローの法則($X_i=XV_i$)で書き換えるという手順によって導かれる。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 33 Operational Laws]] §33.3-§33.5) ## 横断的知見 - **待ち行列理論の教科書(Jain)が与える一般証明の条件と、実務書が強調する「分布によらない」という主張は、同一の性質を異なる角度から述べている**: Jain のリトルの法則の証明は、到着過程やサービス時間分布の形をいっさい仮定せず、「観測期間内で到着数と退出数がほぼ等しい」という弱い条件だけを要求する黒箱的な議論である。[[@2023__OReillyJapan__SLO サービスレベル目標 - Chapter 9 SLIとSLOの確率と統計]] は N=μ_a w という形でリトルの法則を導入し、「システムが安定した状態であるかぎり、リクエストを受信するプロセスがポアソン過程であるかどうかや、それらが処理される方法にかかわらず正しい」と実務的な言葉で同じ性質を述べる。両者を重ねると、実務書が経験則として述べる「分布によらず成り立つ」という性質には、Jain が示す「境界を出入りする客数の収支が釣り合ってさえいればよい」という具体的で検証可能な条件が対応していることが分かる。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 30 Introduction to Queueing Theory]] §30.3, [[@2023__OReillyJapan__SLO サービスレベル目標 - Chapter 9 SLIとSLOの確率と統計]] §9.2.5.1) - **同じ法則が L=λW(詳解システム・パフォーマンス)、N=μ_a w(SLOサービスレベル目標)、「平均系内客数 = 到着率 × 平均応答時間」(Jain)という互いに異なる記号・語順で表記される**: 3ソースはいずれも「系内の平均客数」「平均到着率」「平均滞在時間」という同じ3つの量の積の関係を述べているが、変数名(L/N/系内客数、λ/μ_a/到着率、W/w/応答時間)も語順(積の左右)も統一されていない。読み手が複数の性能工学書を横断して読む際は、記号の対応(L=N=系内客数、λ=μ_a=到着率、W=w=応答時間)を明示的に意識する必要がある。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 30 Introduction to Queueing Theory]] §30.2, [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 2 メソドロジ]] §2.6.5, [[@2023__OReillyJapan__SLO サービスレベル目標 - Chapter 9 SLIとSLOの確率と統計]] §9.2.5.1) - **Jain が明示する「境界をどこに引くかで別々の等式が得られる」という一般原理を、実務書は個別の局面(ディスクI/O・SLIレイテンシ)への単一の適用として使うにとどまり、境界を明示的に選び直す議論はしていない**: Jain ch.30 は同一の系に対して、システム全体・待機部分だけ・サービス部分だけという3通りの境界でリトルの法則を独立に適用できることを図示し、境界の選択自体を意識的な設計判断として提示する。一方、詳解システム・パフォーマンス2章・SLOサービスレベル目標9章のリトルの法則の応用は、いずれも系全体(ディスクサーバ、あるいはサービス全体)を境界として固定した1通りの適用にとどまり、待機部分だけ・サービス部分だけを切り出す使い方には触れていない。これは、待ち行列理論の教科書が示す一般性(境界の自由度)が、実務書ではまだ活用しきれていない余地であることを示唆する。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 30 Introduction to Queueing Theory]] §30.3, [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 2 メソドロジ]] §2.6.5, [[@2023__OReillyJapan__SLO サービスレベル目標 - Chapter 9 SLIとSLOの確率と統計]] §9.2.5.1) - **第31章は、既に導出済みの M/M/1 の平均系内客数にリトルの法則を適用し、平均応答時間の閉形式を得るという、教科書内で完結した最初の具体例を与える**: 第30章はリトルの法則を境界の出入りだけに基づく一般的な黒箱証明として与えるにとどまるのに対し、第31章§31.2は同じ法則を E[n]=ρ/(1-ρ) という既知の量に適用し、E[r]=E[n]/λ=(1/µ)/(1-ρ) という応答時間の閉形式を導く。これは「系内客数さえ分かればほぼ自動的に応答時間が得られる」という、リトルの法則のもっとも基本的な使い方の実例であり、第30章の抽象的な証明に対する最短の具体化になっている。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 30 Introduction to Queueing Theory]] §30.2-§30.3, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] §31.2) - **第30章が一般論として注意する「有限バッファ系では実効到着率を用いる必要がある」という条件を、第31章が具体的な式として与える**: 第31章§31.4はM/M/m/Bキュー(有限バッファ)で、系に実際に入る客の到着率を実効到着率 λ′=λ(1-pB)(pB はブロッキング確率)と定義し、リトルの法則を「λ ではなく λ′ を用いて」平均応答時間 E[r]=E[n]/λ′ を導出する。これは、第30章の一般証明が要求する「観測期間内で到着数と退出数がほぼ等しい」という条件を、有限バッファ系では実際に系に入った客(λ′T)だけが満たし、棄却された客(λ-λ′)は境界の外で消えるため対象外になる、という具体的な適用例である。ただし、詳解システム・パフォーマンスやSLOサービスレベル目標のような実務書がディスクI/OやSLIの文脈でこの実効到着率を明示的に検討していないという既存の未解決の問いは、なお解消されていない(下記参照)。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 30 Introduction to Queueing Theory]] §30.2-§30.3, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] §31.4) - **第33章は、第30章が示す「境界の選び方で別々の等式が得られる」という一般原理を、装置ごとに境界を切り出して連鎖させるという具体的な使い方で実演する**: 第30章はリトルの法則をシステム全体・待機部分・サービス部分という3通りの境界に独立に適用できる一般原理として示すにとどまり(§30.3、既存の横断的知見参照)、境界を切り替えながら複数の法則を連結する具体例は示さない。第33章は、装置ごとの境界(§33.3 の $Q_i=X_iR_i$)と中央サブシステム全体という境界(§33.4 の $Q=XR$)の2つを意識的に使い分け、後者から前者への代入によって一般応答時間の法則を導く。これは、第30章が「未解決の問い」として残していた「実務でどの境界を選ぶべきかの指針」に対する、教科書自身による具体的な回答例になっている。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 30 Introduction to Queueing Theory]] §30.3, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 33 Operational Laws]] §33.3-§33.4) - **第31章がM/M/1という単一の確率モデルにリトルの法則を適用して応答時間の閉形式を得たのに対し、第33章は分布への仮定を一切置かず、複数装置からなるシステム全体の応答時間の閉形式($R=\sum_i V_iR_i$)を導く**: 第31章§31.2の $E[r]=E[n]/\lambda$ は、M/M/1というモデルが与える系内客数 $E[n]=\rho/(1-\rho)$ という確率的な量にリトルの法則を適用した結果であり、モデルの仮定(指数分布の到着・サービス)に依存する。第33章§33.4の一般応答時間の法則は、個々の装置のリトルの法則($Q_i=X_iR_i$)を積み上げるだけで、装置ごとのサービス時間分布や到着過程の形にはいっさい触れずにシステム全体の応答時間を得る。同じリトルの法則が、単一装置では「確率モデルの出力を変換する道具」として、複数装置システムでは「モデルを介さずに測定値だけを積み上げる道具」として、異なる役割を果たしている。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] §31.2, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 33 Operational Laws]] §33.3-§33.4) - **第33章はリトルの法則を装置ごと・中央サブシステム全体という2種類の境界にそれぞれ一度だけ適用するのに対し、第34章のMVAは同じ装置ごとのリトルの法則をジョブ数$N$についての反復のたびに適用し直す**: 第33章は $Q_i=X_iR_i$(装置ごとの境界)と $Q=XR$(中央サブシステム全体の境界)という2つの境界を意識的に使い分けて一般応答時間の法則を導くが(既存の横断的知見参照)、いずれも観測期間1回ぶんの恒等式として一度だけ適用される。第34章§34.2のMVAは、$Q_i(N)=X_i(N)R_i(N)$ という同じ形の装置ごとのリトルの法則を、$N=1,2,\dots$ とジョブ数を1つずつ増やす反復の各ステップで求め直す。すなわち第34章は、第33章が「一時点の恒等式」として使ったリトルの法則を、「ジョブ数について系を1つずつ解き進める再帰アルゴリズムの構成部品」として転用している。これは、境界の選び方(第30章)に加えて、同じ境界を時間方向・ジョブ数方向に繰り返し適用するという第3の使い方があることを示す。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 33 Operational Laws]] §33.3-§33.4, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 34 Mean-Value Analysis and Related Techniques]] §34.2) - **Jainの黒箱的な収支証明(到着数と退出数の差の時間積分)とは異なる第三の導出経路を、計算機アーキテクチャの教科書(H&P)が独立に示す**: Jainの証明(第30章§30.2-§30.3)は到着曲線と退出曲線の差(その時刻の系内客数)を時間積分した面積と、個々の客の系内滞在時間の総和が同じ量になるという恒等性に基づく。これに対し [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix D Storage Systems]] §D.5は、観測期間Time_observe中に完了したタスク数Number_tasksと、各タスクが系内に滞在した時間の総和Time_accumulatedという2つの実測量を定義し、「平均系内客数=Time_accumulated/Time_observe」「平均応答時間=Time_accumulated/Number_tasks」「到着率=Number_tasks/Time_observe」という3つの式を代数的に組み合わせるだけで同じ結論(平均系内客数=到着率×平均応答時間)を導く。両者はいずれも「観測期間中の到着数と退出数がほぼ等しい」という同じ前提に立ちながら、Jainは面積(積分)による幾何学的な証明を、H&Pは3つの実測量の比の代数操作という測定論的な証明を用いており、同一の定理に対する独立した2つの証明の系譜が存在することを示す。(Source: [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix D Storage Systems]] §D.5, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 30 Introduction to Queueing Theory]] §30.2-§30.3) ## 未解決の問い - Jain の実効到着率(effective arrival rate)による有限バッファ系への適用は、詳解システム・パフォーマンスやSLOサービスレベル目標のいずれの応用例でも明示的に検討されていない。ディスクI/Oのキュー溢れやSLIのリクエスト棄却が起きる状況で、実効到着率をどう見積もればリトルの法則を正しく適用できるか。 - 境界の選び方(システム全体か、待機部分だけか、サービス部分だけか)によって同じデータから異なる量(平均滞在時間、平均待ち時間、平均サービス時間)が得られるが、実務でどの境界を選ぶべきかの指針は3ソースいずれにも明示されていない。SLIレイテンシ分析において「キューイング時間だけ」を切り出してリトルの法則を適用すれば、詳解システム・パフォーマンスのM/D/1分析(§2.6.5)とSLOサービスレベル目標のM/M/1分析(§9.2.5)をより直接比較できるのではないか。 - Jain の証明は「観測期間Tが十分長ければ到着数と退出数がほぼ等しい」という近似に依拠するが、Tがどの程度長ければ実務上十分かは本書に定量的な指針がない。SLIの観測窓(例: 1分・5分)が、この近似を満たすのに十分かどうかは未検証。 - 第33章の対話型応答時間の法則($R=N/X-Z$)は、クローズドループ型負荷試験(固定並行数・思考時間ありの仮想ユーザ)の解釈に直結するとされるが、思考時間 $Z=0$ のオープンループ型負荷試験(到着率を外部から制御)ではこの法則がどう単純化・修正されるかは本書に明示されていない。SLIレイテンシ分析(SLOサービスレベル目標9章)が扱うのは主にオープンループ的な到着だが、両者の対応関係は本wiki内でまだ明示的に検討していない。 ## 関連 - [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix D Storage Systems]] — Time_accumulated/Time_observeという実測量の代数操作による、Jainとは独立の別経路の導出(§D.5)。 - [[待ち行列理論]] — リトルの法則が属するより広い理論体系(ケンドール記法、分布によらない諸規則)。 - [[オペレーショナル法則]] — 第33章がリトルの法則を一員として位置づける、確率的仮定を置かない法則群の集約 concept。 - [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 30 Introduction to Queueing Theory]] — リトルの法則の一般証明(黒箱モデル、境界の自由度)の原典。 - [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] — M/M/1への適用(E[r]=E[n]/λ)と、有限バッファ系での実効到着率を用いた適用例(§31.2, §31.4)。 - [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 33 Operational Laws]] — リトルの法則を起点に一般応答時間の法則・対話型応答時間の法則を連鎖的に導く(§33.3-§33.5)。 - [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 34 Mean-Value Analysis and Related Techniques]] — MVAの再帰の各ステップでリトルの法則($Q_i(N)=X_i(N)R_i(N)$)を繰り返し適用する(§34.2)。 - [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 2 メソドロジ]] — L=λW としての導入とM/D/1分析への応用(§2.6.5)。 - [[@2023__OReillyJapan__SLO サービスレベル目標 - Chapter 9 SLIとSLOの確率と統計]] — N=μ_a w としての導入とSLIレイテンシ分析への応用(§9.2.5.1)。 ## 出典 - [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix D Storage Systems]] §D.5(Time_accumulated/Time_observeによる独自導出) - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 30, §30.2-§30.3. - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 31, §31.2, §31.4. - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 33, §33.3-§33.5. - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 34, §34.2. - [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 2 メソドロジ]] §2.6.5 - [[@2023__OReillyJapan__SLO サービスレベル目標 - Chapter 9 SLIとSLOの確率と統計]] §9.2.5.1