How rsync Knows What Not to Send

Change one line in a two-gigabyte log file, run rsync to a server, and it finishes in about a second, having sent a few kilobytes. It did not re-upload the file. That part you probably knew.

Here's the part that's genuinely clever, and that the "rsync only sends changes" summary skips right over. To send only the changed parts, rsync first has to know which parts changed — and the two copies of the file sit on two different machines that have never seen each other's contents. So the real question isn't "how does rsync send only the difference." It's: how do you find the difference between two files that are never in the same place, without sending either one across to compare?

The answer is a small, beautiful algorithm — Andrew Tridgell and Paul Mackerras's rsync algorithm, described cleanly in the docs for openrsync, the OpenBSD team's from-scratch reimplementation. Let's build it up.

The obvious approaches, and why they fall apart

Start with the naive ideas, because seeing them fail is what motivates the real trick.

You could hash both whole files and compare the hashes. That tells you whether the files differ — useless, because you already assume they do, and it tells you nothing about where.

So go finer: chop each file into fixed-size blocks, hash each block, and have the two sides compare block hashes. Send only the blocks whose hashes don't match. This actually works — right up until someone inserts a single byte near the front of the file. That one byte shifts every subsequent byte over by one, so every block boundary lands on different content, every block hash changes, and the algorithm concludes the entire file is different. A one-byte insertion would re-send the whole two gigabytes.

Real edits insert and delete things. An algorithm that only survives in-place changes of the same length isn't good enough. The rsync algorithm's whole job is to find matching regions even when everything after the edit has shifted — and it does it with two ideas working together.

Step 1: the side with the old file describes what it has

The transfer has two roles: the sender has the new, authoritative copy; the receiver has the old copy it wants updated. Counterintuitively, the algorithm starts on the receiver — the side with the stale data.

The receiver takes its existing copy of the file and chops it into fixed-size blocks. (The block size is roughly the square root of the file size — bigger files get bigger blocks — with a floor of 700 bytes.) For each block it computes two hashes: a fast 4-byte checksum, and a strong cryptographic-style hash (MD5 in modern rsync). Then it sends just those hashes across the wire.

Notice what didn't happen: the receiver didn't send the file. It sent a few bytes of hash per block — a compact description of "here's what I already have, block by block." For our two-gigabyte file that's a list of hashes, not two gigabytes of data.

Step 2: the sender slides a window, byte by byte

Now the sender, holding the new file, has to find where the receiver's blocks appear in its version — and crucially, they might appear at any offset, because of those insertions and deletions. So the sender does not chop its file into aligned blocks. Instead it slides a block-sized window along its file one byte at a time, and at every single position asks: "is the fast checksum of this window in the receiver's list?"

A byte-by-byte scan of a two-gigabyte file sounds impossibly expensive — that's billions of positions. Here's the trick that makes it cheap: the fast checksum is a rolling hash. When the window slides forward by one byte, you don't re-hash the whole window. You take the previous checksum, subtract the contribution of the byte that just left the window, add the contribution of the byte that just entered, and you have the new checksum in a couple of arithmetic operations:

window at offset i:    [ b₀ b₁ b₂ … b₇ ]   → checksum C
slide one byte right:  remove b₀, add b₈   → checksum C' in O(1)
window at offset i+1:     [ b₁ b₂ … b₇ b₈ ]

That O(1) update is the hinge of the whole algorithm. Without it, a byte-by-byte search would be hopeless; with it, the sender can check every offset in one efficient pass.

Step 3: two hashes, because fast is cheap but lies

Why two hashes per block? Because the fast rolling checksum is, well, fast — but it's only four bytes and it collides. Lots of windows will accidentally share a fast checksum with a real block without actually matching.

So the fast hash is a filter, not a verdict. When the sender finds a window whose fast checksum matches one in the receiver's list, it has a candidate. Only then does it compute the slow, strong hash of that window and compare it to the block's strong hash. If both match, it's a real block the receiver already has. If the strong hash disagrees, it was a fast-hash collision; the sender shrugs and slides on.

Hash	Size	Speed	Job
Rolling checksum	4 bytes	cheap at every byte (it rolls)	quickly reject the ~99.99% of offsets that can't match
Strong hash (MD5)	16 bytes	computed only on a candidate	confirm a real match with near-certainty

Cheap everywhere, certain where it counts. That division of labor — a fast filter backed by a slow confirmer — is the pattern that makes the byte-by-byte scan practical.

Step 4: send the gaps, point at the rest

Once the sender is scanning and matching, the actual transfer is almost an afterthought. As it slides along, it accumulates the bytes that don't belong to any known block — the genuinely new data. When it finally hits a window that matches one of the receiver's blocks, it sends two things: the run of literal new bytes it has accumulated, followed by a short reference — "and now copy block number 4,217, which you already have."

The receiver reconstructs the file by replaying those instructions: write the literal bytes it was sent, then copy the referenced block out of its own old copy, then the next run of literals, then the next block reference, and so on to the end. The new file is rebuilt from a trickle of changed bytes plus a lot of "copy that piece you already had." When it's done, rsync hashes the whole reconstructed file and checks it against the sender's, so a freak collision can never leave you with a silently corrupt copy.

If the file doesn't exist on the receiver at all, there's nothing to match against, so the sender just streams the whole thing — the one case where rsync sends everything, and correctly so.

Watch it on a tiny file

It's easier to believe with something you can hold in your head. Say the receiver's old file is:

the quick brown fox jumps

and the sender's new file is:

the quick red fox jumps

The receiver chops its copy into blocks and sends their hashes. The sender slides its window along the new file. The head, the quick, matches a block — so the sender notes "copy that block" and sends none of it. Then comes red, which matches nothing; those four bytes accumulate as literals. Then fox jumps matches a block again — "copy that one too." What actually crosses the wire is: the literal bytes red, plus two "copy block N" references. The unchanged head and tail — most of the file — are never sent; the receiver already has them and copies them out of its own old file. Scale that from a sentence to a two-gigabyte log with one edited line, and you have rsync's whole value in one picture.

Why the sliding window is the entire point

Step back and you can see why the byte-by-byte slide, expensive as it sounds, is non-negotiable. Insert a byte at the front of the file and every block boundary in the receiver's chopped-up version now sits one byte off from where the matching content lives in the sender's file. A block-aligned comparison would match nothing. But the sender isn't aligned to anything — its window is sliding past every offset, so it simply finds each original block again, one byte to the right of where it used to be. The shift that defeats the naive approach is invisible to a sliding window.

That's the property that lets rsync send a few kilobytes after you edit one line of a huge file, even though that edit nudged everything after it. You can watch it happen with --stats:

$ rsync -a --stats huge.log server:/backup/
...
Total bytes sent: 11,184
Total bytes received: 412
Total file size: 2,000,000,000 bytes
speedup is 172,711.30

Two gigabytes of file, eleven kilobytes on the wire. The "speedup" is just the file size divided by what actually crossed the network.

Why you need rsync on both ends

One thing the algorithm makes clear: rsync isn't one program talking to a dumb file server. It's two copies of rsync talking to each other. When you run rsync local/ host:dest/, rsync opens an ssh connection, starts another rsync on the remote, and the two negotiate — one as sender, one as receiver — exchanging block hashes and deltas over that connection. That's why the remote host needs rsync installed too, and why a badly mismatched version on the far end can cause trouble. The whole thing is a conversation between two peers, each holding one copy of the file — which is exactly why neither side ever has to hand the other its whole file to find what they have in common.

The flags that change what gets sent

Once you know the algorithm, rsync's flags read differently — most of them are knobs on the steps above.

• -c / --checksum changes Step 1's "should I even bother" test. By default rsync skips a file when its size and modification time match; -c compares full-file checksums instead, catching a file that changed without its mtime changing — at the cost of reading both copies in full.
• -W / --whole-file turns the delta off and just copies the file. rsync already does this automatically when both ends are local, because the rolling-hash CPU cost isn't worth paying when there's no slow network to save.
• -z / --compress compresses the literal bytes the delta produces, on top of the delta — savings stacked on savings, worth it over a slow link.
• --partial / -P keeps a partially transferred file instead of throwing it away, so an interrupted transfer resumes from where it stopped rather than starting over.
• --inplace writes the reconstructed data straight into the destination file instead of building a new copy and renaming it — handy for very large files where you can't spare a second copy's worth of disk, at the cost of the safe atomic swap.

Each one is just a different answer to "given the algorithm, what should we do here?"

What it costs, and where the idea went

None of this is free. rsync pays for that tiny transfer with CPU: the receiver hashes its whole file into blocks, and the sender computes a rolling checksum at every byte offset and a strong hash on every candidate. It is trading bandwidth for computation — which, across a slow or metered network link, is almost always the trade you want. (It's also why rsync over localhost, where bandwidth is free, can be slower than a plain copy: you're paying the CPU and saving a network cost that wasn't there.)

The deeper reason this is worth understanding is that the idea is everywhere now, not just in rsync. Content-defined chunking and rolling hashes are how zsync updates ISOs over plain HTTP, how backup tools like restic and Borg deduplicate across snapshots, how casync ships OS images, and how a dozen sync-and-dedup systems avoid moving data they already have. They are all answering Tridgell's original question — how do you find what two datasets have in common without putting them in the same place — and most of them reach for the same answer he published in 1996: hash it cheaply, slide a window, confirm the matches, and send only the gaps. Once you've seen the trick in rsync, you start seeing it everywhere, which is the nicest thing a thirty-year-old algorithm can do for you.