Jigdo - Spreading the load of CD and DVD downloads
==================================================

(c) 2005 Steve McIntyre <steve@einval.com>

Distribute freely using the terms of the GNU General Public License,
version 2.

What is Jigdo?
==============

Jigsaw Download (jigdo) is a tool designed to ease the distribution of
very large files over the internet, for example CD or DVD images. Its
aim is to make downloading the images as easy for users as a click on
a direct download link in a browser, while avoiding all the problems
that server administrators have with hosting and serving such large
files.

History
=======

Debian has long been distributing CD images of its software. As time
has gone on, this has become more and more problematic. Potato (v2.2)
took 3 CDs for each of its 7 architectures, and Woody (v3.0) took 6 or
7 CDs for each of its 11 architectures. For many users, even with
broadband connections, keeping an FTP or HTTP connection alive long
enough to download a 650MB file was problematic. Also, a significant
number of users (especially Debian developers) would already have most
of the contents of those CDs available locally, either from local
mirrors of the Debian archive, or from older versions of the
CDs. Re-downloading all the data again would not be ideal. Lastly,
mirror space was growing exponentially.

The first solution to the CD download problem was the Pseudo Image Kit
(PIK), written by Anne Bezemer at about the time of the Potato
release. He wrote two simple scripts, one to generate a list of files
included in a CD image and a second to simply stick those files
together into a "pseudo-image". To convert this pseudo-image into an
exact copy of the distributed image, you would run rsync to fill in
the gaps.

This method worked, but still had a few drawbacks, all due to that
final rsync step. The central server had to keep full copies of all
the ISO images, and had to cope with the load caused by clients
syncing their images. Rsync can be _very_ expensive! Also, clients had
to have a net connection available to be able to generate ISO
images. For many people, that could be a big problem - imagine a user
with a laptop on the road, or a user at a Linux show with limited disk
space, writing CDs to sell.

In 2002, Richard Atterer developed jigdo to solve those issues. It
caught on quickly, and ever since then it has been used by Debian as
the primary method of distribution for ISO images. It generally works
well, and is an effective way to allow people to download these ISO
images quickly and efficiently.

How does Jigdo work?
====================

Jigdo is more generic than the PIK. It works on the assumption that a
large file for distribution is primarily made up of smaller files,
along with some extra "padding". This works for CD/DVD ISO images (of
course), but could also be used for tar files and other applications
where the same assumptions hold.

Jigdo splits its data into two files, the "jigdo" file and the
"template" file.

The template file is the piece that contains most of the information
needed to recreate the output file:

<template file diagram>

The first part of the template file is a simple header for
identification purposes. Immediately after that are zero or more
compressed lumps of data, containing the "padding" that is used to
fill in gaps. After that comes the "description" of the output file -
a set of structures which describe the chunks of data that make it up.
Each structure contains either an MD5 checksum of the input file that
should fit next in the output image, or a reference to the compressed
data stored earlier in the template file. Right at the end of the
template file is a summary of the output image - its length and MD5
checksum.

There is still some information missing at this point - the template
file only contains MD5 information about the files it references, not
their names or where to find them. The jigdo file is where the rest of
the metadata is stored, including the location and MD5sum of the
template file, the full filenames to match the input files referenced
in that template file, and (importantly) where to find those input
files. The jigdo file is meant to be the primary download file for
Richard's jigdo-lite application, but many users will download both
parts in parallel anyway.

<jigdo file diagram>

To build the output image, the jigdo application starts at the first
block in the image description. It then walks forward through the
template file. For each description block, it reads in either the
appropriate file or a chunk of compressed template data and writes out
to the output image. This sequence terminates when the next
description block loaded is the summary block for the image
itself. For safety, the jigdo application should also calculate the
MD5 checksum of the image as it goes, so that it can verify the
integrity of the final image. On a typical modern PC, the I/O cost of
reading and writing files will outweigh the CPU time taken in the MD5
calculation, so this check should come almost for free.

How effective is Jigdo?
=======================

The jigdo format is a _very_ space efficient way to distribute ISO
images. For the recent Debian Sarge release, the total size of the
normal CD and DVD images is as follows:

           .iso size (total)      .jigdo/.template size (total)   reduction factor
164 CDs    104,789,962,752 bytes  237,360,605                     441
 26 DVDs   105,308,942,336 bytes  227,314,575                     463

The jigdo files are shipped gzipped, so the metadata is very
small. Most of the space in a template file is taken up by the
metadata sectors and inter-file gaps from the ISO image. In a typical
ISO image, most of that space is zero-filled, so the compressed data
in the template compresses very well!

Of course, to build a CD or DVD from the jigdo data the end user will
need to find the component files that make up the bulk of the
disc. They are already available from Debian mirrors all over the
world, unlike the full ISO images. Also, as the packages will be much
smaller files the cost of a dropped connection is much reduced.

Using jigdo as a CD distribution mechanism allows more of our mirrors
to also act as distribution points for the CDs. Debian is by far the
largest Linux distribution in terms of the disk space needed to mirror
it, and asking each mirror to host

  * 125 GB of packages / sources as files
  * 105 GB of packages / sources as CD images
  * 105 GB of packages / sources as DVD images

would simply cause mirrors to stop carrying Debian. Asking for 500 MB
on top of the 125 GB of Debian archive is much more likely to be
successful. More on this subject later.

Creating Jigdo files
====================

To create the jigdo and template files from a large image file, jigdo
needs the image and a list of possible files that might be components
within it. It calculates an "rsync" checksum of all the files listed,
then rolls through the image file a byte at a time, checking for the
largest input file that will match at that point. If no file matches,
it adds the first byte into an "unmatched" buffer that will become the
compressed template block, and advances onwards. If a file matches, an
entry for that file is added to the list of matched files ready to go
into the jigdo file at the end of the process.

Once the image file is exhausted, jigdo writes all the description
blocks into the template file, and all the MD5 match entries into the
jigdo file.

Although this process is generic, reliable and simple to follow, it
does have a MAJOR drawback - it is incredibly CPU intensive. In the
most common current application (creating jigdo files from Debian CD
images), it's a major bottleneck. During successive Debian releases,
this has become more and more of a problem.

Making Jigdo creation faster - Jigdo Template Export
====================================================

After some consideration, the source of (and the solution to) the
performance problem in jigdo was obvious. In the CD creation process,
temporary trees of files are setup, then mkisofs is called upon to
turn those trees into ISO images. Jigdo was then working backwards from
the ISO images, using a brute-force technique to determine what files
made up those images. This was clearly silly!

In May 2004 I started work on adding jigdo support to
mkisofs. Thankfully, mkisofs is reasonably modular internally, and the
code that actually writes data out was very easy to modify. In the
cases where mkisofs was creating metadata sectors, those sectors could
simply be passed straight through as template data. In the _single_
place where file data was read and written, mkisofs could just add the
filename to the list to go into the template and jigdo file later
on. Add some MD5 checksumming to taste, and within a few days mkisofs
was producing (mostly) valid jigdo/template file combinations. The
performance improvement over the original jigdo application was
staggering - initial tests suggested the new code was faster by a
factor of over 20!

There was another hurdle to overcome at that point - creating bootable
CDs for several of the architectures in Debian was a two stage
process: creating an ISO image, then running another program to setup
structures in the boot sector to point to the boot files. The new
mkisofs-jte application could not help on those architectures until
extra code was added to make bootable CDs directly. That took a little
extra time.

After several test cycles, we started using the new mkisofs-jte code
to create the weekly Debian testing CDs and DVDs. Some bugs were found
and fixed along the way, and in the end the CDs and DVDs for the
Debian 3.1 "Sarge" release were all made using JTE. This allowed us to
build a full set of CDs and DVDs (in all, 164 CDs and 26 DVDs) in just
over 24 hours on a reasonably-specified single PC. Using the original
jigdo program, it would have taken us almost a month!

Other improvements
==================

New client tools
----------------

JTE is a much faster re-implementation of the jigdo creation
tools. The next obvious step was to work on the client programs, those
used to regenerate an ISO image from the jigdo files. First was
"mkimage" - a very simple jigdo client that will recreate the ISO
image generally much faster than the original jigdo tools. "jigdump"
is a simple tool to help in debugging the layout of a template
file. "jigsum" and "jigit" combined are a simpler alternative to the
main jigdo download/assembly application.

Better compression
------------------

Another obvious thing to try was more aggressive compression of the
binary chunks in the template file. Currently released versions of
jigdo will only support gzip-compressed data. Both Richard and I have
added bzip2 support for newer versions of our jigdo tools, and at some
point in the near future we will move over to using bzip2 by
default. From initial testing, bzip2 will reduce the average size of a
template file by a further 10% to 20%, without significantly
increasing the time taken to for jigdo or ISO creation. The fact that
jigdo did not start off using bzip2 was a mere oversight by Richard!

Jigdoofus
=========

Even when using jigdo, an issue remains - if a mirror admin wishes to
allow people to download an ISO image, the image must be created
first. I wrote a perl CGI wrapper script around "mkimage" to allow
serving of images purely using the jigdo files, filling in component
file data as necessary from the local filesystem.

That worked, but did not satisfy the more general problem. Many people
use bittorrent to accelerate the download of ISO images, but
bittorrent requires that the original seed location has a full copy of
the file being transferred. Consider also an an end user who wants to
use a CD or DVD image (e.g. to write a disc). They currently still
have to find the disc space to create that image first. This can be a
real problem in some circumstances; DVD images are large! Exposing
full copies of the ISO images by creating them on the fly, as needed,
would be _very_ useful.

Jigdoofus is the answer to this. FUSE (Filesystems in USErland) is a
small kernel module that makes writing special-purpose filesystems
very easy in Linux. It deals with the hard work of interfacing with
the kernel, and exposes a clean, simple API via a library. Using FUSE,
jigdoofus presents a simple read-only filesystem. The vast majority of
filesystem calls can simply return EROFS (i.e. read-only filesystem)
when any attempt is made to write to the pseudo filesystem. Of the 20
functions supported by FUSE, only six filesystem functions actually
had to be implemented:

 * getattr
 * readlink
 * readdir
 * open (for reading only, of course)
 * read
 * statfs

Normally, jigdo client programs don't need to allow random access to
offsets within the output ISO image. However, a full filesystem
interface must support seeking and arbitrary-sized reads at arbitrary
offsets. The template file itself is laid out ready for client
programs to output the ISO image in a single stream, meaning that
random access to the data is not as efficient as it might be. To solve
this problem, jigdoodus uses a simple SQLite database backend to cache
information from the template file, to allow much faster lookups of
(offset, length) tuples.

Simple testing of the initial version of jigdoofus proved that the
concept could work. Quite a lot of caching was necessary to make
performance reasonable, otherwise the cost of decompressing the raw
template data severely limited performance. With sufficient caching,
performance through jigdoofus when reading a full ISO image is
approximately 10% slower than recreating that full image using
mkimage. Considering the extra functionality that jigdoofus allows,
that's a reasonable overhead.

Jigdoofus should allow selected Debian mirrors to also act as CD/DVD
image mirrors and bittorrent servers in the near future. There are
some more cleanups and bugfixes needed, but the prototype works well
today.

Downloads
=========

Jigsaw Download:   http://atterer.net/jigdo/
JTE / jigdoofus:   http://www.einval.com/~steve/software/JTE/
Debian CDs/DVDs:   http://cdimage.debian.org/debian-cd/