mothcdc

Formerly mincatcdc. A fork of MinCDC that adds a caterpillar layer for metadata-efficient content-defined chunking on redundant data. The algorithm described below is MinCDC; see This fork for what's added and why.

MinCDC is a very simple yet efficient content-defined chunking algorithm. It splits your input data into chunks in such a way that the boundaries are defined by the data itself. This means duplicate regions in large (sets of) files are likely to have identical boundaries and can thus efficiently be found and deduplicated.

To start using mothcdc add the following to your Cargo.toml:

[dependencies]
mothcdc = "0.6"

Please refer to the documentation for more information on usage.

This fork: mothcdc

MinCDC — the algorithm and its SIMD core — is Orson Peters' work. This fork adds a caterpillar layer, an idea from the Chonkers algorithm (Berger, 2025), with vector acceleration in the style of VectorCDC (Udayashankar et al., FAST '25).

When data has a long run of repeated bytes — zeros, padding, the same block over and over — mincdc cuts it into a flood of tiny chunks. Each chunk is a record you have to store and track. The bytes dedupe down to almost nothing, but you still keep every record: a mostly-empty 200 MiB disk image becomes ~182,000 of them.

The caterpillar collapses any run of byte-identical adjacent chunks into a single record with a repeat count. On that disk image: 182,701 → 7,798 records (−96%), with no change to what is stored. A SIMD scan proves a run once and skips the boundary search inside it, so runs chunk several times faster than plain mincdc. A cheap probe keeps the cost near zero (~1%) on data with no runs. When streaming, runs survive buffer refills, so a multi-GB zero region is still one record.

The crate also ships a C API (--features capi) and a dedup-bench fork so it can be measured by the same harness as every other chunker.

Benchmarks

All numbers come from UWASL dedup-bench (the VectorCDC evaluation harness), with mothcdc plugged in as a chunking technique — same loop, same timers, same dedup measurement as every other algorithm. One AMD EPYC/AVX2 machine, one session, ~8 KiB target chunks. Corpora: a raw Debian VM image (768 MiB), DEB .ova appliances (3 GiB, FAST '25 dataset), six consecutive linux-6.6.x source tars (8 GiB, stand-ins for backup generations), and enwik9 (1 GiB of Wikipedia text, never used for tuning). mothcdc uses the recommended window (min=4096, max=12288); the "wide" row is (2048, 14336).

Throughput, GiB/s:

Space savings (dedup-bench measure-dedup; same result on any machine):

In short: best dedup on every corpus at every chunk size tested (4K, 8K, 16K), and the fastest chunker except VectorCDC RAM — which has the worst dedup of any algorithm here. On the VM image (long zero runs) the caterpillar turns 232k chunks into 56k records; on data without runs, records equal chunks and the layer costs ~1%.

Caveats. mincdc runs slightly under the chunk-size target where others run over, so normalizing for chunk size would trim some of the dedup edge over AE-Min. SeqCDC ties plain mincdc's dedup at 16K targets. enwik9 shows the speed holds on data we never tuned on, but says nothing about dedup — a single text file has ~0% duplication for every algorithm. Absolute GiB/s varies across shared hosts; compare within a column.

To reproduce: the corpus is public (https://mincatcdc-bench-corpus.t3.storage.dev/corpus/MANIFEST.sha256, checksums included), the harness fork is linked above, and BENCH_CORPUS=<dir> cargo bench runs the in-repo bench on your own files. No build flags needed — SIMD width is detected at runtime (SSE2/AVX2/AVX-512 on x86_64, NEON on aarch64). Older tables live in CHANGELOG.md and examples/.

Choosing min/max

Prefer a narrow window with a high minimum. At the same ~8 KiB average, (4096, 12288) chunks 40–50% faster than (2048, 14336) with equal or better dedup on every corpus measured — the boundary search scans max - min bytes per chunk. (This is the same window as upstream's "MinCDCHash4-l" below.) Widening max buys fewer records but costs speed and dedup. cargo run --release --example frontier -- <paths> prints the trade-off on your own data. The hash constants make no measured difference; keep the defaults.

Using the caterpillar

It's a drop-in over the byte-slice chunker — iterate Segments instead of Chunks:

use mothcdc::{CaterpillarChunker, MinCdcHash4};

for seg in CaterpillarChunker::new(&data, 4096, 12288, MinCdcHash4::new()) {
    // Store the unique content once. `dedup_key()` returns the bytes to
    // fingerprint regardless of variant (a single chunk or a repeated unit).
    store(hash(seg.dedup_key()), seg.dedup_key());
    // Record where it goes: offset, total byte length, and how many underlying
    // chunks this one record stands for.
    record(seg.offset(), seg.len(), seg.chunk_count());
}

CaterpillarChunker works on an in-memory slice; for inputs larger than memory, CaterpillarReadChunker does the same coalescing over a streaming reader in bounded memory (it yields borrowed Segments valid until the next call, like ReadChunker). Runs coalesce across buffer refills: a run's unit is copied once — at most max_size bytes — when it crosses a refill, so even a multi-gigabyte zero region is a single record. Everything else stays zero-copy.

(An experimental second tier — content-defined period detection for phase-rotating runs — was evaluated and removed: mincdc self-aligns to most periods so it rarely helped, and it cost 76–99% throughput. See examples/CATBENCH_RESULTS.md and the proto/caterpillar-period branch.)

To get the disk-image number, two 200 MiB APFS images were created with hdiutil (hdiutil create -size 200m -fs APFS ...), each holding a real source tree (the second also holds an extra version), so each image is ~92% written-zero free space — not sparse holes, so SEEK_HOLE would not skip them. Both images were chunked with cargo run --release --example catbench at min=2048, max=14336. Plain mincdc produced 182,701 records; the caterpillar produced 7,798, with identical deduplicated content. Full method and the other corpora (Linux kernels, containers, SQLite, source trees) are in examples/REALBENCH_RESULTS.md. Obviously the benchmark is specific to this case. YMMV.

This fork also fixes a soundness bug in the upstream SIMD prefetch and adds test coverage (cross-SIMD-width determinism, an invariant/oracle harness).

Algorithm

The basic idea of MinCDC is to choose chunk boundaries based on the minimum value of a sliding window over the input data. That is, if the desired chunk size is between min_size and max_size, we find some min_size <= i <= max_size such that evaluate(bytes[i - w..i]) is minimized, where w is the window size, breaking ties by choosing the earliest such i. Then we return chunk bytes[..i] and repeat the process on the remainder bytes[i..].

This library provides two SIMD-accelerated implementations of MinCDC, both with a window size of 4:

• MinCDC4, where the evaluation function is u32::from_le_bytes(bytes[i - 4..i]), i.e. a window size of 4 bytes interpreting the bytes as a little-endian u32, and
• MinCDCHash4, where the evaluation function is hash(u32::from_le_bytes(bytes[i - 4..i])). The hash function used is the very simple hash(x) = x.wrapping_mul(a).wrapping_add(b), for some constants a and b.

MinCDCHash4 can be slightly (~10%) slower but is far more robust and predictable, it is the recommended default.

Performance

MinCDC is several times faster than the commonly used FastCDC while providing a similar amount of deduplicating power. To benchmark this I downloaded all available Linux kernel 6.x.tar archives (tools/download-linux.sh) and ran the below algorithms on them, all of them configured to target an expected chunk size of 8 KiB.

To determine the chunking speed I only chunked linux-6.0.tar while the file was loaded into memory to avoid disk overhead. The dedup% is one minus the total size of unique chunks divided by the total size of all input files (thus higher is better). The normalized dedup% is the same percentage acquired from repeating the experiment with different window sizes until the mean chunk size matched 8 KiB (+/- 1%). This is important when comparing deduplication power since smaller chunks typically means better deduplication.

Here the "-s" variants use a small window size of 8 KiB +/- 25% (min=6144, max=10240), and the "-l" variants use a larger window size of 8 KiB +/- 50% (min=4096, max=12288). The maximum chunk size was increased further for FastCDC as it inherently has a long tail of chunk sizes (see below), this did not impact chunking speed much.

The normalized dedup% for FastCDC-l is marked with an asterisk because I was unable to get the mean chunk size within 1% of 8KiB. The mean size would suddenly jump from 7741 to 10846 just by making a tiny adjustment in window size. For comparison, MinCDCHash4-l with a mean size of 7741 has a dedup% of 62.49% versus FastCDC-l's 62.75%.

Chunk Distribution

Unlike most other content-defined chunking algorithms, the distribution of chunk sizes generated by MinCDCHash4 is almost entirely uniform in the range min_size, max_size. This makes it very predictable and well-behaved; the expected chunk size is also very close to the mean chunk size. Compare that with FastCDC's distribution for an expected chunk size of 8 KiB:

While the peak is at 8 KiB as expected for FastCDC, there is a long and heavy tail, increasing the mean chunk size by a lot. MinCDCHash4 never creates a chunk outside of the specified range, except for the last chunk which may be smaller.

There is still a bias towards smaller chunks as MinCDC breaks ties in the minimum value towards the earlier breakpoint, but this bias is relatively small.