파일 맨 앞에 단 한 바이트만 추가해도 그 뒤의 모든 블록이 밀려버리는 구조라면, 아무리 내용이 99% 똑같은 파일이라도 중복제거는 무용지물이 돼요. 2001년 10월 MIT와 NYU 연구진 Athicha Muthitacharoen, Benjie Chen, David Mazières가 SOSP에서 발표한 LBFS(A Low-bandwidth Network File System) 논문은 바로 이 문제를 정면으로 다뤘어요. 그렇다면 파일을 내용 기준으로 잘라내는 콘텐츠 정의 청킹(Content-Defined Chunking)은 정확히 어떤 원리로 중복제거 효율을 끌어올릴까요?
LBFS 논문은 어떤 문제를 풀려고 했나?
LBFS는 저대역폭 네트워크에서도 실용적으로 쓸 수 있는 네트워크 파일 시스템을 만들기 위해 설계된 연구예요. 논문 저자들은 사람들이 느린 네트워크에서 원격 파일 시스템 대신 원격 로그인(SSH)이나 로컬 사본 편집에 의존하는 현실을 지적하면서, 파일이나 그 이전 버전들 사이에 존재하는 데이터 유사성(cross-file similarity)을 찾아내 이미 전송된 적 있는 데이터는 다시 보내지 않는 방식으로 문제를 풀었어요. 논문은 이 기법과 압축·캐싱을 함께 쓰면 일반적인 작업 부하에서 기존 네트워크 파일 시스템 대비 대역폭을 한 자릿수 넘게(over an order of magnitude) 줄일 수 있다고 밝혔어요. 이 절감의 핵심 엔진이 바로 파일을 청크 단위로 쪼개고 해시로 인덱싱하는 청킹 알고리즘이었어요.
고정 크기 청킹은 왜 실패할까?
고정 크기 청킹은 파일을 처음부터 균일한 바이트 수 단위로 자르기 때문에, 파일 맨 앞부분에 데이터가 삽입되거나 삭제되는 순간 그 뒤 모든 블록의 경계가 통째로 밀려버려요. 논문은 이 문제를 “단 1바이트를 파일 맨 앞에 삽입해도 모든 블록의 해시가 바뀌어버려서 잠재적인 대역폭 절감 효과를 완전히 무력화한다”고 설명해요. 두 파일을 동시에 비교하며 고정 크기 블록을 매칭하는 rsync 알고리즘도 이 문제를 어느 정도 완화하긴 하지만, LBFS는 아예 접근 방식을 다르게 가져가요 — 파일 하나만 보고도 내용 자체에서 경계를 결정하기 때문에 두 파일을 동시에 비교할 필요가 없고, 여러 파일에 흩어진 청크까지도 재사용할 수 있어요. 이 차이는 두 파일의 델타를 실시간으로 계산하는 rsync 알고리즘의 델타 전송 방식과 비교해보면 더 뚜렷하게 드러나요.
Rabin fingerprint 롤링 해시로 청크 경계는 어떻게 정해질까?
LBFS는 파일의 모든 겹치는(overlapping) 48바이트 구간마다 Rabin fingerprint를 계산해서, 그 값이 미리 정한 조건을 만족하는 지점을 청크 경계(breakpoint)로 삼아요. Rabin fingerprint는 해당 구간의 데이터를 미리 정한 기약다항식(irreducible polynomial)으로 나눈 나머지로 표현되는 다항식 해시인데, 슬라이딩 윈도우 위에서 효율적으로 계산할 수 있다는 특성 때문에 선택됐어요. LBFS는 이 fingerprint의 하위 13비트가 특정 값과 일치하면 그 지점을 breakpoint로 지정했고, 그 결과 무작위 데이터를 가정했을 때 기대 청크 크기는 2¹³ = 8,192바이트(약 8KB)가 돼요. 실제 병리적 상황(청크가 지나치게 작거나 커지는 경우)을 막기 위해 최소 청크 크기는 2KB, 최대는 64KB로 강제했고, 실험에서 사용한 /usr/local 디렉터리(354MB, 10,702개 파일)를 분석한 결과 42,466개 청크가 생성됐고 청크 크기의 중앙값은 5.8KB, 평균은 8,570바이트로 이론값 8,240바이트에 근접했어요. 이렇게 경계가 파일 내 절대 위치가 아니라 그 지점 직전 48바이트의 내용에만 의존하기 때문에, 파일 앞부분이 바뀌어도 나머지 청크들은 흔들리지 않고 그대로 남아요.
청크는 어떻게 식별되고 재사용될까?
LBFS는 각 청크를 SHA-1 해시값의 상위 64비트로 인덱싱해서 클라이언트와 서버가 각자 청크 데이터베이스를 유지해요. 파일을 전송할 때는 먼저 GETHASH RPC로 청크들의 해시 목록만 주고받고, 수신 측이 이미 갖고 있는 해시라면 실제 데이터는 전송하지 않고 CONDWRITE로 해시만 보내 서버가 로컬에 있는 데이터로 채우도록 해요. 해시가 없는 경우에만 TMPWRITE로 실제 바이트를 전송하는 구조라, 두 버전의 파일이 상당 부분 겹친다면 실제로 오가는 데이터는 바뀐 청크뿐이에요. 흥미로운 점은 LBFS가 데이터베이스의 정합성을 아예 신뢰하지 않는다는 거예요 — 청크를 실제로 사용하기 전에 항상 SHA-1을 재계산해서 검증하기 때문에, 데이터베이스가 손상돼도 최악의 경우 성능이 떨어질 뿐 데이터 무결성은 깨지지 않아요.
실제로 얼마나 절약됐을까?
LBFS 논문 실험에서 emacs 20.6 소스 트리를 이미 갖고 있는 클라이언트가 52.1MB 크기의 emacs 20.7 소스 트리를 받을 때, 실제로 전송해야 했던 데이터는 12.6MB뿐이었습니다 — 두 버전 사이에 76%의 청크가 겹쳤기 때문이에요. gcc로 emacs를 다시 컴파일하는 워크로드, Microsoft Word 문서를 편집하는 워크로드, ed 편집기로 perl 소스를 변환하는 워크로드까지 세 가지 실전 시나리오에서 LBFS는 CIFS나 NFS 같은 기존 네트워크 파일 시스템 대비 눈에 띄게 적은 대역폭을 소비했다는 게 논문의 결론이에요. 물론 청크를 잘게 나눈다고 무조건 좋은 건 아니었는데, 청크 크기를 8KB에서 2KB로 줄이면 공유되는 데이터 비율은 소폭(17.01% → 21.33%) 늘었지만 그만큼 청크 개수가 늘어나 GETHASH·CONDWRITE 통신 오버헤드도 함께 커져서, 저자들은 이 트레이드오프가 실익보다 손해가 크다고 판단했어요.
restic은 이 아이디어를 실제 백업 도구에 어떻게 적용했을까?
restic은 공식 문서에서 밝히듯 LBFS와 같은 원리인 Rabin fingerprint 기반 롤링 해시로 콘텐츠 정의 청킹을 구현하지만, 파라미터는 백업 도구라는 용도에 맞게 다시 조정했어요. restic은 64바이트 슬라이딩 윈도우로 fingerprint를 계산하면서 그 값의 하위 21비트가 모두 0인 지점을 청크 경계로 잡고, 512KiB 미만의 작은 파일은 아예 쪼개지 않으며, 청크 크기는 512KiB에서 8MiB 사이(평균 목표 1MiB)로 LBFS의 8KB보다 훨씬 크게 잡혀 있어요. 이건 LBFS가 인터랙티브한 파일 접근 지연을 최소화하는 게 목표였던 반면, restic은 수십~수백 GB 규모 백업 저장소에서 청크 인덱스 자체의 크기와 조회 오버헤드를 억제하는 게 더 중요하기 때문이에요. 또 하나 눈여겨볼 부분은 보안이에요 — restic은 저장소를 초기화할 때마다 청킹에 쓸 기약다항식을 무작위로 골라 config 파일에 저장해두는데, 이렇게 하면 공격자가 특정 바이트 패턴을 미리 심어서 청크 경계를 예측·조작하는 워터마크 공격(watermark attack)을 훨씬 어렵게 만들 수 있어요. restic과 Duplicati를 비교한 글에서 다뤘듯 restic이 매번 전체 백업을 돌려도 실제로는 바뀐 데이터만 저장소에 쌓이는 이유가 바로 이 청킹 구조 덕분이에요.
콘텐츠 정의 청킹이 홈랩 백업 전략에 주는 실전 의미
콘텐츠 정의 청킹을 쓰는 백업 도구는 파일 앞부분에 로그 한 줄이 추가되거나 문서 맨 앞에 문단 하나가 끼어드는 흔한 변경에도 나머지 청크는 그대로 재사용하기 때문에, 매일 반복되는 백업에서 실제로 새로 저장되는 데이터량과 백업 저장소가 차지하는 용량을 크게 줄여줘요. rclone으로 클라우드 저장소에 동기화하는 것과 restic처럼 청크 단위로 중복을 제거하며 백업하는 것은 목적 자체가 다른데, 전자는 파일을 있는 그대로 복제하는 데 초점이 있고 후자는 시점별 스냅샷을 최소한의 저장 공간으로 오래 보관하는 데 초점이 있어요. 여러 백업·동기화 도구가 어떤 트레이드오프를 갖는지는 동기화·백업 도구 비교 글에서, 여러 기기가 충돌 없이 상태를 합의하는 CRDT 같은 또 다른 분산 데이터 구조 원리는 CRDT 논문 리뷰에서 이어서 다루고 있으니 함께 참고할 만해요.
결론
LBFS 논문이 2001년에 제시한 통찰 — 파일을 절대 위치가 아니라 내용 자체의 패턴으로 잘라야 앞부분의 작은 변경이 뒤쪽 청크 경계를 흔들지 않는다는 원리 — 은 20년이 훨씬 지난 지금도 restic을 비롯한 현대 백업 도구의 핵심 설계로 그대로 이어지고 있어요. 홈랩에서 매일 백업을 돌리면서 “왜 restic은 매번 전체 스캔을 해도 저장 공간이 크게 늘지 않을까”라는 질문을 품어본 적이 있다면, 그 답은 결국 롤링 해시 하나로 파일 어디를 잘라야 할지 스스로 판단하는 이 청킹 알고리즘에 있었던 셈이에요.
자주 묻는 질문
Q1. 콘텐츠 정의 청킹(Content-Defined Chunking)이 뭔가요?
콘텐츠 정의 청킹은 파일을 고정된 바이트 수가 아니라 데이터 내용 자체에서 나타나는 패턴을 기준으로 가변 길이 조각(청크)으로 나누는 방식이에요.
Q2. LBFS 논문은 언제, 누가 발표했나요?
LBFS는 Athicha Muthitacharoen, Benjie Chen, David Mazières가 MIT와 NYU 소속으로 2001년 10월 SOSP(ACM Symposium on Operating Systems Principles)에서 발표한 논문이에요.
Q3. 고정 크기 청킹은 왜 문제가 되나요?
파일 맨 앞에 바이트 하나만 추가되거나 삭제돼도 그 뒤의 모든 고정 크기 블록 경계가 밀려서, 실제로는 내용이 거의 그대로인 파일도 전혀 다른 블록들의 나열로 바뀌어버리기 때문이에요.
Q4. Rabin fingerprint는 어떤 역할을 하나요?
Rabin fingerprint는 파일의 48바이트 슬라이딩 윈도우마다 다항식 기반 해시값을 굴려가며 계산해서, 그 값이 특정 조건을 만족하는 지점을 청크 경계(breakpoint)로 정하는 데 쓰여요.
Q5. restic도 LBFS와 똑같은 방식으로 청킹하나요?
아니요, restic도 Rabin fingerprint 기반 롤링 해시로 콘텐츠 정의 청킹을 한다는 원리는 같지만, 윈도우 크기·청크 크기·워터마크 공격 방어를 위한 무작위 다항식 선택 등 백업 도구 용도에 맞게 파라미터를 다르게 조정했어요.
Q6. 청크 크기를 작게 나눌수록 무조건 유리한가요?
아니요, LBFS 논문 실험에서도 청크를 2KB로 잘게 나누면 공유되는 데이터 비율은 소폭 늘지만 청크 개수가 늘어난 만큼 인덱스 조회와 통신 오버헤드도 함께 커져서, 실제 절감 효과가 상쇄되는 경우가 많았어요.
관련 글
