Content-defined chunking: an interactive delta sync simulator

File sync and backup tools avoid re-uploading whole files by splitting them into chunks, hashing each, and sending only chunks the server does not already have. How the file is cut decides how well that works. Cutting every N bytes breaks as soon as bytes are inserted, because every later chunk shifts. Content-defined chunking cuts where the content itself says to, using a rolling hash, so an edit only changes the chunks around it.

The playground cuts a 4,000-byte file both ways, makes an edit, and shows which chunks of the edited file are new and must be uploaded.

The boundary-shift problem

With fixed 128-byte chunks, inserting 6 bytes near the start of the file moves every later byte, so every later chunk has different contents and a different hash: 30 of 32 chunks, 3,750 bytes, must be uploaded for a 6-byte change. Deleting 40 bytes does the same. Content-defined chunks upload 107 bytes for the insert and 240 for the delete. When nothing shifts, as when one byte is overwritten or text is appended, both approaches upload about one chunk.

How content-defined chunking works

The chunker slides along the file computing a rolling hash of the last few dozen bytes, updated in constant time per byte. Wherever the hash matches a pattern, for instance its top 7 bits all zero, which happens once every 128 bytes on average, it cuts. Since a boundary depends only on the bytes just before it, the boundaries after an edit fall in the same places as before, and the chunks between them have the same hashes. Minimum and maximum chunk sizes stop runs of unlucky or repetitive data from making tiny or huge chunks. LBFS used Rabin fingerprints; modern tools use faster hashes such as the Gear hash in FastCDC.

• Chunk size trades deduplication for metadata: smaller chunks re-upload less after an edit but mean more hashes to store and look up. Backup tools aim for kilobytes to a few megabytes.
• Deduplication across files. Because chunks are found by content, the same data in two files, or two versions of one, is stored once. Restic, Borg and casync work this way.
• rsync solves a related problem differently: the receiver sends checksums of fixed blocks of its old copy, and the sender slides a rolling checksum over the new file to find those blocks at any offset. It needs the old version of the same file; content-defined chunking does not.

Content-defined chunking in code

import hashlib, random

random.seed(1)
GEAR = [random.getrandbits(32) for _ in range(256)]   # one random number per byte value

def chunks(data: bytes, avg=1 << 20):
    """Content-defined chunks, about avg bytes each (avg a power of two)."""
    bits = avg.bit_length() - 1
    mask = ((1 << bits) - 1) << (32 - bits)            # test the hash's top bits
    start, h = 0, 0
    for i, byte in enumerate(data):
        h = ((h << 1) + GEAR[byte]) & 0xFFFFFFFF      # rolling: old bytes shift out
        size = i - start + 1
        if (size >= avg // 4 and h & mask == 0) or size >= avg * 4:
            yield data[start:i + 1]
            start, h = i + 1, 0
    if start < len(data):
        yield data[start:]

def to_upload(data, server_has):
    return [c for c in chunks(data) if hashlib.sha256(c).hexdigest() not in server_has]

In a system design interview

For a Dropbox-style service: “Clients split files with content-defined chunking, about 4 MB on average, and hash each chunk with SHA-256. A file version is a list of chunk hashes. Before uploading, the client asks which hashes the server lacks and sends only those, straight to object storage, so editing the middle of a large file uploads one or two chunks, and identical chunks across users are stored once.” Expect the follow-ups: how chunks are garbage-collected when no version references them, how conflicting edits are detected, and the privacy cost of cross-user deduplication.

Read the guide to delta sync or object storage, see the Merkle tree for comparing large sets of hashes, or watch a strong candidate design a file sync service.

Questions people ask