🎄

Gitの内部表現をちょっと詳しく見てみる

2022/12/14に公開

インターファーム エンジニアの沖野です。
今更ながらGit自作本を読んでみたので、気になっていた部分を少し深掘りしてまとめてみました。
ネタバレ防止のため、内容はGit自作本が無料で公開されている範囲の内容プラスα とさせていただきます。
自作してみたいという方はぜひこちら↓の記事を読んでみてください。

この記事では、主に基本的なGitオブジェクトとrefs, HEAD, Packfileについて触れます。

Gitオブジェクトとは?

Gitに保存されるデータの内部表現には、blob, tree, commitの3タイプ存在します。
※ Tagオブジェクトも存在しますが、本エントリーでは割愛させていただきます。
これらを組み合わせることで、データを永続化すると共に、変更を追跡することができます。

  • Blobオブジェクト … 1つのファイルに当たるオブジェクト。
  • Treeオブジェクト … 複数のGitオブジェクトをまとめるためのオブジェクトで、ディレクトリを表現したもの。
  • Commitオブジェクト … 1つのTreeオブジェクトを参照し、コミットした人やメッセージを保存するオブジェクト。直前のコミットの参照も持ち、変更が追えるようになっている。

イメージとしては、次のようになっています。

git_study.jpg

Blobオブジェクトがファイルの中身を保存し、Treeオブジェクトがそれをまとめて木構造を作り、Commitオブジェクトでコミット内容を保存するという流れになっています。

全オブジェクトに共通な仕様

Gitはこれらのオブジェクトをオブジェクトストレージ( .git/objects/ 以下)にファイルとして保存し、永続化します。
各オブジェクトは、タイプにかかわらず、キーをオブジェクトのSHA1ハッシュ値として、オブジェクトストレージに保存されます。

例えば、ハッシュ値が 00e55bb5e2c5831a6a543a のオブジェクトであれば、.git/objects/00/e55bb5e2c5831a6a543a のファイルに中身が保存されることになります。

またオブジェクトをストレージに保存する際には、zlib圧縮されます。
読み出す際は、中身を解凍することでデータ量を削減することができます。

git_study_img.png

オブジェクトをバイト列に変換するフォーマットは後述の各オブジェクトについての解説で触れます。

まとめると、GitではキーをオブジェクトのSHA1ハッシュ値バリューをzlib圧縮したオブジェクトとして永続化します。
これがGitが「シンプルなキー・バリュー型データストアである」と言われる所以です。

オブジェクトのヘッダー

各オブジェクトは先頭にヘッダー情報を持っています。

{type} {size}\0{オブジェクトの中身}

type にはblobやtreeのようなオブジェクトの種類が、size はオブジェクトの中身の長さが入ります。
次に、各オブジェクトについて詳しく見ていきます。

Blobオブジェクト

まずは、ファイルに対応するBlobオブジェクトからみていきます。
Blobオブジェクトは以下の情報を持ちます。

  • size … ファイルサイズ
  • content … ファイルの中身
    ※ファイル名は持っていないことに注意してください。

フォーマットは、以下のようになっています。

blob {size}\0{content}

配管コマンドを使ってBlobオブジェクトを作ってみる

ここでは、配管コマンドを利用して、実際にBlobオブジェクトをオブジェクトストレージに登録してみます。

配管コマンドとは、Gitでより低レベルな操作を行うために用意されているコマンドで、Blobオブジェクトの作成には、 hash-objectコマンドが利用できます。(一方で私たちが普段よく利用する addcommit などのコマンドは磁器コマンドと呼ばれます。)
hash-object コマンドは与えられたファイルパスからBlobオブジェクトを生成し、オブジェクトストレージに登録することができます。

# "sample"と書かれたファイルを用意(改行コードを含めない)echo -en "sample" > sample.txt

# Blobオブジェクトを生成git hash-object -w sample.txt
eed7e79a92ce81c482fe5865098047e0293a31b2
# ↑ 生成されたオブジェクトのハッシュ値。メモっておく

これでBlobオブジェクトが生成されました。
まずはこのハッシュ値が、 blob 6\0sample のSHA1ハッシュ値と一致することを確認してみます。

echo -en "blob 6\0sample" | openssl sha1
(stdin)= eed7e79a92ce81c482fe5865098047e0293a31b2

このように、 blob 6\0sample という文字列をSHA1ハッシュに入力した結果と一致することが確認できました。

続いて、ファイルの中身を確認してみましょう。
先ほど説明したように、ハッシュ値が eed7e79a92ce81c482fe5865098047e0293a31b2 だっため、生成されたファイルのパスは .git/objects/ee/d7e79a92ce81c482fe5865098047e0293a31b2 となっています。

# catしてみるcat .git/objects/ee/d7e79a92ce81c482fe5865098047e0293a31b2
# xKOR0c(N-IXx

# zlibで解凍してみる
❯ zlib_decompress .git/objects/ee/d7e79a92ce81c482fe5865098047e0293a31b2 /dev/stdout
# blob 6sample

# zlibで解凍 + xxdでバイト列確認
❯ zlib_decompress .git/objects/ee/d7e79a92ce81c482fe5865098047e0293a31b2 /dev/stdout | xxd
# 00000000: 626c 6f62 2036 0073 616d 706c 65         blob 6.sample

以上の結果確認してみると、 blob {size}\0{content} をzlib圧縮したデータと一致していることが確認できました。
UTF8文字コードとの対応は以下です。

62 6c 6f 62 20 36 00 73 61 6d 70 6c 65
b l o b SP(空白) 6 NULL s a m p l e

gitでは cat-file と言うオブジェクトの中身やタイプを表示するための配管コマンドも用意されているため、こちらでも確認できます。

# 整形して表示する(-pは中身を表示して、-tはオブジェクトタイプを表示)git cat-file -p eed7e79a92ce81c482fe5865098047e0293a31b2
# samplegit cat-file -t eed7e79a92ce81c482fe5865098047e0293a31b2
# blob

Treeオブジェクト

次に、ディレクトリに相当するTreeオブジェクトについてみていきます。
Treeオブジェクトは以下の情報を持ちます。

  • contents(直下のBlobオブジェクト or Treeオブジェクト情報の配列)
    • mode … ファイルタイプを表す値(100644は通常のファイル、100755は実行可能ファイルなど)
    • name …. ファイルorディレクトリ名
    • hash… そのcontentの中身が保存されているGitオブジェクトへの参照

フォーマットとしては、次のようになっています。

tree {len}\0{mode1} {name1}\0{hash1}{mode2} {name2}\0{hash2}...

配管コマンドを使ってTreeオブジェクトを作ってみる

Blobオブジェクトの時と同様、配管コマンドを利用してTreeオブジェクトを生成し、中身を確認してみます。
今回利用するコマンドは、 write-tree です。このコマンドはステージングに登録されたファイルからTreeを生成するコマンドで、 add コマンドの内部で利用されています。

# ステージングに登録する(これも配管コマンド)git update-index --add --cacheinfo 100644 \
  eed7e79a92ce81c482fe5865098047e0293a31b2 sample.txt

# ステージングに登録されているか確認する(配管コマンド)git ls-files --stage
100644 eed7e79a92ce81c482fe5865098047e0293a31b2 0       sample.txt

# ツリーを作成するgit write-tree
1a38e7953af851a9919d16f59e8cbe7b2580288d

これでTreeオブジェクトが生成され、オブジェクトストレージに保存されました。
このTreeオブジェクトのハッシュ値は 1a38e7953af851a9919d16f59e8cbe7b2580288d です。

Blobオブジェクトの時と同様、オブジェクトの中身を確認してみましょう。

# catしてみるcat .git/objects/1a/38e7953af851a9919d16f59e8cbe7b2580288d
# x+)JMU0`040031Q(N-I+(axwI4Hlpie

# zlibで解凍してみる
❯ zlib_decompress .git/objects/1a/38e7953af851a9919d16f59e8cbe7b2580288d /dev/stdout
# tree 38100644 sample.txt΁ĂXe    G):1

# zlibで解凍 + xxdでバイト列確認
❯ zlib_decompress .git/objects/1a/38e7953af851a9919d16f59e8cbe7b2580288d /dev/stdout | xxd
# 00000000: 7472 6565 2033 3800 3130 3036 3434 2073  tree 38.100644 s
# 00000010: 616d 706c 652e 7478 7400 eed7 e79a 92ce  ample.txt.......
# 00000020: 81c4 82fe 5865 0980 47e0 293a 31b2       ....Xe..G.):1.

# 整形して表示するgit cat-file -p 1a38e7953af851a9919d16f59e8cbe7b2580288d
# 100644 blob eed7e79a92ce81c482fe5865098047e0293a31b2    sample.txtgit cat-file -t 1a38e7953af851a9919d16f59e8cbe7b2580288d
# tree

生成されたTreeオブジェクトの中身を見てみると、

  • header
    • type … tree
    • len … 38
  • contents
    • mode … 100644
    • name … sample.txt
    • hash … eed7e79a92ce81c482fe5865098047e0293a31b2

のTreeオブジェクトが生成されたことが確認できました。

また、このツリーオブジェクトに含まれる sample.txt のハッシュは先ほど生成したBlobオブジェクトのハッシュ値と一致していることも確認できます。
このようにして、ツリーオブジェクトを利用して複数のファイルをまとめて管理することができます。

Commitオブジェクト

今まで見てきたBlob, Treeオブジェクトを利用することで、変更内容は保存できますが、誰がいつなぜ保存したのかについての情報は保存できません。
これらの問題を解決するのがCommitオブジェクトで、さらに直前のCommitオブジェクトのハッシュ値を持つことで、コミットツリーを形成できます。
Commitオブジェクトが持つ情報は以下です。

  • tree … ツリーオブジェクトのハッシュ値
  • parent … 親コミットのハッシュ値(ない場合は省略)
  • author … オリジナルのコードを書いた人
    • name … 作者名
    • email … 作者のメールアドレス
    • timestamp … タイムスタンプ
  • committer … コミットした人(authorと同じデータフォーマット)
  • message … コミットメッセージ

(↓authorとcommitterの違いはこちらの記事をご参照ください。)

Commitオブジェクトのデータフォーマットは以下です。

commit {size}\0tree {tree}
parent {parent}
author {name} <{email}> {timestamp} {offset}
committer {name} <{email}> {timestamp} {offset}

{message}

配管コマンドを使ってCommitオブジェクトを作ってみる

Commitオブジェクトの生成には、 commit-tree という配管コマンドを利用します。
以下のコマンドを実行して、Commitオブジェクトを生成してみましょう。

# コミットの作成echo "commit message" | git commit-tree 1a38e7953af851a9919d16f59e8cbe7b2580288d
# 4492091b4c200e7fbcc9fe0a42eabb542c2f8892

# refを更新git update-ref refs/heads/master 4492091b4c200e7fbcc9fe0a42eabb542c2f8892

# log確認git log --pretty=fuller
# commit 4492091b4c200e7fbcc9fe0a42eabb542c2f8892 (HEAD -> master)
# Author:     oky-123 <hogehoge@example.com>
# AuthorDate: Thu Oct 27 16:25:01 2022
# Commit:     oky-123 <hogehoge@example.com>
# CommitDate: Thu Oct 27 16:25:01 2022
# 
#     commit message

二つ目のコマンドの update-ref では、コミットの後処理としてHEADが参照する先頭コミットを、一行目のコマンドで生成したコミットに差し替えています。
こうすることで、常に最新のCommitを参照することができるようになります。(HEADについては後述します。)

生成されたCommitオブジェクトの中身を確認してみます。

# catしてみるcat .git/objects/44/92091b4c200e7fbcc9fe0a42eabb542c2f8892
# xA
# 0E]K&a  xi:AC
#              oo^<xj-0SUųD^V&0-VJy8;b#h;uة}R^SnB`g5ÎljE5:

# zlibで解凍してみる
❯ zlib_decompress .git/objects/44/92091b4c200e7fbcc9fe0a42eabb542c2f8892 /dev/stdout
# commit 173tree 1a38e7953af851a9919d16f59e8cbe7b2580288d
# author oky-123 <sample@example.com> 1666855501 +0900
# committer oky-123 <sample@example.com> 1666855501 +0900
# 
# commit message

# 整形して表示するgit cat-file -p 4492091b4c200e7fbcc9fe0a42eabb542c2f8892
# tree 1a38e7953af851a9919d16f59e8cbe7b2580288d
# author oky-123 <sample@example.com> 1666855501 +0900
# committer oky-123 <sample@example.com> 1666855501 +0900
# 
# commit messagegit cat-file -t 4492091b4c200e7fbcc9fe0a42eabb542c2f8892
# commit

コミットオブジェクトが生成され、先ほど生成したTreeオブジェクトが参照されていることが確認できました。
※今回の場合初期コミットのためparentが入っていません。

refsとBranch

ここまで見てきたオブジェクトを利用することで、コミットツリーを生成し、変更を追うことができます。
複数人で並行して開発する際にはBranch切って開発するのが一般的かと思いますが、ブラントの最新コミットのハッシュ値を記憶するものが、参照(refs) です。
参照は.git/refs/heads の中に保存されているファイルで、参照先コミットのSHA1ハッシュ値が保存されています。

先ほど配管コマンドでコミットに相当する処理を実行したときに、update-ref を使っていましたが、このコマンドが参照を差し替える処理を担っています。
git commit する際には、この update-refが行われているため、refsは常に最新のコミットのSHA1ハッシュ値を記憶することができます。

ブランチはこの参照を利用しており、自身のブランチの先頭コミットのハッシュ値を持っています。
以下のように.git/refs/headsにファイルを作成してみると、新たなブランチが作成されます。

echo -en ${適当なコミットハッシュ} > .git/refs/heads/hoge
❯ git branch
#   hoge
# * maingit checkout hoge

HEAD

Branchが参照(refs)という仕組みを使って実現されていることがわかりましたが、ではどうやって現在のブランチを把握するのでしょうか?

これを実現するのがHEADで、中身はrefsへのパスを持っています。
例えばmainブランチにいる場合は、HEADファイルの中身はref: refs/heads/mainで、hogeブランチにいる場合はref: refs/heads/hogeとなっています。

git br
#   hoge
# * maincat .git/HEAD
# ref: refs/heads/maingit checkout hoge
# Switched to branch 'hoge'cat .git/HEAD
# ref: refs/heads/hoge

このように、HEADが参照(refs)への参照を持つことで、現在のブランチを把握することができます。

Packfile

ここまでGitオブジェクトについて見たときに、ファイルに変更があった場合には毎回新しいBlobファイルが作成されていましたが、ファイルの差分だけを保存できればデータ量の削減ができそうですよね。
この役割を担ってくれるのが、Packfileです。
Packfileでは、最新のオブジェクトをそのまま保存して、それより前のオブジェクトを増分として保存します。
これは、最新のものほどアクセスが多く、高速にアクセスできるように設計されているからです。

git gcでPackfileに圧縮してみる

では、実際にPackfileに圧縮して確認してみましょう。

# 初期化mkdir ~/tmp && cd ~/tmp
❯ git init

# 1回目のCommit(大きなファイルを作成する)curl <https://raw.githubusercontent.com/mojombo/grit/master/lib/grit/repo.rb> > repo.rb
❯ git add .git commit -m "first commit"

# 2回目のCommit(大きなファイルに少しだけ変更を加える)echo "updated" >> repo.rb
❯ git add .git commit -m "second commit"

この段階でのオブジェクトストレージは以下のようになっています。
Object, Tree, Commitオブジェクトが2個づつの計6個存在します。

find .git/objects -type f
# .git/objects/03/3b4468fa6b2a9547a70d88d1bbe8bf3f9ed0d5
# .git/objects/ab/8899f238801b52ce1c72152f38a76a9dedc723
# .git/objects/e5/2ab9c2ed1308d84f9098b6a935d5f6c888e4e3
# .git/objects/38/feecbdf638935287fd920e8f2d694aa8c28d9f
# .git/objects/a1/d55431a67aabd91724969506857ccb7c915ac5
# .git/objects/e7/ccd05f35daa2c5ab06102a59fc0b6e6e8c80d7

保存されたBlobオブジェクトをそれぞれ確認してみましょう。

# 初回に作成されたrepo.rbgit cat-file -p 033b4468fa6b2a9547a70d88d1bbe8bf3f9ed0d5
# module Grit
#
#   class Repo
#     DAEMON_EXPORT_FILE = 'git-daemon-export-ok'
#     BATCH_PARSERS      = {
#       'commit' => ::Grit::Commit
#     }
#
#     # Public: The String path of the Git repo.
#     attr_accessor :path
#     ...
#   end # Repo
# end # Grit

# 更新されたrepo.rbgit cat-file -p ab8899f238801b52ce1c72152f38a76a9dedc723
# module Grit
#
#   class Repo
#     DAEMON_EXPORT_FILE = 'git-daemon-export-ok'
#     BATCH_PARSERS      = {
#       'commit' => ::Grit::Commit
#     }
#
#     # Public: The String path of the Git repo.
#     attr_accessor :path
#     ...
#   end # Repo
# end # Grit
# updated

増分は1行ですが、変更前後のファイルがまるまる2つのBlobオブジェクトとして保存されているようです。このようにナイーブにファイル全体を保存していくと、Objectファイルが全て新規ファイルとして保存されるため、データ効率がよろしくありません。
gitでは普段リモートサーバーにpushする時やたくさんのlooseオブジェクトが存在する時に、自動的にパックしてくれますが、git gcを実行することで手動でパックすることもできます。

git gc
# Enumerating objects: 6, done.
# Counting objects: 100% (6/6), done.
# Delta compression using up to 8 threads
# Compressing objects: 100% (4/4), done.
# Writing objects: 100% (6/6), done.
# Total 6 (delta 1), reused 0 (delta 0), pack-reused 0find .git/objects -type f
# .git/objects/pack/pack-ffb2c9b5216eb5a264ba03a61689029baa7ba551.idx
# .git/objects/pack/pack-ffb2c9b5216eb5a264ba03a61689029baa7ba551.pack
# .git/objects/info/commit-graph
# .git/objects/info/packsgit verify-pack -v .git/objects/pack/pack-ffb2c9b5216eb5a264ba03a61689029baa7ba551.idx
#
# e7ccd05f35daa2c5ab06102a59fc0b6e6e8c80d7 commit 220 151 12
# a1d55431a67aabd91724969506857ccb7c915ac5 commit 171 119 163
# ab8899f238801b52ce1c72152f38a76a9dedc723 blob   22052 5796 282
# e52ab9c2ed1308d84f9098b6a935d5f6c888e4e3 tree   35 46 6078
# 38feecbdf638935287fd920e8f2d694aa8c28d9f tree   35 46 6124
# 033b4468fa6b2a9547a70d88d1bbe8bf3f9ed0d5 blob   9 20 6170 1 ab8899f238801b52ce1c72152f38a76a9dedc723
# non delta: 5 objects
# chain length = 1: 1 object
# .git/objects/pack/pack-ffb2c9b5216eb5a264ba03a61689029baa7ba551.pack: ok

6つobjectファイルがPackfileにまとめられたことが確認できました。
verify-pack の出力フォーマットは以下の通りですので、照らし合わせて確認してみます。

  • SHA-1 type size size-in-packfile offset-in-packfile (deltifiedされていないもの)
  • SHA-1 type size size-in-packfile offset-in-packfile depth base-SHA-1 (deltifiedされたもの)

初期作成されたBlobオブジェクト 033b4468fa6b2a9547a70d88d1bbe8bf3f9ed0d5 はsizeが9まで圧縮されて、 ab8899f238801b52ce1c72152f38a76a9dedc723 をベースにdeltified(増分化?)されているようです。
一方、更新時に作成されたBlobオブジェクト ab8899f238801b52ce1c72152f38a76a9dedc723 はdeltifiedされずにlooseなオブジェクトとして保存されています。

このようにして、最新のオブジェクトをそのまま保持し、古いファイルを増分としてパックしています。より詳細な参照Packfileのフォーマットについては、こちら↓の記事をご参照ください。

参考

Discussion

ログインするとコメントできます