In a cloud-drive sync client, why does content-defined chunking survive an insert near a file's start when fixed-size blocks do not?

middlemust knowfreq 62%

answer

positions versus content
one insert moves every later byte
small sliding window decides the cut
low bits of a rolling hash

basics

~20 s

Fixed-size blocks cut at fixed offsets, so an insert shifts every later boundary and hash. Content-defined chunking cuts where a rolling hash of nearby bytes matches a pattern, so boundaries follow the content and realign after the edit.

solid answer

~50 s

With fixed-size blocks every boundary is an offset: 0, 4 MiB, 8 MiB and so on. Insert one byte near the start and every later byte moves one position, so every block from there on holds different bytes, every hash changes, and a 2 GiB file re-uploads almost entirely. Content-defined chunking instead slides a small window of a few dozen bytes across the data and computes a rolling hash — typically a Rabin fingerprint — updated in constant time per byte. It cuts wherever the hash's low bits match a fixed pattern, for example the low 13 bits being zero, which gives an average chunk of roughly 8 KiB. Because each decision depends only on the bytes inside the window, once the window has passed the edit the same boundaries reappear at the same content, merely shifted. Only the chunk holding the edit, and occasionally a neighbour, changes. Minimum and maximum sizes bound the variance.

With fixed-size blocks every boundary is an offset: 0, 4 MiB, 8 MiB and so on. Insert one byte near the start and every later byte moves one position, so every block from there on holds different bytes, every hash changes, and a 2 GiB file re-uploads almost entirely. **Content-defined chunking** instead slides a small window of a few dozen bytes across the data and computes a **rolling hash** — typically a Rabin fingerprint — updated in constant time per byte. It cuts wherever the hash's low bits match a fixed pattern, for example the low 13 bits being zero, which gives an average chunk of roughly 8 KiB. Because each decision depends only on the bytes inside the window, once the window has passed the edit the same boundaries reappear at the same content, merely shifted. Only the chunk holding the edit, and occasionally a neighbour, changes. Minimum and maximum sizes bound the variance.

code

pseudocode · 12 lines

pseudocode

chunk_start = 0
h = 0
for i in 0 .. len(data) - 1:
    h = roll(h, incoming = data[i], outgoing = data[i - W] if i >= W else none)
    size = i - chunk_start + 1
    if size < MIN_SIZE:
        continue
    if (h & MASK) == 0 or size >= MAX_SIZE:
        emit_chunk(data[chunk_start .. i])
        chunk_start = i + 1
if chunk_start < len(data):
    emit_chunk(data[chunk_start .. len(data) - 1])

go deeper

for a junior

Recall the one-line contrast: fixed blocks cut at offsets, content-defined chunking cuts where the content says so, which is why an insert only disturbs nearby chunks.

for a middle

Explain the boundary-shift problem with a concrete insert, then the sliding window, the rolling hash test on low bits, and why boundaries realign after the window passes the edit.

for a senior

Discuss the minimum and maximum bounds, their pathologies, and the data types where chunking gives little benefit, such as compressed or encrypted files and applications that rewrite whole files.

for a principal

Weigh CDC's per-byte CPU cost and variable chunk count against bandwidth and storage savings, and decide per data class whether content-defined, fixed or whole-file storage fits best.

Fixed-size blocks and the boundary-shift problem

The simplest chunker cuts a file at fixed offsets: bytes 0 to 4 MiB are block 0, the next 4 MiB are block 1, and so on. Each block is hashed with SHA-256 and stored by its hash. This works well for in-place overwrites — change bytes inside block 7 and only block 7's hash changes.

It fails badly for insertions and deletions, which is how many documents actually change. Insert a single byte at offset 100 of a 2 GiB file and every byte after offset 100 moves one position later. Block 0 now holds different bytes, and so does block 1, and every block after it, because each one now starts one byte earlier in the original content. Every hash changes, dedup against the previous version finds nothing, and the client re-uploads almost the whole file. This is the boundary-shift problem: boundaries are tied to positions, and an insert changes the position of everything after it.

Content-defined chunking

Content-defined chunking (CDC) ties boundaries to content instead. The chunker slides a small window — typically a few dozen bytes — over the data and computes a rolling hash of the window at every byte position. A rolling hash can be updated in constant time as the window advances; the classic choice is a Rabin fingerprint, the same family of technique used in Rabin-Karp string search.

At each position the chunker tests a cheap condition on the hash, such as hash & MASK == 0 with a 13-bit mask. When it holds, the chunker cuts. If hash values behave like random numbers, the condition holds with probability 1 in 8,192 at each position, so boundaries appear on average about every 8 KiB. The average is a tuning knob: test more bits for bigger chunks, fewer bits for smaller ones.

Why the boundaries realign

Take the same one-byte insert under CDC:

Boundaries before the insert are unaffected, because the window never saw the new byte when deciding them.
For the next few dozen positions the window contains the inserted byte, so hash values differ and a boundary may appear or vanish in that stretch.
Once the window has fully passed the insert, it again holds exactly the bytes it held at the corresponding place in the old file, so it produces the same hashes and finds the same boundaries, just shifted by one byte.
From there on each chunk contains bytes identical to an old chunk, so its SHA-256 matches and it deduplicates.

The net effect: only the chunk containing the edit changes, occasionally together with a neighbour when a boundary near the edit moved. With about 8 KiB average chunks, that insert costs on the order of 8-16 KiB of upload rather than 2 GiB.

Minimum and maximum chunk sizes

Pure CDC has two pathologies, so practical chunkers bound it:

Minimum size: without it, data where the condition fires repeatedly produces many tiny chunks, each costing an index entry and a request. The chunker skips the boundary test until the chunk reaches the minimum.
Maximum size: without it, a long stretch where the condition never fires — such as a run of identical bytes, whose window hash is constant — yields one giant chunk and destroys delta granularity. The chunker forces a cut at the maximum.

Parameter	Set too low	Set too high
Minimum	tiny chunks, metadata overhead	boundaries skipped, edits spread further
Average (mask bits)	huge chunk count	coarse deltas, weaker dedup
Maximum	many forced, position-based cuts	giant chunks after uniform regions

Forced cuts at the maximum are position-based again, so a region full of them can still suffer boundary shifts; keeping the maximum several times larger than the average makes forced cuts rare.

Where CDC does not help

Compressed or encrypted files: a small change to the plaintext typically alters most of the output bytes, so nearly every chunk changes whatever the chunker does. Some designs chunk the plaintext first and compress or encrypt each chunk afterwards.
Files rewritten wholesale: an application that reorders or re-encodes its whole file on every save leaves nothing stable for the chunker to find.
CPU cost: CDC evaluates a hash at every byte, which is more work than slicing at offsets; it is still linear time and usually cheap next to the network.

Summary

Fixed-size blocks are cheap and fine for in-place overwrites, but one insert shifts every later boundary. CDC decides boundaries from a sliding window of content, so they move with the data and realign about one window's length after the edit, keeping the upload proportional to the size of the change rather than the size of the file.

## Fixed-size blocks and the boundary-shift problem The simplest chunker cuts a file at fixed offsets: bytes 0 to 4 MiB are block 0, the next 4 MiB are block 1, and so on. Each block is hashed with SHA-256 and stored by its hash. This works well for **in-place overwrites** — change bytes inside block 7 and only block 7's hash changes. It fails badly for **insertions and deletions**, which is how many documents actually change. Insert a single byte at offset 100 of a 2 GiB file and every byte after offset 100 moves one position later. Block 0 now holds different bytes, and so does block 1, and every block after it, because each one now starts one byte earlier in the original content. Every hash changes, dedup against the previous version finds nothing, and the client re-uploads almost the whole file. This is the **boundary-shift problem**: boundaries are tied to *positions*, and an insert changes the position of everything after it. ## Content-defined chunking **Content-defined chunking (CDC)** ties boundaries to *content* instead. The chunker slides a small window — typically a few dozen bytes — over the data and computes a **rolling hash** of the window at every byte position. A rolling hash can be updated in constant time as the window advances; the classic choice is a **Rabin fingerprint**, the same family of technique used in Rabin-Karp string search. At each position the chunker tests a cheap condition on the hash, such as `hash & MASK == 0` with a 13-bit mask. When it holds, the chunker cuts. If hash values behave like random numbers, the condition holds with probability 1 in 8,192 at each position, so boundaries appear on average about every 8 KiB. The average is a tuning knob: test more bits for bigger chunks, fewer bits for smaller ones. ## Why the boundaries realign Take the same one-byte insert under CDC: 1. Boundaries before the insert are unaffected, because the window never saw the new byte when deciding them. 2. For the next few dozen positions the window contains the inserted byte, so hash values differ and a boundary may appear or vanish in that stretch. 3. Once the window has fully passed the insert, it again holds exactly the bytes it held at the corresponding place in the old file, so it produces the same hashes and finds the **same boundaries**, just shifted by one byte. 4. From there on each chunk contains bytes identical to an old chunk, so its SHA-256 matches and it deduplicates. The net effect: only the chunk containing the edit changes, occasionally together with a neighbour when a boundary near the edit moved. With about 8 KiB average chunks, that insert costs on the order of 8-16 KiB of upload rather than 2 GiB. ## Minimum and maximum chunk sizes Pure CDC has two pathologies, so practical chunkers bound it: - **Minimum size**: without it, data where the condition fires repeatedly produces many tiny chunks, each costing an index entry and a request. The chunker skips the boundary test until the chunk reaches the minimum. - **Maximum size**: without it, a long stretch where the condition never fires — such as a run of identical bytes, whose window hash is constant — yields one giant chunk and destroys delta granularity. The chunker forces a cut at the maximum. | Parameter | Set too low | Set too high | |---|---|---| | Minimum | tiny chunks, metadata overhead | boundaries skipped, edits spread further | | Average (mask bits) | huge chunk count | coarse deltas, weaker dedup | | Maximum | many forced, position-based cuts | giant chunks after uniform regions | Forced cuts at the maximum are position-based again, so a region full of them can still suffer boundary shifts; keeping the maximum several times larger than the average makes forced cuts rare. ## Where CDC does not help - **Compressed or encrypted files**: a small change to the plaintext typically alters most of the output bytes, so nearly every chunk changes whatever the chunker does. Some designs chunk the plaintext first and compress or encrypt each chunk afterwards. - **Files rewritten wholesale**: an application that reorders or re-encodes its whole file on every save leaves nothing stable for the chunker to find. - **CPU cost**: CDC evaluates a hash at every byte, which is more work than slicing at offsets; it is still linear time and usually cheap next to the network. ## Summary Fixed-size blocks are cheap and fine for in-place overwrites, but one insert shifts every later boundary. CDC decides boundaries from a sliding window of content, so they move with the data and realign about one window's length after the edit, keeping the upload proportional to the size of the change rather than the size of the file.

Why do content-defined chunkers enforce both a minimum and a maximum chunk size?
Without a minimum, data where the boundary condition fires often produces many tiny chunks, each costing an index entry and a request. Without a maximum, a long region where it never fires, such as a run of identical bytes, becomes one huge chunk, so any edit there re-uploads all of it. The trade-off is that forced cuts at the maximum are offset-based and can shift again.
Does content-defined chunking help when a user edits a compressed or encrypted file?
Very little. A small change to the underlying content typically changes most of the compressed or encrypted bytes, so nearly every chunk's hash changes regardless of where the boundaries fall. Dedup works best on data stored uncompressed; some designs chunk the plaintext and only then compress or encrypt each chunk individually.

saying these in an interview costs you the question

Fixed-size blocks handle inserts well because only one block changes.
Content-defined chunking produces chunks of identical size.
Each boundary decision depends on everything read so far in the file.
Content-defined chunking makes compressed files deduplicate well.
Content-defined chunking just means fixed blocks with a smaller size.

In a cloud-drive sync client, why does content-defined chunking survive an insert near a file's start when fixed-size blocks do not?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Fixed-size blocks and the boundary-shift problem

Content-defined chunking

Why the boundaries realign

Minimum and maximum chunk sizes

Where CDC does not help

Summary

▾common follow-ups2 questions

▾red flags5 flags

Fixed-size blocks and the boundary-shift problem

Content-defined chunking

Why the boundaries realign

Minimum and maximum chunk sizes

Where CDC does not help

Summary

answer

go deeper