Wednesday, December 17, 2008

PiecePicking and runtime method overriding

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.

26 comments:

Scott said...

I'll be honest, this is a really cool API design. Did you come up with this all by yourself, or did you find a similar pattern somewhere?

Anonymous said...

I struggled for quite a while to understand this (i hadn't found this blog, and your code isn't exactly well-commented ;), but once I did, I fell in love with it.

Seriously, this is a great way to do this. Nice job!

wow gold said...

Weekends to peopleig2tmean that they can have a two-day wowgold4europe good rest. For example, people gameusdcan go out to enjoy themselves or get meinwowgoldtogether with relatives and friends to talk with each storeingameother or watch interesting video tapes with the speebiewhole family.
Everyone spends agamegoldweekends in his ownmmoflyway. Within two days,some people can relax themselves by listening to music, reading novels,or watchingogeworld films. Others perhaps are more active by playing basketball,wimming ormmorpgvipdancing. Different people have different gamesavorrelaxations.
I often spend weekends withoggsalemy family or my friends. Sometimes my parents take me on a visit to their old friends. Sometimesgamersell I go to the library to study or borrow some books tommovirtexgain much knowledge. I also go to see various exhibition to broadenrpg tradermy vision. An excursion to seashore or mountain resorts is my favorite way of spending weekends. Weekends are always enjoyable for me.
igxe swagvaultoforu wowgold-usaignmax wowgoldlivebrogame thsaleGoldRockU

Anonymous said...

出会い喫茶出会いカフェテレクラ不倫セックスフレンドセフレ出会い出会い出会い掲示板出会い出会い出会い人妻風俗デリヘルデリバリーヘルス出会い出会い無料フィリピンライブチャットアダルトライブチャットデリヘル

Anonymous said...

不動産ソープランドアクセスカウンターコレステロール中性脂肪花粉症在宅ワーク内職在宅アルバイト乾燥肌ダイエット 食事サプリメント無料占い出会い山口クレジットカード現金化クレジット現金化ライブチャットフィリピンチャットレディパソコン在宅ワーク

Anonymous said...

出会い豊島区出会い北区出会い荒川区出会い板橋区出会い練馬区出会い足立区出会い葛飾区出会い江戸川区ニキビCholesterol水虫冷え性むくみ産後わきが車買取転職加齢臭

Anonymous said...

出会い愛知出会い秋田出会い青森出会い千葉出会い愛媛出会い福井出会い福岡出会い福島出会い岐阜出会い群馬出会い広島出会い北海道出会い兵庫出会い茨城出会い石川出会い岩手出会い香川出会い鹿児島出会い神奈川出会い高知

Anonymous said...

出会い熊本出会い京都出会い三重出会い宮城出会い宮崎出会い長野出会い長崎出会い奈良出会い新潟出会い大分出会い岡山出会い沖縄出会い大阪出会い佐賀出会い埼玉出会い滋賀出会い島根出会い静岡出会い栃木出会い徳島

Anonymous said...

出会い東京出会い鳥取出会い富山出会い和歌山出会い山形出会い山口出会い山梨出会い北九州出会い下関出会い川崎出会い神戸出会い久留米出会い水戸出会い名古屋出会い大牟田出会い埼玉出会い堺出会い仙台出会い横浜出会い横須賀出会い札幌出会い川崎

Anonymous said...

出会い堺出会い仙台出会い横浜出会い横須賀出会い札幌出会い千代田区出会い中央区出会い港区出会い新宿区出会い文京区出会い台東区出会い墨田区出会い江東区出会い品川区出会い目黒区出会い大田区出会い世田谷区出会い渋谷区出会い中野区出会い杉並区

Anonymous said...

福井出会い愛知出会い岐阜出会い静岡出会い三重出会い兵庫出会い大阪出会い和歌山出会い滋賀出会い京都出会い奈良出会い山口出会い鳥取出会い島根出会い岡山出会い広島出会い徳島出会い香川出会い愛媛出会い高知出会い

Anonymous said...

出会い札幌出会い函館出会い北海道出会い秋田出会い青森出会い岩手出会い東京出会い八王子出会い府中出会い調布出会い銀座出会い仙台出会い優良出会いサイトアダルト盗撮素人熟女エロアニメAV女優

Anonymous said...

出会い愛知出会い秋田出会い青森出会い千葉出会い愛媛出会い福井出会い福岡出会い福島出会い岐阜出会い群馬出会い広島出会い北海道出会い兵庫出会い茨城出会い石川出会い岩手出会い香川出会い鹿児島出会い神奈川出会い高知

Anonymous said...

出会い熊本出会い京都出会い三重出会い宮城出会い宮崎出会い長野出会い長崎出会い奈良出会い新潟出会い大分出会い岡山出会い沖縄出会い大阪出会い佐賀出会い埼玉出会い滋賀出会い島根出会い静岡出会い栃木出会い徳島

Anonymous said...

福井出会いカフェ愛知出会いカフェ岐阜出会いカフェ静岡出会いカフェ三重出会いカフェ兵庫出会いカフェ大阪出会いカフェ和歌山出会いカフェ滋賀出会いカフェ京都出会いカフェ奈良出会いカフェ山口出会いカフェ鳥取出会いカフェ島根出会いカフェ岡山出会いカフェ広島出会いカフェ徳島出会いカフェ香川出会いカフェ愛媛出会いカフェ高知出会いカフェ

Anonymous said...

出会い東京出会い大阪出会い福岡出会い兵庫出会い神奈川出会い宮城出会い千葉出会い愛知出会い埼玉出会い青森出会い岩手出会い秋田出会い山形出会い山口出会い東京出会い鳥取出会い富山出会い和歌山出会い山形

Anonymous said...

出会い奈良出会い滋賀出会い三重出会い和歌山出会い愛知出会い静岡出会い岐阜出会い広島出会い岡山出会い山口出会い島根出会い鳥取出会い富山出会い石川出会い福井出会い徳島出会い香川出会い愛媛出会い高知出会い福岡

Anonymous said...

セフレ奈良セフレ滋賀セフレ三重セフレ和歌山セフレ愛知セフレ静岡セフレ岐阜セフレ広島セフレ岡山セフレ山口セフレ島根セフレ鳥取セフレ富山セフレ石川セフレ福井セフレ徳島セフレ香川セフレ愛媛セフレ高知セフレ福岡

Anonymous said...

福井テレクラ愛知テレクラ岐阜テレクラ静岡テレクラ三重テレクラ兵庫テレクラ大阪テレクラ和歌山テレクラ滋賀テレクラ京都テレクラ奈良テレクラ山口テレクラ鳥取テレクラ島根テレクラ岡山テレクラ広島テレクラ徳島テレクラ香川テレクラ愛媛テレクラ高知テレクラ

Anonymous said...

福井セフレ愛知セフレ岐阜セフレ静岡セフレ三重セフレ兵庫セフレ大阪セフレ和歌山セフレ滋賀セフレ京都セフレ奈良セフレ山口セフレ鳥取セフレ島根セフレ岡山セフレ広島セフレ徳島セフレ香川セフレ愛媛セフレ高知セフレ

smallawei said...

免費視訊,煙火,煙火工廠,視訊,正妹視訊,真愛密碼,真愛密碼,煙火秀,煙火圖片,衣蝶,衣蝶,AV女優,AV女優,
煙火批發,小泉彩,小泉彩,情趣用品,鞭炮,live119論壇,蜂炮,視訊

Oci Beken said...

How about if i want it from the beginning?
if the first piece is not there than Download the first piece first.

酒店上班請找艾葳 said...

艾葳酒店經紀公司提供專業的酒店經紀, 酒店上班小姐,八大行業,酒店兼職,傳播妹,或者想要打工兼差打工,兼差,八大行業,酒店兼職,想去酒店上班, 日式酒店,便服店,制服酒店,ktv酒店,禮服店,整天穿得水水漂漂的,還是想去制服店日領上班小姐,水水們如果想要擁有打工工作、晚上兼差工作兼差打工假日兼職兼職工作酒店兼差兼差打工兼差日領工作晚上兼差工作酒店工作酒店上班酒店打工兼職兼差兼差工作酒店上班等,想了解酒店相關工作特種行業內容,想兼職工作日領假日兼職兼差打工、或晚班兼職想擁有鋼琴酒吧又有保障的工作嗎???又可以現領請找專業又有保障的艾葳酒店經紀公司!

艾葳酒店經紀是合法的公司工作環境高雅時尚,無業績壓力,無脫秀無喝酒壓力,高層次會員制客源,工作輕鬆,可日領現領
一般的酒店經紀只會在水水們第一次上班和領薪水時出現而已,對水水們的上班安全一點保障都沒有!艾葳酒店經紀公司的水水們上班時全程媽咪作陪,不需擔心!只提供最優質的酒店上班,酒店上班,酒店打工環境、上班條件給水水們。心動嗎!? 趕快來填寫你的酒店上班履歷表

水水們妳有缺現領、想要兼職、有缺錢的煩腦嗎?想到日本留學缺錢嗎?妳是傳播妹??想要擁有高時薪又輕鬆的賺錢,酒店和,假日打工,假日兼職賺錢的機會嗎??想實現夢想卻又缺錢沒錢嗎!??
艾葳酒店台北酒店經紀招兵買馬!!徵專業的酒店打工,想要去酒店的水水,想要短期日領,酒店日領,禮服酒店,制服店,酒店經紀,ktv酒店,便服店,酒店工作,禮服店,酒店小姐,酒店經紀人,
等相關服務 幫您快速的實現您的夢想~!!

Anonymous said...

JK人妻アニメ巨乳SM痴女熟女ナース盗撮素人エロ動画JK人妻アニメ巨乳熟女痴女ナースSM盗撮素人芸能芸能人芸能yourfilehostyourfilehostyourfilehost動画ファイルナビゲーターyourfilehostグラビアアイドルイラマチオyourfilehost
yourfilehostyourfilehostyourfilehostyourfilehost無修正yourfilehostyourfilehostアゲサゲパンチラパンストおっぱいYouTubeYouTubeYouTubeYouTubeYouTubeYouTubeYouTube

Anonymous said...

痴女熟女おっぱいおしりロリ手こき素人エロ動画おまんこおまんこおまんこおまんこおまんこおまんこおまんこおまんこ下着フェチ芸能麻美ゆまAV女優浜崎りお吉沢明歩桜木凛大沢佑香Rio高坂保奈美佐藤美紀つぼみ大橋未久佳山三花川上ゆう橘れもんアダルト動画エロ動画エロ動画ニコ動画ようつべようつべdmmユーチューブエロ動画えろつべ無料アダルト無修正月野りさ三村翔子希崎ジェシカ大塚咲JK人妻

Anonymous said...

痴女熟女おっぱいおしりロリ手こき素人エロ動画おまんこおまんこおまんこおまんこおまんこおまんこおまんこおまんこ下着フェチ芸能麻美ゆまAV女優浜崎りお吉沢明歩桜木凛大沢佑香Rio高坂保奈美佐藤美紀つぼみ大橋未久佳山三花川上ゆう橘れもんアダルト動画エロ動画エロ動画ニコ動画ようつべようつべdmmユーチューブエロ動画えろつべ無料アダルト無修正月野りさ三村翔子希崎ジェシカ大塚咲JK人妻

Hit Counter