Git Internals Deep Dive — Object Model、Packfile、Mergeアルゴリズム、Reflog、プロトコル完全解説 (2025)

TL;DR

• Gitはcontent-addressableファイルシステムである。バージョン管理はその上に構築されたレイヤーに過ぎない。全データ（ファイル、ディレクトリ、Commit）はSHA-1ハッシュで参照される。
• 4種類のオブジェクト: Blob（ファイル内容）、Tree（ディレクトリ）、Commit（スナップショット + メタ）、Tag（署名付き参照）。
• Loose Object vs Packfile: 最初は各オブジェクトが個別ファイル（.git/objects/ab/cd...）、後にPackfileに圧縮しDelta保存。
• Refs: Branch/TagはCommitハッシュを指すテキストファイルのみ。HEADは現在Checkoutされているもの。
• Index: ステージングエリア。次のCommitのTreeを事前に構成するバイナリファイル。
• Merge: 2021年にrecursive → **ort**へ既定変更。500倍高速な場合も。
• Rebase: Commitを1つずつcherry-pickし新しいbaseへ再配置。Commitハッシュが変わる点に注意。
• Reflog: HEADとrefsのあらゆる変更履歴。「失ったCommit」を復旧する鍵。
• Packfile: Delta圧縮 + インデックス（.idx）+ Bitmap（.bitmap）。Push/FetchをKB規模に。
• Protocol: Smart HTTP（最も一般的）、SSH、Git protocol。Clientが「持っているもの」を宣言 → Serverが必要なものだけ送信。

1. Gitの哲学 — 「ファイルシステムであってバージョン管理ではない」

2005年、Linuxカーネルで使われていたBitKeeperが無料ライセンスを撤回。Linusは2週間でGitを作った。設計目標は分散、高速、完全性、ブランチ/マージのファーストクラス化。

Linusの洞察: 従来のVCSは誤った抽象を採用していた。ファイル間のdiffではなくスナップショットを保存すべき。

Content-Addressable Filesystem

本質はキーバリューストア:

SHA-1ハッシュ → オブジェクト内容

保存: 「この内容を保存して」 → SHA-1が返る。取得: 「このハッシュの内容をくれ」 → オブジェクトが返る。Branch、Merge、履歴はすべてこの上のレイヤー。

mkdir /tmp/gitrepo && cd /tmp/gitrepo
git init
echo "Hello, Git" | git hash-object -w --stdin
# 3b18e512dba79e4c8300dd08aeb37f8e728b8dad

git cat-file -p 3b18e512
# Hello, Git

hash-object -wはヘッダを付与しSHA-1を計算、zlibで圧縮し.git/objects/3b/18e5.../に保存する。

2. オブジェクトモデル

2.1 4種類

• Blob: 純粋なファイル内容（メタなし）。内容が同じなら同一Blob。
• Tree: ディレクトリ一覧。名前 → モード → Blob/Treeハッシュ。
• Commit: Treeへのポインタ + メタデータ（親、著者、メッセージ）。
• Tag: Annotated Tag。CommitをCommitを指す署名/メッセージ付きオブジェクト。

2.2 Blob

形式: blob <byte_length>\0<content> → SHA-1 → zlib圧縮。10,000ファイルが同じ"Hello World"なら、Blobは1つだけ保存される。

2.3 Tree

tree <length>\0
100644 blob abc123... README.md
040000 tree def456... src
100755 blob ghi789... build.sh

各エントリはモード（100644通常、100755実行可、040000Tree、120000symlink、160000submodule）、タイプ、SHA-1（20バイトバイナリ）、null終端名。

git cat-file -p HEAD^{tree}

Treeは再帰的にファイルシステムスナップショットを表現する。

2.4 Commit

commit <length>\0
tree 3c4e9cd789...
parent 5a9d8b41...
author Linus Torvalds <torvalds@linux.org> 1234567890 -0700
committer Linus Torvalds <torvalds@linux.org> 1234567890 -0700

Initial commit

フィールド: tree（スナップショット）、parent（初回は無し、Merge Commitは2つ以上）、author（変更を作った人）、committer（適用した人。RebaseやCherry-pick時にauthorと異なる）、メッセージ。

2.5 Tag

Annotated Tag（git tag -a）はobject、type、tag、tagger、メッセージ、任意のPGP署名を持つオブジェクト。Lightweight Tagは単なるref。

2.6 ハッシュチェーン

commit → tree → blob
              → blob
              → tree → blob
commit → parent commit → parent commit → ...

全てのリンクがハッシュ。1バイト変えると全祖先ハッシュが連鎖的に変わる → 完全性保証。

2.7 SHA-1 vs SHA-256

Gitは元々SHA-1。2017年のSHAttered（Google）を受けSHA-256対応を追加（git init --object-format=sha256）。両者は相互運用不可。多くのプロジェクトは依然SHA-1。

2.8 Loose Objectの保存

.git/objects/
├── 3b/
│   └── 18e512dba79e4c8300dd08aeb37f8e728b8dad
├── 5a/
│   └── 9d8b41...

先頭2文字でディレクトリ分割（256バケット）し、巨大ディレクトリによるファイルシステム遅延を避ける。

3. Refs — 意味のある名前

3.1 Ref = ハッシュの別名

cat .git/refs/heads/main
# 3c4e9cd789abc...

それだけである。「mainブランチ」はCommitハッシュを持つ1つのファイル。

3.2 HEAD

cat .git/HEAD
# ref: refs/heads/main

Detached HEADはハッシュを直接保持。

3.3 TagとRemote Refs

Lightweight TagはCommitを直接指す。Annotated TagはTagオブジェクト経由。Remote refsは.git/refs/remotes/origin/に存在し、最後にfetchした状態を保持。ローカルBranchとは完全に独立。

3.4 packed-refs

Refが大量になると個別ファイルは重い。Gitは定期的に.git/packed-refsにまとめる。個別ファイル（unpacked）が優先。

3.5 Symbolic Ref

Refが他のRefを指せる（HEADが典型）。git symbolic-ref HEADで確認。

4. Index — ステージングエリア

4.1 役割

作業ディレクトリ → (git add) → Index → (git commit) → Commit

Indexは次のCommitのTreeを先に構成するキャッシュ。

4.2 構造

.git/indexはバイナリ: ヘッダ + エントリ（ctime、mtime、dev、ino、mode、uid、gid、サイズ、SHA-1、flags、path）+ チェックサム。

git ls-files --stage
# 100644 a906cb2a4a904a15... 0 README.md
# 100644 3b18e512dba79e4c... 0 src/main.c

4.3 なぜIndexがあるのか

1. 部分Commit: ファイル単位で選択的にCommit可能。
2. 性能: inode/mtime/sizeのキャッシュでgit statusが高速。
3. Merge中間状態: 衝突時、Indexに複数stage（1 祖先、2 ours、3 theirs）を保持。

4.4 3ツリーモデル

HEAD              Index            Working Tree
(直前Commit)  →  (Staged)      →  (Unstaged)

git statusはHEAD vs Index（"Changes to be committed"）とIndex vs Working Tree（"Changes not staged"）を比較する。

5. Packfile — 効率的な保存

5.1 Loose Objectの限界

10,000ファイル × 10回変更 = 100,000 Loose Object。inode浪費、ディスク浪費。さらにDelta圧縮が効かない — 100MBファイルの10バイト編集で100MBの新Blobが作られる。

5.2 Packfileの配置

.git/objects/pack/
├── pack-abc123.idx     # オフセット検索用インデックス
├── pack-abc123.pack    # 実データ
├── pack-abc123.bitmap  # reachability bitmap（任意）

5.3 Packフォーマット

ヘッダ（PACK + version + オブジェクト数）、オブジェクト群（type + 圧縮データ、deltaはOFS_DELTAかREF_DELTAのbase参照を持つ）、20バイトチェックサム。

5.4 Delta圧縮

BlobがBに似ていれば:

PackのB: 全内容（zlib圧縮）
PackのA: 「Bを参照し、以下の編集を適用」

編集命令: COPY（baseのoffset XからNバイト）、INSERT（新規Nバイト挿入）。

例: "Hello, World" → "Hello, Git":

A = COPY(0, 7) + INSERT("Git") + COPY(12, 1)

5.5 Base Object選定

ヒューリスティック: 同ファイル名の以前バージョン、サイズ近似、接頭辞一致など。git repack -fで強制再構築。

5.6 Delta Chain

V1 (full) ← V2 (delta of V1) ← V3 (delta of V2) ← ...

チェーンを遡って復元。pack.depth（既定50）で上限。

5.7 Pack Index (.idx)

fanout表（256、先頭バイトごとのオフセット）+ ソート済SHA-1一覧 + CRC32 + オフセット。O(log n)検索。

5.8 Reachability Bitmap

Git 2.0以降。各選定CommitにReachableオブジェクトのBitmapを保持。git fetchが「必要X、既にあるY」を高速計算。GitHubのgit cloneが速い理由。

6. Object Storageの動作

6.1 生成

git add file.txt: ファイル読み込み → Blobハッシュ計算 → .git/objects/に存在確認 → 無ければzlibで保存 → Index更新。

6.2 Commit

git commit -m "...": Indexからtreeオブジェクトを再帰的に生成 → tree + parent + author + messageでCommitオブジェクト生成 → HEADのrefを更新。

6.3 Checkout

git checkout main: refs/heads/main読み込み → CommitのTreeを読み → Tree走査で作業ディレクトリ更新 → Index同期 → HEAD更新。

6.4 GCとPrune

git gc

Loose ObjectをPackfileに圧縮、到達不能なオブジェクト（2週間超のdangling）を削除。Loose Objectが6700を超えると自動GCが発火。git prune --expire=nowで即時削除（reflogが残っていると消えない）。

7. Mergeアルゴリズム

7.1 Three-way Merge

• Common Ancestor: 共通祖先Commit。
• Ours: 現在のBranch先端。
• Theirs: 取り込むBranch先端。

各ファイルについて: Oursのみ変更 → Ours、Theirsのみ変更 → Theirs、両者同じ変更 → その変更、両者異なる変更 → 衝突。

7.2 Fast-forward

mainがBranchの厳密な祖先の場合、mainをそのまま進めるだけ。Merge Commitなし。

7.3 Three-way Merge Commit

履歴が分岐していれば、2つの親を持つMerge Commit Mを生成。

7.4 Recursive → Ort

2021年までGitの既定はrecursive。Criss-cross Merge（共通祖先が複数）では祖先たちを再帰的にMergeするため、大規模レポで指数的に遅くなる事があった。

Ort（Ours/Recursive/Theirs）はElijah Newrenが再実装: 500倍速のケース、Rename Detectionの向上、Subtree Merge、メモリ効率の大幅改善。Git 2.33（2021）から既定。多くの開発者は気付かなかった — Mergeが単に速くなっただけ。

7.5 Rename Detection

50%以上の内容類似でリネームとみなす。別Branchでの編集は旧名ではなく新名に適用されるべき。OrtはこれをThree-way Mergeはより正確かつ高速に処理する。

7.6 衝突解決

<<<<<<< HEAD
int x = 1;
=======
int x = 2;
>>>>>>> branch

編集後、git add、git commit。Indexの多段stageがこれを支える。

7.7 Strategy オプション

• -X ours / -X theirs: 衝突時に自動選択。
• -X ignore-all-space: 空白無視。
• -X rename-threshold=80: Rename検出閾値。

Strategy（-s）: ort（既定）、recursive（legacy）、resolve、octopus（複数Branch、衝突無しのみ）、ours（Theirsを捨て履歴だけ合流）。

8. Rebaseメカニクス

8.1 アイデア

main:    A → B → C
branch:  A → B → D → E

git rebase main 後:

main:    A → B → C
branch:  A → B → C → D' → E'

D'、E'は新Commit。同じ変更でも親が違うためSHA-1も違う。

8.2 実際の動作

1. mainの先端を仮HEADに。
2. Branch固有のCommitを順に並べる。
3. 各CommitをCherry-pick: 祖先算出 → Three-way Merge → 新しい親で新Commit生成。
4. 全成功ならBranchのrefを新先端へ。

8.3 Interactive Rebase

git rebase -i HEAD~5

アクション: pick、reword、edit、squash、fixup、drop。履歴を書き換える（新ハッシュ）。

8.4 公開Branchでの危険

RebaseはCommitハッシュを変える。同僚が旧ハッシュに基づいて作業していれば、Force Push後に履歴が食い違う。共有Branchはmergeで、自分のBranchはrebaseで。

8.5 Force-with-lease

git push --force-with-lease

最後にfetchした時と同じ状態の場合のみForce Pushを許可。他人のPushを上書きしない最低限のセーフティネット。

9. Reflog — セーフティネット

9.1 Reflogとは

HEADと各Refの変更履歴をローカルに記録するログ。git reset --hard、git rebase、git checkout、git commitなど全ref変更がタイムスタンプ付きで.git/logs/以下に保存される。

git reflog
# abc123 (HEAD -> main) HEAD@{0}: commit: Add feature
# def456 HEAD@{1}: commit: Fix bug
# ghi789 HEAD@{2}: rebase finished

9.2 復旧例

git reflog
# abc123 HEAD@{1}: commit: 失ったCommit
# def456 HEAD@{0}: reset: moving to HEAD~1

git reset --hard abc123

Reflogにハッシュが残っている限りオブジェクトは.git/objects/に存在する。

9.3 保存と期限

.git/logs/HEADと.git/logs/refs/...。既定の期限: reachableは90日、unreachableは30日。git gcが整理。

9.4 復旧ルーチン

慌てない → git reflog → 目的のハッシュ特定 → git reset --hard <hash>またはgit cherry-pick <hash>。30日以内ならほぼ全ての失敗は復旧可能。

10. Partial CloneとSparse Checkout

10.1 巨大リポの問題

Linuxカーネル: 3GB。Chromium: 50GB。完全Cloneは時間と容量の浪費。

10.2 Shallow Clone

git clone --depth=1 https://github.com/...

最新Commit 1つ。CI/CDでよく使う。完全履歴が必要なgit pullには不向き。

10.3 Partial Clone（Git 2.19+）

git clone --filter=blob:none https://github.com/...

Commit + Tree全取得。Blobは必要時に遅延取得。

10.4 Sparse Checkout

git sparse-checkout init
git sparse-checkout set src/feature-x docs

指定ディレクトリのみ作業ツリーに展開。Monorepo必須。

10.5 併用

git clone --filter=blob:none --sparse https://...
git sparse-checkout init
git sparse-checkout set src/mymodule

50GBレポが1GB以下で運用可能。

10.6 Git LFS

大容量ファイルは別サーバに、Git側はポインタ（約60バイト）のみ。画像・動画・ビルド成果物に好適。差分diffは効かない。

11. Gitプロトコル

11.1 Clone/Fetchの流れ

1. Refs交換。
2. "have" / "want"ネゴシエーション（Pack Negotiation）。
3. Serverがpackfile生成 → 送信。

11.2 Smart HTTP

最も一般的（GitHub、GitLab）:

GET  /repo.git/info/refs?service=git-upload-pack
POST /repo.git/git-upload-pack

HTTP上のGit固有プロトコル。Firewallに優しい（443番）。

11.3 SSH

ssh git@github.com "git-upload-pack 'user/repo.git'"

SSH上に同プロトコル。HTTPオーバーヘッドが無く速いことも。

11.4 Git Protocol（9418番）

原型のGit Protocol。認証なし（匿名Cloneのみ）。現在ほぼ非使用。

11.5 Protocol V2（2018以降）

改善版。Capability Negotiation、ls-refsフィルタ、より効率的な圧縮、Stateless。Git 2.18以降、GitHub/GitLabで既定。

11.6 Packfile転送の最適化

ServerはReachability Bitmapで必要オブジェクトを即座に算出 → Clientが既に持つ分を除外 → Delta圧縮してPack生成。大規模ホスティングは事前計算Pack + ユーザ毎差分を動的圧縮。

12. デバッグ・探索ツール

git cat-file -t abc123    # type
git cat-file -s abc123    # size
git cat-file -p abc123    # pretty-print
git cat-file --batch-all-objects --unordered

git rev-list HEAD
git rev-list --count HEAD
git rev-list --objects HEAD

git verify-pack -v .git/objects/pack/pack-abc123.idx
git fsck --full
git show-ref
git count-objects -v

13. よくある実戦シナリオ

13.1 誤ってForce Push

git reflog
git push --force-with-lease origin main:<元のハッシュ>

13.2 膨大な衝突

git merge --abort
git checkout feature
git rebase -i main
git checkout main
git merge feature

13.3 Commitを分割したい

git rebase -i HEAD~3
# 対象Commitを 'edit'
git reset HEAD^
git add file1 && git commit -m "前半"
git add file2 && git commit -m "後半"
git rebase --continue

13.4 機密情報を誤コミット

git reset --soft HEAD~1   # 直近なら
# または古いCommitの場合:
git filter-branch --index-filter \
  'git rm --cached --ignore-unmatch secrets.txt' HEAD
# あるいはBFG Repo-Cleaner

Force Push必須、全Cloneに影響。秘密情報は既に漏れた前提で直ちに交換する。

13.5 このファイルはいつ追加された?

git log --all --full-history --source -- <file>
git log --diff-filter=A -- <file>
git log -p -- <file>
git blame <file>

14. 2024-2025年のGit

14.1 git worktree改善

git worktree add ../feature-x feature-x

複数Branchを同時Checkout。Context Switchingなしで複数PRを触れる。

14.2 Reftable

Refが大量にある場合に高速なO(log n)検索の単一ファイル形式。2024年は実験的、2025年に安定化中。

14.3 Scalar

Microsoft製巨大レポ最適化ツール。Git 2.38以降に統合。Partial Clone + Sparse Checkout + Background Maintenanceを自動設定。

14.4 SSH Signing

git config gpg.format ssh
git config user.signingkey ~/.ssh/id_ed25519.pub
git commit -S -m "Signed"

GPGを使わずSSH鍵でCommit署名。GitHubは2022年以降サポート。

15. まとめ

本質: Content-addressable filesystem、SHA-1ハッシュ → オブジェクト
Objects: Blob（内容）、Tree（ディレクトリ）、Commit（スナップショット+メタ）、Tag
Storage: Loose (.git/objects/ab/cd...) / Pack (*.pack+*.idx+*.bitmap)
Refs:    refs/heads、refs/tags、refs/remotes、HEAD、packed-refs
Index:   .git/index バイナリ、3ツリーモデル（HEAD/Index/Working）
Merge:   Three-way Merge、Fast-forward、ort（2021+）、Rename Detection
Rebase:  Cherry-pickで新Commit、新ハッシュ、公開Branchでは避ける
Reflog:  Ref変更の記録、30-90日保持
巨大リポ: --depth=1、--filter=blob:none、Sparse Checkout、LFS
Protocol: Smart HTTP / SSH / Protocol V2 / Dumb Protocol（旧）
Tools:   cat-file、rev-list、fsck、verify-pack、count-objects、reflog

16. クイズ

参考になったら、以下も参照:

• "Binary Serialization: Protobuf/Thrift/Avro/FlatBuffers" — Gitのバイナリ形式と比較。
• "Docker BuildKit & Image Layers Deep Dive" — もう1つのContent-addressableシステム。
• "RocksDB & LSM-Tree Deep Dive" — Append-only + Background Compactionの哲学。
• "Consistent Hashing & Virtual Nodes" — Content Addressingの分散版。