M/M/c キューモデルでコネクションプールのサイジングをしてみた

はじめに

全国のサーバーサイドエンジニアのみなさんにおかれましては日々、キュー付きスレッドプールやコネクションプールのサイジングにお悩みかと思います。私もその一人です。ワーカースレッドの数は何個がいいのか、キューは1つがいいのか、優先度付きがいいのか、などなど悩みはつきません。

今回はHTTPクライアントのキュー付きコネクションプールの最大コネクション数サイジングをM/M/cキューモデルを使ってやってみました。

キュー付きコネクションプール

ここではキュー付きのHTTPコネクションプールを持つHTTPクライアントを想定します。このクライアントでは、HTTPクライアントに送信されたリクエストに対してプールからコネクションを引き当てリクエストを送信します。レスポンスを受信したらコネクションは解放されて別のリクエストの送信に使うことができます。リクエストを受信した時に引き当て可能なクライアントがない場合にはリクエストはキューに送信され、先頭から処理されていきます。

M/M/cキューのモデル

M/M/cキューについてはモバイルアプリのスレッドプールサイズの最適化（画像読み込み編） やM/M/c queue の説明がわかりやすいです。今回は以下のようにパラメータを設定します。

到着率 λ: 単位時間あたりのリクエスト数
サービス時間 μ: HTTPリクエストの応答時間
サービス数 c: コネクションプールのコネクション数

M/M/c queue によるとリクエストがキューに滞留する確率 Cおよびインフライトとキューに滞留しているリクエスト数の合計の平均はそれぞれ以下の式で表せます。

M/M/c モデルではキューの長さが無限であると想定しています。実際のHTTPクライアントではキューの長さは有限なので別のモデルを使う必要があるのですが、今回は単純化と私の理解が追いついていないためM/M/cを使いました。

ソースコード(python)と計算結果

上記の滞留リクエスト数を求める式をpythonで実装したものが以下です。

from scipy import special
import numpy as np

# 計算時のエラーをraise
np.seterr('raise')

def avg_waiters(rambda, mu, c):
  """
   M/M/c 待ち行列の平均キュー滞留数、サービス中滞留数を計算する
   Parameters
   ----------
   rambda 単位時間あたりの平均到着率(e.g. リクエスト数)
   mu 単位時間あたりの平均サービス率 (e.g. レイテンシの逆数)
   c 窓口数 (e.g. サーバ数, プールサイズ)
   -----------
   returns [待ち行列の平均キュー滞留数、サービス中滞留数, 平均利用率]
  """
  rho = rambda / (mu* c)
  def C():
    s = np.sum(np.vectorize(lambda k: np.power(c*rho, k)/special.factorial(k, False))(np.arange(0, c)))
    deno =  1 + (1-rho) * (special.factorial(c, False)  / np.float_power(c*rho, c)) * s
    return 1 / deno
  # in queue, in service, rho
  return [rho / (1 - rho) * C() , c * rho, rho]

この関数を使ってコネクション数を変えた場合に滞留するリクエスト数がどうなるかをみてみます。

import pandas as pd
import matplotlib.pyplot as plt

# 1分あたりのリクエスト数(λ)
rambda = 5000
# １分間の平均サービス率(レイテンシmsの逆数)
mu = 60*1000/500

#200超えると204付近でオーバーフローするので200まで
df = pd.DataFrame({'c': np.arange(5, 100, 1)})
df[['in_queue', 'in_service', 'rho']] = df.apply(lambda r : avg_waiters(rambda, mu, r['c']), axis=1, result_type='expand')
df = df[df['rho'].between(0, 1)]

# 各数値をプロット
fig = plt.figure(figsize=(10,15))

for i, fs in enumerate(['rho', 'in_service', 'in_queue']):
  ax = fig.add_subplot(3, 1, i+1)
  ax.plot(df['c'], df[fs], label=fs)
  ax.legend()
fig.tight_layout()

出力は以下のようになります。コネクション数50付近でキュー内の滞留リクエスト数が0に近くなるのがわかります。利用率ρが0.5以下になるのはコネクション数80以上なので余裕を持つならコネクション数はこの辺りの数にした方がいいかもしれません。

まとめ

待ち行列はIPAの試験対策でチラッとみたことあるなレベルでしたが手探りでpythonでの計算をしてみました。可能であれば実際にHTTPクライアントをプログラムを使って計算結果の妥当性を確かめてみようと思います。