Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
「GitHub トレーニングチームから学ぶ Git の内部構造」のノートです。 曖昧なところもあるので、間違いがあったら教えてください! http://connpass.com/event/3808/

GitHub トレーニングチームから学ぶ Git の内部構造

Graphs, Hashes, and Compression, Oh My!

Hash について

従来の CVCS (集中バージョン管理システム)のリビジョン番号は連番。 SVN はサーバーにデプロイした時点でリビジョン番号1と設定される。

Git は SHA1 をつかっている。40桁の16進数のフィンガープリントがついてる。これは理論上は重複しない大きさ。こうすることで単純で強固な DVCS (分散バージョン管理システム)がつくれる。

新しいファイルを追加すると、.git/objects/55/7db03de...(SHA1 finger print) が作成されている。

$ printf "blob 12\000Hello World\n" | shasum
557db03...(SHA1 finger print)

これはファイルに対してではなく、文字列に対して SHA1 を走らせているだけ。コンテンツに対してユニークなので、同じコンテンツであれば同じ finger print になるということが重要。

最終的な finger print はファイルの内容・フォルダの内容・コミットした人から作成される。

$ echo "Hello World" | git hash-object -w --stdin
557db03...(SHA1 finger print)

ファイルの中に何が入ってるかはこれで簡単に分かる。ただし、結果は圧縮されている。

$ alias deflate="perl -MCompress::Zlib -e 'undef $/; print uncompress(<>)'"
$ deflate .git/objects/55/7db03...(SHA1 finger print)
blob 12Hello World

最初の word は git がサポートしている4つのうちのひとつ。

  • blob はファイル
  • tree はフォルダ
  • commit はアクション
  • tag は重要なときに使用するラベル

12 はファイルのバイト数のキャッシュ。

$ git update-index --add --cacheinfo 100644 557db03...(SHA1 finger print)

これで .git/objects 以下にひとつのオブジェクトが保存される。

$ git commit -m"First commit"

これで .git/objects 以下に2つのオブジェクトが保存される。ひとつは commit で、もうひとつは tree

これで終わり。ね、簡単でしょ?

  • Q: なんで最初の2桁がディレクトリなの?

  • A: ファイルシステムの呪いが理由。ひとつのフォルダに十万個のファイルを保存したりすると大変なことになる。最初の二桁をフォルダにすることでロードバランスさせている。たとえば、Linux のカーネルだと各フォルダの中に数百もオブジェクトが保存されることがある。

  • Q: .git/pack の中には何があるのか?

  • A: ファイル自体を圧縮して保存している(この圧縮は前の説明のとは違う動作)。

コミット番号のおはなし

finger print は長すぎて人間には辛いので、最初の6桁や4桁を使うことが多い。短縮した finger print を復元することも可能。

$ git rev-parse f6b4
f6b410a3...(SHA1 finger print)

ただし、これは重複する finger print がなければの話。重複する finger print があるなら、もっと桁数を入力しろと言われる。

ストレージについて

ディスクに保存される方法をもっと詳しく見ていく。 従来の SCM は普通、差分保管を利用している。これは賢いアプローチに見える。しかし、差分保管はファイル履歴が長いとパフォーマンスが悪くなる。

git はいくつかの点で違う方法を利用している。git は差分を保存しない。Directed(時間について有方向) Acyclic(無閉路) Graph を使っている。ファイルに変更があった場合のみ、そのファイルを保存する。 それ以外のときは、ツリーの全体をチェックインしたときにコピーする。この方法は効率的。ディスク容量については効率的じゃない(しかし、近年それは問題にならないよね)。

blob をハッシュするときには、ファイルの内容のみがハッシュ化される。ファイル名の方は treeblob の SHA1 と組で保存されている。これによって同じ内容のファイルが複数存在したとしても、ひとつの blob オブジェクトで済むようになっている(blob の SHA1 をファイルポインタ代わりに使っているイメージ)。

tree の圧縮は次のコマンドで実行できる(自動で面倒見てくれるので人間がタイプする必要はほとんどない)。

$ git gc

こうすることで、Groovy の 2.1GB がたった 205MB になった。

それぞれの hash の関連性

commit はひとつ前の commit と繋がっている。時系列とは逆に過去方向にデータは伸びていく。次のコマンドで親の hash が見られる。

$ git log --pretty=raw
tree 69834...(SHA1 finger print)
parent f031b...(SHA1 finger print)
...

commit は1~2つの親を持つことができる。いっきに複数のブランチをmergeすればさらに多くの親を持てる。

前に説明したとおり、内部的には共通の祖先のファイル単位での差分を利用している。

  • Q: merge の CONFLICT の解決はどこのリビジョンになるのか?

  • A: merge オブジェクトはコードの変更ももてる。そこで解決される。

  • Q: 複数 merge する利点は何か?

  • A: 一気に merge されてるのでアトミックな操作になる。つまりロールバックするときに楽。

  • Q: pack するとき、複数の blob が同じ内容になって圧縮されているはず。これってパフォーマンス的に問題あるんじゃ?()<質問内容聞き取れなかった

  • A: ある程度の期間をおいてからパックされるので問題にはならない。

  • Q: Github にはすごい数のコミットがあると思うが SHA1 が衝突したことはないのか?

  • A: ない(ドヤァ

  • Q: (ネットワークパフォーマンスの話)

  • A:

  • Q: hard link 使えないと git 使えないの?

  • A: 使える。hard link がない場合は hash 使ってうまくやっている。あまり見ないと思うが、ローカルからの clone は hard link になっている。

commitish & treeish

"-ish" は git で使われている DSL(ドメイン特化言語)のこと。 "commitish" は commit 用の DSL。 "treeish" は tree 用の DSL。 この命名についてはみんなで憤慨しようね!(゜゜)<ggiiiiitttttt

ある commit のひとつ前のやつは 9AB22F^ と指定できる(DSLみたいだね!)。キャレットを複数書くと、ひとつずつ戻っていく。9AB22F~5 で5つ前の commit になる。範囲指定も .. で指定できる。HEAD は最新の commit を示す。

これは、実際にはグラフの一部分を指しているだけ。 つまり、こんなふうにもできる:master^^

.git/objects/ 以下のどこが HEAD なのかというデータは .git/HEAD に保存されている。これは実際には .git/refs/heads/ 以下のブランチを参照している。次のコマンドでも同じように見られる。

$ git rev-parse HEAD
8db8f...(SHA1 finger print)

こういう便利な使い方もできる。これは、git clone し直すよりも楽だよね。

$ git reset --hard origin/master

しかし、この操作によって origin/master 以降の commit が宙に浮いてしまう。この commit は90日過ぎるとゴミ箱行きになる。それでもゴミ箱は次のコマンドで閲覧でき、git reset を使えば戻すことが出来る。

$ git reflog 

つまり、commit さえしていればなんとかなる。

また、リポジトリに問題があるかどうかは次のコマンドでチェックできる。

$ git fsck
  • Q: branch を戻すと 0 byte になっちゃうときがある。どうすればいいのか。()<うまく聞き取れなかった

  • A: git fsck は問題を確認するだけで、修復は出来ない。この場合はバックアップから戻してくるのが git のやり方。

  • Q: git reflog のデータはどこに保存されているのか?

  • A: .git/logs の中。

Graph について

git の commit にはもうひとつ hash がある。次の結果の2行目の tree だ。

$ git log --pretty=raw
tree 69834...(SHA1 finger print)
parent f031b...(SHA1 finger print)
...

次のコマンドでメッセージと変更が確認できる。

$ git show 3cef...(SHA1 finger print)

commit の tree に含まれるファイル一覧は次のコマンドで確認できる。

$ git show master^{tree}

一番近いタグを探すにはこうする。

$ git describe master

git show ??? の???部分の DSL について

branch:/search word でマッチするコミットを検索できる(うまくいかなかった場合は、shell が / をファイルパスだと勘違いしていることが原因。クォートで囲めばおk):

$ git show 'HEAD:/Tokyo'

あるコミット時点でのファイルを実際のファイルツリーを変更せずに確認することもできる。その場合は branch:FILE と指定する:

$ git show HEAD~2:file_name

他に3つパターンがある。

  • :0:FILE:Stuging エリアのファイルを表示

  • :1:FILE:merge の途中の場合で、共通の先祖(分岐する直前の commit)のファイルを表示

  • :2:FILE:merge 元のファイルが一番最近に変更された場所を表示

    $ git show branch:0:FILE

休憩後の質問タイム

hash の種類は次のコマンドで閲覧できる:

$ git cat-file -t 0dcd6277...(SHA1 finger print)
commit
  • Q: git logHEAD からツリーをたどるということであってる?

  • A: master ブランチの場合はあってる。git log HEAD~2 だと、HEAD ツリーを前に2つ辿ってね、という意味になる。

  • Q: なぜ SHA1 を選んだのか?

  • A: SHA1 を選ぶ過程で多くの議論があった(この議論では開発者の Linus は放送禁止用語を連発しつつ「変えないんだからね!」と言ったらしい)。SHA1 は今から10、20年後でも衝突せず、計算が軽いというメリットがある。SHA1 はセキュリティ専用だと思われがちだが、そもそもの目的はユニークな値を作成するための方法なので、git みたいな利用方法でも適切。

(ここで Linus の Nvidia, Fuck You! が上映される)

  • Q: ローカルのリポジトリとリモートのリポジトリは何が違うのか?

  • A: 両者は同じ構造。

  • Q: ファイルシステムの変更はアトミックじゃない状況が発生しうると思うが、この状況では git はどのような振る舞いをするか?

  • A: git は実際には、git add があってから書き込まれる。また、ツリーはリファレンスでしかない。つまり、git commit のなかで有効なオブジェクトが書き込まれたかどうかを確認できる。また、ブランチのポインタの更新は一番最後なので事実上アトミックである。これで壊れることは宝くじであたるようなもの。()<聞き取れなかったです。助けて!

  • Q: git clone することなくリポジトリを参照することができるか?

  • A: githubで見られます(ドドヤァ あまり知られていないが次のコマンドでもできる:

    $ git ls-remote https://github.com/...
    
  • Q: ssh > git > https の順でプロトコルがいいと言われているけど、実際どれがいいの?

  • A: https はシンプルでネットワークエラーが起こりにくい。なのでデフォルトで使っている。SSH はフィルタリングされてたりするしね。(補足:ssh > git > https の順で速い。これは github が原因でなく、git に原因がある。github チームは改善のため努力しているところ)

  • Q: git log の順番ってどうなってるの?

  • A: git log --help の Order節を参照せよ。

    Commit Ordering
      By default, the commits are shown in reverse chronological order.
    
      --date-order
          Show no parents before all of its children are shown, but otherwise
          show commits in the commit timestamp order.
    
      --author-date-order
          Show no parents before all of its children are shown, but otherwise
          show commits in the author timestamp order.
    
      --topo-order
          Show no parents before all of its children are shown, and avoid
          showing commits on multiple lines of history intermixed.
    
          For example, in a commit history like this:
    
                  ---1----2----4----7
                      \              \
                       3----5----6----8---
    
          where the numbers denote the order of commit timestamps, git
          rev-list and friends with --date-order show the commits in the
          timestamp order: 8 7 6 5 4 3 2 1.
    
          With --topo-order, they would show 8 6 5 3 7 4 2 1 (or 8 7 4 2 6 5
          3 1); some older commits are shown before newer ones in order to
          avoid showing the commits from two parallel development track mixed
          together.
    
      --reverse
          Output the commits in reverse order. Cannot be combined with
          --walk-reflogs.
    

Githubについての質問

  • Q: pull request の commit の部分にコメントを書いても discussion のところに表示されないのはなんで?

  • A: コメントする場所によって扱いを変えている。discussion にコメントすると全ての pull request にコメントされる。pull request についてコメントするときは、特定の pull request についてコメントされる。()< 聞き取れませんでした。fixme!

  • Q: Github のユーザーのアイコンは自動生成なのはなんで?

  • A: ユーザーが区別できるようにそうしている。それと、アイコンからユーザーを連想するのって楽しいでしょう?表示されたページ

@chiastolite
Copy link

chiastolite commented Nov 16, 2013

「ストレージについて」と「それぞれの hash の関連性」のとこにあるhard linkの説明ですが、実際にはhard linkを使っているのではなく、「hard link」ぽい挙動ってニュアンスだったと思います

@Kuniwak
Copy link
Author

Kuniwak commented Nov 16, 2013

@chiastolite さん、ありがとうございます!

hard link の件ですが、発表資料が出ないようなので過去の文献を調べてみました。
git-clone(1) Manual Page では、次のように書かれています。

The files under .git/objects/ directory are hardlinked to save space when possible.

この前後の文からはhard link 「みたいな」というニュアンスがないため、hard link を使っていると考えても良いと思ったのですが、いかがでしょうか?(不確かなのですが、「hard linkぽい」というのは hard link が利用できない環境についての説明の中ででてきたような覚えがあります)

@DQNEO
Copy link

DQNEO commented Nov 18, 2013

こんにちは。横から失礼いたします。

ストレージについてのところですが、実体はblobのsha1ハッシュ値がtreeオブジェクトの中にバイナリとして埋め込まれています。
treeオブジェクトをバイナリエディタで閲覧すればそれが見えます。 (git 1.8で確認済み)

なので、「blob への hard link で実現」というのは正しくありません。おそらく単に「リンクしている」とおっしゃりたかっただけかと思われます。

git clone --local を同一パーティション内でやるとファイルコピーする代わりにハードリンクが使われるようですが、これはまた別の話。

@DQNEO
Copy link

DQNEO commented Nov 18, 2013

ついでにすごいおせっかいですが、本gistを例にしてtreeがどのようにblobを格納しているかを説明します。

$ git clone git://gist.github.com/7482397.git
$ cd 7482397
$ git cat-file -p HEAD
tree 2a0bfac9bb49415b05f10943d605f169949407ff
parent c2e36c95562ee41ac9fc7a8ab0efbf920cc6c4f7
author OrgaChem <OrgaChem@xxxx>
committer OrgaChem <OrgaChem@xxxx>
$ git ls-tree 2a0bfac9bb49415b05f10943d605f169949407ff
100644 blob f5ba06ac8c475c660322b101031d08311188e148    2013_11_15_githubjp_note.markdown

という感じで、treeオブジェクト2a0bfac9bb49415b05f10943d605f169949407ffの中に、
blobのハッシュ値f5ba06ac8c475c660322b101031d08311188e148が含まれているのが見れます。

「ファイル名は tree の方に保存されている。ファイルはただ単にポインターみたいな感じで保持されている」というのはつまりこういうことです。

おせっかい失礼しました。

@Kuniwak
Copy link
Author

Kuniwak commented Nov 19, 2013

@DQNEO さん、ご指摘・詳しい解説をありがとうございます!

内容を修正しました。
@DQNEOさん、@chiastolite さんのご指摘のとおりで、私の記憶が間違っていました(ごめんなさい!)。
お二人のご指摘でより正しいノートに近づくことができました!ありがとうございます!

@DQNEO
Copy link

DQNEO commented Nov 19, 2013

👍

@kmdsbng
Copy link

kmdsbng commented Nov 21, 2013

typoがあります。

perl -MCompless::Zlib ...

perl -MCompress::Zlib ...

@Kuniwak
Copy link
Author

Kuniwak commented Nov 24, 2013

@kmdsbng さん、ありがとうございます!
修正しました。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment