この記事は、ユニファ Advent Calendar 2021の15日目の記事です。 adventar.org
こんにちは。プロダクトエンジニアリング部のちょうです。
今回は、皆さんがRubyで開発するときよく使うbundlerについてすこし中身を深堀りして説明したいと思います。bundlerはGemfileに基づいてライブラリつまりgemをダウンロードしてくれますが、その中身はどうな仕組みで依存関係のあるライブラリをダウンロードするのかに興味ありませんか。何も設定せずbundle installを実行したら、順番的にダウンロードしますが、jobsオプションを1以上の数字に設定することで並列でダウンロードしてくれます。
私は以前この記事で依存関係のあるリソースを並列で作成するとき、依存関係を示すグラフにサイクルがあるかとリソースが作成したあとどういう形で依存関係に沿った順番でほかのリソースを作成し始めるかを重点的に説明しました。今回もこの2つについてbundlerの内部の仕組みをみてみたいと思います。
依存関係からサイクルの検出
公開されているコードから、Tarjan's algorithm for strongly connected componentsというアルゴリズムを使っていることがわかりました。アルゴリズム自体はwikipediaなどで調べるのでここで割愛します。
順番的にダウンロードと並列でダウンロード
まず注意すべきなのは、bundle installを実行するとき,複数スレッドで実行するのを指定していない場合でも、ParallelInstallerというクラスでダウンロードします。複数実行はWorkerのインスタンスを作成し、中身はWorkerPoolで複数スレッドを管理します。
WorkerPoolは2つのキューを経由して、メインスレッドからダウンロード対象を受け取り、ダウンロードしたらその結果をキューでメインスレッドに通知します。依存関係のあるリソースはすべてダウンロードしたいライブラリを一気にキューにいれることができなくて、あるライブラリをダウンロードし終わったら次のライブラリを開始可能かどうかを確認します。そのため、ここのレスポンスキューが必要です。
ロックが使っていないように見えますが、レスポンスキュー自体は一つ大きなロックです。MRIでしたらVMにロックもありますので、もうちょっと小さいロックはできない、もしくはできてもあまり意味がないと思います。ただ、次のダウンロード対象を見つがるにはすべての対象をチェックしていて効率は悪そうなので、もっとグラフっぽいデータ構造にしたほうがいい印象です。
まとめ
いかがですか。近くてもグラフ関連のアルゴリズムが使われていて、そしては依存関係のあるリソースをどうやってダウンロードするのも興味深いですよね。実際にこんな機能を実装する機会がなくても、中身をみてすこし勉強になってもいいと思います。
--
ユニファでは新たな仲間を積極採用中です。
詳細についてはこちらからご確認ください。