File sync: chunking and content addressing

The problem: re-uploading 2 GB for a one-line change

Snip Drop adds versions: a creator replaces their 2 GB video project file with an edited one, and the short link now serves the new version. Most of the file is identical to the last version. Re-uploading all 2 GB for every edit wastes the creator's time and Snip's bandwidth, and storing every version in full multiplies storage. Many creators also upload the very same stock footage, byte for byte.

Chunks named by their content

Split each file into chunks and name each chunk by the hash of its bytes (SHA-256). A file becomes a list of chunk hashes. This is content addressing:

• Upload only what's missing. The client sends the list of hashes; the server answers which ones it doesn't have; the client uploads only those.
• Store identical content once. Two files sharing a chunk point at the same stored chunk, whether they're two versions of one file or the same footage from two creators.
• Integrity for free. A chunk's name is its checksum: recompute the hash on read and corruption is caught (09.06 Checksums and silent corruption).

Dropbox works this way: every file is split into 4 MB blocks hashed with SHA-256, and the list of hashes, the "blocklist", identifies the file's contents; on commit, the server replies with which blocks it still needs.

The insertion problem

Fixed-size chunks have one weakness: insert a single byte near the start, and every boundary after it shifts by one. Every chunk's bytes change, every hash changes, and the "edit" re-uploads the whole file. The LBFS paper from 2001 put it exactly: a single byte inserted at the start of a large file would shift all the block boundaries.

Content-defined chunking

Instead of cutting every N bytes, cut where the content says. Slide a small window over the file computing a rolling hash of the last few dozen bytes, and cut a chunk wherever that hash's low bits are all zero. The cut points depend only on nearby bytes, so after an insertion, boundaries further on are found in the same places relative to the content, and only the chunk containing the edit changes. LBFS used Rabin fingerprints over 48-byte regions, cutting when the low 13 bits matched a value, for chunks of about 8 KB on average, with minimum and maximum sizes to avoid pathological cases.

Try it

In the lab's 600-character note, inserting "DRAFT. " at the start changes all 19 fixed chunks but only 1 of 16 content-defined ones; deleting a sentence changes 12 of 17 fixed chunks and 1 of 15 content-defined. Changing a word near the end changes one chunk either way: in-place edits don't shift anything.

Tested the same way on a 20 KB document: with 10 bytes inserted near the start, 285 of 286 fixed 64-byte chunks were new, against 2 of 190 content-defined chunks.

// A gear-style rolling hash: each byte shifts the hash and adds a pseudo-random value for that byte, so the hash
// depends only on the last ~32 bytes. Cut where its low bits are all zero: the cut depends on content, not position.
export function contentChunks(data: Buffer, mask = 0x3f, min = 16, max = 256) {
  const out: Buffer[] = [];
  let start = 0;
  let h = 0;
  for (let i = 0; i < data.length; i++) {
    h = ((h << 1) + GEAR[data[i]]) >>> 0; // GEAR: 256 fixed random 32-bit values
    const len = i - start + 1;
    if ((len >= min && (h & mask) === 0) || len >= max) {
      out.push(data.subarray(start, i + 1));
      start = i + 1;
      h = 0;
    }
  }
  if (start < data.length) out.push(data.subarray(start));
  return out;
}

Production tools use the same idea with bigger chunks: restic, the backup tool, cuts files with Rabin fingerprints into chunks of 512 KiB to 8 MiB, about 1 MiB on average. Newer algorithms such as FastCDC make the cutting itself much faster.

What content addressing costs

• An index of every chunk, with reference counts or a periodic mark-and-sweep, to know when a chunk is no longer used by any file and can be deleted.
• Many small objects. Millions of chunks are packed into larger files in object storage, like Haystack (09.04 How object storage works).
• Chunk size is a trade-off. Smaller chunks find more duplication; larger ones mean a smaller index and fewer requests.
• Cross-user deduplication leaks a little. If uploading a file is instant because the server already has it, the uploader learns that someone else stored that exact file. Services that care deduplicate only within one account.

Recap

Interview questions