DEV Community: Vadym Stupakov

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

Vadym Stupakov — Mon, 19 Oct 2026 18:44:27 +0000

Most developers know rsync as a command:

rsync -av source/ server:/destination/

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

The sender has:

new.bin

Both files are 10 GB.

Only 20 MB actually changed.

The obvious solution is:

send new.bin

That's 10 GB of network traffic.

Another possibility is:

sender gets old.bin
sender computes diff(old.bin, new.bin)
sender sends patch

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 ]
...

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
...

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

then:

 BCDE

then:

  CDEF

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

we can efficiently derive the checksum of:

BCDE

by removing the contribution of A and adding E.

Conceptually:

checksum(ABCD)
      |
remove A
add E
      |
checksum(BCDE)

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?

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

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]

New:

X[AAA][ABBB][BCCC][CDDD]...

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

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

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

It can calculate:

diff(version_1_0, version_1_1)

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

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

they determine chunk boundaries from the content.

Conceptually:

data stream
    |
rolling fingerprint
    |
boundary condition
    |
    v
chunk

You might end up with:

[ 2.8 MB ][ 5.1 MB ][ 3.7 MB ][ 4.4 MB ]

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]...

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 ]

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?

CDC asks:

Where should this content naturally be divided?

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

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

Sometimes:

just send the file

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

should produce:

completely unrelated ciphertext

So synchronizing:

database.gz
backup.tar.zst
encrypted-volume.img

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

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

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

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

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.

DatasetRT: Stop Rebuilding Datasets to Rebalance Training

Vadym Stupakov — Fri, 16 Oct 2026 05:29:44 +0000

You’re running another training experiment on the same dataset. The images are
already processed, the features are computed, or the text is tokenized. Millions
of records are sitting on disk, ready to use.

This time, you want to rebalance a rare class. Or exclude low-quality samples.
Or run on 1% of the data while debugging a model change.

You also want your PyTorch loading workers to keep the GPU fed without filling
RAM with copies of dataset metadata.

This article is for ML engineers and researchers who reuse large preprocessed
datasets across training experiments and need to change how those samples are
selected. The examples use Python, Polars, and PyTorch; the cache itself is
independent of the training framework.

The problem becomes familiar once your dataset contains more than just an input
and a target. You might have an image with annotations and preprocessing
outputs, or a tokenized document with several arrays. Loading that whole record
just to check its label or quality score is work your experiment shouldn’t need.

The payloads haven’t changed. Your decisions about which records to train on
have.

That distinction is the starting point for DatasetRT: a Rust-powered dataset cache for Python that keeps serialized samples and their sampling metadata separate.

It lets you change the training population without rebuilding the payload cache.
The useful part is the combination: Python records you already know how to
serialize, separately queryable metadata, native sample reads, and shared mapped
buffers for multiprocessing loaders.

One dataset, two connected parts

Imagine a training record containing an image, its class label, and
arrays produced during preprocessing. Your Python source packs that structure
with pickle or dill.

That record might be large. Its label, split, quality score, and sampling
weight are usually much smaller. Keeping those attributes queryable lets you
ask for more examples of an underrepresented class without unpacking every
image first. The same pattern applies to source categories in tokenized corpora.

DatasetRT keeps both:

Payload store	Metadata table
Serialized sample bytes in indexed disk shards	Sample identities, labels, splits, scores, and weights
Read when training needs a sample	Used to analyze and select the training population
Unpacked by your Python code	Exposed as a Polars DataFrame

A (cache_id, sample_id) identity connects a metadata row to its stored payload.

Polars operates on the metadata. Your pickled records stay in the payload store.

That makes a surprisingly useful question cheap to answer:

“How many examples of each class do I have?”

metadata = dataset.get_metadata()

print(
    metadata.group_by("label")
    .agg(pl.len().alias("samples"))
)

You don’t need to unpickle every training record to count its label.

Changing an experiment shouldn’t mean copying a dataset

Suppose your next training run should exclude low-quality records while keeping
the original cache available for other experiments. With label, split, and
quality stored as metadata columns, the selection is:

selected = (
    dataset.get_metadata()
    .filter(
        (pl.col("split") == "train")
        & (pl.col("quality") >= 0.8)
    )
)

dataset.update_metadata(selected)

The cache files stay unchanged. Future dataset iterators use the selected population.

For a quick development run:

dataset.update_metadata(selected.head(100))

You now have a smaller active dataset backed by the same immutable payloads.

That matters when preprocessing is expensive, storage is large, or experiments keep changing the selection rules. You can express those rules directly instead of maintaining another collection of copied records.

Analyze the metadata. Change the population. Reuse the bytes.

Class balancing becomes a table operation

Consider a dataset with 9,000 examples of one class and 1,000 of another.

With uniform per-record sampling, their expected shares are 90% and 10%.

Assign each record the inverse of its class count:

balanced = selected.with_columns(
    (1.0 / pl.len().over("label")).alias("weight")
)

dataset.update_metadata(balanced)

Each class now has total weight 1, giving them equal expected sampling probability.

Rust validates the accepted identities and weights before applying the update. Payloads remain untouched.

The same mechanism can support hard-example sampling: compute scores in your training workflow, turn them into positive sampling weights, and update the population before creating the next iterator or loader.

One detail deserves explicit attention: shuffled sampling uses replacement. A sample can appear several times while another is absent. Equal expected class probabilities do not guarantee exactly equal class counts in every epoch.

Multiprocessing shouldn’t require another full metadata copy per worker

Once your Python decode or augmentation step becomes a bottleneck, adding
PyTorch loading processes is a reasonable experiment. It also creates another
budget to watch: RAM.

If each worker reconstructs a private metadata table and decoded index, worker count becomes a multiplier on those allocations.

DatasetRT uses read-only, file-backed mmap for the loader’s immutable Arrow metadata snapshot. Workers map the same snapshot, letting the operating system share its backing pages on the same host.

Cache indexes are also mapped from their original files.

This works with spawn: workers open their mappings independently, so sharing does not depend on inheriting a live parent runtime.

There are still private allocations. Weights, sampling state, decoded records, and prefetched batches consume memory per consumer. Separate metadata exports also have separate backing files.

The saving is specific and useful: workers can reference shared metadata and index pages instead of each retaining a complete private copy of those buffers.

Rust handles the sample reads

After selecting a sample, DatasetRT’s native runtime resolves its index entry and reads the payload using native workers and bounded prefetching.

Python receives the serialized bytes and performs application-specific unpacking:

record = pickle.loads(sample.data)

Your source chooses the serialization format. DatasetRT doesn’t need to understand your nested dictionary, tensor layout, or domain object to store and retrieve its bytes.

Keeping that boundary small lets the native reader focus on indexed access, ordering, and bounded work.

Payload size matters when comparing readers: 10,000 small records and 10,000
large images represent very different amounts of work. I measured random
weighted reads plus unpickling, and report the reconstructed image bytes per
second so the amount of work is explicit.

Each cached payload is a pickled dictionary containing a 256 × 256 RGB NumPy
array (uint8), a label, and sample identity. Each reconstructed image occupies
192 KiB. There are 4096 image records across two caches: 768 MiB of image data,
plus pickle headers and the other dictionary fields.

This benchmark uses shuffle=True: weighted multinomial sampling with
replacement, not sequential reading. Four equally populated classes have
per-record weights 1:2:4:8, giving expected draw shares of approximately
6.7%, 13.3%, 26.7%, and 53.3%. Each pass draws 4096 samples; repeats count as
additional reads and reconstructions.

Every delivered record goes through pickle.loads() inside the timed consumer
or loading worker. The benchmark validates the reconstructed image's shape,
dtype, sample identity, and identifying pixels. It does not cache unpacked
records between draws.

These are medians of five trials per configuration, with case order rotated:

Configuration	First pass: image data reconstructed (MiB/s)	Second pass: image data reconstructed (MiB/s)
Native iteration	6657	6767
PyTorch loader, zero loading workers	6669	6808
PyTorch loader, one spawned worker	1313	6604
PyTorch loader, two spawned workers	1337	11954

Measurements used an Apple M5 with 24 GiB RAM, macOS 27.0.1, Python 3.11.15,
PyTorch 2.14.1, and DatasetRT 0.4.6. Each consumer has two native reader threads;
batch size and native prefetch capacity are both 64. Loading workers use spawn,
replicated weighted populations, two prefetched batches per worker, and automatic
persistence between passes. Fresh readers with the same seed and topology
reproduced their sample traces; successive passes continued the sampling stream.

The timer covers iterator creation through exhaustion: sample reading,
unpickling, validation, batching, and consumption. The first-pass figures include
loading-worker startup; the second pass reuses persistent workers. Dataset and
loader construction, imports, fixture creation, and metadata-weight setup are
outside these timers. MiB/s is reconstructed image bytes divided by total pass
time, including first-batch latency; 1 MiB is 1,048,576 bytes. The raw report also
retains serialized-payload byte counts for the steady interval after the first
batch.

The images are synthetic RGB arrays, not photographs or encoded JPEG/PNG
files. Unpickling reconstructs the dictionary and NumPy array; this benchmark
does not include codec decoding, augmentation, GPU transfer, or model execution.
Loading workers send compact validation results back to the parent rather than
full image arrays, so the table does not measure full-image IPC throughput.

The dataset fits in RAM and the filesystem cache is warm. These are logical
read-and-reconstruction rates, including replacement draws—not physical disk
bandwidth. A benchmark of compressed images or a complete training pipeline
would measure a different workload.

The one-worker result is worth keeping in the table. It was slower than the zero-worker baseline. More processes also increased startup time and memory.

Fast native reads give you a useful foundation. Your actual decoding workload determines whether additional Python workers help.

The workflow I wanted

The combination is what makes DatasetRT useful:

Preprocess and serialize records once.
Keep their sampling attributes in a separate metadata table.
Analyze, filter, and reweight that table as experiments change.
Read selected payloads through the Rust runtime.
Share mapped metadata and indexes across loader workers where possible.

There is one deliberate responsibility left with the application: cache reuse follows the source name. If preprocessing or source contents change, use a new source name or cache root. DatasetRT does not automatically fingerprint your preprocessing code.

DatasetRT is worth evaluating when preprocessing is expensive, cached records
are large, and your experiment loop repeatedly changes subsets or sampling
weights. It is especially relevant when multiple loading processes make private
metadata and index copies costly.

If your data is small enough to keep in memory and a simple dataset plus sampler
already does the job, the extra cache layer may buy you little. The intended
user is the person who keeps revisiting the same expensive records and wants the
next experiment to start with a metadata change rather than another data-preparation
job.

Explore DatasetRT on GitHub or install the package:

uv add dataset-rt

git-sfs: Large File Storage Without the LFS Server

Vadym Stupakov — Thu, 07 May 2026 20:42:25 +0000

The Problem

You added a 2 GB dataset to a repo. Now git clone takes 10 minutes, CI downloads the full history on every run, and GitHub is billing you per GB transferred. You switch to Git LFS - and now you need a server, a token, and a storage plan. You try DVC - and now you need Python, a pipeline config, and lock files that conflict on every PR.

None of this is the actual problem. The actual problem is: large files don't belong in Git objects. Everything else is overhead.

Meet git-sfs

SFS stands for Symbolic File Storage. The name is deliberate - it's Git LFS with the L swapped for S. Git LFS replaces large files with opaque pointer files and routes bytes through a proprietary server protocol. git-sfs replaces large files with plain symlinks that Git already understands natively, and routes bytes through rclone to any remote you already have.

No new protocol. No server. No pointer file format to decode. Just symlinks.

How It Works

The model is three sentences:

Git tracks symlinks.
git-sfs stores file bytes.
rclone moves files.

When you run git-sfs add data/train-000.tar.zst, here's what happens:

The file is hashed with SHA-256
Bytes are stored in <cache>/files/sha256/ab/<hash> - write-once, read-only
The original path becomes a relative Git symlink pointing into the cache

data/train-000.tar.zst -> ../.git-sfs/cache/files/sha256/ab/<hash>

data/train-000.tar.zst opens normally. Git commits a 70-byte symlink. Your repo stays fast.

Why Not Git LFS?

Git LFS solves the storage problem but adds a server problem. You need an LFS endpoint, pay per-GB transfer fees on GitHub, and the pointer-file format is an opaque internal detail.

git-sfs remotes are plain rclone destinations - S3, GCS, Azure Blob, Backblaze B2, SFTP, a local path, anything rclone supports. You can rclone ls your remote and see exactly what's there. No magic.

One Binary, No Runtime

git-sfs is written in Go. It ships as a single static binary - no Python environment, no runtime, no version conflicts. Drop it on any machine and it runs.

Quick Start

# Install (macOS/Linux, arm64 and x86_64)
curl -LsSf https://github.com/Red-Eyed/git-sfs/releases/latest/download/install.sh | sh

# Init and configure
git-sfs init        # creates .git-sfs/config.toml
# edit config.toml: set remote backend, path, rclone config
git-sfs setup       # bind local cache

# Add files
git-sfs add data/
git add .git-sfs/config.toml data/
git commit -m "track datasets"

# Sync to remote
git-sfs push

On another machine:

git clone <repo> && cd <repo>
git-sfs setup
git-sfs pull        # download only what you need

You can also pull a subset - useful when one machine only needs validation data:

git-sfs pull data/validation/

Safety by Design

Data loss in a dataset management tool is unacceptable, so git-sfs has a few hard rules:

Hash-verify at every boundary - after hashing, after download, after copy. A corrupted file is rejected, not silently accepted.
Atomic writes - temp file + rename everywhere. An interrupted push or pull never leaves a partial file.
Cache files are immutable - write-once, then write-protected. Accidental overwrites are impossible.

The verify command is designed for CI:

git-sfs verify              # presence check (fast)
git-sfs verify --with-integrity data/  # rehash cached + remote files (thorough)

And doctor checks your entire setup - config, cache, rclone binary, remote connectivity - in one shot:

git-sfs doctor

What's Different from dvc, git-annex, etc.?

Tool	Requires	Remote	PR-friendly?
Git LFS	LFS server	proprietary protocol	✅
DVC	Python, pipelines	S3/GCS/etc via SDK	❌
git-annex	Haskell runtime	many backends	❌
git-sfs	rclone	anything rclone supports	✅

DVC stores large file metadata in .dvc sidecar files and a dvc.lock that encode pipeline state. When two branches touch the same dataset, merging those lock files creates conflicts that have no meaningful resolution in a pull request - reviewers see .dvc diffs, not data diffs, and the merge problem is fundamentally DVC's, not Git's.

git-annex stores its metadata in a separate orphan branch (git-annex). That branch never appears in a normal git log or PR diff, so reviewers have no visibility into what large files changed or why. Merging the annex branch is a separate out-of-band operation that GitHub PRs don't surface at all.

git-sfs tracks only plain relative symlinks. A PR diff shows exactly which files were added, removed, or renamed - the same way any other file change looks in Git. Reviewers can approve or reject dataset changes with full context, and there are no sidecar files or hidden branches to reconcile.

git-sfs has no pipelines, no Python, no manifests, no committed lock files. The Git tree is the file list. The cache is a plain directory. The remote is whatever rclone can reach.

Concurrency and Partial Pulls

Large dataset workflows often mean hundreds of files if not millions. git-sfs runs add, push, and pull with a configurable worker pool:

# .git-sfs/config.toml
[settings]
n_jobs = 8

And partial pulls let teams share a repo where different machines only materialize what they actually use:

git-sfs pull data/train/         # only training split
git-sfs pull data/checkpoints/   # only model weights

Source

The project is open source under MIT: github.com/Red-Eyed/git-sfs

Feedback and issues welcome. If you're managing large files in Git and the LFS server tax is getting old, give it a try.