ADR-003: Use FastCDC instead of Fixed Chunking
Status
Accepted
Context
Large files need to be chunked for storage to support:
- Incremental sync (only transfer changed chunks)
- Deduplication (store chunks with same content only once)
- Streaming processing (constant memory)
The choice of chunking strategy directly affects deduplication efficiency and sync bandwidth.
Decision
Use FastCDC (Content-Defined Chunking) instead of fixed-size chunking.
Considered Options
1. Fixed-size chunking (4MB)
Pros:
- Simple implementation
- Predictable chunk sizes
Cons:
- Insertions/deletions cause all subsequent chunk hashes to change
- Low deduplication efficiency (similar files rarely match)
- Transfers large amounts of invalid data during sync
Example: Insert 100B at the beginning of a file
Fixed chunking (4MB):
Original: [Block1][Block2][Block3][Block4]...
After insert: [Block1'][Block2'][Block3'][Block4']...
↑ All chunk hashes changed!
Need to re-upload the entire file.2. FastCDC (Selected)
Pros:
- Content-defined boundaries: Insertions/deletions only affect local areas
- 30%+ improvement in deduplication rate
- 90%+ reduction in incremental sync bandwidth
Cons:
- Slightly more complex implementation
- Variable chunk sizes (but within range)
Example: Insert 100B at the beginning of a file
FastCDC (avg 4MB):
Original: [Block1][Block2][Block3][Block4]...
After insert: [Block1'][Block2][Block3][Block4]...
↑ Only the first chunk changed!
Only need to upload ~4MB.3. Rabin fingerprinting
Pros:
- Classic CDC algorithm
Cons:
- Lower performance
- FastCDC is an optimized version of it
Performance Comparison
| Scenario | Fixed Chunking | FastCDC | Improvement |
|---|---|---|---|
| Insert 1KB at beginning | 100% retransmission | ~4MB retransmission | 96% |
| Modify 100B in middle | ~50% retransmission | ~4MB retransmission | 92% |
| Similar file deduplication | ~10% | ~99% | 89% |
Configuration
pub struct ChunkingConfig {
pub min_size: usize, // 2 MB (minimum chunk)
pub avg_size: usize, // 4 MB (average chunk)
pub max_size: usize, // 8 MB (maximum chunk)
}Consequences
Pros
- Efficient incremental sync
- Significantly improved deduplication rate
- Space savings for similar files
Cons
- Variable chunk sizes, slightly more complex management
- Need to store chunk boundary information