[bittorrent] Introductory/endgame algorithms

Elliott Mitchell ehem at m5p.com
Thu Sep 29 23:03:18 EDT 2005

>From: Olaf van der Spek <olafvdspek at gmail.com>
> On 9/29/05, Elliott Mitchell <ehem at m5p.com> wrote:
> > > I think it's the other way around, the common case being multiple files.
> >
> > To tell the truth, no idea. I'm mostly after Linux CD images which tend
> > to be very large single files, I won't claim that is the majority. Other
> > things I've seen tend to be multi-hundred megabyte files. There needs to
> > be one more factor present to make this problematic, the file sizes need
> > to not be a factor of your page size.
> Only a single file needs to have a 'non-aligned' end to affect all
> files following.
> DVDs are frequently distributed as VIDEO_TS dir and I'm not sure if
> all file ends are aligned there.

I'm well aware of that fact. Though you can still do page-sized I/O
aligned to the file, though not well aligned to the torrent (yuck).

This is definitely something that should be considered in any V2 protocol

>From: Jari Sundell <sundell.software at gmail.com>
> On 9/29/05, Elliott Mitchell <ehem at m5p.com> wrote:
> > > I'm limiting the number of peers that can download a single piece to 5
> > in
> > > the endgame mode. With a 2 minute timeout this has shown itself to work
> > well
> > > in all cases I've encountered. Also the piece with fewest concurrent
> > > downloads is delegated next. Peers with a transfer speed less than 4kb/s
> > > only queue a single piece, while faster peers use a queue size of half
> > what
> > > they do in normal downloads.
> >
> > Uh, you need to clear this paragraph up. You're saying that you'll only
> > request blocks from a particular piece from a grouping of 5 peers?
> >
> > The second though is a bad idea. If the queue depth on the remote end is
> > ideal (zero or near zero), then you've just cut your download rate by
> > 50%.
> Sorry, there's some confusion of terminology here. I meant what you call
> blocks, but which the protocol part of the specification calls piece. You
> may ignore the rant though.

I was sticking to protocol terminology since that is the common frame of
reference for this mailing list. /If/ I'm reading your meaning correctly
I can see why it would help. Has the benefit of limiting the performance
degradation on those clients from randomized I/O.

I must still mention that the second is a bad idea since you're
decreasing performance on your high speed peers. With your kind of
bandwidth an RTT of 0.05s can result in a very high BDP.

> > I haven't considered doing this explicitly, I use mmap'ed files directly
> > and
> > > the kernel keeps the pages in memory if there's room. If the user wants
> > to
> > > preload the files, he may use dd or similar to dump them into /dev/null.
> >
> > Bad idea to do it that way. I doubt most OSes do read-ahead on mmap()ed
> > files, and for what BitTorrent is doing readahead is quite important.
> > Your best bet is use pread()/readv() on whole pieces when the first block
> > is requested, and ensure your buffer is page-aligned
> > (sysconf(_SC_PAGESIZE)).
> >
> > There are two key points here. First, when the first block of a piece is
> > requested, very probably subsequent blocks will be read (I'd even advise
> > adding a seek penalty each time a new piece is requested to prevent
> > deliberate attacks). By reading the whole piece you'll avoid a second
> > seek returning to fetch the rest of the piece, a crucial performance
> > factor. Second, by doing I/O to page-aligned boundaries the OS is free to
> > do copies by merely memory-maping the files in and doing zero-copy.
> Please don't call it a bad idea, it really isn't. Very few high performance
> programs that do a lot of disk IO use the read/write variants because they
> involve creating copies of the data. (With the exception of direct IO, but
> that's not widely supported)

Wrong. If your buffer is page-aligned and you're doing I/O to
page-aligned portions of a file, Linux will do a copy but by modifying
the page table. I'm less certain of FreeBSD doing the same, but I think
it does. If you're not doing large blocks I/O this isn't convenient, and
not all OSes will do the copy via page table.

> Accessing mmaped file regions do use read ahead, and you can even control
> certain aspects of it by using madvise. If you do "cat /proc/<pid>/maps" on
> linux, you'll see a list of mmap'ed files. It's very common in use for
> accessing file data, and definitely provides good performance. Usually much
> better than read/write.

Hmm, seems you've got better knowledge of what it can do than I do.
Perhaps (hmm, make that likely) better performance on many systems, but
on some OSes with the right preparation they're equivalent.

> Using mmap does lead to some rather complicated code due to the page
> alignment and chunks spanning multiple files, but I feel my code does layer
> that complexity well.

I don't envy you here.

> http://libtorrent.rakshasa.no/

Unfortunately two issues here. First, http://libtorrent.sourceforge.net/,
there is already a library of the same name out there. Second, despite
claims to the contrary, the world is not ruled by C++, quite a few new
things are written in C. Just because you're using C, doesn't mean you
aren't doing OO (sorry, rant time there).

(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \BS (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_CS\   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/

More information about the BitTorrent mailing list