CSE Roadmap

Common tier · about 3 hours · 8 parts

Part 4 of 8 · 3 min read

Chunks, hashes and delta sync

Cutting a file into blocks so that only changed parts travel, and equal parts are stored once.

Think of moving house with a thousand books. If one book is replaced after the move, the owner does not repack the whole library. A numbered box system lets the owner swap one box.

The book "System Design Interview" uses this idea in its design of a cloud drive. Block servers take a file from the client, split it into blocks, compress each block and encrypt it, then upload the blocks to storage. For the block size, the book takes Dropbox as a reference, with a maximum of 4 MB. Each block has a unique hash value stored in the metadata database. To rebuild a file, the blocks are joined in their order.

Chunk (block) and content hash

A chunk is a fixed-size piece of a file. A content hash is a short fingerprint computed from the bytes of the chunk, so that equal bytes give equal fingerprints and different bytes almost certainly give different ones.

Example: a 100 MB file cut into 4 MB chunks gives 25 chunks. Each gets a fingerprint such as 9f3a....

Delta sync

Delta sync uploads only the chunks that changed since the last version.

Example: after a small edit, 2 of a file's 25 chunks differ. Only those 2 are sent.

A worked example. A user edits a 100 MB file by changing a paragraph in the middle.

  • Without delta sync: all 100 MB are uploaded.
  • With delta sync: the client hashes its 25 chunks and compares them with the stored hashes. Chunks 11 and 12 differ, since the edit straddles a boundary. Upload 2 × 4 MB = 8 MB.
  • Saving: 92 MB, or 92 percent.
  • On a 10 Mbit/s link (1.25 MB per second), 100 MB takes 80 seconds and 8 MB takes 6.4 seconds.

A caution: if the editor inserts bytes at the start of the file, every following chunk shifts by that amount, and with fixed-size chunks every chunk after the edit looks changed. Some systems use content-defined boundaries to avoid this. The book's design keeps fixed sizes for simplicity.

Hashes also allow deduplication: keeping one copy of equal chunks.

A worked example. Two users upload the same 100 MB installer.

  • The second client sends only the hashes of its 25 chunks. The server says that all 25 already exist.
  • No bytes are uploaded. Storage grows by 0, instead of 100 MB.
  • With 1,000 users holding the same file: stored once, 100 MB, instead of 100,000 MB (100 GB).

This saves space and time, but has privacy side effects: the answer "already stored" tells the client that someone has this file. Many services scope deduplication to a user or an account for that reason.

Large uploads can fail halfway. The book mentions resumable upload for large files on poor networks:

  1. The client asks for a resumable upload address.
  2. It uploads the data and watches the state.
  3. If the upload is interrupted, it asks where the upload stopped and resumes from there.

With chunks, resuming is natural: the server knows which chunks arrived, and the client sends the rest. For a 2 GB file in 4 MB chunks (500 chunks), a break after 380 chunks resumes with 120 chunks, not 500.

Compression and encryption belong before upload. The book notes that compression depends on the file type: text compresses well, and images and videos need special algorithms. Files must be encrypted at rest according to the book's requirements.

Technique Saves Costs
Chunking with hashes Lets the system see which parts changed Hash work, chunk table in the metadata
Delta sync Bandwidth and time Hashing on the client
Deduplication Storage Privacy care, reference counting
Resumable upload Retries on poor networks State on the server
Compression Bytes sent and stored CPU

Check yourself:

  • A file has 40 chunks of 4 MB, and 3 of them changed. How many MB does delta sync upload?
  • Why does deduplication need a count of how many files use each chunk?