Insert some data near the beginning of a file, and the unchanged material after it moves. Rsync, released by Andrew Tridgell and Paul Mackerras in 1996, can find matching blocks at their new positions, allowing two computers to synchronize files without transmitting all that material again.
The key trick is that the receiving computer does not have to send its entire old file back for comparison. It sends compact descriptions of blocks it already holds. The sending computer searches for those blocks in the new file and returns instructions for rebuilding it.
That saves communication by spending resources elsewhere: computing checksums, searching the source and reading existing data at the destination.
A file transfer without both files in one place
On June 19, 1996, Tridgell announced that he and Mackerras had released a package called rsync. The announcement described an update algorithm that could send differences between source and destination files without requiring both sets of files to be available at one end of the connection.
This mattered particularly over a slow link. If much of a file was already present at the destination, sending it again consumed bandwidth without providing new content. But knowing that two files were similar was not enough: the sender needed a way to identify which existing pieces the receiver could reuse.
Their technical report describes the solution in terms of two files. The receiver holds an old file; the sender holds the version it wants the receiver to obtain. Rather than request a complete copy of the old file, the sender receives a list of block checksums—values computed from the contents of each block.
The receiver describes blocks; the sender searches positions
In the report’s algorithm, the receiver divides its file into fixed-size, non-overlapping blocks, with a potentially shorter final block. For each block, it computes a weak rolling checksum and a stronger checksum, then sends those values to the sender.
The important asymmetry is where the sender searches. It looks for matches at any byte offset in its own file, rather than only at the boundaries used to divide the receiver’s file.
Consider an illustrative edit: a new paragraph is inserted near the beginning of a document. Comparing only blocks at identical positions would pair later old material with different new material, because the insertion shifted the contents. Searching at other offsets lets the sender find reusable blocks after that shift.
This example explains the mechanism; it is not a benchmark or a promise that every edit preserves every block. New or changed material still needs to be sent, and matching depends on the blocks available in the receiver’s existing file.
A rolling checksum makes the search practical
Searching every possible position sounds expensive if each candidate requires recalculating a checksum over an entire block. The rolling checksum avoids repeating that whole calculation when the search window advances by one byte.
Given the current checksum, the byte leaving the window and the byte entering it, the algorithm can cheaply compute the next checksum. It can therefore scan across the source file while maintaining a checksum for the moving window.
The weak checksum acts as an initial filter. When it matches a block description from the receiver, the sender calculates the more expensive strong checksum to check the candidate further. The historical report specifies a 32-bit rolling checksum and a 128-bit MD4 (Message Digest 4) checksum; those details describe that report, rather than every later implementation.
Norman Ramsey’s independent implementation makes the separation explicit: one interface provides cheap rolling checksums, another provides fingerprints for checking candidate blocks. Finding a cheap candidate and checking it more thoroughly are different jobs.
The result is a reconstruction recipe
Once matches are found, the sender transmits a sequence of instructions. An instruction either refers to a block already present in the receiver’s file or contains literal data that must cross the connection.
The receiver follows those instructions to construct the new file in order. For a block reference, it reads the corresponding existing data. For literal data, it writes the bytes received from the sender.
This is more precise than saying that rsync sends only changed bytes. The transfer also includes block descriptions and references, while unmatched sections travel as literal data. The saving comes from replacing matching content with instructions to reuse it.
The project’s practical overview describes a receiver building a temporary file from those two sources, checking the completed file and then replacing the existing version. It also cautions that its explanation simplifies implementation details and exceptions.
The network saving has a local cost
Reusing old data does not eliminate work. The sender must compute checksums and search for matches. The receiver must read matching blocks from its existing file and write the reconstructed output.
The practical overview identifies checksum generation and searching as substantial processor work. On the receiving side, reading old blocks while writing a new file can become expensive when the working data exceeds the disk cache and requires repeated disk seeks.
The design therefore exchanges one resource for others. A slow connection makes avoided transmission valuable; local computation and storage access determine part of the price. The mechanism alone does not establish a universal speed advantage.
Rsync’s enduring idea is visible in its reconstruction recipe: describe what the other computer already has, locate it even after it moves, and send instructions to reuse it.
Related stories
Sources
- Andrew Tridgell — First release of rsync: rcp replacement, June 1996
- Andrew Tridgell and Paul Mackerras — The rsync algorithm
- Andrew Tridgell and Paul Mackerras — Rolling checksum
- Rsync project — How Rsync Works: A Practical Overview
- Norman Ramsey — The Rsync Algorithm: an independent implementation
- Featured image: Mk2010; Wikimedia Commons; CC BY 4.0 (adapted from the original)
SIGNAL TITANS
Leave a Reply