待ち行列という理論があり、IPAの情報処理試験にも登場する。実務での活用が難しい理論だと思う。本質を理解して活用できるように体系化する。
概要
システムでの待ち行列は、以下の4つを考える。
- CPUリソースの空待ち
- IOリソースの空待ち
- ネットワークリソースの空待ち
- ロック待ち
例えばCPUとロックだと下記の図のような待ちが発生する。もし、処理が1つのみ（例えばバッチ処理）だと待ちは発生しないので待ち行列を考える必要はない。また、定期バッチ処理のように処理が到着するタイミングが分かっている場合も、待ち行列理論は必要ではない。待ち行列理論が有効なのは、処理がランダムに到着して、時間帯によって負荷に偏りがある場合で、ユーザーの満足度を考慮して待ち時間を許容範囲に抑えたい場合である。
つまり、不特定多数のアクセスのような処理について、待ち時間のシュミュレーションおよびサイジングに待ち行列理論が使える。
CPUリソース待ちの例
1CPUコアは同時に複数処理（スレッド）を実行することはできない。CPUコアは瞬間的には常に、どれか1つの処理のみを実行している。その他の処理はWAITする。
ロック待ちの例
トランザクション処理やファイル書き込み処理ではメモリ領域やファイルをロックする。このときロックした処理以外はWAITする。
待ち行列の怖さ
待ち行列の怖さは下記の図のように利用率の増加に比例ではなく加速度的に待ち時間が長くなるところにある。このリスクを考慮してサイジングするために待ち行列理論が必要となる。
待ち時間が加速度的に増加する原理は複雑だが、以降で理解し易いように工夫したのでぜひ読んで頂きたい。
待ち行列理論の活用方法
同時アクセスが発生する場合に、ユーザーの待ち時間を目標値以内にするには、どの程度ハードウェアリソースを準備するべきか判断する。または、ハードウェアリソースの利用率を低減するチューニングを行うべきか判断する。手順としては以下の1、2、3のステップとなる。
- 待ち行列理論の公式で平均待ち時間を算出する。
- 目標待ち時間を達成するには、システム利用率をどの程度にすれば良いか算出する。（処理時間を短縮すればシステム利用率は下る）
- 上記のとおり利用率が高くなると加速度的に待ち時間が長くなるので、50％の利用率以内とする等、システムの重要度に合わせてサイジングやチューニングの度合いを調整する。
※本投稿では概念の説明に留めている。実際の分析方法、チューニング等の対策方法は別途投稿予定。
参考）待ち行列理論
ChatGPTに教えてもらった公式は下記のとおり。参考までに記載したがこの記事の以降を読み進める上でこの公式を理解する必要はない。
M/M/1キューの平均待ち時間（または平均滞在時間）の公式は以下のようになります：
W = 1 / (μ – λ)
ここで、以下のように定義されます：
- λ：平均到着率（顧客がキューに到着する平均の速度）
- μ：サーバーの平均サービス率（顧客がサーバーで処理される平均の速度）
システム設計での待ち行列の本質
上記の”待ち行列理論の活用方法”で理論の使い方を記載したが原理が理解できないと不安で利用でないだろう。本セクションが今回の記事で最も重要な部分である。
利用率が高くなれば、ユーザーの平均待ち時間が加速度的に増加する。理由は、アクセスしたとき処理中である確率が高くなるからである。以降は直感的にイメージできるようになることを目標に記載したので活用してほしい。
下記の図1は利用率が低い場合の8時間のサービス稼働を表している。処理中である可能性は低く待ち時間は小さく（処理時間＝待ち時間）なる。
図1 利用率が少ない場合
下記の図2は利用率が高い場合の8時間のサービス稼働を表している。ただし、都合良く決まった一定の間隔でアクセスが発生するものとする。処理中である可能性は0で待ち時間は小さく（処理時間＝待ち時間）なる。しかし、現実的にはアクセスは下記図3のようにランダムに発生する。
図2 利用率が高いが都合よく前のUserの処理完了後に次のUserが到着する場合
下記の図3は利用率が高い場合の8時間のサービス稼働を表している。処理中である可能性は高く待ち時間は大きくなる。赤線の部分が待ち行列の影響で増加した待時間である。
利用率に比例ではなく加速度的に増加するのは複数人が行列に並ぶ確率が高くなるからである。下記の赤線部分が加速度的に大きくなるのが直感的にイメージできれば良いと思う。
また、待ち行列の公式にはランダムにアクセスされることが考慮されている点がポイントである。（ポアソン分布という理論だが私は理解できていない。実務で支障はないと思う）
図3 利用率が高くランダムにUserが到着する場合
