Git 시니어 코딩 면접
새 면접Q. Git의 3-way merge 알고리즘을 구현한다고 가정할 때, base(공통 조상), ours(현재 브랜치), theirs(병합할 브랜치) 세 버전의 파일에서 충돌을 자동으로 해결하는 로직을 설계해주세요. 특히 라인 단위 병합에서 충돌 판단 기준과 자동 해결 가능한 케이스를 구체적으로 설명해주세요.
3-way merge는 각 라인별로 base와 비교하여 변경사항을 추적합니다. (1) base와 ours가 같고 theirs가 다르면 theirs 채택, (2) base와 theirs가 같고 ours가 다르면 ours 채택, (3) 세 버전 모두 같으면 그대로 유지, (4) base와 다르면서 ours와 theirs가 서로 다른 경우 충돌로 표시합니다. 이 알고리즘은 diff3 방식으로 구현되며, 각 변경의 의도를 파악하여 자동 병합 가능성을 최대화합니다. 구현 시 라인 해시맵을 사용하여 O(n) 시간복잡도로 처리할 수 있습니다.
- • base를 기준으로 양쪽 변경사항을 독립적으로 판단
- • 한쪽만 변경된 경우 자동 해결 가능
- • 양쪽 모두 변경되고 내용이 다르면 충돌
- • 라인 해시맵을 활용한 효율적 비교
recursive merge 전략과 ort(Ostensibly Recursive's Twin) 전략의 차이점과 각각의 성능 특성을 설명해주세요.
Q. 대규모 feature 브랜치(200+ 커밋)를 주기적으로 main 브랜치에 rebase해야 하는 상황에서, 매번 rebase 시 발생하는 반복적인 충돌 해결을 최소화하는 전략을 코드 레벨에서 설계해주세요. rerere(reuse recorded resolution) 메커니즘의 동작 원리와 구현 방식을 포함해서 설명해주세요.
rerere는 충돌 발생 시 충돌 전후 상태를 해시값으로 저장하여 동일한 충돌 패턴을 자동 해결합니다. 충돌 마커 사이의 내용을 정규화하여 해시를 생성하고, .git/rr-cache 디렉토리에 preimage(충돌 상태)와 postimage(해결 상태)를 저장합니다. rebase 중 동일한 해시의 충돌이 발생하면 저장된 해결 방법을 자동 적용합니다. 구현 시 충돌 컨텍스트의 정규화가 핵심이며, 라인 번호나 공백 차이를 무시하여 매칭률을 높입니다. 추가로 rebase 전 merge-base를 캐싱하고 점진적 rebase 전략을 사용하면 충돌 범위를 최소화할 수 있습니다.
- • rerere는 충돌 패턴을 해시로 저장하여 재사용
- • preimage와 postimage 쌍으로 해결 방법 기록
- • 충돌 컨텍스트 정규화로 매칭률 향상
- • 점진적 rebase로 충돌 범위 최소화
interactive rebase에서 autosquash 기능을 구현한다면 커밋 메시지 파싱과 재정렬 로직을 어떻게 설계하시겠습니까?
Q. Git의 가비지 컬렉션(gc) 프로세스를 최적화하는 알고리즘을 설계해야 합니다. unreachable 객체를 식별하고, pack file을 재구성하며, loose object를 정리하는 전체 프로세스를 효율적으로 구현하는 방법을 설명해주세요. 특히 대용량 저장소에서 gc 수행 시간을 최소화하는 전략을 포함해주세요.
gc는 크게 세 단계로 구현됩니다. (1) reachability 분석: refs에서 시작하여 BFS/DFS로 모든 도달 가능한 객체를 마킹하고, 마킹되지 않은 객체를 unreachable로 식별합니다. (2) pack file 최적화: 자주 함께 접근되는 객체들을 클러스터링하여 하나의 pack으로 묶고, delta compression을 적용합니다. (3) loose object 정리: 생성 시간이 일정 기간 지난 unreachable loose object를 삭제합니다. 최적화를 위해 incremental gc를 사용하여 변경된 부분만 처리하고, bitmap index를 활용하여 reachability 체크를 O(1)로 수행하며, multi-pack-index로 pack 탐색을 가속화합니다.
- • BFS로 reachable 객체 마킹 후 unreachable 식별
- • 객체 클러스터링과 delta compression으로 pack 최적화
- • bitmap index로 reachability 체크 고속화
- • incremental gc로 변경분만 처리
Git의 prune 작업이 reflog와 상호작용하는 방식과, aggressive gc 옵션이 일반 gc와 다른 점을 설명해주세요.
Q. 복잡한 merge 충돌을 프로그래밍 방식으로 분석하고 해결하는 도구를 만든다고 가정합니다. AST(Abstract Syntax Tree) 레벨에서 코드 충돌을 분석하여 semantic merge를 수행하는 접근법을 설계해주세요. 텍스트 기반 merge와의 차이점과 구현 시 고려사항을 포함해주세요.
semantic merge는 소스코드를 파싱하여 AST로 변환한 후 구조적 차이를 분석합니다. 함수, 클래스, 변수 선언 등을 노드로 식별하고, 동일한 의미 단위의 변경을 추적합니다. 예를 들어 한쪽에서 함수를 파일 상단으로 이동하고 다른 쪽에서 함수 내부를 수정한 경우, 텍스트 merge는 충돌로 보지만 semantic merge는 두 변경을 독립적으로 적용할 수 있습니다. 구현 시 언어별 파서 통합, AST diff 알고리즘(tree edit distance), 그리고 AST를 다시 소스코드로 변환하는 pretty printer가 필요합니다. 단, 주석이나 포맷팅 정보 손실을 방지하기 위해 원본 텍스트 정보를 보존하는 CST(Concrete Syntax Tree) 사용을 고려해야 합니다.
- • AST 레벨에서 구조적 변경 분석
- • 의미 단위 변경을 독립적으로 처리
- • tree edit distance로 AST diff 계산
- • CST로 포맷팅 정보 보존
여러 언어를 지원하는 semantic merge 시스템의 아키텍처를 설계한다면 플러그인 구조를 어떻게 구성하시겠습니까?
Q. 멀티 리전에 분산된 Git 저장소 간의 효율적인 동기화 시스템을 구현해야 합니다. 네트워크 지연이 큰 환경에서 fetch와 push 작업을 최적화하고, 동시 push 시 발생하는 경쟁 조건을 해결하는 프로토콜을 설계해주세요. Git의 smart HTTP protocol과 pack protocol의 동작 원리를 기반으로 설명해주세요.
분산 동기화는 크게 세 단계로 최적화합니다. (1) capability negotiation: 클라이언트와 서버가 지원하는 기능을 교환하여 최적 프로토콜을 선택합니다. (2) want/have negotiation: 클라이언트가 원하는 객체(want)와 이미 가진 객체(have)를 서버에 알려 필요한 객체만 전송받습니다. bitmap을 사용하면 이 과정이 대폭 단순화됩니다. (3) thin pack transfer: delta 체인을 활용하여 전송량을 최소화합니다. 동시 push 경쟁 조건은 atomic push와 compare-and-swap 방식의 ref update로 해결하며, 서버는 expected old value를 검증한 후에만 ref를 업데이트합니다. 멀티 리전 환경에서는 CDN 스타일의 pack cache를 두고, commit graph를 미리 계산하여 negotiation 단계를 줄입니다.
- • want/have negotiation으로 필요한 객체만 전송
- • thin pack과 delta compression으로 전송량 최소화
- • atomic push와 compare-and-swap으로 경쟁 조건 방지
- • pack cache와 commit graph로 분산 환경 최적화
Git protocol v2가 v1 대비 개선한 점과, partial clone에서 on-demand object fetching을 구현하는 방법을 설명해주세요.
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!