← all posts
DEV 2026.05.05 · 12 min read Intermediate

Git history는 왜 DAG인가

Commit 객체의 불변성 설계부터 Reachability 탐색 알고리즘, commit-graph 캐시까지 — Git이 history를 DAG로 표현하는 이유와 그 귀결을 추적한다.

📚 Git In Depth 4 / 16
  1. 01 Git이 파일이 아닌 SHA로 세상을 보는 이유
  2. 02 Git의 모든 포인터는 어디에 살고 있는가
  3. 03 Git은 파일 변경을 어떻게 추적하는가
  4. 04 Git history는 왜 DAG인가
  5. 05 Git Branch는 왜 이렇게 가벼운가
  6. 06 Git merge는 어떻게 충돌을 판단하는가
  7. 07 Rebase는 왜 새 commit을 만드는가
  8. 08 Git에서 변경을 되돌린다는 것의 의미
  9. 09 git stash는 어떻게 두 영역을 동시에 보존하는가
  10. 10 git push/fetch는 내부에서 무슨 일이 일어나는가
  11. 11 Git은 어떻게 실수를 복구하는가
  12. 12 Git Hook은 어디서 막고 어디서 통과시키는가
  13. 13 Submodule과 Subtree — 외부 레포 통합의 두 가지 철학
  14. 14 거대 레포는 어떻게 git을 견디는가
  15. 15 Git 워크플로우의 선택은 왜 팀 규모와 신뢰 수준에 달려 있는가
  16. 16 Git이 Push를 거부할 때 — 7가지 거부의 구조

Git의 모든 history 명령 — log, merge-base, bisect, rev-list — 은 하나의 자료구조 위에서 동작한다: 방향성 비순환 그래프(DAG). 이 구조는 우연이 아니라 “commit은 한 번 만들어지면 절대 바뀌지 않는다”는 설계 원칙의 직접적 귀결이다. 그 원칙이 어떻게 구조를 결정하고, 구조가 어떻게 협업 전략까지 제약하는가?

Commit 객체 — 불변성의 기반

Git commit은 diff가 아니라 그 시점 전체 tree의 스냅샷이다. raw 포맷은 단순한 텍스트 헤더다.

tree 8d06f00aef...
parent ef56789012...
author IQ <iq@example.com> 1714800000 +0900
committer IQ <iq@example.com> 1714800000 +0900

feat: implement new feature

이 전체 바이트열을 SHA-1로 해시한 값이 commit SHA다. 헤더의 모든 byte — tree SHA, parent SHA, author 이름, Unix 타임스탬프, 타임존 오프셋까지 — 가 SHA 계산에 포함된다. 따라서 같은 변경이라도 1초 차이, 타임존 차이만으로 완전히 다른 SHA가 만들어진다.

author와 committer가 분리된 것도 이 맥락에서 이해된다. git rebase나 cherry-pick은 원본 commit의 author를 그대로 두고 committer만 갱신한 새 commit 객체를 만든다. SHA가 달라지므로 “수정”이 아니라 “새 생성”이다.

✎ commit --amend는 무엇을 하는가

기존 commit을 고치는 게 아니라, 같은 parent를 가리키는 새 commit을 만들고 branch ref를 그것으로 이동시킨다. 원본 commit은 reflog에 남아 있다 GC 대상이 된다. SHA가 반드시 달라지므로 push 후 amend는 force push가 필요하다.

DAG — 자식이 부모를 가리키는 이유

commit이 불변이어야 한다면, 참조 방향은 자식 → 부모 방향일 수밖에 없다.

# 만약 부모가 자식 목록을 들고 있다면:
parent.children = [child1, child2, ...]
# → 새 자식이 생길 때마다 parent 내용이 바뀜 → SHA 바뀜 → 불변 깨짐

# Git의 선택:
child.parents = [parent1, parent2, ...]
# → 새 자식이 생겨도 부모는 그대로 → SHA 불변

이 방향 선택의 직접적 결과가 DAG다. 한 commit이 두 parent를 가질 수 있으면(merge commit) tree 구조를 벗어나고, cycle이 없어야 parent SHA가 commit SHA에 포함될 수 있다.

Merge commit의 parent 2개:

  C4 ─────────────── M   ← main
              /
  C2 ── C3 ──         ← feature

M.parents = [C4, C3]

M의 "first parent"(C4)는 merge된 목적지(main),
second parent(C3)는 merge된 출처(feature).
git log --first-parent는 이 구분을 이용해 main의 진행만 추적한다.

branch는 이 DAG 위의 포인터일 뿐이다. branch가 100개 생겨도 DAG에 노드/엣지가 추가되지 않는다. Git이 branch를 “가볍다”고 말하는 이유가 여기 있다 — 40 byte 파일 하나다.

History 전략 — DAG 모양을 결정하는 선택

DAG 구조를 이해하면 merge 전략 선택이 “미관 취향”이 아님을 알 수 있다.

--no-ff merge는 항상 merge commit을 만든다. DAG에 합류 노드가 생기고, PR 경계가 명확히 보존된다. git revert -m 1 <merge-SHA>로 PR 단위 rollback이 가능하다.

squash merge는 feature의 여러 commit을 하나로 압축해 main에 단일 commit으로 붙인다. main의 first-parent chain이 선형이 되어 git bisect가 효율적이다. 대신 squash commit의 parent는 main tip 하나뿐이라 feature branch를 가리키지 않는다.

rebase merge는 feature commit들을 main 위에 새 SHA로 다시 적용한다. DAG는 선형이 되지만 원본 SHA가 사라진다. 공유 branch에서 rebase하면 다른 사람의 history와 충돌한다.

⚠ 트레이드오프

--no-ff: PR 경계 명확, DAG 복잡, bisect 비효율 가능. Squash: main 깨끗, 내부 commit 의미 잃음(GitHub PR에는 보존). Rebase: 선형 + commit 보존, 원본 SHA 변경 → 공유 branch 위험. 어떤 전략도 완전한 정답은 없다. PR 경계가 중요하면 --no-ff, 깨끗한 main이 우선이면 squash, 선형 + commit 보존이 필요하면 rebase.

Reachability — DAG 위에서 답하는 질문들

Git의 비교 명령은 DAG 탐색으로 환원된다.

git rev-list main..feature   # feature에만 있는 commit
git rev-list feature..main   # main에만 있는 commit
git merge-base main feature  # 두 branch의 최근 공통 조상(LCA)

A..B는 “B의 ancestor 중 A의 ancestor가 아닌 것”이다. A를 시작으로 BFS해 excluded set을 만들고, B를 시작으로 BFS해 excluded가 아닌 것만 반환한다.

git diff main..feature와 git diff main...feature(3-dot)는 다르다. 2-dot은 main tip과 feature tip의 직접 비교, 3-dot은 git diff $(git merge-base main feature) feature — LCA 기준으로 feature가 추가한 것만 본다. PR 리뷰에는 3-dot이 적합하다.

Commit-Graph — DAG 탐색을 100배 빠르게

DAG가 100만 commit 규모로 커지면 traversal이 문제가 된다. 매 commit마다 zlib으로 압축 해제 후 parent SHA를 읽어야 하기 때문이다.

Git 2.18+의 commit-graph 파일(.git/objects/info/commit-graph)은 모든 commit의 parent SHA와 generation number를 단일 binary로 미리 계산해 캐시한다.

generation number는 “이 commit의 ancestor chain 중 가장 긴 것의 길이”다.

C1 (gen=1) → C2 (gen=2) → C3 (gen=3)
                         ↘
                          C4 (gen=3) → C_merge (gen=4)

ancestor 검사에서 generation을 먼저 비교하면 disk read 없이 컷오프할 수 있다.

def is_ancestor(A, B):
    if A.generation > B.generation:
        return False  # 즉시 판정, disk read 0회
    # 이후 실제 traversal

--changed-paths 옵션으로 빌드하면 각 commit이 변경한 경로를 bloom filter로 저장해 git log -- src/file.c 같은 path-based 검색도 수십 배 빨라진다.

git commit-graph write --reachable --changed-paths
git config fetch.writeCommitGraph true  # fetch 시 자동 갱신

Linux 커널 수준의 DAG에서 git log --graph --all이 12초에서 1초대로 줄어드는 건 이 파일 덕분이다.

정리

  • Commit 객체는 스냅샷이다. diff가 아니라 tree SHA를 가리키며, 헤더의 모든 byte가 SHA 계산에 포함된다.
  • 자식이 부모를 가리키는 방향이 불변성을 보장한다. 이 방향 선택이 DAG를 만든다.
  • Merge 전략(--no-ff / squash / rebase)은 DAG 모양을 결정하고, 모양은 bisect 효율, revert 단위, 협업 비용에 직접 영향을 준다.
  • Reachability 탐색(rev-list, merge-base)이 log/fetch/bisect 모두의 기반이다.
  • 대규모 DAG에서는 commit-graph 파일이 traversal을 메모리 내 binary 조회로 바꿔 100배 가까운 속도 향상을 만든다.

다음 글에서는 이 DAG 위에서 git rebase가 정확히 어떤 객체를 새로 만들고, interactive rebase의 각 명령(edit, squash, fixup, drop)이 DAG를 어떻게 재구성하는지 추적한다.

# git # dag # commit-object # reachability # commit-graph