[Debtorrent-devel] Fwd: BitTorrent Protocol Expansion (Google SoC)

[Cameron Dale]

---------- Forwarded message ----------
From: Cameron Dale <camrdale at gmail.com>
Date: Apr 6, 2007 11:08 AM
Subject: Re: BitTorrent Protocol Expansion (Google SoC)
To: Anthony Towns <aj at azure.humbug.org.au>


Anthony Towns wrote:
> On Thu, Apr 05, 2007 at 02:23:43PM -0700, Cameron Dale wrote:
>>>> "Proposal A"
>>>> "communicate all torrent information in the Packages file"
>>>> "pieces can no longer be numbered"
>> I think a same-ordered Packages file is something we definitely can't
>> depend on. If I download the Packages file today and download bar, then
>> bar updates overnight, and tomorrow you download the new Packages file
>> and try to download the new bar from me because I tell you I have piece
>> 6, there's going to be problems.
>
> Right, but pieces are related to a torrent, and if you're looking
> at tomorrow's Packages files, that's a different torrent anyway. The
> simplest example there might as well be:
>
>       Package: bar
>       Version: 2.3
>       Size: 1023
>
>       Package: foo
>       Version: 1.0
>       Size: 2045
>
> then:
>
>       Package: bar
>       Version: 2.3
>       Size: 1023
>
>       Package: baz
>       Version: 4.5
>       Size: 518
>
>       Package: foo
>       Version: 1.0
>       Size: 2045
>
> In which case if you want/have "foo 1.0" you're talking about piece 3
> on day two, instead of piece 2 on day one. (Packages files are almost always
> alphabetical by package name, fwiw)
>
> But if you're treating that as two different torrents (ie, a torrent
> per Packages file), then you're just participating in two torrents that
> share a couple of files on disk.
>
> That's probably necessary anyway, in order to treat testing and unstable
> as separate torrents, I guess; and possibly testing/i386 and testing/amd64
> depending on how arch:all packages get treated.

My idea for this proposal is that you don't have a new torrent every day,
instead you have a single torrent for every suite and architecture (separate
all) combination. From the proposal: "create a torrent for every combination of
suite (stable/testing/unstable) and architecture, including separate ones for
architecture:all and source." That torrent stays the same, even though the
Packages file changes every day, and new pieces get added. This allows you to
maintain communication between peers who have Packages files from
different days.

If you have a new torrent file each day, then in order for me, who downloaded
the Packages file today, to share pieces with you, who downloaded it yesterday,
I would have to participate in both torrents. Add in people who downloaded the
Packages file up to 100 days ago, and I'm now running 100 torrents just to share
with all of them. And I can now contact you through 99 of those torrents, since
you're also running them all. It's getting complicated.

Whether you call it a torrent or something else, you need a giant swarm of peers
all talking to each other, no matter what day they downloaded the Packages file
on, since they will have something like 90% of the pieces in common. And when
one says to another, I have package foo, they need to know they're talking about
the same version. Since peers within a torrent only exchange information in the
form of piece numbers, these need to uniquely identify a package AND version.

Of course, the person who downloaded the Packages file 100 days ago doesn't know
about some of the pieces that are now available in the swarm. But he could just
drop information he receives from newer peers about pieces he's unaware of
(since he doesn't want them), and other peers could assume that the shorter
bitfield they receive from him indicates that he doesn't have the newer pieces
(which he doesn't).

>> Things get even worse if a package
>> grows in size and requires a new piece, then all packages after it in
>> the Packages file are offset by one.
>
> Right, but I'd view that as a different Packages file, by definition. That
> way you can just use the sha1sum the uncompressed Packages file to
> identify the torrent, whether you get it from http://ftp.debian.org/,
> or a local mirror, or put it together from diffs or whatever.
>
>> Since these numbers are kind of arbitrary, I was suggesting we just do
>> away with them and instead use the SHA1 as the piece number. Then
>> instead of saying "I have piece 18001" you would say "I have piece
>> 9425fa8de16f6283365f6bee87f405da16a203e6". The only reason to have piece
>> numbers that I can see is for the BITFIELD communication (more below on
>> that).
>
> There's that, which I definitely agree on, and there's also that it
> might make implementation easier, since piece numbering is presumably
> a pretty fundamental assumption, that it'll be awkward to break.

I think it's possible to do though. Instead of storing an array of pieces you
have, you would just store a dictionary of hash values. But, as I said, bitfield
may prove necessary.

>> BITFIELD is useful though, so maybe numbering should be kept. The key is
>> whether it can be unique and not grow to too large a size. Some more
>> statistics are needed here, ;) such as how many new piece numbers would
>> we need per day.
>
> It depends what you're treating as your "torrent". You can look at the
> "Version:" lines in dists/sid/main/binary-i386/Packages.diff/*.gz (eg)
> to get some idea of how many updates there are -- by the looks of things
> it's anywhere from 12 to 223 per half-day, or about 122 per day averaged
> over the past week, which is maybe 43k per year, and an increase in the
> size of the bitfield by about 5kB each year. Of course we're in the last
> stages of a freeze at the moment, so that could be a wild underestimate.

These numbers definitely seem like it would be possible to keep unique piece
numbers for long periods of time before reuse. I think the release of a new
version might be the perfect time to start fresh from piece number 0. It's
probably possible to keep unique piece numbers for a given release (say 'etch')
all through the release's lifetime without ever having to reuse piece numbers,
especially since it will need very few new piece numbers once it becomes a
stable release.

>>>> "how do peers communicate BITFIELD information of all the pieces they
>>>>  have when the pieces are no longer numbered"
>>> Probably by sending a lot of "HAVE ..." notices?
>> Yeah, like a few thousand, every time you connect to a new peer? That
>> would probably mean a lot of wasted bandwidth and connections. If we use
>> the unique piece numbering I mentioned above, it could also grow to the
>> point where we have bitfields that are too long. BitTorrent currently
>> sends bitfields as "001010..." indicating that it has pieces 2 and 4,
>> but needs 0,1,3,5. So, our bitfields could grow to the point of being a
>> 100 KB in length or much more. It should be pretty easy to convert this
>> bit string into a more efficient Hex or even binary representation to
>> save on communication costs though.
>
> Hrm? I thought it was already a real bitfield? "The first byte in
> the bitfield corresponds to indices 0-7 from high bit to low bit,
> respectively" -- www.bittorrent.org/protocol.html

Sorry, my mistake. The bitfield is indeed already transmitted in binary form, so
transmitting a really long one would not be too cumbersome. I was thinking of
something else.

> There's currently about 20k packages in sid/binary-i386 (including
> arch:all) which makes the bitfield 2.5kB, afaics.

Seems small enough. If we use unique pieces like I mentioned, this could grow to
100,000 or more, which is only 12.5kB, but might warrant some compression,
especially since most of it (98%) will be 0's.

> Oh, other consideration: the client needs to keep track of availability
> for all its peers in memory, being able to use bitfields for that might
> still be worthwhile, even if they can't be in the protocol per se.

Right, storing the dictionary of pieces for all peers might become too much of a
memory hog. Again with 100,000 pieces, this might become large as well, so some
form of compression could be useful. Something to think about, anyway.

>> Just so you know, [...] Just something to think about.
>
> Well, hopefully tomorrow we find out slot numbers so we really can think
> about this stuff. :)

Any word on this yet? They're 2 days overdue already. Guess you can't complain
as they're the ones with the money in this.

I'll update my proposal with some of these unique piece number ideas, as I am
starting to think that is the way to go. Thanks for all the thoughts and ideas.

Cameron
-------------- next part --------------
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGFoygDx924g0gNq0RAmv+AJkBI2wnk+KHrxRgxWk6XmP0+BV5yQCcC/IG
KQ/Y03vPfUrgfIe4IwhlVts=
=WqiK
-----END PGP SIGNATURE-----