DEV Community

Vadym Stupakov
Vadym Stupakov

Posted on

The rsync Algorithm Is Brilliant. Why Don't We See It Everywhere?

#cli #computerscience #networking #performance

Most developers know rsync as a command:

rsync -av source/ server:/destination/
Enter fullscreen mode Exit fullscreen mode

It copies files. It resumes transfers. It avoids transferring unnecessary data.

But underneath the familiar CLI is a much more interesting idea: the rsync algorithm can synchronize two similar files without sending either entire file across the network.

It was designed for a world where bandwidth was expensive.

The surprising part is that, decades later, we don't see the exact algorithm used very often outside rsync.

Why?

To answer that, we need to separate rsync the tool from rsync the algorithm.

The Problem

Imagine two machines.

The receiver has:

old.bin
Enter fullscreen mode Exit fullscreen mode

The sender has:

new.bin
Enter fullscreen mode Exit fullscreen mode

Both files are 10 GB.

Only 20 MB actually changed.

The obvious solution is:

send new.bin
Enter fullscreen mode Exit fullscreen mode

That's 10 GB of network traffic.

Another possibility is:

sender gets old.bin
sender computes diff(old.bin, new.bin)
sender sends patch
Enter fullscreen mode Exit fullscreen mode

But now the receiver must upload its 10 GB file first.

That defeats the purpose.

The rsync algorithm solves a more interesting problem:

How can the sender discover which parts of new.bin already exist inside old.bin without receiving old.bin?

Step 1: The Receiver Creates Signatures

The receiver divides its file into blocks.

For example:

old.bin

[ block 0 ]
[ block 1 ]
[ block 2 ]
[ block 3 ]
...
Enter fullscreen mode Exit fullscreen mode

For every block it calculates two checksums:

block 0 -> weak checksum + strong checksum
block 1 -> weak checksum + strong checksum
block 2 -> weak checksum + strong checksum
...
Enter fullscreen mode Exit fullscreen mode

The weak checksum is cheap and, crucially, can be updated incrementally.

The strong checksum is much more resistant to collisions and is used to verify a candidate match.

The receiver sends these signatures to the sender.

It does not send the file itself.

Step 2: The Sender Searches Its File

The sender now has new.bin and a compact description of the receiver's blocks.

Suppose the block size is four bytes.

The sender can examine:

ABCD
Enter fullscreen mode Exit fullscreen mode

then:

 BCDE
Enter fullscreen mode Exit fullscreen mode

then:

  CDEF
Enter fullscreen mode Exit fullscreen mode

and so on.

Normally, calculating a checksum for every possible window would be expensive.

But rsync uses a rolling checksum.

If we already know the checksum of:

ABCD
Enter fullscreen mode Exit fullscreen mode

we can efficiently derive the checksum of:

BCDE
Enter fullscreen mode Exit fullscreen mode

by removing the contribution of A and adding E.

Conceptually:

checksum(ABCD)
      |
remove A
add E
      |
checksum(BCDE)
Enter fullscreen mode Exit fullscreen mode

The update is O(1).

This means rsync can efficiently slide through the new file looking for blocks that exist on the receiver.

Step 3: Weak Match, Strong Verification

A weak checksum is fast, but collisions are possible.

So rsync does something clever:

rolling checksum
      |
      v
possible match?
      |
     yes
      |
      v
strong checksum
      |
      v
actual match?
Enter fullscreen mode Exit fullscreen mode

The cheap operation runs constantly.

The expensive operation runs only when necessary.

This pattern is useful far beyond file synchronization:

Use a cheap approximate test to find candidates, then use an expensive reliable test to verify them.

Step 4: Send Instructions Instead of the File

Suppose the sender discovers that most of its file already exists on the receiver.

Instead of sending the entire file, it can send something conceptually like:

COPY block 0
COPY block 1

LITERAL <new bytes>

COPY block 3
COPY block 4
COPY block 5
Enter fullscreen mode Exit fullscreen mode

The receiver reconstructs the new file using its existing data plus the new bytes.

If a 10 GB file changed by only 20 MB, the network transfer can therefore be dramatically smaller than 10 GB.

That is the magic of rsync.

Why Not Just Compare Blocks?

You might wonder why we need the rolling checksum at all.

Why not simply split both files into 4 MB blocks and compare their hashes?

Consider inserting one byte at the beginning.

Old:

[AAAA][BBBB][CCCC][DDDD]
Enter fullscreen mode Exit fullscreen mode

New:

X[AAA][ABBB][BCCC][CDDD]...
Enter fullscreen mode Exit fullscreen mode

Every fixed block boundary has shifted.

A normal block-hash comparison now makes the files look almost completely different.

But the actual data is almost identical.

Rsync searches for the old blocks at any offset.

After seeing the extra X, it can eventually discover:

AAAA
BBBB
CCCC
DDDD
Enter fullscreen mode Exit fullscreen mode

inside the new byte stream.

The rolling checksum makes that search practical.

So Why Isn't the rsync Algorithm Everywhere?

This is where things get interesting.

The algorithm solves a very specific problem:

Two machines contain similar data, bandwidth matters, and the sender does not already have the receiver's version.

Many modern systems don't actually have this problem.

They have easier problems.

And easier problems often have better solutions.

Git Doesn't Need rsync

Git already models data using content hashes.

Very roughly:

blob   -> hash
tree   -> hash
commit -> hash
Enter fullscreen mode Exit fullscreen mode

If both machines know object IDs, they can negotiate which objects are missing.

Instead of asking:

Which regions of this file happen to exist on the other machine?

Git can ask:

Which objects do you already have?

Git also uses delta compression in packfiles, but that's a different layer of the problem.

The architecture already provides information rsync has to discover dynamically.

This illustrates an important principle:

A clever synchronization algorithm can become unnecessary if your data model makes identity explicit.

Software Updates Have an Easier Problem

Suppose you're distributing an application.

The server may have:

version 1.0
version 1.1
Enter fullscreen mode Exit fullscreen mode

It can calculate:

diff(version_1_0, version_1_1)
Enter fullscreen mode Exit fullscreen mode

ahead of time.

Then users with version 1.0 download only the patch.

Algorithms and formats such as binary delta encoding can be optimized specifically for this situation.

Rsync solves something harder:

sender has NEW
receiver has OLD

sender does NOT have OLD
Enter fullscreen mode Exit fullscreen mode

If the server already has both versions, there is often no reason to pay the complexity cost of rsync's remote block discovery.

Then Came Content-Defined Chunking

This is perhaps the most interesting descendant of the same family of ideas.

Modern backup and deduplication systems often use content-defined chunking, or CDC.

Instead of saying:

split every 4 MB
Enter fullscreen mode Exit fullscreen mode

they determine chunk boundaries from the content.

Conceptually:

data stream
    |
rolling fingerprint
    |
boundary condition
    |
    v
chunk
Enter fullscreen mode Exit fullscreen mode

You might end up with:

[ 2.8 MB ][ 5.1 MB ][ 3.7 MB ][ 4.4 MB ]
Enter fullscreen mode Exit fullscreen mode

The chunks aren't the same size.

Their boundaries depend on their contents.

Why Content-Defined Chunking Is Powerful

Consider inserting some data near the beginning of a file.

With fixed-size chunks:

OLD:

[AAAA][BBBB][CCCC][DDDD]

NEW:

X[AAA][ABBB][BCCC][CDDD]...
Enter fullscreen mode Exit fullscreen mode

Everything becomes misaligned.

With content-defined chunking, the insertion temporarily disturbs the boundaries:

OLD:

[ chunk A ][ chunk B ][ chunk C ][ chunk D ]

NEW:

[ changed... ][ chunk B ][ chunk C ][ chunk D ]
Enter fullscreen mode Exit fullscreen mode

Eventually the rolling fingerprint encounters the same content and starts selecting the same boundaries again.

The streams resynchronize naturally.

This makes CDC extremely useful for:

  • backup systems
  • deduplication
  • content-addressed storage
  • distributed storage
  • container/image storage
  • large artifact stores

The important idea escaped rsync.

The exact protocol usually didn't.

rsync vs Content-Defined Chunking

The two ideas look similar but solve somewhat different problems.

rsync Content-defined chunking
Main goal Remote synchronization Stable chunk identity
Boundaries Receiver's fixed blocks Determined by content
Rolling function Search for matching blocks Find chunk boundaries
Needs old file on sender No Depends on system
Great for Ad-hoc remote files Deduplication/storage
Persistent chunk index Not required Usually useful

Rsync asks:

Where does this receiver block occur in my file?
Enter fullscreen mode Exit fullscreen mode

CDC asks:

Where should this content naturally be divided?
Enter fullscreen mode Exit fullscreen mode

Similar machinery.

Different architecture.

The Network Also Changed

When rsync was created, network bandwidth was much more precious relative to CPU and storage.

Today we frequently have:

1 Gbit/s LAN
10 Gbit/s LAN
fast datacenter networks
CDNs
cheap object storage bandwidth
Enter fullscreen mode Exit fullscreen mode

Meanwhile, computing millions of hashes, maintaining indexes, performing random reads, and implementing complicated synchronization protocols isn't free.

Sometimes:

just send the file
Enter fullscreen mode Exit fullscreen mode

really is the better engineering decision.

Especially when files are small.

Encryption and Compression Make Things Worse

Rsync works best when similar logical content produces similar bytes.

Compression destroys much of that property.

A small modification to uncompressed data can change a large portion of a compressed stream.

Encryption is even more hostile to byte-level similarity.

Ideally:

similar plaintext
Enter fullscreen mode Exit fullscreen mode

should produce:

completely unrelated ciphertext
Enter fullscreen mode Exit fullscreen mode

So synchronizing:

database.gz
backup.tar.zst
encrypted-volume.img
Enter fullscreen mode Exit fullscreen mode

may provide much less opportunity for rsync-style matching than synchronizing the underlying uncompressed data.

Modern systems often solve this by moving deduplication before compression or encryption.

For example:

files
  |
CDC
  |
chunks
  |
deduplicate
  |
compress
  |
encrypt
  |
storage
Enter fullscreen mode Exit fullscreen mode

Architecture beats trying to recover similarity afterward.

The Bigger Lesson

The fascinating part of rsync isn't really rsync -av.

It's the decomposition of the problem:

cheap rolling checksum
        |
candidate detection
        |
strong verification
        |
delta instructions
        |
minimal network transfer
Enter fullscreen mode Exit fullscreen mode

The complete protocol remains particularly useful when:

sender has new file
receiver has similar old file
sender doesn't have old file
bandwidth is expensive
Enter fullscreen mode Exit fullscreen mode

That's a narrower situation than it initially appears.

But the underlying ideas are very much alive.

Modern systems use:

              rolling fingerprints
                      |
        +-------------+-------------+
        |                           |
        v                           v
      rsync                       CDC
        |                           |
remote block discovery      stable chunk boundaries
        |                           |
        v                           v
delta transfer          dedup / backup / CAS
Enter fullscreen mode Exit fullscreen mode

So perhaps the right conclusion isn't:

"Why did nobody reuse the rsync algorithm?"

It's:

They reused the important ideas and changed the architecture around them.

And that's often what happens to great algorithms.

The original implementation becomes associated with one famous tool, while its ideas quietly become building blocks for the next generation of systems.

Top comments (0)