Save bandwidth with diff/xdelta

[AndrewBirkett]

If I upgrade from emacs-21.2 to emacs-21.3 I have to download the whole new 20Mb tarball, despite there being a 1Mb xdelta from my existing version.

I can imagine an extension to the ebuild system which allows you to express the following: "If you have emacs-21.2 then grab the 21.2-to-21.3 delta and use it to generate emacs-21.3.tar.gz. Otherwise, just download emacs-21.3.tar.gz as normal"

Sure, most projects don't provide diffs but biggies like kernel and GNU projects like emacs, gcc and others do. It'd relieve some of the load on the source archives, and it'd be great for those of us without a fast connection.

What I'm suggesting is something which you could add to a particular ebuild script, which said where to get the diffs between the last two or three releases of the project. If the ebuild didn't include some "CAN-USE-DIFFS:" lines, then you'll just have to download the whole new version of the package.

Apologies if this is a FAQ. I looked around for a while, but 'diff' and 'patch' are poor keywords. If this isn't a crazy idea, I'll could dig around in the code and see if there's an easy and clean way to add it.

[puddpunk]

This was being discussed on the Gentoo-dev mailing list a little while ago, the problem was, nobody could come up with a sturdy way of implimenting it. Perhaps you would like to add your thoughts?

[AndrewBirkett]

Thanks - I eventually found my way to https://bugs.gentoo.org/show_bug.cgi?id=11470, which is pretty close to what I was suggesting.
_________________
- http://www.nobugs.org -

[aethyr]

I know this has been discussed in the past, but I feel that this is an important feature (that is already implemented by other source-based distributions such as sorcery/source mage) that cannot be continually glossed over.

I realize that the devil is in the details, but I feel that this would be a huge advantage for Gentoo in terms of giving users the "power of the source". And not even for slow connections, I started downloading linux-2.4.20.tar.bz2 (26.2mb) last night on my broadband connection and it was taking forever at 13kb/sec. I realized that I had a 2.4.19 tarball sitting around, so I grabbed the patch instead., the patch-2.4.20.tar.bz2 is 4.0mb. That's 1/6 of a difference. That's huge.

I think that some type of "upgrade path" table (contained in a file in the portage directory) needs to be built (possibly manually by the package maintainer?) that basically says something along the lines of:

patch to get to newest version - z - size
patch to get to intermediate version - y - size
current version - x

take the sum of the sizes of the patch files to get from x to z (in this case size of the y-patch), check if it's less than the size of grabbing z, if it is, then patch x to y, then to z, if not, download z.

The size of files is already contained in the portage tree, so it's not a problem finding those out.

In the above scenario, there could be any number of intermediate versions, as long as the total patch size was less than the size of the newest version, and we could forseeable upgrade to any package along the path.

Let's look at a more concrete example, the kernel.

Let's say we have an "upgrade path" table that looks like this

patch-2.4.20.bz2 -> linux-2.4.20 (4M)
patch-2.4.19.bz2 -> linux-2.4.19 (4.5M)
patch-2.4.18.bz2 -> linux-2.4.18 (807k)
patch-2.4.17.bz2 -> linux-2.4.17 (388k)
patch-2.4.16.bz2 -> linux-2.4.16 (6k)
patch-2.4.15.bz2 -> linux-2.4.15 (1.4M)
patch-2.4.14.bz2 -> linux-2.4.14 (560k)
...

Let's say we're currently running 2.4.14, and we do "emerge -p vanilla-sources"

First we see we're going to go to kernel 2.4.20, which has a size of 26.2M. Before doing that, we check our upgrade path, and see that 2.4.20 is available in our path (being at the top position). Once we see it's available, we check to see how much it "costs" to get there. We simply add up the "cost" of each patch:

0.56 + 1.4 + 0.006 + 0.388 + 0.807 + 4.5 + 4.0 = 11.661

11.661 costs less than 26.2 so we decide to follow the upgrade path.

The path is already set up for us, so we just advance step by step up the path, downloading, patching, downloading, patching, along the way, all inside a temporary directory. Once we have our final tarball, we're good to go. And we've saved 50% of the bandwidth, not too bad considering the 2.4.14 kernel is a full year older than the 2.4.20 kernel, the closer you are in the path, the less expensive it is to move up the path.

I realize that there's no code whatsoever in this idea, but I think it gives a feasible framework to work with.

[AndrewBirkett]

That's a nice idea. Though I think I'll try coding up a simpler "upgrade from previous version only" as a test case .. since I'm more likely to have time to complete that.

Earlier today, I thought that it'd be nice if this feature was mostly hidden inside the 'retrieve tarball' code. So, you can get the latest tarball by downloading it, or you can get it by downloading a patch to an existing tarball. Either way, you end up with the latest tarball on your disk and ebuild carries on from there. This keeps the changes to ebuild very localised. Also when you clean out /usr/portage/distfiles you'd only need to keep the latest version rather than a chain of patches. After all, the plan is to conserve bandwidth, not disk space.

However, the patched tarball is unlikely to have the same md5sum as the official one, unless you use exactly the same gzip/bzip options and the file timestamps match. So, maybe it's not such a clever idea after all.
_________________
- http://www.nobugs.org -

[aethyr]

it might be easier to implement it as a seperate script for now rather than try to modify portage directly (i.e. something that could be included in gentoolkit).

[Thulle]

Wouldn't it be an good idea if the users could choose wich idea to use?
For modemusers with some drivespace, it would be great with those upgradepaths, but broadbandusers with small drives would probably choose to save diskspace and instead utilize the connection they paid for.
Maybe an configurable percentagevalue of wasted space (old tar+patches compared to new tarball)?

[aethyr]

Thulle, no actually, it wouldn't be better to give users choice which method they use.

Why would you ever opt to download 20mb over 10mb? Even with broadband, that's still a 2x time difference.

You'd still end up with the same tar.bz2 in the end. All the incremental patches would be deleted, so the disc space taken up would be exactly the same as if you had just emerged a new version.

That being said, it would probably be good to cut it off somewhere, say if the costs of patching were more than half of the cost of downloading. Also, it might not be worth it if the new package download is less than a megabyte. Finally, keep in mind that not all packages post upgrade patches, some just give you new tarballs, so it would be unusable for those projects.

[dreamer3]

[ferringb]

A couple of problems you're going to run into- these are mostly gleamed from a night of screwing around generating a diff for openoffice...
Major diff's annoyances:
1) doesn't do jack about binary files, just states, the files differ. This ain't an issue for sources that lack binary files, but for say openoffice this is an issue. Further, unless I'm wrong (and I checked heavily into it), there really isn't anyway to tack binary data into a diff file. So you couldn't get away with just distributing a diff- you would likely do a tarball w/ a patch and binary files inside.
2) Diff doesn't like zero length files. This probably isn't an issue, but if you are diffing between 1.0 and 1.1, and 1.1 has zero length files in it that 1.0 lacks, diff doesn't do anything (actually if you're just doing diff -ur it will say it exists in one... if you're using -n (likely) it doesn't say anything).
3) not so much a diff issue, but a consideration- try generating a diff between kde 3.1 and 3.11 (as an example)- you'd expect it to be minor, but it's not so minor. Reason being, it seems a lot of the larger projects have auto-generation of files (xml files as an example)- so instead of getting just the changes between 3.1 and 3.11 for a file that may not have even changed, diff registers the file as basically being completely different. Meaning said file is actually a bit larger in diff format cause it encompasses both the old file and the new file (old for deleting said lines, new for adding said lines)- this actually is much more expensive in terms of size.

So that's already a pain in the arse, but if you're doing the patching at the time of untarring, as long as 1 and 2 are dealt with you should be fine. Downside being that every time you compile said package, it must repatch the source adding to the overall complexity/time.
Why not just download the diff, patch the distfile, then retar it you say? Heh heh... I've yet to get the md5sum to match.
1) if all that's changed on a file is it's date/permissions/non-data, diff ignores it. eg the data is the same, but the file attributes aren't...
2) Zero length files mentioned above.
3) If the developer created the tarball, then appended a file to it, that file isn't in it's normal place- it's appended. You would have to match this (basically impossible I think).

So to actually update the distfile (which in my books is a good idea despite it's thornyness), we need to match the patched source exactly to the target versions setup. Why would it be better to do distfile patching rather then doing the 'upgrade path'? Well....
1) upgrade path doesn't always exist/work. Kernel v2.4.11 or 2.4.12 you can't upgrade past IIRC as an example- so the v2.4.11/12 (which ever one it was) would have to have some way of saying, "um, no kiddies, no diff's allowed here...". Minor issue, but you get the idea.
2) One time annoyance of patching the distfile- after that (assuming one gets the md5sum exactly right), to emerge the distfile appears as the full source. This is preferable mainly cause that way emerge doesn't have to dink around w/ having the 12+ version patches cause a user hasn't downloaded a recent full source (less complexity is good). That and it means less modification to emerge (instead of every package emerge having to the diff check on it's sources, you just stick this modification in the fetch section).

There is the matter of generation of the diffs- this would basically be the developer's responsibility (you can't push it onto the servers most likely). Something could be automated to make it easier for the developers, but it would have to be something that isn't a pain in the butt for dev's to deal with. There also is the issue of getting the diff's onto the server- a developer doesn't neccesarily have to upload the source (an automated script grabs missing sources every couple o days), so how would diff creation be handled in such a scenario?

So yeah, that is my 2 cents in a semi-stream of thought rant. I personally would like to see this happen (tiz why I pestered dev mailing list with the distfile diff question), but the issues involved are annoying. Matching the md5sum strikes me as something that would be quite hard if not impossible for the majority of sources... Course that could be dealt w/ by having intermediate md5 sums (as in a patched v1.1 has this md5)... but that gets complex/burdensome/insane fast.

[ferringb]

Heh, while it's kind of responding to my own post, anyone curious as to why this would be a *good thing*- I created a fully working openoffice diff (well, diff, updated binaries files, and empty file listing), used it to modify/patch/recreate the recent oo source- total files downloaded were roughly 12mbs, which I could've pushed smaller by pulling apart zip files and grabbing a diff of the files in there...

Course the stupid thing doesn't match the md5sum, but neh- avoiding a 160+mb download on 56k is worth the md5 hassle...

[dreamer3]

[dreamer3]

Regarding MD5 sums... if full support wasn't coded into Portage to track this in /usr/portage a seperate database (/var/db/patches?) could easily be used that fetch could check first or check if the main md5 compare failed... the md5s of "patched" sources could be stored there.

I think MD5's matching is a non-issue actually... the whole diff idea will take a lot to impliment anyway and without the Gentoo Devs support it will never work for the majority of ebuilds. Assuming we _do_ have their support then I only imagine portage would be changed to handle the MD5 variability.

Ok... lets assume they aren't that interested, or they don't have time for a while... it wouldn't be impossible to impliment a system outside of portage (provided we had some web space open to HEAVY usage). You would create and provide diffs for the largest packages first, followed by smaller. A special "fetch" command could be created that understood the system, would download all the necessary files, patch, place the new tarball in /usr/portage/distfiles, and update the md5s in /usr/portage. These md5s could also be kept track of so /usr/portage could be re-updated with the CORRECT md5s (after a sync for example).

Edit: Portage could then be hacked to have it's fetch functionality first call the "patch fetch" code and only try normal downloads if no suitable patches are found. Not sure how hard this would be to do... biggest problem is the storing and mirroring of diffs...

[ferringb]

I actually sat down and responded to each quote... but that got to long (droning as you said). Soo a couple of choice quote responses and some thoughts.

[vericgar]

From what I understand of the portage system, it shouldn't be to hard to implement this in the ebuild itself. The ebuild can dynamicly generate the SRC_URI, so I see no reason why this can't be hacked up to work in the ebuild without modifying portage itself... or even put into an eclass.

code-flow:

1) check if source tarball for lower versions exists, starting with the most recent and working the way back through the versions until it no longer makes sense to do patching to current (i.e. patches don't exist, or total of all patch files is more then new download, etc)

2) once patch path is found, add all patches to SRC_URI

3) when in src_unpack check to see if we are doing patches (flag set previously) and patch as necessary.

4) continue as normal

Now the MD5SUM would need to contain the MD5s of all the possible downloadable patches, but that isn't a biggie.
_________________
+~+ Sometimes a good ole loving kick is all it needs +~+

[dreamer3]

[jjw]

Hi,
I read your posts and I would like you all to take a look at my project which might be an excellent solution to the problems you mentioned. It's called Deltup, and if it gets merged with Portage it will work automatically, without any extra work when packages are updated! We won't be dependent on the diffs released by the package maintainers either, and finally, YES it does produce correct MD5sums! Please find out more by reading my announcement: https://forums.gentoo.org/viewtopic.php?p=318671. It still might have some bugs... Could someone test this on a 64bit or Big-Endian machine?
---JJW

-------------------------------
Do All for the Glory of God!