PiecePicker 用于實現“片斷選擇算法”，片斷選擇算法在《Incentives Build Robustness in BitTorrent》一文中有介紹，我把相關內容列出來。
BT的片斷選擇算法，綜合下面幾種策略。
l
嚴格的優先級
片斷選擇的第一個策略是：一旦請求了某個片斷的子片斷，那么該片斷剩下的子片斷優先被請求。這樣，可以盡可能快的獲得一個完整的片斷
l
最少的優先
每
個peer都優先選擇整個系統中最少的那些片斷去下載，而那些在系統中相對較多的片斷，放在后面下載，這樣，整個系統就趨向于一種更優的狀態。如果不用這
種算法，大家都去下載最多的那些片斷，那么這些片斷就會在系統中分布的越來越多，而那些在系統中相對較少的片斷仍然很少，最后，某些 peer
就不再擁有其它 peer 感興趣的片斷了，那么系統的參與者越來越少，整個系統的性能就下降。
l
隨機的第一個片斷
“最
少優先”的一個例外是在下載剛開始的時候。此時，下載者沒有任何片斷可供上傳，所以，需要盡快的獲取一個完整的片斷。而最少的片斷，通常只有某一個
peer擁有，所以，它可能比多個peers都擁有的那些片斷下載的要慢。因此，第一個片斷是隨機選擇的，直到第一個片斷下載完成，才切換到“最少優先”
的策略。
l
最后階段模式
有
時候，從一個速率很慢的peer那里請求一個片斷。在下載的中間階段，這不是什么問題，但是卻可能潛在的延遲下載的完成。為了防止這種情況，在最后階段，
peer向它的所有的peers們都發送某片斷的子片斷的請求，一旦某些子片斷到了，那么就會向其它peer發送cancel
消息，取消對這些子片斷的請求，以避免帶寬的浪費。實際上，用這種方法并沒有浪費多少帶寬，而文件的結束部分也一直下載的非常快。
下面是我在分析之前思考的兩個問題：
問題1：如何實現“嚴格優先級”
答案：記錄每個已經開始下載的片斷。優先選擇它們。
問題2：如何實現“最少優先”算法？也就是你如何去統計某個片斷在系統中最少？
答案：通過
have 消息（have消息請參看BT對等協議）來計算。在下載過程中，會不停的收到其它 peer 發來的 have
消息，每個have消息都表明對方擁有了某個片斷。那么，為每個片斷維護一個計數器，每收到一個have消息，相應的計數器加1。在選擇片斷的時候，計數
器最小的某個片斷被選中。
在實際代碼中，可以看到，變量started和seedstarted 是用來實現“嚴格優先級”的，它們記錄了那些已經開始下載的片斷。而變量 numinterests用來實現“最少優先”算法。
PiecePicker類的核心函數是 next() ，它綜合多種策略，來計算出下一個應該被選擇進行下載的片斷。
PiecePicker
類的難點是三個變量
numinterests、interests、pos_in_interests的作用。因為沒有任何注釋，我思考了很久才明白它們的作用，特別是
pos_in_interests。所以，在分析代碼之前，我結合例子來講解這三個變量的作用。
假設有三個片斷：
numinterests：
類型是list，每個片斷對應一項，記錄了每個片斷收到的 have 消息的個數。初始化的時候，numinterests = [0, 0, 0]。
interests：
類型是 list，它的每一項又是一個 list。例如在這個例子中，初始化的時候，interests = [ [0, 1, 2] ]，顯然，它只有一項。
interests 的作用是什么了？嗯，有點難以表達。大概是這樣的吧：所有未完成下載的片斷的索引號都保存在 interests，進行片斷選擇的時候，要用到 interests。我們看兩個例子：
1、interests = [ [0, 1], [2]]
2、interests = [ [1], [0, 2]]
在第一個例子中，片斷0、1位于 interests 的第0項，片斷2位于 interests的第1項。
在第二個例子中，片斷1位于位于 interests 的第0項，片斷0、2位于 interests的第1項。
無論哪種情況，都表明0、1、2三個片斷都還沒有下載完成。
那么，某個片斷到底應該處于 interests 中什么位置了？答案是根據該片斷收到的 have 消息個數，也就是 numinterests 的值。
例如，第一個例子中，說明片斷0、1收到的 have 個數都是0，所以處于 interests的第0項，而片斷2收到的 have
個數是1，所以處于第1項。而初始化的時候，interests =[ [0, 1, 2]]，說明片斷0、1、2收到的 have個數都是0。
奇怪，為什么要這樣設計了？答案就是“最少優先”的片斷選擇策略。我們看到，擁有越多
have 的片斷，在 interests 中，位置越靠后。在進行片斷選擇的時候，可能會從
interests中選一個片斷出來（為什么說可能了，一會可以看到，會優先采用其它策略，如果其它策略不能選一個出來，才會試圖從
interests 中選）。這樣，按照索引從小到大的順序，擁有 have 越少的片斷，越可能被選到。我們考慮這樣一個例子：
interests = [[2, 3], [5, 0, 1], [], [], [4]]
片斷2、3擁有0個 have，不能被選擇。（至少要有一個 have 才被考慮）。
片斷0、1、5都有1個have，所以會優先從它們中選擇一個。
片斷4擁有4個 have，所以最后被考慮。
pos_in_interests：
如上所述，擁有相同
have 個數的片斷，處于 interests
中的同一位置。例如上面這個例子，0、1、5都處于第1個位置。那么它們又根據什么原則進行先后排列了？答案是隨機排列。所以，既可能是0、1、5，也可
能是 1、5、0，或者其它。為了記錄某個片斷的確切位置，就需要用到 pos_in_interests了。它也是一個
list，每個片斷擁有一項，根據上面這個例子，應該是：
pos_in_interests = [1, 2, 0, 1, 0, 0]
看出什么來沒？呵呵
它的意思是，
片斷0是 [5, 0, 1] 的第1個
片斷1是 [5, 0, 1] 的第2個
片斷2是 [2, 3] 的第0個
片斷3是 [2, 3] 的第1個
片斷4是 [4] 的第0個
片斷5是 [5, 0, 1] 的第0個
就是這樣嘍，不知道我有沒有說清楚。
#
封裝“片斷選擇算法”
class
PiecePicker:
def
__init__(self, numpieces, rarest_first_cutoff = 1):
self.rarest_first_cutoff = rarest_first_cutoff
self.numpieces = numpieces #
片斷的個數
self.interests = [range(numpieces)]
self.pos_in_interests = range(numpieces)
self.numinterests = [0] * numpieces
self.started = []
self.seedstarted = []
self.numgot = 0 #
獲得了幾個片斷？
self.scrambled = range(numpieces)
shuffle(self.scrambled)
收到一個
have
消息的處理
def
got_have(self, piece):
if self.numinterests[piece] is None:
return
numint = self.numinterests[piece]
if numint == len(self.interests) - 1:
self.interests.append([])
numinterests
對應的值要加
1
。
self.numinterests[piece] += 1
調整
interests
和
pos_in_interests
self._shift_over(piece, self.interests[numint], self.interests[numint + 1])
丟失一個
have
消息？？？？？
def
lost_have(self, piece):
if self.numinterests[piece] is None:
return
numint = self.numinterests[piece]
self.numinterests[piece] -= 1
self._shift_over(piece, self.interests[numint], self.interests[numint - 1])
調整
interests
和
pos_in_interests
，前面已經分析過。
def
_shift_over(self, piece, l1, l2):
p = self.pos_in_interests[piece]
l1[p] = l1[-1]
self.pos_in_interests[l1[-1]] = p
del l1[-1]
newp = randrange(len(l2) + 1)
if newp == len(l2):
self.pos_in_interests[piece] = len(l2)
l2.append(piece)
else:
old = l2[newp]
self.pos_in_interests[old] = len(l2)
l2.append(old)
l2[newp] = piece
self.pos_in_interests[piece] = newp
為某個片斷發送過
requested
消息，用于“嚴格優先級”策略
def
requested(self, piece, seed = False):
if piece not in self.started:
把片斷索引號添加到
started
中
self.started.append(piece)
if seed and piece not in self.seedstarted:
self.seedstarted.append(piece)
#
如果某個片斷已經得到，那么調用這個函數
def
complete(self, piece):
assert self.numinterests[piece] is not None
self.numgot += 1
l = self.interests[self.numinterests[piece]]
p = self.pos_in_interests[piece]
l[p] = l[-1]
self.pos_in_interests[l[-1]] = p
del l[-1]
self.numinterests[piece] = None
try:
self.started.remove(piece)
self.seedstarted.remove(piece)
except Error:
pass
計算下一個被選擇的片斷
def
next(self, havefunc, seed = False):
bests = None
bestnum = 2 ** 30
首先根據“嚴格優先級”策略，從已經開始下載的片斷中選擇。
if seed:
s = self.seedstarted
else:
s = self.started
“嚴格優先級”策略是和“最少優先”策略結合起來使用的。也就是說，在滿足“嚴格優先”的片斷中，再去選擇一個滿足“最少優先”的片斷。注意，“最少優先”還有一個限制，就是如果一個片斷如果從來沒有收到過
have
消息（也就是計數是
0
），也不能被選擇。這個判斷由下面的
havefunc(i)
完成。
for i in s:
if havefunc(i):
if self.numinterests[i] < bestnum:
bests = [i]
bestnum = self.numinterests[i]
elif self.numinterests[i] == bestnum:
bests.append(i)
經過“嚴格優先級”和“最少優先”策略之后，可能返回多個候選片斷，從中隨機選擇一個，返回。
if bests:
從
bests
隨機返回一個值
return
choice(bests)
如果以上步驟，沒有選擇出一個片斷。那么隨機選擇一個。這大概就是“隨機的第一個片斷”的策略吧。因為
rarest_first_cutoff
默認是設置為
1
的。也就是說，在一個片斷都沒有獲得的情況下，才會選擇這種策略。如果
rarest_first_cutoff
設置為
10
，那么這個策略就可以叫做“隨機的前
10
個片斷”，呵呵。
if self.numgot < self.rarest_first_cutoff:
for i in self.scrambled:
if havefunc(i):
return i
return
None
如果不能采用“隨機的第一個片斷”測率，那么，
interests
終于派上用場了。到這里，終于明白
interests
為什么要用
numinterests
對應的值來進行定位了。還是“最少優先”的思想，因為那些收到
have
消息少的片斷，在
interests
中位置比較靠前，所以會優先被選擇到。
for i in xrange(1, min(bestnum, len(self.interests))):
for j in self.interests[i]:
if havefunc(j):
return
j
如果還選不出來，只好返回
None
了。
return None
def
am_I_complete(self):
return self.numgot == self.numpieces
誰來補充？
def
bump(self, piece):
l = self.interests[self.numinterests[piece]]
pos = self.pos_in_interests[piece]
del l[pos]
l.append(piece)
for i in range(pos,len(l)):
self.pos_in_interests[l[i]] = i
posted on 2007-01-19 00:22
苦笑枯 閱讀(254)
評論(0) 編輯 收藏 所屬分類:
P2P