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