依存関係アップデートにおける QA テストのバッチサイズを最適化する

はじめに

わたしの所属するチームでは Renovate を用いて依存関係のバージョンアップ Pull Request を自動生成しています。 また、プロダクションコードに一定の影響を与える更新に対しては QA チームによるテストを実施して品質を担保しています。
QA テストにおいては Renovate が作成した複数の Pull Request をまとめてバッチ化することで効率化を図っています。 このとき、どのくらいのバッチサイズが最もコスト効率が高いかは感覚で決められがちです。

本記事では、最もシンプルな前提から数学モデルを構築し、最適バッチサイズが概ね $n^{*} \approx 1/\sqrt{p}$（$p$: 単一の Pull Request がリグレッションを起こす確率）に比例することを導出します。

前提と記号

記号	意味
$n$	1 回のバッチに含める Pull Request の数（バッチサイズ）
$p$	単一の Pull Request がリグレッションを引き起こす確率（$0 \leq p \leq 1$）
$c$	QA テスト 1 回の実行コスト

運用仮定

以下のようなシンプルな運用を仮定します。

1. バッチ（サイズ $n$）をまとめて 1 回テスト
2. テストが成功したら終了
3. 失敗したら各 Pull Request を個別に再テスト（$n$ 回）

期待コストの導出

バッチ化したテストの失敗確率は $1 - (1-p)^n$ 。

テスト実行回数の期待値:

$$E[T(n)]= 1 + n\bigl(1 - (1-p)^n\bigr)$$

テストコスト期待値:

$$E[C_{\text{test}}(n)]= c\Bigl[1 + n\bigl(1 - (1-p)^n\bigr)\Bigr]$$

単一 Pull Request あたりに正規化:

$$\bar C(n) = \frac{E[C_{\text{test}}(n)]}{n} = c\left(\frac{1}{n} + 1 - (1-p)^n\right) \equiv c\,f(n)$$

よって $f(n)=\frac{1}{n} + 1 - (1-p)^n$ を最小化する $n$ が最適バッチサイズとなります。

期待コストの可視化

いくつかの $p$ につき $f(n)=\frac{1}{n} + 1 - (1-p)^n$ のグラフを以下に示します。

• $f(n)$ は下に凸の関数
• 小さい $p$ ほど最適バッチサイズ $n$ が大きい
• 小さい $p$ ほど最適バッチサイズを採用した際のコスト期待値が小さい

例えば $p = 0.01$ のとき、最適バッチサイズ $n$ は 10 前後で、単一 Pull Request あたりおおよそ $0.2c$ のコスト期待値で対応できることがわかります。

最適条件と厳密解

$f(n)=\frac{1}{n} + 1 - (1-p)^n$ を最小化する $n$ を求めます。

$$f'(n) = -\frac{1}{n^{2}} - (1-p)^n \ln(1-p) = 0$$

$a = -\ln(1-p) > 0$ とおくと $(1-p)^n = e^{-a n}$ なので

$$a n^{2} e^{-a n} = 1$$

$x = a n$ とすると

$$x^{2} e^{-x} = a$$

Lambert $W$ 関数（$W(z) e^{W(z)} = z$）を用いて整理すると

$$n^{*} = -\frac{2}{a} W\!\left(-\frac{\sqrt{a}}{2}\right), \quad a=-\ln(1-p)$$

これはモデルに対する連続最適解の解析的表現です。

小さい $p$ に対する近似

小さい $p$ では $a \approx p$、さらに $W(-\epsilon) \approx -\epsilon$（$\epsilon \to 0^+$）より

$$n^{*} \approx \frac{1}{\sqrt{p}}$$

実務上は「リグレッション率 $p$ の平方根の逆数」を目安にバッチサイズを設定し、近傍の整数（±1）を試すのが簡便です。

例

$p$	$1/\sqrt{p}$ 近似	推奨バッチサイズ（例）
0.01	10.00	10
0.02	7.07	7〜8
0.05	4.47	4〜5
0.10	3.16	3

連続最適値・整数最適値・近似の比較

横軸に $p$、縦軸に $n^*$ を取ったグラフを以下に示します。
黄色の実線が連続最適、オレンジの実線が整数最適、赤い破線が近似 $1/\sqrt(p)$ を示します。

• 小さい $p$ ほど最適 $n$ は急速に増加する
• 近似 $1/\sqrt{p}$ は広い範囲で連続最適に密接する
• 実務は整数制約なので階段状に変化する

リグレッション率はバージョンアップの変更度合いやそのパッケージへの依存度などにより異なるため、過去数週間〜数ヶ月の実績を元に推定するとよさそうです。

まとめ

前提としたシンプルな運用において、依存関係アップデートの QA テストの最適バッチサイズは、リグレッション率 $p$ の平方根の逆数 $1/\sqrt{p}$ を目安に設定するとよいことがわかりました。 連続最適値・整数最適値・近似値の比較からも、広い範囲でこの近似が有効であることがわかりました。 実際には過去のリグレッション実績をもとに $p$ を推定し、近傍の整数値（±1）を試すとよりよいでしょう。