Gitリポジトリを高速化する技術

Gitリポジトリが大規模になると、各種操作のパフォーマンスが低下します。本記事ではパフォーマンスを支えるデータ構造や、パフォーマンスを向上させる実践的なテクニックをいくつか紹介します 🎉

📈 Commit Graphs

コミットグラフ（Commit Graph）とは、Git オブジェクトの中でも、コミットオブジェクトについての探索を効率化するための仕組み（ファイル）です。コミットグラフは、データベース分野でいうところのインデックスとほぼ同じものだとイメージしてもらってよいです。

GitHub 社のブログにコミットグラフの概念図があるので紹介します。本記事で重要なカラムは、 Object ID と Parent 1 です。Object ID とはコミットオブジェクトのハッシュのことです。そして親コミットオブジェクトのハッシュが「Parent1」になります。また Object ID が辞書順に並んでいる点もポイントです。

出典）Git’s database internals II: commit history queries

上記の場合、0 行目（0-Origin で）は 2 番目のコミットオブジェクトを指しています。これはつまり、2 行目のコミットオブジェクトが親であることを意味し、つまり 2 行目のコミット → 0 行目のコミットという順序関係があることを示しています。

これらの情報を踏まえると、下記の工夫がコミットグラフのファイルからは見て取れます。

オブジェクトのデータのハッシュ値を辞書順で並べておくことで、特定のオブジェクトを検索するときに二分探索が可能になる
ある特定のコミットオブジェクトを探索するときに、親コミットをオフセット値で辿っていけばよく、コミットグラフファイルの検索で効率よく完結する

v2.42 時点では、デフォルトで作成されるため、特にこちらで設定する必要はありませんが、興味深いのでコミットグラフの仕組みについて紹介しました。また、コミットグラフでは、世代番号によるコミットオブジェクトの枝刈りや、Bloom Filter による探索のスキップなどの効率化も行われています。

公式ドキュメント

https://git-scm.com/docs/commit-graph-format/en

⏲ FS-Monitor

v2.38 で導入された仕組みで、 git status や git add などのステージングエリアの操作関連のパフォーマンスを改善するものです。

git addやgit resetのインデックス操作は、.git/indexというファイルに情報が格納されます。そして、git statusなどのコマンドを使用して、追跡しないファイルやインデックスされた（ステージングエリアに移動した）ファイルを確認する際には、.git/indexをチェックし、保存されているワークツリーを探索する必要があります。この作業はワークツリーをルートから探索する必要があるため、線形時間の計算量が必要になります。

そこで、バックグラウンドでプロセスを起動しておいて、リポジトリ内のファイルの変更を検知し、バックグラウンドのメモリ上に保存します。そして git status などのコマンド実行時には、このバックグラウンドのプロセスとの IPC 通信を行うことで、 .git/.index を探索する代わりに対象のデータを返すことができるものです。

GitHub 社によるパフォーマンス検証の結果を以下に紹介します。上位３つの棒グラフが FSMonitor を利用していない場合、下記３つが利用した場合の git status の性能になります。大きく性能が向上していることが見受けられます。

出典) Improve Git monorepo performance with a file system monitor

デメリットとしては、バックグラウンドでプロセスを起動し続けていなければいけないことです。休止してしまえば、ファイルの更新の検知ができないため、結局はワークツリーを先頭から辿る必要があります。

v2.42 の時点では、常駐プロセスということもあり、デフォルトはオフになっています。git config core.fsmonitor true を実行すれば、次回の Git コマンド操作から自動で開始されます。

公式ドキュメント

https://git-scm.com/docs/git-fsmonitor—daemon

⌛ Scheduled background maintenance

Git 2.28 より追加されたコマンドが git maintenance です。現在でも Git では、定期的に .git ディレクトリをメンテナンスする処理が実行されています。

具体的に行われる処理としては、

単一の Git オブジェクトのファイル（Loose object）を Packfile にまとめる
到達不可能になったオブジェクトを削除する

などの掃除（ガーベジコレクション）を行います。

しかし、ガーベジコレクションをするタイミングは、コマンドを実行するタイミングなので、場合によっては作業を長い時間ブロックする可能性があります。これを防ぐためのコマンドが git maintenance です。

v2.42 時点では、デフォルトでは無効になっています。git maintenance start コマンドを実行すると、そのリポジトリで有効になり、定期的にバックグラウンドでメンテナンスするように適切な設定をしてくれます。

設定項目のキー名がややこしいのですが、デフォルトでもmaintenace.auto というフラグは true になっています。これは通常のコマンドの実行時に自動で git maintenanceをオンデマンドで実行するための設定です。

また戦略（Strategy）を選択することも可能です。例えば、 incremental という戦略を選択すると、よりアグレッシブなクリーンを実行してくれます。

バックグラウンドで最新オブジェクトを fetch する
commit-graph を 1 時間に 1 回更新する
Loose Object をまとめて Packfile を作成 / 更新する
自動で行われるgit gc を無効化する

などの処理を自動で行うようになります。また設定さえ変更すれば、特定の処理を頻繁にさせたり、逆に処理しないように指定したりも可能です。

公式ドキュメント

https://git-scm.com/docs/git-maintenance

📁 Shallow Clone / Partial Clone

デフォルトでは、git clone はリモートリポジトリから、すべてのオブジェクトを取得します（Full Clone）。ファイルのデータを圧縮した Blob オブジェクトというオブジェクト以外にも、前述したコミットオブジェクトなどの種類のオブジェクトがダウンロードされます。

Full Clone では、過去のデータを含む履歴のスナップショットをすべて取得するため、非常にダウンロードに時間がかかる場合があります。しかし、」CI/CD でビルドするためにリポジトリから Clone したい場合」や「手元で動作させてみたい場合」など、履歴情報は不要で最新のオブジェクトだけでもよい場合もあります。

Shallow clone という方法を使えば、リモートリポジトリから最新のオブジェクトのみを取得するため、git clone の時間を短縮することができます。以下のようにコマンドを実行します。

$ git clone -depth=1 <url>

ただし、履歴情報を必要とする git diff や git log のようなコマンドを使用すると、必要なオブジェクトがそのタイミングでダウンロードされるので注意が必要です。

シャロ―クローンの例 Shallow Clone （出典）Get up to speed with partial clone and shallow clone

※ 〇がコミットオブジェクト、△ がツリーオブジェクト、□ がブロブオブジェクトです

Partial Clone とは、特定のオブジェクトのみを Clone（fetch）する仕組みのことです。様々なフィルタを指定できますが、例えばBlobless Clone という方法があります。Blob とはファイルのデータそのもので、コミットしたタイミングのデータ（スナップショット）が保存されています。長い歴史を持つリポジトリの場合は履歴に大量に Blob オブジェクトが含まれるので、ダウンロードに時間がかかります。

git clone --filter=blob:none <url> と指定して、クローンすればブロブオブジェクトを除外したクローンをすることが可能になります。

ブロブレスクローンの例 Blobless Clone （出典）Get up to speed with partial clone and shallow clone

下記は、GitHub 社のブログに記載されている torvalds/linux のリポジトリの各クローン方法によるパフォーマンスになります。フルクローンが圧倒的に時間がかかっていることがわかります。

テスト番号	説明	クローン平均実行時間 (分)	クローンあたりの git の CPU 消費時間
T1	Full Clone	5m (最も遅い)	60s (T3 よりも 2 倍少ない)
T2	Shallow Clone	1.2m (T1 より 4 倍高速)	40s (T3 よりも 3.5 倍少ない)
T3	Blobless Clone	3m (T1 より 1.5 倍高速)	130s (最も多い)

公式ドキュメント

https://git-scm.com/docs/git-clone/ja

✨ Sparse Checkout

v2.25 で導入された部分的なチェックアウトの仕組みです。

近年、Monorepo（モノレポ）を使用してプロジェクトを管理することが増えています。複数のサービスを 1 つのリポジトリにまとめることで、Web フロントエンドとバックエンドで共通の型を利用するなど、実用的なメリットを享受することができます。また、Git リポジトリを分離しないことにより、変更の影響範囲をより広範囲に把握することができます。

しかし、場合によっては、リポジトリの中の特定のディレクトリやファイルだけを利用すればよいこともあります。上記の Web アプリケーションの例では、CI/CD によるビルドでは、フロントエンド単体またはバックエンド単体でビルドすれば十分です。反対にバックエンドのビルドでは、フロントエンドの情報を取得する必要はありません。

このような場合に、 sparse-checkout を利用できます。下記はリポジトリをクローンするときの例です。

$ git clone --sparse https://github.com/derrickstolee/sparse-checkout-example
Cloning into 'sparse-checkout-example'...
remote: Enumerating objects: 424, done.
remote: Counting objects: 100% (73/73), done.
remote: Compressing objects: 100% (42/42), done.
remote: Total 424 (delta 43), reused 52 (delta 31), pack-reused 351
Receiving objects: 100% (424/424), 88.06 KiB | 6.29 MiB/s, done.
Resolving deltas: 100% (57/57), done.
remote: Enumerating objects: 3, done.
remote: Counting objects: 100% (2/2), done.
remote: Compressing objects: 100% (2/2), done.
remote: Total 3 (delta 0), reused 1 (delta 0), pack-reused 1
Receiving objects: 100% (3/3), 1.45 KiB | 1.45 MiB/s, done.

$ cd sparse-checkout-example/
$ ls sparse-checkout-example/
bootstrap.sh  LICENSE.md  README.md

$ git sparse-checkout add

git clone 時に --sparce を指定することでリポジトリのトップレベルのみ生成します。つまり、この時点では作業ディレクトリには、特定のディレクトリとその配下のファイルが生成されないです。そして、該当のリポジトリに移動後に、git sparse-checkout add <dir> を実行するときに特定のディレクトリを絞れば、その特定のディレクトリ配下の Git オブジェクトから限定してファイルを復元します。

ほかにもsparse-checkout 機能は既存のリポジトリからでも実行できますし、 git sparse-checkout disable をすれば、もともとの完全な状態の作業ディレクトリに復元もできるので、お手元の環境でも実験してみてはいかがでしょうか。

さらにオススメな方法としては、デフォルトではすべての Git オブジェクトがダウンロードされるため、前述した Shallow Clone などと組み合わせると、さらに高速な git clone を実現することが可能です！

 $ git clone --filter=blob:none --sparse <git repository url>

公式ドキュメント

https://git-scm.com/docs/git-sparse-checkout

さいごに

本記事が大規模リポジトリのパフォーマンス問題について解決の糸口となれば幸いです 🙏

さいごに宣伝です。Git の内部の仕組みの基礎から、本記事で紹介した概念をより深堀りした書籍を Zenn で販売中です！

zenn.dev

仕組みから理解するGit 📚 本書について【Chatper3までは無料公開中！】 Gitの内部の仕組みを徹底的に丁寧に解説する本です。「Gitはいかにバージョンを管理しているのか？」「コミットはスナップショットと聞いたことがあるものの、どういう意味？」「操作時にエラー表示をネットの記事を

本記事の内容の事前知識である Git オブジェクトの基礎から、さらに踏み込んだ下記のような内容も含んでいるので、ぜひお買い求めください！

Git オブジェクトの構造（commit, tree, blob, tag , delta オブジェクトの詳細）
Packfile の構造やバイナリフォーマット
オブジェクトを効率よく探索するデータ構造やアルゴリズム（multipack-index、fanout テーブル、Topological level、bloom filter など）

参考資料

Gitリポジトリを高速化する技術

📈 Commit Graphs

公式ドキュメント

⏲ FS-Monitor

公式ドキュメント

⌛ Scheduled background maintenance

公式ドキュメント

📁 Shallow Clone / Partial Clone

公式ドキュメント

✨ Sparse Checkout

公式ドキュメント

さいごに

参考資料

Commit graph

FS Monitor

Scheduled background maintenance

Partial Clone / Shallow Clone （日本語）

sparse-checkout