Palantir 소프트웨어 엔지니어가 Git의 병합 및 이름 변경(리네임) 탐지 성능을 높이기 위한 새로운 병합 알고리즘 기여 과정에서의 최적화들을 소개하는 첫 글입니다. 배경과 필요성을 설명하고, ‘완벽한 일치보다 더 나은 일치’를 찾지 않는 간단한 최적화로 큰 속도 향상을 이뤄낸 사례를 다룹니다.
읽는 데 14분
2021년 3월 8일
편집자 주: 이 글은 Palantir 소프트웨어 엔지니어가 git의 병합 및 이름 변경 탐지 메커니즘을 최적화한 내용을 다루는 연재의 첫 번째 글입니다. 두 번째 글을 읽어보세요.
Enter 키를 누르거나 클릭하여 이미지를 전체 크기로 보기
과거에 저는 Git에서의 이름 변경과 깊은 디렉터리 계층에 대해 이야기했습니다. 당시 git의 병합 메커니즘과 이름 변경 탐지 기능에 구현할 성능 개선에 대해 언급했죠. 이번 글과 이후 글들에서, 제가 진행 중인 새 병합 알고리즘을 git에 기여[1]하는 과정에서 수행한 해당 개선들에 대해 이야기하고자 합니다. 이 블로그 연재에서는 제가 git에 적용한 최적화들을 설명할 텐데, 이를 Git Merge 2020 발표에서 유머러스하게 다음과 같이 요약한 바 있습니다:
좀 더 정확하게 요약하자면 다음과 같습니다:
Git Merge 2020 발표 이후 구현을 마쳤고, 위 최적화들을 더 개선하는 한편 두 가지 새로운 최적화도 추가했습니다:
이 연재의 첫 글에서는 Palantir에서 우리가 git을 어떻게 사용하는지와 이러한 최적화가 왜 중요한지를 설명하고, 최적화를 이해하는 데 필요한 배경을 제공한 뒤, 첫 번째이자 매우 단순한 최적화인 ‘완벽한 일치보다 더 나은 일치를 찾지 말 것’을 소개합니다(이는 파일 내용을 직접 비교하기보다 파일 해시를 기반으로 이름 변경을 감지하여 병합을 가속하는 기존 최적화를 한 단계 더 개선한 것입니다).
git merge만을 위한 것인가?git의 병합 메커니즘(merge-recursive라 불림)은 git의 여러 기능을 구동합니다:
따라서 우리는 단순히 git merge만을 이야기하는 것이 아닙니다.
요약하면:
Palantir에는 리눅스 커널 규모에 필적하는 꽤 큰 모노레포가 몇 개 있습니다. 이러한 저장소에서 상위 디렉터리 이름 변경을 포함한 심층 리팩터링을 때때로 수행합니다. 우리는 git이 이런 작업을 효율적으로 처리해 주길 원합니다. 어떤 패치를 구버전 브랜치에 백포트하기 위해 체리픽할 때, 한계 때문에 동작하지 않거나 비정상적으로 오래 걸린다면, 사람들은 중요한 부분을 놓칠 위험을 감수하고 수작업 패치로 돌아가게 됩니다. 실제로 한 팀은 대규모 이름 변경을 수반한 리팩터링 이후 패치 백포팅의 어려움 때문에 몇 달 동안 작업이 지연되는 막대한 시간 손실을 겪었습니다. 결국 “다시는 리팩터링하지 말자”는 합의를 요청하는 회의까지 열었고, 이는 더 나은 병합 기능만 있었더라도 피할 수 있었던 매우 바람직하지 못한 상황이었습니다.
리팩터링 워크플로우를 넘어, 개발자들이 마치 훨씬 작은 저장소를 다루는 것처럼 자신이 관심 있는 영역에만 집중할 수 있기를 바랍니다. 우리는 git sparse-checkout이 등장하기 이전부터 스파스 체크아웃을 가능하게 하는 스크립트를 만들었습니다(스파스 체크아웃 자체는 git에 오래전부터 있던 SKIP_WORKTREE 기능을 기반으로 하지만 쉽게 접근할 수 있는 UI가 없었습니다). 이후 Microsoft가 기여한 git sparse-checkout 패치를 리뷰했고, 우리도 해당 기능에 여러 패치를 기여했습니다.
이 영역의 지속적인 작업에는 스파스 인덱스 생성(역시 Microsoft가 주도)이 포함되며, 이를 통해 작업 트리뿐 아니라 git의 인덱스(스테이징 영역)도 스파스하게 만들 수 있습니다. 인덱스는 git 전반에 걸친 데이터 구조이므로, 이러한 변경은 git 코드베이스 전반에 걸친 대규모 수정이 필요합니다. 기존 병합 메커니즘은 인덱스와 다른 대부분의 코드 영역보다 훨씬 더 복잡하게 얽혀 있으며, 이를 바꾸는 것은 사실상 완전한 재작성에 가깝습니다. 따라서 스파스 인덱스 작업에는 새로운 병합 알고리즘이 필요하며, 우리가 이를 기여하고 있습니다.
스파스 체크아웃과 스파스 인덱스와 연결된 개념으로 부분(Partial) 클론이 있습니다 — 관심 경로의 히스토리만 다운로드하는 기능이죠. 저는 이 기능에 오래전부터 관심이 있었고, 매우 기초적인 구현의 스파스 클론 패치를 처음 올린 사람이라고 생각합니다. 구현을 완성하진 못했지만, 이후 다른 이들이 유사한 기능을 만들었습니다. 부분 클론은 히스토리를 부분적으로 내려받고, 접근할 때 추가 객체를 지연 다운로드합니다. 당연히 부분 클론이 유용하려면, 최적화되지 않은 방식으로 너무 자주 추가 객체를 내려받거나 불필요한 객체를 다운로드하지 않아야 합니다. 안타깝게도 이름 변경 탐지는 과도하게 많은 객체 다운로드를 요구할 수 있습니다. 다만 경우에 따라서는 이름 변경 탐지 없이도 문제를 해결하고 객체 다운로드를 줄일 수 있는 방법이 있음이 알려져 있었습니다. 따라서 병합에서의 이름 변경 탐지를 개선하는 방법을 찾는 것은 부분 클론의 성능을 위해서도 매우 중요합니다.
해당 구현 뒤에 있는 ‘설계’는 “저 다른 코드가 우리가 필요한 것과 거의 같으니, 조금만 손보면 돼”라는 형태였습니다. (그 ‘다른 코드’는 unpack-trees였는데, git 코드에 익숙하지 않으면 무슨 말인지 감이 오지 않을 겁니다.) 그 ‘조금 손보면 돼’가 점점 커져서 결국 손댈 수 없는 수준에 이르렀습니다. 불행히도 merge-recursive는 거의 모두가 피하는, 어둡고 신비로운 코드 영역 중 하나입니다. 가장 활발한 기여자 두 명도 이렇게 말했습니다:
저는 그 코드가 작성된 지 3–4년 후에 합류했지만, 그 코드에 충분한 수의 수정을 제출하면서 어느 순간 해당 영역의 전문가가 되었습니다. 초기 작업의 대부분은 각종 기괴한 에지·코너 케이스에서도 정확성을 확보하는 것이었고, 코드 구조상 고치기 극도로 어려운 에지 케이스들이 있었습니다.
저는 처음에 기존 병합 알고리즘을 오랫동안 그래 왔던 것처럼 리팩터링하는 것부터 시작했습니다. 그러다 설계의 큰 부분을 바꾸자고 제안하기에 이르렀고, 이때 git의 유지관리자인 Junio Hamano가 아예 새로 작성하자고 제안했습니다. 그는 지적했습니다 git에는 병합 백엔드를 플러그인처럼 교체할 수 있는 구조가 있어, 기존 것과 공존 가능한 새 알고리즘을 작성할 수 있다고요. 이는 사용자 안정성 관점에서도 바람직합니다. 어떤 이들은 새 알고리즘을 써 보고 다른 이들은 기존 것을 쓰게 하면서(심지어 간단한 설정 스위치로 왔다갔다 하면서) 동시에 운영할 수 있기 때문입니다.
Medium에 무료로 가입하고 이 작성자의 업데이트를 받아보세요.
이로 인해 저는 핵심 데이터 구조와 가정을 성능 향상과 골칫거리였던 코너 케이스 해결 관점에서 다시 생각해 볼 자유를 얻게 되었습니다.
제가 한 최적화를 이해하려면 git에 대해 몇 가지를 알아야 합니다:
위 내용을 이미 알고 이해한다면, 이 배경 섹션은 건너뛰어도 좋습니다. 낯설거나 놀라운 부분이 있다면 아래의 해당 섹션을 읽어보세요.
다음과 같은 히스토리가 있고 현재 브랜치가 “main”이라고 가정해 봅시다:
A---B---C topic
\
D---E---F---G main
“main” 브랜치의 어떤 파일에 아래와 같은 코드 구간이 있다고 가정해 보겠습니다
line 1
line 2
line 3
그런데 “topic” 브랜치의 같은 파일에는 두 번째 줄이 없습니다. 병합 메커니즘은 여기서 무엇을 해야 할까요? “main”이 그 중간 줄을 추가했을까요, 아니면 “topic”이 그것을 삭제했을까요? 이를 알 수 있는 유일한 방법은 공통 히스토리 지점을 참조하는 것입니다. 가장 최근 공통 커밋(위 그림에서 ‘E’로 표시된 커밋)을 git에서는 “병합 베이스(merge base)”[2]라고 부릅니다. 병합 베이스에 그 줄이 있었다면 분명히 “topic”이 삭제한 것이고, 병합 결과에서도 삭제되어야 합니다. 병합 베이스에 그 줄이 없었다면 분명히 “main”이 추가한 것이고, 병합 결과에도 추가되어야 합니다. 병합 베이스가 이 영역에서 어느 쪽과도 일치하지 않는다면, 병합 충돌이 발생합니다.
따라서 병합은 양자 간 연산이 아니라, 병합 베이스(커밋 E), 현재 커밋(“main”이 가리키는 커밋 G), 다른 브랜치의 끝(“topic”이 가리키는 커밋 C)을 함께 참조하는 3방향 연산입니다[3]. (참고로, git config --global merge.conflictStyle diff3를 설정하면 병합 충돌을 해결할 때 원본 버전에 대한 정보가 함께 제공되어 이 점을 활용할 수 있습니다.)
병합 알고리즘의 기본 아이디어는 따라서, 저장소의 각 파일에 대해 이 세 커밋에서의 버전을 사용하여 3방향 콘텐츠 병합을 수행하는 것입니다[4].
많은 사용자가 git이 커밋마다 해시를 갖는다는 사실에는 익숙합니다. 그러나 git은 커밋에 포함된 각 파일(“blob”)과 하위 디렉터리(“tree”)에도 해시를 갖고 있으며, 트리 해시는 그 안의 blob과 하위 트리 해시에서 파생되고, 커밋 해시는 최상위 트리와 커밋의 작성자/날짜/메시지/기타 정보를 바탕으로 파생됩니다. 이는 머클 트리(Merkle Tree)로 알려진 데이터 구조입니다. 아래 명령으로 이러한 해시를 직접 확인할 수 있습니다:
git ls-tree -rt $COMMIT
또는 다음을 반복 실행해 볼 수도 있습니다:
git cat-file -p $HASH
커밋의 해시에서 시작하여, 이전 명령의 출력에 나타나는 해시들에 대해 반복합니다. git은 내부적으로 모든 것을 해시로 저장하고 조회합니다. 트리 객체는 git 내부 저장소의 해시와 작업 디렉터리에 써야 할 파일 이름 간의 매핑을 기록합니다. (해시 기반 저장은 일종의 자동 중복 제거 역할도 합니다.)
앞서 언급했듯, git은 파일 단위로 리비전을 저장하지 않습니다. 또한 각 커밋에서 수행된 파일 이름 변경을 추적하는 메타데이터도 없습니다. 대신 관련 명령이 실행될 때마다 즉석에서 이름 변경을 감지합니다.
병합이 이름 변경 탐지를 필요로 하는 이유는 두 가지입니다
merge-base:src/oldname.java, side1:src/oldname.java, side2:src/subdir/newname.java) — 그래야 그들의 콘텐츠를 병합할 수 있습니다병합에는 병합 베이스와 양쪽이 있으므로, 이름 변경 탐지는 두 번 수행해야 합니다 — 병합 베이스에서 side1으로, 그리고 병합 베이스에서 side2로.
불행히도 이름 변경 탐지는 이차 시간(quadratic) 알고리즘입니다. 먼저 병합 베이스에만 고유한 파일 N개를 구하고, 주어진 한쪽에만 고유한 파일 M개를 구한 뒤, N×M 모든 파일 쌍의 콘텐츠 유사도를 비교하여 충분히 유사한 최적 짝을 이름 변경으로 표시합니다. 이름 변경이 소수만 있어도 이름 변경 탐지는 병합에서 가장 느린 부분이 되기 충분합니다.
병합 베이스, side1, side2 간의 3방향 병합 개념은 두 가지 다른 방식으로도 볼 수 있습니다. 병합 베이스와 side1 간의 차이를 side2에 적용한다고 볼 수도 있고, 병합 베이스와 side2 간의 차이를 side1에 적용한다고 볼 수도 있습니다.
이러한 관점은 리베이스나 체리픽이 어떻게 동작하는지를 이해하는 데 도움이 됩니다. 높은 수준에서 보면, 리베이스나 체리픽은 어떤 커밋을 새 기반 커밋 위에 적용하는 것입니다. 다시 말해, 선택한 커밋과 그 부모 간의 변경 사항을 추출해 새 기반 커밋에 적용하는 것입니다. 그런데, 앞서 말했듯 이는 ‘부모 커밋, 선택할 커밋, 새 기반 커밋’ 사이의 3방향 병합을 수행하는 것과 동일합니다. 따라서 리베이스나 체리픽은 다소 특이한 병합 베이스[5]를 사용하는 3방향 병합으로 구현됩니다… 다만 최종적으로 결과 커밋은 부모를 하나(새 기반 커밋)만 기록할 뿐입니다.
여러 커밋을 리베이스하거나 체리픽할 때는 일련의 병합을 수행하며, N번째 3방향 병합의 새 기반 커밋은 직전 커밋을 리베이스/체리픽한 결과가 됩니다.
앞서 언급했듯, 이름 변경 탐지는 먼저 병합 베이스에만 고유한 파일 N개, 주어진 한쪽에만 고유한 파일 M개를 구한 다음, N×M 모든 파일 쌍의 콘텐츠 유사도를 비교해 충분히 유사한 최적 짝을 이름 변경으로 표시합니다. N과 M을 줄일 수 있을까요? 사전(프리패스) 단계에서 감지할 수 있는 특수한 경우가 있을까요?
파일이 이름만 바뀌고 내용은 수정되지 않은 경우는 어떨까요? 그런 파일은 해시가 정확히 동일합니다. git은 저장소의 각 파일 해시를 저장하므로 이를 계산하기 위해 추가 작업이 전혀 필요 없습니다. 두 집합(N과 M)에서 동일한 해시를 공유하는 파일이 있는지만 확인하면 됩니다. 예를 들어, 이전 파일과 그 (축약된) 해시가 다음과 같다면:
c01055a1 hex.java
5eac0a57 word.java
acc057ed fun.java
새 파일과 그 (축약된) 해시가 다음과 같다면:
c01055a1 hexadecimal.java
0b57ac1e phrase.java
acc057ed games.java
decea5ed copy.java
두 파일이 같은 해시를 가지므로, hex.java와 hexadecimal.java는 둘 중 어느 것도 열어 볼 필요 없이 이름 변경으로 감지할 수 있습니다. fun.java와 games.java도 마찬가지입니다. 이는 전수 쌍 비교에서 hex.java와 hexadecimal.java를 제외할 수 있고, fun.java와 games.java도 제외할 수 있음을 의미합니다. 따라서 최종적으로 유사도 비교가 필요한 파일 쌍은 (word.java, phrase.java), (word.java, copy.java)뿐입니다. 12개 쌍에서 2개 쌍으로 줄어든 셈입니다.
이 단순한 아이디어는 수년 전에 구현되었지만… 단서가 하나 있었습니다. 이름 변경 탐지를 수행하는 동일한 코드가 복사(copy) 탐지도 수행했습니다. 복사 탐지에서는 하나의 소스 파일이 여러 대상 파일과 짝지어질 수 있습니다. 따라서 공통 해시를 찾았을 때 대상은 제거할 수 있어(M을 1 줄임)도, 소스의 수는 그대로 둬야 합니다. 위 예에서 copy.java가 둘 중 어느 파일의 복사본일 수도 있기 때문입니다. 즉, hexadecimal.java와 games.java는 제거할 수 있어도 hex.java나 fun.java는 제거할 수 없습니다. 결과적으로 전수 비교는 총 3×2, 즉 6쌍이 됩니다. 6쌍은 원래의 12쌍보다는 적지만, 2쌍에 비하면 여전히 많습니다.
물론 복사 탐지가 필요할 때만 6쌍의 비교를 해야 합니다. 이름 변경 탐지만 필요하다면(병합 알고리즘의 경우가 그렇습니다) 2쌍만 비교하면 됩니다. 그러나 이름 변경과 복사 탐지를 구현한 코드는 항상 더 많은 수의 비교를 하도록 작성되어 있었고, 이는 이름 변경 탐지의 경우 ‘이미 소스 파일에 대해 찾아낸 완벽한 일치보다 더 나은 일치’를 찾느라 시간을 소비한다는 뜻이었습니다.
물론 이 최적화는 병합 베이스와 이름을 바꾼 브랜치 끝 사이에서 ‘내용 수정 없이 파일이 이동/이름 변경’된 경우에만 적용됩니다. 따라서 효과는 저장소와 살펴보는 커밋들에 크게 의존합니다. 그럼에도 ‘완벽한 일치보다 더 나은 일치’를 찾지 않도록 하자, 라는 변경만으로도, 약 2만6천 개 파일을 이름 변경한 브랜치 위로 35개 패치를 리베이스하는 특정 테스트 케이스에서 약 3배의 속도 향상을 보여줬습니다:
Before After
mega-renames: 5504.231 s ± 5.150 s 1799.937 s ± 0.493 s
현실 세계에서 이름 변경이 많은 첫 번째 테스트 케이스(한 커밋을 단순 체리픽)에서도 2배의 속도 향상을 보였습니다. 이는 가장 단순한 최적화였지만 여전히 매우 인상적인 가속을 제공했습니다. 이 최적화에 대한 자세한 내용은 업스트림 스레드를 참고하세요.
이 최적화는 3월 중순에 릴리스될 git-2.31에 포함됩니다.
[1] git-2.31에는 새로운 “ort” 병합 전략의 기본 미리보기 버전이 포함됩니다(“ort”는 “ostensibly recursive’s twin”의 약자로, 기존 기본 “recursive” 전략을 최종적으로 대체할 드롭인 교체가 될 것임을 암시합니다. 또한 병합 전략 선택이 -s 플래그로 이루어지기 때문에 git merge -s ort를 볼 때 웃음이 나옵니다. 명령 인자 파서가 git merge -sort도 받아들인다는 점도 재밌죠). git-2.31의 ort 버전에는 ort 관련 코드의 대부분이 포함되지만, 제출 준비가 된 나머지 패치들이 리뷰 과정을 통과하는 데에는 최소 3개월이 더 걸릴 것입니다.
[2] 이 글에서는 병합 베이스가 없거나 둘 이상인 경우는 무시하겠습니다.
[3] 참고로 git 커밋은 스냅샷을 저장하지, diff를 저장하지 않습니다. git log -p 같은 명령이 특정 커밋과 그 부모 간의 차이만 보여주어 마치 커밋이 diff인 것처럼 보이게 만들고, git pull 같은 명령이 새 커밋에만 고유한 객체들만 영리하게 가져오며 기존 커밋에서 도달 가능한 객체는 가져오지 않기 때문에, 종종 사용자들이 오해하곤 합니다.
[4] 여기서는 명백히 많은 세부 사항을 생략하고 있습니다. 예를 들어 gitattributes에 관련된 모든 것(바이너리 파일, 줄 끝 처리 정규화, 특수 병합 드라이버), 콘텐츠 외 충돌(예: 수정/삭제 충돌, 이름 변경/삭제 충돌, 디렉터리/파일/서브모듈/심볼릭 링크 유형 충돌, 추가/추가 충돌, 이름 변경/이름 변경 충돌, 디렉터리 이름 변경 탐지로 인한 파일 위치 충돌, 중첩된 충돌 마커를 유발하는 난해한 경우 등), 유일하지 않은 병합 베이스, 기타 등등.
[5] 기술적으로 리베이스 백엔드는 여러 가지가 있고, 기본 리베이스 백엔드(“merge”)만이 위와 같이 동작합니다. 이전 기본 리베이스 백엔드(“apply”)는 선택할 커밋과 그 부모 간의 패치를 계산한 다음, 그 패치를 새 기반 커밋에 적용하려 시도하는 방식이었습니다. 하지만 두 방법은 대부분의 경우 논리적으로 동일합니다. 차이는 merge 백엔드가 더 많은 정보를 활용할 수 있어 apply에 내재한 일부 한계를 피할 수 있다는 점입니다. 또한 apply가 git-2.26까지 기본이었기 때문에, 그 주변에 더 많은 기능이 성장했고 아직 새로운 백엔드로 옮겨오지 않은 것들이 있습니다.