Twitterを眺めていたら、Uberでのモノリポのビルドを常にグリーンに保つための取り組みを紹介した論文についてのツイートを見かけて、面白そうだったので読んでみました。

読んだ論文はこちらです:Keeping Master Green at Scale

そもそもモノリポとは?

モノリシックリポジトリ(Monolithic Repository)の略で、ある企業の中で作られている全てのソフトウェアや、ある製品に関する全てのソフトウェアを1つのリポジトリにまとめる手法です。この手法自体の是非はひとまずおいておきますが、有名どころではGoogleやFacebook、Twitter、Uberがこの手法を使っているそうです。

モノリポについては、Googleがその理由を書いた記事があるようなのでこちらを読むと良いかもしれません(私はまだ読んでいないのでそのうち読んでみます):”Why Google Stores Billions of Lines of Code in a Single Repository

Uberが抱えていた問題

この論文で例として挙げられているのは、Uberの運転手向けのiOSアプリです。このアプリはモノリポで管理されていて、リポジトリ全体ではピーク時には数分間に数百の変更が行われる(平常時でも1時間に数百の変更が行われる)というような規模だそうです。

当然開発時にはフィーチャーブランチを切ってそのブランチに対するCIは回していますが、このくらいの数の変更が行われると、masterブランチがどんどん進んでいくのでフィーチャーブランチ上でのビルドとmasterにマージしてからのビルドの結果が異なるということが起こりえます。また、同時並行するフィーチャーブランチの数も多いのでコンフリクトが起きる可能性も高まってきます。そのため、Uberのこのアプリではmasterのビルドがグリーンの状態の時間が52%しかなかったそうです。下図はある1週間における1時間辺りのビルド成功率を時系列にプロットしたものです。これを見ても結構な割合でビルドが落ちている状態であることがわかります。

ビルド成功率

ビルド成功率

ビルドがグリーンでない状態が半分近くあるということは、それだけ開発者の生産性は下がります。このビルドが常にグリーンではないという問題を解決するのがこの論文の主旨です。

解決手法

まず開発者が書いた変更のレビューが通ったら、その変更をいきなりmasterにマージするのではなく、キューに積むようにします。そして、このキューに積まれた変更の内容をmasterにあててビルドした結果成功するものは実際に取り込み、失敗したものは取り込みを行わないという選別を行うことでmasterを常にグリーンに保つことが出来ます。

開発の流れ

開発の流れ

しかし、単にキューに積まれた変更を順番にビルドしていったのではキューに積まれる変更の勢いに追いつきません。そこで、この論文の著者たちはSubmitQueueというシステムを開発しました。

SubmitQueue

SubmitQueueの基本的なアイデアとしてはキューに積まれている変更のビルドを投機的に並行で実行していくというものです。ただ、無鉄砲に投機実行をしていくと状態の数が爆発してしまうので、いかに状態の数を減らしたり無駄な投機をしないかというのが肝になってきます。

ここで例として、今キューに $C_1$ 、 $C_2$ 、 $C_3$ という順番で3つの変更が積まれているとします。そしてmasterの最新をHEADと呼ぶことにします。そして、HEADに $C_i$ の変更を加えたビルドを $B_i$ と呼ぶことにします。また、 $B_{i,j}$ と書いた場合にはHEADに $C_i$ と $C_j$ の変更を加えた状態でのビルドを指すものとします。

まだこの $C_1$ 、 $C_2$ 、 $C_3$ の変更を取り込んだビルドを行っていない状況では、それぞれの変更を取り込んだ結果ビルドが成功するかどうかに応じて、これから行う可能性のあるビルドの場合の数は下図のように7個あります。このような2分木をこの論文では”Speculation tree”と呼んでいます(多分一般的に使われる用語じゃないですよね?)。

Speculation tree

Speculation tree

キューに積まれる変更の数を $n$ とすると、行われる可能性のあるビルドの場合の数は $2^n - 1$ 個になるので、すべての場合を投機的にビルドすることは現実的ではありません。

そこで、SubmitQueueでは2つの手法を使ってこの投機的実行を効率化しています。

  • それぞれの変更をmasterのHEADに取り込んだ時のビルドが成功する確率を機械学習で求め、それを元に優先的に実行するビルドを決める
  • 変更同士がコンフリクトしているかどうかを計算し、コンフリクトがない場合はSpeculation treeの枝刈りをする

それぞれどういうことかを説明します。

それぞれの変更によるビルドの成功する確率

まずロジスティック回帰を使って、masterに各変更を取り込んだ際のビルドの成功確率を予測します。

先程のFigure 5の例で言うと、例えば $B_1$ は成功する確率が高いとします。その場合はSpeculation treeの2段目では $B_2$ よりも $B_{1,2}$ を優先してビルドした方がその後の役に立つ確率が高いと言えます。なぜかと言うと、 $B_1$ が成功する確率が高いということはSpeculation treeの右側に進む可能性が高いためです。

このようにして、Speculation tree上のビルドに優先度を付け、優先度の高いものたちだけを並行して投機的に実行することで、その投機が成功する確率を高める訳です。

Uberの例では97%の精度で各変更のビルドが成功するかどうかを予測できているそうです(このくらいの精度で予測できるならビルドせずに弾いてしまうという手法も有りうるのではとも思いましたが、3%の変更は間違って弾かれてしまいますし、なにより単なる予測では弾かれた理由がわからないというのが厳しいので、やっぱりビルドを実行する必要があるのだろうと推測しました)。

変更同士のコンフリクトの検出

$C_1$ と $C_2$ の変更がコンフリクトしないとします。そうすると、 $B_1$ と $B_2$ の結果から $B_{1,2}$ の結果を導くことができるので $B_{1,2}$ のビルドは実行する必要がありません。なぜなら、 $C_1$ と $C_2$ は独立しているので $B_1$ と$B_2$ が両方成功すれば $B_{1,2}$ も成功するはずで、 $B_1$ と$B_2$ のどちらか(もしくは両方)が失敗すれば $B_{1,2}$ は失敗するはずだからです。

このようにキューに積まれている変更同士がコンフリクトしているかどうかを調べることで、Speculation tree上のビルドで不要なものを見つけることができ、枝刈りをすることができます。

SubmitQueueの効果

詳細な結果は元論文を参照頂くとして、ざっくりいうとこういった効果があったそうです。

  • masterを常にグリーンに保つことに成功
  • SubmitQueueに変更を登録してからビルドの結果がわかるまでの時間はほぼ1時間以内(キューに登録される頻度による)※

※ 論文中にこの時間は明記はされていないので実験結果のグラフから私が推測した値です。

まとめ

Uber社内でのモノリポのビルドの仕組みについての論文の内容を紹介しました。いかにうまくビルドの投機的実行を行うかという所がこの論文の肝ですね。

また、感想としてはここまでやれる会社じゃないとモノリポを運用するのは大変なんだろうなと思いました。そもそもモノリポを管理するためのバージョン管理システムもTwitterはGitにパッチを当てたりFacebookはMercurialにパッチを当てているらしいので、かなりのエンジニアリングリソースがないと現状はモノリポにはデメリットの方が大きそうに思います。ここまでしてモノリポを続けるメリットがまだはっきりと理解できていないので、次はモノリポのメリットについて調べてみたいと思います。