BT客户端源码分析之四：PiecePicker 类（1）

转载自：http://blueidea.bokee.com/1497251.html

作者：小马哥

日期：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