The encyclopedia · Software & IT · Technical decision · 1996
rsync updated files over slow links by sending checksums, not data
Tridgell and Mackerras split files into blocks and moved only unmatched parts, so one round trip synced any two similar files.
rsync (Australian National University)
the move
Copying a file over a slow link wastes everything both machines already share. Compression helps only by a factor of two to four, and ordinary diff tools need both files on the same machine, which is exactly what the link makes impossible.
Andrew Tridgell and Paul Mackerras solved it in 1996 with a remote diff: the receiver splits its file into blocks, sends checksums of each block, and the sender, in one pass, finds which of its own blocks match at any offset, using a rolling checksum cheap enough to compute at every byte position. Only unmatched data and references cross the wire.
The design needs only one round trip, so latency barely matters, and it works correctly even when files are quite different. Tridgell announced the tool on June 19, 1996 as an rcp replacement with this remote update algorithm, plus pipelining that overlaps communication with computation.
why it works
- Rolling checksums let the sender scan every offset cheaply
- One round trip makes it fast even on high-latency links
- Strong checksums confirm weak matches before data moves
- Sending only unmatched blocks saves bandwidth in proportion to similarity
what transfers
When bandwidth is scarce and files overlap, send evidence, not data: rolling checksums reveal what already exists at the far end without needing both files in one place.
what came after
rsync became the standard Unix tool for backups, mirrors and software distribution, and its block-checksum diff remains the core of the tool today. The 1996 report is still the reference cited for the algorithm, and the one-round-trip design influenced later sync systems.
references
spotted an error? The archive wants to know.