FastCDC4J

maven-central

javadoc

Java

license

FastCDC4J는 FastCDC 알고리즘을 구현하고 간단한 라이브러리 형태로 기능을 제공하는, 데이터 중복 제거를 위한 빠르고 효율적인 콘텐츠 정의 청킹(content-defined chunking) 솔루션입니다.

이 라이브러리는 파일 내용을 기반으로 청크로 분할할 수 있습니다. 생성된 청크는 결정론적(deterministic)이며, 파일이 수정되거나 데이터가 이동하더라도 유지될 가능성이 높기 때문에 데이터 중복 제거에 사용될 수 있습니다. 이 솔루션은 다음의 콘텐츠를 청킹합니다:

• InputStream
• byte[]
• Path, 디렉터리 순회 포함
• Stream<Path>

다음 내장 청커(built-in chunkers)들을 활용하며, 알고리즘을 조작할 수 있는 방법을 제공하여 높은 수준의 사용자 정의가 가능합니다:

• FastCDC - Wen Xia et al. (publication)
• 수정된 FastCDC (modified FastCDC) - Nathan Fiedler (source)
• 고정 크기 청킹 (Fixed-Size-Chunking)

청커의 주요 인터페이스는 다음 메서드를 제공합니다:

• Iterable<Chunk> chunk(InputStream stream, long size)
• Iterable<Chunk> chunk(final byte[] data)
• Iterable<Chunk> chunk(final Path path)
• Iterable<Chunk> chunk(final Stream<? extends Path> paths)

요구 사항 (Requirements)

• 최소 Java 14 필요

다운로드 (Download)

Maven:

<dependency>
   <groupId>io.github.zabuzard.fastcdc4j</groupId>
   <artifactId>fastcdc4j</artifactId>
...

Jar 파일은 릴리스 섹션(release section)에서 다운로드할 수 있습니다.

문서 (Documentation)

• API Javadoc
  또는 릴리스 섹션(release section)에서 이용 가능

시작하기 (Getting started)

1. 프로젝트에 FastCDC4J를 통합하세요.
   API는 io.github.zabuzard.fastcdc4j 모듈에 포함되어 있습니다.
2. ChunkerBuilder를 사용하여 청커(chunker)를 생성합니다.
3. Chunker가 제공하는 메서드를 사용하여 파일을 청크화합니다.

예시

자주 수정되고 서버에 업로드해야 하는 파일들로 가득 찬 디렉터리가 있다고 가정해 봅시다. 하지만 과거에 이미 업로드된 데이터는 업로드를 건너뛰고 싶습니다.

따라서 파일을 청크화하고 로컬 청크 파일 캐시를 설정해야 합니다. 만약 어떤 청크가 이전 업로드에서 이미 포함되어 있다면, 업로드를 생략할 수 있습니다.

Cache example

var buildPath = ...
var cachePath = ...

...

빌드(build) 내의 파일이 수정되거나 데이터가 재배치되어도 청크는 유지될 가능성이 높아 효율적인 데이터 중복 제거를 가져옵니다.

디렉터리 순회(Directory traversal)는 싱글 스레드로 실행되지만, 파일별 다중 스레드 청킹은 쉽게 구현할 수 있습니다:

Consumer<? super Iterable<Chunk>> chunkAction = ...

// Files.walk는 멀티스레딩 특성이 좋지 않으므로 대신 List를 사용하세요.
...

빌더(Builder)

청커 빌더인 ChunkerBuilder는 매우 사용자 정의가 가능한 알고리즘을 제공합니다. 제공되는 내장 청커는 다음과 같습니다:

• FastCDC
• Nlfiedler Rust - FastCDC의 수정된 변형체
• Fixed Size Chunking

또한, 인터페이스 Chunker를 구현하거나 단순화된 인터페이스 IterativeStreamChunkerCore를 구현하여 사용자 정의 청커를 추가하는 것도 가능합니다. 청커는 setChunkerOption(ChunkerOption), setChunkerCore(IterativeStreamChunkerCore) 및 setChunker(Chunker)를 사용하여 설정할 수 있습니다.

청커들은 setExpectedChunkSize(int)로 설정 가능한 예상 청크 크기를 목표로 합니다. 최소 크기는 setMinimalChunkSizeFactor(double)가, 최대 크기는 setMaximalChunkSizeFactor(double)가 제공합니다.

대부분의 청커(chunker)는 예측된 노이즈를 유도하는 소스로 해시 테이블을 내부적으로 사용하며, 커스텀 테이블은 setHashTable(long[])로 제공할 수 있습니다.
반대로, 미리 정의된 테이블 중에서 선택하려면 setHashTableOption(HashTableOption)을 사용할 수 있습니다:

• RTPal
• Nlfiedler Rust

알고리즘은 컷 포인트(cut-points)를 정의하는 마스크(masks)에 의해 크게 유도됩니다. 기본적으로, 이들은 고정된 시드(seed)를 사용하여 무작위로 생성되며, setMaskGenerationSeed(long)을 사용해 변경할 수 있습니다.

마스크를 생성하기 위해 다양한 기술이 사용할 수 있으며, 이는 setMaskOption(MaskOption)으로 설정할 수 있습니다:

• FastCDC
• Nlfiedler Rust

예상 크기에 가능한 한 가까운 청크 크기 분포를 달성하려면 마스크 생성 중에 정규화 레벨(normalization levels)이 사용됩니다. 레벨을 변경하는 데는 setNormalizationLevel(int)가 사용됩니다. 레벨이 높을수록 크기가 예상 크기에 더 가깝지만, 중복 제거율(deduplication rate)은 떨어지는 비용이 따릅니다.

대안으로, 청크가 여전히 예상 크기보다 작은 경우에 사용되는 마스크는 setMaskSmall(long)를, 큰 청크의 경우 사용되는 마스크는 setMaskLarge(long)를 사용하여 수동으로 마스크를 설정할 수도 있습니다.

청크가 읽힌 후에는 그 내용(content)을 기반으로 해시가 생성됩니다. 이 프로세스에 사용되는 알고리즘은 setHashMethod(String)으로 설정할 수 있으며, 이는 java.security.MessageDigest에 의해 지원되고 승인되어야 합니다.

마지막으로, 선택된 속성을 사용하는 청커는 build()를 사용하여 생성할 수 있습니다.

**기본 구성(default configuration)**은 다음과 같습니다:

• 청커 옵션: ChunkerOption#FAST_CDC
• 예상 크기: 8 * 1024
• 최소 크기 계수: 0.25
• 최대 크기 계수: 8
• 해시 테이블 옵션: HashTableOption#RTPAL
• 마스크 생성 시드: 941568351
• 마스크 옵션: MaskOption#FAST_CDC
• 정규화 레벨: 2
• 해시 메서드: SHA-1

fastCdc(), nlFiedlerRust() 및 fsc() 메서드를 사용하여 원래 제안된 알고리즘을 사용하는 구성을 얻을 수 있습니다.