The 2% Delta: Why Your Differential Updates Save Nothing

Here’s the pitch every OTA system makes: don’t ship the whole binary, ship the difference. You changed three functions, so send three functions’ worth of bytes. On a fleet connected over NB-IoT at 20–60 kbps, that is the difference between an update that lands and an update that times out for two hours.

I wanted that for Keystone, my edge orchestration agent. So before building anything, I measured it against two real consecutive releases.

The patch came out at 13.1 MB. The full artifact was 13.4 MB.

A 2% saving. Two hours of transfer became one hour and fifty-seven minutes.

Why the first measurement was garbage

#

The artifacts were .tar.gz, because that is what everyone publishes. And a gzip stream has no stable structure to diff against: change one byte near the start and the entire compressed output downstream is reshuffled. Two archives whose contents differ by 1% produce compressed bytes that differ almost everywhere.

Binary diffing algorithms find common blocks between two files. If there are no common blocks, there is no delta — just an expensive way to re-send the file.

So I ran the same diff over the uncompressed tars:

Same tool, same two releases, same everything except what I fed it. 13.4 MB became 1.0 MB.

I also tried the obvious middle ground — gzip --rsyncable, which resets the compression window periodically so a change stays local. It got the compressed case from 98% down to 50%. Better, and still not worth building anything for.

The number nobody quotes

#

That 8% is two adjacent releases with ordinary code changes. Here is the same measurement across a release where I bumped the Go toolchain:

6.3 MB. 47% of the artifact.

A toolchain upgrade relinks and reorders the entire binary. Nothing moved in my code that would explain a 6× larger patch, but the layout moved everywhere, and a byte-level differ can only see layout.

This matters because the honest claim is a range, not a headline. If you build a delta pipeline expecting a consistent 90% saving, the first toolchain bump will make it look broken. It isn’t. It’s working exactly as designed on input that happens to be hostile.

And below roughly 1 MB of artifact, don’t bother: the patch approaches the size of the thing it replaces, and you have added a server to your architecture for nothing.

The design that follows from the numbers

#

If patches must be computed over uncompressed bytes, something has to produce those bytes. The obvious answer — “publish uncompressed artifacts” — is the wrong one: it makes every first install 2.5× more expensive, and it forces a change on whoever publishes the artifacts, which in a real deployment is not the same person running the agent.

The answer that costs nobody anything: decompress locally. The device already has the previous release cached as .tar.gz. Decompressing gzip is deterministic — it recovers the original tar byte for byte. So:

1. The agent decompresses the archive it already has. That’s the base.
2. It fetches a patch and applies it, producing the new uncompressed tar.
3. It verifies and unpacks that.

Nobody republishes anything. The uncompressed form exists only on the device, for the seconds it takes to patch.

Every arrow leaving that path to the right is a fallback, and none of them fails the deployment.

What verifies the result

#

This is the part I find most satisfying, because it removed work rather than adding it.

A patched artifact needs a digest to check against, and that digest needs to be trustworthy. The usual answer is a signed manifest: a new document, a new key, a new signing step in the release pipeline.

Keystone already verifies a detached signature over every recipe before it acts on any of it. So the recipe is already a signed document. Put the digest of the patched result in it and you inherit the trust for free:

[[artifacts]]
uri = "https://downloads.example.com/myapp-1.1.0.tar.gz"   # unchanged
sha256 = "9f2c8b1e…"                                       # unchanged

[artifacts.delta]
server = "https://ota.example.com"
sha256 = "4a71d0c3…"    # digest of the uncompressed archive after patching

No second signature, no manifest format, no key management. And because the agent knows both digests — it hashes the base itself, and the target comes from the signed recipe — the patch location is fully determined:

{server}/delta/{sha256 of the base}/{sha256 of the target}

One GET. No handshake, no device registration, no protocol.

There is a real trade here and it deserves stating plainly: on the normal path, the artifact’s own signature proves that the publisher signed those bytes. On the delta path, the attestation comes from whoever signed the recipe. Where the same trust bundle covers both, that is equivalent. Where you deliberately rely on a separate publisher key, it is not — which is why this is opt-in, per artifact, and off unless a recipe asks for it.

Two things I only learned by running it

#

I had tests. The tests passed. Then I stood up a real delta server and pointed the agent at it, and learned two things no test I had written would have caught.

A 404 means “not yet”, not “no”

#

The first request for a patch returned 404. I nearly concluded the whole no-handshake design was broken.

The server log said otherwise:

14:18:50.181  delta not cached      → 404
14:18:50.187  generating delta
14:19:00.666  delta cached          size=1034559

The 404 dispatched the generation. Computing a patch takes about ten seconds for a 34 MB artifact, so the server answers “not yet” and starts working. Ten seconds later, the same URL serves the patch.

Taking that 404 at face value — as my code did — means a lone device never receives a patch. It falls back to the full download every time, and only a second device asking later would find the result of the work the first one triggered. In a fleet you would never notice. On a single device it silently never works.

The fix is three lines: retry a not-found, fail fast on anything else.

The base does not belong on the heap

#

Patching needs the old file addressable as a single byte slice. The obvious implementation reads it into memory, which means peak usage is roughly twice the artifact — the base plus the reconstructed result — on the device with the least memory in the system.

Half of that is avoidable. Decompress the base to a file and mmap it: those pages become the kernel’s page cache, shared and evictable under pressure, instead of being charged to the process heap. I measured both paths on the same 32.5 MiB base:

mmap      → 0.000 MiB allocated
ReadFile  → 32.6   MiB allocated

The reconstructed result is still on the heap, and that floor is not mine to remove: go-bsdiff has no streaming path at any entry point — bspatch.Reader and bspatch.File both read everything into memory and call the []byte implementation. Worth knowing before anyone tries to “just use the File variant”.

For the record, on the server side the same job peaks at 752 MiB of RSS for 10.8 seconds to generate one patch for a 34 MB artifact — bsdiff’s suffix sort is roughly 20× its input, and that is genuinely allocated working memory that no amount of mmap will help. zstd --patch-from does the same job in 7.3 s and 274 MB, for a patch twice the size. On a 20 kbps link, “twice the size” is several extra minutes per device. That trade is not obvious, which is why I haven’t made it yet. Where that multiplier comes from, and what halves it, is the subject of its own post, published next.

What shipped

#

All of this is in Keystone v0.4.0, as an opt-in block on an artifact. The property I care about most is that it cannot break anything:

Every one of these falls back to downloading the whole artifact, and none of them fails the deployment: no previous version on disk (a first install), a server holding no patch from this device’s version, a patch that will not apply, a result whose digest does not match, a base over the configured size limit, or a patch format the agent does not implement.

A delta is an optimisation. The download is the contract.

The other thing I did deliberately: Keystone does not depend on the delta server’s code. It implements the patch format against the same libraries rather than importing the server’s package, so an edge agent doesn’t carry a server’s module graph. But independent implementations of the same wire format drift, and that failure would land on a device in the field — so there is one test, behind a build tag, that imports the server’s own package, generates a patch the way the server would, and asserts the agent reconstructs the target. It’s the only place that dependency exists, and its whole job is to go red the day the format changes.

What I don’t know yet

#

This has not seen a real fleet. It is measured, tested against a real server, and released — which is not the same as proven. The numbers in this post are two Go binaries on my machine and one server on localhost.

What I’d watch first in production: how often the base is missing because retention evicted it, since that quietly turns every delta back into a full download while all the graphs still look green.

If you’re building something similar, the one thing I’d take from this post is the method rather than the result: I nearly built the whole feature on top of a 2% saving because the first measurement looked plausible and I didn’t ask what it was measuring.