1996년 6월, 호주국립대학교(ANU) 컴퓨터과학과에서 앤드류 트리젤(Andrew Tridgell)과 폴 매커라스(Paul Mackerras)가 “The rsync algorithm”이라는 제목의 기술보고서(TR-CS-96-05)를 냈어요. 저대역폭·고지연 회선으로 두 파일을 동일하게 맞추면서도, 파일 전체를 전송하지 않고 단 한 번의 왕복(round trip)만으로 차이 나는 부분만 찾아 전송하는 방법을 다룬 문서예요. 30년 가까이 지난 지금도 rsync, 그리고 이후 나온 여러 동기화 도구가 이 아이디어의 변형을 쓰고 있는데, 이 롤링 체크섬 알고리즘이 실제로 어떻게 변경분만 골라내는 걸까요?
rsync 알고리즘이 푸는 문제는 정확히 뭘까?
rsync 알고리즘은 한쪽 컴퓨터에 있는 파일을 다른 쪽 컴퓨터에 있는 파일과 동일하게 맞추되, 두 파일을 같은 장소에 모으지 않고도 차이만 계산해서 전송하는 방법이에요. 논문은 이 상황을 컴퓨터 α(최신 버전을 가진 쪽)와 컴퓨터 β(구버전 파일을 가진 쪽)로 나눠서 설명하는데, 목표는 β가 가진 구버전 파일을 최대한 재사용하면서 α의 최신 파일을 β 쪽에 재구성하는 거예요. 두 파일을 통째로 비교하려면 둘 다 같은 위치에 있어야 하지만, rsync는 네트워크로 연결된 서로 다른 두 컴퓨터 사이에서 이 문제를 풀어야 하니 일반적인 diff와는 접근 자체가 달라야 했어요.
알고리즘의 뼈대: 블록으로 쪼개고 체크섬으로 대조한다
이 알고리즘은 목적지 파일을 겹치지 않는 고정 크기 블록(S바이트)으로 나눈 뒤, 각 블록의 체크섬만으로 원본 파일 전체를 스캔해 일치하는 부분을 찾아내는 방식으로 동작해요. 구체적으로는 구버전 파일을 가진 β가 파일을 S바이트짜리 블록으로 나누고(마지막 블록만 S바이트보다 짧을 수 있어요), 각 블록마다 32비트 약한 체크섬과 128비트 MD4 강한 체크섬 두 가지를 계산해 α에게 보내요. 그러면 최신 파일을 가진 α는 이 체크섬 목록만으로 자기 파일 전체를 한 바이트씩 밀어가며 스캔해서, β의 어떤 블록과 일치하는 S바이트 구간이 있는지 찾아요. 일치하는 구간을 찾으면 “β의 몇 번째 블록을 그대로 써라”는 참조로 대체하고, 일치하지 않는 나머지 바이트만 실제 데이터(리터럴)로 β에 전송하죠. 결과적으로 β는 이 명령어 시퀀스(블록 참조 + 리터럴 데이터)만 받아서 α의 최신 파일을 그대로 재구성할 수 있어요.
왜 하필 롤링 체크섬이어야 했을까?
롤링 체크섬은 버퍼가 한 바이트 밀릴 때 전체를 다시 계산하지 않고, 빠지는 바이트와 새로 들어오는 바이트 값만으로 다음 위치의 체크섬을 즉시 구할 수 있는 체크섬이에요. 문제는 α가 β의 블록과 일치하는 구간을 찾으려면 자기 파일의 모든 오프셋(0바이트째부터 시작하는 S바이트, 1바이트째부터 시작하는 S바이트, 2바이트째부터…)에서 체크섬을 계산해야 한다는 점이었어요. 블록이 정렬돼 있지 않고 파일 중간 아무 위치에서나 시작할 수 있다 보니, 매 오프셋마다 체크섬을 처음부터 새로 계산하면 계산량이 파일 크기에 비례해 폭발해버려요.
논문은 이 문제를 마크 애들러(Mark Adler)의 adler-32 체크섬에서 영감을 받은 약한 체크섬으로 풀었어요. 블록의 시작 위치를 k, 끝 위치를 l이라 할 때, 두 개의 합 a(k,l) = (Σ Xᵢ) mod M과 b(k,l) = (Σ (l-i+1)Xᵢ) mod M을 구해 s(k,l) = a(k,l) + 2¹⁶ b(k,l)로 32비트 체크섬을 만들어요(M = 2¹⁶). 여기서 핵심은 순환 관계식이에요. a(k+1,l+1) = a(k,l) - X_k + X_{l+1}, b(k+1,l+1) = b(k,l) - (l-k+1)X_k + a(k,l+1) 형태로, 앞서 계산해둔 값에 빠진 바이트와 새로 들어온 바이트만 더하고 빼면 다음 오프셋의 체크섬이 바로 나와요. 덕분에 α는 파일 전체를 단 한 번만 훑으면서도 모든 오프셋에서의 체크섬을 사실상 상수 시간에 계산할 수 있고, 이게 바로 변경분만 골라내는 계산을 파일 크기에 비례하는 부담 없이 끝낼 수 있는 이유예요.
약한 체크섬 하나로는 부족한 이유
32비트 약한 체크섬만으로 블록이 일치한다고 판단하면 서로 다른 데이터가 우연히 같은 체크섬 값을 내는 충돌이 실무에서 무시할 수 없는 빈도로 발생해요. 그래서 논문은 3단계 검색 절차를 제안해요. 먼저 β가 보낸 각 블록의 32비트 약한 체크섬을 16비트로 해시해 2¹⁶ 크기의 해시 테이블에 채워두고, α는 파일을 스캔하며 현재 위치의 약한 체크섬을 같은 방식으로 해시해 테이블에서 후보를 찾아요. 후보가 나오면 32비트 약한 체크섬 값 자체를 비교해 더 좁히고, 여기까지 일치하면 마지막으로 128비트 MD4 강한 체크섬을 계산해 최종 검증해요. 논문은 이 단계에서 약한 체크섬과 MD4가 동시에 일치했는데도 실제로는 다른 데이터일 확률을 “microscopic”(극히 미미함)하다고 표현하는데, 오늘날 rsync는 프로토콜 버전 30부터 기본 강한 체크섬을 MD4에서 MD5로 바꾸고 XXH3 같은 옵션도 추가해 이 검증 단계를 계속 보강해왔어요.
실제로 얼마나 절감됐을까 — 논문의 실험 결과
논문은 리눅스 커널 1.99.10과 2.0.0 버전의 소스 tar 파일(약 24MB, 2,441개 파일 중 291개 변경·19개 삭제·25개 추가)로 이 알고리즘을 검증했어요. 블록 크기를 500바이트로 설정했을 때 46,989번의 블록 매치와 620,013번의 해시 히트가 발생했고, 약한 체크섬과 강한 체크섬이 동시에 일치했지만 실제로는 다른 데이터였던 거짓 알람(false alarm)은 단 64건에 그쳤어요. 최종적으로 실제 전송된 데이터는 약 1.1MB, β 쪽에서 읽어야 했던 데이터는 979KB 수준이었는데, 같은 두 파일을 표준 GNU diff로 비교하면 3만 2천 줄이 넘는 diff 결과(2.1MB)가 나온다는 점과 비교하면 상당한 절감이에요. 논문은 이 과정에 걸린 CPU 시간이 “표준 diff를 두 파일에 돌리는 시간보다 짧았다”고 밝히고 있어요. 여기서 끝이 아니에요 — 이 알고리즘은 여러 파일을 연속으로 처리할 때 한쪽 프로세스는 체크섬을 계속 생성·전송하고 다른 쪽 프로세스는 차이 정보를 받아 파일을 재구성하는 방식으로 파이프라인화해서, 파일 하나마다 매번 왕복을 기다리지 않고도 지연 시간을 줄일 수 있다는 점도 함께 제시해요.
오늘날의 동기화 도구는 이 알고리즘을 어떻게 다루고 있을까?
이 알고리즘이 30년 가까이 실전에서 쓰이고 있지만, 모든 후속 도구가 그대로 채택한 건 아니에요. rclone은 rsync의 철학(원본과 목적지를 동일하게 맞춘다)은 이어받았지만, 클라우드 오브젝트 스토리지 API 특성상 파일 일부만 골라 덮어쓰는 게 까다롭다 보니 기본적으로는 파일을 통째로 전송하고, 대신 여러 파일을 동시에 병렬 업로드해 처리량을 끌어올리는 쪽으로 설계됐어요. 즉 rsync가 “한 파일 안의 변경분을 최소화”하는 데 집중했다면, rclone은 “여러 파일을 동시에 얼마나 빨리 옮기느냐”에 집중한 셈이라 같은 델타 전송 계열로 묶기는 어려워요.
반대로 Syncthing은 한때 이 논문에서 영감을 받은 약한 해시(weak hash) 기반 블록 매칭을 실제로 코드베이스에 갖고 있었어요. 하지만 2024년 관련 PR에서 실측해보니 이 기능으로 절감되는 전송 블록량이 전체 평균 0.8% 수준에 그치는 반면, 매칭을 시도하려면 목적지 파일을 미리 통째로 읽어야 해서 큰 파일일수록 동기화 시작 전에 I/O 위주의 긴 지연이 생기는 데다 약한 해시 계산 자체도 SHA-256 대비 약 2배 느리다는 게 확인됐어요. 개발팀은 “사용자의 99%를 느리게 만들면서 1%도 안 되는 절감을 최적화하고 있었다”고 판단해 결국 이 기능을 제거했는데, 이건 논문의 알고리즘이 틀렸다는 뜻이 아니라 오히려 어떤 워크로드에서 이 트레이드오프가 실제로 이득인지를 실측 없이는 알 수 없다는 걸 보여주는 사례예요. rsync가 다루는 저대역폭·고지연 원격 전송 상황과, Syncthing이 다루는 로컬 네트워크 위주의 실시간 동기화 상황은 대역폭과 I/O 비용의 균형점 자체가 다르기 때문이에요.
결론
트리젤과 매커라스가 1996년에 제시한 롤링 체크섬 + 강한 체크섬 조합은 “파일 전체를 옮기지 않고도 원격지의 두 파일을 동일하게 맞춘다”는 문제를, 순환 관계식으로 계산량을 상수 시간에 묶어낸 약한 체크섬과 오탐을 사실상 없애는 강한 체크섬의 2단 검증으로 풀어낸 결과물이에요. 이 알고리즘은 지금도 rsync 자체에서 현역으로 쓰이고 있지만, rclone처럼 다른 제약 조건(클라우드 API, 병렬성) 아래서는 다른 전략이 선택되기도 하고 Syncthing처럼 한때 도입했다가 실측 결과에 따라 제거되기도 했다는 점에서, 좋은 알고리즘도 어떤 환경에 놓이느냐에 따라 실전에서의 값어치가 크게 달라진다는 걸 보여줘요. 콘텐츠 기반 청킹이나 CRDT 같은 다른 동기화 알고리즘과 비교하며 읽으면, 결국 “무엇을 얼마나 자주 다시 계산할 것인가”라는 같은 질문에 각 알고리즘이 서로 다른 답을 내놓고 있다는 걸 확인할 수 있을 거예요. 이런 델타 전송·동기화 알고리즘들이 실제 백업 도구 선택에서 어떤 트레이드오프로 이어지는지는 동기화·백업 도구 비교 글에서 더 자세히 다뤄요.
참고 자료
- Andrew Tridgell, Paul Mackerras, “The rsync algorithm”, Technical Report TR-CS-96-05, Department of Computer Science, Australian National University, June 1996.
- rsync 공식 저장소, NEWS (프로토콜 버전별 체크섬 변경 이력)
- Syncthing, PR #10005: remove weak hashing which does not pull its weight
자주 묻는 질문
Q1. rsync는 파일이 조금만 바뀌어도 전체를 다시 전송하나요?
아니요, rsync는 목적지 파일을 고정 크기 블록으로 나눠 만든 체크섬 목록을 기준으로 원본 파일을 스캔해서, 이미 일치하는 블록은 재사용하고 달라진 부분만 새로 전송해요.
Q2. 롤링 체크섬이 일반 체크섬과 다른 점이 뭔가요?
일반 체크섬은 버퍼가 한 바이트만 밀려도 전체를 처음부터 다시 계산해야 하지만, 롤링 체크섬은 빠진 바이트와 새로 들어온 바이트 값만으로 다음 위치의 체크섬을 즉시 갱신할 수 있어서 모든 오프셋을 훑어도 계산량이 거의 늘지 않아요.
Q3. 약한 체크섬만으로는 왜 부족한가요?
32비트 롤링 체크섬은 계산은 빠르지만 서로 다른 데이터가 같은 값을 낼 확률(충돌 가능성)이 상대적으로 높기 때문에, 후보를 빠르게 걸러낸 뒤 128비트 MD4/MD5 같은 강한 체크섬으로 한 번 더 검증해야 오탐을 사실상 없앨 수 있어요.
Q4. rclone도 rsync처럼 파일의 바뀐 부분만 전송하나요?
아니요, rclone은 기본적으로 파일을 통째로 전송하는 방식이라서 rsync식 블록 단위 델타 전송과는 접근이 달라요. 대신 여러 파일을 동시에 병렬 전송해 속도를 높이는 쪽에 최적화돼 있어요.
Q5. Syncthing은 지금도 rsync 같은 롤링 체크섬을 쓰나요?
쓰지 않아요. 한때 rsync에서 영감받은 약한 해시(weak hash) 매칭 기능이 있었지만, 절감되는 전송량이 평균 0.8% 수준에 그치는 반면 목적지 파일을 통째로 미리 읽어야 하는 비용이 커서 개발팀이 해당 기능을 코드베이스에서 제거했어요.
Q6. 블록 크기는 클수록 좋은가요, 작을수록 좋은가요?
무조건 좋은 방향은 없어요. 블록이 작을수록 변경분을 더 세밀하게 잡아내 전송량은 줄지만 체크섬 개수와 해시 테이블 검색 비용이 늘고, 블록이 크면 반대로 체크섬 오버헤드는 줄지만 블록 하나에 바이트 하나만 바뀌어도 그 블록 전체를 다시 보내야 해요.
관련 글
