한양과학기술고등학교

에듀테크 프로젝트 대시보드

rsync 알고리즘 (델타 동기화)

rsync 알고리즘 (델타 동기화)

10MB짜리 발표 자료에서 제목 한 줄만 고쳤는데 클라우드가 파일 전체를 다시 올린다면 억울하다. rsync는 받는 쪽이 이미 가진 옛 파일을 블록으로 잘라 체크섬 목록을 만들어 보내고, 보내는 쪽은 새 파일 위로 창(window)을 1바이트씩 밀며 "이 조각, 너 이미 갖고 있지?"를 확인한다. 이미 있는 조각은 번호만, 처음 보는 조각은 내용 그대로 보낸다. 핵심은 롤링 체크섬 — 창을 한 칸 밀 때 O(1)로 갱신되는 약한 해시다.

1. 옛 파일 → 새 파일, 무엇을 전송할까

아래 옛 파일(받는 쪽이 이미 보유)과 새 파일(보내는 쪽의 최신본)을 자유롭게 고쳐 보자. 초록 = 옛 파일에서 재사용한 블록(번호만 전송), 주황 = 그대로 보낸 새 바이트. 공백은 · 로 표시한다.

6
receiver가 만든 옛 파일 블록 + 체크섬 목록 (초록 = 새 파일에서 재사용됨)
sender가 실제로 만들어 보내는 지시서(instruction stream)

2. 롤링 체크섬 — 창을 한 칸 밀 때 O(1) 갱신

새 파일의 모든 위치에서 블록 체크섬을 처음부터 다시 더하면 O(n×블록크기)로 느리다. rsync의 약한 체크섬(Adler 계열)은 맨 앞 바이트를 빼고 새 바이트를 더하는 뺄셈·덧셈 두 번이면 끝난다. «Prev / Next»로 창을 밀어 보자.

두 단계 체크: 약한 체크섬이 우연히 같을 수 있으므로(해시 충돌), 약한 값이 맞으면 그때만 강한 체크섬(MD5/BLAKE 계열)을 계산해 진짜 같은지 확인한다. 약한 건 빠르게 거르고, 강한 건 어쩌다 한 번만 — 블룸 필터와 같은 아이디어다.

3. 전체 흐름 4단계

① 블록 분할 (receiver)

옛 파일을 크기 S 블록으로 자르고, 각 블록의 약한+강한 체크섬을 계산해 sender에게 보낸다.

② 해시 테이블 (sender)

받은 체크섬들을 약한 값 → 블록 목록 해시 테이블에 넣는다. 조회 O(1).

③ 롤링 검색 (sender)

새 파일 위로 창을 1바이트씩 민다. 약한 체크섬이 테이블에 있으면 강한 체크섬으로 확인. 맞으면 블록 번호를 기록하고 창을 S칸 점프, 아니면 앞 바이트를 literal로 모은다.

④ 재조립 (receiver)

지시서를 읽어 COPY는 자기 옛 파일에서 복사, LITERAL은 받은 바이트를 이어 붙여 새 파일을 완성한다.

4. 롤링 검색 핵심 코드 (의사 코드)

# receiver: 옛 파일을 S바이트 블록으로 → {약한체크섬: [(강한체크섬, 블록번호)]} table = {} for i in range(0, len(old), S): blk = old[i:i+S] table.setdefault(weak(blk), []).append((strong(blk), i // S)) # sender: 새 파일 위로 창을 1바이트씩 민다 out, lit, a, b = [], b"", *weak_init(new[0:S]) i = 0 while i < len(new): w = (a + M*b) & 0xffffffff hit = None for (sh, idx) in table.get(w, []): # 약한 체크섬 일치? if sh == strong(new[i:i+S]): # 강한 체크섬까지 확인 hit = idx; break if hit is not None: if lit: out.append(("LIT", lit)); lit = b"" out.append(("COPY", hit)) # 번호만 전송 i += S; a, b = weak_init(new[i:i+S]) # 창을 S칸 점프 else: lit += new[i:i+1] # 처음 보는 바이트 a = (a - new[i] + new[i+S]) % M # ← 롤링: 뺄셈+덧셈 O(1) b = (b - S*new[i] + a) % M i += 1 if lit: out.append(("LIT", lit))
실제 rsync는 여기에 더해 — 전송 중 데이터를 zlib으로 압축, SSH 위에서 동작, 디렉터리 전체를 재귀 순회, 소유자/권한/타임스탬프 보존, --delete 로 사라진 파일 정리까지 한다. 같은 델타 아이디어가 Dropbox 파일 동기화, 게임 패치, git의 packfile, 증분 백업에 두루 쓰인다.