How rsync Solved the Bandwidth‑vs‑Difference Deadlock with Rolling Checksums

When a 10 GB file is edited on a Beijing server and rsync is run, the updated data appears on a Shanghai server within seconds, which seems impossible given typical network speeds. The naive expectation that the difference must be known before any data is transferred creates a classic deadlock: to save bandwidth you need the diff, but to compute the diff you must first transfer the whole file.

The article uses a vivid telegraph‑machine analogy: two archivists each hold a 2400‑page book and can only exchange characters at a cost of one cent per character. Sending the entire book would cost 200 000 CNY, while sending only the first and last character of each page (4800 characters) costs 480 CNY. By comparing these “index” characters page by page, they can identify unchanged pages and only transmit the changed ones, reducing cost dramatically.

However, this page‑level index fails when pages are inserted or deleted, because page numbers become misaligned. To handle arbitrary insertions, the algorithm switches to a finer granularity: each page is split into overlapping 500‑character blocks, and a digital fingerprint (hash) is computed for every block.

Two types of fingerprints are used:

Weak fingerprint : a 32‑bit rolling checksum that can be updated in O(1) time when the window slides by one byte.

Strong fingerprint : a 128‑bit MD4 hash that virtually eliminates collisions.

The rolling checksum updates as follows:

a_new = a_old - X_k + X_{l+1}

b_new = b_old - (window_length) * X_k + a_new

Because both updates are constant‑time, the algorithm can slide the window across the entire file without recomputing from scratch.

rsync’s process consists of three steps:

Receiver side (β) : splits the old file into fixed‑size blocks, computes both weak and strong fingerprints for each block, and sends the fingerprint list (≈ 77 KB for a 10 MB file) to the sender.

Sender side (α) : slides a 500‑byte window over the new file, computes the weak fingerprint for each position, looks it up in the receiver’s list, and when a match is found, verifies it with the strong fingerprint. If both match, the block is identical; otherwise the new data is transmitted.

Receiver side again : reconstructs the new file by copying matching old blocks and inserting the newly transmitted fragments.

This double‑filter design (weak then strong) dramatically reduces work: in a test with a 24 MB Linux kernel tarball, the weak checksum produced 620 000 candidate matches, but only 4.7 × 10⁴ were true matches, and the strong checksum rejected all but 64 false positives.

To avoid idle waiting, rsync pipelines the two phases: the receiver continuously streams fingerprint data while the sender simultaneously processes matches and sends reconstruction commands, keeping both network directions busy.

Overall, rsync introduced a third paradigm for remote file synchronization—transmit only fingerprints and the mismatched fragments—replacing the earlier approaches of sending the whole file or requiring both copies locally. Its genius lies in recombining existing primitives (rolling checksum, MD4, hash tables) in a way that updates checksums incrementally, turning an O(n²)‑like problem into a practical O(n) solution.