현재 Git이 Merge 할 때 사용하는 전략이 ort로 바뀌었다. Git에 ort 머지 전략이 들어온 것은 Git 2.33부터였고 Git 2.34에서 별도의 설정 없이도 Merge할 때 사용되는 기본 전략으로 바뀌었다.

이 Merge 전략은 git merge와 git pull을 할 때 주로 사용되지만 rebase, cherry-pick, revert, stash, checkout에서도 사용된다. 2.34가 2021년 11월에 나왔으니 바뀐 지는 꽤 되었지만 뭐가 바뀌는지는 정확히 모르고 있어서 정리를 해봤다. 이 글 쓰는 시점의 Git 최신 버전은 2.43.0

resolve 전략

Git이 2개의 브랜치를 머지할 때 변경 사항을 합치기 위해 여러 가지 전략 중 하나를 선택한다. 원래의 전략은 3-way merge 알고리즘을 사용하는 resolve 전략을 사용했다.

3-way merge는 A 파일과 B 파일의 차이점을 분석한 후 두 파일의 공통 조상인 C 까지 고려해서 합칠 변경 사항을 구성하고 A, B, C 셋 다 다른 경우는 충돌(Conflict)로 표시해서 사용자가 해결하도록 한다.

recursive 전략

Git이 만들어진 초기인 2005년에 resolve 전략은 recursive라는 전략으로 교체된다. 이렇게 recursive로 바꾼 주요 이유는 머지할 두 브랜치가 공통된 조상이 없는 경우에도 각 브랜치에서 그 이름대로 재귀적으로 머지할 수 있어서 resolve 전략에서 충돌하는 경우에도 머지할 수 있고 한 브랜치에서는 파일이 수정되고 다른 브랜치에서는 파일명이 변경된 경우에도 이를 감지할 수 있기 때문이다.

이렇게 적용된 recursive는 오랫동안 Git의 기존 전략으로 사용되었다. 2005년에 적용되고 2021년에 나온 Git 2.33에서 바뀌었으니 16년 동안 사용된 셈이다.

ort 전략

ort는 재귀(recursion)와 파일이름 변경 탐지를 하는 recursive와 같은 컨셉을 가지고 처음부터 새로 작성된 전략이다. 그래서 ort라는 이름도 Ostensibly Recursive’s Twin의 약자로 표면적으로는 Recursive의 쌍둥이라는 의미이고 이전에 비해 훨씬 빨라졌다.

Git 공식 문서를 보면 ort 전략을 다음과 같이 설명하고 있다.

하나의 브랜치를 가져오거나(pull) 머지할 때 사용하는 기본 머지 전략이다. 이 전략은 3-way 머지 알고리즘을 사용해서 두 개의 헤드(head)만 처리할 수 있다. 3-way 머지에 사용할 수 있는 공통 조상이 2개 이상 있다면 공통 조상의 머지된 트리를 만들어서 이를 3-way 머지의 참조 트리로 사용한다. Linux 2.6 커널 개발 기록에서 가져온 실제 머지 커밋을 대상으로 테스트한 결과 ort가 잘못된 머지도 없고 머지 충돌이 더 적게 발생했다. 또한, 이 전략은 이름 변경과 관련된 머지를 탐지하고 처리할 수 있으며 감지된 사본(detected copies)을 사용하지 않는다.

그러면 오랫동안 사용하던 recursive 전략을 왜 바꿀 필요가 있는지를 알아야 하는데 새로운 전략이긴 하지만 방법 자체를 바꾸었다기보다는 많은 최적화 작업을 합쳐서 ort라는 새로운 전략이 탄생했다고 볼 수 있고 그렇기에 이름도 recursive의 쌍둥이라는 이름을 가지게 된 것이다.

Git에서 recursive 머지의 코드 베이스는 문제를 해결하기 위해 조금만 고치다 보니 결국 고칠 수 없는 상황까지 왔습니다. 그래서 버그도 많이 발생하고 해결하기 어려운 엣지 케이스도 발생하고 있었고 개발자들도 이 부분의 코드 수정은 피하고 있었다. Git의 핵심 개발자 중 한 명인 Elijah Newren가 큰 변경을 하려고 하자 초기부터 Git을 리드하고 있는 Junio Hamano 그냥 다시 작성하자는 제안하고 이에 따라 아주 대규모의 최적화 작업이 시작된다.

이 최적화 과정을 이해하려면 Git의 3-way 머지를 좀 이해해야 한다.

     A---B---C topic
    /
D---E---F---G main

즉, 위처럼 2개의 브랜치를 머지한다고 했을 때 각 브랜치의 최신 커밋인 C와 G, 두 브랜치의 공통 조상이 되는 커밋인 E까지 고려해서 머지하는 것이다. 특정 라인이 C 커밋에는 없고 G 커밋에는 있다고 했을 때 이 둘만 가지고는 이 라인이 추가된것인지 제거된 것인지 알 수 없다. 공통 조상이 E 커밋을 봤을 때 해당 라인이 있다면 C 커밋에서 제거한 것이고 E 커밋에 해당 라인이 없다면 G 커밋에서 추가된 것이다.(참고로 git에서 diff3 설정을 하면 충돌이 발생했을 때 공통 조상의 내용도 같이 보여서 수정할 때 편하다.)

여기서 파일 이름 변경까지 되면 훨씬 복잡해진다. 각 브랜치에서 파일 내용을 수정할 수 있지만 파일명을 바꾸거나 파일명은 그대로이지만 디렉터리 위치가 바뀔 수 있다. Git은 파일명을 따로 추적하고 있지 않기 때문에 머지할 때 이 이름 변경을 감지해서 이름이 변경된 파일을 찾아내야 하는 것이다. 위에서 말한 대로 머지를 할 때 3개의 커밋이 필요한데 각 커밋에서 고유의 파일명 목록을 만들고 서로 일일이 비교하면서 내용의 유사성을 비교해서 파일 변경인지를 표시하게 되므로 상당히 느린 부분이다.

코딩에서 추상화는 중요한 개념이지만 때로는 경계를 만들어서 경계에 걸쳐서 어떤 작업을 하려고 할 때 어렵게 만들기도 한다. Git도 이러한 추상화로 인해서 최적화가 어려웠던 경우인데 Git에도 파일 이름 변경을 탐지하는 컴포넌트가 분리되어 있었다. 이 컴포넌트는 3개의 커밋에 대한 정보가 아니라 2개 커밋에 대한 정보만 받고 있었는데 파일 이름 변경을 추적하려면 3개 커밋의 정보가 모두 필요했기 때문에 이 추상화 경계를 넘어서 추가 정보를 제공해야 했다.

또한, rebase나 cherry-pick을 할 때도 각 커밋 단계마다 이름 변경 탐지를 하게 되는데 이게 반복적으로 진행되므로 인메모리에 캐싱해서 개선하게 된다. 당연히 왜 이전에는 안 했는지 궁금할 수 있지만 캐싱해도 동작의 차이가 없는지를 확인하는 것이 아주 복잡했기 때문에 못 했던 것인데 이번에는 몇 가지 제약사항을 가진 채 이 캐싱 최적화를 추가했다.

Git에서 Index라는 것은 보통 우리가 Stage 영역이라고 부르는 것으로 다음 커밋에 포함될 파일에 대한 정보를 가지고 있는 데이터 구조인데 recursive 전략에서는 이 Index 데이터 구조가 핵심이었다(working tree 포함). ort 전략에서는 이 Index를 사용하지 않고 recursive에서 성능에 영향을 많이 주던 unpack_trees()라는 저수준 함수의 사용을 안 하도록 바뀌었다. 그래서 이 두 가지에 의존함으로써 생긴 제약을 대부분 해결할 수 있게 되었다.

다시 정리하면 ort는 index와 working tree를 건드리지 않고 머지 결과를 트리로 만들어서 이 머지 결과가 나왔을 때만 ort가 체크아웃 로직을 이용해서 머지 결과로 이동하게 된다. index에 항목을 추가 제거하는 동작과 머지하면서 수행되는 값비싼 트리 탐색을 피할 수 있게 되어 속도가 훨씬 빨라지게 된다.

최대한 간단히 정리했지만, 이 내용은 이 수많은 최적화 작업을 주도한 Elijah Newren이 작성한 6편의 글 Optimizing Git’s Merge Machinery, #1, #2, #3, #4, #5, #6에 잘 나와 있다. 아주 긴 글이지만 한번 읽어볼 만한 좋은 글이다.

Git 2.33 공지에 따르면 ort가 이전보다 훨씬 빨라져서 파일명 변경이 많고 복잡한 머지의 경우 500배가 빨라졌고 rebase 과정에서 비슷한 머지를 반복해서 하게 되면 ort가 일부 계산을 캐싱하기 때문에 9,000배 이상 빨라진다고 한다. 이건 특수한 경우고 일반적으로도 ort가 recursive보다 약간 빠른 것으로 나타났지만 recursive는 상황에 따라 속도 편차가 크지만 ort는 일관된 속도를 보여주었다.

일반적인 상황에서 보통 머지 속도가 문제 되진 않지만 아마 머지와 리베이스를 가장 많이 실행하는 GitHub이 ort를 적용한 결과를 보면 머지 속도가 p50에서는 10배 p99에서는 5배 빨라졌고 리베이스에서도 이전에 512시간 걸리던 리베이스가 ort에서는 33시간으로 줄어들었다는 것을 보면 속도가 얼마나 개선되었는지 알 수 있다.

추가로 Git으로 머지할 때 다음과 같이 어떤 전략이 사용되었는지 나온다.

Auto-merging a.txt
Merge made by the 'ort' strategy.

git merge --strategy recursive BRANCH-NAME처럼 머지할 때 -s나 --strategy 옵션으로 머지 전략을 지정하면 다른 머지 전략을 사용할 수 있다. 여기서처럼 ort 대신 recursive를 지정하면 메시지에서도 Merge made by the 'recursive' strategy.라고 나와서 머지 전략이 바뀌었음을 확인할 수 있다.