Deciding which chunk of data to download next is a pretty complex task in the bittorrent world. You have to take into account a number of factors, such as:
1) You may want to prefer to download rare pieces first, maybe not.
2) You may want to pick a piece randomly, or maybe you want to download from the start of the file and get pieces in order
3) The user may set a higher priority on a certain file, so you should prefer its pieces.
4) The user may want to ignore certain files and never select their pieces.
Then imagine trying to NUnit test all the combinations and you'll find that it becomes very difficult to ensure the implementation is correct and impossible to extend with new behavior because the interactions become too complex.
The basic premise I had when redesigning this area of code was this: When I want to change the picking behaviour, I want to override one single method and then just slot the picker into the pipeline. So here's a reduced version of the PiecePicker class (3 methods instead of 10) and an example of how it's implemented.
public abstract class PiecePicker
{
protected PiecePicker(PiecePicker picker)
{
this.picker = picker;
}
void CheckOverriden()
{
if (picker == null)
throw new InvalidOperationException("This method must be overridden");
}
public virtual void Initialise(BitField bitfield, TorrentFile[] files, IEnumerable<Piece> requests)
{
CheckOverriden();
picker.Initialise(bitfield, files, requests);
}
public virtual bool IsInteresting(BitField bitfield)
{
CheckOverriden();
return picker.IsInteresting(bitfield);
}
public virtual MessageBundle PickPiece(PeerId id, BitField peerBitfield, List<PeerId> otherPeers, int startIndex, int endIndex, int count)
{
CheckOverriden();
return picker.PickPiece(id, peerBitfield, otherPeers, startIndex, endIndex, count);
}
}
public class RandomisedPicker : PiecePicker
{
Random random = new Random();
public RandomisedPicker(PiecePicker picker)
:base(picker)
{
}
public override MessageBundle PickPiece(PeerId id, BitField peerBitfield, List<PeerId> otherPeers, int startIndex, int endIndex, int count)
{
MessageBundle message;
int midpoint = random.Next(startIndex, endIndex);
if ((message = base.PickPiece(id, peerBitfield, otherPeers, midpoint, endIndex, count)) != null)
return message;
else
return base.PickPiece(id, peerBitfield, otherPeers, startIndex, midPoint, count);
}
}
Here's a usage example:
// StandardPicker provides an implementation for every method in PiecePicker
PiecePicker p = new RandomisedPicker(new StandardPicker);
So what happens is this:
1) p.PickPiece is called which results in RandomisedPicker.PickPiece being called
2) This splits the range between startIndex/endIndex into two and then makes two calls to base.PickPiece.
3) base.PickPiece will call standardPicker.PickPiece (because the 'picker' is non-null)
4) standardPicker.PickPiece will see if there are any pieces to request, and choose the first available one
Suppose I wanted to be able to ignore all the pieces which I already own, well, that's easy, I just use an IgnoringPicker (not a great name I'll admit):
public class IgnoringPicker : PiecePicker
{
BitField bitfield;
BitField temp;
public IgnoringPicker(BitField bitfield, PiecePicker picker)
: base(picker)
{
this.bitfield = bitfield;
this.temp = new BitField(bitfield.Length);
}
public override MessageBundle PickPiece(PeerId id, BitField peerBitfield, List<PeerId> otherPeers, int startIndex, int endIndex, int count)
{
// In binary operations: temp = peerBitfield & (~bitfield);
temp.SetAll(false).Or(peerBitfield).NAnd(bitfield);
return base.PickPiece(id, temp, otherPeers, startIndex, endIndex, count);
}
public override bool IsInteresting(BitField bitfield)
{
temp.SetAll(false).Or(bitfield).NAnd(this.bitfield);
return base.IsInteresting(temp);
}
}
Now i just change my usage to:
Picker picker = new StandardPicker ();
picker = new RandomisedPicker (picker);
picker = new IgnoringPicker (myBitfield, picker);
The biggest benefit is that each individual picking logic unit can very easily tested. They can then be combined in any order you want to change the picking behaviour. Random->Rarest->Standard would be different to Rarest->Random->Standard. The former will give you the rarest piece in a random set, the latter will give you a random piece from the rarest set.
The implementation of a logic unit is also trivial - you only have to override the behaviour you want to change rather than implementing a massive interface where for 90% of the methods you end up calling basePicker.Method anyway. So I'm quite happy with this change. This code already passes all the NUnit tests from the old picker as well as all the new tests I've written, so it should be going live in the near future. There's still some more work to be done before it's complete.
