Feature : Block-Level (Chunking) Deduplication using FastCDC

[vivek0369]

📌 Overview

Currently, the storage engine only performs whole-file deduplication. This means that if two large files differ by even a single byte, both files are stored independently, resulting in significant storage waste — especially for mutable large files such as:

• Virtual Machine Images (.vmdk, .qcow2)

• Database snapshots

• Incremental backups

• Container layers

• Large binary archives

This feature proposes implementing block-level deduplication using the FastCDC content-defined chunking algorithm in Rust.

Instead of hashing entire files, files will be split into variable-sized chunks using rolling hash boundaries. Identical chunks across files will be stored only once, dramatically improving storage efficiency.

---

🎯 Goals

• Implement FastCDC-based content-defined chunking

• Enable block-level deduplication

• Reduce redundant storage for large mutable files

• Improve backup and snapshot efficiency

• Maintain high throughput with minimal memory overhead

---

💡 Why FastCDC?

Traditional fixed-size chunking performs poorly when bytes are inserted or removed because chunk boundaries shift.

FastCDC solves this using:

• Rolling hash fingerprinting

• Content-defined chunk boundaries

• Adaptive normalization

• High-speed chunking performance

This approach is used in enterprise-grade storage and backup systems such as:

• ZFS

• BorgBackup

• Restic

• VDO

• Dropbox backend systems

---

🏗 Proposed Architecture

Current Flow

File → SHA256(file) → Store Entire File

Proposed Flow

File
  ↓
FastCDC Chunking
  ↓
Chunk Hashing (SHA256/BLAKE3)
  ↓
Chunk Index Lookup
  ↓
Store Only Unique Chunks
  ↓
Metadata Manifest Creation

---

🔧 Core Components

1. FastCDC Chunker

Implement content-defined chunking with:

• Rolling hash window

• Min/avg/max chunk sizes

• Boundary detection masks

Suggested defaults:

MIN_CHUNK_SIZE = 16KB
AVG_CHUNK_SIZE = 64KB
MAX_CHUNK_SIZE = 256KB

---

2. Chunk Hashing

Each chunk should be hashed independently using:

• BLAKE3 (preferred for performance)
  or

• SHA256

Example:

hash(chunk_bytes) -> ChunkID

---

3. Chunk Store

Store chunks separately:

/chunks/
    ab/cd/hash.chunk

Avoid storing duplicate chunks.

---

4. Manifest Metadata

Each uploaded file should maintain a manifest:

{
  "file_name": "vm-image.qcow2",
  "chunks": [
    "hash1",
    "hash2",
    "hash3"
  ]
}

This enables reconstruction during restore/download.

---

5. Reconstruction Pipeline

During retrieval:

• Read manifest

• Stream chunks in order

• Rebuild original file

---

⚡ Performance Considerations

Memory Efficiency

• Use streaming I/O

• Avoid loading full files into memory

Parallelism

Potential future optimization:

• Parallel chunk hashing with Rayon

• Async chunk persistence

Chunk Cache

Optional LRU cache for hot chunks.

---

🧪 Edge Cases

• Very small files

• Highly compressed/encrypted files

• Chunk boundary drift

• Corrupted chunk manifests

• Concurrent uploads

---

📊 Expected Impact

Metric | Current | After FastCDC -- | -- | -- Deduplication Granularity | Whole File | Block Level VM Backup Efficiency | Poor | Excellent Incremental Backup Size | Large | Minimal Storage Savings | Low | High Upload Redundancy | High | Reduced

Expected improvements:

• 50–90% storage savings for mutable large files

• Faster incremental backups

• Reduced network transfer

---

🛠 Suggested Rust Crates

• fastcdc

• blake3

• rayon

• tokio

• bytes

Example:

[dependencies]
fastcdc = "3"
blake3 = "1"
rayon = "1"
tokio = { version = "1", features = ["full"] }

---

📁 Suggested File Structure

src/
 ├── chunking/
 │    ├── fastcdc.rs
 │    ├── boundaries.rs
 │
 ├── storage/
 │    ├── chunk_store.rs
 │    ├── manifest.rs
 │
 ├── hashing/
 │    ├── blake3.rs
 │
 ├── restore/
 │    ├── reconstruct.rs

---

✅ Acceptance Criteria

• Files are chunked using FastCDC

• Duplicate chunks are stored only once

• Chunk manifests are generated correctly

• Files can be reconstructed losslessly

• Streaming uploads supported

• Benchmarks added

• Unit + integration tests added

• Documentation updated

---

🧪 Benchmark Ideas

Test against:

• VM disk images

• SQLite/Postgres snapshots

• Incremental backups

• Large binary datasets

Measure:

• Chunking throughput

• Deduplication ratio

• Restore speed

• Memory usage

---

📚 References

• FastCDC Paper:
  “FastCDC: A Fast and Efficient Content-Defined Chunking Approach for Data Deduplication”

• Reference Crates:

  • fastcdc

  • restic

  • borgbackup

---

🏷 Labels

enhancement
NSoC'26 and GSSoC'26

[pranavv2707]

Hi @Rakshat28 ,

I would love to try to tackle this issue and since the architecture given by @vivek0369 has a very clear outline, i think i can implement this feature with the necessary requirements, using FastCDC in Rust.

While I am still not completely familiar with all of the advanced concepts, I am ready to try using them by learning their implementation and using the help of the architecture, I am sure can get through it, with the help of LLMs for clarification and optionally the documentation too.

Could you assign this task to me, under GSSoC '26? I shall try my best to sort this issue!

[Rakshat28]

@pranavv2707 Submit a PR and run the existing benchmarks on it, if it improves the performance, then we'll consider a merger. Also make sure to use BLAKE3 instead of SHA256 as BLAKE3 enables parallel hashing, unlike SHA256.