Linus Torvalds氏によるGitの内部構造の解説

初めに

LinusによるGitのinitial commitのREADMEの訳です。

社内のSVNからの移行を促すために資料を整備していたのですが、SVNでやっていたことを移し替えたりコマンドを覚えたりするより内部構造を知ったほうが早いことに気づきました。

それで、gitの内部構造についての解説資料を色々見ていたのですが、データ構造については原作者のこのREADMEに言い尽くされている気がします。のみならず、gitを使うものが抱くべき精神性のようなものが示されており、深い感銘を覚えました（ヒャッハー）。

README: ”GIT - 馬鹿コンテンツトラッカー”

コミットメッセージ：git, 地獄からきたインフォメーションマネージャ

gitの意味

"git" は何を意味することも出来る、お前の気分次第だ。

• 3文字で、発音可能で、実際のUNIXシステムで共通コマンドとして使われていないものであればなんでも良かったのだ。事実は'get'の発音間違いだ、関係していようがいまいが。

• バカ。情けなくて浅ましい。単純。その他お前のスラング辞典から拾ってきやがれ。

• グローバル・インフォメーション・トラッカー(global information tracker):
  お前はいい気分だ、実際にお前の役に立つ。天使達は歌い、光が突如お前の部屋を満たす。

• くそったれ間抜けなトラック満載のクソ(goddamn idiotic truckload of sh*t):
  壊れた場合。

概要

これは馬鹿（だけど超速い）ディレクトリ・コンテンツ・マネージャだ。
沢山の事はしないが、効率的にディレクトリの内容を追跡する。

2つのオブジェクト構造がある

• オブジェクト・データベース(.git/objects/)
• カレントディレクトリキャッシュ(.git/index)

オブジェクト・データベース（SHA1によるファイル・ディレクトリ）

オブジェクト・データベースとは文字通りコンテンツによってアドレス指定可能なオブジェクトの集まりだ。全てのオブジェクトはそのコンテンツによって命名される。オブジェクト自体のSHA1ハッシュ値によって近似される。オブジェクトは他のオブジェクトを(SHA1ハッシュ値により）参照することができるので、お前はオブジェクトの階層構造を構築できる。

このデータベースには複数の種類のオブジェクトがある。全てzlibにより圧縮されており、先頭はファイルタイプによるタグとデータに関するサイズ情報で始まる。SHA1ハッシュ値は圧縮後のものであり、元データのものではない。

特にオブジェクトの一貫性はコンテンツやオブジェクトの種類とは独立して常にテスト出来る。全てのオブジェクトは次のようにして確かめられる。

• ハッシュ値がファイルのコンテンツにマッチすること

• オブジェクトが次の形式のバイトストリームとして復号に成功すること
  <スペース無しのascii文字によるタグ> + <space> + <ascii文字の10進サイズ情報> + <\0> + <バイナリオブジェクトデータ>

BLOB

ブロブオブジェクトはバイナリ・ブロブデータ以外の何をも意味せず、また他への参照も持たない。データの署名や他の検証は持たず、オブジェクトが一貫している限り(SHA1ハッシュ値によりインデックスされているのでデータ自体は正しいとする）他に何の属性も持たない。名前の関連付けも、パーミッションもない。純粋にデータのブロブだ（別の言い方をすると、ファイルの中身だ）。

TREE

次の階層のオブジェクトの種類は、ツリーオブジェクトだ。ツリーオブジェクトはパーミッション・名前・ブロブデータからなるリストで、名前によりソート済みだ。別の言い方をするとツリーオブジェクトの一意性はコンテンツのセットで決定される。だから2つの別々だが同等のツリーは確実に同じオブジェクトを共有する。

もう一度言うが、ツリーオブジェクトはただの純粋なデータ構造だ。履歴を持たず、署名も持たず、正当性の検証も持たない。コンテンツがハッシュ値によって保護されているだけである。それで、ブロブを信頼するのと同じ理屈でツリーオブジェクトを信頼できるが、お前はコンテンツがどこから来たのか知ることは無い。

※1

ツリーオブジェクトがファイル名+コンテンツでソートされているため、お前は2つのツリーを展開せずともdiffを作り出すことが出来る。共通の部分を無視するだけでお前のdiffは見やすくなるだろう。別の言い方をするとお前は2つのどんなランダムなツリーの比較でも、ツリーのサイズではなく、差分の大きさをnとしてO(n)の計算量で効果的かつ効率よくdiffを表現できるというわけだ。

※2

ブロブデータの名前は全く独占的にその内容に依存しているため（名前やパーミッションも関係ない）、ブロブの内容が変わらなければお前は細々としたリネームやパーミッションの変化を見る事ができる。しかしながら、データを変えつつリネームという場合にはもっと賢いdiffが要求されよう。

チェンジセット

チェンジセットオブジェクト¹は履歴反映の概念を導入するオブジェクトだ。他のオブジェクトとは対象的に、ツリーの物理的な状態を表現するだけでなく、どうやって、そしてなぜそこにたどり着いたのかを表現する。

チェンジセットはツリーオブジェクトによって定義され、結果として（0,もしくは1以上）の親チェンジセットや何が起こったのかを表記するコメントを含む。もう一度言うが、チェンジセットそれ自体が認証されたりしているわけではない。コンテンツは明確で全てのレベルにおいて強固な暗号署名のゆえに「安全」であるが、しかしながらツリーが「良い」とかマージ情報が意味を成すとか信じる理由などない。例えば親チェンジセットはその結果について何の関連も持つ必要はない。

※1

本物のソース・コード管理システム（SCM）とは違い、チェンジセットにはリネーム情報やファイルモードの変更情報は含まれない。そういった事はツリー（結果のツリー、及び結果のツリーの親）が明示的に関わることだ。この馬鹿ファイルマネージャがそれらを表現する意味はない。

※2「信頼」について

「信頼」はgitの全く埒外の概念だが、次の事を覚えておけ。まず第一に、全てのものがSHA1によりハッシュ値を与えられているゆえ、お前はオブジェクトがそのままであり外部の源により弄くられていないことを信頼出来る。オブジェクト名により、知り得る状態を一意的に識別出来るのだ - 単にお前が信頼したいであろう状態ではない。

さらに、チェンジセットのSHA1署名はツリーのSHA1署名と、更にその親と関連付けられており、単一の名前のチェンジセットが全コンテンツと共に全履歴のセットを規定する。一度お前がチェンジセットの名前を得たなら、後ほど履歴のステップを誤魔化す事はできない。²

それで幾つかのシステムにおける現実的な信頼を紹介するとすれば、お前がしなければならないのはトップレベルのチェンジセット名を含む特別な記述一つをデジタル的に署名することだけだ。お前のデジタル署名は他の者にそのチェンジセットが信頼できることを示し、チェンジセットの履歴の不変性は他の者に全履歴が信頼できることを示すであろう。

言い換えるならば、お前はGPG/PGP等のデジタル署名されたemailを使い（SHA1ハッシュ値の）トップのチェンジセットを送るだけで全てのアーカイブの検証を行うことが出来る。

特に、お前や他の者が信頼するドキュメントの複数のトラスト・ポイントやタグから成る分割されたアーカイブを持つことが出来る。もっともそれら「信頼証明」はgitそのものを使っていることからもたらされるわけだが、別に特段gitがお前に何かするというわけでもない。

言い方を変えると、git自体はコンテンツの整合性のみ扱い、信頼は外部から付与されるということである。

カレント・ディレクトリ・キャッシュ

カレントディレクトリキャッシュとは単純なバイナリファイルであり、任意の時点での仮想的なディレクトリのコンテンツを効率よく表現したものである。名前、日付、パーミッション、コンテンツ（またはブロブ）を一緒にセットしたものの単純な配列である。常に名前順に並べられているが、キャッシュなので長い期間に渡って保持されることを意図してはおらず、いつでも部分的に更新できる。

特に、カレントディレクトリキャッシュは確実に現在のディレクトリの内容と一致しなければならないと言うわけではないが、2つの重要な特徴がある。

• キャッシュしている全ての状態が再生成可能である
  （ディレクトリ構造だけでなく、ブロブオブジェクトを通して全データも再生成可能であるということ）
  特殊な場合として、明確で重複しないカレントディレクトリキャッシュからツリーオブジェクトへの単一のマッピングが存在し、他のデータを見る必要も無くカレントキャッシュディレクトリから効率よく生成できる場合がある。それでディレクトリキャッシュはいつどの時点でもただひとつのユニークに定義されたツリーオブジェクトである（しかしながらツリーオブジェクトとディレクトリ内で何が起こったかを照合するため追加的データを持つ)

• キャッシュされた状態（裏付けされるのを待っているツリーオブジェクト）と現在の状態との不整合を検出するための効率の良いメソッドを持つ

以上がディレクトリキャッシュが行うたった2つのことである。キャッシュであり、既存のツリーオブジェクトからの完全な再生成や、開発ツリーの更新、既存ツリーとの比較を行うためのものである。もしお前がディレクトリキャッシュを全く吹き飛ばしたとしても、キャッシュで表現されているツリーの名前を保持している限り、何のデータも失わない。

（しかしながらディレクトリキャッシュには実データが入ることもある。特に、まだ裏付けされていない中間状態のツリーの表現を持つことがある。それでキャッシュ本来の意味や用法とは違う場合がある。見方を変えるならカレントディレクトリキャッシュをツリーコミットへの作業中の状態と考えることも出来る³）。

補遺

扱われていない内容

原文はデータ構造のみの説明です。
それ以外（通信系、ホスティングなどは）扱われていません。
また基本データ構造の応用であるブランチやマージもありません。
こういったことは初期においては手動・応用スクリプトで対応していたようです。

文体

原文の文体の冒頭はスラングと罵倒の羅列です。自作プログラムを馬鹿と卑下する表現もたくさんありますが、問題領域に対してシンプルなデータ構造で解決するんだ、という矜持のようなものも感じられます。当時流行っていた「多機能で信頼可能な」SCMを期待する向きに対して突き放したような表現も多々あります。なおCVSやSVNなど従来型の差分SCMに対するLinusの態度は超攻撃的なことで有名です。

そんなわけで訳文もやや乱暴なテイストにしましたが、不快に思われたらごめんなさい。

理解のために

実際に適当なリポジトリを最新のcommitから

git cat-file -p <hash>

してオブジェクトデータベースを辿ったり、

git ls-files --stage

してindexを見てみると、今でもデータに関しては上記の事は基本的にしていることがわかります⁴。
Pro git 日本語版のGitの内側の章を実際に手を動かしてみると理解が一層深まると思います。

---

1. 要するにコミット情報 ↩

2. このことから、gitによる履歴管理は一種のブロックチェーンとみなすことができる。 ↩

3. git addやrmして、commitしていない状態の時はこのようになる。 ↩

4. 今では上記の基本データに加え、packファイルにより差分を扱い、容量やpush前の転送量を節約したりしている。詳しくはPro Git - Gitの内側　パックファイルを参照のこと。 ↩