Delta upgrade debs

Delta upgrades are widely used by other projects, such as Chrome, Android, FreeBSD, Fedora. One approach exists for dpkg-based systems: debdelta. While debdelta solves the problem, it does so in a sub-optimal way:

Proposal

A new format, called "patch debs" (.pdeb) is introduced. A patch deb consists of the original members from the target deb, with the following changes:

Furthermore, all .deb files are assigned a unique ID at build time, stored in the "ID" field of DEBIAN/control.

Unpacking a .pdeb

Unpacking a .pdeb works identically to a normal .deb, with one exception: The line copying the data to .dpkg-new from the data.tar tarball is replaced by code that uses the diff in the data.tar tarball and the installed file to generate the .dpkg-new.

The .dpkg-new is checksummed and must match the checksum(s) specified in the control.tar member of the pdeb. Packages without checksums may not have deltas.

Repository integration

A new index file is established alongside Packages and Sources, called Deltas. The Deltas index has the following fields

When upgrading a package:

Performance evaluation

All results on a ?ThinkPad X230 with a Core i5-3320M and 16 GB of RAM. Generation times are measured with a libdivsufsort-based bsdiff (or rather, a fork) and a more normal bsdiff.

Package

Size

Delta

Generation Time

Apply Time

firefox (55.0-1 -> 55.0-2)

38MB

2.4MB

40s/96s

0.6s

firefox (54.0-2 -> 55.0-2)

38MB

42MB

-

-

gcc-7 (7.2.0-1 -> 7.2.0-3)

31MB

3.1MB

75-90s/-

0.6s

Binary diffing

The bsdiff fork is maintained at https://github.com/julian-klode/ddelta.