Ruan Yifeng: Github のオブジェクトカウントアルゴリズム

Github を使用しているときに、次のプロンプトを見たことがありますか?

 $ gitクローン https://github.com/torvalds/linux
 'linux' にクローンしています...
リモート: オブジェクトをカウントしています: 4350078、完了。
リモート: オブジェクトの圧縮中: 100% (4677/4677)、完了。
受信オブジェクト: 4% (191786/4350078)、78.19 MiB | 8.70 MiB/秒

このプロンプトは、リモート コード リポジトリにクローン化する必要があるオブジェクトが合計 4350078 個あることを示しています。

これは「オブジェクトのカウント」と呼ばれます。Github は、クローン化する必要があるオブジェクトの総数をリアルタイムで計算する必要があります。

このプロセスは非常に遅いです。Github によると、Linux カーネルのような巨大なライブラリをインベントリするには 8 分かかります。つまり、git clone コマンドを発行した後、実際のデータ転送が開始されるまで 8 分間待機することになります。もちろんこれは耐えられないことだ。 Github チームはこの問題を解決しようと努めてきました。

その後、ついに新しいアルゴリズムが発見され、今では 1 回のカウントに 3 ミリ秒しかかかりません。

このアルゴリズムを理解するには、まず Git オブジェクトが何であるかを知っておく必要があります。簡単に言えば、オブジェクトはファイルであり、最も重要なオブジェクトの種類は 3 つあります。

• スナップショットオブジェクト（コミット）
• ディレクトリオブジェクト
• ファイルオブジェクト

コードを送信するたびに、対応する現在の「ディレクトリ オブジェクト」の名前を含むコミット オブジェクトが生成されます。 「ディレクトリ オブジェクト」には、コード ルート ディレクトリに含まれるサブディレクトリとファイル情報が格納されます。各サブディレクトリは別の「ディレクトリ オブジェクト」であり、各ファイルは特定のファイル コンテンツを含む「ファイル オブジェクト」です。

したがって、「オブジェクトをカウントする」とは、さまざまなコミット、ディレクトリ、ファイルなどをカウントすることを意味します。 git clone と git fetch の両方の操作では、どのオブジェクト ファイルがダウンロードされるかを知る必要があるため、オブジェクト インベントリが必要です。

オブジェクトをカウントするための元のアルゴリズムは次のとおりです。

1. すべてのローカルブランチを一覧表示***コミット
2. すべてのリモートブランチを一覧表示***コミット
3. 2つを比較し、違いがあればブランチが変更されたことを意味します。
4. 変更されたコミットごとに、変更されたサブディレクトリとファイルを確認します。
5. 現在のコミットの親ノードまでトレースバックし、ローカルとリモートの履歴が一致するまで手順 4 を繰り返します。
6. 変更が必要なすべてのオブジェクトを合計します

上記のプロセスは、「オブジェクト カウント」がファイル トラバーサル アルゴリズムであることを示しています。変更されたオブジェクトは 1 つずつカウントされるため、ファイル読み取り操作の回数が多くなります。大規模なコードベースでは、このプロセスは非常に遅くなります。

Github チームが考案した新しいアルゴリズムは、ビットマップ インデックスを作成すること、つまりコミットごとにバイナリ値を生成することです。

ローカル Github リポジトリの .git/objects/pack/ ディレクトリを開くと、ビットマップであるインデックス ファイルとデータ ファイルが表示されます。簡単に言うと、これら 2 つのファイルは現在のコード ベース内のすべてのオブジェクトをインデックス化し、バイナリ値を使用してこれらのオブジェクトを表します。このバイナリ値には、オブジェクトの数と同じ数のビットが含まれます。 n 番目のビットは、データ ファイル内の n 番目のオブジェクトを表します。

各コミットには、現在のスナップショットに含まれるすべてのオブジェクトを表す対応するバイナリ値があります。これらのオブジェクトの対応するバイナリ ビットはすべて 1 で、他のバイナリ ビットはすべて 0 です。

これを実行する利点は、コミット オブジェクトを読み取る必要がないことです。現在のコミットに含まれるノードを知るには、バイナリ値を読み取るだけで済みます。さらに良いことに、2 つのバイナリ値に対して XOR 演算を実行するだけで、どのビット (つまりどのオブジェクト) が変更されたかがわかります。さらに、新しいオブジェクトは常に既存のバイナリ ビットの末尾に追加されるため、現在のコミットに前のコミットよりも多くのオブジェクトが含まれているかどうかを確認するには、追加ビットを読み取るだけで済みます。

このように、「オブジェクトのカウント」はバイナリ値の比較操作となるため、速度が非常に速くなります。詳しい説明については、公式ドキュメント「ビットマップの説明」および「ビットマップのフォーマット」を参照してください。

現在、このアルゴリズムは Github の実稼働環境に導入されており、ユーザーはオブジェクトのカウントを待つ必要がなくなりました。さらに、Github チームはこれを Git に統合しました。つまり、今後はすべての Git 実装で Bitmap 関数を使用できるようになり、将来的にはより興味深い使用法が確実に生まれるでしょう。

（以上）