Edit: did a bit of looking around and it seems to be planned for Oneric Ocelot
https://blueprints.launchpad.net/ubuntu/+spec/foundations-o-...
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
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?
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.
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.
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.
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 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).
edit: not that I don't think this can be improved, nor that the updating software they used was any good. Just sayin'.
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)..
Then it downloads the diff and the new file hash :-)
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.
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.