Mobile Factory Tech Blog

技術好きな方へ!モバイルファクトリーのエンジニアたちが楽しい技術話をお届けします!

gitを自分で実装して内部を理解しよう

要約

git内部のデータ格納に関するサブコマンド、git cat-filegit hash-object を自分でPerlで実装しgit内のデータの保存方法について知る

目次

  • イントロダクション
  • git内部のデータの確認
  • perl実装の紹介

実装

github.com

イントロダクション

自己紹介

駅メモにて主にバックエンドを担当しているid:toricorです。 仕事ではPerl実装のサーバ周りを触ることが多いです。

仕事以外では、以前Perlで簡単なJVMを書きました

毎日使うソフトウェアといえば

gitは欠かせないですよね。 でも毎日の仕事で生成されるあの膨大なファイルやコミットを、内部でどのように記録し管理しているか気になりませんか。私は気になりました。

本家の説明によると

Git は内容アドレスファイルシステムです。 素晴らしい。 …で、それはどういう意味なのでしょう? それは、Gitのコアの部分はシンプルなキー・バリュー型データストアである、という意味です。 Git - Gitオブジェクト

少しわかりにくいですね

Gitを自分で書いたら理解できるかも!?

"Write yourself a Git!" https://wyag.thb.lt/

gitの自力実装の方法を紹介してくれています。 数百行程度のPython実装でgitのいろいろなサブコマンドが実装できます。

以前Python実装のままチーム内で紹介したのですが、弊社はPerlをよく使う会社なので今回Perlで書き直しました(ただし一部のみ)。

以降はデータの格納という点に注目してgitを見ていきたいと思います。

内部のデータの確認

.git のどこにデータが入るのだろうか

gitを使う場合に必要なデータ(ブランチ、コミット、など)は.gitに全て格納されています。 適当なGitプロジェクトをつくり、コミットをした場合に .git の中身がどのように変わっていくかをまずは確認します。

git init 直後

% tree .git                                                                                       
.git
├── HEAD
├── config
├── description
├── hooks
│   ├── applypatch-msg.sample
│ (省略)
│   └── update.sample
├── info
│   └── exclude
├── objects
│   ├── info
│   └── pack
└── refs
    ├── heads
    └── tags

8 directories, 16 files

ファイル作成 & git add

% echo 'print "Hello Git!\n";' > hello.pl                                                                                  
% git add .                                                                                                                        
% tree .git                                                                                                        
.git
├── HEAD
├── config
├── description
├── hooks
│   ├── applypatch-msg.sample
│ (省略)
│   └── update.sample
├── index
├── info
│   └── exclude
├── objects
│   ├── 36
│   │   └── 9b01f4c6a00c39f0362e3f6c9648c2dc178b47  <-- ファイルが増えたぞ??
│   ├── info
│   └── pack
└── refs
    ├── heads
    └── tags

9 directories, 18 files

git add .を実行後、.git/objects/ 以下に1つファイルが増えました。

git commit

% git commit -m 'add an example file'                                                                                         
[master (root-commit) dc8cc4a] add an example file
 1 file changed, 2 insertions(+)
 create mode 100644 hello.pl
% tree .git                                                                                                            
.git
├── COMMIT_EDITMSG
├── HEAD
├── config
├── description
├── hooks
│   ├── applypatch-msg.sample
│ (省略)
│   └── update.sample
├── index
├── info
│   └── exclude
├── logs
│   ├── HEAD
│   └── refs
│       └── heads
│           └── master
├── objects
│   ├── 36
│   │   └── 9b01f4c6a00c39f0362e3f6c9648c2dc178b47
│   ├── dc
│   │   └── 8cc4a05ebbb7771a46e61bfe6dcfbefb905eaa  <-- これと
│   ├── dd
│   │   └── b362c0207a67dc4d63684794a50fcdaf69a155  <-- このファイルがcommitしたら増えた!
│   ├── info
│   └── pack
└── refs
    ├── heads
    │   └── master
    └── tags

14 directories, 24 files

コミット操作により、更に2つのファイルが生成されました。 これらはGitオブジェクトと呼ばれます。

生成されたファイル(Gitオブジェクト)の中身を見てみる

% less .git/objects/36/9b01f4c6a00c39f0362e3f6c9648c2dc178b47                                                                
".git/objects/36/9b01f4c6a00c39f0362e3f6c9648c2dc178b47" may be a binary file.  See it anyway?

バイナリファイルでした

% xxd .git/objects/36/9b01f4c6a00c39f0362e3f6c9648c2dc178b47                                                        
00000000: 7801 4bca c94f 5230 3264 2828 cacc 2b51  x.K..OR02d((..+Q
00000010: 50f2 48cd c9c9 5770 cf2c 51e4 52b2 e602  P.H...Wp.,Q.R...
00000020: 0087 f508 5c

ちょっとこれでは内容がよくわからないですね。

Gitオブジェクトのフォーマットについて

実はコミットや特定の時点でのファイルを表すGitオブジェクトは、ハッシュ値に基づいたファイルとなります。 それぞれオブジェクト作成時に40文字からなるSHA-1ハッシュが計算され最初の2文字をディレクトリ、残り38文字がファイル名のファイルとなります。

例: .git/objects/36/9b01f4c6a00c39f0362e3f6c9648c2dc178b47

ハッシュ値が369b01f4c6a00c39f0362e3f6c9648c2dc178b47のとき36というディレクトリに9b01f4c6a00c39f0362e3f6c9648c2dc178b47 というファイルが作られます。

Q. Gitオブジェクトの中身はどういう変換を受けている? (普通のファイル: blob(後述)の場合)

  1. 普通のファイルの内容にヘッダーをつけて、zlibを使い圧縮されています

ヘッダー: オブジェクトタイプ + 空白 + データの長さ + ヌルバイト

Gitオブジェクトを読み取るコマンド: git cat-file

Gitオブジェクトを扱うためのgitのサブコマンドを紹介しておきます。 読み取り専用のサブコマンドがあります。

git-cat-file - Provide content or type and size information for repository objects

では実際に今回生成された3つのGitオブジェクトの内容を見てみます。 -t オプションでGitオブジェクトのタイプを表示します。

% git cat-file -t 369b01f4c6a00c39f0362e3f6c9648c2dc178b47                                                                            
blob
% git cat-file -t dc8cc4a05ebbb7771a46e61bfe6dcfbefb905eaa                                                                    
commit
% git cat-file -t ddb362c0207a67dc4d63684794a50fcdaf69a155                                                          
tree

-p オプションでもう少し詳しく見てみましょう

# blob
% git cat-file -p 369b01f4c6a00c39f0362e3f6c9648c2dc178b47                                                          
print "Hello Git!
";

# commit
% git cat-file -p dc8cc4a05ebbb7771a46e61bfe6dcfbefb905eaa                                                 
tree ddb362c0207a67dc4d63684794a50fcdaf69a155
author toricor <toriyabe@mfac.jp> 1597738778 +0900
committer toricor <toriyabe@mfac.jp> 1597738778 +0900

add an example file

# tree
% git cat-file -p ddb362c0207a67dc4d63684794a50fcdaf69a155                                               
100644 blob 369b01f4c6a00c39f0362e3f6c9648c2dc178b47    hello.pl

このようにGitオブジェクトは上に示したblob, commit, treeタイプと他にtagタイプの4つから成り立っています。

Gitオブジェクトを書き込むコマンド: git hash-object

git-hash-object - Compute object ID and optionally creates a blob from a file

git cat-file と対になるコマンドになります。Gitオブジェクトにしたいファイルのハッシュ値を計算して(-w付きなら).git/objects/以下にGitオブジェクトファイルを作成します。

Gitを実装しよう

git cat-filegit hash-object を理解できればgit内部のデータの格納について基本は理解したといえそうです。

参考にしたサイトはPython実装ですが、 Perlでこれらのコマンドを実装してみました。

実装のポイント

いくつかポイントを絞って実装を紹介します。

例1: SHA-1のハッシュ値を求める

Digest::SHA1モジュールのsha1_hexが使えます。

use Digest::SHA1 qw/sha1_hex/;

my $data = ...; # 適当なデータ
my $len = length($data); # データの長さ

# build a header
my $fmt = 'blob'; # commit/blob/tree/tag
my $result = "$fmt $len\x00$data";

# e.g. 369b01f4c6a00c39f0362e3f6c9648c2dc178b47
my $digest = sha1_hex($result);

例2: Gitオブジェクトを解凍してデータを確認する

  • バイナリファイルを読むのでopenの第2引数に"<:raw"を指定します
    • binmode($fh)でもいいです
  • 圧縮・解凍にはCompress::Zlibモジュールが使えます
# simple_uncompress.pl
# 適当なPerlプロジェクトを作成し簡単なスクリプトを用意しました

use Compress::Zlib qw//;

sub dump_commit {
    my ($path) = @_;
    open(my $fh, "<:raw", $path) or die $!;

    my $bufs;
    while (read $fh, my $buf, 1024) {
        $bufs .= $buf;
    }
    close $fh;

    my $uncompressed = Compress::Zlib::uncompress($bufs);
    print $uncompressed;
}

# git logした結果から適当なものを選んでcommitタイプのGitオブジェクトを見てみる
my $path = '.git/objects/8f/083b8b230e833e1ea7e679fac265ca6a422c02';
dump_commit($path);
% carton exec -- perl simple_uncompress.pl
commit 220tree 6e7c0d7b065c5bd3708c8aeb7e85c81ccffbb01d
parent 97a587d82878afd2d81d56b30d3dd9a910316b8a
author toricor <toriyabe@mfac.jp> 1596040311 +0900
committer toricor <toriyabe@mfac.jp> 1596040311 +0900

refactor HashObject

ヘッダ+コミットからなる表示が見えました!

Gitを動かそう

では先の実装ポイントを踏まえて実装したperlのスクリプトを実行してみましょう

ハッシュ値 => 内容表示 ( cat-file )

コミットを調べます

% carton exec -- perl main.pl cat-file -t 8f083b8b230e833e1ea7e679fac265ca6a422c02
commit

% carton exec -- perl main.pl cat-file -p 8f083b8b230e833e1ea7e679fac265ca6a422c02
tree 6e7c0d7b065c5bd3708c8aeb7e85c81ccffbb01d
parent 97a587d82878afd2d81d56b30d3dd9a910316b8a
author toricor <toriyabe@mfac.jp> 1596040311 +0900
committer toricor <toriyabe@mfac.jp> 1596040311 +0900

refactor HashObject

コミットの中身が表示できました

ファイル => Gitオブジェクト

適当なファイルのハッシュ値を求めます

% echo 'print 123;' > 123.pl
% carton exec -- perl main.pl hash-object -t blob 123.pl
4a8a8bc47b318a7ca83c5f739440e969fef59325

ハッシュ値を求めるだけではなくGitオブジェクトも作ってみます(ファイルはblobタイプです)

% carton exec -- perl main.pl hash-object -w 123.pl
4a8a8bc47b318a7ca83c5f739440e969fef59325
% ls .git/objects/4a/8a8bc47b318a7ca83c5f739440e969fef59325
8a8bc47b318a7ca83c5f739440e969fef59325

Gitオブジェクトが.git/objects以下に作られました

% git cat-file -t 4a8a8bc47b318a7ca83c5f739440e969fef59325
blob
% git cat-file -p 4a8a8bc47b318a7ca83c5f739440e969fef59325
print 123;

本物のgit cat-fileコマンドからもきちんとGitオブジェクトの内容が認識されているようですね!

まとめ

意外とgitは自分で作れます!

参考文献

ISUCON10でPerlの参考実装をしました

こんにちは。id:kfly8 です。普段はヒューマンリレーションズ部でエンジニア組織開発をしています。

先日、ISUCON *1でPerlの参考実装をやらせてもらったのですが、とても楽しかったです!貴重な機会をありがとうございました。また、"あのISUCON"の運営裏側を見れて、苦労、凄さなど身近な所で感じることができました。 微力ながら協力できて嬉しかったです。

この記事では、Goの参考実装からPerlへの移植をして考えたことを書きたいと思います。今後、移植をされる方の何かの参考になれば幸いです。注意として、ここでの考えは公式の見解ではなく、あくまで個人的な見解です。

できるだけGo実装に寄せる

移植は、できるだけオリジナル実装のGoに寄せるよう心がけました。 実装の乖離が大きいと競技としてフェアでない、移植ミスの際に気づきやすくなりそう、そんなことが理由です。

具体的には、次の2つを行いました。

  1. Cpanel::JSON::XS::Typeで、JSONレスポンスを明示
  2. 返り値でエラーも返してみる

1. Cpanel::JSON::XS::Typeで、JSONレスポンスを明示

これまでのISUCONのPerl実装では、ベンチマーカーの期待通りのJSONレスポンスをエンコードするために、JSON::Typesを利用していました。 ですが、今回はCpanel::JSON::XS::Typeを利用し、JSONレスポンスの構造を明示的にしました。

# JSONレスポンスを明示しておく
use constant Chair => {
    id          => JSON_TYPE_INT,
    name        => JSON_TYPE_STRING,
    description => JSON_TYPE_STRING,
    thumbnail   => JSON_TYPE_STRING,
    price       => JSON_TYPE_INT,
    height      => JSON_TYPE_INT,
    width       => JSON_TYPE_INT,
    depth       => JSON_TYPE_INT,
    color       => JSON_TYPE_STRING,
    features    => JSON_TYPE_STRING,
    kind        => JSON_TYPE_STRING,
    popularity  => undef,
    stock       => undef,
};

use constant ChairSearchResponse => {
    count  => JSON_TYPE_INT,
    chairs => json_type_arrayof(Chair),
};

Goのstructを使って明示する書きっぷりに、雰囲気は似ている(?)と思います。JSONレスポンスの構造が把握しやすいメリットだけでなく、パフォーマンス面でもJSON::Typesより優位になります。通常のJSONエンコードは、値が文字列か数値かといった内部の状態を確認してエンコードしますが、この場合、値が何であれ型宣言の通りエンコードを試みます。JSON::Typesの実行コスト分、エンコード速度は優位になります。JSON::Typesは、簡単、簡潔に利用できるメリットがありましたが、今回は変更してみました。

2. 返り値でエラーも返してみる

返り値でエラーも返すようにしてみたのですが、効果は特に得られなかった趣味の話です。

例えば、普段であれば、system(@cmd) or die '..'と異常時はorで繋ぐところ、次のように書いていました。

my $err = system(@cmd);
if ($err) {
    ...
}

range_idからrangeを取り出すget_range関数も、エラーも返すようにしました。

my ($chair_price, $err) = get_range($CHAIR_SEARCH_CONDITION->{price}, $price_range_id);
if ($err) {
    ...
}

次のようにget_rangeを剥がすこともできましたが、参考実装のGoに寄せました。

my $chair_price = $CHAIR_SEARCH_CONDITION->{price}{ranges}{$price_range_id};
if (!$chair_price) {
    ...
}

ただPerlの場合、例外で処理するケースがどうしても混ざるので、一貫性が出せず、中途半端でした。趣味でした。

余談

移植は、予定スケジュールよりも早く参考実装を運営チームが用意してくれたので、かなり前持って作業を始めることができました。ただ、悩んだ所、躓いた所もあったので、早めに始められて助かりました。特に次のような所で悩みました。

perlのビルドにuselongdoubleオプションを利用

perlのビルドオプションにuselongdoubleを利用しました。uselongdoubleは、拡張倍精度浮動小数点を扱うためのビルドオプションで、perl -V:nvsizeが8でなく16になります。変更した理由は、緯度経度で桁が足りなくなる為です。例えば、緯度:34.560727610897644 が、緯度:34.5607276108976 となってしまっていました。他の選択肢として、任意桁を扱うモジュール(Math::BigFloatなど)を考えましたが、Go実装と乖離が大きくなりそうな為、不採用にしました。オチとして、PHPでも同様の問題を抱え、結局ベンチマーカーのチェックは緩くなりました。今回の移植で一番悩み、不安だった所です。

isa operator

せっかく、perl5.32を採用したので、本筋でないところにしれっと利用しました。

eval {
    if ($err) {
        die $self->res_no_content($c, HTTP_NOT_FOUND);
    }
}
if ($@) {
    # $@が blessされているかどうかとかいちいち確認しなくて済んで便利
    return $@ if $@ isa Plack::Response;
}

isa operatorはさらっと書けていいですね。ただ、そもそも、evalでなく、try/catchを使う方が直感的で実務の場面に近いと感じるので、evalを無くすかどうか迷いました。Syntax::Keyword::Tryを採用すれば、次のように簡潔に書けるのですが、Try::Tinyを普段利用している人にとっては逆にハマりどころになると思い、今回は見送りました。Syntax::Keyword::Tryの魅力については、papix氏の記事を参照ください。

use Syntax::Keyword::Try;

try {
    if ($err) {
        # ここでreturnしても、直感通り動く。(普通のことなんだけど・・!)
        return $self->res_no_content($c, HTTP_NOT_FOUND);
    }
}
catch { ... }

cpmを採用

CPANインストーラーに、cpmを利用しました。速いですね。Perlの公式系でもcpmを利用されている例があり、採用しても受け入れてもらえると思い、入れさせてもらいました!

秘密のアレ

ISUCONの恒例(?)でしょうか。気づいてもらえたみたいで、よかったです。

おわりに

初めての移植でしたが、本番一発勝負で受け入れてもらえるか、きちんと動作するか緊張感がありましたが、その分充実感も大きかったです。楽しかったです!ありがとうございました!

*1:ISUCON」は、LINE株式会社の商標または登録商標です。