News for hackers. Stuff that matters.
Re:Chrome has transcended version numbers by wladimir on Monday May 23, 2011 @08:10AM (#2575684)
That upgrader using binary differences (courgette) is impressive. From 10 megabytes to 78 kilobytes. 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.

Edit: did a bit of looking around and it seems to be planned for Oneric Ocelot

https://blueprints.launchpad.net/ubuntu/+spec/foundations-o-...

Re:Chrome has transcended version numbers by nuclear_eclipse on Monday May 23, 2011 @09:18AM (#2575808)
> 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

Re:Chrome has transcended version numbers by dspillett on Monday May 23, 2011 @10:52AM (#2576099)
> 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).

Re:Chrome has transcended version numbers by Groxx on Monday May 23, 2011 @02:59PM (#2577083)
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'.

Re:Chrome has transcended version numbers by dspillett on Monday May 23, 2011 @08:06PM (#2578128)
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)..

Re:Chrome has transcended version numbers by idonthack on Monday May 23, 2011 @04:52PM (#2577537)
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.
Re:Chrome has transcended version numbers by lallysingh on Tuesday May 24, 2011 @04:50AM (#2579134)
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 :-)

Re:Chrome has transcended version numbers by shalinmangar on Monday May 23, 2011 @09:40AM (#2575856)
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.
Re:Chrome has transcended version numbers by nuclear_eclipse on Monday May 23, 2011 @09:48AM (#2575879)
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.
Re:Chrome has transcended version numbers by wladimir on Monday May 23, 2011 @09:43AM (#2575870)
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.

Re:Chrome has transcended version numbers by rjh29 on Monday May 23, 2011 @09:28AM (#2575821)
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?

Re:Chrome has transcended version numbers by nuclear_eclipse on Monday May 23, 2011 @09:45AM (#2575873)
> 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.

Re:Chrome has transcended version numbers by leif on Monday May 23, 2011 @01:33PM (#2576745)
> 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.

Re:Chrome has transcended version numbers by true_religion on Monday May 23, 2011 @11:27AM (#2576233)
> 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.

Re:Chrome has transcended version numbers by cubicle67 on Monday May 23, 2011 @09:53AM (#2575896)
er yeah. someone want to show this to the guys at Apple who push out the XCode updates?
Re:Chrome has transcended version numbers by stock_toaster on Monday May 23, 2011 @03:31PM (#2577217)
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.

Re:Chrome has transcended version numbers by cookiecaper on Monday May 23, 2011 @01:11PM (#2576656)
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.

Re:Chrome has transcended version numbers by scoopr on Monday May 23, 2011 @12:26PM (#2576480)
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.
Re:Chrome has transcended version numbers by vijaydev on Monday May 23, 2011 @08:39AM (#2575734)
The launchpad link returns a 404.
Re:Chrome has transcended version numbers by wladimir on Monday May 23, 2011 @08:45AM (#2575746)
Yep, thanks for noticing, it's solved.