How rsync Solved the Remote Delta Sync Deadlock with Rolling Checksums

The Core Problem: The Remote Diff Deadlock

Imagine you have a 10 GB file on a server in Beijing and an older version in Shanghai. Running rsync syncs them in seconds, even though transferring 10 GB over a typical WAN would take minutes. The common answer is "rsync only sends differences," but that raises a paradox: to find differences you must compare the two files, yet they are on different machines. Sending the whole remote file to compare defeats the purpose. This is the deadlock rsync had to break.

Analogy: The Telegraph and the Yearbook

The article illustrates the problem with a story: you in Beijing and a colleague in Shanghai each hold a 2,400-page yearbook. You must make the Shanghai copy identical to the revised Beijing copy using only a telegraph that charges per character. Sending the whole book costs ¥200,000; sending the old book to compare then sending diffs costs even more. The challenge is to minimize telegraph cost while guaranteeing correctness.

First Attempt: First/Last Character Index

Ask Shanghai to telegraph the first and last character of each page (4,800 characters, ¥480). Compare with your new edition: if they match, the page is likely unchanged; if not, send the full page. This reduces cost to ~¥10,000. But it fails if a page changes only in the middle while first/last characters stay the same — a silent data corruption.

Second Attempt: Per-Page Strong Hash (MD5)

Replace the weak index with a cryptographic hash (MD5, 16 bytes) per page. Shanghai sends 2,400 hashes (38,400 bytes, a few hundred yuan). You compute hashes for your new pages and compare. This catches any change, but breaks completely if pages are inserted or deleted: all subsequent page numbers shift, causing every later hash to mismatch and forcing a full retransmission.

The Breakthrough: Byte-Level Sliding Window with Rolling Checksum

Tridgell and Mackerras realized that instead of fixed-page boundaries, they could slide a fixed-size window (e.g., 500 bytes) one byte at a time across the new file, computing a checksum at each position and looking it up in a hash table of the old file's block checksums. Any long-enough unchanged region will eventually align with a window and be detected, regardless of insertions/deletions.

The computational cost seemed prohibitive: a 10 MB file with 500-byte blocks yields ~20 million windows; recomputing a strong hash (MD4) per window is too slow. The key insight was a rolling checksum that can be updated in O(1) time when the window slides by one byte.

Rolling Checksum Design (Adler-32 Inspired)

The checksum has two 16-bit parts modulo a prime:

a = sum of all bytes in the window

b = sum of each byte multiplied by its position weight

When the window slides from bytes X_k ... X_l to X_{k+1} ... X_{l+1}:

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

b_new = b_old - (window_length) * X_k + a_new

Both updates are simple arithmetic, turning millions of O(n) hash computations into millions of O(1) updates — a speedup of thousands.

Two-Layer Filter: Weak + Strong Checksums

The rolling checksum is only 32 bits, so collisions are inevitable (birthday paradox). Rsync uses a two-stage filter:

Weak checksum (rolling) — computed at every window position, used as a fast hash-table lookup key. Most non-matching windows are discarded here.

Strong checksum (MD4, 128 bits) — computed only when the weak checksum matches a block from the old file. MD4 collisions are negligible in practice.

In tests on a 24 MB Linux kernel tarball with 500-byte blocks, the weak checksum produced 620,000 candidate matches; only 47,000 were true matches, and the strong checksum rejected just 64 false positives. The strong hash is rarely invoked, keeping CPU usage low.

End-to-End Protocol

Receiver (Shanghai) splits the old file into fixed 500-byte blocks, computes both checksums per block, sends the list (~77 KB for 3,840 blocks).

Sender (Beijing) slides a 500-byte window across the new file one byte at a time, computes the rolling checksum, checks the hash table. On weak-match, computes MD4; if strong-match, emits a "reuse block N" token; otherwise emits literal bytes. After a match, the window jumps to the end of the matched block.

Receiver reconstructs the new file by interleaving received literal data with copies of old blocks referenced by tokens.

Pipeline Optimization

To hide network latency, the receiver runs two concurrent processes: one streaming block checksums to the sender, another consuming the sender's instruction stream and assembling the output file. Both directions of the link are utilized simultaneously, a remarkable engineering foresight for 1996 dial-up links.

Why It's a Masterpiece of Engineering

Rsync invented no new mathematics or cryptographic primitives. It combined existing pieces — rolling checksum, MD4, hash tables — in a novel architecture that transformed an apparently impossible problem (remote diff without remote data) into a practical tool. Before rsync, the only options were full transfer or diff/patch requiring both files locally. Rsync opened a third path: send only fingerprints and mismatched fragments, let the remote end rebuild. The rolling checksum turned a theoretical O(n²) algorithm into a linear-time one, and the dual-checksum filter kept both speed and correctness. Today, rsync underpins countless backup, mirroring, and container-layer systems, moving billions of files daily while typically transferring only ~5% of the data.