How Rsync Actually Syncs Files by Sending Only the Diff

Quick Answer

Rsync avoids re-sending a whole file by having the receiver checksum the blocks of its old copy, sending just those small checksums to the sender, who then slides a window across the new file to find which byte ranges already match a known block versus which bytes are genuinely new. We built and ran a real Python version of this: on a 200,163-byte test file with a 163-byte insertion in the middle, only 8,495 bytes actually needed to cross the wire — a 95.8% reduction versus sending the whole file, verified by reconstructing the file and checking it matched byte for byte.

The Problem Rsync Solves

The naive way to sync a file to a remote machine is to send the whole file, every time, even if only a few bytes changed. For a 2 GB file where you edited one paragraph, that's an enormous waste. Rsync, designed by Andrew Tridgell and described in his 1996 thesis, solves this with an algorithm that transfers only the parts of the file that actually changed — and it does this without requiring the sender to already know what changed. The sender doesn't diff the old and new file directly (it may not even have the old file); instead, the receiver, which already has the old version, tells the sender what it already has, and the sender figures out from that what's new.

The hard part is that a simple insertion or deletion shifts every byte after it. If you insert one sentence at the start of a 10 MB text file, a naive byte-by-byte comparison ("does byte 500,000 of the old file equal byte 500,000 of the new file?") would report almost the entire rest of the file as "different," even though every byte of content after the insertion point is identical, just shifted. Rsync's algorithm is specifically designed to still recognize that shifted content as unchanged.

The Two Checksums: Weak and Rolling vs. Strong

Rsync's trick is using two different kinds of checksum for two different jobs. A weak, rolling checksum (classically an Adler-32-style sum) is cheap to compute and, critically, cheap to update incrementally: sliding a fixed-size window forward by one byte lets you recompute the checksum in constant time from the old checksum, without re-reading or re-summing the whole window from scratch. This cheapness is what makes it feasible to check every single byte offset in the new file as a candidate block boundary, not just the boundaries that happen to line up with the old file's fixed block grid.

The weak checksum is fast but not collision-proof — two genuinely different blocks of bytes can produce the same weak checksum by coincidence. So whenever the weak checksum of the current window matches something in the receiver's table, rsync computes a strong, cryptographic checksum (historically MD4, and real rsync lets you choose the algorithm) of that same window and confirms it actually matches before trusting it enough to skip sending those bytes. Weak checksum narrows down candidates cheaply; strong checksum confirms correctness before anything is skipped.

The Algorithm, Step by Step

Putting the two checksums together, the full exchange looks like this:

1. The receiver (which holds the old version of the file) splits it into fixed-size blocks and computes both a weak and a strong checksum for every block.
2. The receiver sends just this list of checksums to the sender — a small amount of data compared to the file itself, since it's one weak+strong checksum pair per block, not the block contents.
3. The sender (which holds the new version) slides a window the same size as one block across the new file, one byte at a time, computing the rolling weak checksum at every offset.
4. Whenever a weak checksum matches an entry in the receiver's table, the sender confirms with the strong checksum. If it's a real match, the sender emits a short "copy this range from your old file" instruction instead of the actual bytes, and jumps the window forward a full block length. If there's no match, the current byte is added to a "literal" buffer of genuinely new data, and the window advances by just one byte.

Because the matching is done by content (what the bytes actually are) rather than by position (what offset they're at), a block of unchanged content that got shifted by an insertion earlier in the file still matches — the sliding window will eventually land on it at its new offset and recognize it, which is exactly the shifted-content problem described above solved for free by this design.

Real Rolling-Checksum Demo in Python, Run for Real

To make this concrete rather than diagrammatic, we implemented the weak and strong checksums and the full matching algorithm from scratch in Python and ran it against a real test case: a 200,000-byte "old" file of random bytes, edited by inserting a 163-byte sentence about 40% of the way through (simulating a real text edit, which shifts everything after the insertion point) to produce a 200,163-byte "new" file. The core pieces:

def weak_checksum(block):
    a, b = 1, 0
    MOD = 65521
    for byte in block:
        a = (a + byte) % MOD
        b = (b + a) % MOD
    return (b << 16) | a

def strong_checksum(block):
    return hashlib.md5(block).hexdigest()

Running the full receiver-indexes / sender-scans algorithm on that real 200,163-byte file produced this actual output:

Old file size: 200,000 bytes
New file size: 200,163 bytes
Bytes actually inserted: 163
Block size used: 512 bytes

Step 1 (receiver -> sender): send checksums for 391 blocks
of the OLD file = 7,820 bytes of checksum data

Step 2 (sender -> receiver): instruction stream
  COPY instructions: 390 (total 199,488 bytes reused, NOT re-transferred)
  LITERAL instructions: 1 (total 675 bytes of genuinely new/shifted data)

Total bytes actually sent (checksums + literal) = 8,495 bytes
Naive full-file transfer would have sent = 200,163 bytes
Bandwidth saved: 95.8%

Reconstruction check: rebuilt file from (old_data + instructions)
is byte-identical to new_data -> PASSED

That last line matters as much as the savings number: the script doesn't just claim the instructions are smaller, it uses them (plus the receiver's own old file) to rebuild the new file byte for byte and asserts the result is identical. A delta algorithm that sends less data but reconstructs the wrong file is worthless, so this check is the actual proof the instruction stream was correct, not just small.

What Real Rsync Does Differently (and Better)

This demo captures the core mechanism, but production rsync adds refinements our simplified version skips. Real rsync chooses its block size based on the total file size (larger files get larger blocks, which keeps the checksum table from growing unreasonably large relative to the file). It lets you pick the strong-checksum algorithm (--checksum-choice) rather than hardcoding one. It compresses the literal data it does send (the -z flag layers gzip on top of the delta transfer, so even the "new" bytes get shrunk further). And it supports resuming interrupted transfers and preserving file metadata (permissions, timestamps, ownership) as part of the same sync operation — none of which is specific to the delta algorithm itself, but all of which is part of why rsync is the tool people actually reach for rather than a reimplementation.

An Honest Note: No Real Rsync Binary in This Environment

Before writing any of the above, we checked whether real rsync was available in this environment to run an actual side-by-side transfer and capture its own --stats output. It isn't — rsync --version returned "command not found." Rather than fabricate what rsync's own reported bytes-transferred would look like, everything numeric in this article comes from the from-scratch Python implementation above, which we did write and actually run, with the reconstruction check as proof the algorithm's output is correct and not just a plausible-looking number. If you have rsync installed locally, running it with -v --stats between two versions of a real file is worth doing yourself to see the same effect from the actual tool.

Where This Algorithm Shows Up Beyond Rsync

The rolling-checksum, content-addressed-block idea generalizes well beyond file-copying over SSH. rdiff and rdiff-backup use the same algorithm to generate and apply binary patches between file versions for backup systems. Block-level sync in consumer cloud-storage clients (uploading only the changed chunk of a large file you edited, rather than the whole file again) is the same core idea applied to upload bandwidth instead of rsync's two-host transfer. Git's packfile delta compression solves a related but distinct problem — representing one blob as a diff against a similar blob to shrink repository storage — using a different specific algorithm, but the same underlying insight that unrelated-looking data often shares long runs of identical content worth finding and not re-storing.

Frequently Asked Questions