[bittorrent] 'Rarest first' question.

Elliott Mitchell ehem at m5p.com
Fri Jun 30 01:28:21 EDT 2006


>From: Bruno Hertz <brrhtz at yahoo.de>
> Elliott Mitchell <ehem at m5p.com> writes:
> >>From: Bruno Hertz <brrhtz at yahoo.de>
> >> His motivation btw is better caching, to reduce disk seeks. That's why
> >> he basically wants to serialize the pieces to some extent, simply by
> >> downloading them in that order :)
> >
> > Is the motivation wrong though? Certainly with high-bandwidth, locality
> > of reference is a very serious issue. As you mention though, unless all
> > your peers are synchronized (and rarest first will tend to break this)
> > you'll have a problem with reads. This looks like an accidental feature
> > of having 256KB pieces and 32KB request blocks, mainly in addition to
> > keeping traffic from HAVEs down it also strongly encourages some locality
> > of reference.
> 
> I'm not questioning the motivation but the solution. The attempt to
> improve IO throughput in fact is very commendable. Question is how to
> achieve this without hurting BT.

Quite true, but you sounded to me like you didn't regard disk seek
performance as an issue in any way what so ever. Perhaps not a huge issue
yet, but it is likely to become a bigger issue as wide-area networks
become faster. Very much an issue for local transfers though.

> As it turns out, he has another solution in store which is writing
> packets as they're downloaded to disk and reshuffle them later. While
> not helping on the read side either, this approach does not bend the
> piece selection, so it sure is preferable.

If you have the space, merge-sorting is quite efficient. By avoiding
seeking the disk during writes, this likely does provide speed gains.
Given how many files are useless until totally reassembled, seems a very
worthwhile approach.

> >> I've been looking into this for about two weeks now and already got
> >> the impression developers implement anything but the mainline
> >> algorithms (ok, that's an exaggeration, but the tendency is definitely
> >> there).
> >
> > Make sure you realize that some sections of the specification are
> > required, while some are merely suggested. The over the wire protocol and
> > .torrent file arrangement are strictly defined. The choice of piece
> > selection order though is merely suggested.
> 
> Are you to say clients may download in any order they choose?
> Interesting interpretation of BT ...

Please find the words "must" anywhere in the mentions of rarest first.
Random order is *any* order, at which point any selection is valid by
the protocol. Notice too, that portion is untestable. You can look at the
over the wire and .torrent files and deterministically state that
something is valid or not. You cannot test for a random selection order
and so any is valid.

> >> You don't need to convince me. I have a math background, and to me it
> >> is intuitively obvious that rarest first very likely performs better
> >> than random selection and surely better than sequential. Finding the
> >> proper arguments though in discussions is not that easy, since there's
> >> all kinds of other random factors involved (initial peer set
> >> etc.).
> >
> > Try this on for size. Random selection tends to effectively provide for
> > maintaining diversity. In the general case I'd suggest use of weighted
> > random piece selection will perform best.
> 
> Random selection sure is the best approach if you have no live
> knowledge about how the other peers perform. Bitfields and 'have'
> messages provide such knowledge though, so it makes sense to utilize
> it.

Incorrect.

The protocol specification does not require clients to send HAVE
messages, nor provide a full bitfield. The specification tells you what
those messages mean and provides suggestions for how to use them, but a
client doesn't have to send them in order to conform to the BT protocol.

Having said that, in general those give you a rough estimate of peer
performance as most clients will send them, since they want to talk. Yet
there are a number of interesting things that can be done which degrade
the quality of that estimate. Suppression of HAVEs for pieces you're
known to already have is one such (pretty much you have to divide by the
fraction of pieces you have to correct for /this/, but other games can be
played as well).

> > Rarest first though is crucial to ensure survival. So the common
> > weight would be rare pieces to get a higher selection likelyhood
> > (single-copies pretty well being guarenteed selection).
> 
> That's a common misconception about rarest first, i.e. that it is
> primarily meant to increase piece availability and thus the chance of
> torrent survival. Better entropy is at least as much of a goal though.

That may be the effect, but I highly doubt it was the original goal. As
already pointed out, beyond a certain level of entropy, additional
entropy isn't useful. Once every piece is helf by at least six of your
neighbors, performance of those neighbors is more crucial than entropy.

> > For stream downloads, you merely add another weight; pieces nearer to the
> > current playback index are prefered over more distant pieces. A
> > psuedo-random number generator is a pretty good arbiter between these
> > two motivations. Distant pieces are valuable because you will eventually
> > play them, and peers ahead of you will be interested in downloading those
> > and in turn uploading.
> 
> And what might be gained by that? Increased likelyhood of live
> playback?  I'm not sure a streaming solution where, depending on
> you're weight, e.g. one out of 100 peers might be able to actually
> watch the stream live would be that much applauded.

The odds are very much better than that. Crucially there is a lot of
extra buffering involved. You end up with the torrent divided into three
areas.

The first segment is the portion already played for which you hopefully
have all the pieces. You're not really interested in these pieces anymore
as you won't replay them. OTOH you do keep them around as you can trade
those pieces to peers behind you in playback.

The second segment is a near-window of soon to be played pieces. Your
portion of this area is densely populated by pieces you *have*. You're
very interested in downloading any pieces in this area as you must soon
play them, but you can also trade them too.

The third segment is a portion well beyond the portion you're playing.
You won't soon play them, so you're not too interested in them, but if
you can't download anything else these will be valuable in time. These
can also be traded to peers who are well ahead of you in playback, that
have pieces you are really interested in.

You can estimate the rate at which download will complete. The trick is
to ensure the fully populated first area is sufficiently large that it
will grow to encompass the whole torrent before playback reaches the end.
The borderline between the first and second areas is where playback can
occur (beyond that you're missing pieces and cannot play).


-- 
(\___(\___(\______          --=> 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