Gitを支える内部構造についての話

こんにちは。Timers プラットフォームチームの山口です。
入社して9ヶ月が経ちました。今回で二回目の執筆です。

どうぞよろしくお願いいたします。

はじめに

Timersでは半年に一回自身の裁量で決めた目標をコミットメントシートに記入し、その半年後に目標に責任を持って取り組んだかをチーム内で評価し合う文化になっています。コミットメントシートはTimersの誰でも閲覧できるようになっています。私はこの文化がたいへん気に入っています。

理由は3つです。

自身がチームに貢献したことについてのフィードバックを得られる。
チームに貢献する方向性や手段を自身で決められる。
自身がどのように学習し成長するかの方向性を自身で決められる。

今期は「個人の目標」と「チームにどのような貢献をするかの目標」をテーマに目標を決めなければなりませんでした。私の今期チーム目標はチームの生産性をあげることです。

私は開発にかけられる時間は限られているために、ある程度のところで妥協したものを世に出さなければならないことに苛立ちを感じていました。妥協しないためには、よりよいものを作るための多くの時間を確保するひつようがありました。解決するひとつの手段として、生産性を高めることに私は着目しました。それがチームの生産性を高めるを目標に設定した理由です。

Gitはチームの生産性を高める強力なツール

さて、今回はチームの生産性を高めるをテーマに、世の中にあるツールの中でチームの開発を強力にサポートするツールのひとつであるGitについてお話します。、Gitを知らない開発者に出会うことがとても珍しいくらい現在では普及したツールとなっています。Gitで開発同士の開発をコラボレーションするGithubは一般公開からたった7年間で970万人を突破したそうです。広い範囲の一般ユーザーに比べて、狭い範囲の開発ユーザーという少ないユーザーを対象に、急スピードで普及したのは、Gitが開発者にはなくてはならない強力な機能を備えていたからでしょう。

Gitのチームでの開発をサポートする強力な機能

branch チームでの試行錯誤を円滑にする
log 過去にわたってチームの作業目的の概要を知る
diff チームの作業内容を詳細に知る
merge お互いの作業内容を融合させる
clone すべての作業履歴とソースコードをダウンロードする

世界中の開発者とコラボレーションを強力に支援するGithub
github.com

Gitをただ使うだけでも十分にチームでの生産性を高めることはのぞめますが、Gitの考え方を学んだ上でGitを使えば、よりはやいスピードでチームでの生産性を高めることに役立てることができるでしょう。この記事を執筆する３年程前にGithubチームのマシューさん、ジョンさんたちが「Gitの内部構造について」の勉強会を開催することをconnpass上で知り、お話を聞く機会がありました。そのとき私が彼らから学んだことをシェアさせてください。

Gitを支えるハッシュ関数 SHA-1

セキュリティハッシュアルゴリズムでも使われているSHA-1というハッシュ関数を利用することで、Gitは高速にソースコードの差分を検出しマージすることが可能になっています。SHA-1は、セキュリティ暗号アルゴリズムでよく使われているのでその分野で有名ですが、元々はあるデータを端的に表すためのもので、巨大なファイル同士の完全一致を高速に調べるために生み出されたそうです。

Gitで使われるSHA1は40桁の16進数の文字列で表現されます。

be5a750939c212bc0781ffa04fabcfd2b2bd744e

短い文字列なので計算されたハッシュには衝突の可能性がありますが、聞いた話によると地球上にあるすべての砂粒の数の千二百倍にあたる量を表現することができるそうです。つまり、途方もなく小さな確率でしか衝突しないというわけです。

1.3GBという大きなファイルのハッシュを高速に計算することができます。

$ wget http://cdimage.ubuntulinux.jp/releases/16.04/ubuntu-ja-16.04-desktop-amd64.iso
$ time openssl sha1 ubuntu-ja-16.04-desktop-amd64.iso
SHA1(ubuntu-ja-16.04-desktop-amd64.iso)= 34dad02ac99fdce957cbfabbd9cb0b5d14bbd9ff

real	0m3.456s
user	0m2.145s
sys	0m0.785s

低速なネットワークを介して大きなファイルそのものをやりとりしなくても、この短い小さな40桁の文字列だけを比較すれば、ファイルが一致しているかを調べることができるというわけです。Gitはこの仕組を使って、どれだけ強大なファイルであったとしてもリモートとローカルのファイル差分検出を高速に行うことができるようになっています。

Gitの内部構造

すべてのデータを４種類のGitオブジェクトに分類して記録しています。

アクション Commit
バイナリ・ラージ・オブジェクト、ファイル Blob
ディレクトリ名とファイル名 Tree
ラベル Tag

Commit間の関係性を表す図

f:id:timers-tech:20161115212503p:plain
ブランチ名: 赤色
タグ名: 橙色
コミットハッシュ: 黒色

現在いるブランチの先頭を挿しているGItオブジェクトが格納されているものをHEADと言います。commit操作を行うと、HEADの指し先が変更され、現在いるブランチの指し先も変更されます。TagはBranchに似た機能ですが、Commit操作を行っても指し先は変更されません。その点がBranchとTagとの違いです。

ある一つのGitオブジェクトを指すSHA1が一致するときは、そこから辿れるすべてのGitオブジェクトが完全に一致するデータ設計になっています。次の図を参考にGitオブジェクトの関係がどのように表現されていることを知ることがGitの内部構造を理解する上でとても重要なポイントになっています。

Gitオブジェクトの関係性を表す図

f:id:timers-tech:20161105002024p:plain

次のコマンドでGitオブジェクトの詳細を調べることができますので、あなたの開発しているプロジェクトのGitリポジトリ内をのぞいてみるとよいでしょう。

git cat-file -p <commit | tree | blob | tag>

Gitオブジェクトの格納場所

Gitオブジェクトの記録方法は2つ

Gitオブジェクトを指すSHA1をファイル名に、2桁のディレクトリ名と38桁のファイル名で記録
複数のGitオブジェクトをpackファイルに束ねて記録

$ tree .git/objects/
.git/objects/
├── 1d
│   └── c3d2588e156d3891416a69e883db469115821a
├── 51
│   └── 0cf8b64fbce460229800019c9847e108e8edd2
├── info
└── pack
    ├── pack-87b1f26bb70a188f06e38ecb440292ab693aa711.idx
    ├── pack-87b1f26bb70a188f06e38ecb440292ab693aa711.pack

まとめ

LinuxとGitの生みの親リーナス・トーバルズは「良いプログラマーと悪いプログラマーの違いは、コードとデータのどちらの設計を重点的に気をつかっているか。悪いプログラマーはコード設計に気をつかう。良いプログラマーはデータ設計に気をつかう」と言っています。40桁のハッシュを比較するだけで差分比較やマージを高速に行うことが可能であるのは、Gitのデータ構造が適切に設計されているためということですね。そして、その設計の素晴らしさが結果として、Gitが世界中の開発者同士のコラボレーションを強力に支えるツールであり続けることができる理由になっているのでしょう。