Summary

  • In Tridgell and Mackerras's original rsync algorithm, the receiver divides its existing file into blocks and sends two checksums per block. The sender searches the new file at every offset, then sends references to reusable receiver blocks and literal data for unmatched spans.
  • The project's implementation account describes the other side of the bargain: checksum search costs sender CPU, reconstructing from the old file costs receiver disk work, and a final whole-file checksum checks the result. The cheap link was not a free computation.

The receiver mailed a list of what it owned

Picture two copies of a large file on opposite ends of a slow connection. The source has the version that should win. The destination already has most of its contents, perhaps with a paragraph inserted near the front. A simple copy sends the entire source file again. A fixed position comparison also suffers: after that insertion, much of the unchanged text has moved to a new offset. The original rsync report starts from this practical asymmetry. The two full files are separated by the link, so neither machine can cheaply compute an ordinary local diff.

The surprising first move belongs to the destination. It cuts its existing file into non-overlapping blocks and computes a small rolling checksum and a stronger checksum for each block. It sends those summaries to the source. In the original description, the weak checksum was 32 bits and the strong one was an MD4 digest. Those numbers describe the historical design; the important mechanism is the two-stage test. The sender now knows enough about the destination's pieces to search for them without receiving the destination file itself.

The source scans its desired file for those pieces. If it finds a block the destination already holds, it can send a block reference rather than those bytes. If no existing block matches, it sends the new bytes literally. The receiver rebuilds the desired file from its old pieces and the new material. Checksums and block indexes also cross the link, so the traffic is not only the differences. On the low-bandwidth, high-latency connection described by the authors, that overhead can be much smaller than retransmitting a largely unchanged file.

The checksum had to move one byte at a time

The key was not simply putting checksums on old blocks. If the source inspected only matching block positions, an inserted sentence could shift everything after it and destroy the apparent match. The source must look for a destination block at every byte offset in its own file. Naively calculating a fresh checksum of a whole block at every position would be costly.

The report's rolling-checksum section describes the trick: when the scan moves forward one byte, the next weak checksum can be updated from the previous one by removing the outgoing byte and including the incoming byte. A weak match triggers the more expensive strong check. The search section adds a hash-table stage before those comparisons. This lets a source discover matching content even when the content moved to another position. The computer sweats over arithmetic so the narrow wire does not carry an entire book again.

The report also describes overlapping communication with computation. Once the sender finds a match, it can transmit the unmatched run and the block index while it continues searching. The original algorithm needs one round trip to exchange the block summaries and reconstruction instructions. That mattered when latency was part of the price of every conversation between machines.

The saved bytes had an owner and a cost

The rsync project's practical account names three working roles: a generator on the receiving side decides which files need attention and sends checksums for an existing basis file; the sender scans the source; the receiver assembles the result. The sender does the most checksum search and is CPU intensive. The receiver may read scattered pieces of the old file while writing a new temporary file, making it disk intensive. A whole-file checksum is compared at the end; if the assembled file fails that check, it is discarded and the transfer can be retried.

This description also warns against treating the efficient wire format as an elegant general protocol. The stream has few explicit packet boundaries and depends heavily on context and protocol version. That saves overhead but makes the exchange hard to document, debug and extend. The project's own documentation says so. Those are implementation costs of the same discipline that spared a slow connection.

An update can also be a bad fit for the bargain. A destination with no useful matching blocks has little to reuse. A very fast link paired with slow storage may not reward the extra checksum and disk work. The original report framed its best case as similar files across a slow connection, not as a universal claim that every transfer should be a delta.

The clever part was a change in who spoke first

The source knew what the finished file should be. The receiver knew which old pieces were already close at hand. rsync let the receiver describe those pieces before the source chose what to send. That changed the order of information across the link and made the source's search possible without collecting both entire files at one machine.

The result was a compact delivery plan: reuse this block, then that one, and carry these genuinely new bytes. The receiving machine still had to assemble and verify the file. The history of rsync is often told as a triumph of sending less; the original design was more specific. It spent local computation, storage access and protocol complexity to buy back scarce network capacity. The parcel company avoided hauling the whole library, but both warehouses had to sort the shelves.