Jigdo

Spreading the load of CD and DVD downloads

Steve McIntyre <steve@einval.com>

July 2005

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. 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.

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 sizes (bytes)	Jigdo sizes (bytes)	Size factor
164 CDs	104,789,962,752	237,360,605	441
26 DVDs	105,308,942,336	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 many of the 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/

Copyright 2005 Steve McIntyre <steve@einval.com>

Text distributable freely using the terms of the GNU General Public License,

Version 2.

2005-07-07T00:06:01