[GNUnet-developers] gnunet-download changes

[Christian Grothoff]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi all!

Only :-) a year after the tree encoding was conceived, the implementation now 
is powerful (= convoluted) enough to actually take the full benefits of the 
tree encoding that we initially planned for. This has some minor implications 
on how gnunet-download behaves. Since I seem to periodically get requests to 
how the download works, let me take the opportunity to elaborate a bit...

The GNUnet encoding encodes the file in a Merkle/CHK-ish tree. Every node in 
the tree identifies all nodes below uniquely. The top-node is identified by 
the arguments given to gnunet-download. If a file is downloaded, the process 
must thus first receive the top node, which then describes the nodes on the 
next level below, and so forth until the leaves are reached. The leaves then 
contain the actual data of the file. 

In GNUnet prior to 0.4.0, an aborted download had to be resumed from scratch. 
This was wasteful since some blocks of the file may already be on the drive. 
Note that the blocks can arrive in random order, so it is not always that the 
first n blocks are present. In 0.4.x, we started to check for the leaf-blocks 
if the file on the drive matches the expectation that we had for the block 
(by encoding the block from the drive and comparing if it matches the reply 
we would expect from gnunetd). If the block matched, we would not bother to 
request it. This was much more efficient, but a resumed download would still 
have to download all the inner blocks again.

The first rewrite of the code in the 0.4.9 branch already did much better. It 
saves the inner blocks in filename.X files on the drive and is thus able to 
avoid downloading these blocks again if a maching inner block is found in the 
.X files. There is only one problem with this approach -- if in the meantime 
the .X files are removed (or if they were never there in the first place), 
gnunet-download still has to request them again.

Can we do better? Yes, we can. If no matching block is in the .X files, we can 
attempt to reconstruct (!) the IBlocks from the nodes underneith in the tree. 
This is essentially equivalent to encoding the existing file on the drive and 
testing if that results in the same file that is being requested. So if an 
IBlock is not found in .X, we try to reconstruct it from the blocks below. If 
the reconstruction fails (results in a different block), we really must 
request it from the network.

The effect of this procedure is of course that when a download is started, the 
code must first go though the existing file on the drive and check if the 
blocks already correspond to what we want to have. If the entire file matches 
exactly, 0 requests will be issued to gnunetd. The checking takes of course 
quite a bit of time when gnunet-download starts on a large file, but if 
successful, this will be a lot less time than the actual download takes. Note 
that since we do not have to update the gnunetd database (we are not actually 
inserting), this check is much faster than actually inserting a file.

How much can we save? An extreme case is a 50 MB file that has 1 byte 
corrupted (and all .X files are gone). If we download the file again, we will 
have to download the corrupted block and all the inner blocks above that 
block up to the top, a total of 4k. Before the latest patch, gnunet-download 
would have to downloaded more than 2 MB from the network -- just to check 
that all inner blocks actually match. I've illustrated which blocks would be 
requested in the new scheme in the attached png image. Note that while I used 
a binary tree for the illustration, GNUnet uses a 25-ary tree in the actual 
implementation.

Oh, and Igor, Jan Marco and Maestro: I also fixed a segfault in 
gnunet-download that got in my way :-). Looked like one that could have fit 
your reports (only another dozen to go, I know...)

Christian
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9vl8k9tNtMeXQLkIRApvpAKCI6JEc1Dhdr4zFh9hKo0tVDziZmwCfZz5U
P16gOlycS1M+zBG+Y3TrWyM=
=dfsB
-----END PGP SIGNATURE-----

fixup.png
Description: PNG image