File: x182.html

package info (click to toggle)
debdelta 0.50%2B3
links: PTS
area: main
in suites: jessie, jessie-kfreebsd
size: 920 kB
ctags: 408
sloc: python: 4,383; perl: 1,398; sh: 1,031; xml: 727; ansic: 215; makefile: 102; awk: 21
file content (804 lines) | stat: -rw-r--r-- 19,652 bytes
parent folder | download | duplicates (5)
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN""http://www.w3.org/TR/html4/loose.dtd">
<HTML
><HEAD
><TITLE
>Goals, tricks, ideas and issues</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
REL="HOME"
HREF="index.html"><LINK
REL="PREVIOUS"
TITLE="debdelta-upgrade service"
HREF="x65.html"><LINK
REL="NEXT"
TITLE="Todo"
HREF="x277.html"></HEAD
><BODY
CLASS="section"
BGCOLOR="#FFFFFF"
TEXT="#000000"
LINK="#0000FF"
VLINK="#840084"
ALINK="#0000FF"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="3"
ALIGN="center"
></TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="bottom"
><A
HREF="x65.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="80%"
ALIGN="center"
VALIGN="bottom"
></TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="bottom"
><A
HREF="x277.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="section"
><H1
CLASS="section"
><A
NAME="AEN182"
>4. Goals, tricks, ideas and issues</A
></H1
><DIV
CLASS="section"
><H2
CLASS="section"
><A
NAME="AEN184"
>4.1. exact patching</A
></H2
><P
>&#13;      When <B
CLASS="command"
>debpatch</B
>  or <B
CLASS="command"
>debdelta-upgrade</B
>
      recreates a .deb, it will be identical to the desired
      one (so it may be possible to check it using the 
      <A
HREF="http://wiki.debian.org/SecureApt"
TARGET="_top"
>&#13;       security features in APT</A
>
      <A
NAME="AEN190"
HREF="#FTN.AEN190"
><SPAN
CLASS="footnote"
>[1]</SPAN
></A
>). See though <A
HREF="x182.html#long_time"
>Section 4.5</A
>.
    </P
></DIV
><DIV
CLASS="section"
><H2
CLASS="section"
><A
NAME="AEN195"
>4.2. exact recompression</A
></H2
><P
>&#13;      Suppose a .deb has inside a huge file
      /usr/share/doc/foobar/document.info.gz
      and this starts with a RCS tag ... then each time it
      is released, the file will be different even though
      just few bytes were changed. Another examples are manpages that start with the header
      containing the version of the command.
      So , to get good compression of the difference, I had
      to be able to gunzip those files, diff them,
      and gzip back them <SPAN
CLASS="emphasis"
><I
CLASS="emphasis"
>exactly identical</I
></SPAN
> (but possibly for headers
      <A
NAME="AEN199"
HREF="#FTN.AEN199"
><SPAN
CLASS="footnote"
>[2]</SPAN
></A
>)
      For this reason, I studied gzip formats, and I wrote in debdelta
      some python code that does the trick (90% of the times...).
      <A
NAME="AEN201"
HREF="#FTN.AEN201"
><SPAN
CLASS="footnote"
>[3]</SPAN
></A
>
    </P
></DIV
><DIV
CLASS="section"
><H2
CLASS="section"
><A
NAME="AEN204"
>4.3. speed</A
></H2
><DIV
CLASS="section"
><H3
CLASS="section"
><A
NAME="AEN206"
>4.3.1. some (old) numbers</A
></H3
><P
>&#13;      Warning: this section is referred to experiments done in 2006, and the backend for
      delta encoding was 'xdelta'.

      On a desktop with CPU  Athlon64 3000 and a average hard disk,
      <PRE
CLASS="programlisting"
>&#13;	$ debdelta mozilla-browser_1.7.8-1sarge3_i386.deb \
	mozilla-browser_1.7.8-1sarge6_i386.deb /tmp/m-b.debdelta
      </PRE
>
      processes the 10Mb of mozilla-browser in ~11sec, 
      that is a speed of ~900kB per second.

      Then  debpatch applies the above delta in  16sec,
      at a speed of  ~600kB per second.

      Numbers drop in a old PC, or in a notebook (like mine, that has a
      Athlon 1600MHz and slow disks), where data are chewed at ~200kB per
      second. Still, since I have a ADSL line that downloads at
      max 80kB per second, I have a benefit downloading deltas.

      In a theoretical example, indeed, to download a 80MB package, it would
      take 1000seconds; whereas to download a delta that is 20% of 80MB it
      takes 200seconds, and then 80MB / (200kB/sec) = 400seconds to apply
      it, for a total of 600seconds. So I may get a "virtual speed" of 80MB /
      600sec = 130kB/sec .

      Note that delta downloading and delta patching is done in parallel:
      if 4 packages as above have to be downloaded, then the total
      time for downloading of full debs would be 4000seconds, while the time
      for  parallel-download-patch-apply-patch may be as low as 1400seconds.
      </P
><P
>&#13;      This is a real example of running 'debdelta-upgrade' :
      <PRE
CLASS="programlisting"
>&#13;	Looking for a delta for libc6 from 2.3.6-9 to 2.3.6-11
	Looking for a delta for udev from 0.092-2 to 0.093-1
	Patching done, time: 22sec, speed: 204kB/sec, result: libc6_2.3.6-11_i386.deb
	Patching done, time: 4sec, speed: 57kB/sec, result: udev_0.093-1_i386.deb
	Delta-upgrade download time 28sec speed 21.6k/sec
	total time: 53sec; virtual speed: 93.9k/sec.
      </PRE
>
      (Note that the "virtual speed" of 93.9k/sec , while less than the 
      130kB/sec of the theoretical example above, is still more than the
      80kB that my ADSL line would allow).

      Of course the above is even better for people with fast disks and/or
      slow modems.

      Actually, an apt delta method may do a smart decision of how many
      deltas to download, and in which order, to optimize the result, (given
      the deltas size, the packages size, the downloading speed and the
      patching speed).
      </P
></DIV
><DIV
CLASS="section"
><H3
CLASS="section"
><A
NAME="AEN212"
>4.3.2. speeding up</A
></H3
><P
>&#13;      The problem is that the process of applying a delta to create a new
      deb is currently slow, even on very fast machines.

      One way to overcome is to "parallelize as much as possible".

      The best strategy that I can imagine is to keep both the CPU,
      the hard disk, and the Internet connection, always maxed up.

      This is why 'debdelta-upgrade' has two threads, the "downloading
      thread" and the "patching thread". The downloading thread downloads
      deltas (ordered by increasing size), and as soon as they are
      downloaded, it queues them to be applied in the "patching thread";
      whereas as soon as all available deltas are downloaded it starts
      downloading some debs, and goes on for as long as the deltas are being
      applied in the "patching thread".

      Summarizing, the downloading thread keeps Internet busy while the
      patching thread keeps the CPU and HDD busy.
      </P
><P
>&#13;      Another speedup strategy is embedded inside the deltas
      themselves: since bsdiff is a memory hog, when the backend is
      bsdiff, I have to divide the data in chunks; this may lower the
      compression ratio, but the good point is that the HDD accesses
      and the calls to bsdiff can run "in parallel".  With newer
      xdelta3, xdelta3 can read the original data from a pipe, so the
      data are not divided in chunks, but rather continously piped
      into xdelta3; so xdelta3 runs at the same time as when the data
      are read from HDD.
      </P
></DIV
><DIV
CLASS="section"
><H3
CLASS="section"
><A
NAME="AEN216"
>4.3.3. the 10kb trick</A
></H3
><P
>currently, roughly half of the generated deltas<A
NAME="AEN219"
HREF="#FTN.AEN219"
><SPAN
CLASS="footnote"
>[4]</SPAN
></A
>  are less than 10KB. 
	  <B
CLASS="command"
>debdelta-upgrade</B
> downloads deltas in two passes,
          <P
></P
><OL
TYPE="1"
><LI
><P
>in the first pass it tries to download the first 10KB of a delta;
             if it gets a complete delta, it immediatly pipes it in the "patching thread queue", otherwise if it gets
             only a partial download,              it adds it to the download queue; if it gets HTTP404, it 
              possibly checks for the "toobig" timestamp, and it possibly warns the user.
	    </P
></LI
><LI
><P
>in the second pass, it downloads the rest of the deltas, and queues them for patching</P
></LI
></OL
>
	  Why this complex method? because the first 10KBs of a delta contain the info, and those may be used
          to actually decide not to download the rest of the delta (if a TODO predictor 
	  decides that it is not worthwhile...<A
HREF="x182.html#predictor"
>Section 4.3.4</A
>).
      </P
></DIV
><DIV
CLASS="section"
><H3
CLASS="section"
><A
NAME="predictor"
>4.3.4. the choice, the predictor</A
></H3
><P
>&#13;      Which deltas should be downloaded, VS which debs?

      Currently there is a rule-of-thumb: the server immediately deletes any
      delta that exceeds 70% of the original deb , and it replaces it with
      an empty file ending in ".debdelta-too-big". In such cases,
      "debdelta-upgrade" will download the deb instead.

      See the explanation of "debdelta-upgrade --deb-policy" in the man page
      for more info and customization on which debs get downloaded.
    </P
><P
>&#13;      Some time ago I tried to do devise a better way to understand when to
      download a delta w.r.t. a deb. The code is in the "Predictor" class
      .... but I could not reliably predict the final speed of patching, so
      currently it is not used.
    </P
></DIV
><DIV
CLASS="section"
><H3
CLASS="section"
><A
NAME="AEN232"
>4.3.5. State of the art</A
></H3
><P
>&#13;      All in all, I still cannot obtain high speeds: so people that have a fast
      ADSL Internet connection usually are better
      downloading all the debs, and ignoring "debdelta-upgrade" alltogether.
      Anyway, the best way to know is to try "debdelta-upgrade -v" and 
      read the final statistics. See 
      <A
HREF="x182.html#format_unzipped"
>Section 4.7</A
>
      and <A
HREF="x182.html#format_preunpacked"
>Section 4.8</A
> for recent developments.
    </P
></DIV
></DIV
><DIV
CLASS="section"
><H2
CLASS="section"
><A
NAME="the_enemy_within"
>4.4. better deb compression is a worse delta</A
></H2
><P
>&#13;      'xdelta3' can reconstruct data at high speed: on nowadays processors, it can process up to 2MB per second;
      but, when applying a delta, 'xdelta3' works on <SPAN
CLASS="emphasis"
><I
CLASS="emphasis"
>uncompressed data</I
></SPAN
>.
      So if the data is then compressed at a ratio 1/3, then the resulting speed on <SPAN
CLASS="emphasis"
><I
CLASS="emphasis"
>compressed data</I
></SPAN
>
      is 700KB/sec. Moreover, time is needed to actually compress the data.
    </P
><P
>&#13;      In recent years, 'dpkg' has transitioned from 'data.tar.gz' to    'data.tar.bz2' to   'data.tar.lzma';
      each method is better at compressing, but is also slower than the previous one; since it is better at
      compressing, it also defeats the ability of 'debdelta' to produce small deltas (wrt the original deb, of course),
      and indeed statistics show that deltas are getting larger; since it is slower, it slows down the applying of
      deltas as well.</P
></DIV
><DIV
CLASS="section"
><H2
CLASS="section"
><A
NAME="long_time"
>4.5. long time recovery</A
></H2
><P
>As aforementioned, deltas can rebuild the deb identically to the byte. But the patch.sh script
       calls the standard tools 'tail','head','zgip','bzip2','lzma', etc etc to rebuild a delta; so 
       if the argument calling or output of any of those tools changes, than a delta may become unusable.
       As long as deltas are used for the debdelta-upgrade service, this is no big deal: if such a tool changes,
       then we can adjust the deltas to it, and there is just some days disruption of the service 
       <A
NAME="AEN246"
HREF="#FTN.AEN246"
><SPAN
CLASS="footnote"
>[5]</SPAN
></A
>
       (and people will download debs instead of deltas .... as we used to).</P
><P
>If anybody wants instead to use debdelta to archive debs for long time, (as the archive.debian.org service
         was doing), then we should make sure that , at any moment in future, deltas can be applied. 
         A possible solution would be that deltas should contain, in the info files, the versions of all tools that
         are needed for applying. A second solution is that debdelta should keep a standard set of those tools inside the package.
    </P
></DIV
><DIV
CLASS="section"
><H2
CLASS="section"
><A
NAME="AEN249"
>4.6. streaming</A
></H2
><P
>&#13;      Let me summarize. When 'debdelta-upgrade' (or 'debpatch') recreates a
      deb, one step is reassembling the data.tar part inside it; this part
      moreover is compressed (gzip, bzip2 or lately lzma). This
      'reassembling and compressing' takes time (both for CPU and for HD),
      and is moreover quite useless, since, in short time, 'apt' will call
      'dpkg -i' that  decompresses and reopens the data.tar in the deb.
      </P
><P
>&#13;      It is then reasonable to collapse this two parts, and this would
      possibly speed up the upgrade a bit. A first step is
      <SPAN
CLASS="emphasis"
><I
CLASS="emphasis"
>'--format=unzipped'</I
></SPAN
>       <A
HREF="x182.html#format_unzipped"
>Section 4.7</A
>
      , a next step may be          <SPAN
CLASS="emphasis"
><I
CLASS="emphasis"
>'--format=preunpacked'</I
></SPAN
>
      <A
HREF="x182.html#format_preunpacked"
>Section 4.8</A
>.
      </P
></DIV
><DIV
CLASS="section"
><H2
CLASS="section"
><A
NAME="format_unzipped"
>4.7. --format=unzipped</A
></H2
><P
>The recently introduced
       new <CODE
CLASS="varname"
>--format=unzipped</CODE
>
       may speed up package upgrades. If you call
       'debdelta-upgrade' with the option '--format=unzipped' , then in the
       recreated deb the data.tar part will not be compressed. 
       This may speedup the 'debdelta-upgrade' + 'apt-get upgrade' process. Indeed, writing
       to hard disk is fast (let's say 5MB/sec, but usually much more); whereas
       compressing random data with 'bzip2 -9' or 'lzma -9' is much slower
       (let's say 2.0MB/sec and 1.5 MB/sec) ; and moreover the compressed data
       is then decompressed by dpkg when installing; so avoiding the
       compress/decompress should be a win/win (unless you run out of disk
       space...).  Indeed I see that the creation of deltas is much faster; 
        but I still do not have enough data collected....
     </P
></DIV
><DIV
CLASS="section"
><H2
CLASS="section"
><A
NAME="format_preunpacked"
>4.8. --format=preunpacked</A
></H2
><P
>&#13;      Here is another idea. When  'debdelta-upgrade' is called in upgrading a
      package 'foobar' it currently creates 'foobar_2.deb'. By an
      appropriate cmdline switch <SPAN
CLASS="emphasis"
><I
CLASS="emphasis"
>'--format=preunpacked'</I
></SPAN
>,
      instead of creating a 'foobar_2.deb' , it
      directly saves all of its file to the filesystem, and it
      adds an extension to all the file names, making sure that no file name
      conflicts (=overwrite) with a preexisting file on the filesystem
      ; then it creates a file 'foobar_2.deb_preunpacked' , that is 
      a deb package were 'data.tar.xxx' is replaced with 
      'data_list', just a text file specifying the contents of 'data.tar.xxx' 
      and  where regular files  were temporarily unpacked.
      </P
><P
>&#13;      Note that the above idea overlaps a lot with 
      <A
HREF="http://wiki.debian.org/SummerOfCode2010/StreamingPackageInstall"
TARGET="_top"
>&#13;           the SummerOfCode2010 StreamingPackageInstall</A
>
     </P
><P
> 
       <B
CLASS="command"
>debdelta-upgrade --format=preunpacked</B
> is now implemented as a proof-of-concept
       (it does not really write temporary files to HD yet).
       
       
       
       
       
       The format of <SPAN
CLASS="emphasis"
><I
CLASS="emphasis"
>data_list</I
></SPAN
> is
       <PRE
CLASS="programlisting"
>&#13;Files:
 TYPE MODE USER GROUP MTIME
 NAME_FILE_WAS_UNPACKED_TO (if regular file)
 ORIGINAL_FILENAME
 LINK_NAME (if link)
[repeat]
       </PRE
>
       Example of data_list
       <PRE
CLASS="programlisting"
>&#13;Files:
 d 0755 root root 1304626623
 
 ./etc
 
 - 0644 root root 1304626594
 /./etc/gnashrc_1956_debdelta_preunpacked
 ./etc/gnashrc
 l 0777 root root 1304626629
 
 ./usr/share/man/man1/gtk-gnash.1.gz
 gnash.1.gz
       </PRE
> 
      </P
><P
> PROS: (1) may be faster; (2) if you need to
      upgrade a 100MB package, you do not need to save both the deb
      and (while 'dpkg --unpack') the whole new deb data : so there is
      less risk of running our of disk space.  
      </P
><P
> CONS: (1)
      you cannot install that "preunpacked deb" twice (so dpkg should
      probably remove it once it has installed it); (2) you cannot
      move it to another host; (3) when "apt-get clean", all temporary
      files have to be removed as well.
      </P
><P
>  <SPAN
CLASS="emphasis"
><I
CLASS="emphasis"
> So it may be a
      good idea to use ".deb_preunpacked" as extension for them.  And
      I would recommend using '--format=unzipped' for essential
      packages such as the kernel.</I
></SPAN
>
     </P
><P
>&#13;      If you like the idea, someone should help in changing 'dpkg' so that it would be
      able to install starting from 'foobar_2.deb_preunpacked'. And change APT
      so that it would interact with 'debdelta' to create the
      'foobar_2.deb_unpacked' files, and pass them to dpkg (and clean them properly).
      </P
></DIV
></DIV
><H3
CLASS="FOOTNOTES"
>Notes</H3
><TABLE
BORDER="0"
CLASS="FOOTNOTES"
WIDTH="100%"
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="5%"
><A
NAME="FTN.AEN190"
HREF="x182.html#AEN190"
><SPAN
CLASS="footnote"
>[1]</SPAN
></A
></TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="95%"
><P
>note though that <B
CLASS="command"
>debdelta-upgrade</B
> saves the
       recontructed debs in <TT
CLASS="filename"
>/var/cache/apt/archives</TT
>, and APT does not check
       them there, AFAICT</P
></TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="5%"
><A
NAME="FTN.AEN199"
HREF="x182.html#AEN199"
><SPAN
CLASS="footnote"
>[2]</SPAN
></A
></TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="95%"
><P
>the re-gzipped files are identical but for headers,
       (indeed gzip headers contain sometimes a timestamp ); but this is not a problem
       since the reconstructed gzipeed file is then piped again into 'xdelta3' or 'bsdiff' to rebuild the 'data.tar',
       so the header is fixed at that stage
      </P
></TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="5%"
><A
NAME="FTN.AEN201"
HREF="x182.html#AEN201"
><SPAN
CLASS="footnote"
>[3]</SPAN
></A
></TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="95%"
><P
>This is implemented in the python routine <CODE
CLASS="function"
>delta_gzipped_files</CODE
>.
      </P
></TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="5%"
><A
NAME="FTN.AEN219"
HREF="x182.html#AEN219"
><SPAN
CLASS="footnote"
>[4]</SPAN
></A
></TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="95%"
><P
>that is, discarding those that 
          are more than 70% of the corresponding deb</P
></TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="5%"
><A
NAME="FTN.AEN246"
HREF="x182.html#AEN246"
><SPAN
CLASS="footnote"
>[5]</SPAN
></A
></TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
WIDTH="95%"
><P
>this actually already happened some years ago, with libzip</P
></TD
></TR
></TABLE
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="x65.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="index.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="x277.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>debdelta-upgrade service</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
>&nbsp;</TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Todo</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>