客户端源码分析之四：PiecePicker 类
作者：小马哥
日期：2004-7-2
rstevens At hotmail.com
版权所有，未经允许，不得转载
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 ValueError:
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
