FastCDC - 컨텐츠 기반 분할 알고리즘 소개

2026-08-22

Content Defined Chunking 알고리즘 소개글

최근 팀 내에서 업무를 하면서 한 문제에 대해 고민하고 있었습니다. 저는 회사에서 게임서버를 개발하고 있고, 저희 게임은 DynamoDB에 플레이어 정보를 저장하고 있는데요. 게임 서버 도메인 특성상 쓰기 요청의 비율이 높기 때문에 많은 양의 데이터를 한 레코드에 저장하면 비용이 증가하고 쓰로틀링이 발생하기 쉽습니다.

그래서 미리 정해둔 기준에 따라, 데이터를 여러 레코드에 분할 저장해서 사용하고 있는데요. 이런 과정이 코드에 직접적으로 드러나다 보니 팀원이 코딩 과정에서 번거롭다고 의견을 주었는데요. 이런 불편함을 해결하고자 방법을 찾아보다가 해당 팀원이 2016년 USENIX ATC에서 발표된 FastCDC 논문을 발견했고, 이 친구가 이번 글의 주인공입니다.

INDEX

Content Defined Chunking
FastCDC 알고리즘
마무리

Content Defined Chunking

앞서 사례를 먼저 생각해봅시다. 데이터를 도메인 별로 분할해서 데이터베이스에 저장하는 걸 서버 코드에 드러내지 않고 프레임워크 하위 레이어에 숨길 수 있다면 어떨까요? 서버 코드에서는 게임과 관련된 도메인 로직의 비중을 높이고 하위 레이어에서 동작하는 저수준 행위를 숨길 수 있습니다.

가장 쉽게 생각해볼 수 있는 건 바이트 배열을 고정 크기(Fixed Size Chunking)로 분할해서 저장하는 건데요. 내용이 조금만 바뀌어도 대부분의 파티션에 변경이 필요하기 때문에 빈번한 쓰기 요청이 발생합니다.

원본

1 byte 삽입

비슷한 문제로 클라우드 백업 시스템을 떠올려보죠. 소설가인 유저는 500MB 분량의 워드 파일을 저장한 상황입니다. 고정 크기 분할을 사용한 경우에는 중간에 문장 하나만 추가되어도 전체 파일을 동기화 해야 합니다. 또 다른 예시로는 Docker 이미지 저장소가 있을겁니다.

컨텐츠 기반 분할 (Content Defined Chunking) 의 핵심 아이디어는 분할하려는 컨텐츠 내용에서 특정 패턴에 청킹 바운더리를 결정하는 겁니다. 예를 들어서 ZZ 라는 단어를 발견할 때마다 청킹을 하겠다고 결정했다면, ZZ ~ ZZ 사이에는 내용이 조금 바뀌어도 전체 청크에 영향을 주지 않습니다.

원본

중간 수정

경계는 그대로 유지되고, 수정이 발생한 청크만 달라집니다.

2019년 세계 최대 규모 게임 개발자 컨퍼런스인 GDC에서 구글은 Stadia라는 이름의 클라우드 게임 서비스를 발표합니다. 클라우드 게임이란 사용자가 키보드/마우스 입력을 구글 서버로 전송하면 원격에서 대신 게임을 실행해서 그 결과 화면을 실시간으로 전송하는 서비스입니다. 사용자는 고사양 PC를 가지고 있지 않아도 AAA급 게임을 플레이할 수 있습니다.

비록 Stadia는 2023년 서비스가 종료되었지만, Stadia팀은 FastCDC 알고리즘을 사용해서 고속 데이터 전송 도구를 개발했습니다. 게임은 용량이 큽니다. 제가 플레이하는 원신은 PC에서 대략 100GB 이상의 저장공간을 요구하죠. 만약 게임에 업데이트가 발생할 경우 전체 파일을 다시 동기화 해야하면 매우 비효율적입니다. 리눅스에서는 rsync 라는 증분 동기화 명령어를 제공하지만, 표준 rsync는 고정 크기 분할 fixed-size chunk을 사용하고 있습니다.

구글 CDC-file-transfer 인용 | 빌드 전송 속도가 2x에서 최대 5x빠르다.

FastCDC 알고리즘

FastCDC는 지금은 하얼빈 공업 대학교의 교수인 Wen Xia가 2016년 USENIX ATC 컨퍼런스에서 발표한 알고리즘입니다. 10년이 지난 현재 2026년에는 다른 CDC논문들도 여럿 나왔지만 일단 여기서는 FastCDC만 다뤄봅시다. FastCDC는 기존 CDC 알고리즘와 비교하여 크게 3가지 진전을 이루었습니다.

단순화 및 강화된 해시 판정 : Rabin 기반의 CDC보다 더 빠른 Gear Hash를 사용하면서 해시 판정 구문의 마스크 값에 여러 개의 0비트를 패딩하여 슬라이딩 윈도우 크기를 늘렸스빈다. 연산이 무거운 Rabin과 비교해서 거의 대등한 수준의 높은 중복 제거율을 유지합니다. 또한 해시 판정 구문 자체를 단순화하고 최적화 하면서 CPU 연산 부하를 낮췄습니다.
최소 크기 미만의 청크 컷 포인트 : CDC는 패턴을 찾는 문제이기 때문에 확률적으로 바운더리가 생성되는데요. 그래서 나이브한 구현에서는 아주 작은 청크가 생성될 수 있습니다. 이를 보완하고자 최소 크기를 보장하기 위해 해시 판정을 넘기는 방식을 쓰는데요. 여기엔 청크의 최소 보장 크기에 따라 중복 제거율이 worst case에서 15까지 감소하는 트레이드-오프가 존재합니다.
정규화된 분할 : 기존 CDC구현은 청크가 발생하는 확률을 기하분포로 다루었기 때문에 작은 크기의 청크가 더 많이 생깁니다. FastCDC는 이를 정규화 해서 청크 크기가 어느 정도 정규분포의 모습을 따르도록 했습니다.

① Gear hash

CDC의 핵심 아이디어가 데이터에서 특정 패턴을 청크를 생성하는 경게 조건으로 삼는다고 설명했었죠? FastCDC에서는 Gear hash를 사용합니다. 슬라이딩 윈도우 기법을 사용해서 데이터가 들어올 때마다 일정 구간의 정보를 해시합니다. 해시는 입력값에 영향 받지 않고 결과값이 균등 확률 분포로 나타나야 하기 때문에 미리 정해둔 랜덤 테이블 $G$에서 바이트를 랜덤값으로 변환한 다음 해시에 값을 더합니다. 여기서 fp는 fingerprint의 약자입니다

$$ fp = (fp \lt\lt 1) + G(b) $$

import random

MASK_64 = 0xFFFFFFFFFFFFFFFF
random.seed(42) # 시드값은 고정

G = [random.randint(0, MASK_64) for _ in range(256)]

def gear_hash(fp: int, next_byte: int) -> int:
    """
    fp = (fp << 1) + G[b]
    """
    new_fp = (fp << 1) + G[next_byte]
    return new_fp & MASK_64

아래 그림은 논문에서 보여주는 Gearhash 그림과 기존 연구와 비교해서 FastCDC의 롤링 해시를 만드는 연산이 얼마나 단순하고 빠른지 나타내고 있습니다.

이렇게 생성된 해시를 가지고, 미리 정해둔 비트 마스크와 비교해서 값이 모두 0인 경우를 경계값으로 삼아도 그럭저럭 동작하는 CDC를 만들 수 있습니다.

mask = 0x00000FFF # 평균 4KB 크기마다 경계를 결정하기

n = len(data)
idx = 0
chunks = []

while idx < n:
    chunk_start = idx

    # 남아있는 비트가 N을 초과할 때 그냥 자른다
    if chunk_start + min_size >= n:
        chunks.append(data[chunk_start:])
    
    # 최소 크기 보장
    idx += min_size
    fp = 0
    while idx < n:
        byte = data[idx]
        fp = gear_hash(fp, byte)

        chunk_len = idx - chunk_start + 1
        # 최대 크기 도달 시 컷오프
        if chunk_len >= max_size:
            break
        
        if (fp & mask) == 0:
            idx += 1
            break

        idx += 1

    chunks.append(data[chunk_start:idx])

print(chunks)

위 코드는 0x00000FFF 의 마스크를 가지고 데이터를 비교하기 때문에 마스크를 매 순간 ${1}/{2^{12}}$의 확률로 경계를 잡습니다. 청크 길이 $X$에 대해 기하분포의 기댓값이 $E[X] = \frac{1}{p}$이므로, 따라서 평균 $4KB = 2^{12}$ 크기로 청크가 생성됩니다.

② Enlarging the sliding window size

하지만 이 단순한 구현은 좋은 CDC의 조건을 갖추지 못했습니다. CDC는 (1) 중복 제거율, (2) 분할 속도, (3) 평균 청크 크기 이 세 가지 메트릭으로 평가합니다. 분할 속도는 Gearhash를 사용해서 개선했기에 중복 제거율과 평균 청크 크기를 생각해봅시다.

앞 부분이 모두 0이고, 뒤에만 1을 채운 0x00000FFF 같은 마스크는 해시를 비교하는 윈도우 크기가 작기 때문에 중복 제거율이 낮아지는 문제가 있습니다. CDC의 주된 목적은 동기화죠. 파일 중간에 내용이 변경되어도 청크는 이전 버전과 똑같은 위치에서 경계를 찾아야 합니다.

그래서 논문에서는 마스크에 0 비트를 추가해서 검사하는 윈도우 크기를 증가시킵니다. 슬라이딩 위도우 크기를 늘리면 현재 데이터의 고유한 컨텍스트를 충분히 담고 있다고 해석할 수 있습니다.

예를 들어 아래 처럼 P,Q 해시가 존재한다고 봅시다. 둘은 분명 다른 해시값인데 mask를 씌우면 하위 5bit만 검사하기 때문에 이 둘을 동일한 바운더리로 판단합니다.

P: 10101000000
 & 00000011111
 = 00000000000   → CUT

Q: 00111000000
 & 00000011111
 = 00000000000   → CUT

짧은 mask 00000011111

P ≠ Q 경계 불일치

넓은 mask 10000001111

Q = Q 경계 재동기화

즉, 똑같은 패턴에서 경계를 잘라서 청크의 변경이 크게 발생하지 않게 막아주는 역할을 합니다.

③ Normalized Chunking

지금까지 설명한 내용만 가지고 CDC를 하면 K번째 위치에서 컷이 발생할 확률이 기하 분포를 따르기 때문에 작은 크기의 청크가 평균 값보다 더 많이 만들어집니다.

$$ (1-p)^{k-1}p $$

그래서 FastCDC는 기댓값 위치 전후로 마스크를 다르게 써서 이를 정규화 하려는 노력을 합니다. 청크의 평균 크기를 8KB로 하고자 한다면, 앞 구간에서는 컷이 발생하기 어렵게 하고 뒤에서는 cut을 쉽게 하려는 거죠.

지금까지 이야기 한 걸 모두 조합하면 아래 알고리즘이 완성됩니다.

기대하는 청크 크기의 모습은 정규분포를 따르는 것이겠지만, 사실 알고리즘 특성상 구간 내에서는 기하분포를 따르기 때문에 실제로 잘리는 청크 크기는 아래 그림과 같은 양상을 가집니다.

그림에서 NC Level은 정규화 강도를 의미합니다. 마스크에서 검사 조건을 더 힘들게 할수록 레벨이 올라갑니다

마무리

Hugging Face에서 XET라는 대용량 모델 및 데이터셋 파일을 저장/전송하기 위한 스토리지 시스템을 개발했는데요. 여기서 FastCDC 알고리즘이 사용되었습니다. 정확히는 Apache Parquet을 이용하는데요.

여기서는 8개의 Gear Hash 테이블을 사용해서 FastCDC에서 구간 사이에서는 기하분포를 따르는 걸 최대한 정규분포와 유사하게 맞추려고 노력했습니다.

FastCDC가 자주 쓰이는 알고리즘은 아니지만, 살면서 비슷한 문제를 만나게 되었을 때 이 글을 다시 떠올려보면 좋을 것 같습니다.