待ち行列理論で考えるGoogle Kubernates Engineの最適なポッド数🤔

読み飛ばしていい、著者の戯言

色々ありまして、Clood Professional Architectの勉強しています。アウトプットしようと思っても、「本や公式ページ、Udemiyで勉強したことを、ただただまとめるのはつまらんなあ」と駄々を捏ねて書いた記事１作目です。GKEについて勉強していて気になったことを調べました。CPA関連で、この記事を含めて３報アップする予定です。

この記事を書くためにGeminiさんらと問答して、待ち行列なるものも新たに勉強することになりました（問答はしましたが、この記事を書いているのはすべて私です）。純粋な理論ばかり触ってきた私にって、応用数学は新鮮で、より現実の問題とリンクしてる感覚をひしひしと感じています。

もちろん学術書ではないので、ゴリゴリ数学の式変形をZennでやるようなことはしません。結果だけ使います。S. Hawkingの著書であるA Brief History of Time（ホーキング、宇宙を語る : ビッグバンからブラックホールまで）の冒頭には、数式を文書に入れると、その数だけ減少するという旨の話があります。流石に数式１つというわけにはいかないですが、紹介しながら進めていきます。

導入

クラウドネィティブなマイクロサービスのデプロイ先としてGoogle Kubernates Engine (GKE)を想像する人は多いと思います。マイクロサービスとして動くそれぞれのサービスのポッド性能は、開発段階において人の感覚で決められることが多いのではないでしょうか？「とりあえず、他のサービスのCPUがこれくらいだから」「ベストプラクティスがこれくらいだから」という理由で決めてしまっていることが、GKE上で、いやそうでない一般の開発現場でも往々にして存在するのではないか、と予想しています（だって、人間だもの）。

ベストプラクティスという言葉は、効率的にで業務を回す日常において安心感のある言葉ではあります。一方でよくよく考えてみると、なぜベストプラクティスなのかは瞬時にわかりかねます（私に関しては経験不足によるものでしょうが）。「〇〇という状況を想像してみると、こちらのほうがよい」と、なんとなく説得させられた気になります。しかしながら、「ベストプラクティス」は過去の多くの経験から帰納的に考えられたものです。

そこで、帰納的な考えをできる限り排すことにし、数理モデルから演繹的に、ポッドの性能を決定をすることを目指します。

この記事ではGKEのポッドを待ち行列理論、および実務的な観点から、いくつかの仮定を置くことで、数理的に適切なポッド数を予想します。

この記事の構成は次のとおりです。

1. 待ち行列理論の概要を説明します。
2. Google Kubernates Engineについて軽く触れます。
3. 必要な数学（ポアソン分布、指数分布、待ち行列理論）を導入します。

待ち行列理論 (queueing theory)とは

簡単にいうと、ある系の混雑状況を数学的に記述した理論のこと。物理的、社会的な洞察から要請する仮定を使い、得られた系の数学的な表現を、単にモデルということが多いです。

混雑状況を数理的に表現するといことから、応用範囲は広く、レジに並ぶ顧客であったり、今回の記事にもなっているサーバなどの、性能評価に応用されることが多いようです。

ここで行列とは、線形代数でいう行列 (matrix)ではなく、並んでいる列(queue)を表します。

※英語版Wikipediaにも書いていますが、スペルが"queuing"と書かれる分野もあるそうですが、重要なジャーナルの一つは次のような雑誌名になっています：Queueing Systems

https://en.wikipedia.org/wiki/Queueing_theory

Google Kubernates Engine (GKE)とは

コンテナのオーケストレーションツールです。GoogleのBorgらの論文から始まった、GoogleがGoogle Cloud Platfrom上で提供するサービスです。

コンテナに対して、管理、実行、オートスケール、オートヒーリング、ローリングアップデートなどなどを宣言的に処理することができる便利ツールですね。

この記事では特に、オートスケールに興味を持ちます。このスケーリングにも種類があり、

• 水平スケール (HPA: Horizontal Pod Autoscaler)
• 垂直スケール (VPA: Vertical Pod Autoscaler)
• 水平垂直スケール (MPA: MultidimensionalPodAutoscaler)

があります。

https://queue.acm.org/detail.cfm?id=2898444

準備

数学的な仮定

今回採用する待ち行列のモデルとして、簡単なMMcモデルを採用します（理由は特にありません。時間が足らんかったんです泣）。ここで、MMcはそれぞれ

• M: マルコフ到着過程 (Markovian Arrival Process)　リクエストの到着がランダム
• M: マルコフサービス過程 (Markovian Service Process)　ポッドでの処理時間がランダム
• c: 処理を行うポッド数
  であると仮定します。

到着過程

現実のリクエストはランダムに飛んでくると考えられます。もちろん、特定の時間に周期的に大量のリクエストが来るということはありますが、簡単のためにこの記事では言及いたしません。リクエストのランダムネスは、数学の言葉でポアソン分布というものにモデル化することができます。単位時間の平均リクエスト数を$\lambda$とするとし、その単位時間で$k$回のリクエストが飛んでくると確率は

$$P(k) = \frac{\lambda^k e^{-\lambda}}{k!}$$

と与えられます。

（ポアソン分布と調べると、よく馬に蹴られて死んだ兵士の例が出てきますね）

サービス過程

GKEにデプロイされたアプリを担うポッドでの多くの処理は、これまでの処理の履歴に依存しないと考えられます。

例えばあるリクエストの処理に平均50 msecかかるとします。30 msecも経ったから、あともう直ぐで終わるというのは、平均という尺度を見ているから感じる感覚であって、実際は31 msecで終わることもあれば、100 msecかかることだってあります。確率は小さくとも1000 msecなんてことはあるやもしれません。このような事象の時間間隔にランダムネスがあるとき、数学の言葉では指数分布

$$p(t) = \mu e^{-\mu t}$$

という確率密度に変換することができます。ここで$\mu$は単位時間に処理できるリクエスト数です。単位時間を1 sec (= 1000 msec)とすれば、$\mu = 20$です。

モデル

リクエストをして、$c$個のポッドが処理するという系において、系内に$n$個のリクエストが残っている（ポッドで処理中&待ち行列にある）動的な確率は出生死滅仮定(birth-death process)として

$$\frac{\mathrm{d} P_n(t)}{\mathrm{d}t} = \lambda P_{n-1}(t) + \mu_{n + 1} P_{n+1}(t) - (\lambda + \mu_n) P_n(t)$$

と記述されます。これはポアソン分布や指数分布の性質（無記録性）を使うことと、状態間の遷移が隣同士の状態にしか依存しないことから導かれます。
https://ia601403.us.archive.org/13/items/in.ernet.dli.2015.134547/2015.134547.Queueing-Systems-Volume-1-Theory.pdf

これでポッドのスケールの過渡期を説明するとことができるかもしれませんが、かなり挑戦的な内容になります。オートスケールするタイミングなどを議論する場合には必要な要素で面白い内容だとは思いますが、今回のポッドの最適な数を理論的に見積もるということからは大きく逸脱してしまうので、この式そのままの解析はいたしません。

最適なポッドの数、つまりあるべき状態を定義するということは、あるべき状態になったあと、その状態を維持するということです。状態を維持するということは、確率$P_n$が静的であることです。つまり、$\mathcal{d} P_n(t)/\mathcal{d} t = 0$が要請されます。そうすれば上記の微分方程式の右辺の$P_n$等も時間変化することはなくなるため、単なる差分方程式に落ち着きます。つまり、次のようなつり合いを表す式になります：

$$\underbrace{(\lambda + \mu_n) P_n(t)}_{\tiny{状態nから状態n-1 or n+1への流れ}} = \underbrace{\lambda P_{n-1}(t)}_{\tiny{状態n-1からnへの流れ}} + \underbrace{\mu_{n + 1} P_{n+1}(t)}_{\tiny{状態n+1からnへの流れ}}$$

実は、このような全体のつり合いの式が成り立つとき、より詳細な状態間のつり合いも成り立ちます（詳細つり合い）。つまり、

$$\lambda P_{n-1} = \mu_n P_n$$

です。イメージとしてはポッドにリクエストして、ある程度CPU使用が高い状態を維持しているとき、リクエストの早さと処理の速さが同じ、ということを表しています。

GKE性能指標の導出

さて、上記の議論からGKEの性能指標を導出しましょう！ここまで３つの数式が登場しましたが、ここから使うのは最後の式、詳細釣り合いの式$\lambda P_{n-1} = \mu_n P_n$です。ステップとしては

1. $P_n$を求める
2. 確率の規格化条件から$P_0$を求める
3. $P_n$を使った指標を定義する
   です。

$P_n$を求める

詳細釣り合いの式から、$P_n$を$P_0$で表すことができます。ただし、リクエストが系に存在する数$n$とポッド数$c$の大小で場合分けが必要になります。
結果だけ書くと、

(i) $n < c$の場合

$$P_n = \frac{1}{n!} \left( \frac{\lambda}{\mu} \right)^n P_0 \tag{2}$$

(ii) $n > c$の場合

$$P_n = \frac{1}{c!} \left( \frac{\lambda}{\mu} \right)^c \left( \frac{\lambda}{c\mu} \right)^{n-c} P_0 \tag{3}$$

と表せます。

$P_0$を求める

確率の規格化条件

$$\sum_{n = 0}^\infty P_n = 1$$

を使います。上記の$(2), (3)$を代入することで、最終的に

$$P_0 = \left[ \sum_{n=0}^{c-1} \frac{1}{n!} \left( \frac{\lambda}{\mu} \right)^n + \frac{1}{c!} \left( \frac{\lambda}{\mu} \right)^c \frac{c\mu}{c\mu - \lambda} \right]^{-1} \tag{4}$$

と表されます。無限和がでてきますが、高校数学ででてくる$\sum_{k = 1}^\infty r^k = 1/(1 - r)$を使えば導くことが出てきます。ここで暗に仮定しましたが、$\lambda < c\mu$です。もし$\lambda \geq c\mu$、つまり到着率が全ポッドの処理能力を上回るということは、どんどんリクエストが来ているにも関わらず、ポッドがそれを捌くことができていない状態であるということです。ですから、安定稼働しているという条件のために、$\lambda < c\mu$が要請されるのです。

評価指標を計算する

平均待ち行列長

平均待ち行列長$L_q$を次のように定義します。

$$L_q = \sum_{n=c}^\infty (n - c) P_n \tag{5}$$

これはどう意味かというと、ポッドが全て埋まったときに、系で処理待ちしているリクエストの数です。状態$n$のとき、すなわち系にリクエストが$n$個存在する時、$c$個のポッドが$c$個のリクエストを処理中であり、$n - c$個が未処理（待ち行列）にあります。これを全ての場合について確率をかけて期待値を計算したものが上記の式になります。

ところで、$(3)$から$n > c$のときの$P_n$が与えられているため、具体的に$(5)$を計算することができます。結果だけ書くと

$$L_q = \underbrace{\frac{P_c}{1 - \rho}}_{\tiny{待ちが発生する確率}} \times \underbrace{\frac{\rho}{1 - \rho}}_{\tiny{待ちのやばさ}}$$

を得ることができます。ここで見やすさのために$\rho = \lambda/(c\mu)$としました。計算はちょっとだけ面倒ですが、等比数列の無限級数の導出を少し撚ればOKです。

ですが、ちょっとよくわかりません。なのでなるべく直感的な説明を考えてみます。

待ちが発生する確率

(a) $P_c$は系に$c$個のリクエストが存在する確率です。ちょうどポッドの数だけリクエストが存在し、はじめてポッドを占有するのがこのときです。なので、この状態で、さらにリクエストがくれば「待ち」が発生します。

(b) では、リクエストがすでに待っている状態$c+1, c+2, \ldots$の確率はなんでしょうか？$n \geq c$のとき、$(3)$から$P_n = P_c \rho^{n-c}$となっています。

これらを(a), (b)を総計することで、待ちが発生する確率$P_{\rm wait}$を計算できますね。よって

$$P_{\rm wait} = \sum_{n = c} P_c \rho^{n - c} = P_c \sum_{n = c} \rho^{n - c} = \frac{P_c}{1- \rho}$$

となるのです。

待ちのやばさ

いい表現が思いつきませんでしたが、ポッドの処理が小さいとき、つまり$\rho = 0.01$のとき、近似的に$L_q \simeq 1.01 \times P_c$であり、待ちが長くなることはほとんどなく、すぐ解消されると言えます。

一方、$\rho = 0.99$のとき、$L_q = 10000 P_c$です。系の処理能力が限界に近いと、待っている処理が全然解消されないということです。ノートパソコンのCPUが限界近い時に、処理が死ぬほど重くなっているあの現象は、まさしくこれをが反映されているものだと勝手に思っています。

平均待ち時間

待ちの長さがわかれば、処理の平均速度（=サービス率$\lambda$）を使うことで、平均待ち時間を知ることができます。小学校で学ぶ、距離と速さと時間の関係を使っているだけです：

$$W_q = \frac{L_q}{\lambda}$$

パーセンタイル応答時間の計算

平均待ち時間が$W_q$なので、待ち時間が$t$以下である確率は

$$P(W_q \leq t) = 1 - e^{- t/W_q}$$

です。詳細は省きますが、これは冒頭で紹介したポッドの処理時間が指数分布と仮定できる、ということに直接的に関わるものです。

待ち時間がこの時間以下になる確率が95%であることを求めましょう。これを95パーセンタイル待ち時間$W_{q, 95}$とします。すると、待ち時間が$W_{q, 95}$を越さない確率が$0.95$なので

$$0.95 = 1 - \exp \left[ - \frac{W_{q, 95}}{W_q} \right]$$

です。これを$W_{q, 95}$について解くと

$$W_{q, 95} = -W_q \underbrace{\log (0.05)}_{\simeq -2.995} \simeq 3 W_q$$

です。そして、これは待ち時間なので、ユーザが体感する応答時間$W_{95}$は、上記に処理時間を足して、

$$W_{95} \simeq 3W_{q} + \frac{1}{\mu}$$

となりますね。

具体的な計算例

さて、SLOを設定して、負荷検証を実施して、次が確定したとします：

• SLO: 95パーセンタイル時間が$200~{\rm msec}$以内に収める
• $\lambda$　リクエストが平均$\lambda = 100件 /{\rm sec}$
• $\mu$:　処理するにの$\mu = 20件/{\rm sec}$

すると、ポッドの利用率$\rho$は

$$\rho = \frac{\lambda}{c\mu} = \frac{100}{20c} = \frac{5}{c}$$

ここで、技術的要請から$c > 5$でなければなりません。ポッドの利用率が$100\%$は避けろ、と多くの人が言うでしょう。

ここまでできたら、$W_{95}$を計算できます。ただ、代数的に解くのは厳しいので、ここからはプログラムに任せましょう！$c = 6, 7, 8, \ldots$と増やすことで、要件を満たす$c$が自然とわかるはずです。

この結果によると、ポッドが6つの時点でレスポンスまでの時間が$138 ~ {\rm msec}$となります！!

では逆にビジネスの要件で指定した「95パーセンタイル時間が$200~{\rm msec}$以内に収まる」$\mu$と$\lambda$の範囲はどれくらいなのでしょうか？これはポッド数を固定して、$\mu-\lambda$平面に対する$W_{95}$を計算し、SLOでのcontourをとればいいです。いくつかのポッド数$c$に対して計算してやれば、$c$ごとの$\mu$と$\lambda$の性能の許容範囲が図示されます。

縦軸はリクエストの到着率$\lambda$、横軸はポッドの処理のサービス率$\lambda$です。この図は右下の領域であればあるほど安全な系ということを示しています。リクエストが少ないほど（図の下らへんの領域）、そしてポッドの処理性能が高いほど（右側）、リクエストがスムーズに処理されてことが想像できるのではないでしょうか？☺️

※簡単のために、コストの観点は本件では考慮していません。想定としては、図の右側に禁止区域が現れるはずです。

結果

本記事で用いた待ち行列理論と具体的な計算例から、いくつかの知見が得られました。

第一に設定したSLO（今回は例として95パーセンタイル応答時間が200msec以内を採用）、リクエスト到着率$\lambda=100 件/{\rm sec}$、ポッドの処理能力$\mu=20 件/{\rm sec}$という条件下で、SLOを達成するために最低限必要なポッド数は6つであることが理論的に示されました。ポッド数が5つの場合、系の利用率$\rho = \lambda/(c\mu) = 100/(5 \times20) =1$となり、リクエストを捌ききれず待ち行列が無限に増大するため、そもそも安定稼働しません。ポッド数を6つに増やすことで初めて利用率が1を下回り($\rho=5/6 \simeq 0.83$)、計算上の95パーセンタイル応答時間は約 $138~{\rm msec}$となり、目標の$200~{\rm msec}$をクリアします。

次に、ポッド数を固定した場合に、SLOを満たすリクエスト到着率 ($\lambda$) とポッドの処理能力 ($\mu$) の関係を可視化したのが、先の $\mu−\lambda$平面のグラフです。

この図の各線は、指定したポッド数 ($c=6,8,10$) において、95パーセンタイル応答時間がちょうど$200~{\rm msec}となる$ ($\lambda, \mu$)の組み合わせ、すなわちパフォーマンスの境界線を表しています。

• 曲線の右下の領域: 安全領域です。この領域では、リクエストの到着が比較的少ないか、ポッドの処理性能が高いため、システムはSLOを満たし安定稼働します。
• 曲線の左上の領域: 危険領域です。リクエストが多すぎるか、処理性能が追いついていないため、応答時間がSLOを超過してしまいます。

この図は、システムの性能要件を考える上で有用になる可能性があります。例えば、「秒間200リクエスト ($\lambda=200$) までは耐えられるようにしたい」という目標がある場合、グラフの縦軸$\lambda=200$の線を見れば、ポッド数に応じてどの程度の処理性能 ($\mu$) が必要か、あるいはその逆も一目で見積もることができます！これにより、勘や経験則に頼らず、定量的な根拠に基づいたキャパシティプランニングが可能になります。

まとめと展望

この記事では、GKE上のポッドの適切な数を決定するという実務的な課題に対し、待ち行列理論（M/M/cモデル）という数理モデルを適用し、演繹的に解を導出するアプローチを試みました。

具体的なSLOと性能要件（リクエスト到着率$\lambda$、ポッドの処理能力$\mu$）を設定することで、安定稼働に必要な最小ポッド数や、目標応答時間を達成するための性能限界を理論的に見積もれることを示しました。この手法は、感覚的なサイジングを排し、ビジネス要件と技術的性能を直接結びつける定量的な意思決定を可能にする可能性があります。

Future workとしては、いくつかの発展的なテーマが考えられます。

まず、理論と現実の比較検証が不可欠です。実際にGKE環境で負荷試験を行い、ここで導出した理論値と実測値のパフォーマンスを比較・評価することで、モデルの妥当性や限界を明らかにできます（今はお金がない泣）。

次に、モデルの精緻化です。今回は最もシンプルなM/M/cモデルを仮定しましたが、現実のトラフィックは必ずしもランダム（ポアソン分布）ではなく、特定の時間に集中するバーストな振る舞いを示すことは十分に考えられます。また、処理時間も常に指数分布に従うとは限りません。より現実に近い分布（例えば、M/G/cモデルなど）を適用することで、さらに精度の高い予測が可能になるでしょう。

最後に、コスト最適化と動的スケーリングについても考える余地があります。本記事ではコストを度外視しましたが、実運用ではパフォーマンスとコストのトレードオフが常に問われます。今回のモデルにコストの概念を加え、費用対効果が最も高いポッド構成を模索することが考えられます。また、定常状態だけでなく、リクエストの増減に応じてポッド数を動的に変えるオートスケーリング（HPA）の挙動をモデル化し、スケールアップ・ダウンの最適な閾値やタイミングを理論的に決定することもできるもしれません。

参考文献

• https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.40_11_649.pdf
• https://www.scirp.org/journal/paperinformation?paperid=51426
• https://queue.acm.org/detail.cfm?id=2898444
• https://cloud.google.com/kubernetes-engine?hl=ja#deploying-and-running-applications

付録

図出力用のスクリプト

https://github.com/inuverse44/kubernates-queueing-theory

ポアソン分布の導出

観測時間を$T$を$T = N \Delta t$のように$N$分割しておきます。この$\Delta t$中にリクエストされる確率は十分小さいとします。また単位時間あたりの平均リクエスト数を$\lambda$とします。この時、$\lambda \Delta t$は$\Delta t$秒間にリクエストが1回来る確率と解釈できます。

$\Delta t$中に$p = \lambda \Delta t$という確率でリクエストが到達するということは、2項分布を考えることができます。どういうことかというと、$\Delta t$にリクエストが来る確率を$p$と表せるということは$1-p$がリクエストが来ない確率です。すると、その確率分布は次のように求められます：

$$p_i = {}_N C_i$$

指数分布の導出

（今後の更新に期待）

ErlangのC式