> I wonder why Linux distributions such as Ubuntu still download the entire new packages on an upgrade. A lot of upgrade time and bandwidth could be saved by only sending the differences. And it would reduce load on the mirror sites.

Speaking as someone who has worked on this problem for my own projects [1], I think I can answer this.

Fedora/Yum already supports downloading a binary diff between rpm packages to reduce download size, but this also requires keeping a cache of previous rpm's to run the patch against. There are multiple reasons why you can't rely on binary diffs against the files actually stored on the system, most namely for files like /etc/* that are more than likely modified since installation.

But the real problem with binary diffs is that unless you're doing what Google does to ensure that people stay up to date, the number of binaries you need to diff against grows very quickly, and there are a lot of edge cases to take care of.

For example, let's assume some package A has been released as version 1, 2, and 3. When A has a new release 4, you obviously want to build a diff against release 3, but then you also most likely need or want to build a diff against 2 and maybe even 1 to take care of people who haven't already upgraded to 3. And even if you build a diff against every single version ever released, you will still always need to provide a full version of the package as well for two cases:

1. New installations, or reinstallations, of the package.

2. When the user has cleared their package cache to save room.

And even beyond that, creating diffs involves a lot more effort and knowledge on the part of the packaging team because they not only need to know how to build those diffs, but they also need to keep track of old package versions to build those diffs against.

The end result is that you trade download bandwidth and time on part of the server and end users for a lot of effort, time, and storage space on part of the packagers and distro mirrors. For mirrors that are already encroaching on 50GB for a single release of Ubuntu and/or Fedora, adding a whole bunch of binary diff packages will most likely grow the repository size by at least 30-50%, if not more, depending on how many old versions you diff against.

The question then becomes: does this trade off actually make sense, or does it present further roadblocks for contribution from packagers and donated mirrors?

[1]: If you would like to see how I handled this sort of task, I have a Python library I wrote to handle the client side updating. I know it's not the entire piece of the puzzle because it doesn't cover generating the updates, but it might be useful for someone else. http://github.com/overwatchmod/combine

> When A has a new release 4, you obviously want to build a diff against release 3, but then you also most likely need or want to build a diff against 2 and maybe even 1 to take care of people who haven't already upgraded to 3.

You wouldn't need a diff for every combination (1->2, 1->3, 1->4, 2->3, 2->4, 3->4 in the four version case), just the three diffs 1->2, 2->3 and 3->4. Then if someone has v2 you send out the diffs for 3 and 4 and have the client apply both in order to make the updated package ready to apply. The saving in space and number of diffs stored will grow as the number of versions grows.

This will be a little less efficient in terms of bandwidth use on average when people are skipping a couple of versions, but will make little or no difference if people are upgrading in a timely manner (so are only moving in single version steps most of the time) and will save space over storing diffs between all versions.

As well as the diffs I would store checksums for each version and have the client send the checksum for the version they have just-in-case, to avoid sending a diff (sending the file package instead) if the reference file seems corrupt.

Also if you store diffs for both directions you can serve old versions of packages (in case people need to roll-back due to some unexpected incompatibility, or they are developers needing to build a test environment with older library versions) without storing every version completely. This increases the diffs per package, but not nearly as much as storing one diff between every version (for 11 versions, 1 diff per change is 10, diffs in both directions is 20, diffs between all versions totals 45 (or 90 for both directions), for 21 versions those numbers are 20, 40, 190, 380).

In my experience, diff + diff + diff = super-long update process. It was done for many game updates up to several years ago, and an update from the box version through 3 patches could take up to an hour. The install, meanwhile, would take 20 minutes or so at most.

edit: not that I don't think this can be improved, nor that the updating software they used was any good. Just sayin'.

Often with game updates to get around the fact that patching the compressed multi-asset files directly would not be efficient (as a change early in the file would mean the rest of the file to the end would need patching unless they had the foresight to use something like gzip's rsync-friendly option), the patch would unpack the compressed resource files, patch them, then recompress. Depending on how granularly the assets are distributed amongst the installed files and how many of them were being touched by the patch this could be a lot slower than just reading the compressed file from CD to hard-drive which is what the installer would do.

Of course this means that if using the multi-diff method of update distribution you would need to be careful about your selection of compression arrangement to avoid the same inefficiency (unless the saving in bandwidth for the client and the package storage servers is far more important than a bit of extra time spent on the updates client-side)..

i expect those game updates didn't use bindiffs, they had to repackage the entirety of each updated file. when you consider that many developers do things like compress all game content files into a few large archives, it's easy to see how that adds up. you end up re-downloading the same content repeatedly when they repeatedly make small changes to a few scattered files in one large archive.

That makes a good case for some of the existing mirrors to provide 'diffserv'-like facilities. A small daemon could do that server-side, and the client may just need a hash of the prior package's binary file.

Then it downloads the diff and the new file hash :-)

Although it'd be nice to have diffs available for all earlier versions but it doesn't need to be mandatory. A simple way to get started would be, for example, to make the diffs available for the last version released by Ubuntu 11.04 as well as the last security update on top of 11.04 -- which I guess should take care of the majority. If people are running older versions of the packages, or if they haven't applied security updates regularly, they download the complete binary.

That's exactly how I handled it for my project, but it's still a lot more complicated than just always downloading a full package. Which is exactly what I was trying to get across. It's not impossible, just a lot more complicated on every part of the equation.

Thanks for the explanation.

I think you can use the files stored on the system itself in many cases, at least for binaries. /etc/ and other configuration is an exception, which you could special-case. As config files are generally small files, this is no problem.

Of course you should check whether the file you are going to patch is the file you assume it is, but this is easily built-in to binary diff using a hash.

If a file doesn't match, err on the safe side and simply fetch the entire package.

You mentioned storing diffs against every previous version. In principle, couldn't you, when a new package is pushed to the repository:

1. Diff against the previous version and store the diff.

2. Delete the previous version.

You could upgrade from any previous version by applying all the diffs in sequence, and you only need to keep one full version around. You could also discard diffs after a certain date because, as you point out, the worst case is that the full version is used instead.

I guess this would increase disk space for the mirrors, but even 100GB wouldn't be a lot of disk space, and the savings for (presumably more expensive) internet data transfer would be a lot bigger?

> You mentioned storing diffs against every previous version

I didn't say you need to. Eg, with my software project, I wrote an update system that supported diff upgrading against the two latest versions, and anyone still running an older version had to download a full update.

> You could upgrade from any previous version by applying all the diffs in sequence

At that point you also need to make sure that you aren't downloading more in the process of applying a series of patches than you would need to download for a full update, which also means you need to start being aware of multiple update options, which balloons the complexity of your update code.

> At that point you also need to make sure that you aren't downloading more in the process of applying a series of patches than you would need to download for a full update, which also means you need to start being aware of multiple update options, which balloons the complexity of your update code.

The obvious way to handle this is to store full package "snapshots" on "major" version releases (probably upstream releases for packages with lots of local patching, or "one level up from the bottom" releases) and diffs in between. That is not a lot of code if you already have a sane way of managing release numbers within your package manager, which you hopefully do.

> At that point you also need to make sure that you aren't downloading more in the process of applying a series of patches than you would need to download for a full update

Well you wouldn't really need to but it would be a good sanity check on the client side.

The common case could be that people are simply keeping up with the stable edge w/o patching binaries themselves out of band---that's the case with some desktop linux variants.

er yeah. someone want to show this to the guys at Apple who push out the XCode updates?

I agree that this is a major failing of the mac app store as it currently stands.

Given that for updates there is a high likelihood that the previous version is on-disk, sending some type of diff would be very beneficial to end users. Even if it is a diff for only the previous to the current version, with a full download required outside that window.

For the record, pacman already supports diffs like this, but Arch has not set up official mirrors that host binary diffs instead of full packages. There has been at least third-party repository that hosted diffs for ArchLinux packages.

I too think this should be a much higher priority than it is for many. Fedora has had (non-default) support for this for years, but that's about it. You shouldn't worry so much about diffing against previous versions -- if you diff against the last two versions, it won't use much extra disk space, and the worst case scenario is that someone has to download the full package as a fallback, which everyone has to do now.

Lately, I've been less bothered about the download sizes of updates, and more bothered by the update-install times. Takes under a minute to download the usual 100-1000MB update, but then it's 5-15min to install it, be it ubuntu, ps3 firmware or xcode4. Providing bigger stuff on readily usable squishfs images instead of tarballs, even if vastly bigger might actually make my update times shorter.

The launchpad link returns a 404.

Yep, thanks for noticing, it's solved.