Resync

A deduplicating backup does one thing: cut the file into chunks, hash each chunk, and send only the hashes the store has never seen. Everything that makes it fast or useless is in the first step, because the hash and the store have no opinions — a chunk whose bytes shifted by one position is simply a chunk nobody has ever seen.

So: where do the cuts go?

fixed      cut every 4096 bytes.          cut position = f(offset)
content    cut where a rolling hash of
           the last 48 bytes hits 0.      cut position = f(those 48 bytes)

Insert a single byte at the front of a 1 MiB file and the two answers are not close.

That third row is the point of the piece, and the demo’s whole-prefix hash button is where it lives.

The mechanism is locality, not content-awareness

“Content-defined chunking” is the name everyone uses, and it suggests the win comes from the boundary being derived from the bytes. It does not. The third row above derives its boundary from the bytes too — a hash folded over every byte seen so far, cut when it lands on the same one-in-4096 pattern — and it loses the whole file to one inserted byte, exactly like cutting on the offset.

The windowed hash survives for one reason: its decision at position i reads bytes (i−48, i] and nothing else. Two streams that share those 48 bytes make the same decision, so the second pass’s boundaries do not have to be found again after an edit — they were never lost, except in the handful of positions whose window straddles the new byte. Everything downstream hashes identically because it is identical, cut for cut.

The demo draws this as a row of teal ticks between each pair of lanes: one tick per cut the two passes agree on. Fixed chunking’s ticks stop dead at the edit. The window’s ticks have a single gap in them, and the gap is the bill.

Where the boundaries re-agree

The gap has a length, and the length is predictable. A 1-byte edit lands inside some chunk; the next cut both passes can agree on is the end of that chunk, because its window clears the edit long before it arrives. Chunk lengths are exponential and an exponential is memoryless, so the distance from an arbitrary edit to the end of its chunk is one whole expected chunk, not half of one.

Nothing in that prediction mentions the size of the file, and the measurement agrees — a one-byte insert costs the same whether there is a quarter of a megabyte downstream of it or sixteen megabytes:

Fixed chunking’s column is not a cost, it is a coin flip: it re-uploads everything downstream of wherever you happened to edit, so its average is half the file and its distribution is a ramp. The cost view draws that ramp against the window’s flat line, with the whole-prefix hash sitting on top of fixed where it belongs.

Why one chunk costs two chunks

A 1-byte edit costs 1.02 chunks on average — and 9,363 bytes, against a mean chunk of 4,280. Twice the mean, and not by accident: the chunk an edit lands in is not drawn from the distribution of chunks, it is drawn from the distribution of chunks weighted by length, because a long chunk catches proportionally more edits. For an exponential that doubles the expectation exactly. It is the same arithmetic as waiting longer than average for a bus that arrives on average every ten minutes.

So the honest headline for content-defined chunking is not “one chunk per edit”. It is two chunks’ worth of bytes per edit, forever, regardless of file size — which is still 54× better than fixed chunking on a 1 MiB file and 833× better on a 16 MiB one.

The number you configured is a mean, never a size

A cut happens when the hash lands on one pattern in target, independently at every position. That is a geometric wait, and it looks like one:

An exponential puts 1 − e^(−½) = 39.3% of its mass under half its mean and its median at ln 2 = 0.693 of it. Both show up in the table to within a percent, for three targets, which is the sizes view: the bars are the measurement, the dashed curve is p·e^(−x/target), and nothing was fitted.

Two in five chunks under half the configured size is why every real implementation ships a minimum, and a tail that reaches 8× is why they ship a maximum.

What the clamps cost

They are not free, and what they cost is the property the whole scheme is built on. A minimum makes a cut depend on where the last cut was — the boundary stream stops being a function of local bytes and becomes a chain.

The damage is small — the chain is short, because after one agreed cut the two passes are back in lockstep — but the drift in the mean is not small and is rarely mentioned: a 2 KiB minimum on a 4 KiB target gives a 5.96 KiB average chunk. The prediction is min + 1/p = 2 KiB + 4 KiB = 6 KiB, which is what you get, 50% above the number anyone thought they configured. Turn clamps on in the sizes view to watch the spike at the minimum and the cliff at the maximum replace the tail.

The case fixed chunking wins

Overwrite a byte in place rather than inserting one, and nothing downstream moves. Fixed chunking then loses exactly one chunk — and it is the smaller bill, because a fixed chunk is exactly 4 KiB while the content-defined chunk the edit landed in averages twice its mean:

one byte overwritten, averaged over 33 positions in a 1 MiB file
  fixed    4.00 KiB   0.39%        ← one chunk, by construction
  window   8.89 KiB   0.87%        ← one chunk, size-biased

Fixed chunking is not a bad idea. It is a bad idea for streams that shift, which is every file an application rewrites and no file that is only ever appended to. A log, an append-only segment, a block device with in-place writes: fixed chunks are correct and cheaper there. The question was never “which hash is cleverer”, it was “does anything in my format insert bytes in the middle”.

Twenty-four small edits at random positions, each one backed up, on a 4 MiB file, which is a mild day for a mail spool or an SQLite database:

fixed    28.00 MiB uploaded   7.0×  the file
window   177.9 KiB uploaded   0.043× the file      161× apart

Reading the demo

Three views, every number in them measured on the bytes rather than asserted:

• chunks — the headline. Four lanes of the same bytes: the 1st pass that the store already holds and the 2nd pass being backed up, for fixed cuts and for content-defined cuts. Each chunk is coloured by its own hash, so a chunk the store recognises keeps the colour it had in the lane above; a red hatched chunk is one that has to go over the wire. Click or drag anywhere to move the edit; insert, delete and overwrite are the three things an application does to a file.
• sizes — the length distribution against the exponential it is, with the clamps available as a toggle.
• cost — the same one-byte edit walked across a 128 KiB file, which is where fixed chunking’s ramp and the window’s flat line are side by side.

src/resync.mjs is the whole thing in 243 lines of code and no dependencies: a buzhash rolling hash (a random 32-bit word per byte value, rotated one bit per position and XORed back out as it leaves the window — which is what makes the window exact rather than approximate), the two chunkers, a content-address stand-in, and the upload accounting. scripts/measure.mjs prints every table above; scripts/screenshot-demo.mjs drives the page in a real browser, checks the page and a cold run of the module agree byte for byte, and fails if any claim on this page stops holding.

The streams are uniform random bytes, which is the unflattering choice: there are no duplicate chunks to find, so every number here is dedup against the previous pass only. Real data would make both columns look better and the ratio between them no different.