버전 관리 시스템의 마이그레이션 전략과 방법

최근에 버전 관리 시스템 마이그레이션 작업을 진행하고 있고 작년에는 저장소 재구성 작업을 했었다. 작업을 진행하면서 고민했던 마이그레이션 전략과 방법을 정리했다.

마이그레이션

저장소 마이그레이션은 예전 저장소에서 새 저장소로 데이터를 옮기는 과정이다. 이 과정은 아래의 그림과 같이 예전 저장소에 있는 파일과 로그를 익스포트하는 과정과 여기서 얻은 데이터를 새 저장소로 임포트하는 과정으로 이루어진다.

특히 마이그래이션 작업은 두 저장소가 다른 버전 관리 시스템에 있을 때 까다로워진다. 만약 두 시스템의 리비전 모델이 많이 다른 경우라면 더욱 그렇다. 예를 들어 subversion 의 경우 디렉토리도 파일과 같이 리비전 대상이 되지만 mercurial 의 경우에는 그렇지 않다. 때문에 subversion 의 mkdir 작업은 mercurial 에서는 빠져야 하고 반대로 mercurial 에서 subversion 으로 올 때는 적당한 시점에 mkdir 작업을 임의로 넣어줘야 한다. (다행히 subversion -> mercurial 은 hgsubversion 툴이 있어 간편하게 마이그레이션 할 수 있다)

최대한 예전 저장소의 구조와 데이터를 유지하면서 마이그레이션을 할 수 있다면 좋겠지만 그 만큼 개발 비용이 소모되니 절충안을 잘 선택해야 한다. 이제 여러 전략을 살펴보고 장단점을 따져 최적의 방법을 골라보자.

예제 데이터, 전략의 이점

설명을 위해 아래와 같은 예제 저장소 데이터를 가정하자. 

가로축이 리비전 증가다. 리비전 1 부터 4 까지 총 4개의 리비전 변화가 있었다. 저장소의 파일은 노드로 표시되고 "파일이름 <내용>" 형식으로 표현되어 있다. 위 그림에서 리비전 2 에는 apple 과 banana 파일 있는 것을 알 수 있다. 또 가장 최근 리비전 4 에는 banana 와 orange 파일이 있는 것을 알 수 있다.

리비전이 증가함에 따라 파일이 변하는데 파일의 변화는 노드 사이를 잇는 선으로 표시한다. 변화를 발생시키는 파일 변경 내용은 A(dd, 추가), M(odify, 변경), C(opy, 복사), D(elete, 삭제) 이렇게 네 가지가 있다. 위 그림에서 리비전 2-> 3 과정을 보면 apple 파일은 삭제되고, banana 파일은 내용이 brown 으로 수정되고 orange 는 banana 로부터 복사되었음을 알 수 있다.

각 마이그레이션 전략이 제공하는 이점이 있다. 먼저 어떤 이점이 있는지 살펴보고 각 전략이 그 중 어떤 이점을 제공하는지 다루기로 하자.

• 현재 스냅샷 유지
  가장 마지막 리비전의 파일의 구성은 최소한 유지되어야 올바른 마이그레이션이다. 과거 데이터가 어떻든 새 저장소에서 현재 파일을 받았을때 예전 저장소와 동일한 파일이 받아져야 한다. 따라서 유지되어야할 필수 조건이다. (예제 데이터의 새 저장소에서 최신 리비전을 받으면 banana, orange 가 나와야 한다.)
• 과거 시점의 스냅샷의 완결성 유지
  과거 시점의 파일을 받았을 때 그 시점의 파일 구성이 올바르게 받아지는지 여부다. 예를 들서 1년전 저장소 상태의 파일을 받겠다 라고 했을 때 그 때의 구성으로 올바르게 받아지는지 여부다. (예제 데이터의 리비전 2 데이터를 요청했을 때 정확히 apple 과 banana 가 받아져야 한다.)
• 현재 파일의 변경 내역 유지
  현재 스냅샷에 포함되어 있는 파일들의 변경 이력이 제대로 나오는지 여부다. 현재 파일의 과거 버전을 받을 수도 있고 수정 내역을 통해 blame 을 할 수도 있다. (예제 데이터의 banana 이력을 요청하면 yellow -> brown -> black 으로 변해 왔는지를 알 수 있어야 한다.)

그럼 어떤 전략이 있는지 살펴보자.

전략: 현재 스냅샷

현재 스냅샷 (마지막 리비전에 포함되어 있는 모든 파일) 을 새 저장소에 그대로 추가 하는 방식이다. 과거 이력은 모두 무시하고 현재 파일만 이동하는 전략이다. 새 저장소에 옮겨진 리비전의 모습은 아래 그림과 같으며 과거 리비전에 대한 정보가 모두 사라졌음을 볼 수 있다.

이 방법은 간단하다. 단순히 예전 저장소의 최신파일을 받아 새 저장소에 추가하는 것으로 충분하다. 때문에 마이그레이션 비용이 가장 적고 그래서 많이 사용되는 방법이기도 하다. 만약 과거 리비전 로그를 살리는 것이 중요하지 않다면 좋은 방법이다.

이점: 현재 스냅샷 유지

전략: 주요 스냅샷

중요 포인트가 되는 리비전들을 정하고 그 리비전들의 파일과 그 리비전 사이마다 차이를 남기는 방식이다. 예를 들어 알파 테스트, 베타 테스트, 공개 오픈 이렇게 세 시점이 중요 포인트고 그 시점의 스냅샷과 그 사이의 변화를 남기고 싶다면 이 방법을 사용할 수 있다. 아래 그림은 중요 포인트로 리비전 2와 4를 선택했을 경우의 새 저장소의 리비전 모습이다. 리비전 2, 4 시점의 파일은 정확히 남고 그 사이의 이력은 뭉게지는 것을 볼 수 있다. (banana 의 파일 내용이 yellow 에서 바로 black 이 되는 것이 한 예이다.)

방법도 간단하다. 먼저 중요 포인트의 리비전에 해당하는 파일을 모두 받는다. 이것을 리비전 별로 묶고 아래와 같은 절차를 밟는다.

• 가장 첫 리비전에 포함되는 파일은 모두 그대로 새 저장소에 추가
• 그 다음 리비전 r 에 대해서 포함되어 있는 파일에 대해서
• 새 저장소에 없는 파일이 리비전 r 에 있다면 : Add file
• 새 저장소에 있던 파일이 리비전 r 에 없다면 : Delete file
• 새 저장소와 리비전 r 에 모두 있지만 내용이 다르다면 : Modify file
• 위 내용을 새 저장소에 커밋. 마지막 리비전이 될 때까지 반복

그다지 복잡하지 않다. 다만 새 저장소에 대해 위에서 설명한 리비전 변경 작업을 생성해 내고 수행 하는 스크립트 작업을 해야 한다. 하지만 상대적으로 간단한 기능만으로 가능하기 때문에 수월한 편이다. 또한 중요 포인트를 촘촘히 설정하면 이력이 뭉게지는 범위를 좁힐 수 있다.

이점: 최근 스냅샷 유지 + (주요) 과거 시점의 스냅샷의 완결성 유지

전략: 현재 파일의 변경 로그 유지

과거 스냅샷 보다는 현재 파일이 어떻게 변해왔는지를 유지하는게 중요하다면 현재 파일의 변경 로그 유지 방법을 사용해볼 수 있다. 이 방법은 마지막 리비전에 있는 파일과 이력만 새 저장소로 마이그레이션 하는 방법이다. 예제 데이터의 마지막 리비전 4에는 banana 와 orange 파일이 있는데 이 파일에 대한 이력만 추려서 새 저장소를 구성하면 아래와 같은 그림을 얻을 수 있다. 이 방법은 현재 남아있는 파일의 이력이 남기 때문에 blame 등의 기능을 종전과 같이 그대로 사용할 수 있는 장점이 있다.

구현은 예전 저장소에 있는 모든 파일들의 과거 이력을 얻는 것으로 시작한다. 개별 이력을 얻는 것이 보통의 버전 관리 시스템은 빠르지 않기 때문에 파일이 많은 경우 전체 리비전 정보로 부터 개별 파일 정보를 재구축 하는 것이 효율적이다.

• 예전 저장소 모든 리비전 r 에 대해 순서대로
• 리비전 r 에 해당하는 현재 파일의 이력이 있는 경우
• 그 파일의 첫 로그라면: Add file
• 그렇지 않은 경우라면: Modify file
• 새 저장소에 변경 내용 커밋

이 방법 역시 그다지 복잡하지 않다. 예전 저장소에서 개별 파일 이력을 얻는 부분도 일반적으로 대부분의 버전 관리 시스템이 지원하기 때문에 손쉽게 얻을 수 있다. 새 저장소에 파일을 추가하고 변경 내역을 구축하는 것도 Add 와 Modify 기능만으로 가능하기 때문에 간단하다. 특히 소스 저장소의 blame 을 그대로 사용할 수 있어 좋다. 또한 이미 삭제된 파일에 대한 데이터를 옮기지 않아 새 저장소 용량 절감 효과도 있다.

이점: 최근 스냅샷 유지 + 현재 파일의 변경 사항 로그 유지

전략: 변경 리플레이

예전 저장소의 모든 파일과 변경 이력을 최대한 그대로 마이그레이션 하고 싶다면 리비전 로그를 순서대로 새 저장소에서 동등하게 재현하는 변경 리플레이 방법을 사용할 수 있다. 이 방법은 최대한 모든 데이터를 그대로 새 저장소에 넣는 방식이기 때문에 매끄러운 마이그레이션이 가능하지만 그 만큼 비용이 많이 들 수 있다. 특히 서로 다른 버전 관리 시스템 간의 마이그레이션의 경우 제공되는 마이그레이션 솔루션이 없다면 손이 많이 가는 작업이 될 가능성이 높다. 만약 1:1 로 완벽하게 마이그레이션이 가능하다면 아래 그림처럼 예제와 동일한 로그가 새 저장소에 구축된다.

방법은 기본적으로 간단하다. 예전 저장소의 변경 내용을 순서대로 새 저장소에 적용하면 된다.

• 예전 저장소 모든 리비전 r 에 대해 순서대로
• 리비전 r 을 구성하는 변경 로그에 대해서
• 변경 로그가 add 면 새 저장소에 add
• 변경 로그가 modify 면 새 저장소에 modify
• 변경 로그가 delete 면 새 저장소에 delete
• ...
• 새 저장소에 변경 내용 커밋

서로 다른 저장소의 경우 리비전 변경을 구성하는 집합 (add, modify, ...) 이 달라 변환 과정이 필요한 경우가 많다. 따라서 완전한 구현을 목표로 하기 보다는 가능한 변경 집합을 제한하고 처리할 수 없는 것은 적당히 예외 처리하는 것이 현실적이다. (예를 들어 브랜치는 기본 모델 부터 다른 경우도 있다.) 적당한 선에서 탑협을 해 이 방법을 사용할 수 있다면 가장 완전한 마이그레이션이 될 수 있다.

이점: 현재 스냅샷 파일 유지 + 과거 시점의 스냅샷의 완결성 유지 + 현재 파일의 변경 내역 유지 

전략: 최신 스냅샷 + 현재 파일의 변경 로그 유지

기본적으로 최신 스냅샷을 사용하되 중요 파일에 대해서만 현재 파일의 변경 로그 유지 방법을 사용한다. 아래 그림은 orange 에 대해서는 최신 스냅샷을 banana 에 대해서는 변경 로그 유지를 적용한 예이다.

방법은 현재 파일 변경 로그 유지와 유사하다. 중요 파일은 기존과 같게 동작하도록 하고 그렇지 않은 파일에 대해서 로그를 옮기지 않으면 된다. 이 방법은 새 저장소의 용량을 절약할 수 있는 장점이 있다.

이점: 최근 스냅샷 유지 + (중요) 현재 파일의 변경 사항 로그 유지

전략: 주요 스냅샷 + 현재 파일의 변경 로그 유지

기본적으로 주요 스냅샷을 사용하고 마지막 스냅샷과 직전 스냅샷 사이는 변경 로그 유지 기능을 사용해 최근 변경 로그를 유지 하는 방법이다. 아래는 리비전 2, 4 를 주요 스냅샷으로 남기고 리비전 2 -> 4 사이의 변경 로그를 유지한 예이다.

방법은 마지막 리비전 직전까지는 주요 스냅샷과 동일하고 마지막 리비전 단계에서 현재 파일의 변경 로그 유지 방법과 동일하다. 이 방법은 주요 스냅샷을 재구성할 수 있고 현재 파일들의 최근 변경 사항을 확인할 수 있는데 특히 변경 이력은 과거는 그다지 상세할 필요가 없는데 반해 최근은 상세한 것이 좋기 때문에 적절히 균형을 맞춘 것이라 볼 수 있다. 과거 이력을 상세히 남기지 않기 때문에 저장소의 공간을 절약하는 장점이 있다.

이점: 최근 스냅샷 유지 + (주요) 과거 시점의 스냅샷의 완결성 유지 + 현재 파일의 (최근) 변경 사항 로그 유지

브랜치

브랜치는 앞서 설명한 트렁크에 발생하는 작업 이력에 비해 복잡하다. 특히 버전 관리 시스템 마다 특징히 달라 저장소 리플레이로 커버하기 어려울 수 있다. 이럴 때는 브랜치가 생성되는 시점과 브랜치 마지막 시점을 주요 스냅샷 방법을 사용해 구성해 주는 간단한 방법을 사용하는 것이 좋다. 보통 브랜치 보다는 트렁크의 로그가 중요하기 때문에 브랜치 시점과 현재 모습을 유지하는 쪽이 좋다.

주요 버전 컨트롤 시스템의 명령 예

마이그레이션 작업 때 다뤄봤던 subversion, mercurial, perforce 의 대략의 사용법과 팁을 남겨둔다.

Subversion

익스포트 작업 주요 명령어

svn list path                    # 디렉토리/파일 목록 출력
svn log                          # 저장소 리비전 로그 출력
svn log -v -r rev                # 리비전 작업 내용 출력
svn cat -r rev path > savepath   # 특정 리비전 때의 파일 내용 저장

파일 작업 주요 명령어

svn add filename                 # 추가
svn delete filename              # 삭제
svn move oldpath newpath         # 이동
svn copy srcpath dstpath         # 복사

커밋 명령어

svn commit -m LOG
svn propset --revprop -r HEAD svn:author AUTHOR
svn propset --revprop -r HEAD svn:date 2012-10-27T00:30:15.000000Z

SVN 의 propset 을 사용하기 위해서는 서버의 pre-revprop-change 가 exit 1 등으로 설정되어 있어야 한다. 그리고 svn:data 는 UTC 시간이다. 특히 Subversion 은 commit 을 저장소 루트 디렉토리하는 것이 원칙이나 빠르게 처리 하기 위해 변경이 발생한 디렉토리의 공통 부모 디렉토리에서 하는 것이 좋다. (가끔 update 가 필요하다고 svn 이 에러를 내면 저장소 루트에서 update 를 한 번 수행하면 해결이 된다)

Mercurial

익스포트 작업 주요 명령어

hg log                           # 저장소 리비전 로그 출력
hg log -v -r rev                 # 리비전 작업 내용 출력
hg cat -r rev path > savepath    # 특정 리비전 때의 파일 내용 저장

파일 작업 주요 명령어

hg add filename # 추가
hg remove filename               # 삭제
hg rename oldpath newpath        # 이동
hg copy srcpath dstpath          # 복사

커밋 명령어

hg commit -m LOG -u AUTHOR -d "2012-10-27 09:30:15" 

Subversion 과 비슷하다. 하지만 DVCS 라서 commit 명령어에서 자유롭게 author 와 date 를 지정할 수 있는 것이 특징이다. 또한 저장소가 로컬에 있기 때문에 디렉토리/파일 목록은 dir, ls 등을 사용하면 된다. hg 의 경우 실제 변경사항이 없는데 commit 을 요청하면 에러를 발생하니 이 부분에 대한 예외 처리가 필요하다.

Perforce

익스포트 작업 주요 명령어

p4 [dirs/files] path             # 디렉토리/파일 목록 출력
p4 changes                       # 저장소 리비전 로그 출력
p4 describe rev                  # 리비전 작업 내용 출력
p4 print -o savepath path@rev    # 특정 리비전 때의 파일 내용 저장

파일 작업 주요 명령어

p4 edit filename                 # 편집
p4 add filename                  # 추가
p4 delete filename               # 삭제
p4 rename oldpath newpath        # 이동
p4 copy srcpath dstpath          # 복사

커밋 명령어

p4 submit -d LOG
p4 change -o REV | change "Date:" "User:" | p4 change -i -f

Perforce 는 checkout 방식이므로 편집 전에 수정 요청을 해야한다. 그리고 perforce 의 경우 파일타입 설정에 주의를 기울여야 한다. (잘못 설정하면 파일이 깨지거나 submit 단계에 에러가 나거나 p4merge 에서 이상하게 나올 수 있다. 마이그레이션 작업전에 p4_filetypes 내용을 잘 살펴봐야 한다.) 또한 파일이름에 @ # * % 문자가 포함되어 있는 경우 이스케입을 해줘야 한다.

결론

저장소 마이그레이션의 여러 전략을 살펴보았다. 각 전략의 이점과 비용을 잘 살펴보고 최적의 방법을 결정하는 것이 중요하다. 또 저장소의 데이터는 프로젝트의 중요한 자산이니 무엇보다도 안전하게 누락없이 데이터를 옮기는데 주의를 기울여야 한다.

버전 관리 시스템의 저장소 관리

요즘 버전 관리 시스템을 사용하지 않는 곳을 찾아 보기 어려울 정도로 버전 관리 시스템은 이제 개발에 필수 요수가 되었다. 이 시스템을 사용하기 전엔 도대체 어떻게 개발을 했나 싶을 정도다.

이제는 사용 요령이나 유용한 팁들이 많아 시스템 사용에 큰 어려움이 없이 잘 쓰지만 정리 차원에서 저장소 관리 가이드라인을 적어본다. 어디까지나 개인적인 프로젝트 경험에 의한 내용이니 적용에는 응용이 필요하다.

저장소와 관련된 가장 기본적인 가이드라인은 다음과 같다.

• 소스 저장소에 개발 / 빌드에 필요한 모든 것을 넣어둔다.
• 소스 저장소와 리소스 저장소를 분리한다.
• 사용 / 관리 정책을 세워야 하고 관심을 기울여 줘야 한다.

좀 더 자세히 살펴보자.

소스 저장소에 개발 / 빌드에 필요한 모든 것을 넣어둔다.

소스 저장소에는 팀에서 개발하는 소스에 더해 빌드에 필요한 라이브러리와 툴이 포함되어 있어야 한다. 만약 개발중인 프로그램이 expat, boost, directx sdk 를 필요로 한다면 이 라이브러리들을 모두 넣어둔다. 이렇게 하면 프로그래머가 일일이 라이브러리를 구해야 하는 수고도 줄고 버전이 불일치 하는 일도 없고 언젠가 있을 라이브러리 업데이트도 자연스럽게 되어 좋다. 

다만 배포되는 라이브러리에 포함되어 있는 모든 파일을 넣지 않도록 조심해야 한다. 라이브러리에 포함되어 있는 튜토리얼, 샘플, 문서, 다른 플랫폼용 파일, 안쓰는 빌드 구성용 lib, pdb 파일 등은 불필요하게 저장소 용량만 차지한다. (예를 들어 boost 1.51 의 경우 빌드 없는 구성으로 총 용량이 334MB 인데 그 중 빌드에 필요한 boost 폴더는 86MB 로 25% 에 불과하다.) 필요한 파일만 등록하고 나중에 해당 라이브러리를 업데이트 할 수 있으니 어디서 구할 수 있는지, 중요 파일을 어떻게 추렸는지 기록해두거나 스크립트로 만들어 저장소에 넣어두면 도움이 된다. 상용 라이브러리라 보관이 꼭 필요하다 싶으면 패키지를 압축해서 올리는 것도 요령이다. 버전 관리 시스템은 많은 파일, 큰 용량 처리에 특화되어 있지 않다.

외부 라이브러리를 svn 의 external link 등으로 연결하는 방법은 효과적인 방법이다. 하지만 내부 프로젝트에서는 추천하지 않는다. 외부 네트워크에서 격리된 곳에서 빌드를 해야할 수도 있고 네트워크 장애로 설치에 어려움을 겪을 수도 있기 때문이다.

외부 라이브러리에 더해 빌드에 관여하는 툴도 저장소에 넣어둔다. 예를 들면 빌드 솔루션, 코드 생성기, 어셈블리 컴파일러 등을 저장소에 같이 넣어둔다. 단 비주얼 스튜디오 등 배보다 배꼽이 커지는 경우도 있으니 득실을 따져보고 넣는다.

소스 저장소와 리소스 저장소를 분리한다.

기본적으로 1개의 프로젝트에 1개의 저장소가 원칙이다. 하지만 리소스가 소스 보다 열 배 이상 용량이 크다면 분리하는 편이 관리와 사용에 유리하다.

소스는 아무리 커져봐야 스냅샷 기준으로 1GB 이상을 넘기가 어렵다. (팀에 코딩 머신이 있어) 매일 10% 분량이 새롭게 수정된다고 해도 저장소 용량이 1TB 까지 가는데 대충 30년이 걸린다. 게다가 텍스트 데이터는 보통 delta 압축이 되어서 실제 용량보다 훨씬 적게 늘어난다.

리소스의 경우 요즘 온라인 게임은 10GB 정도는 기본이고 그 이상도 많다. (역시 팀에 리소스 머신이 있어) 매일 10% 분량이 새롭게 수정된다고 하면 저장소 용량이 1TB 까지 가는데 대충 3년이 걸린다. 3년이 어떤 조직에는 충분히 길 수도 있겠지만 보통 개발 기간 + 라이브 기간 이렇게 합치고 보면 3년은 프로젝트 일생의 유년기 쯤에 해당한다.

문제는 저장소 용량이 커지면 일단 하드도 부족하고 버전 관리 시스템도 느려지고 백업도 어려워지고 이래저래 골치가 아파진다. 이럴 때 보통 최신 스냅샷 + 최근 이력 정보만 남기고 데이터를 지워버리는 저장소 세탁을 하게 된다. 그런데 소스랑 리소스가 같은 저장소에 있으면 소스 이력도 세탁이 되어버린다. 그러면 과거 로그, blame 을 할 수 없게 된다. 특히 몇 년쯤 된 코드의 버그를 추적하다가 로그가 없는 것을 발견하는 것만큼 당황스러운 것도 없다.

백업도 비슷한 이슈가 있다. 백업 공간이 충분하다면 그냥 저장소 내용 전부를 덤프해버리면 되겠지만 백업 용량이 부족하면 스냅샷만 남겨야 한다. 소스의 경우 과거 이력을 잘 보존하는 것이 중요하기 때문에 스냅샷만 남기는 것만으로는 부족하다. 만약 소스와 리소스의 저장소가 분리되어 있다면 '소스는 저장소 전부. 리소스는 스냅샷만.' 과 같이 스토리지 용량에 맞춰 융통성 있게 정책을 세울 수 있다.

사소하지만 권한 설정도 소스, 리소스 저장소가 분리되어 있다면 원천적으로 분리되니 도움이 된다.

소스랑 리소스가 분리되어서 서로 버전 매칭하기가 atomic 하지 않을 수 있는데 일단 대강 시간으로 맞출 수 있고, 좀 더 타이트 하게 하고 싶다면 tag, branch 등의 기능을 활용해 해결할 수 있다.

사용 / 관리 정책을 세워야 하고 관심을 기울여 줘야 한다.

저장소는 쉽게 오염된다. thumbs.db, project.ncb, 누구누구받아.zip 등 용량만 크고 올라갈 필요가 있는 것들이 올라간다. 이런 문제는 커밋 단계에 적당한 후킹 핸들러를 붙여 애초에 이런 파일이 커밋되지 않도록 시스템화 하는 것이 좋다. 비슷하게 커밋 로그를 강제하는 용도로도 사용할 수 있다.

저장 솔루션을 배포 시스템으로 사용하는 것은 추천하지 않는다. 예를 들어 프로그램 실행파일을 팀에서 공유하기 위해 배포 시스템에 올리는 것은 빠르게 저장소 공간을 소모하는 가장 쉬운 방법이다. 예를 들어 빌드로 생성되는 파일 용량이 50MB 라고 하고 매일 10번 정도 빌드가 이루어지면 365 일 열심히 일하고 나면 저장소 공간을 180GB 차지하게 된다. 가끔 있는 작은 크기의 파일이라면 모를까 일반적인 배포는 ftp, 공유 폴더, torrent 등 파일 공유를 위한 솔루션을 쓰는 것이 좋다.

로그를 남기는 방식, 커밋 주기, 단위 등은 팀에서 사용 방식을 결정하고 잘 지켜지도록 보조 시스템을 붙이고 모니터링 해야 한다. 장기적으로 잘 관리된 저장소와 친절한 로그는 개발 단계와 라이브 시기 모두에게 큰 힘이 된다.

저장소 용량 증감, 버전 관리 시스템 건강 상태를 주기 적으로 살펴야 한다. 그리고 불필요한 파일이 올라가는지, 저장소 사용 정책에 위배되는 것이 있는지 살피는 것도 중요하다. 버전 관리 시스템은 개발 시스템중 가장 중요한 시스템임을 잊어서는 안된다.

정리

버전 관리 시스템의 가장 기본인 저장소 관리에 대해한 가이드라인을 정리했다. 이걸 잘 하고 나면 이제 그 위에 폴더 구성, 브랜치 전략을 고민할 수 있다.

문자열 키의 map, unordered_map 성능 비교

map 과 unordered_map 은 키, 값을 저장할 수 있는 컨테이너다. map 은 Red-Black Tree 를 사용해 키의 순서를 유지하는 반면 unoredered_map 은 해시 테이블을 사용해 키의 순서를 유지하지 않는다. unordered_map 은 키의 순서를 유지할 필요가 없기 때문에 탐색 속도등에 유리한 점을 가질 수 있다. (아래 그림 좌: Red-Black Tree, 우: Separate Chaining Hash Table)

데이터가 N 개일 때 map 은 O(lgN) 의 탐색 속도를 보이고 unordered_map 은 O(1) 의 탐색 속도를 보인다. 때문에 데이터가 많을 수록 unordered_map 이 속도에 유리한데 문제는 "언제부터 유리한가?" 이다. 특히 키가 문자열일 때는 어떤 차이가 발생하는지가 궁금해 몇 가지 테스트를 해보았다. (문자열에 대한 궁금증은 지난번 Static String Table Lookup using Radix Tree 의 벤치마크 결과 때문이다)

Map, Unordered_map<int, ...>

먼저 다음과 같이 int 를 키로 받는 map, unordered_map 타입의 변수를 준비한다.

std::map<int, int> map;

std::unordered_map<int, int> umap;

struct bypass {
  size_t operator()(int v) const {
    return (size_t)v;
  }};
std::unordered_map<int, int, bypass> umap_raw;

unordered_map 의 경우 두 개를 만들었는데 하나는 hash 함수로 기본 hash<int> 를 사용하는 것과 나머지 하나는 키 값을 그대로 해시 값으로 사용하는 것이다. VC++ 의 unordered_map 은 해시값으로 부터 버킷을 찾아낼 때 해시값의 하위 b 비트를 보는 형태로 구현되어 있어서 키에 대한 hash 값의 하위 b 비트의 분포가 고른지가 중요하다. 때문에 기본 hash<int> 는 입력값의 하위 b 의 분포가 고르지 않더라도 그것을 고르게 만드는 역할을 한다. 하지만 입력 데이터의 키의 하위 b 비트가 애초부터 고르다면 그대로 해시값으로 쓰는 것도 고려해볼만 하다. 이를 확인하기 위해 hash<int> 사용 umap 과 bypass 사용 umap_raw 이렇게 2개를 만들었다.

다음은 데이터 N 개를 컨테이너에 넣고 탐색을 한다. 테스트는 간단히 [0, N) 범위의 정수를 키로 넣고 그 키들을 다시 탐색하는데 얼마나 걸리는지를 측정했다.

Test<T>
{
  T dict;
  for (int i=0; i<N; i++)
    dict.insert(make_pair(i, i));

  // Measure Elapsed Time
  for (int i=0; i<N; i++)
    dict.find(i);
}

그 결과는 다음과 같다. (실행 환경: Intel i7-3550 3.3GHz, Windows 7 SP1, VC++ 10 SP1)
X 축은 데이터 크기 N, Y 축은 탐색 1회에 걸린 시간 µs 이다.

먼저 map은 O(lgN) 의 형태를 보이는 것을 알 수 있다. 다만 128~512 구간에서 급격히 느려지는데 이는 캐시 미스의 영향으로 보인다. unordered_map 은 hash<int> 와 bypass 모두 O(1) 의 형태를 보인다. 특히 bypass 는 hash 단계에 시간을 소모하지 않아 hash<int> 에 비해 2배 빠른 것을 볼 수 있다. 이 그래프로 부터 hash<int> 을 사용했을 때는 N 이 32 부터, bypass 를 사용할 때는 N 이 6 일 때 부터 unordered_map 이 map 보다 탐색에 유리한 것을 알 수 있다. (다만 이 magic number 는 컴파일러, STL, 실행 환경에 종속적이니 참고에 주의해야 한다.)

그렇다면 문자열이 키인 경우에는 어떨까?

Map, Unordered_map<const char*, ...>

키로 넣을 문자열 집합을 정의하자. 먼저 문자열 길이를 M 이라 하고 문자열을 구성하는 문자 집합을 A 라고 한다. 예를 들어 문자열 길이 M=4, 문자 집합 A={0..9, A..F } 에 해당하는 문자열들의 예는 다음과 같다.

• 0000 1101 ... 9A8E 9A8F ... FFFF

이 집합에서 사전식 순서로 전체 집합에서 균일한 간격을 가지는 데이터 4개를 뽑으면 다음과 같은 문자열을 고를 수 있다.

• 0000 5555 AAAA FFFF

만약 동일한 집합에서 32 개를 뽑으면 다음과 같은 문자열을 고를 수 있다.

• 0000 0842 1084 18C6 ... E738 EF7A F7BC FFFF

일반화 시키면 길이가 M 인 문자열 집합에서 N 개의 문자열을 뽑을 때는 사전식 순서로 번호를 매긴 문자열 리스트에서 0, A^M/(N-1), 2*A^M/(N-1) ... A^M-1 번째 문자열을 키로 사용한다고 할 수 있다.

이렇게 고른 키를 가지고 다음과 같은 map 과 umap 에 키, 값을 등록한다.

struct less_str {
  bool operator () (const char* a, const char* b) const {
    return strcmp(a, b) < 0;
  }};
std::map<const char*, int, less_str> map;

struct hash_str {
  size_t operator()(const char* s) const {
    size_t v = 0;
    while (char c = *s++) {
      v = (v << 6) + (v << 16) - v + c;
    return hash<int>()(v);
  }};
struct equal_str {
  bool operator () (const char* a, const char* b) const {
    return strcmp(a, b) == 0;
  }};
std::unordered_map<const char*, int, hash_str, equal_str> umap;

unordered_map 의 hash 함수로 sdbm 해시 함수를 사용했다. 그리고 그 결과를 바로 hash 값으로 사용하지 않고 hash<int> 를 한 번 더 실행해 사용했다. 왜냐하면 sdbm 해시 함수가 하위 b 비트의 균일성을 보장해주지 않기 때문이다. 이제 준비가 되었으니 아래와 같이 탐색!

Test<T>
{
  T dict;
  for (int i=0; i<N; i++)
    dict.insert(make_pair(k[i], i));

  // Measure Elapsed Time
  for (int i=0; i<N; i++)
    dict.find(k[i]);
}

결과는 아래와 같다. M 이 4, 8, 12, 16 의 경우를 테스트했고 X 축은 데이터 크기 N 이고 Y 축은 탐색 1회에 걸린 시간 µs 이다.

 

기본적으로 정수가 키인 경우와 비슷한 결과를 보인다. 하지만 M 의 크기 변화에 따라 재미있는 현상이 발생하는데 map 과 unordered_map 의 성능이 교차하는 점이 M 이 커짐에 따라 같이 커지는 현상이다. 이를 좀 더 잘 보기위해 M 에 따라 map 탐색시간 / unordered_map 탐색시간 비율 그래프를 아래와 같이 그려봤다.

M=4 일때 ratio 가 1이 되는 지점은 N=128~256 지점이고 M=16 일때 ratio 가 1이 되는 지점은 N=512~1024 지점이다. M 이 커질 수록 map 이 유리한 N 의 범위가 커지는 것을 볼 수 있다.  왜그럴까?

시간 복잡도

map 와 unordered_map 의 "문자열 단위" 탐색 작업의 시간 복잡도는 다음과 같다.

• map: 
• 노드 마다 문자열 비교: O(lgN)
• 마지막 노드의 문자열 비교: O(1)
• unordered_map:
• 입력 문자열의 hash function 수행: O(1)
• 입력 문자열과 버킷에 있는 문자열 비교: O(1)

이번에는 문자열 길이를 적용해 "문자 단위" 탐색 작업의 시간 복잡도를 계산해보자.

• map: 
• 노드 마다 문자열 비교: ?
• 마지막 노드의 문자열 비교: O(M)
• unordered_map: 
• 입력 문자열의 hash function 수행: O(M)
• 입력 문자열과 버킷에 있는 문자열 비교: O(M)

map 의 노드 마다 문자열을 비교하는 부분의 시간 복잡도를 구해보자. map 을 구성하는 트리가 완전하게 균형된 트리를 구축했다고 했을 때 M=4 의 트리는 다음과 같은 형태를 가진다.

먼저 키로 받은 데이터 분포 특성에 의해 d=0 노드는 첫 글자 만으로 분기가 가능하다. 이 부분이 중요한데 노드 분기를 위해 문자 M 을 모두 비교할 필요가 없기 때문이다. d=4 노드부터 두번째 문자까지 비교를 해야 한다. 이를 일반화 하면 노드 깊이 d 일 때 분기를 위해 필요한 문자 비교 횟수는 다음과 같다.

첫 노드부터 마지막 노드까지의 비교 횟수의 합은 다음과 같다.

따라서 비교에 필요한 횟수는 길이 M 과 관계 없이 N 에 종속적인 것을 알 수 있다. (이것은 키 문자열 집합의 분포 특성 때문에 그렇다)

map 과 unoredered_map 을 N 과 M 의 시간 복잡도로 표시하면 다음과 같다. (문자 단위)

• map: O(lgN^2) + O(M)
• unordered_map: O(M) + O(M)

map 은 M 의 길이에 덜 반응하고 unordered_map 은 M 의 길이에 그대로 반응하기 때문에 M 이 커짐에 따라 map 보다 unordered_map 의 속도 저하가 커질 수 있다.

하지만 위의 분포는 다소 인위적인 분포이며 실제 키 문자열 집합이 이러한 이상적인 분포를 가지는 경우는 드물다. 하지만 대부분의 데이터는 어느정도 이런 형태를 유지하는데 예를 들면 기본 컬러 16 의 이름은 다음과 같다.

• black, blue, cyan, gray, green, lime, magenta, maroon,
  navy, olive, purple, red, silver, teal, white, yellow

이 집합은 N 이 16 이고 |A|=26 이기 때문에 모든 노드에서 첫번째 문자만으로 분기가 가능해야 한다. 하지만 (black, blue), (gray, green), (magenta, maroon) 의 경우에는 세 번째 문자까지 봐야 구분이 가능하다. 그럼에도 불구하고 특정 문자열 X 가 주어졌을 때 이 X 가 노드 분기에 필요한 문자 비교 횟수는 대부분 1이다. (예를 들어 magenta 가 주어졌을 때 maroon 을 제외하고는 모두 비교 횟수 1이다) 따라서 이 문자열 집합도 map 이 unordered_map 보다 탐색 속도에 우위를 가지게 된다.

하지만 만약 문자열의 형태가 아래와 같이 접두사가 비슷한 경우라면 비교 문자 개수가 크게 늘어나 전혀 다른 양상을 보인다.

• abnormal abnomality abnomalities abnormalization

결론

몇가지 테스트를 해서 정리를 해보면 이렇다.

• map, unordered_map 의 탐색 속도는 데이터 크기 N 이 작을 때는 map 이 클 때는 unordered_map 이 유리하다.
• map 은 데이터 크기 N 이 커짐에 따라 unordered_map 보다 캐시 미스의 영향을 더 빨리 받는다. 이것은 map 이 탐색을 위해 여러 노드를 방문해야 하기 때문으로 보인다.
• unordered_map 은 해시 함수의 성능이 중요하다. 특히 VC++ 의 경우에는 하위 b 비트의 고른 분포가 중요하다.
• 문자열 키를 사용하는 경우 정수 키를 사용하는 경우에 비해 map 이 더 큰 N 까지 탐색 성능 우위를 가진다. 이것은 문자열 비교에 적은 비교 횟수를 필요로 하기 때문이다.
• 따라서 문자열 길이가 길고 데이터 크기가 크지 않은 경우에는 map 이 unordered_map 보다 탐색에 유리하다.

map 도 좋고 unordered_map 도 좋다. 왜 이렇게 unordered 치는데 오타가 나는지는 모르겠지만...

Make from VC++ Project

작년에 있었던 팀의 서버 프로그램은 윈도우, 리눅스 양쪽에서 실행 가능했다. 윈도우에서는 Visual C++ 를 리눅스에서는 gcc 를 사용해서 빌드를 했다. 팀내 빌드, 테스트 시나리오는 다음과 같다.

• 개발 단계에서는 Visual C++ IDE 를 사용해서 개발
• 개발 테스트는 Visual C++ 혹은 gcc 사용 (개발자 선호에 따라)
• 내부 테스트 및 실제 서비스는 gcc 로 빌드해 리눅스에서 서비스.

때문에 윈도우 빌드용 vcxproj 와 리눅스 빌드용 makefile 이 개별적으로 유지되고 있었다. 그래서 프로젝트 구성을 변경해야 할 경우 vcxproj 와 makefile 양쪽을 수정해야 하는 번거로움이 있었다. 양쪽을 동일하게 맞추는 것을 놓쳐 빌드가 깨지는 경우도 종종 있었다.

일반적으로 이런 상황을 해결하는 방법은 둘 다 커버할 수 있는 하나의 빌드 시스템을 사용하는 것이다. cmake, scons 가 대표적인 멀티 플랫폼 빌드 시스템이다. (Make Alternatives 에서 잘 다루고 있다.) 두 시스템이 잘 되어 있어보여 적용할지를 고민하다가 최종적으로 쓰지 않는 것으로 결정했다. 이유는 다음과 같다.

• cmake, scons 는 마스터 빌드 설정 파일을 따로 만들어야 한다.
  즉 Visual C++ 프로젝트도 아니고 makefile 도 아닌 별도의 빌드 설정을 만들어야 한다. 이 마스터 빌드 파일을 가지고 각 플랫폼별 빌드 파일을 만들어 주거나 직접 빌드를 한다. 좋아보이나 마스터 빌드 설정을 하기 위해 모든 프로그래머가 사용법을 익혀야 하는 부담이 있다.
• Visual C++ IDE 를 사용해 개발하는데 이 IDE 에서 파일 추가/삭제 하던 작업을 마스터 빌드 설정을 통해서 해야 한다. 쉬운 툴 작업이 번거로운 텍스트 편집 작업이 된다
• cmake, scons 모두 Visual C++ 를 지원하지만 (여러 오픈 소스가 그러하듯) 우선순위가 낮다. 최신 버전 Visual C++ 지원이 엉성하거나 특정 컴파일 옵션을 사용할 수 없거나 할 수 있다.

만약 처음부터 cmake 나 scons 등을 썼다면 상황이 많이 달랐겠지만 중간에 빌드 솔루션을 바꾼다는게 간단하지 않을 뿐더러 이득보다 손해가 많을 상황이라 다른 해결책을 찾기로 했다. 그래서 생각해낸 것은

• 윈도우 빌드는 원래 하듯 Visual C++ 프로젝트 파일로 빌드 
• 리눅스 빌드는 make 가 Visual C++ 프로젝트 파일 내용을 읽어서 빌드

이렇게 하면 프로젝트 파일을 하나만 유지할 수 있어서 원래 해결하려 했던 문제가 자연스럽게 해결된다. 또한 새 시스템을 도입하는 것이 아니니 큰 학습 비용 없이 적응해 사용할 수 있다. 자 그럼 어떻게 할까?

Make, the Legacy

Make 는 1977 년에 첫 개발되어서 30 년 넘도록 Unix 계열 OS 에서 널리 사용되고 있다. Rule 의 집합으로 이루어진 파일 makefile 을 바탕으로 빌드 작업을 수행해 주는데 Rule 의 간결하고 강력한 특성으로 아직까지도 광범위 하게 사용되고 있다. 다음은 makefile 의 간단한 예제이다. 

# <rule>
# target: prerequisite
#   recipe

exe: main.o lib.o
  g++ main.o lib.o -o exe

main.o: main.cpp
  g++ -c main.cpp

lib.o: lib.cpp
  g++ -c lib.cpp

기본 개념이 강력한데 반해 (Rule 개념은 거의 모든 빌드 시스템에서 차용하고 있다.) 다만 워낙 옛날에 만들어지고 이러한 형태의 첫 프로그램이다 보니 Rule 외의 기능은 엉성하다. 변수, 제어, 함수 등 언어적 지원은 빈약하고 shell 명령으로 이루어져 다양하게 확장 가능한 recipe 에 비해 prerequisite 은 확장이 어렵다.

make 로 어떻게 하면 vcxproj 빌드를 할 수 있을까? 를 염두하며 Make Manual 을 읽고 나니. 쉽지 않겠구나 라는 생각이 들었다. (make 도 리눅스 개발 환경도 제대로 써본건 이때가 처음이기도 했다)

Import File List

기본 개념은 간단하다. Make 가 실행될 때 프로젝트 파일인 vcxproj 포함되어 있는 cpp 파일 목록을 가져와 makefile 에 넣기. 목록을 제외한 나머지 부분은 (예를 들면 컴파일 옵션) 미리 파일에 적어두고 변경이 많고 플랫폼별 차이가 없는 파일 목록을 끌어오면 되지 않을까?

• 먼저 VC++ 프로젝트 파일로 부터 포함되어 있는 cpp 파일 목록을 추리는 기능을 만든다. makefile 로는 불가능해보여 (XML 파싱이 필요하므로) python 으로 작성한 스크립트를 만든다. (Import.py)
• makefile 의 include 기능을 이용해 목록을 가져와 해당 cpp 파일들을 빌드하게 만든다.

Import.py 는 프로젝트 파일로 부터 파일을 읽어 아래와 같은 형태의 결과를 출력한다.

SRCS := main.cpp lib.cpp
OBJS := $(I)main.o $(I)lib.o

$(I)main.o : main.cpp
  g++ $(CXXFLAGS) -c $< -o $@

$(I)lib.o : lib.cpp
  g++ $(CXXFLAGS) -c $< -o $@

그 결과를 받아다가 make 가 처리하도록 makefile 에 아래와 같은 구문을 넣는다.

include $(shell Import.py Program.vcproj > l.tmp && echo l.tmp)

exe : $(OBJS)
  g++ -o $@ $(OBJS)

이제 빌드할 파일 목록을 자동으로 가져올 수 있게 되었다. 이 목록은 컴파일 뿐 아니라 clean 에도 사용된다. 정확히 어떤 파일이 있고 (SRCS) 어떤 중간 생성물을 만드는지 (OBJS) makefile 이 알기 때문에 clean 도 해당 파일들만 깨끗하게 지울 수 있다.

Include Dependency

앞서 만든 빌드 Rule 셋을 보면 사실 불완전한 부분이 있는데 바로 prerequisite 부분이다. C/C++ 은 cpp 파일 뿐 아니라 #include 헤더가 변경되어도 재컴파일을 해야 하는데 이 부분이 빠져있다. (예를 들어 main.cpp 가 lib.h 를 #include 하고 있다면 lib.h 가 변경되어도 main.cpp 가 재컴파일이 되어야 한다. 따라서 저 위 main.o 룰의 prerequisite 은 main.cpp lib.h 가 되어야 한다)

이 부분이 make 의 까다로운 부분인데 make 스스로 할 수 없으므로 (언어 종속적이라) 보통 makedep 과 같은 외부 프로그램을 사용해 makefile 파일 뒷부분에 dependency 룰을 추가하는 방식으로 동작한다. (make dep 이 그 과정을 수행한다) 반면 Visual C++ 의 경우 이 과정이 숨겨져 있어 자연스럽게 프로그래머는 이 부분을 신경쓰지 않아도 된다. 그래서 새 makefile 도 자연스럽게 #include 종속 관계를 얻을 수 있도록 Import.py 에 기능을 넣었다.

• Import.py 가 실행될 때 Dependency 를 얻어올 수 있는 Rule 파일을 생성함
• makefile 이 생성된 모든 Dependency Rule 파일을 가져옴

특정 C/C++ 파일이 어떤 파일에 대해 #include 종속을 가지는지는 gcc 를 사용해 쉽게 알아낼 수 있다. gcc 의 -M 과 -MM 옵션을 사용하면 다음과 같은 형태로 종속 룰을 출력한다.

main.o : main.cpp lib.h

이와 같은 gcc 기능을 사용하도록 Import.py 는 프로젝트 파일로 부터 파일을 읽어 아래와 같은 형태의 결과를 출력한다.

DEPS := $(I)main.d $(I)lib.h

$(I)main.o : $(I)main.d
$(I)main.d : main.cpp
  g++ -MM $< | sed 's,\(.*\)\.o[ :]*,$(I)\1.o $(I)\1.d : , ' > $@

$(I)lib.o : $(I)lib.d
$(I)lib.d : lib.cpp
  g++ -MM $< | sed 's,\(.*\)\.o[ :]*,$(I)\1.o $(I)\1.d : , ' > $@

file.d 형태의 dependency 파일을 생성하는 Rule 이다. file.o 보다 먼저 file.d 를 생성하기 위해 prerequisite 설정해준다. 또한 file.o 뿐 아니라 file.d 도 #include dependency 가 걸리도록 sed 로 gcc 결과를 살짝 수정해준다. Recipe 에 의해 생성된 main.d 파일은 다음과 같다.

main.o main.d : main.cpp lib.h

생성된 *.d 파일을 make 가 처리하도록 makefile 에 아래와 같은 구문을 넣는다.

include $(filter $(DEPS),$(wildcard $(I)*.d))

이렇게 해서 Include Dependency 를 해결한다. 별도의 make dep 과정 없이 build 요청에 따라 알아서 재컴파일이 필요한 소스 파일을 make 가 잘 찾아 주게 되었다.

Precompiled Header

Visual C++ 프로젝트는 precompiled header 를 사용하도록 되어있고 gcc 프로젝트는 그렇지 않도록 되어 있었다. Precompiled header 를 사용하면 gcc 에서도 빌드 시간이 단축되므로 gcc make 에서도 사용하도록  Import.py 에 기능을 추가했다.

• Import.py 가 실행될 때 프로젝트 파일에서 Precompiled header 파일을 찾아서 gch 빌드 명령을 추가한다.
• gch 가 다른 파일 보다 먼저 빌드가 되어 소스파일의 #include 경로에 존재하면 gcc 가 빌드 때 gch 파일을 우선적으로 사용한다. (VC++ 와 명시적으로 지정하지 않아도 된다.)

Import.py 는 다음과 같은 형태의 명령을 추가한다.

GCHS := $(I)pch.h.gch

$(I)pch.h.gch : pch.h 
  g++ $(CXXFLAGS) -x c++-header $< -o $@

$(OBJS) : $(GCHS)

간단히 gcc 빌드에도 precompiled header 를 사용할 수 있게 되었다.

More

작업을 하다보니 있으면 편한 자잘한 기능이 추가되었다. 추가한 기능을 정리하면

• 자동 병렬 빌드 기능
  빌드가 되는 CPU 의 코어 개수를 파악해 권장 개수 만큼 make 의 병렬 빌드 기능을 사용한다.(make 의 -j 옵션 사용)
• vcxproj 파일을 지정하지 않았을 때 실행 폴더에 vcxproj 가 1개만 있는 경우 그 파일을 자동 선택.
  이런 기능은 make 도 있는데 은근히 편리하다.
• Prebuild, Postbuild 이벤트 지원
  프로그램의 Version 정보를 태깅하거나 symbol 등록을 할 때 사용한다.
• Google Performance Tools 빌드 옵션 지원
• 빌드에 필요한 라이브러리 지정 기능

처음에 생각했던 것보다 더 많은 기능이 추가 되었는데 이는 서버 관련 프로젝트가 10개 이상이었고 기능을 추가했을 때 이득을 볼 프로젝트가 많아서 였다. 추가 기능들로 makefile 은 다음과 같은 정보만 가지고 있었다.

• 종속 라이브러리 목록. 
• 출력 폴더/파일 이름. 
• 컴파일, 링크 옵션. 
• 병렬 빌드 여부, Google Performance Tools 사용 여부 등 기타 옵션.

다음은 위 작업이 적용된 어느 서버의 Makefile 내용이다.

OUTDIR = ./Bin/
OUTPUT = $(OUTDIR)server

DEPLIB = Core Network Data

CXXFLAGS_CUSTOM = $(call lib_I,MySQL) -I./Bin -D_CHECK
LDFLAGS_CUSTOM  = $(call lib_L,MySQL) -lmysql

include MakefileTemplate

MakefileTemplate 은 Import.py 를 사용하며 다음과 같다. (일부만 표시)

.PHONY : BuildEntry
BuildEntry : $(MAKE_BUILD_DEFAULTCONFIG) ;

ifneq ($(CONFIG),)
  ifndef VCXPROJ
    VCXPROJ := $(wildcard *.vcxproj)
  endif
  include $(shell Import.py $(VCXPROJ) > l.tmp && echo l.ret)
  include $(filter $(DEPS),$(wildcard $(I)*.d))
endif

$(OBJS) $(DEPS) $(GCHS) : | $(I)

$(I) :
  mkdir -p $(I)

결론

간단한 파이썬 스크립트와 make script 로 로 원하던 목표를 달성했다. (파이썬 스크립트와 관련 make 스크립트의 라인 수가 200 이 채 되지 않는다) 

윈도우 파일 캐시 비우기

오랜만에 클라이언트 시동 시간을 줄이는 최적화 작업을 하면서 Cold Start 환경을 만들어야 할 상황이 생겼다. (Cold Start 는 시동에 필요한 파일들이 캐시에 있지 않에 디스크로부터 파일 데이터를 읽어야 하는 Start 를 의미한다. 때문에 느리다.)

간단히 File Cache 를 비워주면 되는데 이게 말처럼 간단하지 않다. 파일 캐시를 비운다라는게 일반적으로는 필요한 기능이 아니기 때문에 OS 가 굳이 일반 유저를 위해 기능으로 만들지 않기 때문이다. 때문에 예전에 Windows XP 환경에서 개발을 할 때는 두 가지 우회 방법 중  하나를 사용했다.

• PC 재부팅
  단순 무식한 방법이지만 확실하다. 다만 부팅 시간이 소요되는 단점이 있다.
• 과중한 메모리 할당
  PC 재부팅이 오래 걸리니까 메모리를 무지막지하게 할당하는 프로그램을 돌려 캐시가 할당했던 메모리를 강제로 빼았는 방식이다. 효과적인 방법이나 캐시 메모리만 제거되는게 아니라 지금 돌고 있는 잘 도는 프로세스의 워킹셋 까지 페이징을 시켜서 한참동안 시스템이 버벅거리는 문제가 생긴다.

위 두가지 방법을 쓰면서 "OS 가 해주면 좋겠는데 그걸 안해주니 고생하는 구나" 라고 생각했었다. 이번에 Windows 7 환경에서 작업을 하기전에 혹시나 해서 찾아봤더니! 있다! 이제는 있다!

Sysinternals Cacheset / Rammap

참 고마운 사람들이다. Sysinternals 에서 만든 유틸리티들을 요긴하게 잘 쓰고있는데 캐시를 날리는 유틸리티도 만들어 놨다. 먼저 Cacheset 은 캐시 크기를 제어하는 유틸리티다. 

여기서 Clear 버튼을 누르면 캐시가 날아간다. 하지만 다 날아가지 않는다. 여기에 윈도우 캐시 시스템의 미묘함을 볼 수 있다. 완전히 날리기 위해서는 추가로 Rammap 을 사용해야 한다. Rammap 은 시스템 메모리의 사용 상태를 보는 유틸리티이다. 거기에 유틸리티 기능으로 Empty 기능이 포함되어 있다.

Empty - Empty Standby List 메뉴를 선택하면 캐시를 완전히 비울 수 있다. 이 RamMap 은 Windows Vista 부터 사용할 수 있기 때문이 이 편리한 과정은 Windows Vista 부터 사용할 수 있다.

특히 Empty Standby List 과정이 중요하고 효과적인 과정이라 만약 번거롭다면 두 번째 과정만 수행해도 큰 무리는 없다.

아래는 각 과정을 밟을 때 작업 관리자로 본 메모리 상태이다. 캐시됨 이라는 항목이 캐시에 관여한 메모리 크기인데 첫 번째 Cacheset Clear 를 눌렀을 때는 오히려 약간 증가한 것을  볼 수 있다. 그리고 두 번째 Empty Standby List 를 눌렀을 때 확연히 줄어드는 것을 볼 수 있다. (캐시됨 항목에 사실 Cacheset Workingset 이 포함되지 않는다. 캐시됨 = Standby + Modified. 따라서 첫번째 Cacheset Clear 때 캐시됨 메모리가 늘어나는 것은 자연스러운 현상이다.)

자 이제 부터 Cold Start 를 위해서는 이 방법을 쓰면 좋다. 더 이상 시스템 재시작이나 메모리 과할당을 사용할 필요가 없다. 그럼 왜 Cacheset Clear 만으로 안되는지 살펴보자.

Windows Cache System with Memory Mapped File

먼저 윈도우의 파일 I/O 요청이 어떻게 동작하는지 Windows Internals 에 있는 도표를 통해 살펴보자. (Windows Internals 5th Edition, Chapter 10 Cache Manager, Figure 10-10)

간단히 정리하면 윈도우의 파일 I/O 요청은 다음과 같은 순서로 수행된다.

• File I/O 요청이 들어오면 파일 시스템 드라이버가 캐시 매니저에게 데이터를 요청한다.
• 캐시 매니저 그 요청을 받아서 보고 있는 데이터면 주고 없으면 메모리 매니저에게 데이터를 요청한다. (빨간색 상자)
• 메모리 매니저는 Memory Mapped File 로 파일과 메모리를 연결해 I/O 요청을 수행한다. (파란색 상자)

여기서 Cacheset 이 처리하는 부분은 캐시 매니저의 워킹셋 메모리다. (엄밀히 말하면 시스템 워킹셋이다) 이것만으로 캐시가 다 지워지지 않는 것은 메모리 매니저의 Standby 메모리 때문이다. Standby 는 또 뭔가?

메모리 매니저가 캐시 매니저에게 파일에 대한 요청을 받으면 이를 Memory Mapped File 로 메모리를 할당해 I/O 요청을 처리하도록 해준다. I/O 작업이 끝나서 더 이상 필요 없을 때 메모리 해제 요청을 하면 메모리 매니저는 이를 해제하면서 이 메모리 영역을 Standby 상태로 만들고 그냥 내버려 둔다. 이 상태에서는 실제 소유권이 있지 않아 다른 프로세스가 메모리가 필요하다고 요청을 하면 재깍 초기화 해서 넘겨준다. 하지만 메모리가 여유가 있는 상태라면 Standby 상태로 계속 메모리에 남아있게 된다. 이 때 캐시 매니저가 동일한 파일을 달라고 하면 디스크에서 얻어오는게 아니라 Standby 메모리를 바로 넘겨준다. 일종의 2차 캐시 역할을 하는 셈이다.

때문에 Cacheset Clear 를 아무리 해도 이 Standby 메모리 영역에 남아 있는 캐시 데이터가 있어서 캐시를 완전하게 비울 수 없던 것이다.

Rammap 을 사용하면 어떤 파일이 Standby 상태로 메모리에 올라와 있는지 볼 수 있다.

이런 이유로 Cache 워킹셋을 비우고 Standby 메모리도 비워야 캐시가 완전히 빈 상태를 만들 수 있는 것이다.

구현

이제 마지막으로 이 기능들은 실제 어떻게 구현되어 있을까? OS 가 제공하는 특정 API 를 사용할 것 같은데 간단히 살펴보자.

Cacheset 의 Clear 기능은 Sysinternal 의 Cacheset 소개 페이지의 How It Works 부분을 보면 어떻게 구현했는지 설명이 되어 있다. 아래 소스처럼 (문서화되지 않은) NtSetSystemInformation 함수를 사용해 FileCache 의 WorkingSet 크기를 조절한다. (최소소, 최대 값을 모두 -1 을 넣으면 Clear 로 동작한다.)

SYSTEM_FILECACHE_INFORMATION i;
ZeroMemory(&info, sizeof(i));
i.MinimumWorkingSet = -1;
i.MaximumWorkingSet = -1;
NtSetSystemInformation(
  SystemFileCacheInformation,   // 21
  &i, 
  sizeof(i));

Rammap 의 Empty Standby Memory 기능 구현에 대해서는 설명이 없어 Rammap 의 디스어셈블을 통해 살펴보았다. 마찬가지로 NtSetSystemInformation 을 사용하는데 다음과 같이 구현되어 있었다.

SYSTEM_MEMORY_LIST_COMMAND c = MemoryPurgeStandbyList; // 4
NtSetSystemInformation(
  SystemMemoryListInformation,  // 80
  &c, 
  sizeof(c));

어떻게 구현되는지 안김에 콘솔 유틸리티로 구현해보았다. 위 코드에 프로세스 권한 토큰 제어만 추가하면 손쉽게 만들 수 있다. (FlushFileCache)

결론

Windows Vista 이후로는 간단히 유틸리티를 사용해 Cold Start 환경을 만들어 낼 수 있다. 자주 필요한 기능은 아니지만 좀 더 편해져서 좋다!

다음은 Windows 7 부터 추가된 리소스 매니저의 모습이다. (참고로 작업 관리자와 리소스 매니저에 표시되는 값의 의미는 Measuring memory usage in Windows 7 에 잘 정리되어 있다.)

한글판와 영문판을 위/아래로 붙여봤는데 Modified 가 수정한 날짜, Standby 가 대기 모드로 번역된 한글판 윈도우가 참 인상적이다. :)

Radix Tree 를 이용한 정적 문자열 테이블 탐색

텍스트 문서에서 문자열을 읽어 이 문자열에 해당하는 숫자를 찾아 반환하는 코드를 만드는 일이 가끔씩 있다. 예를 들면 다음과 같은 함수를 들 수 있다.

 int parse(const char* s) {
  return
    s == "apple" -> 1
    s == "apps" -> 2
    s == "bana" -> 3
    s == "banana" -> 4
    else -> -1
}

이 함수가 하는 일을 일반화 하면 "고정된 문자열 -> 값 테이블"에서 주어진 문자열에 해당하는 값을 찾는 일이라고 볼 수 있다. Enum 타입의 멤버 이름 -> 상수를 매핑하는 작업도 이에 해당한다.

이런 작업은 동적인 테이블과 마찬가지로 다음과 같은 방법을 쓸 수 있다.

• 문자열 키로 정렬되어 있는 배열에서 이진 탐색
• std::map<string, T>.find
• std::unordered_map<string, T, hash<string>>.find

모두 좋은 방법이지만 정적인 테이블이라는 특성을 활용해보면 어떨까 하는 생각에 Radix Tree 를 이용해 문자열 탐색을 하는 코드를 작성해 보았다.

Radix Tree

먼저 위에서 예로 들었던 문자열 테이블을 Prefix Tree 로 표현해보면 다음과 같다. (Prefix Tree 는 테이블의 문자열을 받아들이는 DFA 와 비슷하게 생겼다.)

구성한 Prefix Tree 에서 자식이 1개인 노드들을 합쳐서 하나의 노드로 줄이면 다음과 같은  Radix Tree 를 만들 수 있다.

Radix Tree 로 바로 코드를 만들 수 있는데 하기 전에 Radix Tree 를 살짝 변형해보자. "노드 분기는 문자로만 한다." 라는 제약을 만족시키는 Radix Tree 는 다음과 같다.

문자로만 분기를 허용하는 이유는 switch 문을 사용하기 위해서다. 이제 얻어진 수정된 Radix Tree 를 가지고 parse 문을 만들어 보자.

코드 생성

만든 Radix Tree 는 간단하게 구조화 된 코드로 변환할 수 있다. 아래와 같은 단순한 룰로 parse 코드를 생성할 수 있다.

• 문자 분기는 switch 문으로 비교 분기
• 문자열 확인은 str[n]cmp 함수 사용
• 하위 노드로 진입할 때 코드 블럭 열기
• 마지막 노드까지 진입했으면 해당 값을 return
  노드에서 분기/비교에 실패할 때는 -1 을 return

생성 룰을 통해 앞서 구성한 Radix Tree 로 부터 다음과 같은 코드를 만들 수 있다.

int parse(const char* s) {
  switch (s[0]) {
  case 'a': if (!strncmp(s+1, "pp", 2))
    switch (s[3]) {
    case 'l': if (!strcmp(s+4, "e")) return 1; else return -1;
    case 's': if (s[4] == 0) return 2; else return -1;
    default: return -1;
    }
    else return -1;
  case 'b': if (!strncmp(s+1, "ana", 3))
    switch (s[4]) {
    case 0: return 3;
    case 'n': if (!strcmp(s+5, "a")) return 4; else return -1;
    default: return -1;
    }
    else return -1;
  default: return -1;
  }
}

길이 분기가 추가된 코드 생성

위 코드에서 str[n]cmp 대신 memcmp 를 써보자. memcmp 가 str[n]cmp 보다 컴파일러에 의한 최적화될 여지가 많기 때문이다. 하지만 위 parse 함수는 당장 memcmp 를 사용할 수 없다. 문자열 s 의 길이를 알 수 없기 때문이다.

이를 해결하기 위해 맨 처음 단계에 입력받은 문자열의 길이를 확인해 분기하는 단계를 넣어보자. 앞서 생성한 Redix Tree 의 처음 부분에 길이를 확인하는 단계가 추가된다. 또한 길이 확인이 되었으므로 마지막 단계에 있었던 null 문자 확인 단계가 제거된다. 길이 분기가 추가된 Tree 는 다음과 같다.

이 Tree 로 부터 코드 생성 룰은 앞서 만든 것과 유사하다. str[n]cmp 대신 memcmp 를 사용하고 첫 분기에 문자열 길이를 확인 하는 정도다. 이 룰에 따라 코드를 만들면 다음과 같다.

int parse(const char* s, size_t len) {
  switch (len) {
  case 4:
    switch (s[0]) {
    case 'a': if (!memcmp(s+1, "pps", 3)) return 2; else return -1;
    case 'b': if (!memcmp(s+1, "ana", 3)) return 3; else return -1;
    default: return -1;
    }
  case 5: if (!memcmp(s+0, "apple", 5)) return 1; else return -1;
  case 6: if (!memcmp(s+0, "banana", 6)) return 4; else return -1;
  default: return -1;
  }
}

여기서 입력 문자열 s의 길이 len을 함수 인자로 추가했다. parse 함수 안에서 strlen 으로 길이를 구하지 않는 이유는 함수 호출 전에 이미 len 을 알고 있는 경우가 많기 때문이다. 예를 들어 전체 텍스트에서 delimiter 에 의해 구분된 문자열을 입력으로 받는 경우 이미 delimiter 에 의해 길이를 알 수 있고 애초에 std::basic_string 과 같이 길이를 사전에 알고 있는 클래스를 사용할수도 있기 때문이다.

참고로 주어진 테이블 데이터를 파싱하는 함수를 만드는 소스는 python 으로 만들었으며 RadixMaker 에 올려두었다.

성능 측정

테스트 데이터는 다음과 같이 총 3가지를 대상으로 했다.

• D-4: 앞서 예로든 데이터. (apple, apps, bana, banana)
• D-16: 기본 16 컬러 값의 영문 이름. (silver, gray, ..., yellow, cyan)
• D-118: 화학 원소 이름. (Hydrogen, Helium, ..., Ununseptium, Ununoctium)

테스트 알고리즘은 다음과 같이 총 8가지를 대상으로 했다.

• strlen: 주어진 문자열의 길이만 측정하는 baseline 측정용 알고리즘
• sorted_vector: 정렬된 std::vector에 대해 std::lower_bound 를 이용한 이진 탐색 알고리즘
• map: std::map 의 find 탐색 알고리즘
• unordered_map: std::unordered_map 의 find 탐색 알고리즘 (hash function: sdbm)
• static: Radix Tree 에 대해 코드 생성된 탐색 알고리즘
• static_len: static 에 길이 분기가 추가된 알고리즘
• dynamic: Radix Tree 에 대한 코드 생성이 아닌 일반 탐색 알고리즘 
• dynamic_len: dynamic 에 길이 분기가 추가된 알고리즘

테스트 환경은 다음과 같다.

• CPU: Intel Core i5-3550 3.3GHz
• OS: Windows 7 Pro SP1
• Compiler / Build: Visual C++ 10 / Builtin Release

테스트는 다음과 같이 했다.

• 데이터에 포함된 문자열을 순서대로 탐색을 해 걸린 시간을 평균냄.
  따라서 항상 탐색이 성공하는 경우만을 대상으로 한다.

측정 결과는 다음과 같다. 걸린 시간의 단위는 µs.

결과 해석

• 데이터를 보면 Radix Tree 를 구현한 static, dynamic 모두 괜찮은 성능을 보인다. 
• 길이 분기가 추가된 Radix Tree 인 static_len, dynamic_len 의 속도가 그렇지 않은 static, dynamic 보다 빠르다. memcmp 최적화가 잘 됨을 알 수 있다.
• 코드 생성을 기반으로 한 static_len 의 속도가 상당히 빠른데 D-4, D-16 데이터의 경우 strlen 보다 빠른 것을 알 수 있다.
• 코드 생성인 static, static_len 은 D-118 과 같이 큰 테이블에서는 상대적으로 성능이 떨어지는 것을 볼 수 있다. 이는 데이터에 비례해 코드 양이 늘어나기 때문에 발생하는 것으로 추정된다.
• unordered_map 은 map 보다 항상 느린 것을 알 수 있다. 데이터가 충분히 크지 않으면 map 이 문자열 탐색에서는 성능 우위가 있음을 알 수 있다.
• sorted_vector 는 기본적으로 map 과 동일한 성능을 보여야 하는데 생각보다 느리게 나왔다. 이는 컴파일러가 map find 코드를 좀 더 잘 최적화해 줘서 인것으로 보인다. Debug 빌드에서는 sorted_vector 가 좀 더 나은 성능을 보인다.

변형된 테스트를 한 번 더 했다.

• D-118 데이터에 포함된 문자열을 하나만 잡고 그것만 탐색을 해 걸린 시간을 평균냄.

측정 결과는 다음과 같다. 걸린 시간의 단위는 µs.

결과 해석

• 대부분 앞선 테스트와 이번 테스트의 결과가 비슷하다. 이는 입력 데이터가 어떤 패턴을 보여도 비슷한 성능을 보임을 의미한다.
• 단 static 과 static_len 은 드라마틱하게 빨라지는 것을 볼 수 있다. 이는 특정 path 로만 parse 함수가 실행되고 CPU 에 의해 분기 예측이 잘 맞아 떨어지는 경우가 많기 때문으로 보인다.

결론

고정된 문자열 테이블에서 문자열을 탐색하는 함수를 Radix Tree 를 이용한 코드 생성으로 구현해 보았다. 기대보다 빠른 성능을 보여 빠른 성능이 필요한 부분에 쓸만한 것으로 보인다. 특히 다음과 같은 조건 아래에서 성능이 좋게 나오니 참고하면 좋을듯.

• 테이블의 크기가 크지 않은 경우. (n < 100)
• 테이블의 크기가 큰 경우라도 입력 문자열의 분포가 편향된 경우.

가독성이나 유지보수성은 일반 컨테이너 클래스를 사용한 탐색에 비해 떨어지니 꼭 필요한 곳에만 쓸 것.