Faster update downloads: debdelta vs zsync

[Lars Wirzenius]

I ran my benchmark again, this time comparing debdelta with zsync.
Results: 

datafile              downloaded (GiB)    downloaded (%)
------------------------------------------------------------
http                  1.18                100.0         
zsync-rsyncable       0.90                 75.8         
debdelta              0.48                 40.4         

(Note that in this table, a lower number is better.)

debdeltas are much more efficient than zsync. debdelta uses bsdiff as
its backend, and bsdiff is optimized for diffing executables, whereas
zsync is agnostic and applies to all kinds of data. This gives debdelta
a clear edge for .deb files, which mostly consist of executable code.

However, may be less convenient to use. As far as I understand, we may
need to produce deltas for various pairs of versions. However, this
might be manageable: producing a delta from the version in hardy,
hardy-security, hardy-updates, and hardy-proposed to each new version
should perhaps be a manageable amount of data and number of files. This
would mean that a user should rarely need to download the full package.

Deltas from one release to another might also be possible. Most packages
probably don't change a huge amount from release to release, although
the compiler might. I can run a benchmark for this, too.

debdelta is fairly slow, so might only be worth it for people whose
bandwidth is small compared to their CPU speed. But that's a lot of
people.

debdelta can't yet handle packages that use lzma, but we can always fall
back on plain http until this is fixed.

I did not yet look at Courgette, Google's improvement on bsdiff. They
claim large improvements over bsdiff, but it seems to rely on an
architecture specific disassembler.

What do people who understand how the archive works better than I do
think about the debdelta approach as opposed to the zsync approach?