(cache)PHPUnitを高速化するための調査で二分探索を使う日が来るとは - Cybozu Inside Out

CIはどれだけ速くてもいい

こんにちは。サイボウズで大規模向けグループウェア「Garoon」を開発している赤間です。

私たちのプロダクトには、PHPUnitのテストケースが15,000件以上、テストファイルは1,500以上あります。これらを4並列のCIで回しても、PHPUnit本体で約5分程度かかっていました。

この記事は、その4並列のPHPUnit実行時間を1並列1分まで短縮した方法を解説します。一言でまとめると、テストケース間の副作用をすべて解消し、PHPUnitのprocess isolationをオフにしました。そして、その過程で最大の難関だった、どのテストが副作用を持っているのか分からない問題を、乱択と二分探索で解決しました。

process isolationによるプロセス起動コスト

process isolationとは

PHPUnitには、テストケースを1件ずつ別のPHPプロセスで実行する仕組み (processIsolation) があります。これを有効にすると、テストごとにプロセスを起動するため、global変数やstatic変数など、プロセス内に蓄積されるあらゆる状態が毎回リセットされます。つまり、テストがどれだけ行儀悪く状態を汚しても、次のテストには影響しません ¹。

その代償がプロセス起動のオーバーヘッドです。テスト1件ごとにPHPプロセスの起動、autoloaderの初期化、ブートストラップの読み込みが走ります。

1件あたりのコストはわずかに見えても、15,000件分のオーバーヘッドがテスト全体の実行時間を大きく左右します。実際に計測すると、テスト本体のロジックよりも、プロセスの起動と初期化に大半の時間が費やされていました。

process isolationを切ることの難しさ

このことは以前からも問題になっており、何度かprocess isolationを無効にする試みは行われてきました。しかし単純に無効化してPHPUnitを回すと、ある時点でテストがエラーで失敗してから後続のテストが派手に壊れる状態となり、どこから手をつければいいか分からない状態になる、という経験をしました。

確実に発生しているであろう副作用を直そうとしても、どこで発生しているかの特定、および修正していく戦略を練ることは難しく、片手間で太刀打ちできるものではありませんでした。

副作用をどうやって特定し、修正していくか

テストの副作用の修正を行うにしても、どのような問題があるか、どれくらいの規模の修正が必要かを見積もる必要があります。そこでまずは現存のPHPUnitテストケースを調査し、process isolationを切ることが現実的かどうかを見積もることからスタートしました。

副作用を引き起こす犯人を見つけよう

process isolation無しでPHPUnitを実行するシチュエーションを考えます。実行途中にあるテストが失敗したとします（もちろん、すべてのテストは単体で実行すれば成功します）。

図で描くとこのような状況です。

このテストよりも手前に実行したテストのどれかが副作用を持っていた、いわば容疑者に違いません。そのようなテストをどうすれば効率的に発見できるでしょうか？

伝家の宝刀：二分探索

もちろん二分探索です。こういった状況においては二分探索を使って効率的に犯人を絞り込めます。

失敗したテストを $𝐴$ とします。これより以前に実行したテストのリストを $𝑆$ と置き、 $𝑆$ の前半 $𝑆 1$ 、Sの後半 $𝑆 2$ に分割します。そして $𝑆 1 + 𝐴$ 、つまり $𝑆 1$ を実行した最後に被害者 $𝐴$ を実行すると、成功したかどうかで $𝑆 1$ に犯人がいるかどうかがわかります。同様に $𝑆 2 + 𝐴$ も実行して結果を確かめれば、成功する方の部分リストには犯人はいないことになります。²

これを繰り返すことでテスト $𝐴$ を失敗させるテスト $𝑋$ を得ることができます。

以後、あるテスト $𝑋$ があるテスト $𝐴$ を失敗させるような状況において、テスト $𝑋$ を加害者、テスト $𝐴$ を被害者と呼ぶことにします。

アルゴリズム全体の概要

前述の方法を使い、プロダクトのテストケースから加害者をすべて洗い出すことを考えます。実際の手順は次のようになりました。

全テストからランダムに $𝑘$ 個を取り出し、直列に実行する
失敗したテスト $𝐴$ （被害者）と、それ以前に実行されたテスト集合 $𝑆$ （容疑者）を得る
前述の方法で加害者を発見し、マークして除外する
手順1で全テストが成功したら $𝑘$ を増やして手順1に戻る。失敗したら $𝑘$ を少し減らして手順1に戻る
$𝑘$ がテストの総数を超えたら、すべてのテストを昇順、降順で実行し、成功したら終了する

ステップ1で乱択を使っている理由は以下の3つの条件を簡単に満たすことができたからです。

1回の実行で1個の被害者しか見つけることができないため、最初に直列に実行するテストの個数を必要最低限にできる
先頭から順番に被害者・加害者を取り出していくと、それらの濃度の薄い区域ができるが、そういった状況を避けることができる
加害者を実行した後に被害者を実行するという位置関係の条件を気にしなくともよくなる

今回はシンプルな乱択アルゴリズムを使いましたが、もっと工夫すれば良い方法があるかもしれません。ともあれ、これですべての加害者と、加害者それぞれに対応する被害者を得ることができました。

加害者のパターンの分析

こうして得られた加害者と被害者の集合をいっしょくたにして、1対1の総当たりでPHPUnitを実行して加害者-被害者関係を構築します。そうすると九九の表のようなグラフが出来上がります。

加害者と被害者の関係を図示した結果を抜粋したもの。列方向に加害者が、行方向に被害者が並んでいる。

例えばこのグラフの一番上の行を見てもらうと、1つの被害者に多く共通する加害者がいることがわかります。

実行にはコストがかかりますが、こうすると共通の被害者を得ることで加害者を分類できます。この分類をすることが、どのような副作用によって被害者が生まれたかを知る大きな手がかりとなりました。

また、テストごとの問題よりも共通で実行されるコードに問題があるだろうという大まかな予想もついたため、副作用を最後まで修正可能だと判断し、実際の修正作業に着手しました。

加害者の共通点

こうして特定した加害者たちを並べてみると、副作用にはいくつかの類型がありました。

global/static変数の書き換え
ob_start() 関係の関数による出力バッファの干渉
DBへのコミット
uopzによって施されたモックの残留

最も影響が大きかったのはstatic変数の書き換えでした。これに関しては地道に修正を重ね、他のテストを失敗させるような副作用がなくなるまで修正を続けました。

責任の所在を分けて考える

static変数の書き換えは、直し方に応じてさらに3パターンに分けられました。

明示的な設定変更：加害者側のテストが意図的に設定値を書き換えていたなら、その加害者のtearDownで設定値を復元させました。
不安定なデフォルト値への依存：初期値がたまたま都合よく振る舞っていただけなら、被害者側の責任として、テスト自身が必要な値を明示的に設定するように直しました。
暗黙的なキャッシュ：プロダクションコード内部のキャッシュが原因の場合はどちらの責任でもないため、共通の初期化処理を用意して吸収しました。

テストコードの修正のレビューでは、どのように修正するべきかの議論がたびたび発生しました。その際に誰の責任であるかという観点を導入し、上3つの分類のどれに当てはまるかによって修正方針を決めることとしました。

成果：4並列5分から1並列1分へ

他のテストを失敗させるような副作用を取り除き、ついにCI環境でもprocess isolationをオフにしました。結果、セットアップや後始末を除いたPHPUnitそのものの実行速度を大きく高速化することができました。以前は4並列でPHPUnitのCIジョブを実行していましたが、1並列でも十分な速度が得られました。

元々4並列で5分かかっていたPHPUnit本体ですが、1並列で1分となり、トータルの実行時間はおよそ20分の1になりました。

	Before	After
process isolation	有効	無効
PHPUnit本体の実行時間	約5分 x 4並列	約1分 x 1並列

最終的にユニットテスト修正のPull Requestは90本になり、修正自体は3人のチームで1〜2ヶ月で完了しました。

まとめ

私たちのプロダクトにおけるPHPUnitのCIジョブが遅かった原因はprocess isolationのプロセス起動コストであり、それを取り除く鍵は「見えない副作用を探索アルゴリズムを用いて可視化する」ことでした。結果的にCI待ちの時間も短くなり、さらにCI自体の負荷も下げることができました。

個人的には、業務で二分探索や乱択といったアルゴリズム的なテクニックを活用できて満足度が高かったです。この記事が同じ悩みを抱えている方の参考になれば幸いです。

もちろん、ファイルIOやDBへのコミットなどはプロセスを跨ぐ副作用であるため残ります。↩
両方とも成功した場合、 $𝑆 1$ のどれかと $𝑆 2$ のどれかのテストの共犯だと考えられます。稀に発生しますが数は多くなかったため、失敗したテスト自体を除外して続行することにしました。↩

Cybozu Inside Out | サイボウズエンジニアのブログ

PHPUnitを高速化するための調査で二分探索を使う日が来るとは